論文の概要: Variance-Reduced Fast Operator Splitting Methods for Generalized Equations
- arxiv url: http://arxiv.org/abs/2504.13046v3
- Date: Tue, 12 Aug 2025 21:04:57 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-08-14 16:17:42.374797
- Title: Variance-Reduced Fast Operator Splitting Methods for Generalized Equations
- Title（参考訳）: 一般化方程式に対する可変再生高速演算子分割法
- Authors: Quoc Tran-Dinh,
- Abstract要約: 一般化方程式のクラスの解を近似する2つの分散還元高速演算子分割法を開発した。
提案手法は, 加速演算子分割法, 固定点法, 共高調波性, 分散低減の最近の進歩を取り入れたものである。
- 参考スコア（独自算出の注目度）: 8.0153031008486
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We develop two variance-reduced fast operator splitting methods to approximate solutions of a class of generalized equations, covering fundamental problems such as \rvs{minimization}, minimax problems, and variational inequalities as special cases. Our approach integrates recent advances in accelerated operator splitting and fixed-point methods, co-hypomonotonicity, and variance reduction. First, we introduce a class of variance-reduced estimators and establish their variance-reduction bounds. This class includes both unbiased and biased instances and comprises common estimators as special cases, including SVRG, SAGA, SARAH, and Hybrid-SGD. Second, we design a novel accelerated variance-reduced forward-backward splitting (FBS) method using these estimators to solve generalized equations in both finite-sum and expectation settings. Our algorithm achieves both $\mathcal{O}(1/k^2)$ and $o(1/k^2)$ convergence rates on the expected squared norm $\mathbb{E}[ \| G_{\lambda}x^k\|^2]$ of the FBS residual $G_{\lambda}$, where $k$ is the iteration counter. Additionally, we establish almost sure convergence rates and the almost sure convergence of iterates to a solution of the underlying generalized equation. Unlike existing stochastic operator splitting algorithms, our methods accommodate co-hypomonotone operators, which can include nonmonotone problems arising in recent applications. Third, we specify our method for each concrete estimator mentioned above and derive the corresponding oracle complexity, demonstrating that these variants achieve the best-known oracle complexity bounds without requiring additional enhancement techniques. Fourth, we develop a variance-reduced fast backward-forward splitting (BFS) method, which attains similar convergence results and oracle complexity bounds as our FBS-based algorithm.
- Abstract（参考訳）: 一般化された方程式のクラスの解を近似する2つの分散還元高速作用素分割法を開発し、例えば \rvs{minimization} や minimax 問題、特殊ケースとしての変分不等式などの基本的な問題を網羅する。
提案手法は, 加速演算子分割法, 固定点法, 共高調波性, 分散低減の最近の進歩を取り入れたものである。
まず、分散還元推定器のクラスを導入し、その分散還元境界を確立する。
このクラスにはバイアスのないインスタンスとバイアスのあるインスタンスの両方が含まれており、SVRG、SAGA、SARAH、Hybrid-SGDなどの特殊なケースとして一般的な推定器を含んでいる。
第2に、これらの推定器を用いて、有限サムおよび期待条件の両方で一般化方程式を解くために、新しい分散誘導前方分割法(FBS)を設計する。
我々のアルゴリズムは、期待される2乗ノルム $\mathbb{E}[ \| G_{\lambda}x^k\|^2]$ 上の $\mathcal{O}(1/k^2)$ と $o(1/k^2)$ の収束率を達成する。
さらに、ほぼ確実に収束率を確立し、根底にある一般化方程式の解に反復のほぼ確実に収束する。
既存の確率的演算子分割アルゴリズムとは異なり、我々の手法はコヒポモノトン演算子に対応しており、近年の応用で生じる非モノトン問題を含むことができる。
第3に, 上記の各コンクリート推定器について提案手法を定め, 対応するオラクルの複雑さを導出し, これらの変種がさらなる拡張技術を必要とすることなく最もよく知られたオラクルの複雑さ境界を達成できることを実証した。
第4に、FBSに基づくアルゴリズムと同様の収束結果とオラクル複雑性境界が得られる分散還元高速後方分割法(BFS)を開発した。
関連論文リスト
- Accelerated Extragradient-Type Methods -- Part 2: Generalization and Sublinear Convergence Rates under Co-Hypomonotonicity [6.78476672849813]
本稿では,アンカード・エクストラグラディエントとネステロフのアクセルド・エクストラグラディエントという,2種類のエクストラグラディエント・ベースの手法について検討する。
我々は、より広い範囲のスキームにモノトン包摂を包含するアンカー付き指数関数のクラスを統一し、一般化する。
我々は、包含性を解決するために、Nesterovの高速化された指数関数の新たなクラスを提案する。
論文 参考訳（メタデータ） (2025-01-08T16:06:15Z) - Adaptive Variance Reduction for Stochastic Optimization under Weaker Assumptions [26.543628010637036]
非函数に対して$mathcalO(log T)$の最適収束率を達成する新しい適応還元法を導入する。
また、提案手法を拡張して、合成最適化のために$mathcalO(log T)$と同じ最適率を得る。
論文 参考訳（メタデータ） (2024-06-04T04:39:51Z) - Double Variance Reduction: A Smoothing Trick for Composite Optimization Problems without First-Order Gradient [40.22217106270146]
ばらつき低減技術はサンプリングのばらつきを低減し、一階法(FO)とゼロ階法(ZO)の収束率を向上するように設計されている。
複合最適化問題において、ZO法は、ランダム推定から導かれる座標ワイド分散と呼ばれる追加の分散に遭遇する。
本稿では,ZPDVR法とZPDVR法を提案する。
論文 参考訳（メタデータ） (2024-05-28T02:27:53Z) - Sample-efficient Learning of Infinite-horizon Average-reward MDPs with General Function Approximation [53.17668583030862]
一般関数近似の文脈において,無限水平平均逆マルコフ決定過程(AMDP)について検討する。
最適化最適化(LOOP)と呼ばれる新しいアルゴリズムフレームワークを提案する。
我々は LOOP がサブ線形 $tildemathcalO(mathrmpoly(d, mathrmsp(V*)) sqrtTbeta )$ regret を達成することを示す。
論文 参考訳（メタデータ） (2024-04-19T06:24:22Z) - Extragradient-Type Methods with $\mathcal{O} (1/k)$ Last-Iterate
Convergence Rates for Co-Hypomonotone Inclusions [8.0153031008486]
我々は、コヒポモノトン包摂の解を近似するために、よく知られた過次法(英語版)の2つの「ネステロフ加速」変種を開発した。
我々の結果は、ルートフィリング問題に対する最近のハルパーン型手法の代替と見なすことができる。
論文 参考訳（メタデータ） (2023-02-08T14:47:34Z) - Randomized Block-Coordinate Optimistic Gradient Algorithms for Root-Finding Problems [11.15373699918747]
大規模設定における非線形方程式の解を近似する2つの新しいアルゴリズムを開発した。
本稿では,機械学習,統計的学習,ネットワーク最適化などにおける顕著な応用を網羅した大規模有限サム包含のクラスに適用する。
論文 参考訳（メタデータ） (2023-01-08T21:46:27Z) - 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) - Multi-block-Single-probe Variance Reduced Estimator for Coupled
Compositional Optimization [49.58290066287418]
構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。
本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
論文 参考訳（メタデータ） (2022-07-18T12:03:26Z) - Faster One-Sample Stochastic Conditional Gradient Method for Composite
Convex Minimization [61.26619639722804]
滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。
提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
論文 参考訳（メタデータ） (2022-02-26T19:10:48Z) - Momentum Accelerates the Convergence of Stochastic AUPRC Maximization [80.8226518642952]
高精度リコール曲線(AUPRC)に基づく領域の最適化について検討し,不均衡なタスクに広く利用されている。
我々は、$O (1/epsilon4)$のより優れた反復による、$epsilon$定常解を見つけるための新しい運動量法を開発する。
また,O(1/epsilon4)$と同じ複雑さを持つ適応手法の新たなファミリを設計し,実際により高速な収束を享受する。
論文 参考訳（メタデータ） (2021-07-02T16:21:52Z) - On the Convergence of Stochastic Extragradient for Bilinear Games with
Restarted Iteration Averaging [96.13485146617322]
本稿では, ステップサイズが一定であるSEG法の解析を行い, 良好な収束をもたらす手法のバリエーションを示す。
平均化で拡張した場合、SEGはナッシュ平衡に確実に収束し、スケジュールされた再起動手順を組み込むことで、その速度が確実に加速されることを証明した。
論文 参考訳（メタデータ） (2021-06-30T17:51:36Z) - Unified Convergence Analysis for Adaptive Optimization with Moving Average Estimator [75.05106948314956]
1次モーメントに対する大きな運動量パラメータの増大は適応的スケーリングに十分であることを示す。
また,段階的に減少するステップサイズに応じて,段階的に運動量を増加させるための洞察を与える。
論文 参考訳（メタデータ） (2021-04-30T08:50:24Z) - Linearly Converging Error Compensated SGD [11.436753102510647]
本稿では、任意の圧縮と遅延更新を伴う分散SGDの変種を統一的に解析する。
我々のフレームワークは、量子化されたSGD、ErrorCompensated SGD、SGDの様々な変種をカバーするのに十分である。
我々は、分散還元や任意のサンプリングと誤りフィードバックと量子化を組み合わせたSGDの新しい変種を開発する。
論文 参考訳（メタデータ） (2020-10-23T10:46:31Z) - ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。
我々は,過去の勾配を平均化し,実装が容易な小説「Recursive One-Over-T SGD」を考案した。
有限サンプル, 漸近感覚, 感覚の両面において, 最先端の性能を同時に達成できることを実証する。
論文 参考訳（メタデータ） (2020-08-28T14:46:56Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。