Faster Rates for Federated Variational Inequalities

Summary

This paper studies federated optimization for solving stochastic variational inequalities (VIs), a field with growing attention but a significant performance gap compared to federated convex optimization. The authors address this gap by establishing a series of improved convergence rates. They first refine the analysis of the classical Local Extra SGD algorithm, providing tighter guarantees for smooth and monotone VIs. However, they identify an inherent limitation of Local Extra SGD: excessive client drift. To overcome this, they propose the Local Inexact Proximal Point Algorithm with Extra Step (LIPPAX), which mitigates drift and achieves better rates under bounded Hessian, bounded operator, and low-variance regimes. The work also extends these improved guarantees to federated composite variational inequalities.

Takeaways

1. 1

   Improved convergence rates for federated stochastic variational inequalities are established, narrowing the gap to federated convex optimization bounds.

2. 2

   Local Extra SGD suffers from excessive client drift in federated VI settings, which limits its performance.

3. 3

   The proposed LIPPAX algorithm mitigates client drift and yields better convergence guarantees under bounded Hessian, operator, and low-variance conditions.

FAQ