ANITA: An Optimal Loopless Accelerated Variance-Reduced Gradient Method

Abstract

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\ge \frac{1}{{\epsilon }^2}$, ANITA obtains the \emph{first} optimal result $O(n)$, matching the lower bound $\Omega (n)$ provided by Woodworth and Srebro (2016), while previous results are $O(n\log \frac{1}{\epsilon })$ of Varag (Lan et al., 2019) and $O(\frac{n}{\sqrt{\epsilon }})$ of Katyusha (Allen-Zhu, 2017). ii) For strongly convex finite-sum problems, we also show that ANITA can achieve the optimal convergence rate $O((n+\sqrt{\frac{nL}{\mu }})\log \frac{1}{\epsilon })$ matching the lower bound $\Omega ((n+\sqrt{\frac{nL}{\mu }})\log \frac{1}{\epsilon })$ 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.

arXiv comment23 pages

References in corpus (23)

• A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
• A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights
• SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator
• A Universal Catalyst for First-Order Optimization
• Non-convex Finite-Sum Optimization Via SCSG Methods
• Optimization with First-Order Surrogate Functions
• Acceleration for Compressed Gradient Descent in Distributed and Federated Optimization
• A Simple Proximal Stochastic Gradient Method for Nonsmooth Nonconvex Optimization
• Stochastic Nested Variance Reduction for Nonconvex Optimization
• Additional symmetries of KP, Grassmannian, and the string equation
• Virasoro Symmetry of Constrained KP Hierarchies
• An optimal randomized incremental gradient method
• A unified variance-reduced accelerated gradient method for convex optimization
• SpiderBoost and Momentum: Faster Stochastic Variance Reduction Algorithms
• Additional symmetries of KP, Grassmannian, and the string equation II
• From Additional Symmetries to Linearization of Virasoro Symmetries
• The (N,M)-th KdV hierarchy and the associated W algebra
• A Unified Analysis of Stochastic Gradient Methods for Nonconvex Federated Optimization
• Less than a Single Pass: Stochastically Controlled Stochastic Gradient Method
• An extension of the Kadomtsev-Petviashvili hierarchy and its Hamiltonian structures
• ZeroSARAH: Efficient Nonconvex Finite-Sum Optimization with Zero Full Gradient Computation
• Stabilized SVRG: Simple Variance Reduction for Nonconvex Optimization
• CANITA: Faster Rates for Distributed Convex Optimization with Communication Compression

Cited by in corpus (5)

• PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimization
• FedPAGE: A Fast Local Stochastic Gradient Method for Communication-Efficient Federated Learning
• CANITA: Faster Rates for Distributed Convex Optimization with Communication Compression
• Practical Schemes for Finding Near-Stationary Points of Convex Finite-Sums
• Accelerating Perturbed Stochastic Iterates in Asynchronous Lock-Free Optimization