論文の概要: Adaptive Accelerated (Extra-)Gradient Methods with Variance Reduction
- arxiv url: http://arxiv.org/abs/2201.12302v1
- Date: Fri, 28 Jan 2022 18:07:25 GMT
- ステータス: 処理完了
- システム内更新日: 2022-01-31 16:32:46.566735
- Title: Adaptive Accelerated (Extra-)Gradient Methods with Variance Reduction
- Title（参考訳）: 可変化を伴う適応加速度(Extra-)勾配法
- Authors: Zijian Liu, Ta Duy Nguyen, Alina Ene, Huy L. Nguyen
- Abstract要約: AdaVRAE(Adaptive Variance Reduced Accelerated Extra-Gradient)とAdaVRAG(Adaptive Variance Reduced Accelerated Gradient)の2つの新しい適応VRアルゴリズムを提案する。
我々のアルゴリズムは滑らかさパラメータの知識を必要としない。
実世界のデータセットを用いた実験において,従来の手法と比較して,アルゴリズムの性能が優れていることを示す。
- 参考スコア（独自算出の注目度）: 25.94147708122371
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we study the finite-sum convex optimization problem focusing
on the general convex case. Recently, the study of variance reduced (VR)
methods and their accelerated variants has made exciting progress. However, the
step size used in the existing VR algorithms typically depends on the
smoothness parameter, which is often unknown and requires tuning in practice.
To address this problem, we propose two novel adaptive VR algorithms: Adaptive
Variance Reduced Accelerated Extra-Gradient (AdaVRAE) and Adaptive Variance
Reduced Accelerated Gradient (AdaVRAG). Our algorithms do not require knowledge
of the smoothness parameter. AdaVRAE uses $\mathcal{O}\left(n\log\log
n+\sqrt{\frac{n\beta}{\epsilon}}\right)$ gradient evaluations and AdaVRAG uses
$\mathcal{O}\left(n\log\log n+\sqrt{\frac{n\beta\log\beta}{\epsilon}}\right)$
gradient evaluations to attain an $\mathcal{O}(\epsilon)$-suboptimal solution,
where $n$ is the number of functions in the finite sum and $\beta$ is the
smoothness parameter. This result matches the best-known convergence rate of
non-adaptive VR methods and it improves upon the convergence of the state of
the art adaptive VR method, AdaSVRG. We demonstrate the superior performance of
our algorithms compared with previous methods in experiments on real-world
datasets.
- Abstract（参考訳）: 本稿では,一般凸の場合に着目した有限サム凸最適化問題について検討する。
近年, 分散低減(VR)法とその加速変種の研究は, わくわくする進歩を遂げている。
しかし、既存のVRアルゴリズムで使用されるステップサイズは、しばしば未知であり、実際にチューニングを必要とする滑らかさパラメータに依存する。
この問題に対処するため,Adaptive Variance Reduced Accelerated Extra-Gradient (AdaVRAE) とAdaptive Variance Reduced Accelerated Gradient (AdaVRAG) の2つの新しい適応VRアルゴリズムを提案する。
我々のアルゴリズムは滑らかさパラメータの知識を必要としない。
AdaVRAE は $\mathcal{O}\left(n\log\log n+\sqrt {\frac{n\beta}{\epsilon}}\right)$グルーフ評価と AdaVRAG は $\mathcal{O}\left(n\log\log n+\sqrt {\frac{n\beta\log\beta}{\epsilon}}\right)$グルーフ評価を使用して $\mathcal{O}(\epsilon)$-suboptimal Solution を得る。
この結果は、非適応型VR手法の最もよく知られた収束率と一致し、アート適応型VR手法であるAdaSVRGの収束率を改善する。
実世界のデータセット実験における従来の手法と比較して,アルゴリズムの優れた性能を示す。
関連論文リスト
- Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity [50.25258834153574]
我々は、(強に)凸 $(L0)$-smooth 関数のクラスに焦点を当て、いくつかの既存のメソッドに対する新しい収束保証を導出する。
特に,スムーズなグラディエント・クリッピングを有するグラディエント・ディフレッシュと,ポリアク・ステップサイズを有するグラディエント・ディフレッシュのコンバージェンス・レートの改善を導出した。
論文 参考訳（メタデータ） (2024-09-23T13:11:37Z) - 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) - ELRA: Exponential learning rate adaption gradient descent optimization
method [83.88591755871734]
我々は, 高速(指数率), ab initio(超自由)勾配に基づく適応法を提案する。
本手法の主な考え方は,状況認識による$alphaの適応である。
これは任意の次元 n の問題に適用でき、線型にしかスケールできない。
論文 参考訳（メタデータ） (2023-09-12T14:36:13Z) - AdaGDA: Faster Adaptive Gradient Descent Ascent Methods for Minimax
Optimization [104.96004056928474]
本稿では,非コンケーブ最小値問題に対する高速適応勾配降下法を提案する。
我々は,本手法が,ミニバッチサイズが$O(kappa2.5epsilon-3)$のより低いサンプル複雑性に達することを示す。
論文 参考訳（メタデータ） (2021-06-30T14:47:09Z) - SVRG Meets AdaGrad: Painless Variance Reduction [34.42463428418348]
一般的なVR手法であるSVRGの完全適応型を提案する。
AdaSVRGはSVRGの内部ループでAdaGradを使用し、ステップサイズの選択に堅牢にします。
AdaSVRGのロバスト性と有効性を検証し、他の「ツインフリー」VR手法よりも優れた性能を示す。
論文 参考訳（メタデータ） (2021-02-18T22:26:19Z) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文 参考訳（メタデータ） (2021-02-15T07:10:33Z) - Gradient Free Minimax Optimization: Variance Reduction and Faster
Convergence [120.9336529957224]
本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。
本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
論文 参考訳（メタデータ） (2020-06-16T17:55:46Z) - Zeroth-Order Regularized Optimization (ZORO): Approximately Sparse
Gradients and Adaptive Sampling [29.600975900977343]
我々はZOROと呼ばれる新しい$textbfZ$eroth-$textbfO$rder $textbfR$egularized $textbfO$ptimization法を提案する。
基礎となる勾配がイテレートでほぼスパースである場合、ZOROは目的関数を減少させる新しいイテレートを得るために、非常に少数の客観的関数評価を必要とする。
論文 参考訳（メタデータ） (2020-03-29T11:01:17Z) - Towards Better Understanding of Adaptive Gradient Algorithms in
Generative Adversarial Nets [71.05306664267832]
適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。
本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。
実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
論文 参考訳（メタデータ） (2019-12-26T22:10:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。