論文の概要: Average case analysis of Lasso under ultra-sparse conditions
- arxiv url: http://arxiv.org/abs/2302.13093v1
- Date: Sat, 25 Feb 2023 14:50:32 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-28 18:57:52.451423
- Title: Average case analysis of Lasso under ultra-sparse conditions
- Title(参考訳): 超スパース条件下でのLassoの平均ケース解析
- Authors: Koki Okajima, Xiangming Meng, Takashi Takahashi, Yoshiyuki Kabashima
- Abstract要約: 回帰器の数が大きくなると、線形モデルに対する最小絶対収縮・選択演算子(Lasso)の性能を解析する。
完全サポート回復のための得られた境界は、以前の文献で与えられたものを一般化したものである。
- 参考スコア(独自算出の注目度): 4.568911586155097
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: We analyze the performance of the least absolute shrinkage and selection
operator (Lasso) for the linear model when the number of regressors $N$ grows
larger keeping the true support size $d$ finite, i.e., the ultra-sparse case.
The result is based on a novel treatment of the non-rigorous replica method in
statistical physics, which has been applied only to problem settings where $N$
,$d$ and the number of observations $M$ tend to infinity at the same rate. Our
analysis makes it possible to assess the average performance of Lasso with
Gaussian sensing matrices without assumptions on the scaling of $N$ and $M$,
the noise distribution, and the profile of the true signal. Under mild
conditions on the noise distribution, the analysis also offers a lower bound on
the sample complexity necessary for partial and perfect support recovery when
$M$ diverges as $M = O(\log N)$. The obtained bound for perfect support
recovery is a generalization of that given in previous literature, which only
considers the case of Gaussian noise and diverging $d$. Extensive numerical
experiments strongly support our analysis.
- Abstract(参考訳): 我々は,リニアモデルにおける最小絶対収縮選択演算子(lasso)の性能を解析し,レグレプタ数n$が大きくなると,真のサポートサイズである$d$有限,すなわち超スパースケースを維持する。
この結果は、統計物理学における非厳密な複製法の新しい扱いに基づいており、これはN$,$d$とM$の観測数が同じ速度で無限大となるような問題設定にのみ適用されている。
分析により,n$ および $m$ のスケーリング,ノイズ分布,真の信号のプロファイルを仮定することなく,ガウス型センシング行列を用いてlassoの平均性能を評価することができる。
ノイズ分布の穏やかな条件下では、M$が$M = O(\log N)$として発散した場合、部分的および完全サポート回復に必要なサンプル複雑性の低い境界も提供される。
得られた完全サポート回復の限界は、ガウスノイズと$d$の発散を考慮すれば、以前の文献で与えられたことを一般化したものである。
広範な数値実験が我々の分析を強く支持している。
関連論文リスト
- Minimax-optimal estimation for sparse multi-reference alignment with
collision-free signals [1.3658544194443192]
衝突のない信号に対するMRAモデルに基づく信号推定における最小値の最適化について検討する。
この設定におけるスパースMRA問題に対する推定の最小最大値は$sigma2/sqrtn$であり、$n$はサンプルサイズである。
論文 参考訳(メタデータ) (2023-12-13T02:06:52Z) - KL-Entropy-Regularized RL with a Generative Model is Minimax Optimal [70.15267479220691]
モデル強化学習のサンプル複雑性を,生成的分散自由モデルを用いて検討・解析する。
我々の分析は、$varepsilon$が十分小さい場合、$varepsilon$-optimal Policyを見つけるのが、ほぼ最小の最適化であることを示している。
論文 参考訳(メタデータ) (2022-05-27T19:39:24Z) - Optimal Online Generalized Linear Regression with Stochastic Noise and
Its Application to Heteroscedastic Bandits [88.6139446295537]
一般化線形モデルの設定におけるオンライン一般化線形回帰の問題について検討する。
ラベルノイズに対処するため、古典的追従正規化リーダ(FTRL)アルゴリズムを鋭く解析する。
本稿では,FTRLに基づくアルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-02-28T08:25:26Z) - Sharp Analysis of Random Fourier Features in Classification [9.383533125404755]
ランダムなフーリエ特徴分類が,Omega(sqrtn log n)$機能のみで,O(sqrtn)$学習率を達成できることを初めて示す。
論文 参考訳(メタデータ) (2021-09-22T09:49:27Z) - Heavy-tailed Streaming Statistical Estimation [58.70341336199497]
ストリーミング$p$のサンプルから重み付き統計推定の課題を考察する。
そこで我々は,傾きの雑音に対して,よりニュアンスな条件下での傾きの傾きの低下を設計し,より詳細な解析を行う。
論文 参考訳(メタデータ) (2021-08-25T21:30:27Z) - Towards Sample-Optimal Compressive Phase Retrieval with Sparse and
Generative Priors [59.33977545294148]
O(k log L)$サンプルは振幅に基づく経験損失関数を最小化する任意のベクトルに信号が近いことを保証するのに十分であることを示す。
この結果はスパース位相検索に適応し、基底信号が$s$-sparseおよび$n$-dimensionalである場合、$O(s log n)$サンプルは同様の保証に十分であることを示す。
論文 参考訳(メタデータ) (2021-06-29T12:49:54Z) - Convergence Rates of Stochastic Gradient Descent under Infinite Noise
Variance [14.06947898164194]
ヘビーテールは様々なシナリオで勾配降下 (sgd) で現れる。
SGDの収束保証は、潜在的に無限のばらつきを持つ状態依存性および重尾ノイズ下で提供します。
その結果,SGDは無限に分散した重尾雑音下であっても,地球最適値に収束できることが示された。
論文 参考訳(メタデータ) (2021-02-20T13:45:11Z) - Stochastic Approximation for Online Tensorial Independent Component
Analysis [98.34292831923335]
独立成分分析(ICA)は統計機械学習や信号処理において一般的な次元削減ツールである。
本稿では,各独立成分を推定する副産物オンライン時系列アルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-12-28T18:52:37Z) - Faster Convergence of Stochastic Gradient Langevin Dynamics for
Non-Log-Concave Sampling [110.88857917726276]
我々は,非log-concaveとなる分布のクラスからサンプリングするために,勾配ランゲヴィンダイナミクス(SGLD)の新たな収束解析を行う。
我々のアプローチの核心は、補助的時間反転型マルコフ連鎖を用いたSGLDのコンダクタンス解析である。
論文 参考訳(メタデータ) (2020-10-19T15:23:18Z) - Tight Nonparametric Convergence Rates for Stochastic Gradient Descent
under the Noiseless Linear Model [0.0]
このモデルに基づく最小二乗リスクに対する1パス, 固定段差勾配勾配の収束度を解析した。
特殊な場合として、ランダムなサンプリング点における値のノイズのない観測から単位区間上の実関数を推定するオンラインアルゴリズムを解析する。
論文 参考訳(メタデータ) (2020-06-15T08:25:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。