論文の概要: Penalized Langevin and Hamiltonian Monte Carlo Algorithms for Constrained Sampling

• arxiv url: http://arxiv.org/abs/2212.00570v1
• Date: Tue, 29 Nov 2022 18:43:22 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-02 15:28:12.358339
• Title: Penalized Langevin and Hamiltonian Monte Carlo Algorithms for Constrained Sampling
• Title（参考訳）: 制約サンプリングのためのペナル化ランゲヴィンとハミルトンモンテカルロアルゴリズム
• Authors: Mert G\"urb\"uzbalaban, Yuanhan Hu, Lingjiong Zhu
• Abstract要約: 分布(x)prop ef(x)$と$x$が凸体上で制約されるような制約付きサンプリング問題を考える。 我々は,制限されたサンプリング問題をペナルティ関数制約違反を導入して非拘束なものに変換する,ペナルティ付ハミルトンモンテカルロダイナミクス(PLD)とペナルティ付ハミルトンモンテカルロダイナミクス(PHMC)を提案する。 PHMCでは、Hessianが$であるときに $tildemathcalO(sqrtd/varepsilon7)$に改善します。
• 参考スコア（独自算出の注目度）: 8.333246626497363
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the constrained sampling problem where the goal is to sample from a distribution $\pi(x)\propto e^{-f(x)}$ and $x$ is constrained on a convex body $\mathcal{C}\subset \mathbb{R}^d$. Motivated by penalty methods from optimization, we propose penalized Langevin Dynamics (PLD) and penalized Hamiltonian Monte Carlo (PHMC) that convert the constrained sampling problem into an unconstrained one by introducing a penalty function for constraint violations. When $f$ is smooth and the gradient is available, we show $\tilde{\mathcal{O}}(d/\varepsilon^{10})$ iteration complexity for PLD to sample the target up to an $\varepsilon$-error where the error is measured in terms of the total variation distance and $\tilde{\mathcal{O}}(\cdot)$ hides some logarithmic factors. For PHMC, we improve this result to $\tilde{\mathcal{O}}(\sqrt{d}/\varepsilon^{7})$ when the Hessian of $f$ is Lipschitz and the boundary of $\mathcal{C}$ is sufficiently smooth. To our knowledge, these are the first convergence rate results for Hamiltonian Monte Carlo methods in the constrained sampling setting that can handle non-convex $f$ and can provide guarantees with the best dimension dependency among existing methods with deterministic gradients. We then consider the setting where unbiased stochastic gradients are available. We propose PSGLD and PSGHMC that can handle stochastic gradients without Metropolis-Hasting correction steps. When $f$ is strongly convex and smooth, we obtain an iteration complexity of $\tilde{\mathcal{O}}(d/\varepsilon^{18})$ and $\tilde{\mathcal{O}}(d\sqrt{d}/\varepsilon^{39})$ respectively in the 2-Wasserstein distance. For the more general case, when $f$ is smooth and non-convex, we also provide finite-time performance bounds and iteration complexity results. Finally, we test our algorithms on Bayesian LASSO regression and Bayesian constrained deep learning problems.
• Abstract（参考訳）: 分布 $\pi(x)\propto e^{-f(x)}$ と $x$ が凸体 $\mathcal{C}\subset \mathbb{R}^d$ 上で制約されるような制約付きサンプリング問題を考える。 ペナルティ法を最適化から動機付け,制約付きサンプリング問題を制約違反のペナルティ関数を導入し,制約付きサンプリング問題を制約なしのペナルティ関数に変換する,ペナルティ付きランゲヴィンダイナミクス(PLD)とペナルティ付きハミルトンモンテカルロ(PHMC)を提案する。 f$ が滑らかで勾配が利用可能であれば、$\tilde{\mathcal{o}}(d/\varepsilon^{10})$ 反復複雑性を示す。 pld は目標を$\varepsilon$-error までサンプリングし、誤差は全変動距離で測定され、$\tilde{\mathcal{o}}(\cdot)$ はいくつかの対数因子を隠蔽する。 phmc の場合、この結果を $\tilde{\mathcal{o}}(\sqrt{d}/\varepsilon^{7})$ に改善する: $f$ のヘッセンがリプシッツであり、$\mathcal{c}$ の境界が十分滑らかである。 我々の知る限りでは、これらは非凸$f$を処理でき、決定論的勾配を持つ既存の方法間で最適な次元依存性を持つ保証を提供できる制約付きサンプリング設定において、ハミルトン・モンテカルロ法の最初の収束率結果である。 次に、偏りのない確率勾配が利用できる設定を考える。 メトロポリス・ハスティング補正ステップなしで確率勾配を処理できるPSGLDとPSGHMCを提案する。 f$ が強凸かつ滑らかであれば、それぞれ 2-ワッサーシュタイン距離において $\tilde{\mathcal{O}}(d/\varepsilon^{18})$ と $\tilde{\mathcal{O}}(d\sqrt{d}/\varepsilon^{39})$ の反復複雑性が得られる。 より一般的な場合、$f$ が滑らかで非凸であれば、有限時間のパフォーマンス境界と反復複雑性の結果も提供する。 最後に、アルゴリズムをベイズラッソ回帰とベイズ制約付き深層学習問題でテストする。

関連論文リスト

• Iterative thresholding for non-linear learning in the strong $\varepsilon$-contamination model [3.309767076331365]
  閾値降下を用いた単一ニューロンモデル学習のための近似境界を導出する。 線形回帰問題も研究し、$sigma(mathbfx) = mathbfx$ となる。
  論文  参考訳（メタデータ） (2024-09-05T16:59:56Z)
• ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
  本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。 我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2023-01-01T18:51:29Z)
• Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP [58.13930707612128]
  この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。 我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
  論文  参考訳（メタデータ） (2022-12-01T15:57:58Z)
• Optimal Gradient Sliding and its Application to Distributed Optimization Under Similarity [121.83085611327654]
  積 $r:=p + q$, ここで$r$は$mu$-strong convex類似性である。 エージェントの通信やローカルコールにマスターされた問題を解決する方法を提案する。 提案手法は$mathcalO(sqrtL_q/mu)$法よりもはるかにシャープである。
  論文  参考訳（メタデータ） (2022-05-30T14:28:02Z)
• 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)
• Denoising modulo samples: k-NN regression and tightness of SDP relaxation [5.025654873456756]
  サンプルの値が$f(x_i)$で一様誤差率$O(fraclog nn)frac1d+2)$を高い確率で保持する2段階のアルゴリズムを導出する。 サンプル $f(x_i)$ の見積もりは、その後、関数 $f$ の見積もりを構築するために使われる。
  論文  参考訳（メタデータ） (2020-09-10T13:32:46Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。 i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  論文  参考訳（メタデータ） (2020-07-16T06:44:44Z)
• Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
  期待される正方形損失から、最も適合した単一ニューロンを学習することの問題点を考察する。 ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。 ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
  論文  参考訳（メタデータ） (2020-05-29T07:20:35Z)
• Randomized Bregman Coordinate Descent Methods for Non-Lipschitz Optimization [31.474280642125734]
  そこで本研究では,新しいテクステンラン化ブレグマン座標降下法(CD)を提案する。 提案手法は$O(epsilon-2n)$であり,$n$は座標のブロック数であることを示す。
  論文  参考訳（メタデータ） (2020-01-15T09:57:38Z)

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

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