論文の概要: Truncated Linear Regression in High Dimensions
- arxiv url: http://arxiv.org/abs/2007.14539v1
- Date: Wed, 29 Jul 2020 00:31:34 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-05 20:21:06.318544
- Title: Truncated Linear Regression in High Dimensions
- Title（参考訳）: 高次元におけるひずみ線形回帰
- Authors: Constantinos Daskalakis, Dhruv Rohatgi, Manolis Zampetakis
- Abstract要約: truncated linear regression において、従属変数 $(A_i, y_i)_i$ は $y_i= A_irm T cdot x* + eta_i$ は固定された未知の興味ベクトルである。
目標は、$A_i$とノイズ分布に関するいくつかの好ましい条件の下で$x*$を回復することである。
我々は、$k$-sparse $n$-dimensional vectors $x*$ from $m$ truncated sample。
- 参考スコア（独自算出の注目度）: 26.41623833920794
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: As in standard linear regression, in truncated linear regression, we are
given access to observations $(A_i, y_i)_i$ whose dependent variable equals
$y_i= A_i^{\rm T} \cdot x^* + \eta_i$, where $x^*$ is some fixed unknown vector
of interest and $\eta_i$ is independent noise; except we are only given an
observation if its dependent variable $y_i$ lies in some "truncation set" $S
\subset \mathbb{R}$. The goal is to recover $x^*$ under some favorable
conditions on the $A_i$'s and the noise distribution. We prove that there
exists a computationally and statistically efficient method for recovering
$k$-sparse $n$-dimensional vectors $x^*$ from $m$ truncated samples, which
attains an optimal $\ell_2$ reconstruction error of $O(\sqrt{(k \log n)/m})$.
As a corollary, our guarantees imply a computationally efficient and
information-theoretically optimal algorithm for compressed sensing with
truncation, which may arise from measurement saturation effects. Our result
follows from a statistical and computational analysis of the Stochastic
Gradient Descent (SGD) algorithm for solving a natural adaptation of the LASSO
optimization problem that accommodates truncation. This generalizes the works
of both: (1) [Daskalakis et al. 2018], where no regularization is needed due to
the low-dimensionality of the data, and (2) [Wainright 2009], where the
objective function is simple due to the absence of truncation. In order to deal
with both truncation and high-dimensionality at the same time, we develop new
techniques that not only generalize the existing ones but we believe are of
independent interest.
- Abstract（参考訳）: 標準線形回帰と同様に、truncated linear regression において、従属変数が $y_i= A_i^{\rm T} \cdot x^* + \eta_i$, where $x^*$ is some fixed unknown vector of interest and $\eta_i$ is independent noise となるような観測へのアクセスが与えられるが、従属変数 $y_i$ が従属変数 $S \subset \mathbb{R}$ にある場合のみ観察される。
目標は、$A_i$とノイズ分布に関するいくつかの好ましい条件の下で$x^*$を回復することである。
我々は,$k$-sparse $n$-dimensional vectors $x^*$ from $m$ truncated sample という計算量的かつ統計的に効率的な方法が存在することを証明し,$o(\sqrt{(k \log n)/m})$ の最適な$\ell_2$ 再構成誤差を得る。
提案手法は, 計算効率と情報理論上, 圧縮センシングの最適アルゴリズムであり, 測定飽和効果から生じる可能性がある。
我々の結果は、トラルニケーションに対応するLASSO最適化問題の自然な適応を解くための確率勾配 Descent (SGD) アルゴリズムの統計的および計算学的解析から導かれる。
これにより、(1)データの低次元性のために正規化が不要な[daskalakis et al. 2018]と(2)停止の欠如により目的関数が単純である(2)[wainright 2009]という2つの作業が一般化される。
止血と高次元の両方を同時に扱うため、既存のものを一般化するだけでなく、独立した関心事であると信じている新しい技術を開発する。
関連論文リスト
- Inverting the Leverage Score Gradient: An Efficient Approximate Newton Method [10.742859956268655]
本稿では,レバレッジスコア勾配から固有モデルパラメータを復元することを目的とする。
具体的には、レバレッジスコア勾配の逆転を$g(x)$として精査する。
論文 参考訳（メタデータ） (2024-08-21T01:39:42Z) - 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) - Hardness and Algorithms for Robust and Sparse Optimization [17.842787715567436]
スパース線形回帰やロバスト線形回帰といったスパース最適化問題に対するアルゴリズムと制限について検討する。
具体的には、スパース線型回帰問題は$k$-スパースベクトル$xinmathbbRd$を求め、$|Ax-b|$を最小化する。
頑健な線形回帰問題は、少なくとも$k$行を無視する集合$S$と、$|(Ax-b)_S|$を最小化するベクトル$x$を求める。
論文 参考訳（メタデータ） (2022-06-29T01:40:38Z) - Robust Testing in High-Dimensional Sparse Models [0.0]
2つの異なる観測モデルの下で高次元スパース信号ベクトルのノルムを頑健にテストする問題を考察する。
回帰係数のノルムを確実に検定するアルゴリズムは、少なくとも$n=Omegaleft(min(slog d,1/gamma4)right)サンプルを必要とする。
論文 参考訳（メタデータ） (2022-05-16T07:47:22Z) - Active Sampling for Linear Regression Beyond the $\ell_2$ Norm [70.49273459706546]
対象ベクトルの少数のエントリのみを問合せすることを目的とした線形回帰のためのアクティブサンプリングアルゴリズムについて検討する。
我々はこの$d$への依存が対数的要因まで最適であることを示す。
また、損失関数に対して最初の全感度上界$O(dmax1,p/2log2 n)$を提供し、最大で$p$成長する。
論文 参考訳（メタデータ） (2021-11-09T00:20:01Z) - Optimal Spectral Recovery of a Planted Vector in a Subspace [80.02218763267992]
我々は、$ell_4$ノルムが同じ$ell$ノルムを持つガウスベクトルと異なるプラントベクトル$v$の効率的な推定と検出について研究する。
規則$n rho gg sqrtN$ では、大クラスのスペクトル法(そしてより一般的には、入力の低次法)は、植込みベクトルの検出に失敗する。
論文 参考訳（メタデータ） (2021-05-31T16:10:49Z) - Outlier-robust sparse/low-rank least-squares regression and robust
matrix completion [1.0878040851637998]
ヘテロジニアス雑音を伴う統計的学習フレームワークにおける高次元最小二乗回帰について検討する。
また, 製品プロセスの新たな応用に基づいて, 行列分解を伴う新しいトレーサリグレス理論を提案する。
論文 参考訳（メタデータ） (2020-12-12T07:42:47Z) - Sparse sketches with small inversion bias [79.77110958547695]
逆バイアスは、逆の共分散に依存する量の推定を平均化するときに生じる。
本研究では、確率行列に対する$(epsilon,delta)$-unbiased estimatorという概念に基づいて、逆バイアスを解析するためのフレームワークを開発する。
スケッチ行列 $S$ が密度が高く、すなわちサブガウスのエントリを持つとき、$(epsilon,delta)$-unbiased for $(Atop A)-1$ は $m=O(d+sqrt d/ のスケッチを持つ。
論文 参考訳（メタデータ） (2020-11-21T01:33:15Z) - Conditional Uncorrelation and Efficient Non-approximate Subset Selection
in Sparse Regression [72.84177488527398]
相関性の観点からスパース回帰を考察し,条件付き非相関式を提案する。
提案手法により、計算複雑性は、スパース回帰における各候補部分集合に対して$O(frac16k3+mk2+mkd)$から$O(frac16k3+frac12mk2)$に削減される。
論文 参考訳（メタデータ） (2020-09-08T20:32:26Z) - 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) - Online Robust Regression via SGD on the l1 loss [19.087335681007477]
ストリーミング方式でデータにアクセス可能なオンライン環境において、ロバストな線形回帰問題を考察する。
この研究で、$ell_O( 1 / (1 - eta)2 n )$損失の降下は、汚染された測定値に依存しない$tildeO( 1 / (1 - eta)2 n )$レートで真のパラメータベクトルに収束することを示した。
論文 参考訳（メタデータ） (2020-07-01T11:38:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。