論文の概要: Unified Analysis of Stochastic Gradient Methods for Composite Convex and
Smooth Optimization
- arxiv url: http://arxiv.org/abs/2006.11573v1
- Date: Sat, 20 Jun 2020 13:40:27 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-18 22:27:52.346295
- Title: Unified Analysis of Stochastic Gradient Methods for Composite Convex and
Smooth Optimization
- Title(参考訳): 複合凸・平滑最適化のための確率勾配法の統一解析
- Authors: Ahmed Khaled, Othmane Sebbouh, Nicolas Loizou, Robert M. Gower, Peter
Richt\'arik
- Abstract要約: 本稿では、滑らかで凸な損失と凸正則化器を最小化するための勾配アルゴリズムの収束解析のための統一定理を提案する。
我々は、Gorbunov, Hanzely & Richt'arik (2020) の統一解析を拡張し、損失関数が強く凸であるという要求を下げる。
我々の統一解析は、近位SGD、分散還元法、量子化、およびいくつかの座標降下型法などの既存のアルゴリズムのホストに適用できる。
- 参考スコア(独自算出の注目度): 15.82816385434718
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We present a unified theorem for the convergence analysis of stochastic
gradient algorithms for minimizing a smooth and convex loss plus a convex
regularizer. We do this by extending the unified analysis of Gorbunov, Hanzely
\& Richt\'arik (2020) and dropping the requirement that the loss function be
strongly convex. Instead, we only rely on convexity of the loss function. Our
unified analysis applies to a host of existing algorithms such as proximal SGD,
variance reduced methods, quantization and some coordinate descent type
methods. For the variance reduced methods, we recover the best known
convergence rates as special cases. For proximal SGD, the quantization and
coordinate type methods, we uncover new state-of-the-art convergence rates. Our
analysis also includes any form of sampling and minibatching. As such, we are
able to determine the minibatch size that optimizes the total complexity of
variance reduced methods. We showcase this by obtaining a simple formula for
the optimal minibatch size of two variance reduced methods (\textit{L-SVRG} and
\textit{SAGA}). This optimal minibatch size not only improves the theoretical
total complexity of the methods but also improves their convergence in
practice, as we show in several experiments.
- Abstract(参考訳): 本稿では,滑らかな凸損失と凸正規化子を最小化する確率的勾配アルゴリズムの収束解析のための統一定理を提案する。
我々は、Gorbunov, Hanzely \& Richt\'arik (2020) の統一解析を拡張し、損失関数が強く凸であるという要求を下げる。
代わりに、損失関数の凸性のみに依存します。
この統一解析は, 近位sgd法, 分散還元法, 量子化法, 座標降下型法などの既存のアルゴリズムのホストに適用できる。
分散低減法では, 特別な場合として最もよく知られた収束率を回復する。
量子化法と座標型法である近位sgdについて,新しい収束率を明らかにする。
分析にはサンプリングやミニバッチも含んでいます。
これにより,分散低減法の全複雑性を最適化するミニバッチサイズを決定できる。
2つの分散還元法 (\textit{l-svrg} と \textit{saga}) の最適ミニバッチサイズに対する簡単な公式を得ることで、これを示す。
この最適ミニバッチサイズは、理論全体の複雑性を向上させるだけでなく、いくつかの実験で示されているように、実際の収束性も改善する。
関連論文リスト
- Variance reduction techniques for stochastic proximal point algorithms [5.374800961359305]
そこで本研究では,近点アルゴリズムにおける分散低減手法の統一化研究を提案する。
我々は,SVRG,SAGA,およびそれらの変種の近位バージョンを提供するために特定可能な,汎用的近位アルゴリズムを提案する。
本実験は, 勾配法よりも近似分散還元法の利点を実証する。
論文 参考訳(メタデータ) (2023-08-18T05:11:50Z) - SignSVRG: fixing SignSGD via variance reduction [3.3504365823045044]
本稿では SignSGD に分散低減手法を組み込むための, 単純かつ実用的な方法を提案する。
滑らかな関数に対しては、勾配の期待ノルムに対して $mathcalO (1 / sqrtT)$ rate と、滑らかな凸関数の場合 $mathcalO (1/T)$ rate を与える。
論文 参考訳(メタデータ) (2023-05-22T16:14:53Z) - Asymptotically Unbiased Instance-wise Regularized Partial AUC
Optimization: Theory and Algorithm [101.44676036551537]
One-way partial AUC (OPAUC) と Two-way partial AUC (TPAUC) はバイナリ分類器の平均性能を測定する。
既存の手法のほとんどはPAUCをほぼ最適化するしかなく、制御不能なバイアスにつながる。
本稿では,分散ロバスト最適化AUCによるPAUC問題の簡易化について述べる。
論文 参考訳(メタデータ) (2022-10-08T08:26:22Z) - Faster One-Sample Stochastic Conditional Gradient Method for Composite
Convex Minimization [61.26619639722804]
滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。
提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
論文 参考訳(メタデータ) (2022-02-26T19:10:48Z) - Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and
Beyond [63.59034509960994]
シャッフルに基づく変種(ミニバッチと局所ランダムリシャッフル)について検討する。
ポリアック・ロジャシエヴィチ条件を満たす滑らかな函数に対して、これらのシャッフル型不変量(英語版)(shuffling-based variants)がそれらの置換式よりも早く収束することを示す収束境界を得る。
我々は, 同期シャッフル法と呼ばれるアルゴリズムの修正を提案し, ほぼ均一な条件下では, 下界よりも収束速度が速くなった。
論文 参考訳(メタデータ) (2021-10-20T02:25:25Z) - A Variance Controlled Stochastic Method with Biased Estimation for
Faster Non-convex Optimization [0.0]
減少勾配(SVRG)の性能を向上させるために, 分散制御勾配(VCSG)という新しい手法を提案する。
ラムダ$はVCSGで導入され、SVRGによる分散の過剰還元を避ける。
$mathcalO(min1/epsilon3/2,n1/4/epsilon)$ 勾配評価の数。
論文 参考訳(メタデータ) (2021-02-19T12:22:56Z) - Balancing Rates and Variance via Adaptive Batch-Size for Stochastic
Optimization Problems [120.21685755278509]
本研究は,ステップサイズの減衰が正確な収束に必要であるという事実と,一定のステップサイズがエラーまでの時間でより速く学習するという事実のバランスをとることを目的とする。
ステップサイズのミニバッチを最初から修正するのではなく,パラメータを適応的に進化させることを提案する。
論文 参考訳(メタデータ) (2020-07-02T16:02:02Z) - Gradient Free Minimax Optimization: Variance Reduction and Faster
Convergence [120.9336529957224]
本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。
本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
論文 参考訳(メタデータ) (2020-06-16T17:55:46Z) - Convergence of adaptive algorithms for weakly convex constrained
optimization [59.36386973876765]
モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。
我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
論文 参考訳(メタデータ) (2020-06-11T17:43:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。