Faster Rates For Federated Variational Inequalities
This work addresses a specific bottleneck in federated learning for variational inequalities, offering incremental improvements in convergence rates for researchers in optimization and distributed systems.
The paper tackles the gap in convergence rates between federated variational inequalities (VIs) and federated convex optimization by establishing improved rates, including a new algorithm (LIPPAX) that mitigates client drift and achieves better guarantees in various settings.
In this paper, we study federated optimization for solving stochastic variational inequalities (VIs), a problem that has attracted growing attention in recent years. Despite substantial progress, a significant gap remains between existing convergence rates and the state-of-the-art bounds known for federated convex optimization. In this work, we address this limitation by establishing a series of improved convergence rates. First, we show that, for general smooth and monotone variational inequalities, the classical Local Extra SGD algorithm admits tighter guarantees under a refined analysis. Next, we identify an inherent limitation of Local Extra SGD, which can lead to excessive client drift. Motivated by this observation, we propose a new algorithm, the Local Inexact Proximal Point Algorithm with Extra Step (LIPPAX), and show that it mitigates client drift and achieves improved guarantees in several regimes, including bounded Hessian, bounded operator, and low-variance settings. Finally, we extend our results to federated composite variational inequalities and establish improved convergence guarantees.