論文の概要: Stability and Risk Bounds of Iterative Hard Thresholding
- arxiv url: http://arxiv.org/abs/2203.09413v1
- Date: Thu, 17 Mar 2022 16:12:56 GMT
- ステータス: 処理完了
- システム内更新日: 2022-03-18 18:56:34.582722
- Title: Stability and Risk Bounds of Iterative Hard Thresholding
- Title（参考訳）: 反復型ハードThresholdingの安定性とリスク境界
- Authors: Xiao-Tong Yuan and Ping Li
- Abstract要約: アルゴリズム安定性の概念の下でIHTの新しいスパース一般化理論を導入する。
スパースレベル$k$のIHTは、スパース過剰リスクにおける収束率を$mathcaltilde O(n-1/2sqrtlog(n)log(p))$で楽しむことを示す。
理論的予測を確認するための予備的な数値的証拠が提供される。
- 参考スコア（独自算出の注目度）: 41.082982732100696
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this paper, we analyze the generalization performance of the Iterative
Hard Thresholding (IHT) algorithm widely used for sparse recovery problems. The
parameter estimation and sparsity recovery consistency of IHT has long been
known in compressed sensing. From the perspective of statistical learning,
another fundamental question is how well the IHT estimation would predict on
unseen data. This paper makes progress towards answering this open question by
introducing a novel sparse generalization theory for IHT under the notion of
algorithmic stability. Our theory reveals that: 1) under natural conditions on
the empirical risk function over $n$ samples of dimension $p$, IHT with
sparsity level $k$ enjoys an $\mathcal{\tilde
O}(n^{-1/2}\sqrt{k\log(n)\log(p)})$ rate of convergence in sparse excess risk;
2) a tighter $\mathcal{\tilde O}(n^{-1/2}\sqrt{\log(n)})$ bound can be
established by imposing an additional iteration stability condition on a
hypothetical IHT procedure invoked to the population risk; and 3) a fast rate
of order $\mathcal{\tilde O}\left(n^{-1}k(\log^3(n)+\log(p))\right)$ can be
derived for strongly convex risk function under proper strong-signal
conditions. The results have been substantialized to sparse linear regression
and sparse logistic regression models to demonstrate the applicability of our
theory. Preliminary numerical evidence is provided to confirm our theoretical
predictions.
- Abstract（参考訳）: 本稿では,sparse recovery問題に広く用いられている反復型ハードしきい値(iht)アルゴリズムの一般化性能について解析する。
IHTのパラメータ推定と疎性回復の整合性は、長い間圧縮センシングにおいて知られていた。
統計的学習の観点からは、別の根本的な疑問は、IHT推定が目に見えないデータに対してどの程度うまく予測するかである。
本稿では,アルゴリズム的安定性の概念の下でIHTの新しいスパース一般化理論を導入することにより,このオープンな質問に答える。
私たちの理論が示すのは
1) 次元 $p$ 以上の経験的リスク関数上の自然条件の下では、スパルシティレベル $k$ を持つ iht は、スパース過剰リスクにおける収束率 $\mathcal{\tilde o}(n^{-1/2}\sqrt{k\log(n)\log(p)}) を享受する。
2) より厳密な$\mathcal{\tilde O}(n^{-1/2}\sqrt{\log(n)})$boundは、集団リスクによって誘導される仮説的IHTプロシージャに追加の反復安定条件を課すことによって確立できる。
3) 次数 $\mathcal{\tilde o}\left(n^{-1}k(\log^3(n)+\log(p))\right)$ は、適切な強信号条件下での強凸リスク関数に対して導出することができる。
その結果, 線形回帰モデルと疎ロジスティック回帰モデルを用いて, 理論の適用性を示すことができた。
理論的予測を確認するための予備的な数値的証拠が提供される。
関連論文リスト
- Towards Faster Non-Asymptotic Convergence for Diffusion-Based Generative
Models [49.81937966106691]
我々は拡散モデルのデータ生成過程を理解するための非漸近理論のスイートを開発する。
従来の研究とは対照的に,本理論は基本的だが多目的な非漸近的アプローチに基づいて開発されている。
論文 参考訳（メタデータ） (2023-06-15T16:30:08Z) - On the Stability and Generalization of Triplet Learning [55.75784102837832]
トリプルトラーニング(トリプルトラーニング)、すなわちトリプルトデータから学ぶことは、コンピュータビジョンタスクに大きな注目を集めている。
本稿では,安定解析を利用した三重項学習の一般化保証について検討する。
論文 参考訳（メタデータ） (2023-02-20T07:32:50Z) - Retire: Robust Expectile Regression in High Dimensions [3.9391041278203978]
ペナル化量子化法と期待回帰法は、高次元データの異方性検出に有用な手段を提供する。
我々は,頑健な期待回帰(退職)を提案し,研究する。
提案手法は半平滑なニュートン座標降下アルゴリズムにより効率よく解けることを示す。
論文 参考訳（メタデータ） (2022-12-11T18:03:12Z) - A Conditional Randomization Test for Sparse Logistic Regression in
High-Dimension [36.00360315353985]
emphCRT-logitは、変数蒸留ステップとデコレーションステップを組み合わせたアルゴリズムである。
本手法の理論的解析を行い,大規模な脳画像とゲノムデータセットの実験とともにシミュレーションにおける有効性を示す。
論文 参考訳（メタデータ） (2022-05-29T09:37:16Z) - Non-Asymptotic Guarantees for Robust Statistical Learning under
$(1+\varepsilon)$-th Moment Assumption [0.716879432974126]
本稿では,統計レグレッションの多種族を対象としたログトランケート型M-メチエータを提案する。
標準推定よりもログトランケート推定の方が優れていることを示す。
論文 参考訳（メタデータ） (2022-01-10T06:22:30Z) - Heavy-tailed Streaming Statistical Estimation [58.70341336199497]
ストリーミング$p$のサンプルから重み付き統計推定の課題を考察する。
そこで我々は,傾きの雑音に対して,よりニュアンスな条件下での傾きの傾きの低下を設計し,より詳細な解析を行う。
論文 参考訳（メタデータ） (2021-08-25T21:30:27Z) - Understanding the Under-Coverage Bias in Uncertainty Estimation [58.03725169462616]
量子レグレッションは、現実の望ましいカバレッジレベルよりもアンファンダーカバー(enmphunder-cover)する傾向がある。
我々は、量子レグレッションが固有のアンダーカバーバイアスに悩まされていることを証明している。
我々の理論は、この過大被覆バイアスが特定の高次元パラメータ推定誤差に起因することを明らかにしている。
論文 参考訳（メタデータ） (2021-06-10T06:11:55Z) - SLOE: A Faster Method for Statistical Inference in High-Dimensional
Logistic Regression [68.66245730450915]
実用データセットに対する予測の偏見を回避し、頻繁な不確実性を推定する改善された手法を開発している。
私たちの主な貢献は、推定と推論の計算時間をマグニチュードの順序で短縮する収束保証付き信号強度の推定器SLOEです。
論文 参考訳（メタデータ） (2021-03-23T17:48:56Z) - Convergence Rates of Stochastic Gradient Descent under Infinite Noise
Variance [14.06947898164194]
ヘビーテールは様々なシナリオで勾配降下 (sgd) で現れる。
SGDの収束保証は、潜在的に無限のばらつきを持つ状態依存性および重尾ノイズ下で提供します。
その結果,SGDは無限に分散した重尾雑音下であっても,地球最適値に収束できることが示された。
論文 参考訳（メタデータ） (2021-02-20T13:45:11Z) - Estimation in Tensor Ising Models [5.161531917413708]
N$ノード上の分布から1つのサンプルを与えられた$p$-tensor Isingモデルの自然パラメータを推定する問題を考える。
特に、$sqrt N$-consistency of the MPL estimate in the $p$-spin Sherrington-Kirkpatrick (SK) model。
我々は、$p$-tensor Curie-Weiss モデルの特別な場合における MPL 推定の正確なゆらぎを導出する。
論文 参考訳（メタデータ） (2020-08-29T00:06:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。