A weak convergence approach to large deviations for stochastic approximations
The theory of stochastic approximations form the theoretical foundation for studying convergence properties of many popular recursive learning algorithms in statistics, machine learning and statistical physics. Large deviations for stochastic approximations provide asymptotic estimates of the probability that the learning algorithm deviates from its expected path, given by a limit ODE, and the large deviation rate function gives insights to the most likely way that such deviations occur. In this paper we prove a large deviation principle for general stochastic approximations with state-dependent Markovian noise and decreasing step size. Using the weak convergence approach to large deviations, we generalize previous results for stochastic approximations and identify the appropriate scaling sequence for the large deviation principle. We also give a new representation for the rate function, in which the rate function is expressed as an action functional involving the family of Markov transition kernels. Examples of learning algorithms that are covered by the large deviation principle include stochastic gradient descent, persistent contrastive divergence and the Wang-Landau algorithm.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Q-Learning for Stochastic Control under General Information Structures and Non-Markovian Environments
As a primary contribution, we present a convergence theorem for stochastic iterations, and in particular, Q-learning iterates, under a general, possibly non-Markovian, stochastic environment. Our conditions for convergen…
Q-LearningQuantizationWeak error rates of numerical schemes for rough volatility
Simulation of rough volatility models involves discretization of stochastic integrals where the integrand is a function of a (correlated) fractional Brownian motion of Hurst index $H \in (0,1/2)$. We obtain results on th…
Diffusion Approximations for Thompson Sampling
We study the behavior of Thompson sampling from the perspective of weak convergence. In the regime with small $\gamma > 0$, where the gaps between arm means scale as $\sqrt{\gamma}$ and over time horizons that scale as $…
Multi-Armed BanditsThompson SamplingSubgradient Selection Convergence Implies Uniform Subdifferential Set Convergence: And Other Tight Convergences Rates in Stochastic Convex Composite Minimization
In nonsmooth, nonconvex stochastic optimization, understanding the uniform convergence of subdifferential mappings is crucial for analyzing stationary points of sample average approximations of risk as they approach the …
Stochastic OptimizationWeak Convergence Properties of Constrained Emphatic Temporal-difference Learning with Constant and Slowly Diminishing Stepsize
We consider the emphatic temporal-difference (TD) algorithm, ETD($\lambda$), for learning the value functions of stationary policies in a discounted, finite state and action Markov decision process. The ETD($\lambda$) al…