Variance Reduction and Low Sample Complexity in Stochastic Optimization
  via Proximal Point Method
Jiaming Liang
This paper proposes a stochastic proximal point method to solve a stochastic
convex composite optimization problem. High probability results in stochastic
optimization typically hinge on restrictive assumptions on the stochastic
gradient noise, for example, sub-Gaussian distributions. Assuming only weak
conditions such as bounded variance of the stochastic gradient, this paper
establishes a low sample complexity to obtain a high probability guarantee on
the convergence of the proposed method. Additionally, a notable aspect of this
work is the development of a subroutine to solve the proximal subproblem, which
also serves as a novel technique for variance reduction.