Fugu-MT 論文翻訳(概要): Adaptive SGD with Polyak stepsize and Line-search: Robust Convergence and Variance Reduction

論文の概要: Adaptive SGD with Polyak stepsize and Line-search: Robust Convergence and Variance Reduction

arxiv url: http://arxiv.org/abs/2308.06058v1
Date: Fri, 11 Aug 2023 10:17:29 GMT
ステータス: 処理完了
システム内更新日: 2023-08-14 14:25:32.008802
Title: Adaptive SGD with Polyak stepsize and Line-search: Robust Convergence and Variance Reduction
Title（参考訳）: Polyak StepizeとLine-searchによる適応SGD:ロバスト収束と可変化
Authors: Xiaowen Jiang and Sebastian U. Stich
Abstract要約: AdaSPSとAdaSLSと呼ばれる2種類の新しいSPSとSLSを提案し、非補間条件における収束を保証する。我々は, AdaSPS と AdaSLS に新しい分散低減技術を導入し, $smashwidetildemathcalO(n+1/epsilon)$グラデーション評価を必要とするアルゴリズムを得る。
参考スコア（独自算出の注目度）: 29.212978707073855
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: The recently proposed stochastic Polyak stepsize (SPS) and stochastic line-search (SLS) for SGD have shown remarkable effectiveness when training over-parameterized models. However, in non-interpolation settings, both algorithms only guarantee convergence to a neighborhood of a solution which may result in a worse output than the initial guess. While artificially decreasing the adaptive stepsize has been proposed to address this issue (Orvieto et al. [2022]), this approach results in slower convergence rates for convex and over-parameterized models. In this work, we make two contributions: Firstly, we propose two new variants of SPS and SLS, called AdaSPS and AdaSLS, which guarantee convergence in non-interpolation settings and maintain sub-linear and linear convergence rates for convex and strongly convex functions when training over-parameterized models. AdaSLS requires no knowledge of problem-dependent parameters, and AdaSPS requires only a lower bound of the optimal function value as input. Secondly, we equip AdaSPS and AdaSLS with a novel variance reduction technique and obtain algorithms that require $\smash{\widetilde{\mathcal{O}}}(n+1/\epsilon)$ gradient evaluations to achieve an $\mathcal{O}(\epsilon)$-suboptimality for convex functions, which improves upon the slower $\mathcal{O}(1/\epsilon^2)$ rates of AdaSPS and AdaSLS without variance reduction in the non-interpolation regimes. Moreover, our result matches the fast rates of AdaSVRG but removes the inner-outer-loop structure, which is easier to implement and analyze. Finally, numerical experiments on synthetic and real datasets validate our theory and demonstrate the effectiveness and robustness of our algorithms.
Abstract（参考訳）: 近年提案された確率的ポリアックステップズ (sps) と確率的直線探索 (sls) は, 過パラメータモデルのトレーニングにおいて顕著な効果を示した。しかし、非補間設定では、どちらのアルゴリズムも解の近傍への収束を保証し、最初の推測よりも悪い出力をもたらす可能性がある。適応的なステップサイズを人工的に減少させる手法が提案されている(Orvieto et al. [2022])が、このアプローチは凸および過パラメータ化モデルの収束速度を遅くする。本稿では,まず,非補間条件下での収束を保証するSPSとSLSの2つの新しい変種,AdaSPSとAdaSLSを提案する。 AdaSLSは問題依存パラメータの知識を必要とせず、AdaSPSは入力として最適関数値の下位境界のみを必要とする。次に、adasps と adasls を新しい分散還元法で満たし、非補間領域の分散還元なしで adasps と adasls のレートを低下させるような凸関数に対する $\mathcal{o}(\epsilon)$-suboptimality を達成するために、$\smash{\widetilde{\mathcal{o}}}(n+1/\epsilon)$gradient evaluations を必要とするアルゴリズムを得る。さらに,本結果はAdaSVRGの速度と一致するが,実装や解析が容易な内外ループ構造を除去する。最後に、合成および実データセットに関する数値実験により、我々の理論を検証し、アルゴリズムの有効性と堅牢性を示す。

