On computing Goldstein approximate second-order stationary points of structured nonsmooth nonconvex programs

Abstract

In this paper, we exhibit a randomized first-order algorithm to compute Goldstein approximate second-order stationary points of $L$-smooth functions, using tools from randomized smoothing. The algorithm has oracle complexity $\tilde{O}(n^2/{\epsilon }^9+n^3/{\epsilon }^7)$, where $n=1,2,\dots$ is the input dimension and $\epsilon >0$ is the (common) tolerance. We also present extensions to weakly convex functions and applications to bilevel optimization.