2023/03/28 by M. Vidyasagar, Tadipatri, Uday Kiran Reddy, Vidyasagar, Mathukumalli · 1 citation
Engineering · Mathematics · #68Q25 #68R10 #68U05 #Advanced Optimization Algorithms Research #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (stat.ML) #Numerical methods in inverse problems #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques
paper · pdf · doi:10.48550/arxiv.2303.16241
openalex publication_date 2023/03/28 · openalex created_date 2023/04/05 · openalex updated_date 2026/07/28
In this paper, we establish the convergence of the stochastic Heavy Ball (SHB) algorithm under more general conditions than in the current literature. Specifically, (i) The stochastic gradient is permitted to be biased, and also, to have conditional variance that grows over time (or iteration number). This feature is essential when applying SHB with zeroth-order methods, which use only two function evaluations to approximate the gradient. In contrast, all existing papers assume that the stochastic gradient is unbiased and/or has bounded conditional variance. (ii) The step sizes are permitted to be random, which is essential when applying SHB with block updating. The sufficient conditions for convergence are stochastic analogs of the well-known Robbins-Monro conditions. This is in contrast to existing papers where more restrictive conditions are imposed on the step size sequence. (iii) Our analysis embraces not only convex functions, but also more general functions that satisfy the PL (Polyak-Łojasiewicz) and KL (Kurdyka-Łojasiewicz) conditions. (iv) If the stochastic gradient is unbiased and has bounded variance, and the objective function satisfies (PL), then the iterations of SHB match the known best rates for convex functions. (v) We establish the almost-sure convergence of the iterations, as opposed to convergence in the mean or convergence in probability, which is the case in much of the literature. (vi) Each of the above convergence results continue to hold if full-coordinate updating is replaced by any one of three widely-used updating methods. In addition, numerical computations are carried out to illustrate the above points.