2018/05/31 by Michael B. Cohen, Cohen, Michael B., Jelena Diakonikolas +3 · 1 citation
Computer Science · Engineering · Mathematics · #Acceleration #Algorithm #Artificial intelligence #Computer science #Convergence (economics) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Generality #Machine Learning and ELM #Machine learning #Noise (video) #Optimization and Control (math.OC) #Physics #Scale (ratio) #Simplicity #Sparse and Compressive Sensing Techniques #Stability (learning theory) #Stochastic Gradient Optimization Techniques #Variance (accounting) #cs.DS #math.OC
paper · pdf · doi:10.48550/arxiv.1805.12591
Appeared in Proc. ICML'18; v2 corrects the statement of Corollary 3.9; v3 added references to concurrent work
openalex publication_date 2018/05/31 · arxiv created 2018/07/31 · arxiv updated 2018/08/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Accelerated algorithms have broad applications in large-scale optimization, due to their generality and fast convergence. However, their stability in the practical setting of noise-corrupted gradient oracles is not well-understood. This paper provides two main technical contributions: (i) a new accelerated method AGDP that generalizes Nesterov's AGD and improves on the recent method AXGD (Diakonikolas & Orecchia, 2018), and (ii) a theoretical study of accelerated algorithms under noisy and inexact gradient oracles, which is supported by numerical experiments. This study leverages the simplicity of AGDP and its analysis to clarify the interaction between noise and acceleration and to suggest modifications to the algorithm that reduce the mean and variance of the error incurred due to the gradient noise.