Third-order smoothness helps: Faster stochastic optimization algorithms for finding local minima

We propose stochastic optimization algorithms that can find local minima faster than existing algorithms for nonconvex optimization problems, by exploiting the third-order smoothness to escape non-degenerate saddle points more efficiently. More specifically, the proposed algorithm only needs O^e(ℰ-¹⁰/³) stochastic gradient evaluations to converge to an approximate local minimum x, which satisfies krf(x)k2 ≤ℰ and λmin(r²f(x)) ≥ -pℰ in unconstrained stochastic optimization, where O^e(·) hides logarithm polynomial terms and constants. This improves upon the O^e(ℰ-⁷/²) gradient complexity achieved by the state-of-the-art stochastic local minima finding algorithms by a factor of O^e(ℰ-¹/⁶). Experiments on two nonconvex optimization problems demonstrate the effectiveness of our algorithm and corroborate our theory.

Duke Scholars

Author Pan Xu Biostatistics & Bioinformatics, Division of Translational Bi ...