論文の概要: A Stochastic Halpern Iteration with Variance Reduction for Stochastic Monotone Inclusion Problems

• arxiv url: http://arxiv.org/abs/2203.09436v2
• Date: Mon, 21 Mar 2022 14:39:23 GMT
• ステータス: 処理完了
• システム内更新日: 2022-03-22 10:33:09.597137
• Title: A Stochastic Halpern Iteration with Variance Reduction for Stochastic Monotone Inclusion Problems
• Title（参考訳）: 確率的モノトン包摂問題に対する可変化を用いた確率的ハルパーン反復法
• Authors: Xufeng Cai, Chaobing Song, Crist\'obal Guzm\'an, Jelena Diakonikolas
• Abstract要約: 機械学習アプリケーションで広く見られるモノトーン包摂問題について検討する。 我々のアルゴリズムは、$mathcalO(frac1epsilon3)$演算子の評価で演算子に$epsilon$ノルムを得る。
• 参考スコア（独自算出の注目度）: 17.597000481404883
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study stochastic monotone inclusion problems, which widely appear in machine learning applications, including robust regression and adversarial learning. We propose novel variants of stochastic Halpern iteration with recursive variance reduction. In the cocoercive -- and more generally Lipschitz-monotone -- setup, our algorithm attains $\epsilon$ norm of the operator with $\mathcal{O}(\frac{1}{\epsilon^3})$ stochastic operator evaluations, which significantly improves over state of the art $\mathcal{O}(\frac{1}{\epsilon^4})$ stochastic operator evaluations required for existing monotone inclusion solvers applied to the same problem classes. We further show how to couple one of the proposed variants of stochastic Halpern iteration with a scheduled restart scheme to solve stochastic monotone inclusion problems with ${\mathcal{O}}(\frac{\log(1/\epsilon)}{\epsilon^2})$ stochastic operator evaluations under additional sharpness or strong monotonicity assumptions. Finally, we argue via reductions between different problem classes that our stochastic oracle complexity bounds are tight up to logarithmic factors in terms of their $\epsilon$-dependence.
• Abstract（参考訳）: 本研究では,ロバスト回帰や逆行学習など,機械学習アプリケーションで広く見られる確率的単調包含問題について検討する。 再帰的分散還元を伴う確率的ハルパーン反復の新たな変種を提案する。 コヒーレンシブ -- より一般的にはリプシッツモノトン -- のセットアップにおいて、我々のアルゴリズムは、演算子のノルムを$\mathcal{O}(\frac{1}{\epsilon^3})$確率演算子評価で達成し、同じ問題クラスに適用された既存の単調包含分解器に必要な確率演算子評価を$\mathcal{O}(\frac{1}{\epsilon^4})$確率演算子評価で大幅に改善する。 さらに、提案された確率的ハルパーン反復の1つの変種を、追加のシャープネスや強い単調性仮定の下での確率的作用素評価で${\mathcal{O}}(\frac{\log(1/\epsilon)}{\epsilon^2})で確率的単調包含問題を解くためにスケジュールされた再起動スキームと組み合わせる方法を示す。 最後に、我々の確率的オラクル複雑性境界が、それらの$\epsilon$-dependenceの対数的因子に強く依存しているという、異なる問題クラス間の還元を通じて議論する。

関連論文リスト

• Stochastic Halpern iteration in normed spaces and applications to reinforcement learning [0.30693357740321775]
  基礎となるオラクルが一様有界であれば,本手法は全体のオラクル複雑性が$tildeO(varepsilon-5)$であることを示す。 平均報酬と割引報酬を決定するための新しい同期アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-03-19T01:07:35Z)
• Variance Reduced Halpern Iteration for Finite-Sum Monotone Inclusions [18.086061048484616]
  平衡問題の幅広いクラスをモデル化した有限サム単調包含問題について検討する。 我々の主な貢献は、複雑性の保証を改善するために分散還元を利用する古典的ハルパーン反復の変種である。 我々は、この複雑さが単調なリプシッツ設定では改善できないと論じる。
  論文  参考訳（メタデータ） (2023-10-04T17:24:45Z)
• Randomized Greedy Learning for Non-monotone Stochastic Submodular Maximization Under Full-bandit Feedback [98.29086113546045]
  本稿では,非拘束型マルチアームバンディットのフルバンドフィードバックとサブモジュール性に対する報奨問題について検討する。 RGLは、サブモジュールおよび非サブモジュール設定において、他のフルバンド変種よりも経験的に優れていることを示す。
  論文  参考訳（メタデータ） (2023-02-02T18:52:14Z)
• Adaptive Stochastic Variance Reduction for Non-convex Finite-Sum Minimization [52.25843977506935]
  有限サム構造をもつ$L$-smooth, non-deuction関数に対して, AdaSpider と呼ばれる適応分散法を提案する。 そうすることで、$tildeOleft + st/epsilonコールで$epsilon-stationaryポイントを計算することができます。
  論文  参考訳（メタデータ） (2022-11-03T14:41:46Z)
• Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization [49.58290066287418]
  構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。 本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
  論文  参考訳（メタデータ） (2022-07-18T12:03:26Z)
• Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
  滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。 漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
  論文  参考訳（メタデータ） (2022-06-17T06:10:20Z)
• Optimal variance-reduced stochastic approximation in Banach spaces [114.8734960258221]
  可分バナッハ空間上で定義された収縮作用素の定点を推定する問題について検討する。 演算子欠陥と推定誤差の両方に対して漸近的でない境界を確立する。
  論文  参考訳（メタデータ） (2022-01-21T02:46:57Z)
• Stochastic Projective Splitting: Solving Saddle-Point Problems with Multiple Regularizers [4.568911586155097]
  本稿では、包含問題に対する単調アルゴリズムの射影分割(PS)系列の新たな変種について述べる。 勾配降下上昇に伴う収束問題なしに、ロバストMLのような応用で生じるmin-maxおよび非協調ゲーム定式化を解くことができる。
  論文  参考訳（メタデータ） (2021-06-24T14:48:43Z)
• On Stochastic Moving-Average Estimators for Non-Convex Optimization [105.22760323075008]
  本稿では,移動平均(SEMA)問題に基づく広く利用されている推定器のパワーを実証する。 これらすべてのアートな結果に対して、これらのアートな問題に対する結果も提示します。
  論文  参考訳（メタデータ） (2021-04-30T08:50:24Z)
• Variance-Reduced Splitting Schemes for Monotone Stochastic Generalized Equations [0.0]
  演算子を期待値とする単調な包摂問題を考える。 分割スキームの直接適用は、各ステップにおける期待値マップによる問題解決の必要性により複雑である。 本稿では,不確実性に対処する手法を提案する。
  論文  参考訳（メタデータ） (2020-08-26T02:33:27Z)

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

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