ZEROTH-ORDER GRADIENT AND QUASI-NEWTON METHODS FOR NONSMOOTH NONCONVEX STOCHASTIC OPTIMIZATION

We consider the minimization of a Lipschitz continuous and expectation-valued function, denoted by f and defined as f(x) = E[f(x,xi)], over a closed and convex set X. Our focus lies on both deriving asymptotics as well as obtaining rate and complexity guarantees for computing an approximate stationary point (in a Clarke sense) via zeroth-order schemes. We adopt a smoothing-based approach reliant on minimizing f_eta, where f_eta(x) = E_u[f(x + etau)], u is a random variable defined on a unit sphere, and eta > 0. In fact, it has been observed that a stationary point of the eta-smoothed problem is an eta-stationary point for the original problem in the Clarke sense. In such a setting, we develop two sets of schemes with promising empirical behavior. (I) We develop a smoothing-enabled variance-reduced zeroth-order gradient framework for minimizing f_eta over X. In this setting, we make two sets of contributions for the sequence generated by the proposed zeroth-order gradient scheme. (a) The residual function of the smoothed problem tends to zero almost surely along the generated sequence, allowing for making guarantees for eta-Clarke stationary solutions of the original problem. (b) To compute an x that ensures that the expected norm of the residual of the eta-smoothed problem is within epsilon requires no greater than O(n^1/2(L₀eta^-1 + L²0)epsilon^-2) projection steps and O(n^3/2(L³0eta^-2 + L⁵0)epsilon^-4) function evaluations. (II) Our second scheme is a zeroth-order stochastic quasi-Newton scheme reliant on a combination of randomized and Moreau smoothing; the corresponding iteration and sample complexities for this scheme are O(L⁴0ⁿ²eta^-4epsilon^-2) and O(L⁹0ⁿ⁵eta^-5epsilon^-5), respectively. These statements appear to be novel in the case of both constrained problems as well as in stochastic quasi-Newton settings, as there appear to be few available results that can contend with general nonsmooth, nonconvex, and stochastic regimes via zeroth-order approaches.