論文の概要: Distributed Sketching for Randomized Optimization: Exact Characterization, Concentration and Lower Bounds

• arxiv url: http://arxiv.org/abs/2203.09755v1
• Date: Fri, 18 Mar 2022 05:49:13 GMT
• ステータス: 処理完了
• システム内更新日: 2022-03-21 16:08:35.781287
• Title: Distributed Sketching for Randomized Optimization: Exact Characterization, Concentration and Lower Bounds
• Title（参考訳）: ランダム化最適化のための分散スケッチ:厳密な特性, 濃度, および下界
• Authors: Burak Bartan, Mert Pilanci
• Abstract要約: 我々はヘシアンの形成が困難である問題に対する分散最適化法を検討する。 ランダム化されたスケッチを利用して、問題の次元を減らし、プライバシを保ち、非同期分散システムにおけるストラグラーレジリエンスを改善します。
• 参考スコア（独自算出の注目度）: 54.51566432934556
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider distributed optimization methods for problems where forming the Hessian is computationally challenging and communication is a significant bottleneck. We leverage randomized sketches for reducing the problem dimensions as well as preserving privacy and improving straggler resilience in asynchronous distributed systems. We derive novel approximation guarantees for classical sketching methods and establish tight concentration results that serve as both upper and lower bounds on the error. We then extend our analysis to the accuracy of parameter averaging for distributed sketches. Furthermore, we develop unbiased parameter averaging methods for randomized second order optimization for regularized problems that employ sketching of the Hessian. Existing works do not take the bias of the estimators into consideration, which limits their application to massively parallel computation. We provide closed-form formulas for regularization parameters and step sizes that provably minimize the bias for sketched Newton directions. Additionally, we demonstrate the implications of our theoretical findings via large scale experiments on a serverless cloud computing platform.
• Abstract（参考訳）: ヘシアンの形成が計算的に困難であり,通信が重要なボトルネックとなる問題に対する分散最適化手法を検討する。 ランダム化されたスケッチを利用して、問題の次元を減らし、プライバシを保ち、非同期分散システムにおけるストラグラーレジリエンスを改善します。 我々は,古典的スケッチ法に対する新しい近似保証を導き,誤差の上下境界となる厳密な集中結果を確立する。 次に,分散スケッチのパラメータ平均化の精度に解析を拡張した。 さらに,ヘシアンのスケッチを用いた正規化問題に対して,ランダム化二階最適化のための偏りのないパラメータ平均化手法を開発した。 既存の研究は推定器のバイアスを考慮に入れておらず、非常に並列な計算に限定している。 スケッチされたニュートン方向のバイアスを最小化する正規化パラメータとステップサイズに対する閉形式式を提供する。 さらに,サーバレスクラウドコンピューティングプラットフォームにおける大規模実験を通じて,理論的な知見の意義を実証する。

関連論文リスト

• Newton Meets Marchenko-Pastur: Massively Parallel Second-Order Optimization with Hessian Sketching and Debiasing [45.475515050909706]
  我々は,作業者間のコミュニケーションが制限されるような,凸関数を極めて並列に最小化する問題を考える。 本稿では、中央ノード(サーバ)がニュートン法を効果的に実行し、その高コストをオフロードする手法を提案する。 提案手法では, 適応的スケッチ手法を用いて, 作業者は独立に粗いが, 低バイアスで逆ヘッセン推定を行う。
  論文  参考訳（メタデータ） (2024-10-02T09:38:04Z)
• Wasserstein Distributionally Robust Estimation in High Dimensions: Performance Analysis and Optimal Hyperparameter Tuning [0.0]
  雑音線形測定から未知パラメータを推定するための分布的ロバストな推定フレームワークを提案する。 このような推定器の2乗誤差性能を解析する作業に着目する。 凸凹最適化問題の解法として2乗誤差を復元できることを示す。
  論文  参考訳（メタデータ） (2022-06-27T13:02:59Z)
• Continuous Wasserstein-2 Barycenter Estimation without Minimax Optimization [94.18714844247766]
  ワッサーシュタイン・バリセンターは、最適輸送に基づく確率測度の重み付き平均の幾何学的概念を提供する。 本稿では,Wasserstein-2 バリセンタのサンプルアクセスを演算するスケーラブルなアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-02-02T21:01:13Z)
• Accelerated, Optimal, and Parallel: Some Results on Model-Based Stochastic Optimization [33.71051480619541]
  凸最適化問題を解決するためのモデルベース手法の近似近位点(aProx)ファミリを拡張します。 我々は、非漸近収束保証と、ミニバッチサイズの線形スピードアップを提供する加速スキームを提供する。 我々は,「補間」問題に対する新しい基本定数を同定し,収束率の改善と下界の整合性を示す。
  論文  参考訳（メタデータ） (2021-01-07T18:58:39Z)
• Effective Dimension Adaptive Sketching Methods for Faster Regularized Least-Squares Optimization [56.05635751529922]
  スケッチに基づくL2正規化最小二乗問題の解法を提案する。 我々は、最も人気のあるランダム埋め込みの2つ、すなわちガウス埋め込みとサブサンプリングランダム化アダマール変換(SRHT)を考える。
  論文  参考訳（メタデータ） (2020-06-10T15:00:09Z)
• Distributed Averaging Methods for Randomized Second Order Optimization [54.51566432934556]
  我々はヘッセン語の形成が計算的に困難であり、通信がボトルネックとなる分散最適化問題を考察する。 我々は、ヘッセンのサンプリングとスケッチを用いたランダム化二階最適化のための非バイアスパラメータ平均化手法を開発した。 また、不均一なコンピューティングシステムのための非バイアス分散最適化フレームワークを導入するために、二階平均化手法のフレームワークを拡張した。
  論文  参考訳（メタデータ） (2020-02-16T09:01:18Z)
• Distributed Sketching Methods for Privacy Preserving Regression [54.51566432934556]
  ランダム化されたスケッチを利用して、問題の次元を減らし、プライバシを保ち、非同期分散システムにおけるストラグラーレジリエンスを改善します。 従来のスケッチ手法に対する新しい近似保証を導出し、分散スケッチにおけるパラメータ平均化の精度を解析する。 大規模実験によるサーバレスコンピューティングプラットフォームにおける分散スケッチのパフォーマンスについて説明する。
  論文  参考訳（メタデータ） (2020-02-16T08:35:48Z)
• Support recovery and sup-norm convergence rates for sparse pivotal estimation [79.13844065776928]
  高次元スパース回帰では、ピボット推定器は最適な正規化パラメータがノイズレベルに依存しない推定器である。 非滑らかで滑らかな単一タスクとマルチタスク正方形ラッソ型推定器に対するミニマックス超ノルム収束率を示す。
  論文  参考訳（メタデータ） (2020-01-15T16:11:04Z)

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

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