論文の概要: On the well-spread property and its relation to linear regression
- arxiv url: http://arxiv.org/abs/2206.08092v1
- Date: Thu, 16 Jun 2022 11:17:44 GMT
- ステータス: 処理完了
- システム内更新日: 2022-06-18 03:31:49.912980
- Title: On the well-spread property and its relation to linear regression
- Title（参考訳）: ウェルスプレッド特性と線形回帰との関係について
- Authors: Hongjie Chen, Tommaso d'Orsi
- Abstract要約: 頑健な線形回帰モデルにおけるパラメータベクトルの一貫した回復は情報理論上不可能であることを示す。
与えられた$n$-by-d$行列が、周囲の次元で観測回数が二次的である場合、適切に証明できることが示される。
- 参考スコア（独自算出の注目度）: 4.619541348328937
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider the robust linear regression model $\boldsymbol{y} = X\beta^* +
\boldsymbol{\eta}$, where an adversary oblivious to the design $X \in
\mathbb{R}^{n \times d}$ may choose $\boldsymbol{\eta}$ to corrupt all but a
(possibly vanishing) fraction of the observations $\boldsymbol{y}$ in an
arbitrary way. Recent work [dLN+21, dNS21] has introduced efficient algorithms
for consistent recovery of the parameter vector. These algorithms crucially
rely on the design matrix being well-spread (a matrix is well-spread if its
column span is far from any sparse vector).
In this paper, we show that there exists a family of design matrices lacking
well-spreadness such that consistent recovery of the parameter vector in the
above robust linear regression model is information-theoretically impossible.
We further investigate the average-case time complexity of certifying
well-spreadness of random matrices. We show that it is possible to efficiently
certify whether a given $n$-by-$d$ Gaussian matrix is well-spread if the number
of observations is quadratic in the ambient dimension. We complement this
result by showing rigorous evidence -- in the form of a lower bound against
low-degree polynomials -- of the computational hardness of this same
certification problem when the number of observations is $o(d^2)$.
- Abstract（参考訳）: 頑健な線形回帰モデル $\boldsymbol{y} = X\beta^* + \boldsymbol{\eta}$ を考えると、設計に不利な逆元 $X \in \mathbb{R}^{n \times d}$ は、観測値 $\boldsymbol{y}$ の(おそらく消滅する)部分を除いて全てを任意の方法で破壊するために $\boldsymbol{\eta}$ を選択することができる。
最近の研究[dLN+21, dNS21]ではパラメータベクトルの一貫した回復のための効率的なアルゴリズムが導入された。
これらのアルゴリズムは設計マトリクスを良くスプレッドする(コラムスパンがスパースベクトルから遠く離れている場合、マトリクスはよくスプレッドされる)。
本稿では, 線形回帰モデルにおけるパラメータベクトルの整合性回復が情報理論的に不可能であるような, 疎結合性に欠ける設計行列群が存在することを示す。
さらに,ランダム行列の拡散性を証明する平均ケース時間複雑性について検討した。
我々は、与えられた$n$-by-d$ Gaussian行列が、周囲の次元において観測回数が二次的である場合、適切に証明可能であることを示す。
この結果は、観測回数が$o(d^2)$である場合に、同じ認証問題の計算硬さの厳密な証拠(低次多項式に対する下限)を示すことによって補完する。
関連論文リスト
- Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - Sparse Linear Regression and Lattice Problems [9.50127504736299]
格子問題の平均ケース硬度を仮定したSLRw.r.t.の全ての効率的なアルゴリズムの平均ケース硬度を示す。
具体的には,SLR に対する格子上の境界距離復号法 (BDD) 問題の変種からインスタンス・バイ・インスタンス・リダクションを与える。
論文 参考訳（メタデータ） (2024-02-22T15:45:27Z) - One-sided Matrix Completion from Two Observations Per Row [95.87811229292056]
行列の欠落値を$XTX$で計算する自然アルゴリズムを提案する。
合成データの一方の回収と低被覆ゲノムシークエンシングについて,本アルゴリズムの評価を行った。
論文 参考訳（メタデータ） (2023-06-06T22:35:16Z) - Perturbation Analysis of Randomized SVD and its Applications to
High-dimensional Statistics [8.90202564665576]
一般の「信号+雑音」の枠組みによるRSVDの統計特性について検討する。
3つの統計的推論問題に適用した場合、RSVDのほぼ最適性能保証を導出する。
論文 参考訳（メタデータ） (2022-03-19T07:26:45Z) - Spectral properties of sample covariance matrices arising from random
matrices with independent non identically distributed columns [50.053491972003656]
関数 $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$.
ここでは、$|mathbb E[R(z)] - tilde R(z)|_F を示す。
論文 参考訳（メタデータ） (2021-09-06T14:21:43Z) - Non-PSD Matrix Sketching with Applications to Regression and
Optimization [56.730993511802865]
非PSDおよび2乗根行列の次元削減法を提案する。
複数のダウンストリームタスクにこれらのテクニックをどのように使用できるかを示す。
論文 参考訳（メタデータ） (2021-06-16T04:07:48Z) - A Precise Performance Analysis of Support Vector Regression [105.94855998235232]
我々は,n$の線形測定に応用したハードおよびソフトサポートベクター回帰法について検討した。
得られた結果は、ハードおよびソフトサポートベクトル回帰アルゴリズムの設計に介入するパラメータを最適に調整するために使用される。
論文 参考訳（メタデータ） (2021-05-21T14:26:28Z) - Compressed sensing of low-rank plus sparse matrices [3.8073142980733]
この写本は、ランクラパース行列と$sスパース行列の和として表現できる$mtimes n$が計算的に抽出可能な方法で復元可能であることを示す同様の保証を開発する。
その結果, 合成問題, 動的地上/静電分離, マルチスペクトルイメージング, ロバストPCAが得られた。
論文 参考訳（メタデータ） (2020-07-18T15:36:11Z) - Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。
i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
論文 参考訳（メタデータ） (2020-07-16T06:44:44Z) - Asymptotic errors for convex penalized linear regression beyond Gaussian
matrices [23.15629681360836]
雑音線形観測から係数ベクトル$x_0$ in$RN$を学習する問題を考察する。
平均二乗誤差に対する明示的な式を厳密に導出する。
我々の予測は、非常に適度なサイズであっても、数値と非常によく一致していることを示す。
論文 参考訳（メタデータ） (2020-02-11T13:43:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。