論文の概要: Complexity of Markov Chain Monte Carlo for Generalized Linear Models

• arxiv url: http://arxiv.org/abs/2512.12748v1
• Date: Sun, 14 Dec 2025 16:04:27 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-12-16 17:54:56.41578
• Title: Complexity of Markov Chain Monte Carlo for Generalized Linear Models
• Title（参考訳）: 一般化線形モデルに対するマルコフ連鎖モンテカルロの複素性
• Authors: Martin Chak, Giacomo Zanella,
• Abstract要約: 我々は、$ngtrsim d$に対して、MCMCは$n$、$d$を1次最適化アルゴリズムと同様に、サブポリノミカル因子まで、同じ複雑さのスケーリングを実現することを示した。 我々の複雑さは、学生=t$や平坦な事前を含む必ずしもガウス的ではない適切にスケールされた先行に適用される。
• 参考スコア（独自算出の注目度）: 1.4466802614938334
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Markov Chain Monte Carlo (MCMC), Laplace approximation (LA) and variational inference (VI) methods are popular approaches to Bayesian inference, each with trade-offs between computational cost and accuracy. However, a theoretical understanding of these differences is missing, particularly when both the sample size $n$ and the dimension $d$ are large. LA and Gaussian VI are justified by Bernstein-von Mises (BvM) theorems, and recent work has derived the characteristic condition $n\gg d^2$ for their validity, improving over the condition $n\gg d^3$. In this paper, we show for linear, logistic and Poisson regression that for $n\gtrsim d$, MCMC attains the same complexity scaling in $n$, $d$ as first-order optimization algorithms, up to sub-polynomial factors. Thus MCMC is competitive with LA and Gaussian VI in complexity, under a scaling between $n$ and $d$ more general than BvM regimes. Our complexities apply to appropriately scaled priors that are not necessarily Gaussian-tailed, including Student-$t$ and flat priors, with log-posteriors that are not necessarily globally concave or gradient-Lipschitz.
• Abstract（参考訳）: マルコフ・チェイン・モンテカルロ(MCMC)、ラプラス近似(LA)、変分推論(VI)手法は、それぞれ計算コストと精度のトレードオフを持つベイズ推論に対する一般的なアプローチである。 しかし、これらの違いに関する理論的理解が欠落しており、特にサンプルサイズ$n$と次元$d$の両方が大きい場合である。 LA と Gaussian VI はベルンシュタイン=ヴォン・ミーゼス(英語版)(BvM)の定理によって正当化され、最近の研究は、その妥当性のために特性条件 $n\gg d^2$ を導出し、条件 $n\gg d^3$ を改良した。 本稿では, 線形, ロジスティック, ポアソン回帰について, MCMCが$n$, $d$を1次最適化アルゴリズムとして, あるいはサブポリノミカル因子まで, 同じ複雑性のスケーリングを実現することを示す。 したがって、MCMCは、BvMレギュレータよりもより一般的な$n$から$d$のスケーリングの下で、複雑性においてLAやガウスVIと競合する。 我々の複雑さは、学生=t$や平坦な事前を含む必ずしもガウス的ではない適切にスケールされた先行に応用され、必ずしも大域的な凹凸や勾配リプシッツではない対数ポストが適用される。

関連論文リスト

• Efficient reductions from a Gaussian source with applications to statistical-computational tradeoffs [8.162867143465382]
  我々はこの手法を利用して、平均ケースの複雑さにおいて広く信じられている予想の下で、いくつかの正準高次元統計モデルに対して、還元に基づく計算下界を確立する。 ガウス雑音を持つスパイクテンソルPCAの計算下界は、クラス内の他のガウス雑音分布にまで拡張可能であることを示す。
  論文  参考訳（メタデータ） (2025-10-08T17:16:36Z)
• Provable Benefit of Annealed Langevin Monte Carlo for Non-log-concave Sampling [28.931489333515618]
  簡単なアンニール型Langevin Monte Carloアルゴリズムに対して$widetildeOleft(fracdbeta2cal A2varepsilon6right)のオラクル複雑性を確立する。 例えば、$cal A$ は対象分布 $pi$ と容易にサンプリング可能な分布を補間する確率測度の曲線の作用を表す。
  論文  参考訳（メタデータ） (2024-07-24T02:15:48Z)
• 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)
• Tempered Calculus for ML: Application to Hyperbolic Model Embedding [70.61101116794549]
  MLで使用されるほとんどの数学的歪みは、本質的に自然界において積分的である。 本稿では,これらの歪みを改善するための基礎的理論とツールを公表し,機械学習の要件に対処する。 我々は、最近MLで注目を集めた問題、すなわち、ハイパーボリック埋め込みを「チープ」で正確なエンコーディングで適用する方法を示す。
  論文  参考訳（メタデータ） (2024-02-06T17:21:06Z)
• Variational inference via Wasserstein gradient flows [10.039378223592013]
  変分推論 (VI) は大規模ベイズ推論における中心的な計算手法として登場した。 我々は、$hat pi$ をガウスあるいはガウスの混合体とする VI の原理的手法を提案する。
  論文  参考訳（メタデータ） (2022-05-31T15:53:15Z)
• Learning Gaussian Mixtures with Generalised Linear Models: Precise Asymptotics in High-dimensions [79.35722941720734]
  多クラス分類問題に対する一般化線形モデルは、現代の機械学習タスクの基本的な構成要素の1つである。 実験的リスク最小化による高次元推定器の精度を実証する。 合成データの範囲を超えて我々の理論をどのように適用できるかを論じる。
  論文  参考訳（メタデータ） (2021-06-07T16:53:56Z)
• Convergence of Langevin Monte Carlo in Chi-Squared and Renyi Divergence [8.873449722727026]
  推定値である$widetildemathcalO(depsilon-1)$が,これらの測定値の既知レートを改善することを示す。 特に凸および1次滑らかなポテンシャルについて、LCCアルゴリズムは、これらの測定値の既知率を改善するために$widetildemathcalO(depsilon-1)$を推定する。
  論文  参考訳（メタデータ） (2020-07-22T18:18:28Z)
• 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)

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

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