Fugu-MT 論文翻訳(概要): HOUDINI: Escaping from Moderately Constrained Saddles

論文の概要: HOUDINI: Escaping from Moderately Constrained Saddles

arxiv url: http://arxiv.org/abs/2205.13753v1
Date: Fri, 27 May 2022 03:36:27 GMT
ステータス: 処理完了
システム内更新日: 2022-05-30 14:05:17.357877
Title: HOUDINI: Escaping from Moderately Constrained Saddles
Title（参考訳）: HoUDINI: 適度に制約されたサドルから逃れる
Authors: Dmitrii Avdiukhin, Grigory Yaroslavtsev
Abstract要約: 本研究では,不等式制約の対数的数の下で,(ノイズの多い)勾配降下法がサドル点から逃れることができることを示す。我々の結果は、正規降下と勾配降下の両方に当てはまる。
参考スコア（独自算出の注目度）: 14.277428617774875
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We give the first polynomial time algorithms for escaping from high-dimensional saddle points under a moderate number of constraints. Given gradient access to a smooth function $f \colon \mathbb R^d \to \mathbb R$ we show that (noisy) gradient descent methods can escape from saddle points under a logarithmic number of inequality constraints. This constitutes the first tangible progress (without reliance on NP-oracles or altering the definitions to only account for certain constraints) on the main open question of the breakthrough work of Ge et al. who showed an analogous result for unconstrained and equality-constrained problems. Our results hold for both regular and stochastic gradient descent.
Abstract（参考訳）: 高次元の鞍点から逃れるための最初の多項式時間アルゴリズムを、適度な制約の下で与える。滑らかな関数 $f \colon \mathbb r^d \to \mathbb r$ への勾配アクセスが与えられると、(ノイズの多い)勾配降下法は、不等式制約の対数数の下で鞍点から逃れることができる。これは、非制約問題と等式制約問題に類似した結果を示した Ge らによるブレークスルーの主開問題において、最初の有形進行(NP-オークルに依存せず、あるいは特定の制約を考慮せずに定義を変更する)を構成する。我々の結果は、正規勾配と確率勾配の両方に当てはまる。

関連論文リスト

Trust-Region Sequential Quadratic Programming for Stochastic Optimization with Random Models [57.52124921268249]
本稿では,1次と2次の両方の定常点を見つけるための信頼逐次準計画法を提案する。本手法は, 1次定常点に収束するため, 対象対象の近似を最小化して定義された各イテレーションの勾配ステップを計算する。 2階定常点に収束するため,本手法は負曲率を減少するヘッセン行列を探索する固有ステップも計算する。
論文参考訳（メタデータ） (2024-09-24T04:39:47Z)
Riemannian stochastic optimization methods avoid strict saddle points [68.80251170757647]
研究中のポリシーは、確率 1 の厳密なサドル点/部分多様体を避けていることを示す。この結果は、アルゴリズムの極限状態が局所最小値にしかならないことを示すため、重要な正当性チェックを提供する。
論文参考訳（メタデータ） (2023-11-04T11:12:24Z)
Bridging Discrete and Backpropagation: Straight-Through and Beyond [62.46558842476455]
本稿では,離散潜在変数の生成に関わるパラメータの勾配を近似する新しい手法を提案する。本稿では,Hunの手法とODEを解くための2次数値法を統合することで,2次精度を実現するReinMaxを提案する。
論文参考訳（メタデータ） (2023-04-17T20:59:49Z)
Adaptive Approximate Implicitization of Planar Parametric Curves via Weak Gradient Constraints [11.559302398966468]
ポリノミカル曲線と非ポリノミカル曲線に新たな正規化制約を導入する。次に、多項式曲線と非多項式曲線の近似的暗黙化の2つの適応アルゴリズムを提案する。より正確には、このアイデアは、出力の弱い勾配損失に明らかな改善がないまで、徐々に暗黙の度合いを増している。
論文参考訳（メタデータ） (2023-02-23T04:08:53Z)
Zeroth-Order Hard-Thresholding: Gradient Error vs. Expansivity [34.84170466506512]
本稿では,新しいランダムサンプリングを用いた一般ZO勾配推定器を用いたゼロ階ハードスレッディング(SZOHT)アルゴリズムを提案する。 SZOHTの問合せ複雑性は, 異なる条件下での次元性に依存しないか, あるいは弱く依存していることが判明した。
論文参考訳（メタデータ） (2022-10-11T09:23:53Z)
High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails [55.561406656549686]
我々は、勾配推定が末尾を持つ可能性のある一階アルゴリズムを用いたヒルベルト非最適化を考える。本研究では, 勾配, 運動量, 正規化勾配勾配の収束を高確率臨界点に収束させることと, 円滑な損失に対する最もよく知られた繰り返しを示す。
論文参考訳（メタデータ） (2021-06-28T00:17:01Z)
Boundary Conditions for Linear Exit Time Gradient Trajectories Around Saddle Points: Analysis and Algorithm [9.69596041242667]
厳密なサドル点の景観における多目的関数の理解について述べる。厳密なサドル点の最大値を持つ局所的な景観に収束する近傍の解析についても述べる。
論文参考訳（メタデータ） (2021-01-07T16:59:15Z)
Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
論文参考訳（メタデータ） (2020-07-07T21:26:35Z)
Exit Time Analysis for Approximations of Gradient Descent Trajectories Around Saddle Points [9.66353475649122]
本稿では, 厳密なサドル地区周辺における勾配日射法について, 厳密な幾何学的解析を行った。これは任意の初期条件に対して近似的な勾配軌道を生成するのに使用できる重要な結果を与える。この解析により, 一定の初期条件下での勾配差分法に対する線形出口時間解が導かれる。
論文参考訳（メタデータ） (2020-06-01T17:47:00Z)
Gradient-Free Methods for Saddle-Point Problem [125.99533416395765]
我々はGasnikov et al., 2017のアプローチを一般化し、不正確な勾配のないオラクルで(確率的な)凸最適化問題を解けるようにした。我々のアプローチは、$fracnlog n$ の要求するオラクル呼び出しの回数を削減します。論文の後半では、そのような仮定ができない場合を分析し、この問題を解決する方法の近代化方法に関する一般的なアプローチを提案する。
論文参考訳（メタデータ） (2020-05-12T16:44:27Z)

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