論文の概要: The Hidden Cost of Approximation in Online Mirror Descent

• arxiv url: http://arxiv.org/abs/2511.22283v1
• Date: Thu, 27 Nov 2025 10:09:07 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-12-01 19:47:55.499606
• Title: The Hidden Cost of Approximation in Online Mirror Descent
• Title（参考訳）: オンラインミラーダイスにおける近似の隠れたコスト
• Authors: Ofir Schlisselberg, Uri Sherman, Tomer Koren, Yishay Mansour,
• Abstract要約: オンラインミラー降下(OMD)は、最適化、機械学習、シーケンシャルな意思決定において多くのアルゴリズムの基盤となる基本的なアルゴリズムパラダイムである。 本研究では,不正確なOMDに関する系統的研究を開始し,正規化器の滑らかさと近似誤差に対する頑健さとの複雑な関係を明らかにする。
• 参考スコア（独自算出の注目度）: 56.99972253009168
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Online mirror descent (OMD) is a fundamental algorithmic paradigm that underlies many algorithms in optimization, machine learning and sequential decision-making. The OMD iterates are defined as solutions to optimization subproblems which, oftentimes, can be solved only approximately, leading to an inexact version of the algorithm. Nonetheless, existing OMD analyses typically assume an idealized error free setting, thereby limiting our understanding of performance guarantees that should be expected in practice. In this work we initiate a systematic study into inexact OMD, and uncover an intricate relation between regularizer smoothness and robustness to approximation errors. When the regularizer is uniformly smooth, we establish a tight bound on the excess regret due to errors. Then, for barrier regularizers over the simplex and its subsets, we identify a sharp separation: negative entropy requires exponentially small errors to avoid linear regret, whereas log-barrier and Tsallis regularizers remain robust even when the errors are only polynomial. Finally, we show that when the losses are stochastic and the domain is the simplex, negative entropy regains robustness-but this property does not extend to all subsets, where exponentially small errors are again necessary to avoid suboptimal regret.
• Abstract（参考訳）: オンラインミラー降下(OMD)は、最適化、機械学習、シーケンシャルな意思決定において多くのアルゴリズムの基盤となる基本的なアルゴリズムパラダイムである。 OMDイテレートは、最適化サブプロブレムの解として定義され、多くの場合、ほとんど解けず、アルゴリズムの不正確なバージョンに繋がる。 それでも、既存のOMD分析は通常、理想的なエラーフリー設定を前提としています。 本研究では,不正確なOMDに関する系統的研究を開始し,正規化器の滑らかさと近似誤差に対する頑健さとの複雑な関係を明らかにする。 正規化器が均一に滑らかな場合、エラーによる過剰な後悔に強く拘束される。 負のエントロピーは、線形後悔を避けるために指数関数的に小さな誤差を必要とするが、対数バリアーとツァリス正則化器は、誤差が多項式である場合でも頑健である。 最後に、損失が確率的であり、領域が単純性であるとき、負のエントロピーはロバスト性を取り戻すが、この性質は全ての部分集合に拡張されない。

関連論文リスト

• Early-Stopped Mirror Descent for Linear Regression over Convex Bodies [14.30754799752932]
  加法的ガウス雑音下での高次元線形回帰の設定について検討する。 その結果,未拘束の早期停止ミラー降下の最悪のリスクは,少なくとも凸体に拘束される最小2乗推定器のリスクであることがわかった。
  論文  参考訳（メタデータ） (2025-03-05T11:59:31Z)
• Error Feedback under $(L_0,L_1)$-Smoothness: Normalization and Momentum [56.37522020675243]
  機械学習の幅広い問題にまたがる正規化誤差フィードバックアルゴリズムに対する収束の最初の証明を提供する。 提案手法では,許容可能なステップサイズが大きくなったため,新しい正規化エラーフィードバックアルゴリズムは,各種タスクにおける非正規化エラーよりも優れていた。
  論文  参考訳（メタデータ） (2024-10-22T10:19:27Z)
• A Stochastic Approach to Bi-Level Optimization for Hyperparameter Optimization and Meta Learning [74.80956524812714]
  我々は,現代のディープラーニングにおいて広く普及している一般的なメタ学習問題に対処する。 これらの問題は、しばしばBi-Level Optimizations (BLO)として定式化される。 我々は,与えられたBLO問題を,内部損失関数が滑らかな分布となり,外損失が内部分布に対する期待損失となるようなii最適化に変換することにより,新たな視点を導入する。
  論文  参考訳（メタデータ） (2024-10-14T12:10:06Z)
• A Mirror Descent-Based Algorithm for Corruption-Tolerant Distributed Gradient Descent [57.64826450787237]
  本研究では, 分散勾配降下アルゴリズムの挙動を, 敵対的腐敗の有無で解析する方法を示す。 汚職耐性の分散最適化アルゴリズムを設計するために、(怠慢な)ミラー降下からアイデアをどう使うかを示す。 MNISTデータセットの線形回帰、サポートベクトル分類、ソフトマックス分類に基づく実験は、我々の理論的知見を裏付けるものである。
  論文  参考訳（メタデータ） (2024-07-19T08:29:12Z)
• Regularization and Optimal Multiclass Learning [10.168670899305232]
  この研究は、経験的リスク最小化が失敗する最も単純な設定における正規化の役割を特徴づけることである。 ワンインクルージョングラフ(OIG)を用いて、試行錯誤アルゴリズムの原理に相応しい最適な学習アルゴリズムを示す。
  論文  参考訳（メタデータ） (2023-09-24T16:49:55Z)
• Loss Minimization through the Lens of Outcome Indistinguishability [11.709566373491619]
  我々は凸損失と最近のOmnipredictionの概念について新しい視点を提示する。 設計上、Los OIは直感的かつ直感的に全滅を意味する。 一般化モデルから生じる損失の重要な集合に対する損失 OI は、完全な多重校正を必要としないことを示す。
  論文  参考訳（メタデータ） (2022-10-16T22:25:27Z)
• Benign Overfitting of Constant-Stepsize SGD for Linear Regression [122.70478935214128]
  帰納バイアスは 経験的に過剰フィットを防げる中心的存在です この研究は、この問題を最も基本的な設定として考慮している: 線形回帰に対する定数ステップサイズ SGD。 我々は、(正規化されていない)SGDで得られるアルゴリズム正則化と、通常の最小二乗よりも多くの顕著な違いを反映する。
  論文  参考訳（メタデータ） (2021-03-23T17:15:53Z)

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

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