Optimization Papers

High-probability convergence of adaptive, proximal, and clipped Adam-type methods for nonconvex stochastic optimization

Zhu and Huang

A unified high-probability analysis gives the normalised adaptive gradient method, and Adam under a momentum-alignment condition, the standard nonconvex rate with only a logarithmic cost in the confidence level \(\delta\).

Filed under Optimization, Probability

The paper studies smooth nonconvex stochastic optimisation when the gradient noise has a sub-Gaussian norm. Using an adaptive descent decomposition with Freedman and Bernstein inequalities, it shows that the normalised adaptive gradient method reaches the standard nonconvex complexity with an additional term logarithmic in \(1/\delta\), inversely proportional to the number of iterations.

The same guarantee is proved for the full adaptive moment method under an explicit momentum-alignment condition, and the analysis is extended to projected and proximal updates through a subdifferential-distance stationarity measure, to objectives satisfying the Polyak–Łojasiewicz condition, and to heavy-tailed noise through truncation.