# Versatile Single-Loop Method for Gradient Estimator: First and Second Order Optimality, and its Application to Federated Learning

arXiv: https://arxiv.org/abs/2209.00361 · HTML: https://mlsanity.com/paper/2209.00361/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 29 of its 52 references that are in the map.
- First posted on arXiv 1 Sep 2022.

## Builds on (most cited first, 29 of 29)

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [Federated Optimization: Distributed Machine Learning for On-Device Intelligence](https://mlsanity.com/paper/1610.02527/) (2016)
- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [Momentum-Based Variance Reduction in Non-Convex SGD](https://mlsanity.com/paper/1905.10018/) (2019)
- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [How to Escape Saddle Points Efficiently](https://mlsanity.com/paper/1703.00887/) (2017)
- [Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition](https://mlsanity.com/paper/1503.02101/) (2015)
- [SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient](https://mlsanity.com/paper/1703.00102/) (2017)
- [Minibatch vs Local SGD for Heterogeneous Distributed Learning](https://mlsanity.com/paper/2006.04735/) (2020)
- [Lower Bounds for Finding Stationary Points I](https://mlsanity.com/paper/1710.11606/) (2017)
- [PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimization](https://mlsanity.com/paper/2008.10898/) (2020)
- [Don't Jump Through Hoops and Remove Those Loops: SVRG and Katyusha are Better Without the Outer Loop](https://mlsanity.com/paper/1901.08689/) (2019)
- [FedVARP: Tackling the Variance Due to Partial Client Participation in Federated Learning](https://mlsanity.com/paper/2207.14130/) (2022)
- [Stochastic Nested Variance Reduction for Nonconvex Optimization](https://mlsanity.com/paper/1806.07811/) (2018)
- [Neon2: Finding Local Minima via First-Order Oracles](https://mlsanity.com/paper/1711.06673/) (2017)
- [Bias-Variance Reduced Local SGD for Less Heterogeneous Federated Learning](https://mlsanity.com/paper/2102.03198/) (2021)
- [ZeroSARAH: Efficient Nonconvex Finite-Sum Optimization with Zero Full Gradient Computation](https://mlsanity.com/paper/2103.01447/) (2021)
- [A Hybrid Stochastic Optimization Framework for Stochastic Composite Nonconvex Optimization](https://mlsanity.com/paper/1907.03793/) (2019)
- [SSRGD: Simple Stochastic Recursive Gradient Descent for Escaping Saddle Points](https://mlsanity.com/paper/1904.09265/) (2019)
- [Stochastic Recursive Gradient Algorithm for Nonconvex Optimization](https://mlsanity.com/paper/1705.07261/) (2017)
- [Stabilized SVRG: Simple Variance Reduction for Nonconvex Optimization](https://mlsanity.com/paper/1905.00529/) (2019)
- [Inexact SARAH Algorithm for Stochastic Optimization](https://mlsanity.com/paper/1811.10105/) (2018)
- [Efficiently avoiding saddle points with zero order methods: No gradients required](https://mlsanity.com/paper/1910.13021/) (2019)
- [An Optimal Hybrid Variance-Reduced Algorithm for Stochastic Composite Nonconvex Optimization](https://mlsanity.com/paper/2008.09055/) (2020)
- [Random-reshuffled SARAH does not need a full gradient computations](https://mlsanity.com/paper/2111.13322/) (2021)
- [Escaping Saddle Points with Bias-Variance Reduced Local Perturbed SGD for Communication Efficient Nonconvex Distributed Learning](https://mlsanity.com/paper/2202.06083/) (2022)

## Abstract (arXiv)

While variance reduction methods have shown great success in solving large scale optimization problems, many of them suffer from accumulated errors and, therefore, should periodically require the full gradient computation. In this paper, we present a single-loop algorithm named SLEDGE (Single-Loop mEthoD for Gradient Estimator) for finite-sum nonconvex optimization, which does not require periodic refresh of the gradient estimator but achieves nearly optimal gradient complexity. Unlike existing methods, SLEDGE has the advantage of versatility; (i) second-order optimality, (ii) exponential convergence in the PL region, and (iii) smaller complexity under less heterogeneity of data. We build an efficient federated learning algorithm by exploiting these favorable properties. We show the first and second-order optimality of the output and also provide analysis under PL conditions. When the local budget is sufficiently large and clients are less (Hessian-)~heterogeneous, the algorithm requires fewer communication rounds then existing methods such as FedAvg, SCAFFOLD, and Mime. The superiority of our method is verified in numerical experiments.