論文の概要: Langevin Monte Carlo: random coordinate descent and variance reduction
- arxiv url: http://arxiv.org/abs/2007.14209v8
- Date: Thu, 7 Oct 2021 14:07:11 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-06 19:46:23.141905
- Title: Langevin Monte Carlo: random coordinate descent and variance reduction
- Title（参考訳）: Langevin Monte Carlo:ランダム座標降下と分散還元
- Authors: Zhiyan Ding and Qin Li
- Abstract要約: Langevin Monte Carlo (LMC) はベイジアンサンプリング法として人気がある。
LMC上でのRCD(ランダム座標降下)の適用により計算効率を向上させる方法について検討する。
- 参考スコア（独自算出の注目度）: 7.464874233755718
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Langevin Monte Carlo (LMC) is a popular Bayesian sampling method. For the
log-concave distribution function, the method converges exponentially fast, up
to a controllable discretization error. However, the method requires the
evaluation of a full gradient in each iteration, and for a problem on
$\mathbb{R}^d$, this amounts to $d$ times partial derivative evaluations per
iteration. The cost is high when $d\gg1$. In this paper, we investigate how to
enhance computational efficiency through the application of RCD (random
coordinate descent) on LMC. There are two sides of the theory:
1 By blindly applying RCD to LMC, one surrogates the full gradient by a
randomly selected directional derivative per iteration. Although the cost is
reduced per iteration, the total number of iteration is increased to achieve a
preset error tolerance. Ultimately there is no computational gain;
2 We then incorporate variance reduction techniques, such as SAGA (stochastic
average gradient) and SVRG (stochastic variance reduced gradient), into
RCD-LMC. It will be proved that the cost is reduced compared with the classical
LMC, and in the underdamped case, convergence is achieved with the same number
of iterations, while each iteration requires merely one-directional derivative.
This means we obtain the best possible computational cost in the
underdamped-LMC framework.
- Abstract（参考訳）: Langevin Monte Carlo (LMC) はベイジアンサンプリング法として人気がある。
log-concave分布関数では、制御可能な離散化誤差まで指数関数的に収束する。
しかし、この手法では各反復における完全な勾配の評価が必要であり、$\mathbb{R}^d$の問題を解くと、1反復あたりの偏微分評価は$d$倍になる。
価格は$d\gg1$で高い。
本稿では,lmcにおけるrcd(random coordinate descent)の適用による計算効率の向上について検討する。
1 は LMC に盲目的に RCD を適用することにより、反復ごとにランダムに選択された方向微分によって全勾配を代理する。
イテレーションあたりのコストは削減されるが、プリセットされたエラー耐性を達成するために、全イテレーション数が増加する。
次に,SAGA (stochastic average gradient) やSVRG (stochastic variance reduced gradient) などの分散低減手法を RCD-LMC に組み込む。
古典的な LMC と比較してコストが削減されることが証明され、アンダーダムドの場合、収束は同じ数の反復で達成され、各反復は単なる一方向微分を必要とする。
これは、アンダーダムドlmcフレームワークで可能な最高の計算コストを得ることを意味する。
関連論文リスト
- MGDA Converges under Generalized Smoothness, Provably [27.87166415148172]
多目的最適化(MOO)はマルチタスク学習など様々な分野で注目を集めている。
最近の研究は、理論解析を伴う効果的なアルゴリズムを提供しているが、それらは標準の$L$-smoothあるいは有界勾配仮定によって制限されている。
一般化された$ell$-smooth損失関数のより一般的で現実的なクラスについて研究し、$ell$は勾配ノルムの一般非減少関数である。
論文 参考訳（メタデータ） (2024-05-29T18:36:59Z) - Double Variance Reduction: A Smoothing Trick for Composite Optimization Problems without First-Order Gradient [40.22217106270146]
ばらつき低減技術はサンプリングのばらつきを低減し、一階法(FO)とゼロ階法(ZO)の収束率を向上するように設計されている。
複合最適化問題において、ZO法は、ランダム推定から導かれる座標ワイド分散と呼ばれる追加の分散に遭遇する。
本稿では,ZPDVR法とZPDVR法を提案する。
論文 参考訳（メタデータ） (2024-05-28T02:27:53Z) - Stochastic Optimization for Non-convex Problem with Inexact Hessian
Matrix, Gradient, and Function [99.31457740916815]
信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。
TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
論文 参考訳（メタデータ） (2023-10-18T10:29:58Z) - Sharper Convergence Guarantees for Asynchronous SGD for Distributed and
Federated Learning [77.22019100456595]
通信周波数の異なる分散計算作業者のトレーニングアルゴリズムを示す。
本研究では,より厳密な収束率を$mathcalO!!(sigma2-2_avg!)とする。
また,不均一性の項は,作業者の平均遅延によっても影響されることを示した。
論文 参考訳（メタデータ） (2022-06-16T17:10:57Z) - Faster One-Sample Stochastic Conditional Gradient Method for Composite
Convex Minimization [61.26619639722804]
滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。
提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
論文 参考訳（メタデータ） (2022-02-26T19:10:48Z) - Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
カーネルヒルベルト空間を用いて、無限水平割引マルコフ報酬過程の値関数を推定する。
我々は、関連するカーネル演算子の固有値に明示的に依存した誤差の非漸近上界を導出する。
MRP のサブクラスに対する minimax の下位境界を証明する。
論文 参考訳（メタデータ） (2021-09-24T14:48:20Z) - 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) - Convergence of Langevin Monte Carlo in Chi-Squared and Renyi Divergence [8.873449722727026]
推定値である$widetildemathcalO(depsilon-1)$が,これらの測定値の既知レートを改善することを示す。
特に凸および1次滑らかなポテンシャルについて、LCCアルゴリズムは、これらの測定値の既知率を改善するために$widetildemathcalO(depsilon-1)$を推定する。
論文 参考訳（メタデータ） (2020-07-22T18:18:28Z) - Variance reduction for Random Coordinate Descent-Langevin Monte Carlo [7.464874233755718]
高速収束を提供するランゲヴィン・モンテカルロ(LMC)は勾配近似の計算を必要とする。
実際には、有限差分近似を代理として使用し、高次元では高価である。
本稿では,新しい分散低減手法であるCoordinates Averaging Descent (RCAD)を導入し,過度に損傷を受けたLCCと過度に損傷を受けたLCCを併用する。
論文 参考訳（メタデータ） (2020-06-10T21:08:38Z) - 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) - Differentially Quantized Gradient Methods [53.3186247068836]
微分量子化グラディエントDescence (DQ-GD) が$maxsigma_mathrmGD, rhon 2-R$の線形収縮係数を得ることを示す。
あるクラス内のアルゴリズムは$maxsigma_mathrmGD, 2-R$よりも早く収束できない。
論文 参考訳（メタデータ） (2020-02-06T20:40:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。