論文の概要: Tighter Analysis of Alternating Stochastic Gradient Method for Stochastic Nested Problems

• arxiv url: http://arxiv.org/abs/2106.13781v1
• Date: Fri, 25 Jun 2021 17:33:51 GMT
• ステータス: 処理完了
• システム内更新日: 2021-06-28 13:12:50.030363
• Title: Tighter Analysis of Alternating Stochastic Gradient Method for Stochastic Nested Problems
• Title（参考訳）: 確率ネスト問題に対する交互確率勾配法のタイター解析
• Authors: Tianyi Chen, Yuejiao Sun, and Wotao Yin
• Abstract要約: 本稿では、ネスト問題に対するSGD型更新を、ALSET(ALternating dEscenT)メソッドと呼ばれる単一のアプローチに統合する。 新しい分析では、ネストされた問題において$epsilon$-stationaryポイントを達成するには、$cal O(epsilon-2)$サンプルが必要である。 本研究の結果を合成, 分極, 強化学習問題に適用することにより, それぞれの症例において最もよく知られたサンプルの複雑さを改善または一致させる。
• 参考スコア（独自算出の注目度）: 31.02472517086767
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Stochastic nested optimization, including stochastic compositional, min-max and bilevel optimization, is gaining popularity in many machine learning applications. While the three problems share the nested structure, existing works often treat them separately, and thus develop problem-specific algorithms and their analyses. Among various exciting developments, simple SGD-type updates (potentially on multiple variables) are still prevalent in solving this class of nested problems, but they are believed to have slower convergence rate compared to that of the non-nested problems. This paper unifies several SGD-type updates for stochastic nested problems into a single SGD approach that we term ALternating Stochastic gradient dEscenT (ALSET) method. By leveraging the hidden smoothness of the problem, this paper presents a tighter analysis of ALSET for stochastic nested problems. Under the new analysis, to achieve an $\epsilon$-stationary point of the nested problem, it requires ${\cal O}(\epsilon^{-2})$ samples. Under certain regularity conditions, applying our results to stochastic compositional, min-max and reinforcement learning problems either improves or matches the best-known sample complexity in the respective cases. Our results explain why simple SGD-type algorithms in stochastic nested problems all work very well in practice without the need for further modifications.
• Abstract（参考訳）: 確率的合成、min-max、bilevel最適化を含む確率的ネスト最適化は、多くの機械学習アプリケーションで人気を集めている。 3つの問題はネスト構造を共有しているが、既存の作品はしばしばそれらを別々に扱い、問題固有のアルゴリズムとその分析を開発する。 様々なエキサイティングな開発の中で、単純なsgdタイプの更新(潜在的に複数の変数上の)は、ネストした問題のクラスを解くために今でも一般的であるが、非ネスト問題に比べて収束速度が遅いと考えられている。 本稿では,確率的ネスト問題に対するSGD型更新を1つのSGDアプローチに統合し,確率的勾配dEscenT法(Alternating Stochastic gradient dEscenT:ALSET)と呼ぶ。 本稿では,問題の隠れた滑らかさを生かして,確率的ネスト問題に対するalsetのより厳密な解析を行う。 新しい解析では、ネストされた問題の$\epsilon$-定常点を達成するには、${\cal O}(\epsilon^{-2})$サンプルが必要である。 一定の規則性条件下では, 確率的構成, min-max, 強化学習問題に適用し, それぞれの場合において最もよく知られたサンプルの複雑さを改善または一致させる。 確率ネスト問題における単純なSGD型アルゴリズムが、さらなる修正を必要とせず、実際に非常にうまく機能する理由を述べる。

関連論文リスト

• Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problems [56.86067111855056]
  構造密度の重み付き雑音によるクリップ最適化問題を考察する。 勾配が有限の順序モーメントを持つとき、$mathcalO(K-(alpha - 1)/alpha)$よりも高速な収束率が得られることを示す。 得られた推定値が無視可能なバイアスと制御可能な分散を持つことを示す。
  論文  参考訳（メタデータ） (2023-11-07T17:39:17Z)
• High-Probability Convergence for Composite and Distributed Stochastic Minimization and Variational Inequalities with Heavy-Tailed Noise [96.80184504268593]
  グラデーション、クリッピングは、優れた高確率保証を導き出すアルゴリズムの鍵となる要素の1つである。 クリッピングは、合成および分散最適化の一般的な方法の収束を損なう可能性がある。
  論文  参考訳（メタデータ） (2023-10-03T07:49:17Z)
• Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation Constrained Optimization [88.0031283949404]
  多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。 提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
  論文  参考訳（メタデータ） (2022-12-19T14:48:54Z)
• Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization [49.58290066287418]
  構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。 本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
  論文  参考訳（メタデータ） (2022-07-18T12:03:26Z)
• Clipped Stochastic Methods for Variational Inequalities with Heavy-Tailed Noise [64.85879194013407]
  単調なVIPと非単調なVIPの解法における信頼度に対数的依存を持つ最初の高確率結果が証明された。 この結果は光尾の場合で最もよく知られたものと一致し,非単調な構造問題に新鮮である。 さらに,多くの実用的な定式化の勾配雑音が重く,クリッピングによりSEG/SGDAの性能が向上することを示す。
  論文  参考訳（メタデータ） (2022-06-02T15:21:55Z)
• Randomized Stochastic Variance-Reduced Methods for Stochastic Bilevel Optimization [62.87181271021217]
  機械学習に多くの応用がある非SBO問題を考察する。 本稿では,非SBO問題に対する高速ランダム化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-05-05T18:28:42Z)
• Stochastic Multi-level Composition Optimization Algorithms with Level-Independent Convergence Rates [12.783783498844022]
  目的関数が$T$関数のネスト合成であるような,スムーズな多層合成最適化問題について検討する。 citeGhaRuswan20を$T$のレベルで一般化した最初のアルゴリズムは、$mathcalO (1/epsilon$6) のサンプル複雑性を実現することができることを示す。 これは、(アン)マルチレベル設定のために設計されたオンラインアルゴリズムが、標準仮定の下で同じサンプル複雑性を得るのはこれが初めてである。
  論文  参考訳（メタデータ） (2020-08-24T15:57:50Z)
• Stochastic Proximal Gradient Algorithm with Minibatches. Application to Large Scale Learning Models [2.384873896423002]
  非滑らかな成分を持つ汎用合成対象関数に対する勾配アルゴリズムのミニバッチ変種を開発し解析する。 我々は、最小バッチサイズ$N$に対して、$mathcalO(frac1Nepsilon)$$epsilon-$subityが最適解に期待される二次距離で達成されるような、定数および変数のステップサイズ反復ポリシーの複雑さを提供する。
  論文  参考訳（メタデータ） (2020-03-30T10:43:56Z)
• Zeroth-Order Algorithms for Nonconvex Minimax Problems with Improved Complexities [21.13934071954103]
  本稿では,非インワンテキスト変数 Descent に対する決定論的アルゴリズムを提案する。 SGC仮定の下では,アルゴリズムの複雑さが既存のアルゴリズムの複雑さと一致していることが示される。 結果はオラクル・テキストZO-GDMSAで示され、数値実験により理論的結果が裏付けられる。
  論文  参考訳（メタデータ） (2020-01-22T00:05:14Z)

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

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