Variance-reduced First-order Methods for Finite-sum Function Constrained Convex Optimization
Abstract
This paper studies finite-sum convex optimization with convex function constraints, where both the objective f(x)=1/m∑i=1m fi(x) and the constraint mapping g(x)=1/n∑j=1n gj(x) may have a large number of components. We propose a variance-reduced anchored constraint extrapolation method (VaRAn-ConEx), which combines stochastic component sampling with primal--dual extrapolation for nonlinear function constraints. Relative to stochastic approximation schemes such as ConEx, VaRAn-ConEx~method reduces gradient complexity by using epoch-wise full-gradient correction and variance-reduced estimators for both the objective and constraint components. In the semi-finite case where n=1, the method attains gradient complexities O(√m/ε) under constant steps and O(m/ε1/2+1/ε3/2) under nonconstant steps. In the fully finite-sum case, we establish boundedness of the Lagrange multiplier sequence and derive convergence and gradient-complexity bounds for constant and nonconstant step-size policies. Under these policies, we then prove similar gradient complexity with m replaced by max{m,n}. We also show acceleration when the finite-sum objective f is strongly convex, irrespective of components fi.
Related
- Accelerated Prox-Level Methods for Unknown Piecewise-Smooth Optimization II: Function-constrained Optimization
- Adaptive Variance-Reduced Stochastic Sequential (Quadratic Constrained) Quadratic Programming
- Breaking the Shot-Noise Barrier: Cached Recycled Variance-Reduced Gradients for Quantum Optimization
- Online reduced-order modeling from primal solver trajectories for PDE-constrained optimization
- First-Order Methods for Wasserstein Distributionally Robust Constrained Optimization
BibTeX
@misc{gharehmohammadlou2026variancereduced,
title = {{Variance-reduced First-order Methods for Finite-sum Function Constrained Convex Optimization}},
author = {Yasin Gharehmohammadlou and Digvijay Boob},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.00317},
eprint = {2611.00317},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.00317},
}
RIS
TY - UNPB
TI - Variance-reduced First-order Methods for Finite-sum Function Constrained Convex Optimization
AU - Yasin Gharehmohammadlou
AU - Digvijay Boob
PY - 2026
DA - 2026/11/01
PB - arXiv
DO - 10.48550/arxiv.2611.00317
UR - https://arxiv.org/abs/2611.00317
AB - This paper studies finite-sum convex optimization with convex function constraints, where both the objective f(x)=1/m∑_i=1^m f_i(x) and the constraint mapping g(x)=1/n∑_j=1^n g_j(x) may have a large number of components. We propose a variance-reduced anchored constraint extrapolation method (VaRAn-ConEx), which combines stochastic component sampling with primal--dual extrapolation for nonlinear function constraints. Relative to stochastic approximation schemes such as ConEx, VaRAn-ConEx~method reduces gradient complexity by using epoch-wise full-gradient correction and variance-reduced estimators for both the objective and constraint components. In the semi-finite case where n=1, the method attains gradient complexities O(√m/ε) under constant steps and O(m/ε^1/2+1/ε^3/2) under nonconstant steps. In the fully finite-sum case, we establish boundedness of the Lagrange multiplier sequence and derive convergence and gradient-complexity bounds for constant and nonconstant step-size policies. Under these policies, we then prove similar gradient complexity with m replaced by max{m,n}. We also show acceleration when the finite-sum objective f is strongly convex, irrespective of components f_i.
ER -