math.OCNov 17, 2026

An inexact stochastic variance-reduced gradient method for constrained convex finite-sum optimization

Authors: Zhaosong Lu, Yifeng Xiao

Organizations: Department of Industrial and Systems Engineering, University of Minnesota, USA

Abstract

In this paper, we study a class of constrained convex finite-sum optimization problems. In many practical applications, all or some of the constraints are hard constraints that represent imperative requirements. Consequently, any desirable approximate solution must (nearly) satisfy these constraints. Motivated by this, we focus on computing an εε-surely feasible stochastic optimalsurely\ feasible\ stochastic\ optimal (εε-SFSO) solution, in which the constraint violation is deterministically bounded by εε, and the expected optimality gap is at most εε. While a recently proposed stochastic variance-reduced first-order penalty method can compute an εε-SFSO solution, there remains a significant gap between its first-order oracle complexity for computing an εε-SFSO solution and that for computing an εε-expected feasible stochastic optimalexpected\ feasible\ stochastic\ optimal solution, where both the expected constraint violation and the expected optimality gap are bounded by εε. To narrow this gap, we propose an inexact stochastic variance-reduced gradient (SVRG) method that significantly improves the previously best-known first-order oracle complexity for computing an εε-SFSO solution. Furthermore, when the objective consists of a single function, the proposed method reduces to a novel deterministic first-order method for solving standard convex conic optimization. It achieves a significantly lower gradient evaluation complexity with respect to the objective function compared to existing methods, and can outperform them when computing constraint gradients and projections onto the associated cone is cheaper than evaluating the objective gradient. Preliminary numerical results are presented to illustrate the performance of the proposed method.

Figures & tables

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

Jun 25, 2025

First-order methods for stochastic and finite-sum convex optimization with deterministic constraints

In this paper, we study a class of stochastic and finite-sum convex optimization problems with deterministic constraints. Existing methods typically aim to find an εε-expected feasible stochastic optimalexpected\ feasible\ stochastic\ optimal solution, in which both the expected constraint violation and the expected optimality gap are within a prescribed tolerance εε. However, in many practical applications, constraints must be nearly satisfied with certainty, rendering such solutions potentially unsuitable due to the risk of substantial violations. To address this issue, we propose stochastic first-order methods for finding an εε-surely feasible stochastic optimalsurely\ feasible\ stochastic\ optimal (εε-SFSO) solution, where the constraint violation is deterministically bounded by εε and the expected optimality gap is at most εε. Our methods apply an accelerated stochastic gradient (ASG) scheme or a modified variance-reduced ASG scheme only onceonly\ once to a sequence of quadratic penalty subproblems with appropriately chosen penalty parameters. We establish first-order oracle complexity bounds for the proposed methods in computing an εε-SFSO solution. Preliminary numerical results are presented to illustrate the performance of the proposed methods.
Sep 8, 2026

How to Make the Gradient Mapping Small for Constrained Stochastic Min-Max Problems and Beyond

We study the stochastic first-order oracle complexity for constrained or regularized convex-concave min-max optimization and stochastic monotone variational inequalities. We focus on the case when suboptimality is measured in terms of the gradient mapping, also known as, forward-backward or natural residual, an optimality notion that generalizes the gradient norm for unconstrained problems. In this setting, under standard unbiased oracle access with now-standard variance assumptions, the best-known complexity for making the norm of the gradient mapping less than ε\varepsilon is O~(ε−4)\widetilde{O}(\varepsilon^{-4}), compared to the near-optimal O~(ε−2)\widetilde{O}(\varepsilon^{-2}) that is established in the unconstrained case. We bridge this gap to improve the gradient mapping complexity for constrained convex-concave min-max problems to O~(ε−2)\widetilde{O}(\varepsilon^{-2}). We then extend to prove the same complexity for problems without the bounded variance, by using the Blum-Gladyshev assumption.
Oct 9, 2026

Optimal Algorithms for Nonsmooth Nonconvex Stochastic Optimization with Constraints

We present new algorithms for stochastic optimization problems in which the objective is neither smooth nor convex, subject to a convex constraint set. Our algorithms return a (δ,ε)(δ,\varepsilon)-Goldstein stationary point, as recently defined for constrained problems by Liu et al. (2024), with improved complexities, and are the first to achieve optimal convergence rates for this task in several settings. In particular, we design projection-based and projection-free algorithms that achieve a O~(δ−1ε−3)\widetilde O(δ^{-1}\varepsilon^{-3}) rate using stochastic gradients, which we show to be optimal, and a O~(dδ−1ε−3)\widetilde O(dδ^{-1}\varepsilon^{-3}) rate using zeroth-order queries, which is also optimal in its dependence on the dimension dd and improves over prior work. Notably, our lower bound is given in terms of the Frank-Wolfe gap and holds even for smooth problems, which is of independent interest. These results show that in nonconvex stochastic optimization, the convergence rate is degraded neither by the presence of constraints nor by nonsmoothness. Our analysis is based on a reduction to online linear optimization, extending a related technique from unconstrained optimization.