論文の概要: Newton-LESS: Sparsification without Trade-offs for the Sketched Newton Update

• arxiv url: http://arxiv.org/abs/2107.07480v1
• Date: Thu, 15 Jul 2021 17:33:05 GMT
• ステータス: 処理完了
• システム内更新日: 2021-07-16 15:55:43.009597
• Title: Newton-LESS: Sparsification without Trade-offs for the Sketched Newton Update
• Title（参考訳）: Newton-LESS:Sketched Newton Updateのトレードオフのないスパリフィケーション
• Authors: Micha{\l} Derezi\'nski, Jonathan Lacotte, Mert Pilanci and Michael W. Mahoney
• Abstract要約: 2階最適化において、潜在的なボトルネックは繰り返しごとに最適化関数のヘシアン行列を計算することである。 本稿では,ガウススケッチ行列を劇的に分散させることにより,スケッチの計算コストを大幅に削減できることを示す。 ニュートン=ルネッサはガウス埋め込みとほぼ同じ問題に依存しない局所収束率を享受していることを証明した。
• 参考スコア（独自算出の注目度）: 88.73437209862891
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In second-order optimization, a potential bottleneck can be computing the Hessian matrix of the optimized function at every iteration. Randomized sketching has emerged as a powerful technique for constructing estimates of the Hessian which can be used to perform approximate Newton steps. This involves multiplication by a random sketching matrix, which introduces a trade-off between the computational cost of sketching and the convergence rate of the optimization algorithm. A theoretically desirable but practically much too expensive choice is to use a dense Gaussian sketching matrix, which produces unbiased estimates of the exact Newton step and which offers strong problem-independent convergence guarantees. We show that the Gaussian sketching matrix can be drastically sparsified, significantly reducing the computational cost of sketching, without substantially affecting its convergence properties. This approach, called Newton-LESS, is based on a recently introduced sketching technique: LEverage Score Sparsified (LESS) embeddings. We prove that Newton-LESS enjoys nearly the same problem-independent local convergence rate as Gaussian embeddings, not just up to constant factors but even down to lower order terms, for a large class of optimization tasks. In particular, this leads to a new state-of-the-art convergence result for an iterative least squares solver. Finally, we extend LESS embeddings to include uniformly sparsified random sign matrices which can be implemented efficiently and which perform well in numerical experiments.
• Abstract（参考訳）: 2階最適化において、潜在的なボトルネックは繰り返しごとに最適化関数のヘシアン行列を計算することである。 ランダム化されたスケッチは、近似ニュートンステップの実行に使用できるヘッセンの見積もりを構築するための強力な技術として出現した。 これはランダムなスケッチ行列による乗算であり、スケッチの計算コストと最適化アルゴリズムの収束率とのトレードオフをもたらす。 理論的に望ましいが、実際には高価すぎる選択は、正確なニュートンステップの偏りのない推定を生成し、強い問題非依存な収束保証を提供する、密集したガウスのスケッチ行列を使用することである。 ガウススケッチ行列は、その収束特性に大きな影響を及ぼすことなく、大幅に分散し、スケッチの計算コストを大幅に削減できることを示す。 このアプローチはNewton-LESSと呼ばれ、最近導入されたスケッチ技術であるLEverage Score Sparsified (LESS)埋め込みに基づいている。 ニュートンレスはガウス埋め込みとほとんど同じ問題非依存な局所収束率を享受できることを証明し, 最適化タスクの大規模クラスに対して, 一定の要因だけでなく, 低次項までも満足できることを証明した。 特に、これは反復最小二乗解法に対する新しい最先端の収束結果をもたらす。 最後に,LESS埋め込みを拡張し,一様にスペーシングされたランダムサイン行列を効率よく実装し,数値実験で良好に動作するようにした。

関連論文リスト

• Online Covariance Matrix Estimation in Sketched Newton Methods [7.441891256588546]
  ランダム化されたスケッチ技術を利用して各イテレーションで近似したニュートンステップを実行するオンラインスケッチNewton法について検討する。 また、制約された問題に対する推定器の拡張についても論じ、回帰問題に対する優れた性能を示す。
  論文  参考訳（メタデータ） (2025-02-10T23:11:02Z)
• Newton Meets Marchenko-Pastur: Massively Parallel Second-Order Optimization with Hessian Sketching and Debiasing [45.475515050909706]
  我々は,作業者間のコミュニケーションが制限されるような,凸関数を極めて並列に最小化する問題を考える。 本稿では、中央ノード(サーバ)がニュートン法を効果的に実行し、その高コストをオフロードする手法を提案する。 提案手法では, 適応的スケッチ手法を用いて, 作業者は独立に粗いが, 低バイアスで逆ヘッセン推定を行う。
  論文  参考訳（メタデータ） (2024-10-02T09:38:04Z)
• Series of Hessian-Vector Products for Tractable Saddle-Free Newton Optimisation of Neural Networks [1.3654846342364308]
  絶対値固有値を持つ正逆 Hessian を,一階乗算可能な最適化アルゴリズムで効率的に利用できることを示す。 この級数のt-runは、他の1階と2階の最適化手法に匹敵する新しい最適化を提供する。
  論文  参考訳（メタデータ） (2023-10-23T13:11:30Z)
• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。 TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
  論文  参考訳（メタデータ） (2023-10-18T10:29:58Z)
• Self-concordant Smoothing for Large-Scale Convex Composite Optimization [0.0]
  2つの凸関数の和を最小化する自己協和スムージングの概念を導入し、そのうちの1つは滑らかであり、もう1つは非滑らかである。 本稿では, 近位ニュートンアルゴリズムであるProx-N-SCOREと近位一般化したガウスニュートンアルゴリズムであるProx-GGN-SCOREの2つのアルゴリズムの収束性を証明する。
  論文  参考訳（メタデータ） (2023-09-04T19:47:04Z)
• Projection-Free Online Convex Optimization via Efficient Newton Iterations [10.492474737007722]
  本稿では、凸領域$mathcalKサブセットmathbbRd$に対するオンライン凸最適化(OCO)のための新しいプロジェクションフリーアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-06-19T18:48:53Z)
• Constrained Optimization via Exact Augmented Lagrangian and Randomized Iterative Sketching [55.28394191394675]
  等式制約付き非線形非IBS最適化問題に対する適応的不正確なニュートン法を開発した。 ベンチマーク非線形問題,LVMのデータによる制約付きロジスティック回帰,PDE制約問題において,本手法の優れた性能を示す。
  論文  参考訳（メタデータ） (2023-05-28T06:33:37Z)
• Second-order optimization with lazy Hessians [55.51077907483634]
  一般の非線形最適化問題を解くためにニュートンの遅延ヘッセン更新を解析する。 我々は、メソッドの各ステップで新しい勾配を計算しながら、これまで見られたヘッセン反復を再利用する。
  論文  参考訳（メタデータ） (2022-12-01T18:58:26Z)
• Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
  制約付き非線形最適化問題のオンライン統計的推測を考察する。 これらの問題を解決するために、逐次二次計画法(StoSQP)を適用する。
  論文  参考訳（メタデータ） (2022-05-27T00:34:03Z)

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

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