New efficient accelerated and stochastic gradient descent algorithms based on locally Lipschitz gradient constants

This paper revisits the recently introduced stepsize in the gradient descent scheme called NGD, proposed by Hoai et al. We first investigate the NGD stepsize in conjunction with two well-known acceleration techniques: the Heavy Ball method and Nesterov's method. In the convex setting of unconstrained nonlinear optimization problems, we establish the ergodic convergence of the iterates generated by the accelerated versions of NGD at a sublinear rate. We introduce stochastic versions of the proposed accelerated algorithms and analyze their convergence in nonconvex settings. Although our proposed algorithms require global Lipschitz continuity of the gradient, we do not utilize the global Lipschitz constant during computations. Instead, we leverage information about local Lipschitz constants derived from previous iterations. Numerical experiments on various practical machine learning and deep learning problems demonstrate the efficiency of our proposed methods compared to the recent ones.