論文の概要: A randomized algorithm for nonconvex minimization with inexact evaluations and complexity guarantees
- arxiv url: http://arxiv.org/abs/2310.18841v2
- Date: Tue, 26 Mar 2024 17:39:30 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-28 00:41:21.563718
- Title: A randomized algorithm for nonconvex minimization with inexact evaluations and complexity guarantees
- Title(参考訳): 不正確な評価と複雑性保証を伴う非凸最小化のためのランダム化アルゴリズム
- Authors: Shuyao Li, Stephen J. Wright,
- Abstract要約: 勾配 Hessian に不連続な滑らかな非オラクル関数の最小化を考える。
提案手法の新たな特徴は, 負曲率の近似方向が選択された場合, 感覚緩和を等勾配で負となるように選択することである。
- 参考スコア(独自算出の注目度): 7.08249229857925
- 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 (without assuming access to the function value) to achieve 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 allow gradients to be inexact in a relative sense and relax the coupling between inexactness thresholds for the first- and second-order optimality conditions. 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 improved gradient sample complexity over existing works.
- Abstract(参考訳): 非凸な滑らかな関数の最小化について検討し、(関数値へのアクセスを前提とせずに)勾配とヘシアンに不正確なオラクルアクセスを施し、近似的な二階最適性を実現する。
提案手法の新たな特徴は, 負曲率の近似方向をステップとして選択した場合, 正あるいは負の感覚を同じ確率で選択することである。
相対的な意味で勾配が不正確なことを許容し、一階と二階の最適条件に対する不正確なしきい値間の結合を緩和する。
我々の収束分析は、マルティンゲール分析に基づく期待値と、濃度不等式に基づく高い確率値の両方を含む。
本稿では,提案アルゴリズムを経験的リスク最小化問題に適用し,既存の作業よりも勾配サンプルの複雑さが向上した。
関連論文リスト
- Optimal Guarantees for Algorithmic Reproducibility and Gradient
Complexity in Convex Optimization [55.115992622028685]
以前の研究は、一階法はより良い収束率(漸進収束率)をトレードオフする必要があることを示唆している。
最適複雑性と準最適収束保証の両方を、滑らかな凸最小化と滑らかな凸最小化問題に対して達成できることを実証する。
論文 参考訳(メタデータ) (2023-10-26T19:56:52Z) - Stochastic Optimization for Non-convex Problem with Inexact Hessian
Matrix, Gradient, and Function [99.31457740916815]
信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。
TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
論文 参考訳(メタデータ) (2023-10-18T10:29:58Z) - 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) - 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) - Exploiting Higher Order Smoothness in Derivative-free Optimization and
Continuous Bandits [99.70167985955352]
強凸関数のゼロ次最適化問題について検討する。
予測勾配降下アルゴリズムのランダム化近似を考察する。
その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
論文 参考訳(メタデータ) (2020-06-14T10:42:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。