A Hitting Time Analysis of Stochastic Gradient Langevin Dynamics
  We study the Stochastic Gradient Langevin Dynamics (SGLD) algorithm for
non-convex optimization. The algorithm performs stochastic gradient descent,
where in each step it injects appropriately scaled Gaussian noise to the
update. We analyze the algorithm's hitting time to an arbitrary subset of the
parameter space. Two results follow from our general theory: First, we prove
that for empirical risk minimization, if the empirical risk is point-wise close
to the (smooth) population risk, then the algorithm achieves an approximate
local minimum of the population risk in polynomial time, escaping suboptimal
local minima that only exist in the empirical risk. Second, we show that SGLD
improves on one of the best known learnability results for learning linear
classifiers under the zero-one loss.
