論文の概要: Sharp dimensional analysis of midpoint methods for Langevin sampling

• arxiv url: http://arxiv.org/abs/2610.06308v1
• Date: Mon, 05 Oct 2026 13:29:57 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-09 09:21:06.992838
• Title: Sharp dimensional analysis of midpoint methods for Langevin sampling
• Title（参考訳）: ランゲヴィンサンプリングにおける中間点法のシャープ次元解析
• Abstract要約: 決定論的ヒューンは最大$widetilde O(4/3dmidpointvarepsilon-2/3)$クエリを使用し、過小評価指数は$widetilde O(5/4d1/4varepsilon-1/2)$を使用する。 これは、高次元において、決定論的離散化がランダムな離散化よりも優れていることを驚くほど示している。
• 参考スコア（独自算出の注目度）: 15.748402989364804
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study deterministic and randomized midpoint discretizations of Langevin dynamics for a target $π\propto e^{-V}$, where $0 \prec αI\preceq\nabla^2V\preceqβI$ and $κ=β/α$. To achieve $\sqrtα\,W_2\leqslant\varepsilon$, we show that deterministic Heun uses at most $\widetilde O(κ^{4/3}d^{1/3}\varepsilon^{-2/3})$ gradient queries, and underdamped exponential midpoint uses $\widetilde O(κ^{5/4}d^{1/4}\varepsilon^{-1/2})$. The proofs exploit cancellation at stationarity and smoothing using techniques from Malliavin calculus, outperforming previous upper bounds based on standard couplings. At bounded condition number, a lower bound matches the $d$ and $\varepsilon$ powers of both deterministic methods. To contrast, for the randomized midpoint methods and Poisson midpoint with at least two grid points (both overdamped and underdamped variants), a simple Gaussian calculation yields a lower bound $d^{1/3}\varepsilon^{-1/3}$ to get an $\varepsilon$-close sample despite starting at a benign initialization. This shows surprisingly that in high dimensions, deterministic discretizations can outperform their random counterparts.
• Abstract（参考訳）: 目的の$π\propto e^{-V}$に対してランゲヴィン力学の決定的およびランダムな中間点離散化について検討し、$0 \prec αI\preceq\nabla^2V\preceqβI$および$κ=β/α$とする。 $\sqrtα\,W_2\leqslant\varepsilon$ を達成するために、決定論的ハウンが少なくとも$\widetilde O(κ^{4/3}d^{1/3}\varepsilon^{-2/3})$勾配クエリを使い、過小評価指数中点が$\widetilde O(κ^{5/4}d^{1/4}\varepsilon^{-1/2})$であることを示す。 証明は定常性によるキャンセルと、マリヤヴィン計算の手法による平滑化を利用しており、標準結合に基づいて以前の上界よりも優れていた。 有界条件数では、下界はともに決定論的手法の$d$と$\varepsilon$の値と一致する。 対照的に、ランダム化された中間点法とポアソン中間点が少なくとも2つの格子点を持つ場合(過度に損傷された変種と過度に損傷された変種の両方)、単純なガウスの計算は、良心的な初期化を始めても$\varepsilon$-closeサンプルを得るために、より低い有界な$d^{1/3}\varepsilon^{-1/3}$を得る。 これは、高次元において、決定論的離散化がランダムな離散化よりも優れていることを驚くほど示している。

関連論文リスト

• Lower Bounds for Stochastic First-Order Algorithms with Variance Reduction in Nonconvex--Concave Minimax Optimization [2.834413535942792]
  非畳み込みミニマックス最適化における一階アルゴリズムの下位境界を確立する。 私たちの貢献は、分散還元を許容するゼロ境界クラスに対する下界である。 これらの結果は、凹凸と凹凸構造をまたいだ複雑さの障壁を同定する。
  論文  参考訳（メタデータ） (2026-10-01T13:24:15Z)
• A stochastic subgradient method with optimal failure exponent [1.3537117504260623]
  我々は,目標精度を超える最適差を観測する確率を最小化するアルゴリズムを設計する。 小音域では,Gsgens と van Parys (2025) の逆誤差モデルに縮退する。
  論文  参考訳（メタデータ） (2026-09-29T12:53:57Z)
• Sublinear Time Quantum Sensitivity Sampling [57.356528942341534]
  本稿では、量子感応サンプリングのための統一的なフレームワークを提案し、量子コンピューティングの利点を古典近似問題の幅広いクラスに拡張する。 我々のフレームワークは、コアセットを構築するための合理化されたアプローチを提供し、クラスタリング、回帰、低ランク近似などのアプリケーションにおいて、大幅なランタイム改善を提供します。
  論文  参考訳（メタデータ） (2025-09-20T20:18:49Z)
• Underdamped Langevin MCMC with third order convergence [1.8374319565577153]
  アンダーダム型ランゲヴィン拡散(ULD)のための新しい数値計算法を提案する。 f$の勾配とヘシアンがリプシッツ連続であるという仮定の下で、我々のアルゴリズムは2-ワッサーシュタイン誤差を$varepsilon$ in $mathcalO(sqrtd/varepsilon)$ steps とする。 これは、3次収束を持つLDDのための最初の勾配のみの方法である。
  論文  参考訳（メタデータ） (2025-08-22T16:00:01Z)
• Almost Minimax Optimal Best Arm Identification in Piecewise Stationary Linear Bandits [55.957560311008926]
  そこで本研究では,各文脈の平均値によって腕の質を計測するPSLBモデルを提案する。 PS$varepsilon$BAI$+$は、$varepsilon$-optimal armを、確率$ge 1-delta$と最小限のサンプルで識別することが保証される。
  論文  参考訳（メタデータ） (2024-10-10T06:15:42Z)
• Efficient Sampling of Stochastic Differential Equations with Positive Semi-Definite Models [91.22420505636006]
  本稿では, ドリフト関数と拡散行列を考慮し, 微分方程式からの効率的なサンプリング問題を扱う。 1/varepsilonは$m2d log (1/varepsilon)$である。 以上の結果から,真の解がより滑らかになるにつれて,どのような凸性も必要とせず,次元の呪いを回避できることが示唆された。
  論文  参考訳（メタデータ） (2023-03-30T02:50:49Z)
• ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
  本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。 我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2023-01-01T18:51:29Z)
• Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP [58.13930707612128]
  この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。 我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
  論文  参考訳（メタデータ） (2022-12-01T15:57:58Z)
• 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)

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

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