# Stochastic Optimization with Constraints: A Non-asymptotic Instance-Dependent Analysis

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

## Key facts

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

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

- [Stochastic approximation with cone-contractive operators: Sharp ℓ_∞-bounds for Q-learning](https://mlsanity.com/paper/1905.06265/) (2019)
- [Variance-reduced Q-learning is minimax optimal](https://mlsanity.com/paper/1906.04697/) (2019)
- [Is Temporal Difference Learning Optimal? An Instance-Dependent Analysis](https://mlsanity.com/paper/2003.07337/) (2020)
- [Asymptotic Optimality in Stochastic Optimization](https://mlsanity.com/paper/1612.05612/) (2016)
- [Instance-optimality in optimal value estimation: Adaptivity via variance-reduced Q-learning](https://mlsanity.com/paper/2106.14352/) (2021)
- [Asymptotic normality and optimality in nonsmooth stochastic approximation](https://mlsanity.com/paper/2301.06632/) (2023)
- [Local Minimax Complexity of Stochastic Convex Optimization](https://mlsanity.com/paper/1605.07596/) (2016)

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

- [Instance-optimal stochastic convex optimization: Can we improve upon sample-average and robust stochastic approximation?](https://mlsanity.com/paper/2603.25657/) (2026)

## Abstract (arXiv)

We consider the problem of stochastic convex optimization under convex constraints. We analyze the behavior of a natural variance reduced proximal gradient (VRPG) algorithm for this problem. Our main result is a non-asymptotic guarantee for VRPG algorithm. Contrary to minimax worst case guarantees, our result is instance-dependent in nature. This means that our guarantee captures the complexity of the loss function, the variability of the noise, and the geometry of the constraint set. We show that the non-asymptotic performance of the VRPG algorithm is governed by the scaled distance (scaled by √N) between the solutions of the given problem and that of a certain small perturbation of the given problem -- both solved under the given convex constraints; here, N denotes the number of samples. Leveraging a well-established connection between local minimax lower bounds and solutions to perturbed problems, we show that as N rightarrow ∞, the VRPG algorithm achieves the renowned local minimax lower bound by H`ajek and Le Cam up to universal constants and a logarithmic factor of the sample size.