Private Zeroth-Order Nonsmooth Nonconvex Optimization
This work addresses privacy-preserving optimization in machine learning for scenarios with non-smooth objectives, offering an incremental improvement by extending privacy guarantees to a broader class of functions.
The paper tackles private stochastic optimization for nonconvex and nonsmooth objectives by introducing a zeroth-order algorithm that ensures Rényi differential privacy and finds stationary points with a dataset size matching the optimal complexity of non-private methods, achieving privacy 'for free' under certain conditions.
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=\tildeΩ\left(\frac{d}{δε^3} + \frac{d^{3/2}}{ρδε^2}\right)$. 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 $ρ\ge \sqrt{d}ε$.