論文の概要: 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（参考訳）: 非凸な滑らかな関数の最小化について検討し、(関数値へのアクセスを前提とせずに)勾配とヘシアンに不正確なオラクルアクセスを施し、近似的な二階最適性を実現する。 提案手法の新たな特徴は, 負曲率の近似方向をステップとして選択した場合, 正あるいは負の感覚を同じ確率で選択することである。 相対的な意味で勾配が不正確なことを許容し、一階と二階の最適条件に対する不正確なしきい値間の結合を緩和する。 我々の収束分析は、マルティンゲール分析に基づく期待値と、濃度不等式に基づく高い確率値の両方を含む。 本稿では,提案アルゴリズムを経験的リスク最小化問題に適用し,既存の作業よりも勾配サンプルの複雑さが向上した。

関連論文リスト

• Trust-Region Sequential Quadratic Programming for Stochastic Optimization with Random Models [57.52124921268249]
  本稿では,1次と2次の両方の定常点を見つけるための信頼逐次準計画法を提案する。 本手法は, 1次定常点に収束するため, 対象対象の近似を最小化して定義された各イテレーションの勾配ステップを計算する。 2階定常点に収束するため,本手法は負曲率を減少するヘッセン行列を探索する固有ステップも計算する。
  論文  参考訳（メタデータ） (2024-09-24T04:39:47Z)
• An Adaptive Stochastic Gradient Method with Non-negative Gauss-Newton Stepsizes [17.804065824245402]
  機械学習の応用では、各損失関数は非負であり、平方根とその実数値平方根の構成として表すことができる。 本稿では, ガウス・ニュートン法やレフスカルト法を適用して, 滑らかだが非負な関数の平均を最小化する方法を示す。
  論文  参考訳（メタデータ） (2024-07-05T08:53:06Z)
• Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
  本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。 本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
  論文  参考訳（メタデータ） (2024-06-28T02:56:22Z)
• High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance [59.211456992422136]
  制約の少ない仮定の下で高確率収束結果のアルゴリズムを提案する。 これらの結果は、標準機能クラスに適合しない問題を最適化するために検討された手法の使用を正当化する。
  論文  参考訳（メタデータ） (2023-02-02T10:37:23Z)
• Differentiable Annealed Importance Sampling and the Perils of Gradient Noise [68.44523807580438]
  Annealed importance sample (AIS) と関連するアルゴリズムは、限界推定のための非常に効果的なツールである。 差別性は、目的として限界確率を最適化する可能性を認めるため、望ましい性質である。 我々はメトロポリス・ハスティングスのステップを放棄して微分可能アルゴリズムを提案し、ミニバッチ計算をさらに解き放つ。
  論文  参考訳（メタデータ） (2021-07-21T17:10:14Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。 非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。 そこで我々は,勾配クリッピングを伴う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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。