Skip to content
Preprint

Variance-reduced First-order Methods for Finite-sum Function Constrained Convex Optimization

Oct 2026 · 0 citations · 30 references
Mathematics

Abstract

This paper studies finite-sum convex optimization with convex function constraints, where both the objective $f(x)=\frac{1}{m}\sum_{i=1}^m f_i(x)$ and the constraint mapping $g(x)=\frac{1}{n}\sum_{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(\sqrt m/\epsilon)$ under constant steps and $O(m/\epsilon^{1/2}+1/\epsilon^{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$.

View source

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.