論文の概要: Sampling with Barriers: Faster Mixing via Lewis Weights
- arxiv url: http://arxiv.org/abs/2303.00480v2
- Date: Wed, 19 Apr 2023 04:38:02 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-20 17:11:17.274837
- Title: Sampling with Barriers: Faster Mixing via Lewis Weights
- Title（参考訳）: バリアによるサンプリング:Lewis Weightsによる高速混合
- Authors: Khashayar Gatmiry, Jonathan Kelner, Santosh S. Vempala
- Abstract要約: 凸障壁関数のヘシアンによって定義される計量により、$Rn$の$m$不等式で定義されるポリトープを解析する。
RHMCのボールウォーク、ヒット・アンド・ラン、ダイキンウォークといったユークリッド法に対する利点は、より長いステップを踏む能力にある。
- 参考スコア（独自算出の注目度）: 8.701566919381223
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We analyze Riemannian Hamiltonian Monte Carlo (RHMC) for sampling a polytope
defined by $m$ inequalities in $\R^n$ endowed with the metric defined by the
Hessian of a convex barrier function. The advantage of RHMC over Euclidean
methods such as the ball walk, hit-and-run and the Dikin walk is in its ability
to take longer steps. However, in all previous work, the mixing rate has a
linear dependence on the number of inequalities. We introduce a hybrid of the
Lewis weights barrier and the standard logarithmic barrier and prove that the
mixing rate for the corresponding RHMC is bounded by $\tilde
O(m^{1/3}n^{4/3})$, improving on the previous best bound of $\tilde
O(mn^{2/3})$ (based on the log barrier). This continues the general parallels
between optimization and sampling, with the latter typically leading to new
tools and more refined analysis. To prove our main results, we have to
overcomes several challenges relating to the smoothness of Hamiltonian curves
and the self-concordance properties of the barrier. In the process, we give a
general framework for the analysis of Markov chains on Riemannian manifolds,
derive new smoothness bounds on Hamiltonian curves, a central topic of
comparison geometry, and extend self-concordance to the infinity norm, which
gives sharper bounds; these properties appear to be of independent interest.
- Abstract（参考訳）: リーマンハミルトニアンモンテカルロ (rhmc) を解析し, 凸障壁関数のヘッシアンによって定義される計量で与えられる$\r^n$ における m$ 不等式で定義されるポリトープをサンプリングする。
RHMCのボールウォーク、ヒット・アンド・ラン、ダイキンウォークといったユークリッド法に対する利点は、より長いステップを踏む能力にある。
しかし、全ての研究において、混合速度は不等式の数に線形依存している。
ルイス重み障壁と標準対数障壁のハイブリッドを導入することにより、対応するrhmcの混合速度が$\tilde o(m^{1/3}n^{4/3})$となることを証明し、以前の最高値である$\tilde o(mn^{2/3})$(対数障壁に基づく)を改良する。
これは最適化とサンプリングの一般的な並列性であり、後者は一般的に新しいツールやより洗練された分析につながる。
主な結果を証明するためには、ハミルトン曲線の滑らかさと障壁の自己調和性に関するいくつかの課題を克服する必要がある。
この過程において、リーマン多様体上のマルコフ連鎖の解析のための一般的な枠組みを与え、ハミルトン曲線上の新しい滑らかさ境界を導出し、比較幾何学の中心的なトピックを導き、無限ノルムへの自己一致を拡張し、よりシャープな境界を与える。
関連論文リスト
- Performative Reinforcement Learning with Linear Markov Decision Process [14.75815792682734]
提案手法がマルコフ決定過程の報酬と遷移の両方に影響を及ぼすような表現的強化学習の設定について検討する。
大規模MDPの主要な理論モデルであるEmphlinear Markov決定過程を一般化する。
論文 参考訳（メタデータ） (2024-11-07T23:04:48Z) - Symmetric Mean-field Langevin Dynamics for Distributional Minimax
Problems [78.96969465641024]
平均場ランゲヴィンのダイナミクスを、対称で証明可能な収束した更新で、初めて確率分布に対する最小の最適化に拡張する。
また,時間と粒子の離散化機構について検討し,カオス結果の新たな均一時間伝播を証明した。
論文 参考訳（メタデータ） (2023-12-02T13:01:29Z) - High-probability Convergence Bounds for Nonlinear Stochastic Gradient Descent Under Heavy-tailed Noise [59.25598762373543]
重み付き雑音の存在下でのストリーミングデータにおける学習の精度保証について検討した。
解析的に、与えられた問題に対する設定の選択に$ta$を使うことができることを実証する。
論文 参考訳（メタデータ） (2023-10-28T18:53:41Z) - Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
本稿では,ニューラルネットワークトレーニングを安定化(大規模)するための原理的手法として,線形アヘッドの理論解析を提案する。
最適化過程の不安定性は、しばしば損失ランドスケープの非単調性によって引き起こされるものであり、非拡張作用素の理論を活用することによって線型性がいかに役立つかを示す。
論文 参考訳（メタデータ） (2023-10-20T12:45:12Z) - Curvature-Independent Last-Iterate Convergence for Games on Riemannian
Manifolds [77.4346324549323]
本研究では, 多様体の曲率に依存しないステップサイズが, 曲率非依存かつ直線的最終点収束率を達成することを示す。
我々の知る限りでは、曲率非依存率や/または最終点収束の可能性はこれまでに検討されていない。
論文 参考訳（メタデータ） (2023-06-29T01:20:44Z) - When does Metropolized Hamiltonian Monte Carlo provably outperform
Metropolis-adjusted Langevin algorithm? [4.657614491309671]
本研究では, 磁化ハミルトン・モンテカルロ (HMC) と跳躍フロッグ積分器の混合時間について解析した。
連続HMC力学の離散化における位置と速度変数の結合分布は, ほぼ不変であることを示す。
論文 参考訳（メタデータ） (2023-04-10T17:35:57Z) - Kernel-based off-policy estimation without overlap: Instance optimality
beyond semiparametric efficiency [53.90687548731265]
本研究では,観測データに基づいて線形関数を推定するための最適手順について検討する。
任意の凸および対称函数クラス $mathcalF$ に対して、平均二乗誤差で有界な非漸近局所ミニマックスを導出する。
論文 参考訳（メタデータ） (2023-01-16T02:57:37Z) - Convergence of the Riemannian Langevin Algorithm [10.279748604797911]
計量$g$の多様体上の自然測度に関して、密度$nu$の分布からサンプリングする問題を研究する。
対数障壁によって定義されるポリトープに制限された等尺的密度をサンプリングする手法が,本手法の特例である。
論文 参考訳（メタデータ） (2022-04-22T16:56:00Z) - Comparison of Markov chains via weak Poincar\'e inequalities with
application to pseudo-marginal MCMC [0.0]
マルコフ連鎖の平衡への有界収束に対する弱ポアンカーの不等式として知られるある種の機能的不等式の使用について検討する。
本研究では, 独立メトロポリス・ハスティングス・サンプリング法や, 難易度を求める疑似マルジナル手法などの手法に対して, サブ幾何学的収束境界の導出を可能にすることを示す。
論文 参考訳（メタデータ） (2021-12-10T15:36:30Z) - Mean-Square Analysis with An Application to Optimal Dimension Dependence
of Langevin Monte Carlo [60.785586069299356]
この研究は、2-ワッサーシュタイン距離におけるサンプリング誤差の非同相解析のための一般的な枠組みを提供する。
我々の理論解析は数値実験によってさらに検証される。
論文 参考訳（メタデータ） (2021-09-08T18:00:05Z) - The Heavy-Tail Phenomenon in SGD [7.366405857677226]
最小損失のHessianの構造に依存すると、SGDの反復はエンフェビーテールの定常分布に収束する。
深層学習におけるSGDの行動に関する知見に分析結果を変換する。
論文 参考訳（メタデータ） (2020-06-08T16:43:56Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。