関連論文リスト

Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity [50.25258834153574]
我々は、(強に)凸 $(L0)$-smooth 関数のクラスに焦点を当て、いくつかの既存のメソッドに対する新しい収束保証を導出する。特に,スムーズなグラディエント・クリッピングを有するグラディエント・ディフレッシュと,ポリアク・ステップサイズを有するグラディエント・ディフレッシュのコンバージェンス・レートの改善を導出した。
論文参考訳（メタデータ） (2024-09-23T13:11:37Z)
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)
Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。 TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
論文参考訳（メタデータ） (2023-10-18T10:29:58Z)
Improved Convergence Rate of Stochastic Gradient Langevin Dynamics with Variance Reduction and its Application to Optimization [50.83356836818667]
勾配ランゲヴィン・ダイナミクスは非エプス最適化問題を解くための最も基本的なアルゴリズムの1つである。本稿では、このタイプの2つの変種、すなわち、分散還元ランジュバンダイナミクスと再帰勾配ランジュバンダイナミクスを示す。
論文参考訳（メタデータ） (2022-03-30T11:39:00Z)
Stochastic Mirror Descent: Convergence Analysis and Adaptive Variants via the Mirror Stochastic Polyak Stepsize [20.376216873620763]
比較的滑らかで滑らかな凸最適化の下でのミラー降下(SMD)の収束について検討した。我々は、新しい適応的なステップサイズスキーム、ミラーポリアクステップサイズ(mSPS)を提案する。
論文参考訳（メタデータ） (2021-10-28T19:49:40Z)
Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
論文参考訳（メタデータ） (2021-10-20T02:57:21Z)
Momentum Accelerates the Convergence of Stochastic AUPRC Maximization [80.8226518642952]
高精度リコール曲線(AUPRC)に基づく領域の最適化について検討し,不均衡なタスクに広く利用されている。我々は、$O (1/epsilon4)$のより優れた反復による、$epsilon$定常解を見つけるための新しい運動量法を開発する。また,O(1/epsilon4)$と同じ複雑さを持つ適応手法の新たなファミリを設計し,実際により高速な収束を享受する。
論文参考訳（メタデータ） (2021-07-02T16:21:52Z)
Reducing the Variance of Gaussian Process Hyperparameter Optimization with Preconditioning [54.01682318834995]
プレコンディショニングは、行列ベクトル乗算を含む反復的な方法にとって非常に効果的なステップである。プレコンディショニングには、これまで検討されていなかった付加的なメリットがあることを実証する。基本的に無視可能なコストで、同時に分散を低減することができる。
論文参考訳（メタデータ） (2021-07-01T06:43:11Z)
On Stochastic Variance Reduced Gradient Method for Semidefinite Optimization [14.519696724619074]
SVRG法は最も有効な方法の1つと考えられている。半定型プログラミング(SDP)に適応する場合、理論と実践の間には大きなギャップがある本稿では,このギャップを,半定値最適化に適応したオプションIを用いて,元のSVRGの新たな変種を利用して埋める。
論文参考訳（メタデータ） (2021-01-01T13:55:32Z)
Adaptive extra-gradient methods for min-max optimization and games [35.02879452114223]
本稿では,初期の反復で観測された勾配データの幾何を自動的に活用する,minmax最適化アルゴリズムの新たなファミリーを提案する。この適応機構により,提案手法は問題がスムーズかどうかを自動的に検出する。滑らかな問題における$mathcalO (1/varepsilon)$反復と、非滑らかな問題における$mathcalO (1/varepsilon)$反復に収束する。
論文参考訳（メタデータ） (2020-10-22T22:54:54Z)

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

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