論文の概要: 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})$と一致しない。
このギャップを埋めるには、さらにヘッセンに基づく補間のような仮定が必要であるようである。
また,ゼロ次設定における複雑度の改善についても考察する。
関連論文リスト
- Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
複素勾配問題に対する2つの分散化ZO推定器を提案する。
我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
論文 参考訳（メタデータ） (2024-10-03T15:04:01Z) - Accelerated Stochastic Min-Max Optimization Based on Bias-corrected Momentum [30.01198677588252]
1次アルゴリズムは、$varepsilon-stationary pointを見つけるのに少なくとも$mathcalO(varepsilonepsilon-4)$ complexityを必要とする。
本稿では,高効率な変動複雑性を生かした新しい運動量アルゴリズムを提案する。
本手法の有効性は実世界のデータセットを用いてロジスティック回帰を用いて検証する。
論文 参考訳（メタデータ） (2024-06-18T20:14:52Z) - 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 [53.044526424637866]
本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。
特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
論文 参考訳（メタデータ） (2023-01-10T20:43:29Z) - Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。
予測と高い確率で、新しい過剰なリスク境界を提供する。
我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
論文 参考訳（メタデータ） (2022-11-03T12:40:24Z) - Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [86.05440220344755]
我々は,非制約のmin-max最適化問題のグローバルなサドル点を求めるために,不正確な正規化ニュートン型手法を提案し,解析する。
提案手法は有界集合内に留まるイテレートを生成し、その反復は制限関数の項で$O(epsilon-2/3)$内の$epsilon$-saddle点に収束することを示す。
論文 参考訳（メタデータ） (2022-10-23T21:24:37Z) - 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 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。