論文の概要: Fundamental Bias in Inverting Random Sampling Matrices with Application to Sub-sampled Newton

• arxiv url: http://arxiv.org/abs/2502.13583v1
• Date: Wed, 19 Feb 2025 09:49:38 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-20 13:59:20.418676
• Title: Fundamental Bias in Inverting Random Sampling Matrices with Application to Sub-sampled Newton
• Title（参考訳）: 逆ランダムサンプリング行列の基本バイアスとサブサンプリングニュートンへの応用
• Authors: Chengmei Niu, Zhenyu Liao, Zenan Ling, Michael W. Mahoney,
• Abstract要約: 逆バイアス(英: inversion bias)とは、ランダムスケッチ自体の非バイアスにもかかわらず、ランダムスケッチの逆は非バイアスにならない現象である。 このバイアスは、さまざまな機械学習パイプラインでランダムスケッチを使用する際の課題を示す。 本研究では,一様および非一様レバレッジに基づくランダムサンプリング法と,構造化されたランダムプロジェクションに対して,逆バイアスを補正する方法を示す。
• 参考スコア（独自算出の注目度）: 43.55440953429919
• License:
• Abstract: A substantial body of work in machine learning (ML) and randomized numerical linear algebra (RandNLA) has exploited various sorts of random sketching methodologies, including random sampling and random projection, with much of the analysis using Johnson--Lindenstrauss and subspace embedding techniques. Recent studies have identified the issue of inversion bias -- the phenomenon that inverses of random sketches are not unbiased, despite the unbiasedness of the sketches themselves. This bias presents challenges for the use of random sketches in various ML pipelines, such as fast stochastic optimization, scalable statistical estimators, and distributed optimization. In the context of random projection, the inversion bias can be easily corrected for dense Gaussian projections (which are, however, too expensive for many applications). Recent work has shown how the inversion bias can be corrected for sparse sub-gaussian projections. In this paper, we show how the inversion bias can be corrected for random sampling methods, both uniform and non-uniform leverage-based, as well as for structured random projections, including those based on the Hadamard transform. Using these results, we establish problem-independent local convergence rates for sub-sampled Newton methods.
• Abstract（参考訳）: 機械学習(ML)とランダム化された数値線形代数(RandNLA)におけるかなりの研究は、ランダムサンプリングやランダムプロジェクションなどの様々なランダムスケッチ手法を利用して、ジョンソン-リンデンシュトラウス(Johnson-Lindenstrauss)とサブスペース埋め込み技術(subspace Embedding technique)を用いて分析した。最近の研究では、ランダムスケッチの逆は、スケッチ自体の不偏性にもかかわらず、逆バイアス(inversion bias)の問題を特定している。 このバイアスは、高速確率最適化、スケーラブルな統計的推定器、分散最適化など、さまざまなMLパイプラインでランダムスケッチを使用する際の課題を示す。 ランダム射影の文脈では、逆バイアスは密度の強いガウス射影に対して容易に補正できる(ただし、多くの応用には高すぎる)。 近年の研究では、スパース準ガウス射影に対して逆バイアスを補正する方法が示されている。 本稿では,一様かつ一様でないレバレッジベースのランダムサンプリング法や,ハダマール変換に基づくランダムプロジェクションに対して,逆バイアスを補正する方法を示す。 これらの結果を用いて、サブサンプルニュートン法における問題非依存の局所収束率を確立する。

関連論文リスト

• Weak Generative Sampler to Efficiently Sample Invariant Distribution of Stochastic Differential Equation [8.67581853745823]
  現在のディープラーニングに基づく手法は、定常フォッカー-プランク方程式を解き、ディープニューラルネットワークの形で不変確率密度関数を決定する。 本稿では, 弱い生成サンプル(WGS)を用いて, 独立かつ同一に分布したサンプルを直接生成するフレームワークを提案する。 提案した損失関数はFokker-Planck方程式の弱い形式に基づいており、正規化フローを統合して不変分布を特徴づける。
  論文  参考訳（メタデータ） (2024-05-29T16:41:42Z)
• Algorithmic Gaussianization through Sketching: Converting Data into Sub-gaussian Random Designs [22.925108493465363]
  平均化によるデータ分布のガウシアン化のためのアルゴリズムフレームワークを提供する。 我々は、ガウス以下のランダムな設計とほとんど区別できないデータスケッチを効率的に構築できることを示す。
  論文  参考訳（メタデータ） (2022-06-21T12:16:45Z)
• Bias-Free Scalable Gaussian Processes via Randomized Truncations [26.985324213848475]
  本稿では,初期乱れ共役勾配 (CG) とランダムフーリエ特徴 (RFF) の2つの共通手法を解析する。 CGは不適合になり、RFFは不適合になりがちです。 分散の増大と引き換えにバイアスを排除したランダム化トランケーション推定器を用いて,これらの問題に対処する。
  論文  参考訳（メタデータ） (2021-02-12T18:54:10Z)
• Pathwise Conditioning of Gaussian Processes [72.61885354624604]
  ガウス過程後部をシミュレーションするための従来のアプローチでは、有限個の入力位置のプロセス値の限界分布からサンプルを抽出する。 この分布中心の特徴づけは、所望のランダムベクトルのサイズで3次スケールする生成戦略をもたらす。 条件付けのこのパスワイズ解釈が、ガウス過程の後部を効率的にサンプリングするのに役立てる近似の一般族をいかに生み出すかを示す。
  論文  参考訳（メタデータ） (2020-11-08T17:09:37Z)
• Precise expressions for random projections: Low-rank approximation and randomized Newton [63.68433510953756]
  マトリックススケッチは、そのような次元削減を非常に効率的に行うための強力な技術として登場した。 本研究では,スケッチによって得られたランダムな投影行列の予測値に対して,確率的に正確な表現を提供する手法を開発した。 これらの表現は、様々な機械学習タスクにおける次元削減のパフォーマンスを特徴付けるのに使うことができる。
  論文  参考訳（メタデータ） (2020-06-18T16:23:00Z)
• Efficiently Sampling Functions from Gaussian Process Posteriors [76.94808614373609]
  高速後部サンプリングのための簡易かつ汎用的なアプローチを提案する。 分離されたサンプルパスがガウス過程の後部を通常のコストのごく一部で正確に表現する方法を実証する。
  論文  参考訳（メタデータ） (2020-02-21T14:03:16Z)
• Distributed Sketching Methods for Privacy Preserving Regression [54.51566432934556]
  ランダム化されたスケッチを利用して、問題の次元を減らし、プライバシを保ち、非同期分散システムにおけるストラグラーレジリエンスを改善します。 従来のスケッチ手法に対する新しい近似保証を導出し、分散スケッチにおけるパラメータ平均化の精度を解析する。 大規模実験によるサーバレスコンピューティングプラットフォームにおける分散スケッチのパフォーマンスについて説明する。
  論文  参考訳（メタデータ） (2020-02-16T08:35:48Z)
• Optimal Iterative Sketching with the Subsampled Randomized Hadamard Transform [64.90148466525754]
  最小二乗問題に対する反復スケッチの性能について検討する。 本研究では、Haar行列とランダム化されたHadamard行列の収束速度が同一であることを示し、ランダムなプロジェクションを経時的に改善することを示した。 これらの手法は、ランダム化次元還元を用いた他のアルゴリズムにも適用することができる。
  論文  参考訳（メタデータ） (2020-02-03T16:17:50Z)

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

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