論文の概要: A Non-Asymptotic Framework for Approximate Message Passing in Spiked
Models
- arxiv url: http://arxiv.org/abs/2208.03313v1
- Date: Fri, 5 Aug 2022 17:59:06 GMT
- ステータス: 処理完了
- システム内更新日: 2022-08-08 12:28:28.009301
- Title: A Non-Asymptotic Framework for Approximate Message Passing in Spiked
Models
- Title（参考訳）: スパイクモデルにおける近似メッセージパッシングのための非漸近的枠組み
- Authors: Gen Li, Yuting Wei
- Abstract要約: 近似メッセージパッシング(AMP)は高次元統計問題を解くための効果的な反復パラダイムとして現れる。
それまでのAMP理論は、反復の数が$obig(fraclog nloglog nbig)$を超えると、AMP力学を予測できなかった。
本稿では,スパイク行列推定におけるAMP理解のための非漸近的枠組みを開発する。
- 参考スコア（独自算出の注目度）: 24.786030482013437
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Approximate message passing (AMP) emerges as an effective iterative paradigm
for solving high-dimensional statistical problems. However, prior AMP theory --
which focused mostly on high-dimensional asymptotics -- fell short of
predicting the AMP dynamics when the number of iterations surpasses
$o\big(\frac{\log n}{\log\log n}\big)$ (with $n$ the problem dimension). To
address this inadequacy, this paper develops a non-asymptotic framework for
understanding AMP in spiked matrix estimation. Built upon new decomposition of
AMP updates and controllable residual terms, we lay out an analysis recipe to
characterize the finite-sample behavior of AMP in the presence of an
independent initialization, which is further generalized to allow for spectral
initialization. As two concrete consequences of the proposed analysis recipe:
(i) when solving $\mathbb{Z}_2$ synchronization, we predict the behavior of
spectrally initialized AMP for up to $O\big(\frac{n}{\mathrm{poly}\log n}\big)$
iterations, showing that the algorithm succeeds without the need of a
subsequent refinement stage (as conjectured recently by
\citet{celentano2021local}); (ii) we characterize the non-asymptotic behavior
of AMP in sparse PCA (in the spiked Wigner model) for a broad range of
signal-to-noise ratio.
- Abstract（参考訳）: 近似メッセージパッシング(AMP)は高次元統計問題を解くための効果的な反復パラダイムとして現れる。
しかし、前者のAMP理論(主に高次元の漸近論に焦点を当てた)は、反復数が$o\big(\frac{\log n}{\log\log n}\big)$(問題の次元は$n$)を超えると、AMP力学を予測できない。
この問題に対処するため,本論文では,スパイク行列推定におけるampを理解するための非漸近的枠組みを開発した。
AMP更新と制御可能な残差項の新たな分解に基づいて、独立初期化の存在下でのAMPの有限サンプル挙動を特徴付ける解析レシピを配置し、スペクトル初期化を可能にするためにさらに一般化した。
提案する分析方法の2つの具体的な結果として
i)$\mathbb{Z}_2$同期を解くとき、最大$O\big(\frac{n}{\mathrm{poly}\log n}\big)$反復に対するスペクトル初期化AMPの挙動を予測し、アルゴリズムがその後の改良段階を必要とせずに成功することを示す(最近 \citet{celentano2021local} によって予想されている)。
(II) 広帯域の信号-雑音比に対して, スパースPCA(スパイクドウィグナーモデル)におけるAMPの非漸近挙動を特徴付ける。
関連論文リスト
- Non-asymptotic bounds for forward processes in denoising diffusions: Ornstein-Uhlenbeck is hard to beat [49.1574468325115]
本稿では,全変動(TV)における前方拡散誤差の非漸近的境界について述べる。
我々は、R$からFarthestモードまでの距離でマルチモーダルデータ分布をパラメライズし、加法的および乗法的雑音による前方拡散を考察する。
論文 参考訳（メタデータ） (2024-08-25T10:28:31Z) - A Random Matrix Approach to Low-Multilinear-Rank Tensor Approximation [24.558241146742205]
本研究では,データテンソルの展開のスペクトルの多次元的挙動を特徴付け,信号の主方向の検出性を決定する関連信号-雑音比を示す。
その結果,非自明な状態下でのマルチリニアSVD (MLSVD) の再構成性能を正確に予測することができた。
論文 参考訳（メタデータ） (2024-02-05T16:38:30Z) - A non-asymptotic distributional theory of approximate message passing
for sparse and robust regression [20.830017611900832]
本稿では、近似メッセージパッシング(AMP)のための非漸近分布特性について述べる。
AMPは、高速な推定器と強力な理論機械の両方として有効であることを示す反復アルゴリズムのファミリーである。
論文 参考訳（メタデータ） (2024-01-08T14:34:35Z) - Restoration-Degradation Beyond Linear Diffusions: A Non-Asymptotic
Analysis For DDIM-Type Samplers [90.45898746733397]
本研究では拡散生成モデルに用いる決定論的サンプリング器の非漸近解析のためのフレームワークを開発する。
確率フローODEに沿った1ステップは,1) 条件付き対数線上を無限に先行して上昇する回復ステップ,2) 雑音を現在の勾配に向けて前向きに進行する劣化ステップの2段階で表すことができる。
論文 参考訳（メタデータ） (2023-03-06T18:59:19Z) - Approximate message passing from random initialization with applications
to $\mathbb{Z}_{2}$ synchronization [25.511475484340156]
本稿では,未知のランク1行列を先行構造情報で再構成する問題について考察する。
我々は,このモデルでアポキシマトメッセージパッシング(AMP)の非同化的特徴を初めて提供する。
論文 参考訳（メタデータ） (2023-02-07T18:58:08Z) - 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) - PCA Initialization for Approximate Message Passing in Rotationally
Invariant Models [29.039655256171088]
主成分分析は自然推定器であり、その性能は高次元状態において急激な結果が得られた。
近年,PCAの精度を向上させる可能性のある代替推定器として,AMPアルゴリズムが提案されている。
そこで本研究では,AMPをPCAに初期化する2つの手法を組み合わせて,この推定器の性能を厳密に評価する手法を提案する。
論文 参考訳（メタデータ） (2021-06-04T09:13:51Z) - Approximate Message Passing with Spectral Initialization for Generalized
Linear Models [35.618694363241744]
我々は、近似メッセージパッシング(AMP)に基づく推定器に焦点を当てる。
スペクトル推定器を用いたAMPアルゴリズムを提案する。
また,提案手法の有効性を示す数値的な結果も提供する。
論文 参考訳（メタデータ） (2020-10-07T14:52:35Z) - A maximum-entropy approach to off-policy evaluation in average-reward
MDPs [54.967872716145656]
この研究は、無限水平非カウントマルコフ決定過程(MDPs)における関数近似を伴うオフ・ポリティ・アセスメント(OPE)に焦点を当てる。
提案手法は,第1の有限サンプル OPE 誤差境界であり,既存の結果がエピソードおよびディスカウントケースを超えて拡張される。
この結果から,教師あり学習における最大エントロピー的アプローチを並列化して,十分な統計値を持つ指数関数型家族分布が得られた。
論文 参考訳（メタデータ） (2020-06-17T18:13:37Z) - Is Temporal Difference Learning Optimal? An Instance-Dependent Analysis [102.29671176698373]
我々は、割引決定過程における政策評価の問題に対処し、生成モデルの下で、ll_infty$errorに対するマルコフに依存した保証を提供する。
我々は、ポリシー評価のために、局所ミニマックス下限の両漸近バージョンと非漸近バージョンを確立し、アルゴリズムを比較するためのインスタンス依存ベースラインを提供する。
論文 参考訳（メタデータ） (2020-03-16T17:15:28Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。