論文の概要: Gaussian Cooling and Dikin Walks: The Interior-Point Method for Logconcave Sampling
- arxiv url: http://arxiv.org/abs/2307.12943v4
- Date: Thu, 21 Mar 2024 20:59:59 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-25 23:29:06.835718
- Title: Gaussian Cooling and Dikin Walks: The Interior-Point Method for Logconcave Sampling
- Title（参考訳）: ガウス冷却とダイキンウォーク:ログコンケーブサンプリングにおける内部点法
- Authors: Yunbum Kook, Santosh S. Vempala,
- Abstract要約: 1990年代、ネスターとネミロフスキーは自己調和障壁に基づく凸最適化のための内部点法(IPM)を開発した。
2012年、カナンとナラヤナンはポリトープを一様にサンプリングするダイキンウォークを提案した。
本稿では、多時間サンプリングアルゴリズムのためのダイキンウォークと共にIPM機械を開発し、適応させることにより、このアプローチを一般化する。
- 参考スコア（独自算出の注目度）: 8.655526882770742
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The connections between (convex) optimization and (logconcave) sampling have been considerably enriched in the past decade with many conceptual and mathematical analogies. For instance, the Langevin algorithm can be viewed as a sampling analogue of gradient descent and has condition-number-dependent guarantees on its performance. In the early 1990s, Nesterov and Nemirovski developed the Interior-Point Method (IPM) for convex optimization based on self-concordant barriers, providing efficient algorithms for structured convex optimization, often faster than the general method. This raises the following question: can we develop an analogous IPM for structured sampling problems? In 2012, Kannan and Narayanan proposed the Dikin walk for uniformly sampling polytopes, and an improved analysis was given in 2020 by Laddha-Lee-Vempala. The Dikin walk uses a local metric defined by a self-concordant barrier for linear constraints. Here we generalize this approach by developing and adapting IPM machinery together with the Dikin walk for poly-time sampling algorithms. Our IPM-based sampling framework provides an efficient warm start and goes beyond uniform distributions and linear constraints. We illustrate the approach on important special cases, in particular giving the fastest algorithms to sample uniform, exponential, or Gaussian distributions on a truncated PSD cone. The framework is general and can be applied to other sampling algorithms.
- Abstract（参考訳）: 凸)最適化と(対数)サンプリングのつながりは、過去10年間に多くの概念的および数学的類似によってかなり豊かになった。
例えば、ランゲヴィンアルゴリズムは勾配降下のサンプリングアナログと見なすことができ、その性能に条件数に依存した保証を持つ。
1990年代初頭、ネステロフとネミロフスキーは自己一致障壁に基づく凸最適化のための内部点法(IPM)を開発し、一般的な方法よりも高速な構造凸最適化のための効率的なアルゴリズムを提供した。
これは、構造化サンプリング問題に類似したIMMを開発することができるかという疑問を提起する。
2012年、カナンとナラヤナンはポリトープを均一に採取するためのダイキンウォークを提案し、2020年にはラッダ=リー=ベンパラによって分析が改良された。
ダイキン・ウォークは、線形制約に対する自己調和障壁によって定義される局所計量を使用する。
本稿では、多時間サンプリングアルゴリズムのためのダイキンウォークと共にIPM機械を開発し、適応させることにより、このアプローチを一般化する。
我々のIPMベースのサンプリングフレームワークは、効率的なウォームスタートを提供し、均一な分布と線形制約を越えています。
特に,不規則なPSDコーン上の一様分布,指数分布,ガウス分布のサンプリングに最も高速なアルゴリズムを与える。
このフレームワークは一般的なもので、他のサンプリングアルゴリズムにも適用できる。
関連論文リスト
- Harmonic Path Integral Diffusion [0.4527270266697462]
本稿では,連続多変量確率分布から抽出する新しい手法を提案する。
本手法では,状態空間の起点を中心とするデルタ関数を$t=0$とし,ターゲット分布に$t=1$で変換する。
これらのアルゴリズムは他のサンプリング手法、特にシミュレートおよびパス積分サンプリングと対比し、解析制御、精度、計算効率の点でそれらの利点を強調した。
論文 参考訳（メタデータ） (2024-09-23T16:20:21Z) - Faster Sampling via Stochastic Gradient Proximal Sampler [28.422547264326468]
非log-concave分布からのサンプリングのための近位サンプリング器 (SPS) について検討した。
対象分布への収束性は,アルゴリズムの軌道が有界である限り保証可能であることを示す。
我々は、Langevin dynamics(SGLD)とLangevin-MALAの2つの実装可能な変種を提供し、SPS-SGLDとSPS-MALAを生み出した。
論文 参考訳（メタデータ） (2024-05-27T00:53:18Z) - Differentially Private Optimization with Sparse Gradients [60.853074897282625]
微分プライベート(DP)最適化問題を個人勾配の空間性の下で検討する。
これに基づいて、スパース勾配の凸最適化にほぼ最適な速度で純粋および近似DPアルゴリズムを得る。
論文 参考訳（メタデータ） (2024-04-16T20:01:10Z) - Distributed Markov Chain Monte Carlo Sampling based on the Alternating
Direction Method of Multipliers [143.6249073384419]
本論文では,乗算器の交互方向法に基づく分散サンプリング手法を提案する。
我々は,アルゴリズムの収束に関する理論的保証と,その最先端性に関する実験的証拠の両方を提供する。
シミュレーションでは,線形回帰タスクとロジスティック回帰タスクにアルゴリズムを配置し,その高速収束を既存の勾配法と比較した。
論文 参考訳（メタデータ） (2024-01-29T02:08:40Z) - Plug-and-Play split Gibbs sampler: embedding deep generative priors in
Bayesian inference [12.91637880428221]
本稿では, 後方分布から効率的にサンプリングするために, 可変分割を利用したプラグアンドプレイサンプリングアルゴリズムを提案する。
後方サンプリングの課題を2つの単純なサンプリング問題に分割する。
その性能は最近の最先端の最適化とサンプリング手法と比較される。
論文 参考訳（メタデータ） (2023-04-21T17:17:51Z) - Resolving the Mixing Time of the Langevin Algorithm to its Stationary
Distribution for Log-Concave Sampling [34.66940399825547]
本稿では,Langevinアルゴリズムの定常分布に対する混合時間の特徴について述べる。
本稿では,差分プライバシー文献からサンプリング文献へのアプローチを紹介する。
論文 参考訳（メタデータ） (2022-10-16T05:11:16Z) - A Proximal Algorithm for Sampling from Non-smooth Potentials [10.980294435643398]
非滑らかなポテンシャルからのサンプリングのための新しいMCMCアルゴリズムを提案する。
本手法は, 近似バンドル法と交互サンプリングフレームワークに基づく。
この研究の重要な貢献は、任意の凸非滑らかポテンシャルに対して制限されたガウスオラクルを実現する高速アルゴリズムである。
論文 参考訳（メタデータ） (2021-10-09T15:26:07Z) - Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box
Optimization Framework [100.36569795440889]
この作業は、一階情報を必要としない零次最適化(ZO)の反復である。
座標重要度サンプリングにおける優雅な設計により,ZO最適化法は複雑度と関数クエリコストの両面において効率的であることを示す。
論文 参考訳（メタデータ） (2020-12-21T17:29:58Z) - Pathwise Conditioning of Gaussian Processes [72.61885354624604]
ガウス過程後部をシミュレーションするための従来のアプローチでは、有限個の入力位置のプロセス値の限界分布からサンプルを抽出する。
この分布中心の特徴づけは、所望のランダムベクトルのサイズで3次スケールする生成戦略をもたらす。
条件付けのこのパスワイズ解釈が、ガウス過程の後部を効率的にサンプリングするのに役立てる近似の一般族をいかに生み出すかを示す。
論文 参考訳（メタデータ） (2020-11-08T17:09:37Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳（メタデータ） (2020-09-28T15:22:24Z) - Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。
我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。
得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
論文 参考訳（メタデータ） (2020-02-21T17:45:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。