論文の概要: Escaping Saddle Points via Curvature-Calibrated Perturbations: A Complete Analysis with Explicit Constants and Empirical Validation

• arxiv url: http://arxiv.org/abs/2508.16540v1
• Date: Fri, 22 Aug 2025 17:06:28 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-25 16:42:36.465368
• Title: Escaping Saddle Points via Curvature-Calibrated Perturbations: A Complete Analysis with Explicit Constants and Empirical Validation
• Title（参考訳）: 曲率キャリブレーションによるサドル点のエスケープ:明示定数と経験的検証による完全解析
• Authors: Faruk Alpay, Hamdi Alakkad,
• Abstract要約: 本研究では,スムーズな非デルタ最適化において,厳密なサドル点を回避するための一階法を包括的に理論的に解析する。 我々の主な貢献は、完全に明示的な定数を持ち、勾配とサドル・エスケープ相を厳密に分離したパーチャベッド・エスケープ・ダイアンス (PSD) アルゴリズムである。 我々は、合成機能と実用的な機械学習タスクの両方の実験を通して、理論的予測を検証する。
• 参考スコア（独自算出の注目度）: 0.2864713389096699
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present a comprehensive theoretical analysis of first-order methods for escaping strict saddle points in smooth non-convex optimization. Our main contribution is a Perturbed Saddle-escape Descent (PSD) algorithm with fully explicit constants and a rigorous separation between gradient-descent and saddle-escape phases. For a function $f:\mathbb{R}^d\to\mathbb{R}$ with $\ell$-Lipschitz gradient and $\rho$-Lipschitz Hessian, we prove that PSD finds an $(\epsilon,\sqrt{\rho\epsilon})$-approximate second-order stationary point with high probability using at most $O(\ell\Delta_f/\epsilon^2)$ gradient evaluations for the descent phase plus $O((\ell/\sqrt{\rho\epsilon})\log(d/\delta))$ evaluations per escape episode, with at most $O(\ell\Delta_f/\epsilon^2)$ episodes needed. We validate our theoretical predictions through extensive experiments across both synthetic functions and practical machine learning tasks, confirming the logarithmic dimension dependence and the predicted per-episode function decrease. We also provide complete algorithmic specifications including a finite-difference variant (PSD-Probe) and a stochastic extension (PSGD) with robust mini-batch sizing.
• Abstract（参考訳）: 本研究では,スムーズな非凸最適化において,厳密なサドル点をエスケープするための一階法に関する包括的な理論的解析を行う。 我々の主な貢献は、完全に明示的な定数を持つ摂動型サドル・エスケープ・Descent (PSD) アルゴリズムであり、勾配型とサドル・エスケープ相の厳密な分離である。 for a function $f:\mathbb{R}^d\to\mathbb{R}$ with $\ell$-Lipschitz gradient and $\rho$-Lipschitz Hessian, we prove that PSD finds a $(\epsilon,\sqrt{\rho\epsilon})$-approximate second-order stationary point with high probability with at most $O(\ell\Delta_f/\epsilon^2)$ gradient evaluations for the descent phase plus $O(\ell/\sqrt{\rho\epsilon})\log(d/\delta)$ escape episode, with at most $O(\ell\Delta_f/\epsilon^2) $-approximate second-order stationary point with at high probability with the highest $O(\ell\Delta_f/\epsilon^2) $ O(\ell/\sqrt{\rho\epsilon}). 我々は,合成関数と実用的な機械学習タスクの双方にわたる広範な実験を通じて理論的予測を検証し,対数次元依存性と表層関数の予測値の減少を確認した。 また、有限差分変種(PSD-Probe)と、ロバストなミニバッチサイズを持つ確率拡張(PSGD)を含む完全なアルゴリズム仕様も提供する。

関連論文リスト

• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。 我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。 我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
  論文  参考訳（メタデータ） (2024-05-10T09:58:47Z)
• ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
  本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。 我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2023-01-01T18:51:29Z)
• Penalized Overdamped and Underdamped Langevin Monte Carlo Algorithms for Constrained Sampling [17.832449046193933]
  目的が目標分布である$pi(x)prop ef(x)$から$x$が制約されたときにサンプリングする制約付きサンプリング問題を考える。 ペナルティ法によって動機付けられた制約付き問題を,制約違反に対するペナルティ関数を導入することにより,非制約サンプリング問題に変換する。 PSGLD と PSGULMC の場合、$tildemathcalO(d/varepsilon18)$ が強凸で滑らかであるとき、$tildemathcalO(d/varepsilon) を得る。
  論文  参考訳（メタデータ） (2022-11-29T18:43:22Z)
• Stochastic Zeroth order Descent with Structured Directions [10.604744518360464]
  我々は, 有限差分法であるStructured Zeroth Order Descent (SSZD)を導入・解析し, 集合 $lleq d 方向の勾配を近似し, $d は周囲空間の次元である。 凸凸に対して、すべての$c1/2$に対して$O( (d/l) k-c1/2$)$ 上の関数の収束はほぼ確実に証明する。
  論文  参考訳（メタデータ） (2022-06-10T14:00:06Z)
• Sharper Rates and Flexible Framework for Nonconvex SGD with Client and Data Sampling [64.31011847952006]
  我々は、平均$n$スムーズでおそらくは非カラー関数のほぼ定常点を求める問題を再考する。 我々は$smallsfcolorgreen$を一般化し、事実上あらゆるサンプリングメカニズムで確実に動作するようにします。 我々は、スムーズな非カラー状態における最適境界の最も一般的な、最も正確な解析を提供する。
  論文  参考訳（メタデータ） (2022-06-05T21:32:33Z)
• Faster Convergence of Stochastic Gradient Langevin Dynamics for Non-Log-Concave Sampling [110.88857917726276]
  我々は,非log-concaveとなる分布のクラスからサンプリングするために,勾配ランゲヴィンダイナミクス(SGLD)の新たな収束解析を行う。 我々のアプローチの核心は、補助的時間反転型マルコフ連鎖を用いたSGLDのコンダクタンス解析である。
  論文  参考訳（メタデータ） (2020-10-19T15:23:18Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。 i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  論文  参考訳（メタデータ） (2020-07-16T06:44:44Z)
• Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
  非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。 特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
  論文  参考訳（メタデータ） (2020-02-10T23:23:04Z)

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

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