論文の概要: A Proximal Algorithm for Sampling

• arxiv url: http://arxiv.org/abs/2202.13975v1
• Date: Mon, 28 Feb 2022 17:26:09 GMT
• ステータス: 処理完了
• システム内更新日: 2022-03-01 18:19:26.981524
• Title: A Proximal Algorithm for Sampling
• Title（参考訳）: サンプリングのための近似アルゴリズム
• Authors: Jiaming Liang, Yongxin Chen
• Abstract要約: 非平滑ポテンシャル(負の対数密度)によるサンプリング問題の検討 これらのサンプリングタスクの最適化手法に類似したマルコフ連鎖モンテカルロアルゴリズムを提案する。 提案アルゴリズムは,同じ設定の既存手法と比較して,最先端の複雑性境界を実現する。
• 参考スコア（独自算出の注目度）: 14.909442791255042
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider sampling problems with possibly non-smooth potentials (negative log-densities). In particular, we study two specific settings of sampling where the convex potential is either semi-smooth or in composite form as the sum of a smooth component and a semi-smooth component. To overcome the challenges caused by the non-smoothness, we propose a Markov chain Monte Carlo algorithm that resembles proximal methods in optimization for these sampling tasks. The key component of our method is a sampling scheme for a quadratically regularized target potential. This scheme relies on rejection sampling with a carefully designed Gaussian proposal whose center is an approximate minimizer of the regularized potential. We develop a novel technique (a modified Gaussian integral) to bound the complexity of this rejection sampling scheme in spite of the non-smoothness in the potentials. We then combine this scheme with the alternating sampling framework (ASF), which uses Gibbs sampling on an augmented distribution, to accomplish the two settings of sampling tasks we consider. Furthermore, by combining the complexity bound of the rejection sampling we develop and the remarkable convergence properties of ASF discovered recently, we are able to establish several non-asymptotic complexity bounds for our algorithm, in terms of the total number of queries of subgradient of the target potential. Our algorithm achieves state-of-the-art complexity bounds compared with all existing methods in the same settings.
• Abstract（参考訳）: 非スムースポテンシャル(負対数密度)を持つサンプリング問題を考える。 特に,滑らかな成分と半滑らかな成分の和として,凸電位が半滑らかか複合形状の2つの特定のサンプリング条件について検討した。 非スムースネスに起因する課題を克服するために,これらのサンプリングタスクの最適化において近位法に類似したマルコフ連鎖モンテカルロアルゴリズムを提案する。 本手法の鍵となる要素は, 4次正規化ターゲット電位のサンプリング方式である。 このスキームは、正規化ポテンシャルの近似最小値であるガウス的提案を慎重に設計した拒絶サンプリングに依存する。 我々は, ポテンシャルの非滑らかさに拘わらず, この拒絶サンプリングスキームの複雑性を制限する新しい手法(修正ガウス積分)を開発した。 次に,このスキームを拡張分布上でgibbsサンプリングを使用する交代サンプリングフレームワーク(asf)と組み合わせることで,検討した2つのサンプリングタスクの設定を実現する。 さらに、最近発見されたASFの差分サンプリングの複雑さ境界と顕著な収束特性を組み合わせることで、対象電位の次数クエリの総数の観点から、アルゴリズムに漸近的でないいくつかの複雑さ境界を確立することができる。 提案アルゴリズムは,同じ設定の既存手法と比較して,最先端の複雑性境界を実現する。

関連論文リスト

• 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)
• Learning Rate Free Sampling in Constrained Domains [21.853333421463603]
  我々は、完全に学習率の低い制約付き領域をサンプリングするための新しい粒子ベースのアルゴリズム一式を導入する。 我々は,本アルゴリズムの性能を,単純度に基づくターゲットからのサンプリングを含む,様々な数値的な例で示す。
  論文  参考訳（メタデータ） (2023-05-24T09:31:18Z)
• A Proximal Algorithm for Sampling from Non-convex Potentials [14.909442791255042]
  滑らかさに欠ける非滑らかなポテンシャルの問題を考察する。 滑らかではなく、ポテンシャルは半滑らかあるいは多重多重滑らか関数であると仮定される。 我々は、交互サンプリングフレームワークとして知られるGibbsサンプリングの特殊なケースを開発する。
  論文  参考訳（メタデータ） (2022-05-20T13:58:46Z)
• A Proximal Algorithm for Sampling from Non-smooth Potentials [10.980294435643398]
  非滑らかなポテンシャルからのサンプリングのための新しいMCMCアルゴリズムを提案する。 本手法は, 近似バンドル法と交互サンプリングフレームワークに基づく。 この研究の重要な貢献は、任意の凸非滑らかポテンシャルに対して制限されたガウスオラクルを実現する高速アルゴリズムである。
  論文  参考訳（メタデータ） (2021-10-09T15:26:07Z)
• Towards Sample-Optimal Compressive Phase Retrieval with Sparse and Generative Priors [59.33977545294148]
  O(k log L)$サンプルは振幅に基づく経験損失関数を最小化する任意のベクトルに信号が近いことを保証するのに十分であることを示す。 この結果はスパース位相検索に適応し、基底信号が$s$-sparseおよび$n$-dimensionalである場合、$O(s log n)$サンプルは同様の保証に十分であることを示す。
  論文  参考訳（メタデータ） (2021-06-29T12:49:54Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。 非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。 そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
  論文  参考訳（メタデータ） (2021-06-10T17:54:21Z)
• Randomized Stochastic Variance-Reduced Methods for Stochastic Bilevel Optimization [62.87181271021217]
  機械学習に多くの応用がある非SBO問題を考察する。 本稿では,非SBO問題に対する高速ランダム化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-05-05T18:28:42Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Active Model Estimation in Markov Decision Processes [108.46146218973189]
  マルコフ決定過程(MDP)をモデル化した環境の正確なモデル学習のための効率的な探索の課題について検討する。 マルコフに基づくアルゴリズムは,本アルゴリズムと極大エントロピーアルゴリズムの両方を小サンプル方式で上回っていることを示す。
  論文  参考訳（メタデータ） (2020-03-06T16:17:24Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。