# Variance Reduction and Low Sample Complexity in Stochastic Optimization via Proximal Point Method

arXiv: https://arxiv.org/abs/2402.08992 · HTML: https://mlsanity.com/paper/2402.08992/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 14 references that are in the map.
- First posted on arXiv 14 Feb 2024.

## Builds on (most cited first, 4 of 4)

- [Loss minimization and parameter estimation with heavy tails](https://mlsanity.com/paper/1307.1827/) (2013)
- [Algorithms of Robust Stochastic Optimization Based on Mirror Descent Method](https://mlsanity.com/paper/1907.02707/) (2019)
- [A single cut proximal bundle method for stochastic convex composite optimization](https://mlsanity.com/paper/2207.09024/) (2022)
- [Parameter-Free FISTA by Adaptive Restart and Backtracking](https://mlsanity.com/paper/2307.14323/) (2023)

## Built on by (most cited first, 1 of 1)

- [Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductions](https://mlsanity.com/paper/2406.02789/) (2024)

## Abstract (arXiv)

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.