論文の概要: Stability and Generalization for Stochastic Recursive Momentum-based Algorithms for (Strongly-)Convex One to $K$-Level Stochastic Optimizations

• arxiv url: http://arxiv.org/abs/2407.05286v1
• Date: Sun, 7 Jul 2024 07:07:04 GMT
• ステータス: 処理完了
• システム内更新日: 2024-07-09 20:27:05.575376
• Title: Stability and Generalization for Stochastic Recursive Momentum-based Algorithms for (Strongly-)Convex One to $K$-Level Stochastic Optimizations
• Title（参考訳）: Strongly-)Convex One to $K$-Level Stochastic Optimization のための確率的再帰モーメントに基づくアルゴリズムの安定性と一般化
• Authors: Xiaokang Pan, Xingyu Li, Jin Liu, Tao Sun, Kai Sun, Lixing Chen, Zhe Qu,
• Abstract要約: STORMベースのアルゴリズムは、K$レベル(K geq 3$)の最適化問題を解決するために広く開発されている。 本稿では,STORMに基づく3つの代表的なアルゴリズムを包括的に分析する。
• 参考スコア（独自算出の注目度）: 20.809499420384256
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: STOchastic Recursive Momentum (STORM)-based algorithms have been widely developed to solve one to $K$-level ($K \geq 3$) stochastic optimization problems. Specifically, they use estimators to mitigate the biased gradient issue and achieve near-optimal convergence results. However, there is relatively little work on understanding their generalization performance, particularly evident during the transition from one to $K$-level optimization contexts. This paper provides a comprehensive generalization analysis of three representative STORM-based algorithms: STORM, COVER, and SVMR, for one, two, and $K$-level stochastic optimizations under both convex and strongly convex settings based on algorithmic stability. Firstly, we define stability for $K$-level optimizations and link it to generalization. Then, we detail the stability results for three prominent STORM-based algorithms. Finally, we derive their excess risk bounds by balancing stability results with optimization errors. Our theoretical results provide strong evidence to complete STORM-based algorithms: (1) Each estimator may decrease their stability due to variance with its estimation target. (2) Every additional level might escalate the generalization error, influenced by the stability and the variance between its cumulative stochastic gradient and the true gradient. (3) Increasing the batch size for the initial computation of estimators presents a favorable trade-off, enhancing the generalization performance.
• Abstract（参考訳）: STOchastic Recursive Momentum (STORM)ベースのアルゴリズムは、K$レベル(K \geq 3$)確率最適化問題を解くために広く開発されている。 具体的には、推定器を用いてバイアス勾配問題を緩和し、ほぼ最適収束結果を得る。 しかしながら、一般化性能の理解については、特に 1 ドルから $K レベルの最適化コンテキストへの移行時に顕著な研究が比較的少ない。 本稿では,STORM, COVER, SVMRの3つの代表的なSTORMアルゴリズムの包括的一般化解析を行う。 まず、$K$レベルの最適化の安定性を定義し、一般化にリンクする。 次に、3つのSTORMベースのアルゴリズムの安定性について詳述する。 最後に、安定性と最適化誤差のバランスをとることで、過大なリスク境界を導出する。 理論的な結果はSTORMに基づくアルゴリズムの完成に強い証拠を与える: 1) 各推定器は、その推定対象とのばらつきにより安定性を低下させることができる。 2) 任意の追加レベルは、その累積確率勾配と真の勾配の間の安定性と分散の影響を受け、一般化誤差をエスカレートする。 (3)推定器の初期計算におけるバッチサイズの増加は良好なトレードオフを示し、一般化性能が向上する。

関連論文リスト

• Stability and Generalization of Stochastic Compositional Gradient Descent Algorithms [61.59448949684493]
  学習例から構築した合成降下アルゴリズムの安定性と一般化解析について述べる。 SCGD と SCSC という2つの一般的な合成勾配勾配勾配アルゴリズムの均一安定性について検討した。 SCGD と SCSC の非依存的過剰リスク境界は,安定性結果と最適化誤差をトレードオフすることによって導出する。
  論文  参考訳（メタデータ） (2023-07-07T02:40:09Z)
• Exploring the Algorithm-Dependent Generalization of AUPRC Optimization with List Stability [107.65337427333064]
  AUPRC(Area Under the Precision-Recall Curve)の最適化は、機械学習にとって重要な問題である。 本研究では, AUPRC最適化の単依存一般化における最初の試行について述べる。 3つの画像検索データセットの実験は、我々のフレームワークの有効性と健全性に言及する。
  論文  参考訳（メタデータ） (2022-09-27T09:06:37Z)
• Momentum Accelerates the Convergence of Stochastic AUPRC Maximization [80.8226518642952]
  高精度リコール曲線(AUPRC)に基づく領域の最適化について検討し,不均衡なタスクに広く利用されている。 我々は、$O (1/epsilon4)$のより優れた反復による、$epsilon$定常解を見つけるための新しい運動量法を開発する。 また,O(1/epsilon4)$と同じ複雑さを持つ適応手法の新たなファミリを設計し,実際により高速な収束を享受する。
  論文  参考訳（メタデータ） (2021-07-02T16:21:52Z)
• Robust Distributed Optimization With Randomly Corrupted Gradients [24.253191879453784]
  本研究では, ビザンチンの故障に頑健で, 潜在的に敵対的な挙動を示す一階分散最適化アルゴリズムを提案する。 我々のアルゴリズムは順序正規化と信頼に値する統計的誤差収束率を達成する。
  論文  参考訳（メタデータ） (2021-06-28T19:45:25Z)
• On Stochastic Moving-Average Estimators for Non-Convex Optimization [105.22760323075008]
  本稿では,移動平均(SEMA)問題に基づく広く利用されている推定器のパワーを実証する。 これらすべてのアートな結果に対して、これらのアートな問題に対する結果も提示します。
  論文  参考訳（メタデータ） (2021-04-30T08:50:24Z)
• A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic [142.1492359556374]
  双レベル最適化は、2レベル構造を示す問題のクラスである。 このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。 本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
  論文  参考訳（メタデータ） (2020-07-10T05:20:02Z)
• Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses [52.039438701530905]
  任意のリプシッツ非平滑凸損失に対して,数種類の勾配勾配降下(SGD)に対して,鋭い上下境界を与える。 我々の限界は、極端に過剰な集団リスクを伴う、微分的にプライベートな非平滑凸最適化のための新しいアルゴリズムを導出することを可能にする。
  論文  参考訳（メタデータ） (2020-06-12T02:45:21Z)

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

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