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

• arxiv url: http://arxiv.org/abs/2212.00570v2
• Date: Sun, 14 Apr 2024 19:57:21 GMT
• ステータス: 処理完了
• システム内更新日: 2024-04-17 00:36:54.884022
• Title: Penalized Overdamped and Underdamped Langevin Monte Carlo Algorithms for Constrained Sampling
• Title（参考訳）: 制約サンプリングのためのLangevin Monte Carloアルゴリズム
• Authors: Mert Gürbüzbalaban, Yuanhan Hu, Lingjiong Zhu,
• Abstract要約: 目的が目標分布である$pi(x)prop ef(x)$から$x$が制約されたときにサンプリングする制約付きサンプリング問題を考える。 ペナルティ法によって動機付けられた制約付き問題を,制約違反に対するペナルティ関数を導入することにより,非制約サンプリング問題に変換する。 PSGLD と PSGULMC の場合、$tildemathcalO(d/varepsilon18)$ が強凸で滑らかであるとき、$tildemathcalO(d/varepsilon) を得る。
• 参考スコア（独自算出の注目度）: 17.832449046193933
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the constrained sampling problem where the goal is to sample from a target distribution $\pi(x)\propto e^{-f(x)}$ when $x$ is constrained to lie on a convex body $\mathcal{C}$. Motivated by penalty methods from continuous optimization, we propose penalized Langevin Dynamics (PLD) and penalized underdamped Langevin Monte Carlo (PULMC) methods that convert the constrained sampling problem into an unconstrained sampling problem by introducing a penalty function for constraint violations. When $f$ is smooth and gradients are available, we get $\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 the TV distance and $\tilde{\mathcal{O}}(\cdot)$ hides logarithmic factors. For PULMC, we improve the 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 results for underdamped Langevin Monte Carlo methods in the constrained sampling that handle non-convex $f$ and provide guarantees with the best dimension dependency among existing methods with deterministic gradient. If unbiased stochastic estimates of the gradient of $f$ are available, we propose PSGLD and PSGULMC methods that can handle stochastic gradients and are scaleable to large datasets without requiring Metropolis-Hasting correction steps. For PSGLD and PSGULMC, when $f$ is strongly convex and smooth, we obtain $\tilde{\mathcal{O}}(d/\varepsilon^{18})$ and $\tilde{\mathcal{O}}(d\sqrt{d}/\varepsilon^{39})$ iteration complexity in W2 distance. When $f$ is smooth and can be non-convex, we provide finite-time performance bounds and iteration complexity results. Finally, we illustrate the performance on Bayesian LASSO regression and Bayesian constrained deep learning problems.
• Abstract（参考訳）: 対象分布 $\pi(x)\propto e^{-f(x)}$ が凸体 $\mathcal{C}$ 上にあるとき、目的が対象分布 $\pi(x)\propto e^{-f(x)} からサンプリングすることであるような制約付きサンプリング問題を考える。 ペナルティ法を連続最適化から動機付け,制約違反に対するペナルティ関数を導入して,制約サンプリング問題を非制約サンプリング問題に変換する,ペナルティ付きランゲヴィン・ダイナミクス(PLD)およびペナルティ付きアンダーダム型ランゲヴィン・モンテカルロ(PULMC)手法を提案する。 f$がスムーズでグラデーションが利用できる場合、PDDがターゲットを最大で$\varepsilon$-errorまでサンプリングするのに、$\tilde{\mathcal{O}}(d/\varepsilon^{10})$イテレーションの複雑さがあり、テレビ距離でエラーが測定され、$\tilde{\mathcal{O}}(\cdot)$が対数要素を隠す。 PULMC に対して、$f の Hessian が Lipschitz であり、$\mathcal{C}$ の境界が十分に滑らかであるとき、 $\tilde{\mathcal{O}}(\sqrt{d}/\varepsilon^{7})$ に改善する。 我々の知る限り、これらは非凸$f$を処理し、決定論的勾配を持つ既存の方法の中で最高の次元依存性を持つ保証を与える制約付きサンプリングにおいて、アンダーダムされたランゲヴィン・モンテカルロ法に対する最初の収束結果である。 もし、$f$の勾配のバイアスのない確率的推定が利用可能であれば、確率的勾配を扱えるPSGLDおよびPSGULMC法を提案し、メトロポリス・ハスティング補正ステップを必要とせずに大規模データセットに拡張可能である。 PSGLD と PSGULMC に対して、$f$ が強凸かつ滑らかであるとき、W2 距離における反復複雑性$ $\tilde{\mathcal{O}}(d/\varepsilon^{18})$ と $\tilde{\mathcal{O}}(d\sqrt{d}/\varepsilon^{39}) を得る。 f$ が滑らかで非凸であれば、有限時間の性能境界とイテレーションの複雑さの結果を提供する。 最後に,ベイジアンLASSO回帰とベイジアン制約によるディープラーニング問題の性能について述べる。

関連論文リスト

• 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)

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

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