論文の概要: Stochastic Zeroth order Descent with Structured Directions
- arxiv url: http://arxiv.org/abs/2206.05124v1
- Date: Fri, 10 Jun 2022 14:00:06 GMT
- ステータス: 処理完了
- システム内更新日: 2022-06-13 16:08:05.067288
- Title: Stochastic Zeroth order Descent with Structured Directions
- Title(参考訳): 構造方向をもつ確率零次輝線
- Authors: Marco Rando, Cesare Molinari, Silvia Villa, Lorenzo Rosasco
- Abstract要約: 有限差分法であるStructured Zeroth Order Descent (S-SZD) を導入・解析し、その場合、$d は周囲空間の次元である集合 $lleq d 方向の勾配を近似する。
凸に関して、収束境界と収束率はほぼ確実に証明し、各$c1/2$は、反復数に関してグラディエント Descent (SGD) の値に任意に近い。
- 参考スコア(独自算出の注目度): 14.338969001937068
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We introduce and analyze Structured Stochastic Zeroth order Descent (S-SZD),
a finite difference approach which approximates a stochastic gradient on a set
of $l\leq d$ orthogonal directions, where $d$ is the dimension of the ambient
space. These directions are randomly chosen, and may change at each step. For
smooth convex functions we prove almost sure convergence of the iterates and a
convergence rate on the function values of the form $O(d/l k^{-c})$ for every
$c<1/2$, which is arbitrarily close to the one of Stochastic Gradient Descent
(SGD) in terms of number of iterations. Our bound also shows the benefits of
using $l$ multiple directions instead of one. For non-convex functions
satisfying the Polyak-{\L}ojasiewicz condition, we establish the first
convergence rates for stochastic zeroth order algorithms under such an
assumption. We corroborate our theoretical findings in numerical simulations
where assumptions are satisfied and on the real-world problem of
hyper-parameter optimization, observing that S-SZD has very good practical
performances.
- Abstract(参考訳): d$が周囲の空間の次元である$l\leq d$直交方向の集合上の確率勾配を近似する有限差分法である構造化確率的零次降下 (s-szd) を導入し,解析する。
これらの方向はランダムに選択され、各ステップで変更される。
滑らかな凸関数に対しては、反復数の収束がほぼ確実に証明され、反復数で確率的勾配降下 (sgd) の1つに任意に近く、各$c<1/2$ に対して $o(d/l k^{-c})$ という形の関数値の収束率が証明される。
私たちの境界はまた、$l$の複数の方向を使う利点を示している。
Polyak-{\L}ojasiewicz 条件を満たす非凸函数に対して、そのような仮定の下で確率零次アルゴリズムに対する最初の収束率を確立する。
S-SZDは,仮定が満たされる数値シミュレーションや,超パラメータ最適化の現実問題において,非常に優れた実用性能を有することを観察する。
関連論文リスト
- On Convergence of Incremental Gradient for Non-Convex Smooth Functions [63.51187646914962]
機械学習とネットワーク最適化では、ミスの数と優れたキャッシュを最小化するため、シャッフルSGDのようなアルゴリズムが人気である。
本稿では任意のデータ順序付けによる収束特性SGDアルゴリズムについて述べる。
論文 参考訳(メタデータ) (2023-05-30T17:47:27Z) - Zero-Order One-Point Estimate with Distributed Stochastic
Gradient-Tracking Technique [23.63073074337495]
本研究では,各エージェントが滑らかで凸な局所目的関数を持つ分散マルチエージェント最適化問題を考える。
分散勾配追跡法を,勾配推定のない帯域設定に拡張する。
近似ツールを用いた滑らかで凸な目的のための新しい手法の収束解析を行う。
論文 参考訳(メタデータ) (2022-10-11T17:04:45Z) - Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。
漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文 参考訳(メタデータ) (2022-06-17T06:10:20Z) - 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) - A Projection-free Algorithm for Constrained Stochastic Multi-level
Composition Optimization [12.096252285460814]
合成最適化のためのプロジェクションフリー条件付き勾配型アルゴリズムを提案する。
提案アルゴリズムで要求されるオラクルの数と線形最小化オラクルは,それぞれ$mathcalO_T(epsilon-2)$と$mathcalO_T(epsilon-3)$である。
論文 参考訳(メタデータ) (2022-02-09T06:05:38Z) - Optimal and instance-dependent guarantees for Markovian linear
stochastic approximation [77.84027086542827]
標準スキームの最後の繰り返しの2乗誤差に対して、$t_mathrmmix tfracdn$の非漸近境界を示す。
マルコフ雑音による政策評価について,これらの結果のまとめを導出する。
論文 参考訳(メタデータ) (2021-12-23T18:47:50Z) - On the Almost Sure Convergence of Stochastic Gradient Descent in
Non-Convex Problems [75.58134963501094]
本稿では,勾配降下(SGD)の軌跡を解析する。
我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
論文 参考訳(メタデータ) (2020-06-19T14:11:26Z) - Almost sure convergence rates for Stochastic Gradient Descent and
Stochastic Heavy Ball [17.33867778750777]
一般近似問題に対する勾配降下法(SGD)と重球法(SHB)について検討した。
SGD の場合、凸と滑らかな設定において、イテレートの重み付き平均に対して、最初の最も確実な収束式を提供する。
論文 参考訳(メタデータ) (2020-06-14T11:12:05Z) - S-ADDOPT: Decentralized stochastic first-order optimization over
directed graphs [16.96562173221624]
有向ネットワークノード上に分散する関数のスムーズかつ高コストな関数の和を最小化するために,分散凸最適化を提案する。
特に,各ノードに1次オラクルを仮定するtextbftextttS-ADDOPTアルゴリズムを提案する。
崩壊するステップサイズ$mathcalO (1/k)$に対して、textbfttS-ADDOPT が$mathcalO (1/k)$ で正解に達し、その収束はネットワーク非依存であることを示す。
論文 参考訳(メタデータ) (2020-05-15T21:14:22Z) - Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。
特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
論文 参考訳(メタデータ) (2020-02-10T23:23:04Z) - Better Theory for SGD in the Nonconvex World [2.6397379133308214]
大規模な非最適化問題は、現代の機械学習ではユビキタスである。
我々は, 広範囲の合成ミニバッチサイズがグラディエントDescent (SG) 問題に与える影響について実験を行った。
論文 参考訳(メタデータ) (2020-02-09T09:56:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。