Private Zeroth-Order Nonsmooth Nonconvex Optimization

We introduce a new zeroth-order algorithm for private stochastic optimization on nonconvex and nonsmooth objectives. Given a dataset of size M , our algorithm ensures (α, αρ 2 /2)-Rényi differential privacy and finds a (δ, ǫ)-stationary point so long as M = Ω d δǫ 3 + d 3/2 ρδǫ 2 . This matches the optimal complexity of its non-private zeroth-order analog. Notably, although the objective is not smooth, we have privacy "for free" whenever ρ ≥ √ dǫ. Our algorithm incorporates four essential components, each crucial for achieving the optimal rate. We leverage the non-private Online-to-non-convex Conversion (O2NC) framework by Cutkosky et al. (2023), which finds a (δ, ǫ)-stationary point of a non-smooth objective using a firstorder oracle. We then build an approximate first-order oracle (i.e. a gradient estimator) with a zerothorder oracle. Although this high-level strategy is a common technique, our approach distinguishes itself through its gradient oracle design. In contrast to prior non-private approaches that directly approximate the gradient with a standard zeroth-order estimator (Kornowski & Shamir, 2023), we introduce a variance-reduced gradient oracle. Our approach incorporates two zeroth-order estimators: one for the gradient and another for its difference between two points. Our gradient oracle also differs subtly from the standard zeroth-order estimator by sampling d i.i.d. estimators for each data point, which is required to achieve the optimal dimension dependence. Both estimators exhibit reduced sensitivity. We reduce the privacy cost of our variance-reduced estimators by using the "tree mechanism" (Dwork et al., 2010; Chan et al., 2011) , yielding a new state-of-the-art privacy guarantee.