論文の概要: Newton Meets Marchenko-Pastur: Massively Parallel Second-Order Optimization with Hessian Sketching and Debiasing

• arxiv url: http://arxiv.org/abs/2410.01374v1
• Date: Wed, 2 Oct 2024 09:38:04 GMT
• ステータス: 処理完了
• システム内更新日: 2024-11-04 21:29:22.023554
• Title: Newton Meets Marchenko-Pastur: Massively Parallel Second-Order Optimization with Hessian Sketching and Debiasing
• Title（参考訳）: Newton が Marchenko-Pastur を発表 - Hessian Sketching と Debiasing による超並列2階最適化
• Authors: Elad Romanov, Fangzhao Zhang, Mert Pilanci,
• Abstract要約: 我々は,作業者間のコミュニケーションが制限されるような,凸関数を極めて並列に最小化する問題を考える。 本稿では、中央ノード(サーバ)がニュートン法を効果的に実行し、その高コストをオフロードする手法を提案する。 提案手法では, 適応的スケッチ手法を用いて, 作業者は独立に粗いが, 低バイアスで逆ヘッセン推定を行う。
• 参考スコア（独自算出の注目度）: 45.475515050909706
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Motivated by recent advances in serverless cloud computing, in particular the "function as a service" (FaaS) model, we consider the problem of minimizing a convex function in a massively parallel fashion, where communication between workers is limited. Focusing on the case of a twice-differentiable objective subject to an L2 penalty, we propose a scheme where the central node (server) effectively runs a Newton method, offloading its high per-iteration cost -- stemming from the need to invert the Hessian -- to the workers. In our solution, workers produce independently coarse but low-bias estimates of the inverse Hessian, using an adaptive sketching scheme. The server then averages the descent directions produced by the workers, yielding a good approximation for the exact Newton step. The main component of our adaptive sketching scheme is a low-complexity procedure for selecting the sketching dimension, an issue that was left largely unaddressed in the existing literature on Hessian sketching for distributed optimization. Our solution is based on ideas from asymptotic random matrix theory, specifically the Marchenko-Pastur law. For Gaussian sketching matrices, we derive non asymptotic guarantees for our algorithm which are essentially dimension-free. Lastly, when the objective is self-concordant, we provide convergence guarantees for the approximate Newton's method with noisy Hessians, which may be of independent interest beyond the setting considered in this paper.
• Abstract（参考訳）: サーバーレスクラウドコンピューティングの最近の進歩、特にFaaS(Function as a Service)モデルに触発された私たちは、労働者間の通信が制限された、非常に並列な方法で凸関数を最小化する問題を考える。 L2ペナルティの対象となる2つの微分可能な対象に焦点をあてて、中央ノード(サーバ)がニュートン法を効果的に実行し、その高イテレーションコスト(ヘッセン語を反転させる必要から生じる)を労働者にオフロードするスキームを提案する。 提案手法では, 適応的スケッチ手法を用いて, 作業者は独立に粗いが, 低バイアスで逆ヘッセン推定を行う。 すると、サーバは労働者が生成する降下方向を平均化し、正確なニュートンステップを近似する。 適応スケッチ方式の主な構成要素は,分散最適化のためのヘッセンスケッチに関する既存の文献にほとんど記載されていない,スケッチ次元を選択するための低複雑さ手順である。 我々の解は漸近的ランダム行列論、特にマルテンコ・パストゥル法に基づく。 ガウススケッチ行列に対しては、本質的に無次元であるアルゴリズムの漸近的保証を導出する。 最後に、目的が自己調和である場合、我々は、この論文で考慮された設定を超えて独立した関心を持つうる、うるさいヘッセンを持つニュートン法に対する収束保証を提供する。

関連論文リスト

• Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
  本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。 本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
  論文  参考訳（メタデータ） (2024-06-28T02:56:22Z)
• 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)
• Smooth over-parameterized solvers for non-smooth structured optimization [3.756550107432323]
  非滑らか性 (non-smoothness) は、空間性、群空間性、低ランクエッジ、鋭いエッジなどの解の構造的制約を符号化する。 我々は、基礎となる非滑らかな最適化問題の非重み付きだが滑らかな過度パラメータ化を運用する。 我々の主な貢献は変数の一部を明示的に最小化することで新しい定式化を定義する変数射影(VarPro)を適用することです。
  論文  参考訳（メタデータ） (2022-05-03T09:23:07Z)
• Distributed Sketching for Randomized Optimization: Exact Characterization, Concentration and Lower Bounds [54.51566432934556]
  我々はヘシアンの形成が困難である問題に対する分散最適化法を検討する。 ランダム化されたスケッチを利用して、問題の次元を減らし、プライバシを保ち、非同期分散システムにおけるストラグラーレジリエンスを改善します。
  論文  参考訳（メタデータ） (2022-03-18T05:49:13Z)
• Newton-LESS: Sparsification without Trade-offs for the Sketched Newton Update [88.73437209862891]
  2階最適化において、潜在的なボトルネックは繰り返しごとに最適化関数のヘシアン行列を計算することである。 本稿では,ガウススケッチ行列を劇的に分散させることにより,スケッチの計算コストを大幅に削減できることを示す。 ニュートン=ルネッサはガウス埋め込みとほぼ同じ問題に依存しない局所収束率を享受していることを証明した。
  論文  参考訳（メタデータ） (2021-07-15T17:33:05Z)
• Byzantine-Resilient Non-Convex Stochastic Gradient Descent [61.6382287971982]
  敵対的レジリエントな分散最適化。 機械は独立して勾配を計算し 協力することができます 私達のアルゴリズムは新しい集中の技術およびサンプル複雑性に基づいています。 それは非常に実用的です:それはないときすべての前の方法の性能を改善します。 セッティングマシンがあります。
  論文  参考訳（メタデータ） (2020-12-28T17:19:32Z)
• Distributed Averaging Methods for Randomized Second Order Optimization [54.51566432934556]
  我々はヘッセン語の形成が計算的に困難であり、通信がボトルネックとなる分散最適化問題を考察する。 我々は、ヘッセンのサンプリングとスケッチを用いたランダム化二階最適化のための非バイアスパラメータ平均化手法を開発した。 また、不均一なコンピューティングシステムのための非バイアス分散最適化フレームワークを導入するために、二階平均化手法のフレームワークを拡張した。
  論文  参考訳（メタデータ） (2020-02-16T09:01:18Z)

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

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