論文の概要: Variance-Reduced Fast Operator Splitting Methods for Stochastic Generalized Equations
- arxiv url: http://arxiv.org/abs/2504.13046v1
- Date: Thu, 17 Apr 2025 16:02:20 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-04-18 14:36:10.006039
- Title: Variance-Reduced Fast Operator Splitting Methods for Stochastic Generalized Equations
- Title（参考訳）: 確率一般化方程式に対する可変再生高速演算子分割法
- Authors: Quoc Tran-Dinh,
- Abstract要約: 分散還元推定器のクラスを導入し,その分散還元限界を確立する。
次に,FBS (Accelerated variance-Reduced forward-backward splitting) アルゴリズムを設計する。
提案手法は,期待ノルム上の$mathcalO (1/k2)$と$o (1/k2)$収束率の両方を達成する。
- 参考スコア（独自算出の注目度）: 8.0153031008486
- License:
- Abstract: We develop two classes of variance-reduced fast operator splitting methods to approximate solutions of both finite-sum and stochastic generalized equations. Our approach integrates recent advances in accelerated 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 covers both unbiased and biased instances and comprises common estimators as special cases, including SVRG, SAGA, SARAH, and Hybrid-SGD. Next, we design a novel accelerated variance-reduced forward-backward splitting (FBS) algorithm using these estimators to solve finite-sum and stochastic generalized equations. Our method 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, for the first time, almost sure convergence rates and almost sure convergence of iterates to a solution in stochastic accelerated methods. Unlike existing stochastic fixed-point algorithms, our methods accommodate co-hypomonotone operators, which potentially include nonmonotone problems arising from recent applications. We further specify our method to derive an appropriate variant for each stochastic estimator -- SVRG, SAGA, SARAH, and Hybrid-SGD -- demonstrating that they achieve the best-known complexity for each without relying on enhancement techniques. Alternatively, we propose an accelerated variance-reduced backward-forward splitting (BFS) method, which attains similar convergence rates and oracle complexity as our FBS method. Finally, we validate our results through several numerical experiments and compare their performance.
- Abstract（参考訳）: 偏微分還元高速作用素分割法の2つのクラスを開発し、有限和および確率一般化方程式の解を近似する。
提案手法は, 加速固定点法, 共催眠音速, 分散低減の最近の進歩を取り入れたものである。
まず、分散還元推定器のクラスを導入し、その分散還元境界を確立する。
このクラスはバイアスのないインスタンスとバイアスのないインスタンスの両方をカバーし、SVRG、SAGA、SARAH、Hybrid-SGDなどの特殊なケースとして一般的な推定器を含んでいる。
次に, これらの推定器を用いて, 有限相および確率的一般化方程式の解法により, FBS法を高速化するアルゴリズムを設計する。
我々の方法は、期待される2乗ノルム $\mathbb{E}[ \| G_{\lambda}x^k\|^2]$ 上の $\mathcal{O}(1/k^2)$ と $o(1/k^2)$ の収束率の両方を達成する。
さらに、我々は初めて、ほぼ確実に収束率とほぼ確実に反復の収束が確率的加速法で解に収束することを確立する。
既存の確率的不動点アルゴリズムとは異なり、我々の手法はコヒポモノトン演算子に対応しており、近年の応用から生じる非モノトン問題を含む可能性がある。
さらに,各確率推定器(SVRG,SAGA,SARAH,Hybrid-SGD)の適切な変種を導出する手法を提案し,拡張技術に頼らずに,それぞれが最もよく知られた複雑性を実現することを示す。
あるいは、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) - 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) - Linearly Converging Error Compensated SGD [11.436753102510647]
本稿では、任意の圧縮と遅延更新を伴う分散SGDの変種を統一的に解析する。
我々のフレームワークは、量子化されたSGD、ErrorCompensated SGD、SGDの様々な変種をカバーするのに十分である。
我々は、分散還元や任意のサンプリングと誤りフィードバックと量子化を組み合わせたSGDの新しい変種を開発する。
論文 参考訳（メタデータ） (2020-10-23T10:46:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。