論文の概要: Sketch-and-Project Meets Newton Method: Global $\mathcal O(k^{-2})$ Convergence with Low-Rank Updates

• arxiv url: http://arxiv.org/abs/2305.13082v1
• Date: Mon, 22 May 2023 14:51:40 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-23 15:15:11.817148
• Title: Sketch-and-Project Meets Newton Method: Global $\mathcal O(k^{-2})$ Convergence with Low-Rank Updates
• Title（参考訳）: Sketch-and-Project Meets Newton Method: Global $\mathcal O(k^{-2})$ Convergence with Low-Rank Updates
• Authors: Slavom\'ir Hanzely
• Abstract要約: 高速な$mathcal O(k-2)$大域収束率を持つスケッチ・アンド・プロジェクトニュートン法を提案する。 SGNは、スケッチ・アンド・プロジェクト方式の安価なイテレーションコスト、最先端の$mathcal O(k-2)$フルランクニュートン方式のグローバル収束率、減衰ニュートン方式のアルゴリズム単純さの3つを継承している。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we propose the first sketch-and-project Newton method with fast $\mathcal O(k^{-2})$ global convergence rate for self-concordant functions. Our method, SGN, can be viewed in three ways: i) as a sketch-and-project algorithm projecting updates of Newton method, ii) as a cubically regularized Newton ethod in sketched subspaces, and iii) as a damped Newton method in sketched subspaces. SGN inherits best of all three worlds: cheap iteration costs of sketch-and-project methods, state-of-the-art $\mathcal O(k^{-2})$ global convergence rate of full-rank Newton-like methods and the algorithm simplicity of damped Newton methods. Finally, we demonstrate its comparable empirical performance to baseline algorithms.
• Abstract（参考訳）: 本稿では,自己共役関数に対して高速に$\mathcal o(k^{-2})$大域収束率を持つ最初のスケッチ・アンド・プロジェクトニュートン法を提案する。 我々の方法であるSGNは3つの方法で見ることができる。 一 ニュートン法の更新を投影するスケッチ・アンド・プロジェクトアルゴリズムとして 二 スケッチ部分空間における立方体正規化ニュートンエトドとして、及び 三 スケッチ部分空間における減衰ニュートン法として SGNは、スケッチ・アンド・プロジェクト方式の安価なイテレーションコスト、最先端の$\mathcal O(k^{-2})$フルランクニュートン方式のグローバル収束率、減衰ニュートン方式のアルゴリズム単純さの3つを継承している。 最後に、ベースラインアルゴリズムに匹敵する経験的性能を示す。

関連論文リスト

• A simple and improved algorithm for noisy, convex, zeroth-order optimisation [59.51990161522328]
  我々は、$f(hat x)$ ができるだけ小さいような点 $hat xin barmathcal X$ を返すアルゴリズムを構築している。 この方法は、$f(hat x) - min_xin barmathcal X f(x)$ が、多対数項まで$d2/sqrtn$ より小さい順序であることを証明する。
  論文  参考訳（メタデータ） (2024-06-26T18:19:10Z)
• Krylov Cubic Regularized Newton: A Subspace Second-Order Method with Dimension-Free Convergence Rate [83.3933097134767]
  次元に依存しない大域収束率を$Oleft(frac1mk+frac1k2right)$とする,新しい部分空間正規化ニュートン法を導入する。 提案手法は,特に高次元問題に対して,既存のランダム部分空間法よりも高速に収束する。
  論文  参考訳（メタデータ） (2024-01-05T20:24:18Z)
• FedNS: A Fast Sketching Newton-Type Algorithm for Federated Learning [27.957498393822338]
  我々は, 高速収束率を保ちながら, この問題に対処するための新しいアプローチを導入する。 提案手法はFedNS (Federated Newton Sketch Method) と名付けられ, 正確なヘシアンではなく, スケッチした平方根ヘシアンを通信することにより, ニュートンの手法を近似する。 連合ニュートンスケッチ手法の統計的学習に基づく収束解析を行う。
  論文  参考訳（メタデータ） (2024-01-05T10:06:41Z)
• Higher-Order Newton Methods with Polynomial Work per Iteration [0.7568448369029973]
  任意の$d$の微分を包含するオラクル法を一般化するが、その反復次元における盆地への依存は維持する。 数値的な例では、$d$ の局所的なアトラクションは、追加の仮定がなされると局所的に大きくなる。
  論文  参考訳（メタデータ） (2023-11-10T20:02:58Z)
• 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)
• Second-order optimization with lazy Hessians [55.51077907483634]
  一般の非線形最適化問題を解くためにニュートンの遅延ヘッセン更新を解析する。 我々は、メソッドの各ステップで新しい勾配を計算しながら、これまで見られたヘッセン反復を再利用する。
  論文  参考訳（メタデータ） (2022-12-01T18:58:26Z)
• New Q-Newton's method meets Backtracking line search: good convergence guarantee, saddle points avoidance, quadratic rate of convergence, and easy implementation [0.0]
  ニュートン法 (Newton's method) は「ニュー・Q・ニュートン法 (New Q-Newton's method)」と名付けられ、サドル点を回避でき、2次収束率を持つ。 小さなスケールでの実験では、この手法は他のニュートンの方法のよく知られた修正と非常に競争的に機能することを示した。
  論文  参考訳（メタデータ） (2021-08-23T15:39:00Z)
• Newton-LESS: Sparsification without Trade-offs for the Sketched Newton Update [88.73437209862891]
  2階最適化において、潜在的なボトルネックは繰り返しごとに最適化関数のヘシアン行列を計算することである。 本稿では,ガウススケッチ行列を劇的に分散させることにより,スケッチの計算コストを大幅に削減できることを示す。 ニュートン=ルネッサはガウス埋め込みとほぼ同じ問題に依存しない局所収束率を享受していることを証明した。
  論文  参考訳（メタデータ） (2021-07-15T17:33:05Z)
• A fast and simple modification of Newton's method helping to avoid saddle points [0.0]
  この論文は、$f$が$C3$でシーケンス$x_n$であれば、極限点は臨界点であり、サドル点ではなく、収束速度はニュートンの方法と同じである。
  論文  参考訳（メタデータ） (2020-06-02T10:38:00Z)
• A Newton Frank-Wolfe Method for Constrained Self-Concordant Minimization [60.90222082871258]
  本稿では,制約集合上の線形最小化オラクル(LMO)を用いて,制約付き自己調和最小化問題のクラスをカラフルに解く方法を示す。 L-smoothの場合、我々の手法のLMO呼び出し数はFrank-Wolfe法とほぼ同じであることを示す。
  論文  参考訳（メタデータ） (2020-02-17T15:28:31Z)

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

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