論文の概要: 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のような手法を用いて,対応するソリューションの信頼性を向上する方法を示す。 一般化線形回帰フレームワークにおけるスパース信号と低階信号の回復に関する古典的問題に適用可能なアルゴリズムの性能について述べる。 我々は,レグレッサと雑音分布に対するかなり弱い仮定の下で,問題次元や信頼度レベルにおいて対数的となる要因まで)パラメータ推定が,我々の精度限界に最もよく従うパラメータ推定にどのようにつながるかを示す。

関連論文リスト

• Trust-Region Sequential Quadratic Programming for Stochastic Optimization with Random Models [57.52124921268249]
  本稿では,1次と2次の両方の定常点を見つけるための信頼逐次準計画法を提案する。 本手法は, 1次定常点に収束するため, 対象対象の近似を最小化して定義された各イテレーションの勾配ステップを計算する。 2階定常点に収束するため,本手法は負曲率を減少するヘッセン行列を探索する固有ステップも計算する。
  論文  参考訳（メタデータ） (2024-09-24T04:39:47Z)
• Alternating Minimization Schemes for Computing Rate-Distortion-Perception Functions with $f$-Divergence Perception Constraints [10.564071872770146]
  離散メモリレスソースに対するRDPF(Ralse-Distortion-Perception Function)の計算について検討した。 最適パラメトリック解を特徴付ける。 歪みと知覚制約について十分な条件を提供する。
  論文  参考訳（メタデータ） (2024-08-27T12:50:12Z)
• Accelerated stochastic approximation with state-dependent noise [7.4648480208501455]
  勾配観測における2次雑音に対する一般仮定の下での滑らかな凸最適化問題を考察する。 このような問題は、統計学におけるよく知られた一般化された線形回帰問題において、様々な応用において自然に発生する。 SAGDとSGEは、適切な条件下で、最適収束率を達成することを示す。
  論文  参考訳（メタデータ） (2023-07-04T06:06:10Z)
• 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)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。 非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。 そこで我々は,勾配クリッピングを伴う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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。