論文の概要: Distributed Least Squares in Small Space via Sketching and Bias Reduction

• arxiv url: http://arxiv.org/abs/2405.05343v1
• Date: Wed, 8 May 2024 18:16:37 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-10 15:02:12.527781
• Title: Distributed Least Squares in Small Space via Sketching and Bias Reduction
• Title（参考訳）: 小型空間におけるスケッチングとバイアス低減による最小方形分散化
• Authors: Sachin Garg, Kevin Tan, Michał Dereziński,
• Abstract要約: マトリックススケッチは、大きなデータ行列のサイズを減らす強力なツールである。 誤差よりも推定器のバイアスを最小限に抑えるスケッチ手法を設計することで,これらの制限を分散環境で回避できることを示す。 特に、最適空間と現在の行列乗算時間で動作するスパーススケッチ法を提案し、2つのパスデータを用いて、ほぼ偏りのない最小二乗推定器を復元する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Matrix sketching is a powerful tool for reducing the size of large data matrices. Yet there are fundamental limitations to this size reduction when we want to recover an accurate estimator for a task such as least square regression. We show that these limitations can be circumvented in the distributed setting by designing sketching methods that minimize the bias of the estimator, rather than its error. In particular, we give a sparse sketching method running in optimal space and current matrix multiplication time, which recovers a nearly-unbiased least squares estimator using two passes over the data. This leads to new communication-efficient distributed averaging algorithms for least squares and related tasks, which directly improve on several prior approaches. Our key novelty is a new bias analysis for sketched least squares, giving a sharp characterization of its dependence on the sketch sparsity. The techniques include new higher-moment restricted Bai-Silverstein inequalities, which are of independent interest to the non-asymptotic analysis of deterministic equivalents for random matrices that arise from sketching.
• Abstract（参考訳）: マトリックススケッチは、大きなデータ行列のサイズを減らす強力なツールである。 しかし、最小二乗回帰のようなタスクの正確な推定器を復元したい場合、このサイズ削減には根本的な制限がある。 誤差よりも推定器のバイアスを最小限に抑えるスケッチ手法を設計することで,これらの制限を分散環境で回避できることを示す。 特に、最適空間と現在の行列乗算時間で動作するスパーススケッチ法を提案し、2つのパスデータを用いて、ほぼ偏りのない最小二乗推定器を復元する。 これにより、最小二乗および関連するタスクに対する新しい通信効率の高い分散平均化アルゴリズムが実現され、いくつかの先行したアプローチが直接改善される。 我々の重要な新規性は、スケッチされた最小二乗に対する新しいバイアス分析であり、スケッチの間隔への依存を鋭く評価する。 この手法には、スケッチから生じるランダム行列に対する決定論的同値の非漸近解析に独立して興味を持つ、新しい高次の制限されたベイ=シルバーシュタインの不等式が含まれる。

関連論文リスト

• Learning the Positions in CountSketch [49.57951567374372]
  本稿では,まずランダムなスケッチ行列に乗じてデータを圧縮し,最適化問題を高速に解くスケッチアルゴリズムについて検討する。 本研究では,ゼロでないエントリの位置を最適化する学習ベースアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-06-11T07:28:35Z)
• Sharp Analysis of Sketch-and-Project Methods via a Connection to Randomized Singular Value Decomposition [14.453949553412821]
  本研究では,スケッチ・アンド・プロジェクト手法の収束率の急激な保証を得るための理論的枠組みを開発する。 収束速度はスケッチサイズとともに少なくとも直線的に改善され、データ行列が特定のスペクトル崩壊を示すとさらに高速になることを示す。 我々の実験は、この理論を支持し、非常にスパースなスケッチでさえ、我々のフレームワークによって予測される収束特性を示すことを示した。
  論文  参考訳（メタデータ） (2022-08-20T03:11:13Z)
• Distributed Sketching for Randomized Optimization: Exact Characterization, Concentration and Lower Bounds [54.51566432934556]
  我々はヘシアンの形成が困難である問題に対する分散最適化法を検討する。 ランダム化されたスケッチを利用して、問題の次元を減らし、プライバシを保ち、非同期分散システムにおけるストラグラーレジリエンスを改善します。
  論文  参考訳（メタデータ） (2022-03-18T05:49:13Z)
• A Dimensionality Reduction Method for Finding Least Favorable Priors with a Focus on Bregman Divergence [108.28566246421742]
  そこで本研究では,次元に明示的な有界な有限次元設定に最適化を移動させることができる次元削減法を開発した。 この問題を進展させるため、比較的大きな損失関数、すなわちブレグマンの発散によって引き起こされるベイズ的リスクに限定する。
  論文  参考訳（メタデータ） (2022-02-23T16:22:28Z)
• Fast Convex Quadratic Optimization Solvers with Adaptive Sketching-based Preconditioners [37.03247707259297]
  二次正則化を伴う最小二乗問題を検討し,適応的なスケッチサイズを持つ新しいスケッチベース反復手法を提案する。 スケッチのサイズは、線形収束を保証するためにデータ行列の有効次元と同じくらい小さくすることができる。 効果的な寸法の観点からスケッチサイズを選択する際の大きな困難は、後者が実際には通常不明であるという事実にあります。
  論文  参考訳（メタデータ） (2021-04-29T04:36:41Z)
• Learning the Positions in CountSketch [51.15935547615698]
  本稿では,まずランダムなスケッチ行列に乗じてデータを圧縮し,最適化問題を高速に解くスケッチアルゴリズムについて検討する。 本研究では,ゼロでないエントリの位置を最適化する学習アルゴリズムを提案する。 このアルゴリズムは, 従来よりも低階近似の精度を向上し, 初めて$k$-meansクラスタリングのような他の問題に適用できることを示す。
  論文  参考訳（メタデータ） (2020-07-20T05:06:29Z)
• Learning Minimax Estimators via Online Learning [55.92459567732491]
  確率分布のパラメータを推定するミニマックス推定器を設計する際の問題点を考察する。 混合ケースナッシュ平衡を求めるアルゴリズムを構築した。
  論文  参考訳（メタデータ） (2020-06-19T22:49:42Z)
• Lower Bounds and a Near-Optimal Shrinkage Estimator for Least Squares using Random Projections [37.27708297562079]
  ガウススケッチを用いた最小二乗解に対する改良された推定器を導出する。 経験的に、この推定器はシミュレーションと実際のデータセットの誤差を小さくする。
  論文  参考訳（メタデータ） (2020-06-15T06:42:18Z)
• Effective Dimension Adaptive Sketching Methods for Faster Regularized Least-Squares Optimization [56.05635751529922]
  スケッチに基づくL2正規化最小二乗問題の解法を提案する。 我々は、最も人気のあるランダム埋め込みの2つ、すなわちガウス埋め込みとサブサンプリングランダム化アダマール変換(SRHT)を考える。
  論文  参考訳（メタデータ） (2020-06-10T15:00:09Z)

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

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