# Randomized Block-Coordinate Optimistic Gradient Algorithms for Root-Finding Problems

arXiv: https://arxiv.org/abs/2301.03113 · HTML: https://mlsanity.com/paper/2301.03113/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 42 of its 105 references that are in the map.
- First posted on arXiv 8 Jan 2023.

## Builds on (most cited first, 30 of 42)

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Federated Optimization in Heterogeneous Networks](https://mlsanity.com/paper/1812.06127/) (2018)
- [Federated Learning: Challenges, Methods, and Future Directions](https://mlsanity.com/paper/1908.07873/) (2019)
- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Federated Optimization: Distributed Machine Learning for On-Device Intelligence](https://mlsanity.com/paper/1610.02527/) (2016)
- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [Coordinate Descent Algorithms](https://mlsanity.com/paper/1502.04759/) (2015)
- [Training GANs with Optimism](https://mlsanity.com/paper/1711.00141/) (2017)
- [Minimax Pareto Fairness: A Multi Objective Perspective](https://mlsanity.com/paper/2011.01821/) (2020)
- [A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach](https://mlsanity.com/paper/1901.08511/) (2019)
- [Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization](https://mlsanity.com/paper/2011.00364/) (2020)
- [Fairness-aware Agnostic Federated Learning](https://mlsanity.com/paper/2010.05057/) (2020)
- [Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems](https://mlsanity.com/paper/1808.02901/) (2018)
- [Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with O(1/k2) Rate on Squared Gradient Norm](https://mlsanity.com/paper/2102.07922/) (2021)
- [Fast Extra Gradient Methods for Smooth Structured Nonconvex-Nonconcave Minimax Problems](https://mlsanity.com/paper/2106.02326/) (2021)
- [Halpern Iteration for Near-Optimal and Parameter-Free Monotone Inclusion and Strong Solutions to Variational Inequalities](https://mlsanity.com/paper/2002.08872/) (2020)
- [Error bounds, quadratic growth, and linear convergence of proximal methods](https://mlsanity.com/paper/1602.06661/) (2016)
- [FedNest: Federated Bilevel, Minimax, and Compositional Optimization](https://mlsanity.com/paper/2205.02215/) (2022)
- [Federated Minimax Optimization: Improved Convergence Analyses and Algorithms](https://mlsanity.com/paper/2203.04850/) (2022)
- [A Forward-Backward Splitting Method for Monotone Inclusions Without Cocoercivity](https://mlsanity.com/paper/1808.04162/) (2018)
- [Simple and optimal methods for stochastic variational inequalities, I: operator extrapolation](https://mlsanity.com/paper/2011.02987/) (2020)
- [A Three-Operator Splitting Scheme and its Optimization Applications](https://mlsanity.com/paper/1504.01032/) (2015)
- [Accelerated Schemes For A Class of Variational Inequalities](https://mlsanity.com/paper/1403.4164/) (2014)
- [FedDR -- Randomized Douglas-Rachford Splitting Algorithms for Nonconvex Federated Composite Optimization](https://mlsanity.com/paper/2103.03452/) (2021)
- [Projected Reflected Gradient Methods for Monotone Variational Inequalities](https://mlsanity.com/paper/1502.04968/) (2015)
- [Solving Nonconvex-Nonconcave Min-Max Problems exhibiting Weak Minty Solutions](https://mlsanity.com/paper/2201.12247/) (2022)
- [Accelerated, Parallel and Proximal Coordinate Descent](https://mlsanity.com/paper/1312.5799/) (2013)
- [ARock: an Algorithmic Framework for Asynchronous Parallel Coordinate Updates](https://mlsanity.com/paper/1506.02396/) (2015)

## Built on by (most cited first, 9 of 9)

- [Stochastic Halpern iteration in normed spaces and applications to reinforcement learning](https://mlsanity.com/paper/2403.12338/) (2024)
- [Variance Reduced Halpern Iteration for Finite-Sum Monotone Inclusions](https://mlsanity.com/paper/2310.02987/) (2023)
- [Revisiting Inexact Fixed-Point Iterations for Min-Max Problems: Stochasticity and Structured Nonconvexity](https://mlsanity.com/paper/2402.05071/) (2024)
- [Unbiased and Biased Variance-Reduced Forward-Reflected-Backward Splitting Methods for Stochastic Composite Inclusions](https://mlsanity.com/paper/2603.15576/) (2026)
- [An Inexact Halpern Iteration with Application to Distributionally Robust Optimization](https://mlsanity.com/paper/2402.06033/) (2024)
- [Revisiting Extragradient-Type Methods -- Part 1: Generalizations and Sublinear Convergence Rates](https://mlsanity.com/paper/2409.16859/) (2024)
- [A Class of Accelerated Fixed-Point-Based Methods with Delayed Inexact Oracles and Its Applications](https://mlsanity.com/paper/2512.13547/) (2025)
- [Extragradient-Type Methods with O (1/k) Last-Iterate Convergence Rates for Co-Hypomonotone Inclusions](https://mlsanity.com/paper/2302.04099/) (2023)
- [Polyak-Type Extragradient Methods for Monotone Root-Finding Problems](https://mlsanity.com/paper/2609.26581/) (2026)

## Abstract (arXiv)

In this paper, we develop two new randomized block-coordinate optimistic gradient algorithms to approximate a solution of nonlinear equations in large-scale settings, which are called root-finding problems. Our first algorithm is non-accelerated with constant stepsizes, and achieves O(1/k) best-iterate convergence rate on mathbbE[ Vert GxkVert2] when the underlying operator G is Lipschitz continuous and satisfies a weak Minty solution condition, where mathbbE[·] is the expectation and k is the iteration counter. Our second method is a new accelerated randomized block-coordinate optimistic gradient algorithm. We establish both O(1/k2) and o(1/k2) last-iterate convergence rates on both mathbbE[ Vert GxkVert2] and mathbbE[ Vert xk+1 - xkVert2] for this algorithm under the co-coerciveness of G. In addition, we prove that the iterate sequence xk converges to a solution almost surely, and kVert GxkVert attains a o(1/k) almost sure convergence rate. Then, we apply our methods to a class of large-scale finite-sum inclusions, which covers prominent applications in machine learning, statistical learning, and network optimization, especially in federated learning. We obtain two new federated learning-type algorithms and their convergence rate guarantees for solving this problem class.