arXiv preprint ·
Optimistic Gradient Algorithms with Randomized Coordinate and Variance Reduction Strategies for Composite Inclusions
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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 $\mathcal{O}(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 $\mathcal{O}(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 $\mathcal{O}\big(n + n^{2/3}ε^{-2}\big)$ and $\mathcal{O}\big(n + n^{2/3}ε^{-1}\big)$ 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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Optimization & Control
Local Budget Benefits, Population Commitment, and Solver Performance: A DGO Case Study with Controlled DE Transfer
Non-asymptotic analysis of SGLD with discontinuous stochastic gradients: a new route to portfolio CVaR minimization
Quantum Vehicle Routing Problem: a smart initialization strategy for ill-conditioned optimization landscapes
Conic Certification of Transformer Attention
Stochastic Mirror Descent under Dependent Observations
Get the few papers worth your time in Optimization & Control every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.