論文の概要: The Statistical Complexity of Early-Stopped Mirror Descent
- arxiv url: http://arxiv.org/abs/2002.00189v2
- Date: Thu, 27 Aug 2020 15:45:06 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-05 00:36:36.975783
- Title: The Statistical Complexity of Early-Stopped Mirror Descent
- Title(参考訳): 早期停止ミラー降下の統計的複雑性
- Authors: Tomas Va\v{s}kevi\v{c}ius, Varun Kanade, Patrick Rebeschini
- Abstract要約: 早期停止ミラー降下アルゴリズムにより達成される過剰リスクの統計的保証について検討する。
正方形損失の凸性を特徴づける不等式を完遂することにより、オフセットラデマッハ複素数とミラー降下法のポテンシャルベース収束解析との内在的リンクを同定する。
- 参考スコア(独自算出の注目度): 27.393821783237186
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Recently there has been a surge of interest in understanding implicit
regularization properties of iterative gradient-based optimization algorithms.
In this paper, we study the statistical guarantees on the excess risk achieved
by early-stopped unconstrained mirror descent algorithms applied to the
unregularized empirical risk with the squared loss for linear models and kernel
methods. By completing an inequality that characterizes convexity for the
squared loss, we identify an intrinsic link between offset Rademacher
complexities and potential-based convergence analysis of mirror descent
methods. Our observation immediately yields excess risk guarantees for the path
traced by the iterates of mirror descent in terms of offset complexities of
certain function classes depending only on the choice of the mirror map,
initialization point, step-size, and the number of iterations. We apply our
theory to recover, in a clean and elegant manner via rather short proofs, some
of the recent results in the implicit regularization literature, while also
showing how to improve upon them in some settings.
- Abstract(参考訳): 近年,反復勾配に基づく最適化アルゴリズムの暗黙的正則化特性を理解することへの関心が高まっている。
本稿では,線形モデルとカーネル手法の2乗損失を伴う非正規化経験的リスクに適用した早期停止ミラー降下アルゴリズムにより達成される余剰リスクの統計的保証について検討する。
正方形損失の凸性を特徴づける不等式を完遂することにより、オフセットラデマッハ複素数とミラー降下法のポテンシャルベース収束解析との内在的リンクを同定する。
本報告では,ミラーマップの選択,初期化点,ステップサイズ,イテレーション数のみに依存する関数クラスのオフセット複素度の観点から,ミラー降下の繰り返しによって追跡される経路に対する過大なリスク保証を直ちに得る。
この理論を比較的短い証明を通じてクリーンでエレガントな方法で復元するために適用し、暗黙の正規化文学における最近の結果のいくつかを、いくつかの設定で改善する方法を示している。
関連論文リスト
- A Mirror Descent-Based Algorithm for Corruption-Tolerant Distributed Gradient Descent [57.64826450787237]
本研究では, 分散勾配降下アルゴリズムの挙動を, 敵対的腐敗の有無で解析する方法を示す。
汚職耐性の分散最適化アルゴリズムを設計するために、(怠慢な)ミラー降下からアイデアをどう使うかを示す。
MNISTデータセットの線形回帰、サポートベクトル分類、ソフトマックス分類に基づく実験は、我々の理論的知見を裏付けるものである。
論文 参考訳(メタデータ) (2024-07-19T08:29:12Z) - Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
本稿では,ニューラルネットワークトレーニングを安定化(大規模)するための原理的手法として,線形アヘッドの理論解析を提案する。
最適化過程の不安定性は、しばしば損失ランドスケープの非単調性によって引き起こされるものであり、非拡張作用素の理論を活用することによって線型性がいかに役立つかを示す。
論文 参考訳(メタデータ) (2023-10-20T12:45:12Z) - Implicit Regularization for Group Sparsity [33.487964460794764]
正方形回帰損失に対する勾配勾配は, 明示的な正則化を伴わずに, 群間隔構造を持つ解に偏りを示す。
一般雑音設定における回帰問題の勾配ダイナミクスを解析し,最小最適誤差率を求める。
サイズ 1 群の退化の場合、我々の手法は疎線形回帰の新しいアルゴリズムを生み出す。
論文 参考訳(メタデータ) (2023-01-29T20:54:03Z) - Vector-Valued Least-Squares Regression under Output Regularity
Assumptions [73.99064151691597]
最小二乗回帰問題を無限次元出力で解くために,還元ランク法を提案し,解析する。
提案手法の学習バウンダリを導出し、フルランク手法と比較して統計的性能の設定を改善する研究を行う。
論文 参考訳(メタデータ) (2022-11-16T15:07:00Z) - Robust Imitation via Mirror Descent Inverse Reinforcement Learning [18.941048578572577]
本稿では,制約付き凸問題の反復解である報酬関数列を予測することを提案する。
提案したミラー降下更新規則は,ブレグマンの発散を最小化できることを示す。
我々のIRL法は, 既存手法よりも高い性能を示した。
論文 参考訳(メタデータ) (2022-10-20T12:25:21Z) - Optimal Rates for Random Order Online Optimization [60.011653053877126]
敵が損失関数を選択できるカテットガルバー2020onlineについて検討するが、一様にランダムな順序で提示される。
2020onlineアルゴリズムが最適境界を達成し,安定性を著しく向上することを示す。
論文 参考訳(メタデータ) (2021-06-29T09:48:46Z) - Implicit Regularization in Matrix Sensing via Mirror Descent [29.206451882562867]
本研究では,行列検出における非正規化経験的リスクに対する離散時間ミラー降下法について検討した。
フルランク分解パラメトリゼーションによる勾配降下はミラー降下の1次近似であることを示す。
論文 参考訳(メタデータ) (2021-05-28T13:46:47Z) - Nearly Minimax-Optimal Rates for Noisy Sparse Phase Retrieval via
Early-Stopped Mirror Descent [29.206451882562867]
本稿では,雑音の位相探索に応用した早期停止ミラー降下法について検討する。
単純なアルゴリズムは、スパーシティを促進するために明示的な正規化やしきい値ステップに依存しない。
論文 参考訳(メタデータ) (2021-05-08T11:22:19Z) - Benign Overfitting of Constant-Stepsize SGD for Linear Regression [122.70478935214128]
帰納バイアスは 経験的に過剰フィットを防げる中心的存在です
この研究は、この問題を最も基本的な設定として考慮している: 線形回帰に対する定数ステップサイズ SGD。
我々は、(正規化されていない)SGDで得られるアルゴリズム正則化と、通常の最小二乗よりも多くの顕著な違いを反映する。
論文 参考訳(メタデータ) (2021-03-23T17:15:53Z) - A Continuous-Time Mirror Descent Approach to Sparse Phase Retrieval [24.17778927729799]
スパース位相探索に適用した連続時間ミラーを解析する。
これは、測定のみの集合からスパース信号を復元する問題である。
この問題に対して収束解析アルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-10-20T10:03:44Z) - Understanding Implicit Regularization in Over-Parameterized Single Index
Model [55.41685740015095]
我々は高次元単一インデックスモデルのための正規化自由アルゴリズムを設計する。
暗黙正則化現象の理論的保証を提供する。
論文 参考訳(メタデータ) (2020-07-16T13:27:47Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。