技術要約：時変移動コストを伴うパラメータフリー動的後悔

1. 問題設定

本論文は、非定常な環境における**制約なしオンライン凸最適化（Unconstrained OCO）を扱っており、学習者が時変移動コスト（Time-varying movement costs）**を負担する設定を対象としている。

標準的なOCOの設定では、学習者は凸集合 $\mathcal{W}$（本研究では $\mathbb{R}^n$）から決定 $w_t$ を選択し、凸損失 $f_t(w_t)$ を被る。目標は、比較対象のシーケンス $(u_1, \dots, u_T)$ に対する**動的後悔（Dynamic Regret）**を最小化することである：
$$R_T(u_{1:T}) = \sum_{t=1}^T f_t(w_t) - \sum_{t=1}^T f_t(u_t)$$

本研究はこの問題に、連続する決定間の距離に比例する移動コストのペナルティを加えることで拡張している。決定的な点は、このコストを制御する係数 $\lambda_t$ が時変であり、かつ任意であることである。学習者の目的は、以下の**非対称動的後悔（Asymmetric Dynamic Regret）**を最小化することである：
$$R_T(u_{1:T}, \lambda_{1:T}) = \sum_{t=1}^T \left( f_t(w_t) - f_t(u_t) + \lambda_t \|w_t - w_{t-1}\| \right)$$
なお、この非対称な定式化において、比較対象のシーケンス $(u_t)$ は移動コストのペナルティを負わないため、この問題は対称的なバリアントよりも困難である。

主な課題は、以下の事前知識を必要としないパラメータフリー（比較対象適応型）アルゴリズムを設計することである：

1. 比較対象のノルム上界 $M = \max_t \|u_t\|$。
2. 比較対象のパス長 $P_T = \sum_{t=2}^T \|u_t - u_{t-1}\|$。
3. 勾配ノルムのシーケンス $\|g_t\|$。
4. 移動コスト係数のシーケンス $\lambda_t$。

2. 手法

著者らは、以下の3つの主要コンポーネントからなる階層的なアルゴリズム・フレームワークを提案している。

A. 時変正則化を用いた複合ミラー降下法 (Algorithm 1)

ベースとなるアルゴリズムは、**複合ミラー降下（Composite Mirror Descent）**の更新を利用する。各ラウンド $t$ において、勾配 $g_t$ と次の移動コスト $\lambda_{t+1}$ を観測した後、学習者は以下を最小化することで $w_{t+1}$ を更新する：
$$w_{t+1} = \arg\min_{w} \left( \langle g_t, w \rangle + D_\psi(w | w_t) + \phi_t(w) \right)$$

• 正則化関数 $\psi(w)$: 非有界な領域を扱うために設計された対数線形関数。
• 補正項 $\phi_t(w)$: $\beta_t^2 = (\|g_t\| + \lambda_{t+1})^2$ によってスケールされる時変二次項。この項は「動的な摩擦」として機能し、イテレートを安定させる。移動コストや勾配が高いときはペナルティが増加して更新を制限し、低いときはペナルティを緩和する。

B. パラメータフリー・メタアルゴリズム (Algorithm 2)

$M, P_T$, および勾配や移動のスケールに関する事前知識を排除するために、著者らは異なる学習率 $\eta_i$ を持つ Algorithm 1 の並列インスタンスのグリッドを維持するメタアルゴリズムを採用している。

• 学習者は全インスタンスからの決定の総和をプレイする。
• 総後悔は、「最適な $\eta$」を近似する「最良の」インスタンスの後悔と、他のインスタンスによる小さな加法的コストに分解される。
• 結果: これにより、後悔の境界 $\tilde{O}\left( \sqrt{(M + P_T) \sum_{t} (\|g_t\|^2 + \lambda_{t+1}^2) \|u_t\|} \right)$ が得られる。
• 限界: この境界は移動コストに対して二次的に依存しており、勾配が小さく移動コストが大きいレジームにおいては劣目標である。

C. 適応的ファーストオーダー削減 (Algorithm 3)

移動コストに対する依存度を二次から一次へと改善するために、著者らは**適応的バッチング（Adaptive Batching）**メカニズムを導入している。

• メカニズム: アルゴリズムはエポックにわたって勾配をバッファ $H_\tau$ に蓄積する。蓄積された勾配ノルム $\|H_\tau\|$ が現在の移動コスト $\lambda_{t+1}$ を超えたときにのみ、ベース学習者への更新をトリガーする。
• 論理: 移動コストが高い場合、アルゴリズムは「信号」（勾配）が「コスト」を正当化できるほど十分に強くなるまで待機する。
• 結果: これにより、移動コストに対する後悔の依存度が $\lambda^2$ から $\lambda \|g\|$ へと減少する。

