Variance Reduction and Low Sample Complexity in Stochastic Optimization via Proximal Point Method
This work addresses the challenge of reliable optimization in noisy environments for machine learning and optimization practitioners, offering a method that is less restrictive than existing approaches.
The paper tackles the problem of achieving high-probability guarantees in stochastic optimization under the weaker assumption of bounded variance, rather than strong noise assumptions like sub-Gaussian tails, by developing a stochastic proximal point method that combines a proximal subproblem solver with a probability booster, resulting in convergence with low sample complexity.
High-probability guarantees in stochastic optimization are often obtained only under strong noise assumptions such as sub-Gaussian tails. We show that such guarantees can also be achieved under the weaker assumption of bounded variance by developing a stochastic proximal point method. This method combines a proximal subproblem solver, which inherently reduces variance, with a probability booster that amplifies per-iteration reliability into high-confidence results. The analysis demonstrates convergence with low sample complexity, without restrictive noise assumptions or reliance on mini-batching.