論文の概要: Faster logconcave sampling from a cold start in high dimension
- arxiv url: http://arxiv.org/abs/2505.01937v1
- Date: Sat, 03 May 2025 22:14:04 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-05-06 18:49:35.33955
- Title: Faster logconcave sampling from a cold start in high dimension
- Title（参考訳）: 高次元冷間開始点からの高速ロジコンケーブサンプリング
- Authors: Yunbum Kook, Santosh S. Vempala,
- Abstract要約: 評価オラクルによって指定された任意の対数凹密度をサンプリングするウォームスタートを高速に生成するアルゴリズムを提案する。
それまでの長い作業のラインは、少なくとも1次元の線形の温かいスタートのペナルティを招き、立方体の障壁を打った。
- 参考スコア（独自算出の注目度）: 8.655526882770742
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We present a faster algorithm to generate a warm start for sampling an arbitrary logconcave density specified by an evaluation oracle, leading to the first sub-cubic sampling algorithms for inputs in (near-)isotropic position. A long line of prior work incurred a warm-start penalty of at least linear in the dimension, hitting a cubic barrier, even for the special case of uniform sampling from convex bodies. Our improvement relies on two key ingredients of independent interest. (1) We show how to sample given a warm start in weaker notions of distance, in particular $q$-R\'enyi divergence for $q=\widetilde{\mathcal{O}}(1)$, whereas previous analyses required stringent $\infty$-R\'enyi divergence (with the exception of Hit-and-Run, whose known mixing time is higher). This marks the first improvement in the required warmness since Lov\'asz and Simonovits (1991). (2) We refine and generalize the log-Sobolev inequality of Lee and Vempala (2018), originally established for isotropic logconcave distributions in terms of the diameter of the support, to logconcave distributions in terms of a geometric average of the support diameter and the largest eigenvalue of the covariance matrix.
- Abstract（参考訳）: 評価オラクルによって指定された任意の対数凹密度をサンプリングするウォームスタートを高速に生成するアルゴリズムを提案する。
先行研究の長い行は、凸体から一様サンプリングを行う特別な場合であっても、少なくとも1次元に線形な温度開始刑を課し、立方体バリアを打った。
我々の改善は2つの重要な利害関係の要素に依存している。
1) 距離の弱い概念、特に$q=\widetilde{\mathcal{O}}(1)$に対する$q$-R\'enyiの発散を、以前の分析では$\infty$-R\'enyiの発散を必要とする(既知の混合時間が高いHit-and-Runを除いて)。
これはLov\'asz and Simonovits (1991)以来、必要な暖かさを初めて改善したことを意味する。
2)Lee and Vempala (2018) の対数ソボレフ不等式は,元来,支持径の等方性対数凹分布として確立され,支持径の幾何平均と共分散行列の最大固有値で対数凹分布として一般化された。
関連論文リスト
- High-accuracy sampling from constrained spaces with the Metropolis-adjusted Preconditioned Langevin Algorithm [12.405427902037971]
本稿では,$mathbbRd$の適切な凸部分集合である対象分布から近似サンプリングを行う1次サンプリング法を提案する。
提案手法は,事前条件付きLangevinアルゴリズムの単一ステップで生成したマルコフ連鎖にメトロポリス・ハスティングスフィルタを適用した結果である。
論文 参考訳（メタデータ） (2024-12-24T23:21:23Z) - Bayesian Circular Regression with von Mises Quasi-Processes [57.88921637944379]
本研究では、円値ランダム関数上の表現的および解釈可能な分布の族を探索する。
後部推論のために,高速ギブズサンプリングに寄与するストラトノビッチ様拡張法を導入する。
本研究では,このモデルを用いて風向予測と走行歩行周期のパーセンテージを関節角度の関数として適用する実験を行った。
論文 参考訳（メタデータ） (2024-06-19T01:57:21Z) - Faster Diffusion Sampling with Randomized Midpoints: Sequential and Parallel [10.840582511203024]
我々のアルゴリズムは、$widetilde O(log2 d)$ parallel roundsでのみ実行できるように並列化可能であることを示す。
また、我々のアルゴリズムは、$widetilde O(log2 d)$ parallel roundsでしか実行できないことを示す。
論文 参考訳（メタデータ） (2024-06-03T01:34:34Z) - Symmetric Mean-field Langevin Dynamics for Distributional Minimax
Problems [78.96969465641024]
平均場ランゲヴィンのダイナミクスを、対称で証明可能な収束した更新で、初めて確率分布に対する最小の最適化に拡張する。
また,時間と粒子の離散化機構について検討し,カオス結果の新たな均一時間伝播を証明した。
論文 参考訳（メタデータ） (2023-12-02T13:01:29Z) - Faster high-accuracy log-concave sampling via algorithmic warm starts [6.117084972237769]
実際には、古典的なメトロポリス調整ランゲヴィンアルゴリズム(MALA)のような高精度なサンプリング器は事実上のゴールド標準のままである。
我々は,このサンプリング問題の次元依存性を$tildeO(d1/2)$に改善し,MALAでは$tildeO(d1/2)$とした。
我々の主な技術的貢献は、離散化アンダーダム化ランゲヴィン拡散に対する最初の$tildeO(d1/2)$ R'enyi混合速度を確立することでこの問題を解決することである。
論文 参考訳（メタデータ） (2023-02-20T19:27:21Z) - Mean-Square Analysis with An Application to Optimal Dimension Dependence
of Langevin Monte Carlo [60.785586069299356]
この研究は、2-ワッサーシュタイン距離におけるサンプリング誤差の非同相解析のための一般的な枠組みを提供する。
我々の理論解析は数値実験によってさらに検証される。
論文 参考訳（メタデータ） (2021-09-08T18:00:05Z) - Instance-Optimal Compressed Sensing via Posterior Sampling [101.43899352984774]
後部サンプリング推定器がほぼ最適回復保証を達成できることを示す。
本稿では,Langevin dynamics を用いた深部生成前駆体の後方サンプリング推定器を実装し,MAP よりも精度の高い推定値が得られることを実証的に見出した。
論文 参考訳（メタデータ） (2021-06-21T22:51:56Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。