論文の概要: A Proximal Algorithm for Sampling from Non-convex Potentials
- arxiv url: http://arxiv.org/abs/2205.10188v1
- Date: Fri, 20 May 2022 13:58:46 GMT
- ステータス: 処理完了
- システム内更新日: 2022-05-23 20:24:22.817089
- Title: A Proximal Algorithm for Sampling from Non-convex Potentials
- Title（参考訳）: 非凸電位からのサンプリングのための近似アルゴリズム
- Authors: Jiaming Liang, Yongxin Chen
- Abstract要約: 滑らかさに欠ける非滑らかなポテンシャルの問題を考察する。
滑らかではなく、ポテンシャルは半滑らかあるいは多重多重滑らか関数であると仮定される。
我々は、交互サンプリングフレームワークとして知られるGibbsサンプリングの特殊なケースを開発する。
- 参考スコア（独自算出の注目度）: 14.909442791255042
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study sampling problems associated with non-convex potentials that
meanwhile lack smoothness. In particular, we consider target distributions that
satisfy either logarithmic-Sobolev inequality or Poincar\'e inequality. Rather
than smooth, the potentials are assumed to be semi-smooth or the summation of
multiple semi-smooth functions. We develop a sampling algorithm that resembles
proximal algorithms in optimization for this challenging sampling task. Our
algorithm is based on a special case of Gibbs sampling known as the alternating
sampling framework (ASF). The key contribution of this work is a practical
realization of the ASF based on rejection sampling in the non-convex and
semi-smooth setting. This work extends the recent algorithm in
\cite{LiaChe21,LiaChe22} for non-smooth/semi-smooth log-concave distribution to
the setting with non-convex potentials. In almost all the cases of sampling
considered in this work, our proximal sampling algorithm achieves better
complexity than all existing methods.
- Abstract（参考訳）: 滑らかさに欠ける非凸電位に関するサンプリング問題について検討した。
特に,対数-ソボレフの不等式を満足する対象分布について考察する。
滑らかではなく、ポテンシャルは半滑らかあるいは多重半滑らか関数の和であると仮定される。
我々は,この難解なサンプリングタスクの最適化において,近位アルゴリズムに類似したサンプリングアルゴリズムを開発した。
本アルゴリズムは,交代サンプリングフレームワーク (asf) として知られるギブスサンプリングの特別な場合に基づいている。
本研究の重要な貢献は,非凸および半スムース設定における拒絶サンプリングに基づくasfの実践的実現である。
この研究は、非スムース/半スムース対凸分布に対する最近のアルゴリズムを、非凸ポテンシャルを持つ集合へと拡張する。
この研究で考慮されたサンプリングのほとんど全てのケースにおいて、我々の近位サンプリングアルゴリズムは、既存の全ての方法よりもより良い複雑さを達成する。
関連論文リスト
- A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。
提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
論文 参考訳（メタデータ） (2024-09-07T06:37:23Z) - Proximal Oracles for Optimization and Sampling [18.77973093341588]
非滑らかな目的関数による凸最適化と非滑らかなポテンシャルによる対数凹型サンプリングについて検討する。
非滑らか性による課題を克服するため、アルゴリズムは最適化とサンプリングに2つの強力な近位フレームワークを用いる。
論文 参考訳（メタデータ） (2024-04-02T18:52:28Z) - Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and
Optimal Algorithms [64.10576998630981]
最適なヘッセン依存型サンプルの複雑さを, 初めて厳密に評価した。
ヘシアン非依存のアルゴリズムは、すべてのヘシアンインスタンスに対して最適なサンプル複雑さを普遍的に達成する。
本アルゴリズムにより得られたサンプルの最適複雑さは,重み付き雑音分布においても有効である。
論文 参考訳（メタデータ） (2023-06-21T17:03:22Z) - PAPAL: A Provable PArticle-based Primal-Dual ALgorithm for Mixed Nash Equilibrium [58.26573117273626]
2プレイヤゼロサム連続ゲームにおける非AL平衡非漸近目的関数について考察する。
連続分布戦略のための粒子ベースアルゴリズムに関する新しい知見を述べる。
論文 参考訳（メタデータ） (2023-03-02T05:08:15Z) - Improved dimension dependence of a proximal algorithm for sampling [16.147290924171692]
そこで本研究では,すべての古典的設定において,より優れた複雑性境界を実現するサンプリングアルゴリズムを提案する。
提案アルゴリズムは,2021年に導入した近位サンプルを用いた。
強い対数対数分布の場合、この手法は温度開始を伴わずに$tildemathcalO(kappa d1/2)$の複雑さを持つ。
LSI を満たす分布に対して、我々は $tilde MathcalO(hat kappa d1/2)$ ここで $hat kappa$ は滑らかさと滑らかさの比である。
論文 参考訳（メタデータ） (2023-02-20T16:44:48Z) - A Proximal Algorithm for Sampling [14.909442791255042]
我々は、滑らかさに欠けるポテンシャルに関連する問題を研究する。
ポテンシャルは凸か非滑らかである。
本アルゴリズムは, 拒絶サンプリングの特殊な事例に基づく。
論文 参考訳（メタデータ） (2022-02-28T17:26:09Z) - A Proximal Algorithm for Sampling from Non-smooth Potentials [10.980294435643398]
非滑らかなポテンシャルからのサンプリングのための新しいMCMCアルゴリズムを提案する。
本手法は, 近似バンドル法と交互サンプリングフレームワークに基づく。
この研究の重要な貢献は、任意の凸非滑らかポテンシャルに対して制限されたガウスオラクルを実現する高速アルゴリズムである。
論文 参考訳（メタデータ） (2021-10-09T15:26:07Z) - High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。
非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。
そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
論文 参考訳（メタデータ） (2021-06-10T17:54:21Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳（メタデータ） (2020-09-28T15:22:24Z) - Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
オンラインデータストリームによって生成される有限個の点からなるランダムな確率測度に対する人口推定バリセンタ問題を考察する。
本稿では,この問題の構造を用いて,凸凹型サドル点再構成を行う。
ランダム確率測度の分布が離散的な場合、最適化アルゴリズムを提案し、その複雑性を推定する。
論文 参考訳（メタデータ） (2020-06-11T19:40:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。