論文の概要: Escaping Saddle Points for Nonsmooth Weakly Convex Functions via
Perturbed Proximal Algorithms
- arxiv url: http://arxiv.org/abs/2102.02837v1
- Date: Thu, 4 Feb 2021 19:17:13 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-08 12:55:26.942983
- Title: Escaping Saddle Points for Nonsmooth Weakly Convex Functions via
Perturbed Proximal Algorithms
- Title（参考訳）: 摂動近位アルゴリズムによる非平滑弱凸関数のサドル点エスケープ
- Authors: Minhui Huang
- Abstract要約: 主な結果は、非滑らか関数に対する$epsilon$-approximate Local minimumの新たな特徴に基づいている。
標準的な仮定では、摂動近位点、摂動近位勾配、摂動近位線形アルゴリズムは非滑らかな凸関数に対して$epsilon$-approximate局所最小値を求める。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose perturbed proximal algorithms that can provably escape strict
saddles for nonsmooth weakly convex functions. The main results are based on a
novel characterization of $\epsilon$-approximate local minimum for nonsmooth
functions, and recent developments on perturbed gradient methods for escaping
saddle points for smooth problems. Specifically, we show that under standard
assumptions, the perturbed proximal point, perturbed proximal gradient and
perturbed proximal linear algorithms find $\epsilon$-approximate local minimum
for nonsmooth weakly convex functions in $O(\epsilon^{-2}\log(d)^4)$
iterations, where $d$ is the dimension of the problem.
- Abstract（参考訳）: 非平滑な弱凸関数の厳密なサドルを回避できる周回近位アルゴリズムを提案する。
主な結果は、非スムース関数に対する$\epsilon$-approximate local minimum の新たなキャラクタリゼーションと、滑らかな問題に対する鞍点をエスケープするための摂動勾配法の開発に基づいている。
具体的には、標準的な仮定の下で、摂動近位点、摂動近位勾配、および摂動近位線形アルゴリズムは、$d$が問題の次元である$O(\epsilon^{-2}\log(d)^4)$反復において、非平滑な弱凸関数に対して $\epsilon$-approximate 局所最小値を求める。
関連論文リスト
- Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。
本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
論文 参考訳（メタデータ） (2024-06-28T02:56:22Z) - Single-Loop Stochastic Algorithms for Difference of Max-Structured Weakly Convex Functions [41.43895948769255]
非滑らかな非漸近公正問題のクラスを$min_x[yin Yphi(x, y) - max_zin Zpsix(x, z)]$の形で示す。
本稿では,これらの問題を解く最初の方法であるエンベロープ近似勾配SMAGを提案する。
論文 参考訳（メタデータ） (2024-05-28T20:52:46Z) - Gradient-free optimization of highly smooth functions: improved analysis
and a new algorithm [87.22224691317766]
この研究は、目的関数が極めて滑らかであるという仮定の下で、ゼロ次ノイズオラクル情報による問題を研究する。
ゼロオーダー射影勾配勾配アルゴリズムを2種類検討する。
論文 参考訳（メタデータ） (2023-06-03T17:05:13Z) - On the Complexity of Finding Small Subgradients in Nonsmooth
Optimization [31.714928102950584]
決定論的アルゴリズムにより次元自由度を達成できないことを示す。
関数が凸である場合に、$(delta,epsilon)$-定常点を見つける収束率をどのように改善できるかを示す。
論文 参考訳（メタデータ） (2022-09-21T13:30:00Z) - Efficiently Escaping Saddle Points in Bilevel Optimization [48.925688192913]
バイレベル最適化は、機械学習における問題の1つだ。
双レベル最適化の最近の進歩は、最初の基本的非適応的多段階解析に収束する。
論文 参考訳（メタデータ） (2022-02-08T07:10:06Z) - A first-order primal-dual method with adaptivity to local smoothness [64.62056765216386]
凸凹対象 $min_x max_y f(x) + langle Ax, yrangle - g*(y)$, ここで、$f$ は局所リプシッツ勾配を持つ凸関数であり、$g$ は凸かつ非滑らかである。
主勾配ステップと2段ステップを交互に交互に行うCondat-Vuアルゴリズムの適応バージョンを提案する。
論文 参考訳（メタデータ） (2021-10-28T14:19:30Z) - Saddle Point Optimization with Approximate Minimization Oracle [8.680676599607125]
サドル点最適化に対する主要なアプローチである$min_xmax_y f(x, y)$は、GAN(Generative Adversarial Network)によって一般化される勾配に基づくアプローチである。
対照的に、最小化問題を解くオラクルのみに依存する代替手法を解析する。
我々のアプローチでは、近似解 $x'$ と $y'$ to $min_x'f(x', y)$ を与えられた点 $(x, y)$ に配置し、これらの近似解 $(x', y)$ に更新する。
論文 参考訳（メタデータ） (2021-03-29T23:03:24Z) - Exploiting Higher Order Smoothness in Derivative-free Optimization and
Continuous Bandits [99.70167985955352]
強凸関数のゼロ次最適化問題について検討する。
予測勾配降下アルゴリズムのランダム化近似を考察する。
その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
論文 参考訳（メタデータ） (2020-06-14T10:42:23Z) - Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。
特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
論文 参考訳（メタデータ） (2020-02-10T23:23:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。