Private Zeroth-Order Nonsmooth Nonconvex Optimization

Abstract

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\'enyi 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.

Tasks

Reproductions