論文の概要: A randomized algorithm for nonconvex minimization with inexact
evaluations and complexity guarantees
- arxiv url: http://arxiv.org/abs/2310.18841v1
- Date: Sat, 28 Oct 2023 22:57:56 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-31 16:03:29.986050
- Title: A randomized algorithm for nonconvex minimization with inexact
evaluations and complexity guarantees
- Title(参考訳): 不正確な評価と複雑性保証を伴う非凸最小化のためのランダム化アルゴリズム
- Authors: Shuyao Li, Stephen J. Wright
- Abstract要約: 我々は、(関数値ではなく)勾配ヘシアンに不コンパクトな滑らかな非Oracle関数の方向を考え、$epsilon_g, epsilon_()$-approximate 2階最適性を達成する。
- 参考スコア(独自算出の注目度): 8.367026421718228
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: We consider minimization of a smooth nonconvex function with inexact oracle
access to gradient and Hessian (but not the function value) to achieve
$(\epsilon_{g}, \epsilon_{H})$-approximate second-order optimality. A novel
feature of our method is that if an approximate direction of negative curvature
is chosen as the step, we choose its sense to be positive or negative with
equal probability. We also use relative inexactness measures on gradient and
Hessian and relax the coupling between the first- and second-order tolerances
$\epsilon_{g}$ and $\epsilon_{H}$. Our convergence analysis includes both an
expectation bound based on martingale analysis and a high-probability bound
based on concentration inequalities. We apply our algorithm to empirical risk
minimization problems and obtain gradient sample complexity.
- Abstract(参考訳): 我々は、oracleが勾配やヘッシアン(関数値ではない)へのアクセスを不必要にする滑らかな非凸関数の最小化を検討し、$(\epsilon_{g}, \epsilon_{h})$-approximate second-order optimalityを達成する。
提案手法の新たな特徴は, 負曲率の近似方向をステップとして選択した場合, 正あるいは負の感覚を同じ確率で選択することである。
また、勾配とヘッセンの相対的不正確な測度を使い、1階と2階の許容値 $\epsilon_{g}$ と $\epsilon_{H}$ の結合を緩和する。
我々の収束解析は,マルティンゲール解析に基づく期待値と濃度不等式に基づく高い確率値の両方を含む。
本アルゴリズムを経験的リスク最小化問題に適用し,勾配サンプル複雑性を得る。
関連論文リスト
- Strictly Low Rank Constraint Optimization -- An Asymptotically
$\mathcal{O}(\frac{1}{t^2})$ Method [5.770309971945476]
最適解における空間性を促進するために,テキスト規則化を用いた非テキスト・非滑らかな問題のクラスを提案する。
我々のアルゴリズムは、滑らかな凸問題に対する一階法に対するネステロフの最適収束と全く同じ$Ofrac(t2)$の特異収束を達成することができることを示す。
論文 参考訳(メタデータ) (2023-07-04T16:55:41Z) - High-Probability Bounds for Stochastic Optimization and Variational
Inequalities: the Case of Unbounded Variance [59.211456992422136]
制約の少ない仮定の下で高確率収束結果のアルゴリズムを提案する。
これらの結果は、標準機能クラスに適合しない問題を最適化するために検討された手法の使用を正当化する。
論文 参考訳(メタデータ) (2023-02-02T10:37:23Z) - A Gradient Smoothed Functional Algorithm with Truncated Cauchy Random
Perturbations for Stochastic Optimization [10.820943271350442]
本稿では,雑音の多いコストサンプルに対する期待値であるスムーズな目的関数を最小化するための凸勾配アルゴリズムを提案する。
また,本アルゴリズムは局所最小値への収束を示唆し,レートリリアを回避できることも示している。
論文 参考訳(メタデータ) (2022-07-30T18:50:36Z) - 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) - Stochastic regularized majorization-minimization with weakly convex and
multi-convex surrogates [0.0]
提案アルゴリズムの最初の最適性ギャップは,非テンソル依存データ設定下での様々な手法の期待損失率で減衰することを示す。
非テンション依存データ設定の下で, 各種手法の収束点を求める。
論文 参考訳(メタデータ) (2022-01-05T15:17:35Z) - Differentiable Annealed Importance Sampling and the Perils of Gradient
Noise [68.44523807580438]
Annealed importance sample (AIS) と関連するアルゴリズムは、限界推定のための非常に効果的なツールである。
差別性は、目的として限界確率を最適化する可能性を認めるため、望ましい性質である。
我々はメトロポリス・ハスティングスのステップを放棄して微分可能アルゴリズムを提案し、ミニバッチ計算をさらに解き放つ。
論文 参考訳(メタデータ) (2021-07-21T17:10:14Z) - Near-Optimal High Probability Complexity Bounds for Non-Smooth
Stochastic Optimization with Heavy-Tailed Noise [63.304196997102494]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。
既存の非滑らか凸最適化法は、負のパワーまたは対数的な信頼度に依存する境界の複雑さを持つ。
クリッピングを用いた2つの勾配法に対して, 新たなステップサイズルールを提案する。
論文 参考訳(メタデータ) (2021-06-10T17:54:21Z) - Gradient Free Minimax Optimization: Variance Reduction and Faster
Convergence [120.9336529957224]
本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。
本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
論文 参考訳(メタデータ) (2020-06-16T17:55:46Z) - Exploiting Higher Order Smoothness in Derivative-free Optimization and
Continuous Bandits [99.70167985955352]
強凸関数のゼロ次最適化問題について検討する。
予測勾配降下アルゴリズムのランダム化近似を考察する。
その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
論文 参考訳(メタデータ) (2020-06-14T10:42:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。