論文の概要: Spike-and-Slab Posterior Sampling in High Dimensions

• arxiv url: http://arxiv.org/abs/2503.02798v1
• Date: Tue, 04 Mar 2025 17:16:07 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-05 19:21:50.739604
• Title: Spike-and-Slab Posterior Sampling in High Dimensions
• Title（参考訳）: 高次元におけるスパイク・アンド・スラブ後部サンプリング
• Authors: Syamantak Kumar, Purnamrita Sarkar, Kevin Tian, Yusong Zhu,
• Abstract要約: スパイク・アンド・スラブ先行法[MB88]による後方サンプリングは,ベイズ・スパース線形回帰の理論的金標準法であると考えられる。 我々は,任意のSNRに適用可能なスパイク・アンド・スラブ後続サンプリングのための最初の証明可能なアルゴリズムを提示し,問題次元における測定カウントサブを使用する。 ラプラス拡散密度を用いたスパイク・アンド・スラブ後方サンプリングに拡張し、$sigma = O(frac1k)$が有界である場合にも同様の保証を達成する。
• 参考スコア（独自算出の注目度）: 11.458504242206862
• License:
• Abstract: Posterior sampling with the spike-and-slab prior [MB88], a popular multimodal distribution used to model uncertainty in variable selection, is considered the theoretical gold standard method for Bayesian sparse linear regression [CPS09, Roc18]. However, designing provable algorithms for performing this sampling task is notoriously challenging. Existing posterior samplers for Bayesian sparse variable selection tasks either require strong assumptions about the signal-to-noise ratio (SNR) [YWJ16], only work when the measurement count grows at least linearly in the dimension [MW24], or rely on heuristic approximations to the posterior. We give the first provable algorithms for spike-and-slab posterior sampling that apply for any SNR, and use a measurement count sublinear in the problem dimension. Concretely, assume we are given a measurement matrix $\mathbf{X} \in \mathbb{R}^{n\times d}$ and noisy observations $\mathbf{y} = \mathbf{X}\mathbf{\theta}^\star + \mathbf{\xi}$ of a signal $\mathbf{\theta}^\star$ drawn from a spike-and-slab prior $\pi$ with a Gaussian diffuse density and expected sparsity k, where $\mathbf{\xi} \sim \mathcal{N}(\mathbb{0}_n, \sigma^2\mathbf{I}_n)$. We give a polynomial-time high-accuracy sampler for the posterior $\pi(\cdot \mid \mathbf{X}, \mathbf{y})$, for any SNR $\sigma^{-1}$ > 0, as long as $n \geq k^3 \cdot \text{polylog}(d)$ and $X$ is drawn from a matrix ensemble satisfying the restricted isometry property. We further give a sampler that runs in near-linear time $\approx nd$ in the same setting, as long as $n \geq k^5 \cdot \text{polylog}(d)$. To demonstrate the flexibility of our framework, we extend our result to spike-and-slab posterior sampling with Laplace diffuse densities, achieving similar guarantees when $\sigma = O(\frac{1}{k})$ is bounded.
• Abstract（参考訳）: 可変選択の不確かさをモデル化するために用いられる多モード分布であるスパイク・アンド・スラブ前駆体[MB88]を用いた後部サンプリングは,ベイズ・スパース線形回帰(CPS09,Roc18]の理論的金標準法であると考えられる。 しかし、このサンプリングタスクを実行するための証明可能なアルゴリズムを設計することは、非常に難しい。 既存のベイジアンスパース変分法タスクの後方サンプリングは、信号-雑音比(SNR) [YWJ16] に関する強い仮定を必要とするか、測定数が[MW24] において少なくとも直線的に増加するときのみ機能するか、または後部へのヒューリスティック近似に依存するかのいずれかである。 我々は,任意のSNRに適用可能なスパイク・アンド・スラブ後続サンプリングのための最初の証明可能なアルゴリズムを提案し,問題次元における測定数サブリニアを使用する。 具体的には、測度行列 $\mathbf{X} \in \mathbb{R}^{n\times d}$ とノイズ観測 $\mathbf{y} = \mathbf{X}\mathbf{\theta}^\star + \mathbf{\xi}$ の信号 $\mathbf{\theta}^\star$ がガウス微分密度と期待間隔 k から引き出され、そこで $\mathbf{\xi} \sim \mathcal{N}(\mathbb{0}_n, \sigma^2\mathbf{I}_n)$ が与えられる。 我々は、任意の SNR $\sigma^{-1}$ > 0 に対して、後続の $\pi(\cdot \mid \mathbf{X}, \mathbf{y})$ に対して多項式時間高精度サンプリングを与える。 さらに、$n \geq k^5 \cdot \text{polylog}(d)$と同じ設定で、ほぼ直線時間で$\approx nd$を走らせるサンプルを提供する。 フレームワークの柔軟性を示すために、我々は結果をラプラス拡散密度でスパイク・アンド・スラブの後方サンプリングに拡張し、$\sigma = O(\frac{1}{k})$が有界である場合にも同様の保証を達成する。

