論文の概要: Distributional Hardness Against Preconditioned Lasso via Erasure-Robust
Designs
- arxiv url: http://arxiv.org/abs/2203.02824v1
- Date: Sat, 5 Mar 2022 22:16:05 GMT
- ステータス: 処理完了
- システム内更新日: 2022-03-08 15:52:35.927234
- Title: Distributional Hardness Against Preconditioned Lasso via Erasure-Robust
Designs
- Title（参考訳）: 消去ロバスト設計によるプレコンディショニングラッソに対する分布硬度
- Authors: Jonathan A. Kelner, Frederic Koehler, Raghu Meka, Dhruv Rohatgi
- Abstract要約: 標準スパースランダム設計は, 逆測定消去に対して高い確率で頑健であることを示す。
消去下での任意のスパース信号の部分的回復性が圧縮センシングで研究されたのはこれが初めてである。
- 参考スコア（独自算出の注目度）: 22.41443027099101
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Sparse linear regression with ill-conditioned Gaussian random designs is
widely believed to exhibit a statistical/computational gap, but there is
surprisingly little formal evidence for this belief, even in the form of
examples that are hard for restricted classes of algorithms. Recent work has
shown that, for certain covariance matrices, the broad class of Preconditioned
Lasso programs provably cannot succeed on polylogarithmically sparse signals
with a sublinear number of samples. However, this lower bound only shows that
for every preconditioner, there exists at least one signal that it fails to
recover successfully. This leaves open the possibility that, for example,
trying multiple different preconditioners solves every sparse linear regression
problem.
In this work, we prove a stronger lower bound that overcomes this issue. For
an appropriate covariance matrix, we construct a single signal distribution on
which any invertibly-preconditioned Lasso program fails with high probability,
unless it receives a linear number of samples.
Surprisingly, at the heart of our lower bound is a new positive result in
compressed sensing. We show that standard sparse random designs are with high
probability robust to adversarial measurement erasures, in the sense that if
$b$ measurements are erased, then all but $O(b)$ of the coordinates of the
signal are still information-theoretically identifiable. To our knowledge, this
is the first time that partial recoverability of arbitrary sparse signals under
erasures has been studied in compressed sensing.
- Abstract（参考訳）: 非条件のガウス的ランダムな設計を持つスパース線形回帰は、統計的/計算的ギャップを示すと広く信じられているが、アルゴリズムの制限されたクラスでは難しい例であっても、この信念に対する公式な証拠は驚くほど少ない。
最近の研究により、ある共分散行列に対して、幅広いプレコンディショニング・ラッソ・プログラムは、サブ線形数のサンプルを持つ多対数的にスパース信号に成功できないことが示されている。
しかし、この下限はすべてのプレコンディショナーに対して、回復に失敗する信号が少なくとも1つ存在することを示している。
これにより、例えば、複数の異なるプリコンディショナーを試すと、スパース線形回帰問題がすべて解決する可能性がある。
この研究では、この問題を克服するより強い下界を証明します。
適切な共分散行列に対して、任意の可逆条件付きlassoプログラムが線形なサンプル数を受信しなければ高い確率で失敗する単一の信号分布を構築する。
意外なことに、我々の下界の心臓部は、圧縮センシングの新たなポジティブな結果である。
標準的なスパースランダム設計は、もし$b$が消去された場合、信号の座標の全てを$O(b)$が情報理論的に識別できるという意味で、逆測定消去に対して高い確率で頑健であることを示す。
我々の知る限り、消去下での任意のスパース信号の部分的回復性が圧縮センシングで研究されたのはこれが初めてである。
関連論文リスト
- Identifying General Mechanism Shifts in Linear Causal Representations [58.6238439611389]
我々は,未知の潜在因子の線形混合を観測する線形因果表現学習環境について考察する。
近年の研究では、潜伏要因の復元や、それに基づく構造因果モデルの構築が可能であることが示されている。
非常に穏やかな標準仮定の下では、シフトしたノードの集合を識別することが可能である。
論文 参考訳（メタデータ） (2024-10-31T15:56:50Z) - Non-convex matrix sensing: Breaking the quadratic rank barrier in the sample complexity [11.412228884390784]
いくつかの測定値から低ランク2次凸行列を再構成する問題について検討した。
スペクトル特異性を持つ分解勾配は標本数と真理に収束することを示す。
論文 参考訳（メタデータ） (2024-08-20T14:09:28Z) - Lasso with Latents: Efficient Estimation, Covariate Rescaling, and
Computational-Statistical Gaps [29.13944209460543]
本研究では、観測されていない潜伏変数から強い相関関係が生じる自然なスパース線形回帰設定を提案する。
この設定では、強い相関関係に起因する問題を解析し、驚くほど単純な修正を設計する。
結果として生じる「再スケールされたラッソ」アルゴリズムのサンプルの複雑さは、(最悪の場合)下層の信号の間隔に二次的に依存する。
論文 参考訳（メタデータ） (2024-02-23T16:16:38Z) - Off-the-grid prediction and testing for linear combination of translated features [2.774897240515734]
付加的なガウス雑音過程で信号(離散あるいは連続)が観測されるモデルを考える。
我々は,スケールパラメータが変化する可能性を考慮して,オフ・ザ・グリッド推定器の過去の予測結果を拡張した。
本稿では,観測信号の特徴が与えられた有限集合に属するか否かを検証する手法を提案する。
論文 参考訳（メタデータ） (2022-12-02T13:48:45Z) - WARPd: A linearly convergent first-order method for inverse problems
with approximate sharpness conditions [0.0]
シャープネス条件は1次法のリスタートスキームのリカバリ性能を直接制御する。
重み付き, 加速度付き, 再起動されたプリマルデュアル(WARPd)の1次手法を提案する。
一般的な近似的シャープネス条件の下では、WARPd は所望のベクトルに対して安定な線形収束を達成する。
本稿では、WARPdが専門的な最先端手法と比較し、大規模問題の解決に最適であることを示す。
論文 参考訳（メタデータ） (2021-10-24T13:19:41Z) - 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) - The Generalized Lasso with Nonlinear Observations and Generative Priors [63.541900026673055]
我々は、幅広い測定モデルで満たされるガウス下測度を仮定する。
この結果から, 局所埋込特性を仮定して, 均一回復保証まで拡張できることが示唆された。
論文 参考訳（メタデータ） (2020-06-22T16:43:35Z) - Robust Compressed Sensing using Generative Models [98.64228459705859]
本稿では,Median-of-Means (MOM) にヒントを得たアルゴリズムを提案する。
我々のアルゴリズムは、外れ値が存在する場合でも、重み付きデータの回復を保証する。
論文 参考訳（メタデータ） (2020-06-16T19:07:41Z) - Approximation Schemes for ReLU Regression [80.33702497406632]
我々はReLU回帰の根本的な問題を考察する。
目的は、未知の分布から引き出された2乗損失に対して、最も適したReLUを出力することである。
論文 参考訳（メタデータ） (2020-05-26T16:26:17Z) - Sample Complexity Bounds for 1-bit Compressive Sensing and Binary Stable
Embeddings with Generative Priors [52.06292503723978]
生成モデルを用いた圧縮センシングの進歩により, 生成モデルを用いた1ビット圧縮センシングの問題点を考察した。
まずノイズのない1ビット測定を考察し, ガウス測度に基づく近似回復のためのサンプル複雑性境界を提供する。
また,リプシッツ連続生成モデルを用いた1ビット圧縮センシングにも有効であることを示すため,評価誤差と雑音に対する再構成の堅牢性を示すBinary $epsilon$-Stable Embedding特性を実証した。
論文 参考訳（メタデータ） (2020-02-05T09:44:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。