論文の概要: Zeroth-Order Negative Curvature Finding: Escaping Saddle Points without
Gradients
- arxiv url: http://arxiv.org/abs/2210.01496v1
- Date: Tue, 4 Oct 2022 10:01:16 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-05 15:35:02.140607
- Title: Zeroth-Order Negative Curvature Finding: Escaping Saddle Points without
Gradients
- Title（参考訳）: ゼロ階負曲率検出:勾配のないサドル点のエスケープ
- Authors: Hualin Zhang and Huan Xiong and Bin Gu
- Abstract要約: 関数評価のみにアクセス可能な非局所問題のサドル点の回避を検討する。
ゼロ階負曲率探索フレームワークを2つ提案する。
- 参考スコア（独自算出の注目度）: 22.153544816232042
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider escaping saddle points of nonconvex problems where only the
function evaluations can be accessed. Although a variety of works have been
proposed, the majority of them require either second or first-order
information, and only a few of them have exploited zeroth-order methods,
particularly the technique of negative curvature finding with zeroth-order
methods which has been proven to be the most efficient method for escaping
saddle points. To fill this gap, in this paper, we propose two zeroth-order
negative curvature finding frameworks that can replace Hessian-vector product
computations without increasing the iteration complexity. We apply the proposed
frameworks to ZO-GD, ZO-SGD, ZO-SCSG, ZO-SPIDER and prove that these ZO
algorithms can converge to $(\epsilon,\delta)$-approximate second-order
stationary points with less query complexity compared with prior zeroth-order
works for finding local minima.
- Abstract（参考訳）: 関数評価のみにアクセス可能な非凸問題の鞍点を脱出することを検討する。
様々な研究が提案されているが、そのほとんどは二階または一階の情報を必要としており、そのほとんどはゼロ階法、特に最も効率的なサドル点の解法であることが証明されたゼロ階法による負曲率探索技術を利用したものである。
このギャップを埋めるため,本論文では,反復複雑性を増大させることなく,ヘッセン・ベクトル積の計算を置き換えることができる2つのゼロ次負曲率探索フレームワークを提案する。
提案手法をZO-GD, ZO-SGD, ZO-SCSG, ZO-SPIDERに適用し, これらのZOアルゴリズムが局所ミニマを見つけるためのゼロ次処理に比べてクエリの複雑さが低い2次定常点に対して$(\epsilon,\delta)$-approximateを収束できることを証明する。
関連論文リスト
- 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) - 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) - Derivative-free Alternating Projection Algorithms for General
Nonconvex-Concave Minimax Problems [9.173866646584031]
本稿では,非滑らかなゼロ次ミニマックス問題に対するアルゴリズムを提案する。
また,非コンケーブミニマックス問題に対処できることを示す。
論文 参考訳（メタデータ） (2021-08-01T15:23:49Z) - Zeroth-Order Algorithms for Smooth Saddle-Point Problems [117.44028458220427]
ゼロオーダーのオラクルを用いてサドルポイント問題を解くアルゴリズムをいくつか提案する。
解析により、この項の収束率は、一階法よりも$log n$因子の方が悪いことが示されている。
また、混合構成を考慮し、その部分に対してゼロ階のオラクルを使用する1/2階法を開発する。
論文 参考訳（メタデータ） (2020-09-21T14:26:48Z) - Second-Order Information in Non-Convex Stochastic Optimization: Power
and Limitations [54.42518331209581]
私たちは発見するアルゴリズムを見つけます。
epsilon$-approximate stationary point ($|nabla F(x)|le epsilon$) using
$(epsilon,gamma)$surimateランダムランダムポイント。
ここでの私たちの下限は、ノイズのないケースでも新規です。
論文 参考訳（メタデータ） (2020-06-24T04:41:43Z) - Exploiting Higher Order Smoothness in Derivative-free Optimization and
Continuous Bandits [99.70167985955352]
強凸関数のゼロ次最適化問題について検討する。
予測勾配降下アルゴリズムのランダム化近似を考察する。
その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
論文 参考訳（メタデータ） (2020-06-14T10:42:23Z) - Nonconvex Zeroth-Order Stochastic ADMM Methods with Lower Function Query
Complexity [109.54166127479093]
ゼロ次法(ゼロ次法、英: Zeroth-order method)は、機械学習問題を解決するための効果的な最適化手法のクラスである。
本稿では,非有限項問題を解くために,より高速なゼロ階交互勾配法乗算器 (MMADMM) を提案する。
我々は、ZOMMAD法が、$epsilon$-stationary pointを見つけるために、より低い関数$O(frac13nfrac1)$を達成することができることを示す。
同時に、より高速なゼロオーダーオンラインADM手法(M)を提案する。
論文 参考訳（メタデータ） (2019-07-30T02:21:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。