Stochastic Optimization with Constraints: A Non-asymptotic Instance-Dependent Analysis
This work addresses optimization under constraints for researchers in machine learning and statistics, offering a refined analysis that is incremental by focusing on instance-dependent guarantees rather than worst-case bounds.
The paper tackles stochastic convex optimization under constraints by analyzing a variance reduced proximal gradient algorithm, providing a non-asymptotic, instance-dependent guarantee that captures loss function complexity, noise variability, and constraint geometry, and showing it achieves the local minimax lower bound up to constants and a logarithmic factor as sample size increases.
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 $\sqrt{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 \infty$, the VRPG algorithm achieves the renowned local minimax lower bound by Hàjek and Le Cam up to universal constants and a logarithmic factor of the sample size.