How to Make the Gradients Small Privately: Improved Rates for Differentially Private Non-Convex Optimization

Jonathan Ullman, Andrew Lowy, Stephen Wright

Code that ran

We lifted 3 functions out of this paper's own repositories and ran 3 of them in a sandbox. "Ran" means the function executed on a synthesized input and returned a value. It is not a reproduction of the paper's results.

Repository	Role	Ran
lowya/how-to-make-the-gradients-small-privately	canonical	3 of 3

Function	Status	Where it lives
grad	Ran	lowya/how-to-make-the-gradients-small-privately/mod_smallgradients_trig_icml24_V3.py code served (permissive licence) · get_code("5d5c9ec5efaf2f23")
grad_norm	Ran	lowya/how-to-make-the-gradients-small-privately/mod_smallgradients_trig_icml24_V3.py code served (permissive licence) · get_code("d7244e1449bbaf90")
sample_indices	Ran	lowya/how-to-make-the-gradients-small-privately/mod_smallgradients_trig_icml24_V3.py code served (permissive licence) · get_code("ac7f91a5ccbb1c83")

Repositories linked to this paper

lowya/how-to-make-the-gradients-small-privately — marked official in Papers with Code; named in the paper

Some links come from the archived Papers with Code dataset (CC BY-SA 4.0): attribution and licence.

Abstract

We provide a simple and flexible framework for designing differentially private algorithms to find approximate stationary points of non-convex loss functions. Our framework is based on using a private approximate risk minimizer to "warm start" another private algorithm for finding stationary points. We use this framework to obtain improved, and sometimes optimal, rates for several classes of non-convex loss functions. First, we obtain improved rates for finding stationary points of smooth non-convex empirical loss functions. Second, we specialize to quasar-convex functions, which generalize star-convex functions and arise in learning dynamical systems and training some neural nets. We achieve the optimal rate for this class. Third, we give an optimal algorithm for finding stationary points of functions satisfying the Kurdyka-Łojasiewicz (KL) condition. For example, over-parameterized neural networks often satisfy this condition. Fourth, we provide new state-of-the-art rates for stationary points of non-convex population loss functions. Fifth, we obtain improved rates for non-convex generalized linear models. A modification of our algorithm achieves nearly the same rates for second-order stationary points of functions with Lipschitz Hessian, improving over the previous state-of-the-art for each of the above problems.

For agents

The same record, over MCP at https://syntology.ai/mcp:

get_harvested_code_for_paper("2402.11173")
get_code_for_paper("2402.11173")
have("2402.11173")

Connect an agent — have() is free.