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

arXiv:2404.00042v1 Announce Type: cross
Abstract: 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 …

abstract algorithm analysis analyze arxiv behavior case constraints cs.ai cs.lg gradient instance math.oc minimax natural optimization stat.ml stochastic type variance