論文の概要: SignSVRG: fixing SignSGD via variance reduction
- arxiv url: http://arxiv.org/abs/2305.13187v1
- Date: Mon, 22 May 2023 16:14:53 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-23 14:39:06.889199
- Title: SignSVRG: fixing SignSGD via variance reduction
- Title（参考訳）: SignSVRG:分散還元によるSignSGDの固定
- Authors: Evgenii Chzhen and Sholom Schechtman
- Abstract要約: 本稿では SignSGD に分散低減手法を組み込むための, 単純かつ実用的な方法を提案する。
滑らかな関数に対しては、勾配の期待ノルムに対して $mathcalO (1 / sqrtT)$ rate と、滑らかな凸関数の場合 $mathcalO (1/T)$ rate を与える。
- 参考スコア（独自算出の注目度）: 3.3504365823045044
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the problem of unconstrained minimization of finite sums of
functions. We propose a simple, yet, practical way to incorporate variance
reduction techniques into SignSGD, guaranteeing convergence that is similar to
the full sign gradient descent. The core idea is first instantiated on the
problem of minimizing sums of convex and Lipschitz functions and is then
extended to the smooth case via variance reduction. Our analysis is elementary
and much simpler than the typical proof for variance reduction methods. We show
that for smooth functions our method gives $\mathcal{O}(1 / \sqrt{T})$ rate for
expected norm of the gradient and $\mathcal{O}(1/T)$ rate in the case of smooth
convex functions, recovering convergence results of deterministic methods,
while preserving computational advantages of SignSGD.
- Abstract（参考訳）: 関数の有限和の制約のない最小化の問題を考える。
我々は,完全な符号勾配降下に類似した収束を保証するために,分散低減手法をsigngdに組み込むための単純かつ実用的な方法を提案する。
中心的なアイデアは、まず凸関数とリプシッツ関数の和を最小化する問題に基づいてインスタンス化され、次に分散還元によって滑らかなケースに拡張される。
我々の分析は、分散還元法における典型的な証明よりも単純で初等的である。
滑らかな関数に対して、この手法は勾配の期待ノルムに対して$\mathcal{o}(1 / \sqrt{t})$レートを与え、滑らかな凸関数の場合は$\mathcal{o}(1/t)$レートを与え、決定論的手法の収束結果を回復し、signalgdの計算上の利点を保った。
関連論文リスト
- 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) - 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) - Towards Noise-adaptive, Problem-adaptive Stochastic Gradient Descent [7.176107039687231]
雑音に対して勾配降下(SGD)を適応させるステップサイズスキームを設計する。
我々は、Nesterov反復によるSGDの$T$反復がほぼ最適であることを示す。
他のステップサイズスキームと比較して、新しい指数的なステップサイズスキームの有効性を実証する。
論文 参考訳（メタデータ） (2021-10-21T19:22:14Z) - 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) - Unified Analysis of Stochastic Gradient Methods for Composite Convex and
Smooth Optimization [15.82816385434718]
本稿では、滑らかで凸な損失と凸正則化器を最小化するための勾配アルゴリズムの収束解析のための統一定理を提案する。
我々は、Gorbunov, Hanzely & Richt'arik (2020) の統一解析を拡張し、損失関数が強く凸であるという要求を下げる。
我々の統一解析は、近位SGD、分散還元法、量子化、およびいくつかの座標降下型法などの既存のアルゴリズムのホストに適用できる。
論文 参考訳（メタデータ） (2020-06-20T13:40:27Z) - On the Almost Sure Convergence of Stochastic Gradient Descent in
Non-Convex Problems [75.58134963501094]
本稿では,勾配降下(SGD)の軌跡を解析する。
我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
論文 参考訳（メタデータ） (2020-06-19T14:11:26Z) - Gradient Free Minimax Optimization: Variance Reduction and Faster
Convergence [120.9336529957224]
本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。
本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
論文 参考訳（メタデータ） (2020-06-16T17:55:46Z) - A Simple Convergence Proof of Adam and Adagrad [74.24716715922759]
我々はAdam Adagradと$O(d(N)/st)$アルゴリズムの収束の証明を示す。
Adamはデフォルトパラメータで使用する場合と同じ収束$O(d(N)/st)$で収束する。
論文 参考訳（メタデータ） (2020-03-05T01:56:17Z) - Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。
特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
論文 参考訳（メタデータ） (2020-02-10T23:23:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。