論文の概要: On the Second-order Convergence Properties of Random Search Methods
- arxiv url: http://arxiv.org/abs/2110.13265v1
- Date: Mon, 25 Oct 2021 20:59:31 GMT
- ステータス: 処理完了
- システム内更新日: 2021-10-27 16:14:57.479421
- Title: On the Second-order Convergence Properties of Random Search Methods
- Title（参考訳）: ランダム探索法の2次収束特性について
- Authors: Aurelien Lucchi, Antonio Orvieto, Adamos Solomou
- Abstract要約: 本研究では,2次情報に依存しない標準的なランダム検索手法が2次定常点に収束することを証明する。
本稿では,関数評価のみに依存する負曲率の新しい変種を提案する。
- 参考スコア（独自算出の注目度）: 7.788439526606651
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the theoretical convergence properties of random-search methods when
optimizing non-convex objective functions without having access to derivatives.
We prove that standard random-search methods that do not rely on second-order
information converge to a second-order stationary point. However, they suffer
from an exponential complexity in terms of the input dimension of the problem.
In order to address this issue, we propose a novel variant of random search
that exploits negative curvature by only relying on function evaluations. We
prove that this approach converges to a second-order stationary point at a much
faster rate than vanilla methods: namely, the complexity in terms of the number
of function evaluations is only linear in the problem dimension. We test our
algorithm empirically and find good agreements with our theoretical results.
- Abstract（参考訳）: 非凸目的関数を導関数にアクセスできることなく最適化する際、ランダム探索法の理論的収束特性について検討する。
二階情報に依存しない標準ランダム探索手法が二階定常点に収束することを証明する。
しかし、それらは問題の入力次元の点で指数関数的な複雑さに悩まされる。
この問題に対処するために,関数評価にのみ依存して負の曲率を利用する新しいランダム探索法を提案する。
このアプローチがバニラ法よりもずっと速い速度で二階定常点に収束することを証明する:すなわち、関数評価の回数の点での複雑性は問題次元において線型である。
我々は経験的にアルゴリズムをテストし、理論結果と良い一致を見出す。
関連論文リスト
- Stochastic First-Order Methods with Non-smooth and Non-Euclidean Proximal Terms for Nonconvex High-Dimensional Stochastic Optimization [2.0657831823662574]
非問題が非問題である場合、一階法のサンプルは問題次元に線形に依存することがあるが、望ましくない問題に対するものである。
我々のアルゴリズムは距離を使って複雑さを見積もることができる。
MathO (log d) / EuM4。
DISFOM は $mathO (log d) / EuM4 を用いて分散を鋭くすることができることを示す。
論文 参考訳（メタデータ） (2024-06-27T18:38:42Z) - Stochastic Optimization for Non-convex Problem with Inexact Hessian
Matrix, Gradient, and Function [99.31457740916815]
信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。
TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
論文 参考訳（メタデータ） (2023-10-18T10:29:58Z) - 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) - High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。
非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。
そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
論文 参考訳（メタデータ） (2021-06-10T17:54:21Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳（メタデータ） (2020-08-23T20:36:49Z) - Provably Convergent Working Set Algorithm for Non-Convex Regularized
Regression [0.0]
本稿では、収束保証付き非正則正規化器のためのワーキングセットアルゴリズムを提案する。
その結果,ブロックコーディネートや勾配ソルバの完全解法と比較して高い利得を示した。
論文 参考訳（メタデータ） (2020-06-24T07:40:31Z) - Exploiting Higher Order Smoothness in Derivative-free Optimization and
Continuous Bandits [99.70167985955352]
強凸関数のゼロ次最適化問題について検討する。
予測勾配降下アルゴリズムのランダム化近似を考察する。
その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
論文 参考訳（メタデータ） (2020-06-14T10:42:23Z) - A New Randomized Primal-Dual Algorithm for Convex Optimization with
Optimal Last Iterate Rates [16.54912614895861]
我々は,非滑らかな制約付き凸最適化問題のクラスを解くために,新しいランダム化ブロック座標原始双対アルゴリズムを開発した。
我々は,一般凸性と強い凸性という2つのケースにおいて,アルゴリズムが最適収束率を達成することを証明した。
その結果,提案手法は異なる実験における性能向上に寄与していることがわかった。
論文 参考訳（メタデータ） (2020-03-03T03:59:26Z) - Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。
我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。
得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
論文 参考訳（メタデータ） (2020-02-21T17:45:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。