Research map / Optimization / Distributed and compressed

Faster Rates For Federated Variational Inequalities

NeurIPS 2026 · Optimization › Distributed and compressed · approach: Decentralized optimization algorithms · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Refines the convergence analysis of federated Local Extra SGD (LESGD) for stochastic monotone VIs and proposes LIPPAX (local inexact proximal point with extra step, plus a Gaussian-smoothing variant SLIPPAX) that removes LESGD's extra-gradient-induced 1/sqrt(K) factor, reaching LSGD-optimal rates in several regimes, including composite VIs.

Problem

Federated optimization for stochastic smooth monotone variational inequalities (and composite VIs) has convergence rates that lag behind the best known federated convex optimization (LSGD) bounds, due to client drift from the extra-gradient operator.

Approach

Refined analysis shows LESGD's rate with a 1/sqrt(K) factor, and a new local inexact proximal point method (LIPPAX) that runs several regularized SGD steps per round followed by an extra gradient step, whose proximal-point operator induces less client drift than extra-gradient; Gaussian smoothing (SLIPPAX) removes the bounded-Hessian requirement.

Key results

• LESGD refined bound O(1/(sqrt(K)R) + sigma/sqrt(MKR) + sigma^{2/3}/(K^{1/3}R^{2/3})), LSGD-optimal when sigma = Omega(1/(sqrt(R) K^{1/4})) or the operator is affine.
• LIPPAX removes the 1/(sqrt(K)R) term, achieving LSGD-optimal rate up to log factors when sigma = O(1/sqrt(KR)) under bounded Hessian or bounded operator assumptions.
• For composite VIs, the local dual averaging extension achieves O(sigma/sqrt(MKR) + 1/R^{2/3} + 1/(KR)), improving the 1/sqrt(R) term of prior work.

Surprising findings

• Extra-gradient operator can be non-co-coercive (even anti-co-coercive), causing client drift to expand and forcing a smaller step size in LESGD.

Limitations

• SLIPPAX achieves the optimal rate only up to logarithmic factors and requires a bounded operator assumption.
• Analysis restricted to the homogeneous (IID) client setting; heterogeneous case left to appendix/future work.
• Composite VI bound still contains an O(G/R^{2/3}) term independent of variance under bounded gradient assumption.

Experimental setup

Metrics: expected restricted gap / err bound as function of R, K, M,

Baselines: LESGD LSGD local dual averaging

Builds on: Local Extra SGD (LESGD) Extra Gradient Mirror-Prox Local SGD / FedAvg local dual averaging

Closest papers by meaning

• On Convergence of FedProx: Local Dissimilarity Invariant Bounds, Non-smoothness and Beyond (NeurIPS 2022 · similarity 0.89)
• Communication-Efficient Gradient Descent-Accent Methods for Distributed Variational Inequalities: Unified Analysis and Local Updates (ICLR 2024 · similarity 0.89)
• Stabilized Proximal-Point Methods for Federated Optimization (NeurIPS 2024 · similarity 0.88)
• Non-Convex Federated Optimization under Cost-Aware Client Selection (ICLR 2026 · similarity 0.88)
• What’s in a Smoothness Constant? Tight Rates for Local SGD with Bounded Second-order Heterogeneity (NeurIPS 2026 · similarity 0.88)
• Methods with Local Steps and Random Reshuffling for Generally Smooth Non-Convex Federated Optimization (ICLR 2025 · similarity 0.87)