論文の概要: Variance Reduced Halpern Iteration for Finite-Sum Monotone Inclusions
- arxiv url: http://arxiv.org/abs/2310.02987v1
- Date: Wed, 4 Oct 2023 17:24:45 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-05 13:38:34.036989
- Title: Variance Reduced Halpern Iteration for Finite-Sum Monotone Inclusions
- Title（参考訳）: 有限サムモノトン包有物の分散低減Halpernイテレーション
- Authors: Xufeng Cai, Ahmet Alacaoglu, Jelena Diakonikolas
- Abstract要約: 平衡問題の幅広いクラスをモデル化した有限サム単調包含問題について検討する。
我々の主な貢献は、複雑性の保証を改善するために分散還元を利用する古典的ハルパーン反復の変種である。
我々は、この複雑さが単調なリプシッツ設定では改善できないと論じる。
- 参考スコア（独自算出の注目度）: 18.086061048484616
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Machine learning approaches relying on such criteria as adversarial
robustness or multi-agent settings have raised the need for solving
game-theoretic equilibrium problems. Of particular relevance to these
applications are methods targeting finite-sum structure, which generically
arises in empirical variants of learning problems in these contexts. Further,
methods with computable approximation errors are highly desirable, as they
provide verifiable exit criteria. Motivated by these applications, we study
finite-sum monotone inclusion problems, which model broad classes of
equilibrium problems. Our main contributions are variants of the classical
Halpern iteration that employ variance reduction to obtain improved complexity
guarantees in which $n$ component operators in the finite sum are ``on
average'' either cocoercive or Lipschitz continuous and monotone, with
parameter $L$. The resulting oracle complexity of our methods, which provide
guarantees for the last iterate and for a (computable) operator norm residual,
is $\widetilde{\mathcal{O}}( n + \sqrt{n}L\varepsilon^{-1})$, which improves
upon existing methods by a factor up to $\sqrt{n}$. This constitutes the first
variance reduction-type result for general finite-sum monotone inclusions and
for more specific problems such as convex-concave optimization when operator
norm residual is the optimality measure. We further argue that, up to
poly-logarithmic factors, this complexity is unimprovable in the monotone
Lipschitz setting; i.e., the provided result is near-optimal.
- Abstract（参考訳）: 対向的ロバスト性やマルチエージェント設定といった基準に頼った機械学習アプローチは、ゲーム理論平衡問題の解決の必要性を高めている。
これらの応用の特に関連性は有限サム構造をターゲットにした手法であり、これらの文脈における学習問題の経験的変種に一般化的に現れる。
さらに、計算可能な近似誤差を持つメソッドは、検証可能な出口基準を提供するため、非常に望ましい。
これらの応用により、平衡問題の幅広いクラスをモデル化する有限サム単調包含問題を研究する。
我々の主な貢献は、分散還元を利用する古典的ハルパーンの反復の変種であり、有限和の$n$成分作用素が 'on average'' であるような複雑性を保証するために、パラメータ$L$ を持つcocoercive あるいは Lipschitz の連続かつ単調である。
最後の反復と(計算可能な)作用素のノルム残量を保証するメソッドのオラクルの複雑さは、$\widetilde{\mathcal{O}}(n + \sqrt{n}L\varepsilon^{-1})$であり、既存のメソッドを最大$\sqrt{n}$まで改善する。
これは、一般の有限和単調包含物と、作用素ノルム残差が最適測度であるときに凸凹最適化のようなより具体的な問題に対する最初の分散還元型結果を構成する。
さらに、この複雑さが単調なリプシッツ設定では改善不可能である、すなわち、与えられた結果がほぼ最適である、とも主張する。
関連論文リスト
- Error Feedback under $(L_0,L_1)$-Smoothness: Normalization and Momentum [56.37522020675243]
機械学習の幅広い問題にまたがる正規化誤差フィードバックアルゴリズムに対する収束の最初の証明を提供する。
提案手法では,許容可能なステップサイズが大きくなったため,新しい正規化エラーフィードバックアルゴリズムは,各種タスクにおける非正規化エラーよりも優れていた。
論文 参考訳（メタデータ） (2024-10-22T10:19:27Z) - Sparsity via Sparse Group $k$-max Regularization [22.05774771336432]
本稿では,新規かつ簡潔な正規化,すなわちスパース群$k$-max正規化を提案する。
提案手法の有効性と柔軟性を,合成データセットと実世界のデータセットの数値実験により検証する。
論文 参考訳（メタデータ） (2024-02-13T14:41:28Z) - An Inexact Halpern Iteration with Application to Distributionally Robust
Optimization [9.529117276663431]
決定論的および決定論的収束設定におけるスキームの不正確な変種について検討する。
不正確なスキームを適切に選択することにより、(予想される)剰余ノルムの点において$O(k-1)収束率を許容することを示す。
論文 参考訳（メタデータ） (2024-02-08T20:12:47Z) - Conditional expectation using compactification operators [0.0]
本稿では,条件付き予測を推定するための演算子理論的アプローチについて述べる。
カーネル積分作用素は、再生されたカーネルヒルベルト空間における線形逆問題として推定問題を設定するためのコンパクト化ツールとして用いられる。
論文 参考訳（メタデータ） (2023-06-18T16:11:40Z) - High-Probability Bounds for Stochastic Optimization and Variational
Inequalities: the Case of Unbounded Variance [59.211456992422136]
制約の少ない仮定の下で高確率収束結果のアルゴリズムを提案する。
これらの結果は、標準機能クラスに適合しない問題を最適化するために検討された手法の使用を正当化する。
論文 参考訳（メタデータ） (2023-02-02T10:37:23Z) - Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。
予測と高い確率で、新しい過剰なリスク境界を提供する。
我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
論文 参考訳（メタデータ） (2022-11-03T12:40:24Z) - A Primal-Dual Approach to Solving Variational Inequalities with General Constraints [54.62996442406718]
Yang et al. (2023) は最近、一般的な変分不等式を解決するために一階勾配法を使う方法を示した。
この方法の収束性を証明し、演算子が$L$-Lipschitz と monotone である場合、この手法の最後の繰り返しのギャップ関数が$O(frac1sqrtK)$で減少することを示す。
論文 参考訳（メタデータ） (2022-10-27T17:59:09Z) - A Stochastic Halpern Iteration with Variance Reduction for Stochastic
Monotone Inclusion Problems [17.597000481404883]
機械学習アプリケーションで広く見られるモノトーン包摂問題について検討する。
我々のアルゴリズムは、$mathcalO(frac1epsilon3)$演算子の評価で演算子に$epsilon$ノルムを得る。
論文 参考訳（メタデータ） (2022-03-17T16:48:57Z) - Faster Algorithm and Sharper Analysis for Constrained Markov Decision
Process [56.55075925645864]
制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。
新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。
これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
論文 参考訳（メタデータ） (2021-10-20T02:57:21Z) - Efficient Methods for Structured Nonconvex-Nonconcave Min-Max
Optimization [98.0595480384208]
定常点に収束する一般化外空間を提案する。
このアルゴリズムは一般の$p$ノルド空間だけでなく、一般の$p$次元ベクトル空間にも適用される。
論文 参考訳（メタデータ） (2020-10-31T21:35:42Z) - Variance-Reduced Splitting Schemes for Monotone Stochastic Generalized
Equations [0.0]
演算子を期待値とする単調な包摂問題を考える。
分割スキームの直接適用は、各ステップにおける期待値マップによる問題解決の必要性により複雑である。
本稿では,不確実性に対処する手法を提案する。
論文 参考訳（メタデータ） (2020-08-26T02:33:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。