Metraipolis › archive › dc_7fadfe4e4c57

Variance-reduced First-order Methods for Finite-sum Function Constrained Convex Optimization — arXiv:2611.00317

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.00317
License (as archived)
CC0-1.0
Archived
2026-11-03T18:44:44.071Z
SHA-256 of the archived text
7efd801bcbef01b92c706ed7b49786951b8beef2343860081d28e71a8c682dae
Stable URL of this page
https://metraipolis.com/documento/dc_7fadfe4e4c57

How to cite

Variance-reduced First-order Methods for Finite-sum Function Constrained Convex Optimization — arXiv:2611.00317 — arXiv (en), https://arxiv.org/abs/2611.00317 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_7fadfe4e4c57 (Metraipolis archive dc_7fadfe4e4c57, sha256 7efd801bcbef01b92c706ed7b49786951b8beef2343860081d28e71a8c682dae)
BibTeX
@misc{dc7fadfe4e4c57,
  title = {Variance-reduced First-order Methods for Finite-sum Function Constrained Convex Optimization — arXiv:2611.00317},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.00317},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_7fadfe4e4c57; sha256 7efd801bcbef01b92c706ed7b49786951b8beef2343860081d28e71a8c682dae},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.00317. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.OC, nuovi lavori del giorno).
Categorie arXiv: Optimization and Control (math.OC).
Pagina del lavoro: https://arxiv.org/abs/2611.00317 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-03T18:14:37.741Z dalla pagina https://arxiv.org/list/math.OC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).