論文の概要: Lower Bounds and a Near-Optimal Shrinkage Estimator for Least Squares using Random Projections

• arxiv url: http://arxiv.org/abs/2006.08160v1
• Date: Mon, 15 Jun 2020 06:42:18 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-21 05:01:59.095363
• Title: Lower Bounds and a Near-Optimal Shrinkage Estimator for Least Squares using Random Projections
• Title（参考訳）: ランダム射影を用いた最小方形に対する下界とほぼ最適収縮推定器
• Authors: Srivatsan Sridhar, Mert Pilanci, Ayfer \"Ozg\"ur
• Abstract要約: ガウススケッチを用いた最小二乗解に対する改良された推定器を導出する。 経験的に、この推定器はシミュレーションと実際のデータセットの誤差を小さくする。
• 参考スコア（独自算出の注目度）: 37.27708297562079
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this work, we consider the deterministic optimization using random projections as a statistical estimation problem, where the squared distance between the predictions from the estimator and the true solution is the error metric. In approximately solving a large scale least squares problem using Gaussian sketches, we show that the sketched solution has a conditional Gaussian distribution with the true solution as its mean. Firstly, tight worst case error lower bounds with explicit constants are derived for any estimator using the Gaussian sketch, and the classical sketching is shown to be the optimal unbiased estimator. For biased estimators, the lower bound also incorporates prior knowledge about the true solution. Secondly, we use the James-Stein estimator to derive an improved estimator for the least squares solution using the Gaussian sketch. An upper bound on the expected error of this estimator is derived, which is smaller than the error of the classical Gaussian sketch solution for any given data. The upper and lower bounds match when the SNR of the true solution is known to be small and the data matrix is well conditioned. Empirically, this estimator achieves smaller error on simulated and real datasets, and works for other common sketching methods as well.
• Abstract（参考訳）: 本研究では,確率予測を用いた決定論的最適化を統計的推定問題とみなし,推定器からの予測と真の解との2乗距離を誤差計量とする。 ガウスのスケッチを用いた大規模最小二乗問題の近似解法において,スケッチ解は真の解を平均とする条件付きガウス分布を持つことを示す。 第一に、ガウススケッチを用いて任意の推定器に対して明示定数を持つ厳密な最悪のケースエラー下限を導出し、古典的スケッチは最適な非バイアス推定器であることが示される。 バイアス付き推定器の場合、下限は真の解に関する事前の知識も組み込む。 次に、ジェームズ・スタイン推定器を用いて、ガウススケッチを用いた最小二乗解に対する改良された推定器を導出する。 この推定器の期待誤差の上限は導出され、任意のデータに対する古典ガウスのスケッチ解の誤差よりも小さい。 真解の SNR が小さく、データ行列が十分に条件付けられたときに、上界と下界は一致する。 経験的に、この推定器はシミュレーションと実際のデータセットの誤差を小さくし、他の一般的なスケッチ手法でも機能する。

関連論文リスト

• Distributed Least Squares in Small Space via Sketching and Bias Reduction [0.0]
  マトリックススケッチは、大きなデータ行列のサイズを減らす強力なツールである。 誤差よりも推定器のバイアスを最小限に抑えるスケッチ手法を設計することで,これらの制限を分散環境で回避できることを示す。 特に、最適空間と現在の行列乗算時間で動作するスパーススケッチ法を提案し、2つのパスデータを用いて、ほぼ偏りのない最小二乗推定器を復元する。
  論文  参考訳（メタデータ） (2024-05-08T18:16:37Z)
• Sketching for Convex and Nonconvex Regularized Least Squares with Sharp Guarantees [23.614074988517864]
  本稿では,非正規化関数によって正規化あるいは凸化される最小二乗問題に対する高速近似を提案する。 スケッチされた凸や非近似問題を解くことにより、推定のための最小値率を初めて示す。
  論文  参考訳（メタデータ） (2023-11-03T09:35:01Z)
• Distributed Sketching for Randomized Optimization: Exact Characterization, Concentration and Lower Bounds [54.51566432934556]
  我々はヘシアンの形成が困難である問題に対する分散最適化法を検討する。 ランダム化されたスケッチを利用して、問題の次元を減らし、プライバシを保ち、非同期分散システムにおけるストラグラーレジリエンスを改善します。
  論文  参考訳（メタデータ） (2022-03-18T05:49:13Z)
• Near-optimal estimation of smooth transport maps with kernel sums-of-squares [81.02564078640275]
  滑らかな条件下では、2つの分布の間の正方形ワッサーシュタイン距離は、魅力的な統計的誤差上界で効率的に計算できる。 生成的モデリングのような応用への関心の対象は、基礎となる最適輸送写像である。 そこで本研究では,地図上の統計的誤差であるL2$が,既存のミニマックス下限値とほぼ一致し,スムーズな地図推定が可能となる最初のトラクタブルアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-12-03T13:45:36Z)
• Near-optimal inference in adaptive linear regression [60.08422051718195]
  最小二乗法のような単純な方法でさえ、データが適応的に収集されるときの非正規な振る舞いを示すことができる。 我々は,これらの分布異常を少なくとも2乗推定で補正するオンラインデバイアス推定器のファミリーを提案する。 我々は,マルチアームバンディット,自己回帰時系列推定,探索による能動的学習などの応用を通して,我々の理論の有用性を実証する。
  論文  参考訳（メタデータ） (2021-07-05T21:05:11Z)
• One-Bit Compressed Sensing via One-Shot Hard Thresholding [7.594050968868919]
  1ビット圧縮センシングの問題は、いくつかのバイナリ測定からスパース信号を推定することである。 広範に使われている非制約の幅の概念から遠ざかる、斬新で簡潔な分析法を提案する。
  論文  参考訳（メタデータ） (2020-07-07T17:28:03Z)
• Learning Minimax Estimators via Online Learning [55.92459567732491]
  確率分布のパラメータを推定するミニマックス推定器を設計する際の問題点を考察する。 混合ケースナッシュ平衡を求めるアルゴリズムを構築した。
  論文  参考訳（メタデータ） (2020-06-19T22:49:42Z)
• Effective Dimension Adaptive Sketching Methods for Faster Regularized Least-Squares Optimization [56.05635751529922]
  スケッチに基づくL2正規化最小二乗問題の解法を提案する。 我々は、最も人気のあるランダム埋め込みの2つ、すなわちガウス埋め込みとサブサンプリングランダム化アダマール変換(SRHT)を考える。
  論文  参考訳（メタデータ） (2020-06-10T15:00:09Z)

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

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