論文の概要: Variance-Reduced Fast Krasnoselkii-Mann Methods for Finite-Sum Root-Finding Problems

• arxiv url: http://arxiv.org/abs/2406.02413v2
• Date: Thu, 20 Mar 2025 01:57:17 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-21 19:00:32.368820
• Title: Variance-Reduced Fast Krasnoselkii-Mann Methods for Finite-Sum Root-Finding Problems
• Title（参考訳）: 有限サムループフィンディング問題に対する可変生成高速クラスノセルキ-マン法
• Authors: Quoc Tran-Dinh,
• Abstract要約: 有限和共役方程式 $Gx = 0$ を解くために, 分散還元を伴う高速クラスクラスKrasnoselkii-Mann 法を提案する。 我々のアルゴリズムは単一ループであり、より広範なルートフィンディングアルゴリズムのために特別に設計された、偏りのない分散還元推定器の新たなファミリーを利用する。 数値実験は我々のアルゴリズムを検証し、最先端の手法と比較して有望な性能を示す。
• 参考スコア（独自算出の注目度）: 8.0153031008486
• License:
• Abstract: We propose a new class of fast Krasnoselkii--Mann methods with variance reduction to solve a finite-sum co-coercive equation $Gx = 0$. Our algorithm is single-loop and leverages a new family of unbiased variance-reduced estimators specifically designed for a wider class of root-finding algorithms. Our method achieves both $\mathcal{O}(1/k^2)$ and $o(1/k^2)$ last-iterate convergence rates in terms of $\mathbb{E}[\| Gx^k\|^2]$, where $k$ is the iteration counter and $\mathbb{E}[\cdot]$ is the total expectation. We also establish almost sure $o(1/k^2)$ convergence rates and the almost sure convergence of iterates $\{x^k\}$ to a solution of $Gx=0$. We instantiate our framework for two prominent estimators: SVRG and SAGA. By an appropriate choice of parameters, both variants attain an oracle complexity of $\mathcal{O}(n + n^{2/3}\epsilon^{-1})$ to reach an $\epsilon$-solution, where $n$ represents the number of summands in the finite-sum operator $G$. Furthermore, under $\sigma$-strong quasi-monotonicity, our method achieves a linear convergence rate and an oracle complexity of $\mathcal{O}(n+ \max\{n, n^{2/3}\kappa\} \log(\frac{1}{\epsilon}))$, where $\kappa := L/\sigma$. We extend our approach to solve a class of finite-sum inclusions (possibly nonmonotone), demonstrating that our schemes retain the same theoretical guarantees as in the equation setting. Finally, numerical experiments validate our algorithms and demonstrate their promising performance compared to state-of-the-art methods.
• Abstract（参考訳）: 有限和共役方程式 $Gx = 0$ を解くために, 分散還元を伴う高速クラスクラスKrasnoselkii-Mann 法を提案する。 我々のアルゴリズムは単一ループであり、より広範なルートフィンディングアルゴリズムのために特別に設計された、偏りのない分散還元推定器の新たなファミリーを利用する。 我々の手法は、$\mathcal{O}(1/k^2)$と$o(1/k^2)$の最後の収束率を$\mathbb{E}[\| Gx^k\|^2]$で達成し、$k$は反復カウンタ、$\mathbb{E}[\cdot]$は総期待値である。 また、ほぼ確実に$o(1/k^2)$収束率を確立し、ほぼ確実に反復の収束は$\{x^k\}$を$Gx=0$の解とする。 SVRGとSAGAという2つの著名な推定器のフレームワークをインスタンス化する。 パラメータの適切な選択により、どちらの変種も$\mathcal{O}(n + n^{2/3}\epsilon^{-1})$のオラクル複雑性を達成し、$\epsilon$-solutionに達する。 さらに、$\sigma$-strong quasi-monotonicity(英語版)の下で、この手法は、$\mathcal{O}(n+ \max\{n, n^{2/3}\kappa\} \log(\frac{1}{\epsilon})$の線形収束率とオラクル複雑性を達成し、$\kappa := L/\sigma$(英語版)となる。 我々はアプローチを拡張して有限サム包含のクラス(おそらく非単調な)を解き、我々のスキームが方程式設定と同じ理論的保証を保持することを示す。 最後に,我々のアルゴリズムを検証し,最先端手法と比較して有望な性能を示す数値実験を行った。

関連論文リスト

• p-Mean Regret for Stochastic Bandits [52.828710025519996]
  単純で統一された UCB ベースのアルゴリズムを導入し、新しい$p$-mean の後悔境界を実現する。 我々の枠組みは、特別な場合として、平均的な累積的後悔とナッシュ後悔の両方を包含する。
  論文  参考訳（メタデータ） (2024-12-14T08:38:26Z)
• Second-Order Min-Max Optimization with Lazy Hessians [17.17389531402505]
  本稿では,凸凹型最小値最適化のための2次法について検討する。 計算コストは反復的にヘッセンによって削減できることを示す。
  論文  参考訳（メタデータ） (2024-10-12T15:30:17Z)
• Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
  複素勾配問題に対する2つの分散化ZO推定器を提案する。 我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
  論文  参考訳（メタデータ） (2024-10-03T15:04:01Z)
• A Proximal Modified Quasi-Newton Method for Nonsmooth Regularized Optimization [0.7373617024876725]
  Lipschitz-of-$nabla f$ $mathcalS_k|p$。 $mathcalS_k|p$。 $nabla f$. $mathcalS_k|p$。
  論文  参考訳（メタデータ） (2024-09-28T18:16:32Z)
• An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue Optimization Problems [76.2042837251496]
  相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。 注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。 本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
  論文  参考訳（メタデータ） (2023-06-30T08:34:29Z)
• Stochastic Distributed Optimization under Average Second-order Similarity: Algorithms and Analysis [36.646876613637325]
  マスタノードと$n-1$ローカルノードを含む有限サム分散最適化問題について検討する。 本稿では,SVRSとAccSVRSの2つの新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-04-15T08:18:47Z)
