2025-11-18T22:10:13.514792

Time-Varying Optimization for Streaming Data Via Temporal Weighting

Abrar, Michelusi, Larsson

Classical optimization theory deals with fixed, time-invariant objective functions. However, time-varying optimization has emerged as an important subject for decision-making in dynamic environments. In this work, we study the problem of learning from streaming data through a time-varying optimization lens. Unlike prior works that focus on generic formulations, we introduce a structured, \emph{weight-based} formulation that explicitly captures the streaming-data origin of the time-varying objective, where at each time step, an agent aims to minimize a weighted average loss over all the past data samples. We focus on two specific weighting strategies: (1) uniform weights, which treat all samples equally, and (2) discounted weights, which geometrically decay the influence of older data. For both schemes, we derive tight bounds on the ``tracking error'' (TE), defined as the deviation between the model parameter and the time-varying optimum at a given time step, under gradient descent (GD) updates. We show that under uniform weighting, the TE vanishes asymptotically with a $\mathcal{O}(1/t)$ decay rate, whereas discounted weighting incurs a nonzero error floor controlled by the discount factor and the number of gradient updates performed at each time step. Our theoretical findings are validated through numerical simulations.

academic

ストリーミングデータの時変最適化：時間加重法

基本情報

論文ID: 2510.13052
タイトル: Time-Varying Optimization for Streaming Data Via Temporal Weighting
著者: Muhammad Faraz Ul Abrar (アリゾナ州立大学)、Nicolò Michelusi (アリゾナ州立大学)、Erik G. Larsson (リンショーピング大学)
分類: cs.LG cs.AI cs.SY eess.SP eess.SY math.OC
発表日: 2025年10月15日 (arXiv プレプリント)
論文リンク: https://arxiv.org/abs/2510.13052

要約

従来の最適化理論は固定的で時間不変の目的関数を扱っています。しかし、時変最適化は動的環境における意思決定の重要なテーマとなっています。本論文は時変最適化の観点からストリーミングデータ学習問題を研究しています。一般的な定式化に焦点を当てた先行研究とは異なり、時変目的の構造化された重み付けベースの定式化を導入し、ストリーミングデータソースを明示的に捉えています。ここで、エージェントは各時間ステップで過去のすべてのデータサンプルの加重平均損失を最小化することを目指しています。2つの特定の重み付け戦略に焦点を当てています：(1) 均一重み付け（すべてのサンプルを等しく扱う）、(2) 割引重み付け（旧データの影響を幾何学的に減衰させる）。両方のスキームについて、勾配降下法(GD)更新下での「追跡誤差」(TE)の厳密な界を導出しました。TEはモデルパラメータと与えられた時間ステップの時変最適解との偏差として定義されます。均一加重下では、TEはO(1/t)の減衰率で漸近的に消失することを証明しました。一方、割引加重は割引因子と各時間ステップで実行される勾配更新回数によって制御される非ゼロの誤差下界を生成します。

研究背景と動機

問題定義

本論文が解決する核心的な問題は、ストリーミングデータ環境における時変最適化学習問題です。具体的には：

従来の最適化の限界：古典的機械学習は静的目的関数を最適化し、静的データ分布を仮定していますが、現実世界のソリューションは動的に進化する環境で動作します
ストリーミングデータの課題：データは順序立てて到着し、目的関数は時間とともに進化し、非定常最適化問題をもたらします
計算上の制約：リアルタイムまたはリソース制限設定では、各時間ステップで限定回数の更新のみが実行可能です

重要性

この問題は複数の重要な応用分野で重要な意義を持ちます：

自動運転車両における移動ロボット追跡
移動目標の位置推定
ポートフォリオ最適化
変動する金融市場におけるリスク管理
時変システムダイナミクスのコントローラ適応

既存手法の限界

一般的定式化の緩い界：ほとんどの既存研究は一般的な時変定式化に焦点を当てており、ストリーミングデータの固有構造を無視し、追跡誤差の緩い界をもたらす可能性があります
構造化分析の欠如：既存手法はストリーミングデータの重み付け構造を明示的に活用してより厳密な性能界を得ていません
理論と実践の乖離：継続学習分野の手法はほとんど経験的であり、理論的基礎が不足しています

核心的貢献

