Optimistic Gradient Algorithms with Randomized Coordinate and Variance Reduction Strategies for Composite Inclusions

概要

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.

参考リンク

• Paper ↗

リンク先のライセンス・再現性・データ条件をご確認ください。自動分類や実装の目安は保証ではありません。

実装を始めるプロンプト

参考リンクを確認したうえで、次の内容をコピーして利用できます。

# 論文・記事
Optimistic Gradient Algorithms with Randomized Coordinate and Variance Reduction Strategies for Composite Inclusions

# 概要
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…

# 原典
https://arxiv.org/abs/2611.00334

上記の手法を実装してください。実行前に依存関係とライセンスを確認してください。