論文の概要: Sparse Linear Regression and Lattice Problems
- arxiv url: http://arxiv.org/abs/2402.14645v1
- Date: Thu, 22 Feb 2024 15:45:27 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-23 14:43:57.113493
- Title: Sparse Linear Regression and Lattice Problems
- Title（参考訳）: スパース線形回帰と格子問題
- Authors: Aparna Gupte, Neekon Vafa, Vinod Vaikuntanathan
- Abstract要約: 格子問題の平均ケース硬度を仮定したSLRw.r.t.の全ての効率的なアルゴリズムの平均ケース硬度を示す。
具体的には,SLR に対する格子上の境界距離復号法 (BDD) 問題の変種からインスタンス・バイ・インスタンス・リダクションを与える。
- 参考スコア（独自算出の注目度）: 9.50127504736299
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Sparse linear regression (SLR) is a well-studied problem in statistics where
one is given a design matrix $X\in\mathbb{R}^{m\times n}$ and a response vector
$y=X\theta^*+w$ for a $k$-sparse vector $\theta^*$ (that is,
$\|\theta^*\|_0\leq k$) and small, arbitrary noise $w$, and the goal is to find
a $k$-sparse $\widehat{\theta} \in \mathbb{R}^n$ that minimizes the mean
squared prediction error $\frac{1}{m}\|X\widehat{\theta}-X\theta^*\|^2_2$.
While $\ell_1$-relaxation methods such as basis pursuit, Lasso, and the Dantzig
selector solve SLR when the design matrix is well-conditioned, no general
algorithm is known, nor is there any formal evidence of hardness in an
average-case setting with respect to all efficient algorithms.
We give evidence of average-case hardness of SLR w.r.t. all efficient
algorithms assuming the worst-case hardness of lattice problems. Specifically,
we give an instance-by-instance reduction from a variant of the bounded
distance decoding (BDD) problem on lattices to SLR, where the condition number
of the lattice basis that defines the BDD instance is directly related to the
restricted eigenvalue condition of the design matrix, which characterizes some
of the classical statistical-computational gaps for sparse linear regression.
Also, by appealing to worst-case to average-case reductions from the world of
lattices, this shows hardness for a distribution of SLR instances; while the
design matrices are ill-conditioned, the resulting SLR instances are in the
identifiable regime.
Furthermore, for well-conditioned (essentially) isotropic Gaussian design
matrices, where Lasso is known to behave well in the identifiable regime, we
show hardness of outputting any good solution in the unidentifiable regime
where there are many solutions, assuming the worst-case hardness of standard
and well-studied lattice problems.
- Abstract（参考訳）: スパース線形回帰 (SLR) は、設計行列 $X\in\mathbb{R}^{m\times n}$ と応答ベクトル $y=X\theta^*+w$ for a $k$-sparse vector $\theta^*+w$ (つまり、$\|\theta^*\|_0\leq k$) と小さな任意のノイズ $w$ を与えられる統計学におけるよく研究された問題であり、目標は、平均二乗予測誤差 $\frac{1}{m}\|\widehat{R}^n$ を最小化する$k$-sparse $\widehat{\theta} \in \mathbb{R}^n$ を見つけることである。
basis pursuit、lasso、dantzig selectorといった$\ell_1$-relaxationメソッドは、設計行列が良く条件付けされているときにslrを解くが、一般的なアルゴリズムは知られていない。
格子問題の平均ケース硬度を仮定したSLRw.r.t.の全ての効率的なアルゴリズムの平均ケース硬度を示す。
具体的には,SLR に対する格子上の有界距離復号法(BDD)問題の変種からインスタンス単位の減算を与える。そこでは,BDD のインスタンスを定義する格子基底の条件数と設計行列の制限固有値条件との直接的関係が,スパース線形回帰に対する古典的統計計算的ギャップのいくつかを特徴付ける。
また、格子の世界における最悪のケースと平均ケースの削減に訴えることで、SLRインスタンスの分布が困難であることを示し、設計行列は不条件である一方で、結果として生じるSLRインスタンスは識別可能な状態にある。
さらに,ラッソが同定可能な状態においてよく振る舞うことが知られている等方性ガウス設計行列に対して,多くの解が存在する不特定な状態において,標準問題やよく研究された格子問題の最悪の場合の困難さを仮定して,良い解を出力することの困難さを示す。
関連論文リスト
- Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。
我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
論文 参考訳（メタデータ） (2024-03-08T18:50:19Z) - Computational-Statistical Gaps for Improper Learning in Sparse Linear Regression [4.396860522241307]
疎線形回帰の効率的な学習アルゴリズムは, 負のスパイクを持つスパースPCA問題を解くのに有効であることを示す。
我々は,低次および統計的クエリの低い境界を減らしたスパース問題に対して補う。
論文 参考訳（メタデータ） (2024-02-21T19:55:01Z) - Statistical-Computational Tradeoffs in Mixed Sparse Linear Regression [20.00109111254507]
この問題は、$frackSNR2$-to-$frack2SNR2$statistic-to-computational gapである。
また,この問題が困難な狭い状況以外では,関連する混合回帰検出問題を解くための簡単なしきい値決定アルゴリズムも分析する。
論文 参考訳（メタデータ） (2023-03-03T18:03:49Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - On the well-spread property and its relation to linear regression [4.619541348328937]
頑健な線形回帰モデルにおけるパラメータベクトルの一貫した回復は情報理論上不可能であることを示す。
与えられた$n$-by-d$行列が、周囲の次元で観測回数が二次的である場合、適切に証明できることが示される。
論文 参考訳（メタデータ） (2022-06-16T11:17:44Z) - Optimal Online Generalized Linear Regression with Stochastic Noise and
Its Application to Heteroscedastic Bandits [88.6139446295537]
一般化線形モデルの設定におけるオンライン一般化線形回帰の問題について検討する。
ラベルノイズに対処するため、古典的追従正規化リーダ(FTRL)アルゴリズムを鋭く解析する。
本稿では,FTRLに基づくアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-02-28T08:25:26Z) - On the Power of Preconditioning in Sparse Linear Regression [24.140675945592704]
プレコンディショニングされたラッソは、大まかな線形回帰問題をほぼ最適に解くことができることを示す。
最適条件のラッソに対して証明が難しいランダム設計のインスタンスを初めて構築する。
論文 参考訳（メタデータ） (2021-06-17T02:12:01Z) - Hashing embeddings of optimal dimension, with applications to linear
least squares [1.2891210250935143]
スケッチの射影次元$m$で最適である$sgeq 1$のスケッチ行列に対して、サブスペース埋め込み特性を提示する。
これらの結果をLinear Least Squares (LLS) の特殊なケースに適用し,これらの問題に対する汎用ソフトウェアパッケージであるSki-LLSを開発する。
論文 参考訳（メタデータ） (2021-05-25T10:35:13Z) - 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) - FANOK: Knockoffs in Linear Time [73.5154025911318]
本稿では,ガウスモデル-Xノックオフを効率的に実装し,大規模特徴選択問題における誤発見率を制御するアルゴリズムについて述べる。
当社のメソッドは、最大50,000ドルという問題でテストしています。
論文 参考訳（メタデータ） (2020-06-15T21:55:34Z) - Breaking the Sample Size Barrier in Model-Based Reinforcement Learning
with a Generative Model [50.38446482252857]
本稿では、生成モデル(シミュレータ)へのアクセスを想定して、強化学習のサンプル効率について検討する。
最初に$gamma$-discounted infinite-horizon Markov decision process (MDPs) with state space $mathcalS$ and action space $mathcalA$を考える。
対象の精度を考慮すれば,モデルに基づく計画アルゴリズムが最小限のサンプルの複雑さを実現するのに十分であることを示す。
論文 参考訳（メタデータ） (2020-05-26T17:53:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。