Differentially Private Non-Convex Optimization under the KL Condition with Optimal Rates

We study private empirical risk minimization (ERM) problem for losses satisfying the (γ,kappa)-Kurdyka-Lojasiewicz (KL) condition. The Polyak-Lojasiewicz (PL) condition is a special case of this condition when kappa=2. Specifically, we study this problem under the constraint of ρ zero-concentrated differential privacy (zCDP). When kappa∈[1,2] and the loss function is Lipschitz and smooth over a sufficiently large region, we provide a new algorithm based on variance reduced gradient descent that achieves the rate tildeObig(big(frac√dn√ρbig)^kappabig) on the excess empirical risk, where n is the dataset size and d is the dimension. We further show that this rate is nearly optimal. When kappa ≥ 2 and the loss is instead Lipschitz and weakly convex, we show it is possible to achieve the rate tildeObig(big(frac√dn√ρbig)^kappabig) with a private implementation of the proximal point method. When the KL parameters are unknown, we provide a novel modification and analysis of the noisy gradient descent algorithm and show that this algorithm achieves a rate of tildeObig(big(frac√dn√ρbig)^frac2kappa4-kappabig) adaptively, which is nearly optimal when kappa = 2. We further show that, without assuming the KL condition, the same gradient descent algorithm can achieve fast convergence to a stationary point when the gradient stays sufficiently large during the run of the algorithm. Specifically, we show that this algorithm can approximate stationary points of Lipschitz, smooth (and possibly nonconvex) objectives with rate as fast as tildeObig(frac√dn√ρbig) and never worse than tildeObig(big(frac√dn√ρbig)1/2big). The latter rate matches the best known rate for methods that do not rely on variance reduction.