論文の概要: Improved Regret Guarantees for Online Mirror Descent using a Portfolio of Mirror Maps

• arxiv url: http://arxiv.org/abs/2602.13177v1
• Date: Fri, 13 Feb 2026 18:37:26 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-16 23:37:54.081089
• Title: Improved Regret Guarantees for Online Mirror Descent using a Portfolio of Mirror Maps
• Title（参考訳）: ミラーマップのポートフォリオを用いたオンラインミラーダイスのためのレギュレット保証の改善
• Authors: Swati Gupta, Jai Moondra, Mohit Singh,
• Abstract要約: L_p$ と $L_p$ を補間する測地線に対して鏡写像を用いることで, 後悔の内在的な利得が得られることを示す。 特に,ブロックノルムに基づくミラーマップがOEGやOPGDに対して($d$で)証明可能な改善を達成できるような,オンライン凸最適化インスタンスのファミリを$mathbbRd$で構築する。
• 参考スコア（独自算出の注目度）: 3.3654644618480547
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: OMD and its variants give a flexible framework for OCO where the performance depends crucially on the choice of the mirror map. While the geometries underlying OPGD and OEG, both special cases of OMD, are well understood, it remains a challenging open question on how to construct an optimal mirror map for any given constrained set and a general family of loss functions, e.g., sparse losses. Motivated by parameterizing a near-optimal set of mirror maps, we consider a simpler question: is it even possible to obtain polynomial gains in regret by using mirror maps for geometries that interpolate between $L_1$ and $L_2$, which may not be possible by restricting to only OEG ($L_1$) or OPGD ($L_2$). Our main result answers this question positively. We show that mirror maps based on block norms adapt better to the sparsity of loss functions, compared to previous $L_p$ (for $p \in [1, 2]$) interpolations. In particular, we construct a family of online convex optimization instances in $\mathbb{R}^d$, where block norm-based mirror maps achieve a provable polynomial (in $d$) improvement in regret over OEG and OPGD for sparse loss functions. We then turn to the setting in which the sparsity level of the loss functions is unknown. In this case, the choice of geometry itself becomes an online decision problem. We first show that naively switching between OEG and OPGD can incur linear regret, highlighting the intrinsic difficulty of geometry selection. To overcome this issue, we propose a meta-algorithm based on multiplicative weights that dynamically selects among a family of uniform block norms. We show that this approach effectively tunes OMD to the sparsity of the losses, yielding adaptive regret guarantees. Overall, our results demonstrate that online mirror-map selection can significantly enhance the ability of OMD to exploit sparsity in online convex optimization.
• Abstract（参考訳）: OMDとその変種は、ミラーマップの選択に重要なパフォーマンスに依存するOCOの柔軟なフレームワークを提供する。 OPGD と OEG の基礎となる測地はどちらも OMD の特殊な場合においてよく理解されているが、任意の制約された集合に対して最適なミラーマップを構築する方法や、損失関数の一般族、例えばスパース損失(英語版)をどう構成するかについては、依然として挑戦的な未解決の問題である。 L_1$ と $L_2$ の間を補間する測地に対して鏡写像を用いることで、後悔して多項式ゲインを得ることができ、これは OEG (L_1$) や OPGD (L_2$) に限定することでは不可能である。 私たちの主な結果は、この質問に肯定的に答える。 ブロックノルムに基づくミラーマップは、以前の$L_p$($p \in [1, 2]$)補間よりも損失関数の空間性によく適応することを示す。 特に、ブロックノルムに基づくミラーマップが、疎損失関数に対するOPGとOPGDに対して($d$で)証明可能な多項式($d$で)改善を達成できるような、オンライン凸最適化インスタンス群を$\mathbb{R}^d$で構築する。 次に、損失関数の空間レベルが不明な設定に目を向ける。 この場合、幾何学の選択そのものがオンライン決定問題となる。 まず, OEG と OPGD の切り換えが線形後悔を招き, 幾何選択の本質的な難しさを浮き彫りにする。 この問題を解決するために,一様ブロックノルムの族の中から動的に選択する乗法重みに基づくメタアルゴリズムを提案する。 提案手法は,OMDを損失の分散度に効果的に調整し,適応的な後悔の保証を与えることを示す。 以上の結果から,オンラインコンベックス最適化において,オンラインミラーマップ選択によってOMDの空間性を活用する能力が著しく向上することが示唆された。

関連論文リスト

• Adaptive Matrix Online Learning through Smoothing with Guarantees for Nonsmooth Nonconvex Optimization [54.723834588133165]
  我々は,演算子AMLによる行列変数を用いたオンライン線形最適化について検討した。 プロジェクションを避ける2つの効率的な手法でこのフレームワークをインスタンス化する。 両手法とも, クローズドフォーム更新はシャンプーの後悔と一致し, 計算コストを大幅に削減することを示した。
  論文  参考訳（メタデータ） (2026-02-09T03:09:47Z)
• Online Mirror Descent for Tchebycheff Scalarization in Multi-Objective Optimization [14.970965673760427]
  OMD-TCHと呼ばれるチェシュスカラー化のためのオンラインミラー降下アルゴリズムを提案する。 我々は,OMD-TCHが,公正性制約下での合成問題とフェデレーション学習タスクの両方に有効であることを示す。
  論文  参考訳（メタデータ） (2024-10-29T05:58:33Z)
• Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
  本稿では,2段階の適応性を持つオンライン凸最適化手法を提案する。 我々は$mathcalO(log V_T)$, $mathcalO(d log V_T)$, $hatmathcalO(sqrtV_T)$ regret bounds for strong convex, exp-concave and convex loss function。
  論文  参考訳（メタデータ） (2023-07-17T09:55:35Z)
• Riemannian Projection-free Online Learning [5.918057694291832]
  プロジェクション操作は、オンライン勾配降下(OGD)のような最適化アルゴリズムにおける重要な要素である。 これは高次元の設定における計算上の制限や、不条件の制約セットを扱う際に悩まされる。 本稿では,曲面空間上でのオンライン測地線凸最適化において,線形後悔の保証を得る手法を提案する。
  論文  参考訳（メタデータ） (2023-05-30T18:22:09Z)
• Universal Online Convex Optimization Meets Second-order Bounds [74.0120666722487]
  ユニバーサルオンライン凸最適化のための簡単な戦略を提案する。 主要なアイデアは、オリジナルのオンライン機能を処理するための専門家のセットを構築し、線形化された損失に対してメタアルゴリズムをデプロイすることである。 このようにして、私たちはブラックボックスの専門家として、既成のオンライン問題解決者をプラグインして、問題依存の後悔の限界を提供することができます。
  論文  参考訳（メタデータ） (2021-05-08T11:43:49Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。