Research map / Optimization / Distributed and compressed
SILVER: Single-loop variance reduction and application to 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 SILVER, a single-loop variance-reduced gradient estimator combining SAGA and SARAH that matches optimal finite-sum nonconvex gradient complexity without periodic full gradients, and extends it to FL-SILVER with client sampling and local updates.
Problem
Variance-reduced finite-sum non-convex optimization typically needs periodic full gradient computations, which are costly and create synchronization bottlenecks in distributed and federated learning; existing single-loop methods lack optimal complexity, second-order optimality, exponential PL conver
Approach
A single-loop gradient estimator that decomposes SAGA's gradient-table approximation into sums of adjacent-step gradient differences (SARAH-style), using an auxiliary variable and sampling independence, so it attains optimal complexity, escapes saddles with small noise, converges exponentially under PL, and scales with Hessian heterogeneity ζ; applied within local-update FL with client sampling.
Key results
- SILVER's gradient estimator error is clearly smaller than SAGA's and close to SARAH's on EMNIST with n=130, while requiring no periodic full gradients.
- FL-SILVER with client sampling p≈√P (P=10^4) achieves gradient norm comparable to BVR-L-SGD (full participation) and about ten times more communication-efficient than BVR-L-SGD.
- Theoretically SILVER achieves O(n + ζ∆√n/ε²) stochastic gradient complexity (Option I), matching the optimal rate when ζ≤2L and improving with smaller Hessian heterogeneity ζ.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use SILVER (Option I) instead of a single-loop estimator without Hessian-heterogeneity speedup | finite-sum nonconvex optimization · Finite-sum nonconvex optimization | stochastic gradient complexity: n + ∆√n/ε2 -> n + ζ∆√n/ε2 | Helped |
| remove the full-gradient computation at initialization (Option II) (ablation) | SILVER · Finite-sum nonconvex optimization | stochastic gradient complexity: n + ζ∆√n/ε2 -> (ζ∆+σ2c)√n/ε2 | Mixed |
| add small noise (ablation) | SILVER · Finite-sum nonconvex optimization | test accuracy | Helped |
| add small noise (ablation) | FL-SILVER · Federated learning, second-order stationary points | test accuracy | Helped |
| allow client sampling | FL-SILVER · Federated learning, first-order stationary points | communication complexity: O(P + ζ√P/ε2) | Helped |
| reduce Hessian heterogeneity | FL-SILVER · Federated learning under PL condition | communication rounds: (L/µK + ζ√P/µp + ζ/µ + P/p) log ε−1 | Helped |
| use client sampling with p = 10 instead of full client participation | FL-SILVER · Federated learning, EMNIST capital-letter classification | communication complexity: about ten times | Helped |
Surprising findings
- Adding small noise to SILVER made test accuracy increase almost monotonically, compared with noiseless SILVER's oscillation, in the four-layer network experiment.
Limitations
- Option I requires inter-client gradient boundedness; Option II avoids full gradient but adds a σc-dependent term.
- Single-loop estimator stores a copy of x (or auxiliary variables) per component function, increasing storage cost.
- Theoretical guarantees depend on Hessian-heterogeneity assumption ζ and minibatch size conditions b ≳ √n + ζ²/δ².
Experimental setup
Datasets: EMNIST By Class
Benchmarks: EMNIST By Class
Metrics: squared gradient estimation error test accuracy gradient norm communication rounds
Baselines: SAGA SARAH SSRGD ZeroSARAH FedAvg SCAFFOLD MimeMVR BVR-L-SGD BVR-L-PSGD
Builds on: SARAH SAGA ZeroSARAH BVR-L-SGD MimeMVR
Closest papers by meaning
- Variance Reduced ProxSkip: Algorithm, Theory and Application to Federated Learning (NeurIPS 2022 · similarity 0.90)
- Federated Optimization with Doubly Regularized Drift Correction (ICML 2024 · similarity 0.88)
- Communication-Efficient Gradient Descent-Accent Methods for Distributed Variational Inequalities: Unified Analysis and Local Updates (ICLR 2024 · similarity 0.87)
- FedSMU: Communication-Efficient and Generalization-Enhanced Federated Learning through Symbolic Model Updates (ICML 2025 · similarity 0.87)
- Efficient Federated Learning against Byzantine Attacks and Data Heterogeneity via Aggregating Normalized Gradients (NeurIPS 2025 · similarity 0.87)
- Stabilized Proximal-Point Methods for Federated Optimization (NeurIPS 2024 · similarity 0.87)
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.