资源分类
》 资源 》论文》Finite-Time Analysis of Projected Langevin Monte Carlo

Finite-Time Analysis of Projected Langevin Monte Carlo

2020-02-04 | |  75 |   43 |   0

Abstract

 We analyze the projected Langevin Monte Carlo (LMC) algorithm, a close cousin of projected Stochastic Gradient Descent (SGD). We show that LMC allows to sample in polynomial time from a posterior distribution restricted to a convex body and with concave log-likelihood. This gives the first Markov chain to sample from a log-concave distribution with a first-order oracle, as the existing chains with provable guarantees (lattice walk, ball walk and hit-and-run) require a zerothorder oracle. Our proof uses elementary concepts from stochastic calculus which could be useful more generally to understand SGD and its variants.

上一篇：Regret Lower Bound and Optimal Algorithm in Finite Stochastic Partial Monitoring

下一篇：Learning Causal Graphs with Small Interventions

用户评价
全部评价

热门资源

  • The Variational S...

    Unlike traditional images which do not offer in...

  • Learning to Predi...

    Much of model-based reinforcement learning invo...

  • Stratified Strate...

    In this paper we introduce Stratified Strategy ...

  • A Mathematical Mo...

    Direct democracy, where each voter casts one vo...

  • Rating-Boosted La...

    The performance of a recommendation system reli...