Research map / Optimization / Nonconvex and smooth optimization
The Power of Extrapolation in Federated Learning
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.
Proposes FedExProx, a server-extrapolated FedProx with constant and adaptive (gradient-diversity and stochastic Polyak) extrapolation parameters, with convergence theory in the interpolation regime for smooth convex/strongly convex problems.
Problem
FedProx averages local proximal iterates at the server, which is suboptimal; the theory of server extrapolation in federated learning is incomplete, and extrapolation parameters typically require unknown smoothness constants.
Approach
Reformulates the FedProx server update as a gradient step on the averaged Moreau envelopes with extrapolation parameter alpha acting as a server step size; derives optimal constant extrapolation from smoothness (L_gamma) and proposes two smoothness-adaptive rules (gradient diversity and stochastic Polyak) for extrapolation.
Key results
- Optimal constant extrapolation alpha = 1/(gamma L_gamma) gives iteration complexity C = L_gamma(1+gamma L_max), at least 2+1/(gamma L_max)+gamma L_max (>=4) times better than FedProx.
- Worst-case complexity of FedExProx is L_max/K versus FedExP's worst case, with speed-up up to a factor of n for full participation.
- Numerical experiments suggest FedExProx achieves at least 2x speed-up in iteration complexity over FedProx on synthetic convex problems (Figure 1).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace server averaging with optimal constant extrapolation | FedProx · Convex interpolated federated problems | iteration complexity: 2 + 1/(γLmax) + γLmax ≥ 4 | Helped |
| Use extrapolation in place of ordinary averaging | FedProx · Full participation; numerical experiment | iterations to convergence: 2× or higher | Helped |
| Use optimal constant extrapolation instead of ordinary averaging | FedProx · Figure 1 experiment, full participation | function-value suboptimality | Helped |
| Increase the participating-client batch size | FedExProx · Partial participation | iteration complexity: C (γ, n, αγ,n) = 1/nC (γ, 1, αγ,1) | Helped |
| Use adaptive gradient-diversity extrapolation | FedExProx-GraDS · Full participation, convex interpolated problems | function-value suboptimality | Mixed |
| Use adaptive stochastic-Polyak extrapolation | FedExProx-StoPS · Full participation, convex interpolated problems | function-value suboptimality | Mixed |
| Use extrapolation in the non-smooth case when γLγ=1 | FedExProx · Convex non-smooth problems | convergence: α⋆=1 | No clear effect |
Surprising findings
- Extrapolation may give no benefit in the non-smooth case when gamma L_gamma = 1 (optimal alpha = 1).
Limitations
- Analysis restricted to the interpolation regime and convex/strongly convex problems
- Non-interpolated and non-convex cases only partially covered
- Assumes exact proximal operator evaluation
Experimental setup
Metrics: function value suboptimality f(x_k)-f(x*) versus iterations
Baselines: FedProx FedExP
Builds on: FedProx FedExP Randomized Projection Method (Necoara et al. 2019) SGD with arbitrary sampling (Gower et al. 2019) stochastic Polyak step size
Closest papers by meaning
- Tighter Performance Theory of FedExProx (ICLR 2026 · similarity 0.93)
- FedExP: Speeding Up Federated Averaging via Extrapolation (ICLR 2023 · similarity 0.89)
- On Convergence of FedProx: Local Dissimilarity Invariant Bounds, Non-smoothness and Beyond (NeurIPS 2022 · similarity 0.89)
- Methods with Local Steps and Random Reshuffling for Generally Smooth Non-Convex Federated Optimization (ICLR 2025 · similarity 0.87)
- Exact and Linear Convergence for Federated Learning under Arbitrary Client Participation is Attainable (NeurIPS 2025 · similarity 0.86)
- A New Theoretical Perspective on Data Heterogeneity in Federated Optimization (ICML 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.