A unified variance-reduced accelerated gradient method for convex optimization

• Main Authors: LAN, Guanghui, LI, Zhize, ZHOU, Yi
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2019
• Subjects: Databases and Information Systems
• Online Access: https://ink.library.smu.edu.sg/sis_research/8678; https://ink.library.smu.edu.sg/context/sis_research/article/9681/viewcontent/NeurIPS_2019_a_unified_variance_reduced_accelerated_gradient_method_for_convex_optimization_Paper.pdf
• Institution: Singapore Management University

We propose a novel randomized incremental gradient algorithm, namely, VAriance-Reduced Accelerated Gradient (Varag), for finite-sum optimization. Equipped with a unified step-size policy that adjusts itself to the value of the conditional number, Varag exhibits the unified optimal rates of convergence for solving smooth convex finite-sum problems directly regardless of their strong convexity. Moreover, Varag is the first accelerated randomized incremental gradient method that benefits from the strong convexity of the data-fidelity term to achieve the optimal linear convergence. It also establishes an optimal linear rate of convergence for solving a wide class of problems only satisfying a certain error bound condition rather than strong convexity. Varag can also be extended to solve stochastic finite-sum problems.