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

arXiv: https://arxiv.org/abs/2506.20630 · HTML: https://mlsanity.com/paper/2506.20630/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 39 references that are in the map.
- First posted on arXiv 25 Jun 2025.

## Builds on (most cited first, 16 of 16)

- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Scientific Machine Learning through Physics-Informed Neural Networks: Where we are and What's next](https://mlsanity.com/paper/2201.05624/) (2022)
- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [Minimizing Finite Sums with the Stochastic Average Gradient](https://mlsanity.com/paper/1309.2388/) (2013)
- [Katyusha: The First Direct Acceleration of Stochastic Gradient Methods](https://mlsanity.com/paper/1603.05953/) (2016)
- [A Proximal Stochastic Gradient Method with Progressive Variance Reduction](https://mlsanity.com/paper/1403.4699/) (2014)
- [Stochastic First-order Methods for Convex and Nonconvex Functional Constrained Optimization](https://mlsanity.com/paper/1908.02734/) (2019)
- [An optimal randomized incremental gradient method](https://mlsanity.com/paper/1507.02000/) (2015)
- [A unified variance-reduced accelerated gradient method for convex optimization](https://mlsanity.com/paper/1905.12412/) (2019)
- [Iteration complexity of inexact augmented Lagrangian methods for constrained convex programming](https://mlsanity.com/paper/1711.05812/) (2017)
- [Lower Bounds for Smooth Nonconvex Finite-Sum Optimization](https://mlsanity.com/paper/1901.11224/) (2019)
- [The First Optimal Algorithm for Smooth and Strongly-Convex-Strongly-Concave Minimax Optimization](https://mlsanity.com/paper/2205.05653/) (2022)
- [An Optimal Algorithm for Decentralized Finite Sum Optimization](https://mlsanity.com/paper/2005.10675/) (2020)
- [Variance Reduction via Accelerated Dual Averaging for Finite-Sum Optimization](https://mlsanity.com/paper/2006.10281/) (2020)
- [An adaptive stochastic optimization algorithm for resource allocation](https://mlsanity.com/paper/1902.04376/) (2019)
- [Iteration complexity of first-order augmented Lagrangian methods for convex conic programming](https://mlsanity.com/paper/1803.09941/) (2018)

## Built on by (most cited first, 1 of 1)

- [Exact Reformulation and Optimization for Direct Metric Optimization in Binary Imbalanced Classification](https://mlsanity.com/paper/2507.15240/) (2025)

## Abstract (arXiv)

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 ε-expectedly feasible stochastic optimal solution, in which the expected constraint violation and expected optimality gap are both 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 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 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. As a byproduct, we also derive first-order oracle complexity results for sample average approximation method in computing an ε-SFSO solution of the stochastic optimization problem using our proposed methods to solve the sample average problem.