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

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 known as root-finding problems. Our first algorithm is nonaccelerated with constant step sizes and achieves a $\mathcal{O}(1/k)$ best-iterate convergence rate on $\mathbb{E}[{\Vert G{x}^k\Vert }^2]$ when the underlying operator G is Lipschitz continuous and possesses a weak Minty solution, in which $\mathbb{E}[·]$ 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 $\mathcal{O}(1/k^2)$ and $o(1/k^2)$ last-iterate convergence rates on both $\mathbb{E}[{\Vert G{x}^k\Vert }^2]$ and $\mathbb{E}[{\Vert x^{k+1}-x^k\Vert }^2]$ for this algorithm under the co-coercivity of G. In addition, we prove that the iterate sequence $\{x^k\}$ converges to a solution almost surely and $\Vert G{x}^k\Vert$ 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. We test our algorithms on four numerical examples using both synthetic and real data and compare them with related methods. Our numerical experiments show some promising performance of the proposed methods against their competitors.

Funding: This work was supported by the National Science Foundation (NSF) [Grant NSF-RTG DMS-2134107] and the Office of Naval Research [Grants N00014-20-1-2088, N00014-23-1-2588].