論文の概要: High-Magnetization Sampling at Low Temperatures: Ising Models and Bayesian Sparse Linear Regression

• arxiv url: http://arxiv.org/abs/2609.08873v1
• Date: Tue, 08 Sep 2026 15:13:03 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-10 19:44:08.684053
• Title: High-Magnetization Sampling at Low Temperatures: Ising Models and Bayesian Sparse Linear Regression
• Title（参考訳）: 低温高磁化サンプリング:イジングモデルとベイズスパース線形回帰
• Abstract要約: スパシティは最適化と統計において強力な構造資源である。 我々はハミングスライス上でのサンプリング問題における疎結合を利用したフレームワークを開発する。 我々は,任意の信号-雑音比において,任意の間隔で,標準的EmphGauss的スパイク・アンド・スラブ後部からサンプリングする方法を示す。
• 参考スコア（独自算出の注目度）: 21.42487326470028
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Sparsity is a powerful structural resource in optimization and statistics. We develop frameworks for leveraging sparsity in sampling problems over the Hamming slice $\mathcal{X}_k^d:=\{\mathbf{x}\in\{\pm 1\}^d:|\{i:\mathbf{x}_i=1\}|=k\}$, in high-dimensional regimes where $k\ll d$ (i.e., where $\mathcal{X}_k^d$ is \emph{highly magnetized}). We use our frameworks to design improved samplers for canonical problems in the study of \emph{Ising models} and \emph{Bayesian sparse linear regression}. Our first main result considers the \emph{Sherrington--Kirkpatrick} (SK) model restricted to fixed-magnetization slices $\mathcal{X}_k^d$. We give a polynomial-time sampler for fixed-magnetization SK models at any inverse temperature $β>0$, under arbitrary external fields, provided that $k\le c_βd$ for an appropriate constant $c_β$. By combining this result with an annealing strategy for estimating normalizing constants, we obtain polynomial-time samplers for the SK model at arbitrarily low temperatures under a sufficiently strong external field of strength $h$. In the large-$β$ limit, our framework permits sampling at field strengths within constant factors of the \emph{Almeida--Thouless line} delineating the replica-symmetric and replica-symmetry-breaking regions ([dAT78]), improving polynomially over the field strength $h(β)$ required by the recent work of [BAR26]. Our second main result concerns the measurement complexity of polynomial-time Bayesian sparse linear regression. Recent work by [KSTZ25] shows how to sample from the canonical \emph{Gaussian spike-and-slab posterior} with expected sparsity $k$, at any signal-to-noise ratio, given $n\gtrsim k^3\log^3 d$ Gaussian measurements. We improve this requirement to $n\gtrsim k^{3/2}\log^2 d+k\log^3 d$, using a common sparsity-aware framework underlying both our results.
• Abstract（参考訳）: スパシティは最適化と統計において強力な構造資源である。 我々は,ハミングスライス$\mathcal{X}_k^d:=\{\mathbf{x}\in\{\pm 1\}^d:|\{i:\mathbf{x}_i=1\}|=k\}$という高次元状態において,サンプリング問題のスパース性を利用するフレームワークを開発する。 本研究では, 標準問題に対する改良型サンプリング器の設計にフレームワークを用いている。 最初の結果は、固定磁化スライス$\mathcal{X}_k^d$に制限された \emph{Sherrington--Kirkpatrick} (SK) モデルを考える。 任意の外部場の下での任意の逆温度$β>0$における固定磁化SKモデルに対する多項式時間サンプリングを、適切な定数$c_β$に対して$k\le c_βd$とする。 この結果と正規化定数を推定するアニーリング戦略を組み合わせることで、SKモデルに対する多項式時間サンプリングを、強度$h$の強い外部場の下で任意に低温で得ることができる。 大規模なβ$制限では、我々のフレームワークは、[BAR26] の最近の研究で要求される場の強度$h(β)$を多項式的に改善し、レプリカ対称性およびレプリカ対称性を破る領域([dAT78])を記述した 'emph{Almeida-Thouless line} の定数要素内のフィールド強度のサンプリングを可能にする。 第2の主結果は多項式時間ベイズスパース線形回帰の測定複雑性に関するものである。 KSTZ25] による最近の研究は、任意の信号と雑音の比が$k$で標準の \emph{Gaussian spike-and-slab rear} からサンプルをサンプリングする方法を示し、$n\gtrsim k^3\log^3 d$ Gaussian の測定値が与えられた。 我々はこの要求を、両方の結果の基礎となる共通の空間認識フレームワークを用いて、$n\gtrsim k^{3/2}\log^2 d+k\log^3 d$に改善する。

関連論文リスト

• Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise [49.730496294398726]
  重み付き確率変数に対する新しい量子平均推定器を開発した。 尾指数>4/3$のより強い下界を導出し、次元への非自明な依存が避けられないことを示す。 凸目的関数に対して,量子射影勾配降下法を提案する。
  論文  参考訳（メタデータ） (2026-07-28T09:29:37Z)
• Separating Oblivious and Adaptive Models of Variable Selection [13.61388474201292]
  最適$ell_infty$誤差は、ほぼ直線時間で$gtrsim k2$サンプルで達成可能であることを示す。 本研究は,一括適応型 $ モデルの予備試験で結論付ける。
  論文  参考訳（メタデータ） (2026-02-18T16:10:35Z)
• Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination [65.37519531362157]
  このタスクに対する効率的な統計的クエリアルゴリズムは、VSTATの複雑さを少なくとも$tildeOmega(d1/2/alpha2)$で要求する。
  論文  参考訳（メタデータ） (2025-10-12T15:42:44Z)
• Spike-and-Slab Posterior Sampling in High Dimensions [11.458504242206862]
  スパイク・アンド・スラブ先行法[MB88]による後方サンプリングは,ベイズ・スパース線形回帰の理論的金標準法であると考えられる。 我々は,任意のSNRに適用可能なスパイク・アンド・スラブ後続サンプリングのための最初の証明可能なアルゴリズムを提示し,問題次元における測定カウントサブを使用する。 ラプラス拡散密度を用いたスパイク・アンド・スラブ後方サンプリングに拡張し、$sigma = O(frac1k)$が有界である場合にも同様の保証を達成する。
  論文  参考訳（メタデータ） (2025-03-04T17:16:07Z)
• Conditional regression for the Nonlinear Single-Variable Model [4.565636963872865]
  次元の統計的および計算的呪いなしで、$mathbbRd$に$F$を回帰するには、特別な統計モデルが必要である。 ここで、モデル $F(X):=f(Pi_gamma X)$ ここで $Pi_gamma:mathbbRdto[0,textrmlen_gamma]$ は正則曲線のパラメータへの最も近い点射影である。
  論文  参考訳（メタデータ） (2024-11-14T18:53:51Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。 我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。 我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
  論文  参考訳（メタデータ） (2024-05-10T09:58:47Z)
• 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)
• Penalized Overdamped and Underdamped Langevin Monte Carlo Algorithms for Constrained Sampling [17.832449046193933]
  目的が目標分布である$pi(x)prop ef(x)$から$x$が制約されたときにサンプリングする制約付きサンプリング問題を考える。 ペナルティ法によって動機付けられた制約付き問題を,制約違反に対するペナルティ関数を導入することにより,非制約サンプリング問題に変換する。 PSGLD と PSGULMC の場合、$tildemathcalO(d/varepsilon18)$ が強凸で滑らかであるとき、$tildemathcalO(d/varepsilon) を得る。
  論文  参考訳（メタデータ） (2022-11-29T18:43:22Z)
• 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)

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

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