Convergence Analysis of Adaptive Optimization Algorithms for High-Dimensional Machine Learning

Abstract

Optimization of high dimensional machine learning problems suffers from convergence difficulties that may stem from diversity in scales of coordinate-wise updates, stochastic gradient noise and the presence of a large number of parameter values. In the current study, we provide a convergence analysis of three popular SGD-based optimization methods—SGD, Adam, and AMSGrad—for solving high-dimensional non-convex optimization problems. The expected squared gradient norm is the main convergence metric, and the impact on parameter dimension, effective gradient sparsity, stochastic gradient variance, and adaptive parameters is analysed. A dimension-sparsity description is born as a result of breaking the symmetry between the dimension d of the ambient parameter and information on the number s of active gradient dimensions. The effective learning rate of adaptive algorithms is also analyzed coordinate-wise and investigated in the presence of various noise levels. A theoretical convergence bound is proposed in order to make a connection between the optimization error, the stochastic variance, the number of iterations, and the strong dependence on dimension; the sparse case was studied by using an effective s-dependent convergence relationship. A comparison is made between SGD, Adam, and AMSGrad under varying parameter dimensions, sparsity and noise variances using controlled experiments. The results provide a common framework for comparing the convergence in theory to optimization performance in practice for serious dimensional problems. The study does not involve a new optimizer; rather, it concentrates on already established optimization methods.