構造化重み付け定式化の提案：ストリーミングデータの構造を明示的に捉える時変目的関数を導入し、すべての過去のサンプル損失の加重平均として定義
2つの重み付け戦略の理論分析：
- 均一重み付け：追跡誤差がO(1/t)速度で漸近的に消失することを証明
- 割引重み付け：明示的な非ゼロ漸近追跡誤差界を導出
厳密な界の導出：ストリーミングデータ構造を活用して、既存の一般的な時変分析よりも厳密なTE界を取得
理論と実験の検証：数値シミュレーションを通じて理論的発見の有効性を検証

方法の詳細

タスク定義

単一エージェント（エッジまたはクラウドサーバーなど）が時変機械学習モデルパラメータを追跡することを目指す学習設定を考えます：

入力：各反復t≥1で、エージェントは新しいデータサンプル(x_t, y_t)を受け取ります
出力：モデルパラメータw_t、累積データの加重平均損失を最小化
制約：各時間ステップで最大E回の勾配更新のみ実行可能

核心的な数学公式

時変目的関数： $w_t^* = \arg\min_{w \in \mathbb{R}^d} F_t(w), \quad \text{ここで} \quad F_t(w) = \sum_{i=1}^t a_i(t)f_i(w)$

ここで：

$a_i(t)$ は時間tにおける第iサンプルの重み
$f_i(w)$ は第iデータサンプルの損失関数
重みは以下を満たします： $0 \leq a_i(t) \leq 1$ かつ $\sum_{i=1}^t a_i(t) = 1$

勾配降下法更新： $w_{t,k+1} = w_{t,k} - \eta\nabla F_{t+1}(w_{t,k}) = w_{t,k} - \eta\sum_{i=1}^{t+1} a_i(t+1)\nabla f_i(w_{t,k})$

追跡誤差の定義： $\text{TE}(t) = \|w_t - w_t^*\|$

2つの重み付け戦略

1. 均一重み付け

すべての $i = 1, \ldots, t$ に対して $a_i(t) = 1/t$ を設定し、目的関数は以下のようになります： $F_{t+1}(w) = \frac{t}{t+1}F_t(w) + \frac{1}{t+1}f_{t+1}(w)$

2. 割引重み付け

幾何学的割引を使用します： $a_i(t) = \frac{1-\gamma}{1-\gamma^t}\gamma^{t-i}$ 、ここで $0 < \gamma < 1$ は割引因子です。

技術的革新点

構造化分析：一般的な時変最適化とは異なり、ストリーミングデータの重み付け構造を明示的に活用
最小化子ドリフト分析： $\|w_{i+1}^* - w_i^*\|$ の分析を通じて目的関数の変化を理解
再帰的誤差分析：誤差進化を追跡するための再帰関係を確立

理論分析

基本的仮定

仮定1（L-滑らかさとμ-強凸性）：各データサンプルの損失関数は以下を満たします：

$\|\nabla f_t(x) - \nabla f_t(y)\| \leq L\|x-y\|$
$f_t(y) \geq f_t(x) + \nabla f_t(x)^T(y-x) + \frac{\mu}{2}\|y-x\|^2$

仮定2（有界最小化子）： $\|w_t^*\| \leq C$ がすべてのtに対して成立するような $C > 0$ が存在します。

主要な理論結果

均一重み付けの追跡誤差

命題1：均一重み付けに対して、追跡誤差は以下を満たします： $\text{TE}(t) \leq \alpha^t\|w_0 - w_1^*\| + \frac{C'A}{t}$

ここで $\alpha = (1-\eta\mu)^E < 1$ 、 $C' = (1+\sqrt{L/\mu})\frac{LC}{\mu}$ です。

重要な結論：TEはO(1/t)速度で減衰し、漸近追跡誤差はゼロです。

割引重み付けの追跡誤差

命題2：割引重み付けに対して、漸近追跡誤差は以下を満たします： $\text{ATE}_\gamma = \limsup_{t\to\infty} \|w_t - w_t^*\| \leq \left(1+\sqrt{\frac{L}{\mu}}\right)\frac{LC}{\mu} \cdot \frac{(1-\gamma)\alpha}{1-\alpha}$

重要な結論：非ゼロの誤差下界が存在し、割引因子γと勾配更新回数Eによって制御されます。

実験設定

データ生成

スカラー二次損失関数を使用します： $f_t(w) = \frac{\mu}{2}(w-c_t)^2$

パラメータ設定：

$c_t$ は有界ランダムウォークで生成： $c_{t+1} = \max(-C_{\max}, \min(c_t + z_{t+1}, C_{\max}))$
$z_t \sim \mathcal{N}(0, \sigma^2)$ 、 $C_{\max} = 100$ 、 $\sigma^2 = 100$ 、 $\mu = 0.1$