論文の概要: A New Framework for Variance-Reduced Hamiltonian Monte Carlo
- arxiv url: http://arxiv.org/abs/2102.04613v1
- Date: Tue, 9 Feb 2021 02:44:24 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-10 15:11:34.773733
- Title: A New Framework for Variance-Reduced Hamiltonian Monte Carlo
- Title(参考訳): 分散還元型ハミルトニアンモンテカルロの新しい枠組み
- Authors: Zhengmian Hu, Feihu Huang, Heng Huang
- Abstract要約: 分散還元型ハミルトン・モンテカルロ法 (HMC) の新たなフレームワークを提案し,$L$-smooth および $m$-strongly log-concave 分布からサンプリングする。
本研究では,SAGA法やSVRG法をベースとした非バイアス勾配推定器を用いて,バッチサイズを小さくすることで,高い勾配効率が得られることを示す。
総合的および実世界のベンチマークデータによる実験結果から、我々の新しいフレームワークは、完全な勾配と勾配HMCアプローチを著しく上回っていることが示された。
- 参考スコア(独自算出の注目度): 88.84622104944503
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose a new framework of variance-reduced Hamiltonian Monte Carlo (HMC)
methods for sampling from an $L$-smooth and $m$-strongly log-concave
distribution, based on a unified formulation of biased and unbiased variance
reduction methods. We study the convergence properties for HMC with gradient
estimators which satisfy the Mean-Squared-Error-Bias (MSEB) property. We show
that the unbiased gradient estimators, including SAGA and SVRG, based HMC
methods achieve highest gradient efficiency with small batch size under high
precision regime, and require $\tilde{O}(N + \kappa^2 d^{\frac{1}{2}}
\varepsilon^{-1} + N^{\frac{2}{3}} \kappa^{\frac{4}{3}} d^{\frac{1}{3}}
\varepsilon^{-\frac{2}{3}} )$ gradient complexity to achieve
$\epsilon$-accuracy in 2-Wasserstein distance. Moreover, our HMC methods with
biased gradient estimators, such as SARAH and SARGE, require
$\tilde{O}(N+\sqrt{N} \kappa^2 d^{\frac{1}{2}} \varepsilon^{-1})$ gradient
complexity, which has the same dependency on condition number $\kappa$ and
dimension $d$ as full gradient method, but improves the dependency of sample
size $N$ for a factor of $N^\frac{1}{2}$. Experimental results on both
synthetic and real-world benchmark data show that our new framework
significantly outperforms the full gradient and stochastic gradient HMC
approaches. The earliest version of this paper was submitted to ICML 2020 with
three weak accept but was not finally accepted.
- Abstract(参考訳): 偏りと偏りのない分散低減法の統一的な定式化に基づいて,l$-smooth と $m$-strongly log-concave 分布からサンプリングするための分散還元型モンテカルロ法(hmc)の新しい枠組みを提案する。
Mean-Squared-Error-Bias(MSEB)特性を満たす勾配推定器を用いてHMCの収束特性を検討する。
我々は、SAGAおよびSVRGを含む偏りのない勾配推定器は、HMC法に基づいて、高精度な体制下での小さなバッチサイズで最高勾配効率を達成し、$\tilde{O}(N + \kappa^2 d^{\frac{1}{2}} \varepsilon^{-1} + N^{\frac{2}{3}} \kappa^{\frac{4}{3}} d^{\frac{1}{3}} \varepsilon^{-\frac{2}{3}} )$ 勾配の複雑さを2-Waserstein距離で実現することを示した。
さらに、SARAH や SARGE のような偏り勾配推定器を持つ HMC 法は、 $\tilde{O}(N+\sqrt{N} \kappa^2 d^{\frac{1}{2}} \varepsilon^{-1})$ 勾配複雑性を必要とし、条件番号 $\kappa$ と次元 $d$ に同じ依存性を持つが、サンプルサイズ $N$ を $N^\frac{1}{2}$ の因子に対して改善する。
合成および実世界のベンチマークデータによる実験結果から、我々の新しいフレームワークは、完全な勾配勾配と確率勾配HMCアプローチを著しく上回っていることが示された。
この論文の初期のバージョンは3つの弱い受け入れを持つICML 2020に提出されましたが、最終的に受け入れられませんでした。
関連論文リスト
- Convergence Analysis of Adaptive Gradient Methods under Refined Smoothness and Noise Assumptions [18.47705532817026]
適応勾配法は間違いなくニューラルネットワークの最も成功した最適化アルゴリズムである。
適応的勾配法は、アダッド・エル・エル・アンド・ジオメトリ(Adad-ell/ell$ geometry)を形作る可能性があることを示す。
論文 参考訳(メタデータ) (2024-06-07T02:55:57Z) - Provable Policy Gradient Methods for Average-Reward Markov Potential
Games [15.136494705127564]
無限水平平均報酬基準の下でマルコフポテンシャルゲームを研究する。
我々は、独立政策勾配と独立自然政策勾配に基づくアルゴリズムが、平均報酬基準に対するナッシュ均衡にグローバルに収束することを証明した。
論文 参考訳(メタデータ) (2024-03-09T00:20:33Z) - Unbiased Kinetic Langevin Monte Carlo with Inexact Gradients [0.8749675983608172]
動力学的ランゲヴィンダイナミクスに基づく後進手段の非バイアス化手法を提案する。
提案した推定器は偏りがなく、有限分散となり、中心極限定理を満たす。
以上の結果から, 偏りのないアルゴリズムは, ランダムなハミルトニアンモンテカルロよりもはるかに効率的であることが示唆された。
論文 参考訳(メタデータ) (2023-11-08T21:19:52Z) - Settling the Sample Complexity of Model-Based Offline Reinforcement
Learning [50.5790774201146]
オフライン強化学習(RL)は、事前収集されたデータを用いて、さらなる探索を行わずに学習する。
事前のアルゴリズムや分析は、最適なサンプルの複雑さに悩まされるか、サンプルの最適性に到達するために高いバーンインコストがかかるかのいずれかである。
モデルベース(あるいは"プラグイン")アプローチは,バーンインコストを伴わずに,最小限のサンプル複雑性を実現することを実証する。
論文 参考訳(メタデータ) (2022-04-11T17:26:19Z) - A Variance Controlled Stochastic Method with Biased Estimation for
Faster Non-convex Optimization [0.0]
減少勾配(SVRG)の性能を向上させるために, 分散制御勾配(VCSG)という新しい手法を提案する。
ラムダ$はVCSGで導入され、SVRGによる分散の過剰還元を避ける。
$mathcalO(min1/epsilon3/2,n1/4/epsilon)$ 勾配評価の数。
論文 参考訳(メタデータ) (2021-02-19T12:22:56Z) - Tightening the Dependence on Horizon in the Sample Complexity of
Q-Learning [59.71676469100807]
この研究は、同期Q-ラーニングのサンプルの複雑さを、任意の$0varepsilon 1$に対して$frac|mathcalS| (1-gamma)4varepsilon2$の順序に絞る。
計算やストレージを余分に必要とせずに、高速なq-learningにマッチするvanilla q-learningの有効性を明らかにした。
論文 参考訳(メタデータ) (2021-02-12T14:22:05Z) - Faster Convergence of Stochastic Gradient Langevin Dynamics for
Non-Log-Concave Sampling [110.88857917726276]
我々は,非log-concaveとなる分布のクラスからサンプリングするために,勾配ランゲヴィンダイナミクス(SGLD)の新たな収束解析を行う。
我々のアプローチの核心は、補助的時間反転型マルコフ連鎖を用いたSGLDのコンダクタンス解析である。
論文 参考訳(メタデータ) (2020-10-19T15:23:18Z) - 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) - Towards Better Understanding of Adaptive Gradient Algorithms in
Generative Adversarial Nets [71.05306664267832]
適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。
本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。
実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
論文 参考訳(メタデータ) (2019-12-26T22:10:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。