math.OCJun 25, 2025

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

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 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.

Figures & tables

Explore similar work

Nov 17, 2026

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

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.
Oct 30, 2026

Near-Optimal Second-Order Convex Finite-Sum Optimization under Individual Smoothness

We study the stochastic second-order oracle complexity of solving smooth convex finite-sum optimization with nn components. Very recently, Tsedenov & Kovalev (2026) showed that the minimax optimal complexity under averaged smoothness and convexity is Θ~(n+n6/7ε−2/7)\tildeΘ(n + n^{6/7} ε^{-2/7}) by establishing nearly matching upper and lower bounds. In this paper, we show that individual smoothness and convexity provably enable further acceleration, where the lower complexity bound is Ω(n+n5/7ε−2/7)Ω(n+ n^{5/7} ε^{-2/7}) under this stronger assumption. Then, by establishing a novel second-order self-bounding inequality, we design a new Taylor-corrected lazy Newton method, which can lead to a better complexity of O~(n+n5/7ε−2/7)\tilde{\mathcal{O}}(n + n^{5/7} ε^{-2/7}) by applying the optimal Monteiro-Svaiter acceleration, matching our lower bound up to only logarithmic factors.
Oct 13, 2025

Accelerated stochastic first-order method for convex optimization under heavy-tailed noise

We study convex composite optimization problems, where the objective function is given by the sum of a prox-friendly function and a convex function whose subgradients are estimated under heavy-tailed noise. Existing work often employs gradient clipping or normalization techniques in stochastic first-order methods to address heavy-tailed noise. %In this paper, we demonstrate that a vanilla stochastic algorithm---without additional modifications such as clipping or normalization---can achieve optimal complexity for these problems. In this paper, we analyze the first-order oracle complexity of vanilla stochastic algorithms---without additional modifications such as clipping or normalization---for solving these problems. In particular, we establish that an accelerated stochastic proximal subgradient method achieves a first-order oracle complexity for finding an approximate optimal solution in expectation that is universally optimal for smooth, weakly smooth, and nonsmooth convex optimization, as well as for stochastic convex optimization under heavy-tailed noise. Moreover, we derive high-probability first-order oracle complexity bounds for the accelerated stochastic proximal subgradient method under heavy-tailed and sub-Weibull noise, respectively. Numerical experiments are further provided to illustrate the numerical behavior of the methods.