論文の概要: Regularized Dikin Walks for Sampling Truncated Logconcave Measures, Mixed Isoperimetry and Beyond Worst-Case Analysis
- arxiv url: http://arxiv.org/abs/2412.11303v1
- Date: Sun, 15 Dec 2024 20:43:51 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-17 13:59:46.621620
- Title: Regularized Dikin Walks for Sampling Truncated Logconcave Measures, Mixed Isoperimetry and Beyond Worst-Case Analysis
- Title(参考訳): サイクリングトレンシングログコンケーブ測定のための正規化ダイキンウォーク,混合アイソシリメトリおよびワーストケース解析を超えて
- Authors: Minhui Jiang, Yuansi Chen,
- Abstract要約: ポリトープ上の対流圏分布から試料を抽出する問題について検討した。
インテリアポイント法とダイキンウォークに基づいて、正規化ダイキンウォークの混合時間を分析する。
- 参考スコア(独自算出の注目度): 3.399289369740637
- License:
- Abstract: We study the problem of drawing samples from a logconcave distribution truncated on a polytope, motivated by computational challenges in Bayesian statistical models with indicator variables, such as probit regression. Building on interior point methods and the Dikin walk for sampling from uniform distributions, we analyze the mixing time of regularized Dikin walks. Our contributions are threefold. First, for a logconcave and log-smooth distribution with condition number $\kappa$, truncated on a polytope in $\mathbb{R}^n$ defined with $m$ linear constraints, we prove that the soft-threshold Dikin walk mixes in $\widetilde{O}((m+\kappa)n)$ iterations from a warm initialization. It improves upon prior work which required the polytope to be bounded and involved a bound dependent on the radius of the bounded region. Moreover, we introduce the regularized Dikin walk using Lewis weights for approximating the John ellipsoid. We show that it mixes in $\widetilde{O}((n^{2.5}+\kappa n)$. Second, we extend the mixing time guarantees mentioned above to weakly log-concave distributions truncated on polytopes, provided that they have a finite covariance matrix. Third, going beyond worst-case mixing time analysis, we demonstrate that soft-threshold Dikin walk can mix significantly faster when only a limited number of constraints intersect the high-probability mass of the distribution, improving the $\widetilde{O}((m+\kappa)n)$ upper bound to $\widetilde{O}(m + \kappa n)$. Additionally, per-iteration complexity of regularized Dikin walk and ways to generate a warm initialization are discussed to facilitate practical implementation.
- Abstract(参考訳): 確率回帰などの指標変数を持つベイズ統計モデルにおいて,ポリトープ上に散在する対数凹分布からサンプルを抽出する問題について検討した。
内部点法と一様分布からサンプリングするダイキンウォークに基づいて、正規化ダイキンウォークの混合時間を分析する。
私たちの貢献は3倍です。
まず、条件番号$\kappa$, truncated on a polytope in $\mathbb{R}^n$ defined with $m$ linear constraints, we prove that soft-threshold Dikin walk mixs in $\widetilde{O}((m+\kappa)n)$ iterations from a warm initialization。
これは、ポリトープを有界にし、有界領域の半径に依存する有界に関係させる事前の作業を改善する。
さらに、ルイス重みを用いた正規化ダイキンウォークを導入し、ジョン楕円体を近似する。
これは$\widetilde{O}((n^{2.5}+\kappa n)$で混合されることを示す。
第二に、上記の混合時間保証は、有限共分散行列を持つならば、ポリトープ上の弱対数凹分布に拡張する。
第3に,ソフトスレッショルドダイキンウォークは,分布の高確率質量に限られた制約が交わる場合に,より高速に混合できることを示し,$\widetilde{O}((m+\kappa)n)$上を$\widetilde{O}(m + \kappa n)$とする。
さらに,正規化ダイキンウォークの多点化複雑性と温かい初期化を生成する方法について考察し,実践的実装を容易にする。
関連論文リスト
- Efficiently learning and sampling multimodal distributions with data-based initialization [20.575122468674536]
静止測度から少数のサンプルを与えられたマルコフ連鎖を用いて多重モーダル分布をサンプリングする問題を考察する。
マルコフ連鎖が$k$dのスペクトルギャップを持つ場合、静止分布からのサンプルは、静止測度からテレビ距離において$varepsilon$-closeの条件法則を持つサンプルを効率よく生成する。
論文 参考訳(メタデータ) (2024-11-14T01:37:02Z) - Nearly $d$-Linear Convergence Bounds for Diffusion Models via Stochastic
Localization [40.808942894229325]
データ次元において線形である第1収束境界を提供する。
拡散モデルは任意の分布を近似するために少なくとも$tilde O(fracd log2(1/delta)varepsilon2)$ stepsを必要とすることを示す。
論文 参考訳(メタデータ) (2023-08-07T16:01:14Z) - When does Metropolized Hamiltonian Monte Carlo provably outperform
Metropolis-adjusted Langevin algorithm? [4.657614491309671]
本研究では, 磁化ハミルトン・モンテカルロ (HMC) と跳躍フロッグ積分器の混合時間について解析した。
連続HMC力学の離散化における位置と速度変数の結合分布は, ほぼ不変であることを示す。
論文 参考訳(メタデータ) (2023-04-10T17:35:57Z) - Settling the Sample Complexity of Model-Based Offline Reinforcement
Learning [50.5790774201146]
オフライン強化学習(RL)は、事前収集されたデータを用いて、さらなる探索を行わずに学習する。
事前のアルゴリズムや分析は、最適なサンプルの複雑さに悩まされるか、サンプルの最適性に到達するために高いバーンインコストがかかるかのいずれかである。
モデルベース(あるいは"プラグイン")アプローチは,バーンインコストを伴わずに,最小限のサンプル複雑性を実現することを実証する。
論文 参考訳(メタデータ) (2022-04-11T17:26:19Z) - A Law of Robustness beyond Isoperimetry [84.33752026418045]
我々は、任意の分布上でニューラルネットワークパラメータを補間する頑健性の低い$Omega(sqrtn/p)$を証明した。
次に、$n=mathrmpoly(d)$のとき、スムーズなデータに対する過度なパラメータ化の利点を示す。
我々は、$n=exp(omega(d))$ のとき、$O(1)$-Lipschitz の頑健な補間関数の存在を否定する。
論文 参考訳(メタデータ) (2022-02-23T16:10:23Z) - Wasserstein distance estimates for the distributions of numerical
approximations to ergodic stochastic differential equations [0.3553493344868413]
エルゴード微分方程式のイン分布と強い対数凸の場合の分布との間のワッサースタイン距離について検討した。
これにより、過減衰および過減衰ランジュバン力学の文献で提案されている多くの異なる近似を統一的に研究することができる。
論文 参考訳(メタデータ) (2021-04-26T07:50:04Z) - A New Framework for Variance-Reduced Hamiltonian Monte Carlo [88.84622104944503]
分散還元型ハミルトン・モンテカルロ法 (HMC) の新たなフレームワークを提案し,$L$-smooth および $m$-strongly log-concave 分布からサンプリングする。
本研究では,SAGA法やSVRG法をベースとした非バイアス勾配推定器を用いて,バッチサイズを小さくすることで,高い勾配効率が得られることを示す。
総合的および実世界のベンチマークデータによる実験結果から、我々の新しいフレームワークは、完全な勾配と勾配HMCアプローチを著しく上回っていることが示された。
論文 参考訳(メタデータ) (2021-02-09T02:44:24Z) - Learning Halfspaces with Tsybakov Noise [50.659479930171585]
テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。
真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
論文 参考訳(メタデータ) (2020-06-11T14:25:02Z) - Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and
Variance Reduction [63.41789556777387]
非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。
Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
論文 参考訳(メタデータ) (2020-06-04T17:51:00Z) - On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and
Non-Asymptotic Concentration [115.1954841020189]
The inequality and non-asymptotic properties of approximation procedure with Polyak-Ruppert averaging。
一定のステップサイズと無限大となる反復数を持つ平均的反復数に対する中心極限定理(CLT)を証明する。
論文 参考訳(メタデータ) (2020-04-09T17:54:18Z) - Logsmooth Gradient Concentration and Tighter Runtimes for Metropolized
Hamiltonian Monte Carlo [23.781520510778716]
これは1次関数情報のみを用いたログコンケーブ分布に対する最初の高精度混合時間結果である。
我々は、$kappa$への依存が標準のMetropolized firstorderメソッドであることを示す。
論文 参考訳(メタデータ) (2020-02-10T22:44:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。