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

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 widetildeO( n2/varepsilon9+ n3/varepsilon7), where n=1,2,ldots is the input dimension and varepsilon>0 is the (common) tolerance. We also present extensions to weakly convex functions and applications to bilevel optimization.