論文の概要: Boundary Conditions for Linear Exit Time Gradient Trajectories Around Saddle Points: Analysis and Algorithm

• arxiv url: http://arxiv.org/abs/2101.02625v1
• Date: Thu, 7 Jan 2021 16:59:15 GMT
• ステータス: 処理完了
• システム内更新日: 2021-04-10 13:23:12.118121
• Title: Boundary Conditions for Linear Exit Time Gradient Trajectories Around Saddle Points: Analysis and Algorithm
• Title（参考訳）: サドル点周辺における線形指数時間勾配軌道の境界条件:解析とアルゴリズム
• Authors: Rishabh Dixit and Waheed U. Bajwa
• Abstract要約: 厳密なサドル点の景観における多目的関数の理解について述べる。 厳密なサドル点の最大値を持つ局所的な景観に収束する近傍の解析についても述べる。
• 参考スコア（独自算出の注目度）: 9.69596041242667
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Gradient-related first-order methods have become the workhorse of large-scale numerical optimization problems. Many of these problems involve nonconvex objective functions with multiple saddle points, which necessitates an understanding of the behavior of discrete trajectories of first-order methods within the geometrical landscape of these functions. This paper concerns convergence of first-order discrete methods to a local minimum of nonconvex optimization problems that comprise strict saddle points within the geometrical landscape. To this end, it focuses on analysis of discrete gradient trajectories around saddle neighborhoods, derives sufficient conditions under which these trajectories can escape strict-saddle neighborhoods in linear time, explores the contractive and expansive dynamics of these trajectories in neighborhoods of strict-saddle points that are characterized by gradients of moderate magnitude, characterizes the non-curving nature of these trajectories, and highlights the inability of these trajectories to re-enter the neighborhoods around strict-saddle points after exiting them. Based on these insights and analyses, the paper then proposes a simple variant of the vanilla gradient descent algorithm, termed Curvature Conditioned Regularized Gradient Descent (CCRGD) algorithm, which utilizes a check for an initial boundary condition to ensure its trajectories can escape strict-saddle neighborhoods in linear time. Convergence analysis of the CCRGD algorithm, which includes its rate of convergence to a local minimum within a geometrical landscape that has a maximum number of strict-saddle points, is also presented in the paper. Numerical experiments are then provided on a test function as well as a low-rank matrix factorization problem to evaluate the efficacy of the proposed algorithm.
• Abstract（参考訳）: 勾配関連一階法は大規模数値最適化問題の解法となっている。 これらの問題の多くは、複数のサドル点を持つ非凸目的関数を含み、これらの関数の幾何学的景観における一階法の離散軌跡の挙動を理解する必要がある。 本稿では,幾何学的景観における厳密な鞍点を構成する非凸最適化問題の局所最小値に対する一階離散法の収束について述べる。 To this end, it focuses on analysis of discrete gradient trajectories around saddle neighborhoods, derives sufficient conditions under which these trajectories can escape strict-saddle neighborhoods in linear time, explores the contractive and expansive dynamics of these trajectories in neighborhoods of strict-saddle points that are characterized by gradients of moderate magnitude, characterizes the non-curving nature of these trajectories, and highlights the inability of these trajectories to re-enter the neighborhoods around strict-saddle points after exiting them. これらの知見と分析に基づき,本論文では,曲線条件付き正規化グラディエントDescent (CCRGD) アルゴリズムと呼ばれるバニラ勾配降下アルゴリズムの単純な変種を提案する。 また,CCRGDアルゴリズムの収束解析を行い,厳密なサドル点数の最大値を持つ幾何学的景観内の局所最小値への収束率について述べる。 次に,提案アルゴリズムの有効性を評価するために,テスト関数と低ランク行列因子化問題について数値実験を行った。

関連論文リスト

• 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)
• Accelerated gradient methods for nonconvex optimization: Escape trajectories from strict saddle points and convergence to local minima [9.66353475649122]
  本稿ではその問題を考察する。 加速勾配法の一般一般の凸挙動を理解すること。 非アプティック関数。 これは、運動量可変ネステロフの加速法(NAG)が、厳密なサドル点をほぼ確実に避けていることを示している。
  論文  参考訳（メタデータ） (2023-07-13T19:11:07Z)
• Curvature-Independent Last-Iterate Convergence for Games on Riemannian Manifolds [77.4346324549323]
  本研究では, 多様体の曲率に依存しないステップサイズが, 曲率非依存かつ直線的最終点収束率を達成することを示す。 我々の知る限りでは、曲率非依存率や/または最終点収束の可能性はこれまでに検討されていない。
  論文  参考訳（メタデータ） (2023-06-29T01:20:44Z)
• Convex and Non-convex Optimization Under Generalized Smoothness [69.69521650503431]
  凸法と非最適化法の分析は、しばしばリプシッツ勾配を必要とし、この軌道による解析を制限する。 最近の研究は、非一様滑らか性条件を通した勾配設定を一般化している。
  論文  参考訳（メタデータ） (2023-06-02T04:21:59Z)
• A Stochastic-Gradient-based Interior-Point Algorithm for Solving Smooth Bound-Constrained Optimization Problems [12.29270365918848]
  提案アルゴリズムは、他のインテリアポイント法からの主観的特異な制約に基づいている。 提案アルゴリズムは,プロジェクション,ステップサイズ,シーケンスシーケンスのバランスを慎重に保ち,数値的および決定論的両方の設定において収束を保証する。
  論文  参考訳（メタデータ） (2023-04-28T15:30:43Z)
• Subgradient methods near active manifolds: saddle point avoidance, local convergence, and asymptotic normality [4.709588811674973]
  目的と段階的近似が問題のスムーズな部分構造を完全に表すことを示す。 コーン可逆/分解可能関数や一般半代数問題など、これらの性質が幅広い問題に対して成り立つことを証明している。 正規性の結果は、最も古典的な設定でも新しいように見える。
  論文  参考訳（メタデータ） (2021-08-26T15:02:16Z)
• Stochasticity helps to navigate rough landscapes: comparing gradient-descent-based algorithms in the phase retrieval problem [8.164433158925593]
  本研究では,動的降下,永続勾配,ランジュバン景観降下などの解析ベースアルゴリズムについて検討する。 統計的軌道からの統計場理論をアルゴリズムにフルタイムで適用し、開始時と大規模なシステムサイズで適用します。
  論文  参考訳（メタデータ） (2021-03-08T17:06:18Z)
• 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)
• Second-Order Guarantees in Centralized, Federated and Decentralized Nonconvex Optimization [64.26238893241322]
  単純なアルゴリズムは、多くの文脈において優れた経験的結果をもたらすことが示されている。 いくつかの研究は、非最適化問題を研究するための厳密な分析的正当化を追求している。 これらの分析における重要な洞察は、摂動が局所的な降下アルゴリズムを許容する上で重要な役割を担っていることである。
  論文  参考訳（メタデータ） (2020-03-31T16:54:22Z)

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

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