論文の概要: Improved dimension dependence of a proximal algorithm for sampling
- arxiv url: http://arxiv.org/abs/2302.10081v2
- Date: Wed, 28 Jun 2023 16:09:48 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-29 18:12:18.556978
- Title: Improved dimension dependence of a proximal algorithm for sampling
- Title（参考訳）: サンプリングのための近位アルゴリズムの次元依存性の改善
- Authors: Jiaojiao Fan, Bo Yuan and Yongxin Chen
- Abstract要約: そこで本研究では,すべての古典的設定において,より優れた複雑性境界を実現するサンプリングアルゴリズムを提案する。
提案アルゴリズムは,2021年に導入した近位サンプルを用いた。
強い対数対数分布の場合、この手法は温度開始を伴わずに$tildemathcalO(kappa d1/2)$の複雑さを持つ。
LSI を満たす分布に対して、我々は $tilde MathcalO(hat kappa d1/2)$ ここで $hat kappa$ は滑らかさと滑らかさの比である。
- 参考スコア（独自算出の注目度）: 16.147290924171692
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose a sampling algorithm that achieves superior complexity bounds in
all the classical settings (strongly log-concave, log-concave,
Logarithmic-Sobolev inequality (LSI), Poincar\'e inequality) as well as more
general settings with semi-smooth or composite potentials. Our algorithm is
based on the proximal sampler introduced in~\citet{lee2021structured}. The
performance of this proximal sampler is determined by that of the restricted
Gaussian oracle (RGO), a key step in the proximal sampler. The main
contribution of this work is an inexact realization of RGO based on approximate
rejection sampling. To bound the inexactness of RGO, we establish a new
concentration inequality for semi-smooth functions over Gaussian distributions,
extending the well-known concentration inequality for Lipschitz functions.
Applying our RGO implementation to the proximal sampler, we achieve
state-of-the-art complexity bounds in almost all settings. For instance, for
strongly log-concave distributions, our method has complexity bound
$\tilde\mathcal{O}(\kappa d^{1/2})$ without warm start, better than the minimax
bound for MALA. For distributions satisfying the LSI, our bound is $\tilde
\mathcal{O}(\hat \kappa d^{1/2})$ where $\hat \kappa$ is the ratio between
smoothness and the LSI constant, better than all existing bounds.
- Abstract（参考訳）: 本研究では,すべての古典的設定(特にlog-concave,log-concave,logarithmic-sobolev inequality (lsi),poincar\'e inequality)において,より汎用的な半スムースあるいは複合ポテンシャルを用いた,より優れた複雑性境界を実現するサンプリングアルゴリズムを提案する。
提案アルゴリズムは, 〜\citet{lee2021structured} で導入された近位標本に基づく。
この近位サンプリング器の性能は、近位サンプリング器の重要なステップである制限されたガウスオラクル(RGO)によって決定される。
この研究の主な貢献は、近似的拒絶サンプリングに基づくRGOの不正確な実現である。
RGOの不等式を束縛するために、ガウス分布上の半滑らか関数に対する新しい濃度不等式を確立し、リプシッツ函数に対するよく知られた濃度不等式を拡張する。
RGOの実装を近位サンプリングに応用し、ほぼすべての設定で最先端の複雑さ境界を達成する。
例えば、強い対数対数分布の場合、我々の手法は、MALA の minimax 境界よりも、ウォームスタートのない$\tilde\mathcal{O}(\kappa d^{1/2})$ の複雑さを持つ。
LSIを満たす分布に対して、我々の境界は$\tilde \mathcal{O}(\hat \kappa d^{1/2})$である。
関連論文リスト
- 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) - Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and
Optimal Algorithms [64.10576998630981]
最適なヘッセン依存型サンプルの複雑さを, 初めて厳密に評価した。
ヘシアン非依存のアルゴリズムは、すべてのヘシアンインスタンスに対して最適なサンプル複雑さを普遍的に達成する。
本アルゴリズムにより得られたサンプルの最適複雑さは,重み付き雑音分布においても有効である。
論文 参考訳（メタデータ） (2023-06-21T17:03:22Z) - Faster high-accuracy log-concave sampling via algorithmic warm starts [6.117084972237769]
実際には、古典的なメトロポリス調整ランゲヴィンアルゴリズム(MALA)のような高精度なサンプリング器は事実上のゴールド標準のままである。
我々は,このサンプリング問題の次元依存性を$tildeO(d1/2)$に改善し,MALAでは$tildeO(d1/2)$とした。
我々の主な技術的貢献は、離散化アンダーダム化ランゲヴィン拡散に対する最初の$tildeO(d1/2)$ R'enyi混合速度を確立することでこの問題を解決することである。
論文 参考訳（メタデータ） (2023-02-20T19:27:21Z) - Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。
予測と高い確率で、新しい過剰なリスク境界を提供する。
我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
論文 参考訳（メタデータ） (2022-11-03T12:40:24Z) - A Proximal Algorithm for Sampling from Non-convex Potentials [14.909442791255042]
滑らかさに欠ける非滑らかなポテンシャルの問題を考察する。
滑らかではなく、ポテンシャルは半滑らかあるいは多重多重滑らか関数であると仮定される。
我々は、交互サンプリングフレームワークとして知られるGibbsサンプリングの特殊なケースを開発する。
論文 参考訳（メタデータ） (2022-05-20T13:58:46Z) - Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and
Beyond [63.59034509960994]
シャッフルに基づく変種(ミニバッチと局所ランダムリシャッフル)について検討する。
ポリアック・ロジャシエヴィチ条件を満たす滑らかな函数に対して、これらのシャッフル型不変量(英語版)(shuffling-based variants)がそれらの置換式よりも早く収束することを示す収束境界を得る。
我々は, 同期シャッフル法と呼ばれるアルゴリズムの修正を提案し, ほぼ均一な条件下では, 下界よりも収束速度が速くなった。
論文 参考訳（メタデータ） (2021-10-20T02:25:25Z) - Sample-Optimal PAC Learning of Halfspaces with Malicious Noise [4.8728183994912415]
Valiant(1985)の悪意のあるノイズの存在下で$mathRd$の半空間の効率的なPAC学習を研究します。
Awasthi et alのアルゴリズムのための新しい分析を提示します。
そして、ほぼ最適に近いサンプル複雑性を$tildeo(d)$という値で達成できることを示します。
Bbbshoutyetal (2002) のより一般的で強力なノイズモデルにアルゴリズムと解析を拡張し、ほぼ最適なノイズ耐性とサンプルの複雑さを時間内に達成可能であることを示す。
論文 参考訳（メタデータ） (2021-02-11T20:18:20Z) - Structured Logconcave Sampling with a Restricted Gaussian Oracle [23.781520510778716]
我々は,複数のロジコンケーブファミリーを高精度にサンプリングするアルゴリズムを提案する。
凸最適化における近点法にインスパイアされた縮小フレームワークをさらに発展させる。
論文 参考訳（メタデータ） (2020-10-07T01:43:07Z) - Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and
Variance Reduction [63.41789556777387]
非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。
Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
論文 参考訳（メタデータ） (2020-06-04T17:51:00Z) - Breaking the Sample Size Barrier in Model-Based Reinforcement Learning
with a Generative Model [50.38446482252857]
本稿では、生成モデル(シミュレータ)へのアクセスを想定して、強化学習のサンプル効率について検討する。
最初に$gamma$-discounted infinite-horizon Markov decision process (MDPs) with state space $mathcalS$ and action space $mathcalA$を考える。
対象の精度を考慮すれば,モデルに基づく計画アルゴリズムが最小限のサンプルの複雑さを実現するのに十分であることを示す。
論文 参考訳（メタデータ） (2020-05-26T17:53:18Z) - Computationally efficient sparse clustering [67.95910835079825]
我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。
ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
論文 参考訳（メタデータ） (2020-05-21T17:51:30Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。