論文の概要: Cubic regularized subspace Newton for non-convex optimization

• arxiv url: http://arxiv.org/abs/2406.16666v1
• Date: Mon, 24 Jun 2024 14:20:02 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-25 14:34:57.803312
• Title: Cubic regularized subspace Newton for non-convex optimization
• Title（参考訳）: 非凸最適化のための立方正則部分空間ニュートン
• Authors: Jim Zhao, Aurelien Lucchi, Nikita Doikov,
• Abstract要約: 我々は、ランダムな部分空間に定常正規化を適用すると解釈できる座標二階SSCNを解析する。 従来の一階法と比較して,大幅な高速化を示した。
• 参考スコア（独自算出の注目度）: 3.481985817302898
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper addresses the optimization problem of minimizing non-convex continuous functions, which is relevant in the context of high-dimensional machine learning applications characterized by over-parametrization. We analyze a randomized coordinate second-order method named SSCN which can be interpreted as applying cubic regularization in random subspaces. This approach effectively reduces the computational complexity associated with utilizing second-order information, rendering it applicable in higher-dimensional scenarios. Theoretically, we establish convergence guarantees for non-convex functions, with interpolating rates for arbitrary subspace sizes and allowing inexact curvature estimation. When increasing subspace size, our complexity matches $\mathcal{O}(\epsilon^{-3/2})$ of the cubic regularization (CR) rate. Additionally, we propose an adaptive sampling scheme ensuring exact convergence rate of $\mathcal{O}(\epsilon^{-3/2}, \epsilon^{-3})$ to a second-order stationary point, even without sampling all coordinates. Experimental results demonstrate substantial speed-ups achieved by SSCN compared to conventional first-order methods.
• Abstract（参考訳）: 本稿では,非凸連続関数を最小化する最適化問題に対処する。これは過度なパラメータ化を特徴とする高次元機械学習アプリケーションのコンテキストに関係している。 我々は、ランダムな部分空間に立方正規化を適用すると解釈できる、SSCNと呼ばれるランダム化された座標二階法を解析する。 このアプローチは、2階情報の利用に伴う計算複雑性を効果的に低減し、高次元のシナリオに適用できる。 理論的には、非凸関数に対する収束保証を確立し、任意の部分空間サイズに対する補間率と不正確な曲率推定を可能にする。 部分空間のサイズが大きくなると、我々の複雑性は3次正規化(CR)レートの$\mathcal{O}(\epsilon^{-3/2})$と一致する。 さらに、全ての座標をサンプリングしなくても、$\mathcal{O}(\epsilon^{-3/2}, \epsilon^{-3})$を2次定常点に正確に収束させる適応サンプリング方式を提案する。 実験の結果,従来の一階法に比べ,SSCNの高速化が顕著であった。

関連論文リスト

• Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
  複素勾配問題に対する2つの分散化ZO推定器を提案する。 我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
  論文  参考訳（メタデータ） (2024-10-03T15:04:01Z)
• Stochastic First-Order Methods with Non-smooth and Non-Euclidean Proximal Terms for Nonconvex High-Dimensional Stochastic Optimization [2.0657831823662574]
  非問題が非問題である場合、一階法のサンプルは問題次元に線形に依存することがあるが、望ましくない問題に対するものである。 我々のアルゴリズムは距離を使って複雑さを見積もることができる。 MathO (log d) / EuM4。 DISFOM は $mathO (log d) / EuM4 を用いて分散を鋭くすることができることを示す。
  論文  参考訳（メタデータ） (2024-06-27T18:38:42Z)
• Krylov Cubic Regularized Newton: A Subspace Second-Order Method with Dimension-Free Convergence Rate [83.3933097134767]
  次元に依存しない大域収束率を$Oleft(frac1mk+frac1k2right)$とする,新しい部分空間正規化ニュートン法を導入する。 提案手法は,特に高次元問題に対して,既存のランダム部分空間法よりも高速に収束する。
  論文  参考訳（メタデータ） (2024-01-05T20:24:18Z)
• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。 TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
  論文  参考訳（メタデータ） (2023-10-18T10:29:58Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。 本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
  論文  参考訳（メタデータ） (2023-01-30T15:46:39Z)
• A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
  本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。 特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
  論文  参考訳（メタデータ） (2023-01-10T20:43:29Z)
• Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [86.05440220344755]
  我々は,非制約のmin-max最適化問題のグローバルなサドル点を求めるために,不正確な正規化ニュートン型手法を提案し,解析する。 提案手法は有界集合内に留まるイテレートを生成し、その反復は制限関数の項で$O(epsilon-2/3)$内の$epsilon$-saddle点に収束することを示す。
  論文  参考訳（メタデータ） (2022-10-23T21:24:37Z)
• DRSOM: A Dimension Reduced Second-Order Method [13.778619250890406]
  信頼的な枠組みの下では,2次法の収束を保ちながら,数方向の情報のみを用いる。 理論的には,この手法は局所収束率と大域収束率が$O(epsilon-3/2)$であり,第1次条件と第2次条件を満たすことを示す。
  論文  参考訳（メタデータ） (2022-07-30T13:05:01Z)
• Convergence Analysis of Nonconvex Distributed Stochastic Zeroth-order Coordinate Method [3.860616339202303]
  本稿では,$ZOn$局所コスト関数の合計により形成されるグローバルコスト関数を最小化する分散非最適化問題について検討する。 エージェントは問題を解くためにzo座標法を近似する。
  論文  参考訳（メタデータ） (2021-03-24T03:07:46Z)
• Escaping Saddle-Points Faster under Interpolation-like Conditions [19.9471360853892]
  過度なパラメータ化の下では、いくつかの標準的な最適化アルゴリズムがサドルポイントを回避し、局所最小化器に収束する。 本稿では、PSGDアルゴリズムの1次オラクル複雑性について論じ、$epsilon$ localminimizerに到達した。 次に、Cubic-Regularized Newton (SCRN)アルゴリズムのアンダーライクな条件を分析し、局所最小化剤アンダーライクな条件に到達するためのオラクルの複雑さが$tildemathcalO (1/epsilon2.5)であることを示す。
  論文  参考訳（メタデータ） (2020-09-28T02:15:18Z)
• Stochastic Subspace Cubic Newton Method [14.624340432672172]
  本稿では,高次元凸関数$f$を最小化するランダム化二階最適化アルゴリズムを提案する。 ミニバッチサイズが変化するにつれて、SSCNのグローバル収束速度は座標降下速度(CD)と立方正規化ニュートン速度とを補間することを示した。 注目すべきことに、SSCN の局所収束速度は、次数関数 $frac12 (x-x*)top nabla2f(x*)(x-x*)$ の最小化問題に適用される部分空間降下率と一致する。
  論文  参考訳（メタデータ） (2020-02-21T19:42:18Z)

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

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