• A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
  本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。 特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
  論文  参考訳（メタデータ） (2023-01-10T20:43:29Z)
• Randomized Block-Coordinate Optimistic Gradient Algorithms for Root-Finding Problems [11.15373699918747]
  大規模設定における非線形方程式の解を近似する2つの新しいアルゴリズムを開発した。 本稿では,機械学習,統計的学習,ネットワーク最適化などにおける顕著な応用を網羅した大規模有限サム包含のクラスに適用する。
  論文  参考訳（メタデータ） (2023-01-08T21:46:27Z)
• Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [86.05440220344755]
  我々は,非制約のmin-max最適化問題のグローバルなサドル点を求めるために,不正確な正規化ニュートン型手法を提案し,解析する。 提案手法は有界集合内に留まるイテレートを生成し、その反復は制限関数の項で$O(epsilon-2/3)$内の$epsilon$-saddle点に収束することを示す。
  論文  参考訳（メタデータ） (2022-10-23T21:24:37Z)
• Halpern-Type Accelerated and Splitting Algorithms For Monotone Inclusions [14.445131747570962]
  我々は、最大単調方程式のクラスを解くために、新しいタイプの加速アルゴリズムを開発する。 我々の手法は[32]におけるハルパーン型固定点反復と呼ばれるものに依存しており、近年多くの研究者が利用している。
  論文  参考訳（メタデータ） (2021-10-15T15:26:32Z)
• Nonconvex Zeroth-Order Stochastic ADMM Methods with Lower Function Query Complexity [109.54166127479093]
  ゼロ次法(ゼロ次法、英: Zeroth-order method)は、機械学習問題を解決するための効果的な最適化手法のクラスである。 本稿では,非有限項問題を解くために,より高速なゼロ階交互勾配法乗算器 (MMADMM) を提案する。 我々は、ZOMMAD法が、$epsilon$-stationary pointを見つけるために、より低い関数$O(frac13nfrac1)$を達成することができることを示す。 同時に、より高速なゼロオーダーオンラインADM手法(M)を提案する。
  論文  参考訳（メタデータ） (2019-07-30T02:21:43Z)

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

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