論文の概要: A Variance Controlled Stochastic Method with Biased Estimation for
Faster Non-convex Optimization
- arxiv url: http://arxiv.org/abs/2102.09893v1
- Date: Fri, 19 Feb 2021 12:22:56 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-22 13:31:20.378505
- Title: A Variance Controlled Stochastic Method with Biased Estimation for
Faster Non-convex Optimization
- Title（参考訳）: より高速な非凸最適化のためのバイアス推定を用いた可変制御確率法
- Authors: Jia Bi, Steve R.Gunn
- Abstract要約: 減少勾配(SVRG)の性能を向上させるために, 分散制御勾配(VCSG)という新しい手法を提案する。
ラムダ$はVCSGで導入され、SVRGによる分散の過剰還元を避ける。
$mathcalO(min1/epsilon3/2,n1/4/epsilon)$ 勾配評価の数。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we proposed a new technique, {\em variance controlled
stochastic gradient} (VCSG), to improve the performance of the stochastic
variance reduced gradient (SVRG) algorithm. To avoid over-reducing the variance
of gradient by SVRG, a hyper-parameter $\lambda$ is introduced in VCSG that is
able to control the reduced variance of SVRG. Theory shows that the
optimization method can converge by using an unbiased gradient estimator, but
in practice, biased gradient estimation can allow more efficient convergence to
the vicinity since an unbiased approach is computationally more expensive.
$\lambda$ also has the effect of balancing the trade-off between unbiased and
biased estimations. Secondly, to minimize the number of full gradient
calculations in SVRG, a variance-bounded batch is introduced to reduce the
number of gradient calculations required in each iteration. For smooth
non-convex functions, the proposed algorithm converges to an approximate
first-order stationary point (i.e.
$\mathbb{E}\|\nabla{f}(x)\|^{2}\leq\epsilon$) within
$\mathcal{O}(min\{1/\epsilon^{3/2},n^{1/4}/\epsilon\})$ number of stochastic
gradient evaluations, which improves the leading gradient complexity of
stochastic gradient-based method SCS
$(\mathcal{O}(min\{1/\epsilon^{5/3},n^{2/3}/\epsilon\})$. It is shown
theoretically and experimentally that VCSG can be deployed to improve
convergence.
- Abstract（参考訳）: 本稿では,確率分散低減勾配(svrg)アルゴリズムの性能を向上させるための新しい手法であるvcsg(em variance controlled stochastic gradient)を提案する。
SVRGによる勾配のばらつきの過度な低減を避けるため、VCSGでは超パラメータ$\lambda$を導入し、SVRGのばらつきを抑えることができる。
理論的には、この最適化法は偏りのない勾配推定器を用いて収束できるが、実際には偏りのある勾配推定は、偏りのないアプローチの方が計算コストが高いため、より効率的な近傍収束を可能にする。
また$\lambda$は偏りのない見積もりと偏りのある見積もりのトレードオフのバランスをとる効果もある。
次に,svrgにおけるフルグラデーション計算回数を最小化するため,各イテレーションに必要なグラデーション計算数を削減する分散バウンドバッチを導入する。
滑らかな非凸関数に対して、提案されたアルゴリズムは近似一階定常点(すなわち)に収束する。
{\mathbb{e}\|\nabla{f}(x)\|^{2}\leq\epsilon$) in $\mathcal{o}(min\{1/\epsilon^{3/2},n^{1/4}/\epsilon\})$ of stochasticgradient evaluations これは、確率的勾配に基づくメソッド scs $(\mathcal{o}(min\{1/\epsilon^{5/3},n^{2/3}/\epsilon\})$ の主勾配の複雑さを改善する。
理論的および実験的に、収束を改善するためにVCSGをデプロイできることが示されている。
関連論文リスト
- 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) - Flattened one-bit stochastic gradient descent: compressed distributed optimization with controlled variance [55.01966743652196]
パラメータ・サーバ・フレームワークにおける圧縮勾配通信を用いた分散勾配降下(SGD)のための新しいアルゴリズムを提案する。
平坦な1ビット勾配勾配勾配法(FO-SGD)は2つの単純なアルゴリズムの考え方に依存している。
論文 参考訳（メタデータ） (2024-05-17T21:17:27Z) - Differentiable Annealed Importance Sampling and the Perils of Gradient
Noise [68.44523807580438]
Annealed importance sample (AIS) と関連するアルゴリズムは、限界推定のための非常に効果的なツールである。
差別性は、目的として限界確率を最適化する可能性を認めるため、望ましい性質である。
我々はメトロポリス・ハスティングスのステップを放棄して微分可能アルゴリズムを提案し、ミニバッチ計算をさらに解き放つ。
論文 参考訳（メタデータ） (2021-07-21T17:10:14Z) - High-probability Bounds for Non-Convex Stochastic Optimization with
Heavy Tails [55.561406656549686]
我々は、勾配推定が末尾を持つ可能性のある一階アルゴリズムを用いたヒルベルト非最適化を考える。
本研究では, 勾配, 運動量, 正規化勾配勾配の収束を高確率臨界点に収束させることと, 円滑な損失に対する最もよく知られた繰り返しを示す。
論文 参考訳（メタデータ） (2021-06-28T00:17:01Z) - Stochastic Bias-Reduced Gradient Methods [44.35885731095432]
モロー・吉田関数の任意の有界な$x_star$の低バイアスで低コストな平滑化である。
論文 参考訳（メタデータ） (2021-06-17T13:33:05Z) - Improving the Transient Times for Distributed Stochastic Gradient
Methods [5.215491794707911]
拡散適応段階法(EDAS)と呼ばれる分散勾配アルゴリズムについて検討する。
EDASが集中勾配降下(SGD)と同じネットワーク独立収束率を達成することを示す。
我々の知る限り、EDASは$n$のコスト関数の平均が強い凸である場合に最も短い時間を達成する。
論文 参考訳（メタデータ） (2021-05-11T08:09:31Z) - Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box
Optimization Framework [100.36569795440889]
この作業は、一階情報を必要としない零次最適化(ZO)の反復である。
座標重要度サンプリングにおける優雅な設計により,ZO最適化法は複雑度と関数クエリコストの両面において効率的であることを示す。
論文 参考訳（メタデータ） (2020-12-21T17:29:58Z) - Variance Reduction with Sparse Gradients [82.41780420431205]
SVRGやSpiderBoostのような分散還元法では、大きなバッチ勾配と小さなバッチ勾配が混在している。
我々は、新しい空間演算子:ランダムトップk演算子を導入する。
我々のアルゴリズムは、画像分類、自然言語処理、スパース行列分解など様々なタスクにおいて、一貫してSpiderBoostより優れています。
論文 参考訳（メタデータ） (2020-01-27T08:23:58Z) - Stochastic gradient-free descents [8.663453034925363]
本稿では,最適化問題の解法として,モーメント付き勾配法と加速勾配を提案する。
本研究では,これらの手法の収束挙動を平均分散フレームワークを用いて解析する。
論文 参考訳（メタデータ） (2019-12-31T13:56:36Z) - Towards Better Understanding of Adaptive Gradient Algorithms in
Generative Adversarial Nets [71.05306664267832]
適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。
本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。
実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
論文 参考訳（メタデータ） (2019-12-26T22:10:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。