A Full Adagrad algorithm with O(Nd) operations

2024/05/03 by Godichon-Baggioni, Antoine, Lu, Wei, Portier, Bruno
#FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (stat.ML) #Statistics Theory (math.ST)

paper · doi:10.48550/arxiv.2405.01908

Abstract

A novel approach is given to overcome the computational challenges of the full-matrix Adaptive Gradient algorithm (Full AdaGrad) in stochastic optimization. By developing a recursive method that estimates the inverse of the square root of the covariance of the gradient, alongside a streaming variant for parameter updates, the study offers efficient and practical algorithms for large-scale applications. This innovative strategy significantly reduces the complexity and resource demands typically associated with full-matrix methods, enabling more effective optimization processes. Moreover, the convergence rates of the proposed estimators and their asymptotic efficiency are given. Their effectiveness is demonstrated through numerical studies.

Related

• Scalable Adaptive Stochastic Optimization Using Random Projections
• Non asymptotic analysis of Adaptive stochastic gradient algorithms and applications
• Dynamic Low-rank Approximation of Full-Matrix Preconditioner for Training Generalized Linear Models
• Stability and convergence analysis of AdaGrad for non-convex optimization via novel stopping time-based techniques
• Adaptive Gradient Descent for Convex and Non-Convex Stochastic Optimization