論文の概要: Variance-Reduced Splitting Schemes for Monotone Stochastic Generalized Equations

• arxiv url: http://arxiv.org/abs/2008.11348v4
• Date: Mon, 18 Oct 2021 01:54:49 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-24 22:24:25.093885
• Title: Variance-Reduced Splitting Schemes for Monotone Stochastic Generalized Equations
• Title（参考訳）: 単調確率一般化方程式に対する変分解法
• Authors: Shisheng Cui and Uday V. Shanbhag
• Abstract要約: 演算子を期待値とする単調な包摂問題を考える。 分割スキームの直接適用は、各ステップにおける期待値マップによる問題解決の必要性により複雑である。 本稿では,不確実性に対処する手法を提案する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider monotone inclusion problems where the operators may be expectation-valued, a class of problems that subsumes convex stochastic optimization problems as well as subclasses of stochastic variational inequality and equilibrium problems. A direct application of splitting schemes is complicated by the need to resolve problems with expectation-valued maps at each step, a concern that is addressed by using sampling. Accordingly, we propose an avenue for addressing uncertainty in the mapping: Variance-reduced stochastic modified forward-backward splitting scheme (vr-SMFBS). In constrained settings, we consider structured settings when the map can be decomposed into an expectation-valued map A and a maximal monotone map B with a tractable resolvent. We show that the proposed schemes are equipped with a.s. convergence guarantees, linear (strongly monotone A) and O(1/k) (monotone A) rates of convergence while achieving optimal oracle complexity bounds. The rate statements in monotone regimes appear to be amongst the first and rely on leveraging the Fitzpatrick gap function for monotone inclusions. Furthermore, the schemes rely on weaker moment requirements on noise and allow for weakening unbiasedness requirements on oracles in strongly monotone regimes. Preliminary numerics on a class of two-stage stochastic variational inequality problems reflect these findings and show that the variance-reduced schemes outperform stochastic approximation schemes and sample-average approximation approaches. The benefits of attaining deterministic rates of convergence become even more salient when resolvent computation is expensive.
• Abstract（参考訳）: 我々は、演算子を期待値にすることができる単調な包摂問題、凸確率最適化問題を仮定する問題のクラス、および確率変動不等式と平衡問題のサブクラスを考える。 分割スキームの直接適用は,各ステップにおける期待値マップによる問題解決の必要性により複雑である。 そこで本研究では,不確実性に対処する手法を提案する。 可変再生確率修正前方分割方式(vr-SMFBS)。 制約された設定では、地図を予測値のマップAと、トラクタブルリゾルダー付き最大モノトーンマップBに分解できる構造化された設定を考える。 提案手法は, 最適オラクル複雑性境界を達成しつつ, A.s. convergence guarantees, linear (strongly monotone A) and O(1/k) rate of convergence (monotone A) を備えることを示す。 モノトーン系におけるレートステートメントは最初のものとなり、モノトーン包含物にフィッツパトリックギャップ関数を活用することに依拠している。 さらに、このスキームはノイズに対するより弱いモーメント要件に依存しており、強いモノトーン状態においてオラクルに対する偏りのない要求を弱めることができる。 2段階確率的変分不等式問題のクラスに関する予備数値はこれらの知見を反映し、分散還元されたスキームが確率的近似スキームと平均平均近似アプローチより優れていることを示す。 決定論的収束率を達成することの利点は、解法計算が高価であるときにさらに有益になる。

関連論文リスト

• An Inexact Halpern Iteration with Application to Distributionally Robust Optimization [9.529117276663431]
  決定論的および決定論的収束設定におけるスキームの不正確な変種について検討する。 不正確なスキームを適切に選択することにより、(予想される)剰余ノルムの点において$O(k-1)収束率を許容することを示す。
  論文  参考訳（メタデータ） (2024-02-08T20:12:47Z)
• Variance Reduced Halpern Iteration for Finite-Sum Monotone Inclusions [18.086061048484616]
  平衡問題の幅広いクラスをモデル化した有限サム単調包含問題について検討する。 我々の主な貢献は、複雑性の保証を改善するために分散還元を利用する古典的ハルパーン反復の変種である。 我々は、この複雑さが単調なリプシッツ設定では改善できないと論じる。
  論文  参考訳（メタデータ） (2023-10-04T17:24:45Z)
• High-Probability Convergence for Composite and Distributed Stochastic Minimization and Variational Inequalities with Heavy-Tailed Noise [96.80184504268593]
  グラデーション、クリッピングは、優れた高確率保証を導き出すアルゴリズムの鍵となる要素の1つである。 クリッピングは、合成および分散最適化の一般的な方法の収束を損なう可能性がある。
  論文  参考訳（メタデータ） (2023-10-03T07:49:17Z)
• First Order Methods with Markovian Noise: from Acceleration to Variational Inequalities [91.46841922915418]
  本稿では,一階変分法の理論解析のための統一的アプローチを提案する。 提案手法は非線形勾配問題とモンテカルロの強い問題の両方をカバーする。 凸法最適化問題の場合、オラクルに強く一致するような境界を与える。
  論文  参考訳（メタデータ） (2023-05-25T11:11:31Z)
• High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance [59.211456992422136]
  制約の少ない仮定の下で高確率収束結果のアルゴリズムを提案する。 これらの結果は、標準機能クラスに適合しない問題を最適化するために検討された手法の使用を正当化する。
  論文  参考訳（メタデータ） (2023-02-02T10:37:23Z)
• Clipped Stochastic Methods for Variational Inequalities with Heavy-Tailed Noise [64.85879194013407]
  単調なVIPと非単調なVIPの解法における信頼度に対数的依存を持つ最初の高確率結果が証明された。 この結果は光尾の場合で最もよく知られたものと一致し,非単調な構造問題に新鮮である。 さらに,多くの実用的な定式化の勾配雑音が重く,クリッピングによりSEG/SGDAの性能が向上することを示す。
  論文  参考訳（メタデータ） (2022-06-02T15:21:55Z)
• Optimal variance-reduced stochastic approximation in Banach spaces [114.8734960258221]
  可分バナッハ空間上で定義された収縮作用素の定点を推定する問題について検討する。 演算子欠陥と推定誤差の両方に対して漸近的でない境界を確立する。
  論文  参考訳（メタデータ） (2022-01-21T02:46:57Z)
• Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity [49.66890309455787]
  本稿では,SGDA と SCO の最終的な収束保証として,期待されるコヒーレンシティ条件を導入し,その利点を説明する。 定常的なステップサイズを用いた場合、両手法の線形収束性を解の近傍に証明する。 我々の収束保証は任意のサンプリングパラダイムの下で保たれ、ミニバッチの複雑さに関する洞察を与える。
  論文  参考訳（メタデータ） (2021-06-30T18:32:46Z)
• Stochastic Variance Reduction for Variational Inequality Methods [19.061953585686986]
  凸凹サドル点問題, 単調変位不等式, 単調包含問題に対する分散化アルゴリズムを提案する。 私たちのフレームワークは、ユークリッドとブレグマンの両方で、エクストラグラデーション、フォワードバックワード、フォワードリフレクテッドバックワードメソッドに適用されます。
  論文  参考訳（メタデータ） (2021-02-16T18:39:16Z)

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

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