  We consider the problem of minimizing a non-convex objective while preserving
the privacy of the examples in the training data. Building upon the previous
variance-reduced algorithm SpiderBoost, we introduce a new framework that
utilizes two different kinds of gradient oracles. The first kind of oracles can
estimate the gradient of one point, and the second kind of oracles, less
precise and more cost-effective, can estimate the gradient difference between
two points. SpiderBoost uses the first kind periodically, once every few steps,
while our framework proposes using the first oracle whenever the total drift
has become large and relies on the second oracle otherwise. This new framework
ensures the gradient estimations remain accurate all the time, resulting in
improved rates for finding second-order stationary points.
  Moreover, we address a more challenging task of finding the global minima of
a non-convex objective using the exponential mechanism. Our findings indicate
that the regularized exponential mechanism can closely match previous empirical
and population risk bounds, without requiring smoothness assumptions for
algorithms with polynomial running time. Furthermore, by disregarding running
time considerations, we show that the exponential mechanism can achieve a good
population risk bound and provide a nearly matching lower bound.
