論文の概要: On the Power of Preconditioning in Sparse Linear Regression
- arxiv url: http://arxiv.org/abs/2106.09207v1
- Date: Thu, 17 Jun 2021 02:12:01 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-18 15:58:28.185555
- Title: On the Power of Preconditioning in Sparse Linear Regression
- Title（参考訳）: スパース線形回帰におけるプリコンディショニングのパワーについて
- Authors: Jonathan Kelner, Frederic Koehler, Raghu Meka, Dhruv Rohatgi
- Abstract要約: プレコンディショニングされたラッソは、大まかな線形回帰問題をほぼ最適に解くことができることを示す。
最適条件のラッソに対して証明が難しいランダム設計のインスタンスを初めて構築する。
- 参考スコア（独自算出の注目度）: 24.140675945592704
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Sparse linear regression is a fundamental problem in high-dimensional
statistics, but strikingly little is known about how to efficiently solve it
without restrictive conditions on the design matrix. We consider the
(correlated) random design setting, where the covariates are independently
drawn from a multivariate Gaussian $N(0,\Sigma)$ with $\Sigma : n \times n$,
and seek estimators $\hat{w}$ minimizing $(\hat{w}-w^*)^T\Sigma(\hat{w}-w^*)$,
where $w^*$ is the $k$-sparse ground truth. Information theoretically, one can
achieve strong error bounds with $O(k \log n)$ samples for arbitrary $\Sigma$
and $w^*$; however, no efficient algorithms are known to match these guarantees
even with $o(n)$ samples, without further assumptions on $\Sigma$ or $w^*$. As
far as hardness, computational lower bounds are only known with worst-case
design matrices. Random-design instances are known which are hard for the
Lasso, but these instances can generally be solved by Lasso after a simple
change-of-basis (i.e. preconditioning).
In this work, we give upper and lower bounds clarifying the power of
preconditioning in sparse linear regression. First, we show that the
preconditioned Lasso can solve a large class of sparse linear regression
problems nearly optimally: it succeeds whenever the dependency structure of the
covariates, in the sense of the Markov property, has low treewidth -- even if
$\Sigma$ is highly ill-conditioned. Second, we construct (for the first time)
random-design instances which are provably hard for an optimally preconditioned
Lasso. In fact, we complete our treewidth classification by proving that for
any treewidth-$t$ graph, there exists a Gaussian Markov Random Field on this
graph such that the preconditioned Lasso, with any choice of preconditioner,
requires $\Omega(t^{1/20})$ samples to recover $O(\log n)$-sparse signals when
covariates are drawn from this model.
- Abstract（参考訳）: スパース線形回帰は高次元統計学の基本的な問題であるが、設計行列上の制約条件なしで効率的に解ける方法については明らかに分かっていない。
我々は、コヴァリエートが複数の変数のガウシアン $n(0,\sigma)$ と $\sigma : n \times n$ から独立に引き出され、$(\hat{w}-w^*)^t\sigma(\hat{w}-w^*)$ を最小化する推定子$\hat{w}$ を求める。
理論的には、任意の$\sigma$ と $w^*$ に対して$o(k \log n)$ の強いエラー境界が得られるが、$\sigma$ や $w^*$ の仮定なしに、これらの保証を$o(n)$ のサンプルと一致させる効率的なアルゴリズムは知られていない。
ハードネスに関しては、計算下限は最悪の場合の設計行列でのみ知られている。
ランダム設計のインスタンスはラッソにとって難しいことが知られているが、これらのインスタンスは単純な基底の変更(つまり)の後、一般にラッソによって解決できる。
プレコンディショニング)
本研究では, 疎線形回帰におけるプレコンディショニングのパワーを明らかにするために, 上下境界を与える。
まず、プレコンディショニングされたラッソは、余変数の依存性構造がマルコフの性質という意味では、木幅が低く、たとえ$\Sigma$ が高条件であったとしても、ほぼ最適に多くの疎線型回帰問題を解くことができることを示す。
第二に、最適な前提条件のlassoでは確実に難しい(初めて)ランダム設計インスタンスを構築します。
実際、木幅分類は、任意の木幅-$t$グラフに対して、このグラフ上にガウスマルコフ確率場が存在することを証明して完了し、事前条件付きラッソは、任意のプリコンディショナーの選択により、このモデルからコヴァリエートが引き出されるときに$o(\log n)$-スパース信号を回収するために$\omega(t^{1/20})$サンプルを必要とする。
関連論文リスト
- Sparse Linear Regression and Lattice Problems [9.50127504736299]
格子問題の平均ケース硬度を仮定したSLRw.r.t.の全ての効率的なアルゴリズムの平均ケース硬度を示す。
具体的には,SLR に対する格子上の境界距離復号法 (BDD) 問題の変種からインスタンス・バイ・インスタンス・リダクションを与える。
論文 参考訳（メタデータ） (2024-02-22T15:45:27Z) - Computational-Statistical Gaps for Improper Learning in Sparse Linear Regression [4.396860522241307]
疎線形回帰の効率的な学習アルゴリズムは, 負のスパイクを持つスパースPCA問題を解くのに有効であることを示す。
我々は,低次および統計的クエリの低い境界を減らしたスパース問題に対して補う。
論文 参考訳（メタデータ） (2024-02-21T19:55:01Z) - Feature Adaptation for Sparse Linear Regression [20.923321050404827]
スパース線形回帰は高次元統計学における中心的な問題である。
少数の近似依存を許容するアルゴリズムを提供する。
我々のフレームワークは、疎線形回帰のためのより広範な機能適応のフレームワークに適合する。
論文 参考訳（メタデータ） (2023-05-26T12:53:13Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Robust Testing in High-Dimensional Sparse Models [0.0]
2つの異なる観測モデルの下で高次元スパース信号ベクトルのノルムを頑健にテストする問題を考察する。
回帰係数のノルムを確実に検定するアルゴリズムは、少なくとも$n=Omegaleft(min(slog d,1/gamma4)right)サンプルを必要とする。
論文 参考訳（メタデータ） (2022-05-16T07:47:22Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳（メタデータ） (2022-04-13T22:18:47Z) - Minimax Optimal Quantization of Linear Models: Information-Theoretic
Limits and Efficient Algorithms [59.724977092582535]
測定から学習した線形モデルの定量化の問題を考える。
この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。
本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
論文 参考訳（メタデータ） (2022-02-23T02:39:04Z) - Statistical Query Lower Bounds for List-Decodable Linear Regression [55.06171096484622]
本稿では,リスト復号化可能な線形回帰問題について考察する。
我々の主な成果は、この問題に対して$dmathrmpoly (1/alpha)$の統計的クエリ(SQ)の低いバウンダリである。
論文 参考訳（メタデータ） (2021-06-17T17:45:21Z) - Estimating Stochastic Linear Combination of Non-linear Regressions
Efficiently and Scalably [23.372021234032363]
サブサンプルサイズが大きくなると、推定誤差が過度に犠牲になることを示す。
私たちの知る限りでは、線形テキスト+確率モデルが保証される最初の研究です。
論文 参考訳（メタデータ） (2020-10-19T07:15:38Z) - 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) - Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
期待される正方形損失から、最も適合した単一ニューロンを学習することの問題点を考察する。
ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
論文 参考訳（メタデータ） (2020-05-29T07:20:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。