関連論文リスト

• Outsourced diffusion sampling: Efficient posterior inference in latent spaces of generative models [65.71506381302815]
  本稿では、$p(mathbfxmidmathbfy) propto p_theta(mathbfx)$ という形式の後続分布からサンプリングするコストを償却する。 多くのモデルと関心の制約に対して、ノイズ空間の後方はデータ空間の後方よりも滑らかであり、そのような償却推論に対してより快適である。
  論文  参考訳（メタデータ） (2025-02-10T19:49:54Z)
• Robust Scatter Matrix Estimation for Elliptical Distributions in Polynomial Time [2.311583680973075]
  我々はフロベニウスノルムで次元非依存誤差を実現する時間アルゴリズムを設計する。 散乱行列 $Sigma$, for every $t in mathbbN$, we design an estimator that, given $n = dO(t)$ sample, in time $nO(t)$ finds $hatSigma。
  論文  参考訳（メタデータ） (2025-02-10T15:31:57Z)
• Variable Selection in Convex Piecewise Linear Regression [5.366354612549172]
  本稿では,凸片方向線形回帰における変数選択の解としてスパース勾配を提案する。 亜ガウス雑音下でのSpGDには非漸近局所収束解析が提供される。
  論文  参考訳（メタデータ） (2024-11-04T16:19:09Z)
• Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
  以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。 本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-11-01T17:59:53Z)
• Provably learning a multi-head attention layer [55.2904547651831]
  マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。 本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。 最悪の場合、$m$に対する指数的依存は避けられないことを示す。
  論文  参考訳（メタデータ） (2024-02-06T15:39:09Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。 本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。 また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
  論文  参考訳（メタデータ） (2023-09-25T17:54:19Z)
• Beyond Independent Measurements: General Compressed Sensing with GNN Application [4.924126492174801]
  我々は、ノイズコーン観測からmathbbRn$の構造化信号$mathbfxを復元する問題を考察する。 実効的な$mathbfB$は測定値のサロゲートとして用いられる可能性がある。
  論文  参考訳（メタデータ） (2021-10-30T20:35:56Z)
• Random matrices in service of ML footprint: ternary random features with no performance loss [55.30329197651178]
  我々は、$bf K$ の固有スペクトルが$bf w$ の i.d. 成分の分布とは独立であることを示す。 3次ランダム特徴(TRF)と呼ばれる新しいランダム手法を提案する。 提案したランダムな特徴の計算には乗算が不要であり、古典的なランダムな特徴に比べてストレージに$b$のコストがかかる。
  論文  参考訳（メタデータ） (2021-10-05T09:33:49Z)
• Non-Parametric Estimation of Manifolds from Noisy Data [1.0152838128195467]
  ノイズの多いサンプルの有限集合から$mathbbRD$の$d$次元部分多様体を推定する問題を検討する。 点推定では$n-frack2k + d$、接空間の推定では$n-frack-12k + d$の収束率を推定する。
  論文  参考訳（メタデータ） (2021-05-11T02:29:33Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。 i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  論文  参考訳（メタデータ） (2020-07-16T06:44:44Z)
• Efficient Statistics for Sparse Graphical Models from Truncated Samples [19.205541380535397]
  i) スパースガウス図形モデルの推論と (ii) スパース線形モデルの回復支援の2つの基本的問題と古典的問題に焦点をあてる。 疎線型回帰については、$(bf x,y)$ が生成されるが、$y = bf xtopOmega* + MathcalN(0,1)$ と $(bf x, y)$ は、truncation set $S subseteq mathbbRd$ に属する場合にのみ見られる。
  論文  参考訳（メタデータ） (2020-06-17T09:21:00Z)

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

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