論文の概要: Feature Adaptation for Sparse Linear Regression
- arxiv url: http://arxiv.org/abs/2305.16892v1
- Date: Fri, 26 May 2023 12:53:13 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-29 15:05:35.386199
- Title: Feature Adaptation for Sparse Linear Regression
- Title（参考訳）: Sparse Linear Regression の特徴適応
- Authors: Jonathan Kelner, Frederic Koehler, Raghu Meka, Dhruv Rohatgi
- Abstract要約: スパース線形回帰は高次元統計学における中心的な問題である。
少数の近似依存を許容するアルゴリズムを提供する。
我々のフレームワークは、疎線形回帰のためのより広範な機能適応のフレームワークに適合する。
- 参考スコア（独自算出の注目度）: 20.923321050404827
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Sparse linear regression is a central problem in high-dimensional statistics.
We study the correlated random design setting, where the covariates are drawn
from a multivariate Gaussian $N(0,\Sigma)$, and we seek an estimator with small
excess risk.
If the true signal is $t$-sparse, information-theoretically, it is possible
to achieve strong recovery guarantees with only $O(t\log n)$ samples. However,
computationally efficient algorithms have sample complexity linear in (some
variant of) the condition number of $\Sigma$. Classical algorithms such as the
Lasso can require significantly more samples than necessary even if there is
only a single sparse approximate dependency among the covariates.
We provide a polynomial-time algorithm that, given $\Sigma$, automatically
adapts the Lasso to tolerate a small number of approximate dependencies. In
particular, we achieve near-optimal sample complexity for constant sparsity and
if $\Sigma$ has few ``outlier'' eigenvalues. Our algorithm fits into a broader
framework of feature adaptation for sparse linear regression with
ill-conditioned covariates. With this framework, we additionally provide the
first polynomial-factor improvement over brute-force search for constant
sparsity $t$ and arbitrary covariance $\Sigma$.
- Abstract（参考訳）: スパース線形回帰は高次元統計学における中心的な問題である。
多変量ガウス$N(0,\Sigma)$から共変量を引き出すような相関ランダムな設計条件について検討し、余剰リスクの少ない推定器を求める。
真の信号が$t$-sparseで情報理論上は$O(t\log n)$サンプルだけで強い回復保証を達成することができる。
しかし、計算効率の良いアルゴリズムはサンプル複雑性を(ある変種)$\Sigma$の条件数に線形に持つ。
ラッソのような古典的なアルゴリズムは、共変量の間に単一のスパース近似依存性がある場合でも、必要以上に多くのサンプルを必要とする。
多項式時間アルゴリズムは、$\Sigma$を与えられた場合、Lassoを自動で適用し、少数の近似依存を許容する。
特に、定数スパーシティと$\sigma$ が ``outlier''' 固有値を持たない場合の最適に近いサンプル複雑性を達成する。
我々のアルゴリズムは、不条件共変量を用いた疎線形回帰のためのより広範な特徴適応の枠組みに適合する。
このフレームワークでは、定数スパーシティ $t$ と任意の共分散 $\sigma$ に対するブルート力探索に対する最初の多項式因子の改善も提供する。
関連論文リスト
- Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。
我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
論文 参考訳（メタデータ） (2024-03-08T18:50:19Z) - Lasso with Latents: Efficient Estimation, Covariate Rescaling, and
Computational-Statistical Gaps [29.13944209460543]
本研究では、観測されていない潜伏変数から強い相関関係が生じる自然なスパース線形回帰設定を提案する。
この設定では、強い相関関係に起因する問題を解析し、驚くほど単純な修正を設計する。
結果として生じる「再スケールされたラッソ」アルゴリズムのサンプルの複雑さは、(最悪の場合)下層の信号の間隔に二次的に依存する。
論文 参考訳（メタデータ） (2024-02-23T16:16:38Z) - 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) - Stochastic Approximation Approaches to Group Distributionally Robust
Optimization [96.26317627118912]
群分散ロバスト最適化(GDRO)
オンライン学習技術は、各ラウンドに必要なサンプル数をm$から1$に減らし、同じサンプルを保持する。
分布依存収束率を導出できる重み付きGDROの新規な定式化。
論文 参考訳（メタデータ） (2023-02-18T09:24:15Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Efficient and robust high-dimensional sparse logistic regression via
nonlinear primal-dual hybrid gradient algorithms [0.0]
弾性ネットペナルティによって正規化されるロジスティック回帰問題に対する解を確実に計算する反復アルゴリズムを提案する。
この結果は、一階最適化法に対して$O(min(m2n,mn2)log (1/epsilon))$の既知の複雑性境界を改善する。
論文 参考訳（メタデータ） (2021-11-30T14:16:48Z) - On the Power of Preconditioning in Sparse Linear Regression [24.140675945592704]
プレコンディショニングされたラッソは、大まかな線形回帰問題をほぼ最適に解くことができることを示す。
最適条件のラッソに対して証明が難しいランダム設計のインスタンスを初めて構築する。
論文 参考訳（メタデータ） (2021-06-17T02:12:01Z) - 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) - FANOK: Knockoffs in Linear Time [73.5154025911318]
本稿では,ガウスモデル-Xノックオフを効率的に実装し,大規模特徴選択問題における誤発見率を制御するアルゴリズムについて述べる。
当社のメソッドは、最大50,000ドルという問題でテストしています。
論文 参考訳（メタデータ） (2020-06-15T21:55:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。