論文の概要: Sparse recovery by reduced variance stochastic approximation
- arxiv url: http://arxiv.org/abs/2006.06365v3
- Date: Wed, 30 Mar 2022 15:46:57 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-22 10:03:40.089832
- Title: Sparse recovery by reduced variance stochastic approximation
- Title(参考訳): 分散確率近似によるスパース回復
- Authors: Anatoli Juditsky and Andrei Kulunchakov and Hlib Tsyntseus
- Abstract要約: 雑音観測によるスパース信号回復問題に対する反復2次最適化ルーチンの適用について論じる。
本稿では,Median-of-Meansのような手法を用いて,対応するソリューションの信頼性を向上する方法について述べる。
- 参考スコア(独自算出の注目度): 5.672132510411465
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we discuss application of iterative Stochastic Optimization
routines to the problem of sparse signal recovery from noisy observation. Using
Stochastic Mirror Descent algorithm as a building block, we develop a
multistage procedure for recovery of sparse solutions to Stochastic
Optimization problem under assumption of smoothness and quadratic minoration on
the expected objective. An interesting feature of the proposed algorithm is
linear convergence of the approximate solution during the preliminary phase of
the routine when the component of stochastic error in the gradient observation
which is due to bad initial approximation of the optimal solution is larger
than the "ideal" asymptotic error component owing to observation noise "at the
optimal solution." We also show how one can straightforwardly enhance
reliability of the corresponding solution by using Median-of-Means like
techniques.
We illustrate the performance of the proposed algorithms in application to
classical problems of recovery of sparse and low rank signals in generalized
linear regression framework. We show, under rather weak assumption on the
regressor and noise distributions, how they lead to parameter estimates which
obey (up to factors which are logarithmic in problem dimension and confidence
level) the best known to us accuracy bounds.
- Abstract(参考訳): 本稿では,反復的確率的最適化ルーチンの雑音観測からのスパース信号回復問題への適用について述べる。
確率鏡のDescentアルゴリズムをビルディングブロックとして用い,確率最適化問題に対するスパース解の滑らかさと2次的マイナレーションを仮定した多段階的手法を開発した。
提案アルゴリズムの興味深い特徴は、最適解の悪い初期近似による勾配観測における確率誤差の成分が、「最適解」の観測ノイズによる「理想的」漸近誤差成分よりも大きいとき、ルーチンの予備相における近似解の線形収束である。
また,Median-of-Meansのような手法を用いて,対応するソリューションの信頼性を向上する方法を示す。
一般化線形回帰フレームワークにおけるスパース信号と低階信号の回復に関する古典的問題に適用可能なアルゴリズムの性能について述べる。
我々は,レグレッサと雑音分布に対するかなり弱い仮定の下で,問題次元や信頼度レベルにおいて対数的となる要因まで)パラメータ推定が,我々の精度限界に最もよく従うパラメータ推定にどのようにつながるかを示す。
関連論文リスト
- Accelerated stochastic approximation with state-dependent noise [7.623467689146604]
勾配観測における2次雑音に対する一般仮定の下での滑らかな凸最適化問題を考察する。
このような問題は、統計学におけるよく知られた一般化された線形回帰問題において、様々な応用において自然に発生する。
SAGDとSGEは、適切な条件下で、最適収束率を達成することを示す。
論文 参考訳(メタデータ) (2023-07-04T06:06:10Z) - OKRidge: Scalable Optimal k-Sparse Ridge Regression [21.17964202317435]
スパースリッジ回帰のための高速アルゴリズムOKRidgeを提案する。
また,ビームサーチを利用した解法を温める方法を提案する。
論文 参考訳(メタデータ) (2023-04-13T17:34:44Z) - Optimal Algorithms for the Inhomogeneous Spiked Wigner Model [89.1371983413931]
不均一な問題に対する近似メッセージパッシングアルゴリズム(AMP)を導出する。
特に,情報理論の閾値よりも大きい信号と雑音の比を必要とする既知のアルゴリズムが,ランダムよりも優れた処理を行うための統計的・計算的ギャップの存在を同定する。
論文 参考訳(メタデータ) (2023-02-13T19:57:17Z) - Stochastic Mirror Descent for Large-Scale Sparse Recovery [13.500750042707407]
本稿では,2次近似の高次元スパースパラメータの統計的推定への応用について論じる。
提案アルゴリズムは, 回帰器分布の弱い仮定の下で, 推定誤差の最適収束を実現する。
論文 参考訳(メタデータ) (2022-10-23T23:23:23Z) - Exploring the Algorithm-Dependent Generalization of AUPRC Optimization
with List Stability [107.65337427333064]
AUPRC(Area Under the Precision-Recall Curve)の最適化は、機械学習にとって重要な問題である。
本研究では, AUPRC最適化の単依存一般化における最初の試行について述べる。
3つの画像検索データセットの実験は、我々のフレームワークの有効性と健全性に言及する。
論文 参考訳(メタデータ) (2022-09-27T09:06:37Z) - Stochastic Approximation with Decision-Dependent Distributions: Asymptotic Normality and Optimality [8.771678221101368]
我々は、アルゴリズムが使用するデータ分布が反復列に沿って進化する決定依存問題に対する近似を解析する。
軽微な仮定の下では、アルゴリズムの反復と解の偏差は正規であることを示す。
また,平均化アルゴリズムの性能は局所的に最小限であることを示す。
論文 参考訳(メタデータ) (2022-07-09T01:44:17Z) - Optimal Rates for Random Order Online Optimization [60.011653053877126]
敵が損失関数を選択できるカテットガルバー2020onlineについて検討するが、一様にランダムな順序で提示される。
2020onlineアルゴリズムが最適境界を達成し,安定性を著しく向上することを示す。
論文 参考訳(メタデータ) (2021-06-29T09:48:46Z) - Near-Optimal High Probability Complexity Bounds for Non-Smooth
Stochastic Optimization with Heavy-Tailed Noise [63.304196997102494]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。
既存の非滑らか凸最適化法は、負のパワーまたは対数的な信頼度に依存する境界の複雑さを持つ。
クリッピングを用いた2つの勾配法に対して, 新たなステップサイズルールを提案する。
論文 参考訳(メタデータ) (2021-06-10T17:54:21Z) - Convergence of adaptive algorithms for weakly convex constrained
optimization [59.36386973876765]
モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。
我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
論文 参考訳(メタデータ) (2020-06-11T17:43:19Z) - Support recovery and sup-norm convergence rates for sparse pivotal
estimation [79.13844065776928]
高次元スパース回帰では、ピボット推定器は最適な正規化パラメータがノイズレベルに依存しない推定器である。
非滑らかで滑らかな単一タスクとマルチタスク正方形ラッソ型推定器に対するミニマックス超ノルム収束率を示す。
論文 参考訳(メタデータ) (2020-01-15T16:11:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。