Efficient Full-Matrix Adaptive Regularization

Abstract

Adaptive regularization methods pre-multiply a descent direction by a preconditioning matrix. Due to the large number of parameters of machine learning problems, full-matrix preconditioning methods are prohibitively expensive. We show how to modify full-matrix adaptive regularization in order to make it practical and effective. We also provide a novel theoretical analysis for adaptive regularization in non-convex optimization settings. The core of our algorithm, termed GGT, consists of the efficient computation of the inverse square root of a low-rank matrix. Our preliminary experiments show improved iteration-wise convergence rates across synthetic tasks and standard deep learning benchmarks, and that the more carefully-preconditioned steps sometimes lead to a better solution.

arXiv commentUpdated to ICML 2019 camera-ready version. Title of preprint was "The Case for Full-Matrix Adaptive Regularization"

Cited by in corpus (9)

• Fast Dimension Independent Private AdaGrad on Publicly Estimated Subspaces
• Disentangling Adaptive Gradient Methods from Learning Rates
• Convergence Analysis of a Momentum Algorithm with Adaptive Step Size for Non Convex Optimization
• On the Convergence of Decentralized Adaptive Gradient Methods
• M-FAC: Efficient Matrix-Free Approximations of Second-Order Information
• Public Data-Assisted Mirror Descent for Private Model Training
• Hessian Estimation via Stein's Identity in Black-Box Problems
• An Optimistic Acceleration of AMSGrad for Nonconvex Optimization
• Toward Communication Efficient Adaptive Gradient Method