Efficient Full-Matrix Adaptive Regularization

2018/06/08 by Agarwal, Naman, Bullins, Brian, Chen, Xinyi +4
#FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.1806.02958

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.

Related

• A Scalable, Adaptive and Sound Nonconvex Regularizer for Low-rank Matrix Completion
• Dynamic Low-rank Approximation of Full-Matrix Preconditioner for Training Generalized Linear Models
• Sketchy: Memory-efficient Adaptive Regularization with Frequent Directions
• Adaptive First- and Second-Order Algorithms for Large-Scale Machine\n Learning
• Low Rank Regularization: A Review