論文の概要: Stochastic gradient-free descents
- arxiv url: http://arxiv.org/abs/1912.13305v5
- Date: Tue, 14 Jan 2020 10:31:56 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-16 21:38:51.334124
- Title: Stochastic gradient-free descents
- Title(参考訳): 確率勾配自由降下
- Authors: Xiaopeng Luo and Xin Xu
- Abstract要約: 本稿では,最適化問題の解法として,モーメント付き勾配法と加速勾配を提案する。
本研究では,これらの手法の収束挙動を平均分散フレームワークを用いて解析する。
- 参考スコア(独自算出の注目度): 8.663453034925363
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper we propose stochastic gradient-free methods and accelerated
methods with momentum for solving stochastic optimization problems. All these
methods rely on stochastic directions rather than stochastic gradients. We
analyze the convergence behavior of these methods under the mean-variance
framework, and also provide a theoretical analysis about the inclusion of
momentum in stochastic settings which reveals that the momentum term we used
adds a deviation of order $\mathcal{O}(1/k)$ but controls the variance at the
order $\mathcal{O}(1/k)$ for the $k$th iteration. So it is shown that, when
employing a decaying stepsize $\alpha_k=\mathcal{O}(1/k)$, the stochastic
gradient-free methods can still maintain the sublinear convergence rate
$\mathcal{O}(1/k)$ and the accelerated methods with momentum can achieve a
convergence rate $\mathcal{O}(1/k^2)$ in probability for the strongly convex
objectives with Lipschitz gradients; and all these methods converge to a
solution with a zero expected gradient norm when the objective function is
nonconvex, twice differentiable and bounded below.
- Abstract(参考訳): 本稿では,確率的最適化問題を解くためのモーメント付き確率的勾配自由法と加速法を提案する。
これらの手法はすべて確率的勾配よりも確率的方向に依存する。
平均分散フレームワークの下でこれらの手法の収束挙動を解析し、また確率的条件におけるモーメントの包含に関する理論的解析を行い、使用したモーメント項が次数$\mathcal{O}(1/k)$の偏差を付加することを示したが、$k$1/k)$の次数$\mathcal{O}(1/k)$で分散を制御する。
So it is shown that, when employing a decaying stepsize $\alpha_k=\mathcal{O}(1/k)$, the stochastic gradient-free methods can still maintain the sublinear convergence rate $\mathcal{O}(1/k)$ and the accelerated methods with momentum can achieve a convergence rate $\mathcal{O}(1/k^2)$ in probability for the strongly convex objectives with Lipschitz gradients; and all these methods converge to a solution with a zero expected gradient norm when the objective function is nonconvex, twice differentiable and bounded below.
関連論文リスト
- Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization
Problems [61.002740957716156]
構造密度の重み付き雑音によるクリップ最適化問題を考察する。
勾配が有限の順序モーメントを持つとき、$mathcalO(K-(alpha - 1)/alpha)$よりも高速な収束率が得られることを示す。
得られた推定値が無視可能なバイアスと制御可能な分散を持つことを示す。
論文 参考訳(メタデータ) (2023-11-07T17:39:17Z) - Asymptotically efficient one-step stochastic gradient descent [62.997667081978825]
これはフィッシャースコアリングアルゴリズムの単一ステップで補正された対数型関数の勾配勾配に基づいている。
理論的およびシミュレーションにより、これは平均勾配あるいは適応勾配勾配の通常の勾配勾配の代替として興味深いものであることをi.d設定で示す。
論文 参考訳(メタデータ) (2023-06-09T13:43:07Z) - CEDAS: A Compressed Decentralized Stochastic Gradient Method with
Improved Convergence [10.770843226843418]
本稿では,通信制限条件下でのマルチエージェントネットワークの分散最適化問題について考察する。
提案手法は,CEDAS (Convexizes) を圧縮し,滑らかな凸関連ステップの適応的なステップを実現する。
論文 参考訳(メタデータ) (2023-01-14T09:49:15Z) - Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。
漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文 参考訳(メタデータ) (2022-06-17T06:10:20Z) - Statistical Inference of Constrained Stochastic Optimization via
Sketched Sequential Quadratic Programming [59.36379287247961]
この問題を解決するために,完全オンライン逐次2次プログラミング(StoSQP)手法を開発した。
最近の数値二階法の設計により、StoSQPは任意のランダムなステップサイズを適応的に選択できる。
また,2次法の計算コストを大幅に削減するため,StoSQPはランダム化反復解法を用いて2次プログラムを不正確に解けるようにした。
論文 参考訳(メタデータ) (2022-05-27T00:34:03Z) - Fast Margin Maximization via Dual Acceleration [52.62944011696364]
指数関数的尾の損失を持つ線形分類器を訓練するための運動量に基づく手法を提案し,解析する。
この運動量に基づく法は、最大マルジン問題の凸双対、特にこの双対にネステロフ加速度を適用することによって導出される。
論文 参考訳(メタデータ) (2021-07-01T16:36:39Z) - High-probability Bounds for Non-Convex Stochastic Optimization with
Heavy Tails [55.561406656549686]
我々は、勾配推定が末尾を持つ可能性のある一階アルゴリズムを用いたヒルベルト非最適化を考える。
本研究では, 勾配, 運動量, 正規化勾配勾配の収束を高確率臨界点に収束させることと, 円滑な損失に対する最もよく知られた繰り返しを示す。
論文 参考訳(メタデータ) (2021-06-28T00:17:01Z) - 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) - Almost sure convergence rates for Stochastic Gradient Descent and
Stochastic Heavy Ball [17.33867778750777]
一般近似問題に対する勾配降下法(SGD)と重球法(SHB)について検討した。
SGD の場合、凸と滑らかな設定において、イテレートの重み付き平均に対して、最初の最も確実な収束式を提供する。
論文 参考訳(メタデータ) (2020-06-14T11:12:05Z) - The Implicit Regularization of Stochastic Gradient Flow for Least
Squares [24.976079444818552]
最小二乗回帰の基本問題に適用したミニバッチ勾配勾配の暗黙正則化について検討した。
我々は勾配流と呼ばれる勾配降下と同じモーメントを持つ連続時間微分方程式を利用する。
チューニングパラメータ $lambda = 1/t$ で、リッジレグレッションを越えて、時間 $t$ での勾配フローの過剰なリスクに制限を与えます。
論文 参考訳(メタデータ) (2020-03-17T16:37:25Z) - Can speed up the convergence rate of stochastic gradient methods to
$\mathcal{O}(1/k^2)$ by a gradient averaging strategy? [8.663453034925363]
私たちが定義した反復的分散が、勾配反復においてほんの少しでも支配的であれば、提案した勾配平均化戦略は収束率を高めることができる。
この結論は、収束率を改善するために勾配の反復をどのように制御すべきかを示唆している。
論文 参考訳(メタデータ) (2020-02-25T09:58:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。