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

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

    Nov 17, 2026Zhaosong Lu, Yifeng XiaoConstrained OptimizationStochastic Optimization

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

    Oct 13, 2025Chuan He, Bowen Li, Zhaosong LuStochastic OptimizationHeavy-Tailed Noise