論文の概要: Escaping Saddle-Points Faster under Interpolation-like Conditions
- arxiv url: http://arxiv.org/abs/2009.13016v1
- Date: Mon, 28 Sep 2020 02:15:18 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-13 21:50:19.239593
- Title: Escaping Saddle-Points Faster under Interpolation-like Conditions
- Title(参考訳): 補間条件下でのサドル点の脱出
- Authors: Abhishek Roy, Krishnakumar Balasubramanian, Saeed Ghadimi, Prasant
Mohapatra
- Abstract要約: 過度なパラメータ化の下では、いくつかの標準的な最適化アルゴリズムがサドルポイントを回避し、局所最小化器に収束する。
本稿では、PSGDアルゴリズムの1次オラクル複雑性について論じ、$epsilon$ localminimizerに到達した。
次に、Cubic-Regularized Newton (SCRN)アルゴリズムのアンダーライクな条件を分析し、局所最小化剤アンダーライクな条件に到達するためのオラクルの複雑さが$tildemathcalO (1/epsilon2.5)であることを示す。
- 参考スコア(独自算出の注目度): 19.9471360853892
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we show that under over-parametrization several standard
stochastic optimization algorithms escape saddle-points and converge to
local-minimizers much faster. One of the fundamental aspects of
over-parametrized models is that they are capable of interpolating the training
data. We show that, under interpolation-like assumptions satisfied by the
stochastic gradients in an over-parametrization setting, the first-order oracle
complexity of Perturbed Stochastic Gradient Descent (PSGD) algorithm to reach
an $\epsilon$-local-minimizer, matches the corresponding deterministic rate of
$\tilde{\mathcal{O}}(1/\epsilon^{2})$. We next analyze Stochastic
Cubic-Regularized Newton (SCRN) algorithm under interpolation-like conditions,
and show that the oracle complexity to reach an $\epsilon$-local-minimizer
under interpolation-like conditions, is
$\tilde{\mathcal{O}}(1/\epsilon^{2.5})$. While this obtained complexity is
better than the corresponding complexity of either PSGD, or SCRN without
interpolation-like assumptions, it does not match the rate of
$\tilde{\mathcal{O}}(1/\epsilon^{1.5})$ corresponding to deterministic
Cubic-Regularized Newton method. It seems further Hessian-based
interpolation-like assumptions are necessary to bridge this gap. We also
discuss the corresponding improved complexities in the zeroth-order settings.
- Abstract(参考訳): 本稿では,過パラメータ化下では,いくつかの標準確率最適化アルゴリズムが鞍点を回避し,より高速に局所最小化器に収束することを示す。
過パラメータモデルの基本的な側面の1つは、トレーニングデータを補間できることだ。
過パラメトリゼーション設定における確率勾配で満たされる補間的仮定の下では、摂動確率勾配Descent(PSGD)アルゴリズムの1次オラクル複雑性が$\epsilon$-local-minimizerに到達し、対応する決定論的速度が$\tilde{\mathcal{O}}(1/\epsilon^{2})$と一致することを示す。
次に補間的立方体規則化ニュートン(SCRN)アルゴリズムを補間的条件下で解析し,補間的条件下で局所最小化器に到達するオラクルの複雑さが$\tilde{\mathcal{O}}(1/\epsilon^{2.5})$であることを示す。
この複雑性はPSGDやSCRNの補間的仮定のない複雑性よりも優れているが、決定論的立方正則化ニュートン法に対応する$\tilde{\mathcal{O}}(1/\epsilon^{1.5})$と一致しない。
このギャップを埋めるには、さらにヘッセンに基づく補間のような仮定が必要であるようである。
また,ゼロ次設定における複雑度の改善についても考察する。
関連論文リスト
- Stochastic Optimization for Non-convex Problem with Inexact Hessian
Matrix, Gradient, and Function [99.31457740916815]
信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。
TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
論文 参考訳(メタデータ) (2023-10-18T10:29:58Z) - A Newton-CG based barrier-augmented Lagrangian method for general
nonconvex conic optimization [77.8485863487028]
本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。
特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
論文 参考訳(メタデータ) (2023-01-10T20:43:29Z) - Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。
予測と高い確率で、新しい過剰なリスク境界を提供する。
我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
論文 参考訳(メタデータ) (2022-11-03T12:40:24Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳(メタデータ) (2022-08-11T04:12:50Z) - Multi-block-Single-probe Variance Reduced Estimator for Coupled
Compositional Optimization [49.58290066287418]
構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。
本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
論文 参考訳(メタデータ) (2022-07-18T12:03:26Z) - Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。
漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文 参考訳(メタデータ) (2022-06-17T06:10:20Z) - A Stochastic Proximal Method for Nonsmooth Regularized Finite Sum
Optimization [7.014966911550542]
スパースサブ構造を検索するために,非滑らかな正規化を伴うディープニューラルネットワークをトレーニングする問題を考察する。
我々は、収束と最悪のケースの複雑さが勾配のリプシッツ定数の知識や近似なしで確立されるSR2と呼ばれる新しい解法を導出する。
CIFAR-10とCIFAR-100で訓練されたネットワークインスタンスの実験により、SR2はProxGENやProxSGDのような関連する手法よりも常に高い空間性と精度を達成することが示された。
論文 参考訳(メタデータ) (2022-06-14T00:28:44Z) - 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) - The Complexity of Nonconvex-Strongly-Concave Minimax Optimization [43.07732143522183]
本稿では,非強凹型(nc-sc)滑らかなミニマックス問題の近似定常点を求めるための複雑さを確立する。
提案された$Omega-strong$lyconcaveサブ2問題を一般複雑性と平均複雑性の両方で展開する。
提案する有限和設定では,提案するアルゴリズムは条件数にほぼ依存している。
論文 参考訳(メタデータ) (2021-03-29T18:53:57Z) - Stochastic Multi-level Composition Optimization Algorithms with
Level-Independent Convergence Rates [12.783783498844022]
目的関数が$T$関数のネスト合成であるような,スムーズな多層合成最適化問題について検討する。
citeGhaRuswan20を$T$のレベルで一般化した最初のアルゴリズムは、$mathcalO (1/epsilon$6) のサンプル複雑性を実現することができることを示す。
これは、(アン)マルチレベル設定のために設計されたオンラインアルゴリズムが、標準仮定の下で同じサンプル複雑性を得るのはこれが初めてである。
論文 参考訳(メタデータ) (2020-08-24T15:57:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。