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) triangleq mathbbE[tildef(x, xi)], over a closed and convex set X. We obtain asymptotics as well as rate and complexity guarantees for computing approximate Clarke-stationary points via zeroth-order schemes. We adopt an approach reliant on minimizing fη where fη(x) triangleq mathbbEuleft[x, f(x+η u), right], u is a random variable defined on a unit sphere, and η > 0. In fact, it is known that a stationary point of the η-smoothed problem is an η-stationary point for the original problem in the Clarke sense. In such a setting, we develop two schemes with promising empirical behavior. (I) We develop a variance-reduced zeroth-order gradient framework (VRG-ZO) for minimizing fη 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, guaranteeing η-Clarke stationary solutions of the original problem; (b) To compute an x such that the expected norm of the residual of the η-smoothed problem is within ε requires no greater than O(n1/2(L0η-1 +L02) ε-2) projection steps and O(n3/2(L03η-2+L05) ε-4) function evaluations. (II) Our second scheme is a zeroth-order stochastic quasi-Newton scheme (VRSQN-ZO) reliant on randomized and Moreau smoothing; the iteration and sample complexities are O(L04n2η-4ε-2) and O(L09 n5η-5ε-5), respectively.