ANITA: An Optimal Loopless Accelerated Variance-Reduced Gradient Method
This work provides an optimal solution for large-scale finite-sum optimization, impacting areas like distributed and federated learning, though it is incremental in improving upon existing methods.
The paper tackles the fundamental finite-sum optimization problem by proposing ANITA, a novel accelerated gradient method that achieves optimal convergence rates for both general convex and strongly convex settings, with results like O(n) matching lower bounds and faster convergence than previous state-of-the-art methods in experiments.
In this paper, we propose a novel accelerated gradient method called ANITA for solving the fundamental finite-sum optimization problems. Concretely, we consider both general convex and strongly convex settings: i) For general convex finite-sum problems, ANITA improves previous state-of-the-art result given by Varag (Lan et al., 2019). In particular, for large-scale problems or the convergence error is not very small, i.e., $n \geq \frac{1}{ε^2}$, ANITA obtains the \emph{first} optimal result $O(n)$, matching the lower bound $Ω(n)$ provided by Woodworth and Srebro (2016), while previous results are $O(n \log \frac{1}ε)$ of Varag (Lan et al., 2019) and $O(\frac{n}{\sqrtε})$ of Katyusha (Allen-Zhu, 2017). ii) For strongly convex finite-sum problems, we also show that ANITA can achieve the optimal convergence rate $O\big((n+\sqrt{\frac{nL}μ})\log\frac{1}ε\big)$ matching the lower bound $Ω\big((n+\sqrt{\frac{nL}μ})\log\frac{1}ε\big)$ provided by Lan and Zhou (2015). Besides, ANITA enjoys a simpler loopless algorithmic structure unlike previous accelerated algorithms such as Varag (Lan et al., 2019) and Katyusha (Allen-Zhu, 2017) where they use double-loop structures. Moreover, we provide a novel \emph{dynamic multi-stage convergence analysis}, which is the key technical part for improving previous results to the optimal rates. We believe that our new theoretical rates and novel convergence analysis for the fundamental finite-sum problem will directly lead to key improvements for many other related problems, such as distributed/federated/decentralized optimization problems (e.g., Li and Richtárik, 2021). Finally, the numerical experiments show that ANITA converges faster than the previous state-of-the-art Varag (Lan et al., 2019), validating our theoretical results and confirming the practical superiority of ANITA.