Optimistic Gradient Algorithms with Randomized Coordinate and Variance Reduction Strategies for Composite Inclusions
Abstract
In this paper, we consider a class of possibly nonmonotone finite-sum composite inclusions in which evaluating all components or updating all coordinates at every iteration can be computationally expensive. We develop two optimistic gradient frameworks that combine variance reduction with randomized block-coordinate updates. The first framework applies under a blockwise average Lipschitz continuity condition and the existence of a weak-Minty solution. It achieves an 𝒪(1/k) convergence rate for the expected squared residual, and its iterates converge almost surely under mild additional conditions. The second framework relies on a backward-forward reformulation under average co-coercivity and co-hypomonotonicity. It achieves faster 𝒪(1/k2) and o(1/k2) rates for the expected squared residual, as well as o(1/k2) almost-sure rates. For both frameworks, we provide a generic condition on the stochastic estimator that covers mini-batch, loopless SVRG, and a generalized JacSketch-type estimator, and we derive the corresponding oracle complexities under importance-based block sampling. In particular, in highly heterogeneous regimes, the L-SVRG and JacSketch variants attain 𝒪(n + n2/3ε−2) and 𝒪(n + n2/3ε−1) oracle complexities for the nonaccelerated and accelerated methods, respectively. Numerical experiments illustrate the effects of variance reduction and block-coordinate sampling, and compare the proposed methods with existing baselines.
Related
- Inexact Proximal Point and Tseng Algorithms with Nonsummable Errors to Solve Monotone Inclusions
- Accelerated Convergence of a Second-Order Dynamical System and its Application to Splitting Algorithms for Comonotone Inclusions
- Accelerated Algorithms for Stochastic Monotone Inclusions with Fixed Queries
- Continuous-time analysis and algorithms for linear and convex quadratic programs via exactly solvable differential inclusions
- Distributed Fast Fixed-Point Algorithms for Composite Monotone Inclusions over Networks
BibTeX
@misc{nguyentrung2026optimistic,
title = {{Optimistic Gradient Algorithms with Randomized Coordinate and Variance Reduction Strategies for Composite Inclusions}},
author = {Nghĩa Nguyen-Trung and Ion Necoara and Quoc Tran-Dinh},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.00334},
eprint = {2611.00334},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.00334},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Optimistic Gradient Algorithms with Randomized Coordinate and Variance Reduction Strategies for Composite Inclusions
AU - Nghĩa Nguyen-Trung
AU - Ion Necoara
AU - Quoc Tran-Dinh
PY - 2026
DA - 2026/11/01
PB - arXiv
DO - 10.48550/arxiv.2611.00334
UR - https://arxiv.org/abs/2611.00334
AB - In this paper, we consider a class of possibly nonmonotone finite-sum composite inclusions in which evaluating all components or updating all coordinates at every iteration can be computationally expensive. We develop two optimistic gradient frameworks that combine variance reduction with randomized block-coordinate updates. The first framework applies under a blockwise average Lipschitz continuity condition and the existence of a weak-Minty solution. It achieves an 𝒪(1/k) convergence rate for the expected squared residual, and its iterates converge almost surely under mild additional conditions. The second framework relies on a backward-forward reformulation under average co-coercivity and co-hypomonotonicity. It achieves faster 𝒪(1/k^2) and o(1/k^2) rates for the expected squared residual, as well as o(1/k^2) almost-sure rates. For both frameworks, we provide a generic condition on the stochastic estimator that covers mini-batch, loopless SVRG, and a generalized JacSketch-type estimator, and we derive the corresponding oracle complexities under importance-based block sampling. In particular, in highly heterogeneous regimes, the L-SVRG and JacSketch variants attain 𝒪(n + n^2/3ε^−2) and 𝒪(n + n^2/3ε^−1) oracle complexities for the nonaccelerated and accelerated methods, respectively. Numerical experiments illustrate the effects of variance reduction and block-coordinate sampling, and compare the proposed methods with existing baselines.
ER -