Reproduce “On the Inherent Privacy of Zeroth Order Projected Gradient Descent” on OpenResearch

About this paper

Devansh Gupta, Meisam Razaviyayn, Vatsal Sharan

Researchers at the University of Southern California established that the inherent stochasticity of widely used zeroth-order gradient estimators does not provide differential privacy for projected gradient descent algorithms, even with random initialization and hidden intermediate states. Their analysis demonstrates that explicit additive noise remains a necessity, as privacy loss can grow superlinearly with the number of iterations.

Key insights

• The inherent randomness of widely used zeroth-order gradient estimators is insufficient to provide differential privacy guarantees, as demonstrated by scenarios where an adversary can perfectly distinguish between neighboring datasets.
• Explicit additive noise is necessary for ZO optimization algorithms to achieve differential privacy, even when considering only the final model output and using fixed initialization.
• Privacy loss in ZO-GD can accumulate superlinearly with the number of iterations, even with random initialization and without revealing intermediate states, indicating that the inherent stochasticity does not offer meaningful privacy protection.

Summary by alphaXiv.