論文の概要: Statistical-Computational Tradeoffs in Mixed Sparse Linear Regression
- arxiv url: http://arxiv.org/abs/2303.02118v1
- Date: Fri, 3 Mar 2023 18:03:49 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-06 13:53:27.703540
- Title: Statistical-Computational Tradeoffs in Mixed Sparse Linear Regression
- Title（参考訳）: 混合スパース線形回帰における統計計算的トレードオフ
- Authors: Gabriel Arpino and Ramji Venkataramanan
- Abstract要約: この問題は、$frackSNR2$-to-$frack2SNR2$statistic-to-computational gapである。
また,この問題が困難な狭い状況以外では,関連する混合回帰検出問題を解くための簡単なしきい値決定アルゴリズムも分析する。
- 参考スコア（独自算出の注目度）: 20.00109111254507
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider the problem of mixed sparse linear regression with two
components, where two real $k$-sparse signals $\beta_1, \beta_2$ are to be
recovered from $n$ unlabelled noisy linear measurements. The sparsity is
allowed to be sublinear in the dimension, and additive noise is assumed to be
independent Gaussian with variance $\sigma^2$. Prior work has shown that the
problem suffers from a $\frac{k}{SNR^2}$-to-$\frac{k^2}{SNR^2}$
statistical-to-computational gap, resembling other computationally challenging
high-dimensional inference problems such as Sparse PCA and Robust Sparse Mean
Estimation; here $SNR$ is the signal-to-noise ratio. We establish the existence
of a more extensive computational barrier for this problem through the method
of low-degree polynomials, but show that the problem is computationally hard
only in a very narrow symmetric parameter regime. We identify a smooth
information-computation tradeoff between the sample complexity $n$ and runtime
for any randomized algorithm in this hard regime. Via a simple reduction, this
provides novel rigorous evidence for the existence of a computational barrier
to solving exact support recovery in sparse phase retrieval with sample
complexity $n = \tilde{o}(k^2)$. Our second contribution is to analyze a simple
thresholding algorithm which, outside of the narrow regime where the problem is
hard, solves the associated mixed regression detection problem in $O(np)$ time
with square-root the number of samples and matches the sample complexity
required for (non-mixed) sparse linear regression; this allows the recovery
problem to be subsequently solved by state-of-the-art techniques from the dense
case. As a special case of our results, we show that this simple algorithm is
order-optimal among a large family of algorithms in solving exact signed
support recovery in sparse linear regression.
- Abstract（参考訳）: 2つの成分による混合スパース線形回帰の問題を考えると、2つの実$k$スパース信号 $\beta_1, \beta_2$ が$n$の非ラベリングノイズ線型測定から回収される。
スパーシティは次元において部分線型であることが許され、加法ノイズは分散 $\sigma^2$ を持つ独立ガウスであると仮定される。
以前の研究によると、この問題は$\frac{k}{snr^2}$-to-$\frac{k^2}{snr^2}$ 統計計算から計算へのギャップに苦しんでおり、スパースpcaやロバストスパース平均推定のような計算上困難な他の高次元推論問題に似ている。
低次多項式の手法によりこの問題に対するより広範な計算障壁の存在を確立するが、この問題は非常に狭い対称パラメータ状態においてのみ計算的に困難であることを示す。
この難易度における任意のランダム化アルゴリズムに対して,サンプル複雑性$n$と実行時の間のスムーズな情報計算トレードオフを同定する。
単純な還元により、サンプル複雑性 $n = \tilde{o}(k^2)$ でスパース位相検索における正確な支持回復を解決するために計算障壁が存在するという新しい厳密な証拠が得られる。
第2の貢献は, 難解な狭い状況以外では, サンプル数と正方根の時間と(非混合)スパース線形回帰に必要なサンプルの複雑さを一致させて, 関連する混合回帰検出問題を$O(np)$で解く, という単純なしきい値決定アルゴリズムを解析することである。
この結果の特別な場合として,この単純なアルゴリズムは,分散線形回帰法において,完全符号付きサポートリカバリを解くためのアルゴリズム群の中で,順序最適であることを示す。
関連論文リスト
- A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。
提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
論文 参考訳（メタデータ） (2024-09-07T06:37:23Z) - Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。
我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。
我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
論文 参考訳（メタデータ） (2024-05-10T09:58:47Z) - Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。
我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
論文 参考訳（メタデータ） (2024-03-08T18:50:19Z) - Information-Computation Tradeoffs for Learning Margin Halfspaces with
Random Classification Noise [50.64137465792738]
ランダム分類ノイズを用いたPAC$gamma$-marginハーフスペースの問題について検討する。
我々は、問題のサンプル複雑性と計算効率の良いアルゴリズムのサンプル複雑性との間に固有のギャップを示唆する情報計算トレードオフを確立する。
論文 参考訳（メタデータ） (2023-06-28T16:33:39Z) - Feature Adaptation for Sparse Linear Regression [20.923321050404827]
スパース線形回帰は高次元統計学における中心的な問題である。
少数の近似依存を許容するアルゴリズムを提供する。
我々のフレームワークは、疎線形回帰のためのより広範な機能適応のフレームワークに適合する。
論文 参考訳（メタデータ） (2023-05-26T12:53:13Z) - A Conditional Randomization Test for Sparse Logistic Regression in
High-Dimension [36.00360315353985]
emphCRT-logitは、変数蒸留ステップとデコレーションステップを組み合わせたアルゴリズムである。
本手法の理論的解析を行い,大規模な脳画像とゲノムデータセットの実験とともにシミュレーションにおける有効性を示す。
論文 参考訳（メタデータ） (2022-05-29T09:37:16Z) - 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) - 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) - Efficient Algorithms for Multidimensional Segmented Regression [42.046881924063044]
多次元回帰を用いた固定設計の基本問題について検討する。
我々は任意の固定次元におけるこの問題に対する最初のサンプルと計算効率のよいアルゴリズムを提供する。
提案アルゴリズムは,多次元的条件下では新規な,単純なマージ反復手法に依存している。
論文 参考訳（メタデータ） (2020-03-24T19:39:34Z) - Efficient algorithms for multivariate shape-constrained convex
regression problems [9.281671380673306]
最小二乗推定器は、制約付き凸プログラミング(QP)問題を$(n+1)d$変数と少なくとも$n(n-1)$線形不等式制約で解くことで計算可能であることを証明している。
一般に非常に大規模な凸QPを解くために、我々は2つの効率的なアルゴリズムを設計する。1つは対称ガウス・シーデルに基づく乗算器の交互方向法(tt sGS-ADMM)であり、もう1つは半滑らかニュートン法(tt)によって解かれる部分プロブレムを持つ近似拡張ラグランジアン法(tt pALM)である。
論文 参考訳（メタデータ） (2020-02-26T11:18:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。