3. 主な貢献

1. 時変コストを伴う初のパラメータフリー動的後悔: 本論文は、任意の時変移動コストを伴う制約なし OCO に対する、初の比較対象適応的な動的後後悔の境界を確立した。
2. 最適な適応性: 提案されたアルゴリズムは、以下の要素に対して同時に適応する：
   • 比較対象の複雑性 ($M$ および $P_T$)。
   • 実現された勾配シーケンス ($\|g_t\|$)。
   • 時変移動係数 ($\lambda_t$)。
3. 改善された移動コスト依存度: 適応的バッチング戦略（Algorithm 3）を導入することで、移動コストに対する後悔のスケールを $\lambda^2$ から $\sum (\|g_t\|^2 + \lambda_t \|g_t\|) \|u_t\|$ へと改善した。これは、勾配が小さいレジームにおいて、従来の二次的な境界よりも大幅な改善である。
4. 他問題への新たな還元: 本フレームワークは、他のオンライン学習問題を、時変移動コストの設定へと翻訳することで解決するためのプリミティブ（基礎的な道具）として示されている：
   • 遅延フィードバックを伴う OCO: 欠落している勾配の数を移動コストのスケールとして扱う。
   • 時変メモリを伴う OCO: メモリ長の変動を時変移動コストにマッピングする。

4. 主な結果

理論的保証

Algorithm 3（改良版）について、本論文は以下の動的後悔を保証する：
$$\tilde{O}\left( (M + P_T)L + \sqrt{(M + P_T) \sum_{t=1}^T (\|g_t\|^2 + \lambda_t \|g_t\|) \|u_t\|} \right)$$
ここで、$L$ は $G + \lambda_{\max}$ に関連するリプシッツ的定数である。

応用 1: 遅延フィードバック

著者らは、$\lambda_t = G |m_t|$（$|m_t|$ は時刻 $t$ における欠落している勾配の数）と設定することで、遅延フィードバックを伴う OCO を本設定に還元した。

• 結果: $\tilde{O}\left( (M + P_T)L + G\sqrt{(M^2 + MP_T)(T + d_{\text{tot}})} \right)$ のパラメータフリー動的後悔を達成した。
• 利点: 非有界な領域を扱い、かつ「順序通り」のフィードバックという制限的な仮定を必要とせずに、最大遅延 $d_{\max}$ ではなく総遅延 $d_{\text{tot}}$ に対してよりタイトな依存関係を実現することで、先行研究（例：Wan et al., 2024）を改善している。

応用 2: 時変メモリ

著者らは、時変メモリ（損失が過去 $b_t$ 個の決定に依存する場合）を伴う OCO を本設定に還元した。

• 結果: $\tilde{O}\left( (M + P_T)L + \sqrt{M(M + P_T)(H^2 T + GH \sum b_t^2)} \right)$ の後悔境界を得た。
• 利点: これは、非有界な領域の仮定を取り除き、メモリ長のシーケンスに対する依存関係を精緻化した、非有界 OCO における初の時変メモリの動的後悔保証である。これは Zhao et al. (2023) を改善している。

5. 重要性と主張

本論文は、その結果がオンライン学習におけるいくつかの困難な方向性を統合したものであると主張している：

• 統合: 本研究は、制約なし最適化、動的後悔、および移動コストの間の溝を埋めるものである。これら三者の組み合わせはこれまで未探索であった。
• 汎用性: 本フレームワークは、移動コストを伴う OCO が強力なプリミティブであることを示している。「欠落した情報」（遅延フィードバックにおいて）や「メモリ依存関係」（メモリ依存において）を移動ペナルティとして解釈するだけで、これらの複雑な設定に対して最適な動的後悔の境界を導出できる。
• 最適性: 著者らは、パス長 $P_T$ および比較対象のノルムに対する依存関係が（対数因子を除いて）ミニマックス最適であり、移動コストに対する一次の依存性は、変動するペナルティがある設定で最適性を達成するために必要な精緻化であると主張している。
• 実用性: アルゴリズムは効率的であり、標準的なパラメータフリー OCO アルゴリズムの計算量と一致する $O(d \log T)$ の計算量を、各ラウンドあたりで必要とする。

本研究は、凸最適化の範囲外の問題を解決することや、現実世界のデータセットに対する実験的な検証を提供することを目的としたものではなく、理論的な保証と還元に焦点を当てている。