Optimal privacy spending improves private learning efficiency and accuracy
When to spend privacy: optimal allocation in private learning
Machine LearningArtificial Intelligence
Summary
Training machine learning models privately means adding noise to protect user data, but deciding how much noise to add in each step is tricky. The authors propose a way to figure out the best way to distribute a set privacy budget over all training steps to get the best learning results. They create a new method called Privacy-Budget Adjoint Mirror Descent that finds these optimal schedules efficiently and prove it works under certain conditions. Tests show this approach beats simple methods of dividing the privacy budget evenly across training.
What this means in practice
- •For machine learning engineers: Improve privacy-utility tradeoffs by optimally allocating privacy budgets during private model training.
- •For data privacy teams: Manage cumulative privacy loss more efficiently to meet strict privacy guarantees while maintaining model accuracy.
Authors
Umberto Biccari, Yongcun Song
Abstract
Privacy accounting bounds the cumulative privacy cost of Differentially Private Stochastic Gradient Descent but does not determine how to allocate a fixed budget across iterations. We formulate the complete Gaussian noise-variance schedule as an open-loop control under a composed zero-Concentrated Differential Privacy constraint, explicitly accounting for schedule selection. For expected quadratic terminal tracking, we prove that every local minimizer exhausts the certified budget, yielding an exact-budget simplex formulation. We introduce Privacy-Budget Adjoint Mirror Descent (PB-AMD), combining pathwise adjoint gradients with entropic updates that preserve positivity, charge floors, and the prescribed budget. Under regularity and coercivity assumptions, we establish existence and budget stability of optimal schedules, design-to-training utility stability, and deterministic, stochastic, and sample-average stationarity guarantees. A linear-quadratic reduction yields an explicit square-root allocation law. Experiments demonstrate tracking improvements over several allocation rules and predictive improvements over uniform allocation in a learning-rate restart setting, where learning-rate allocation performs similarly. Comparisons at a common stationarity tolerance show lower schedule-optimization times than projected gradient descent on the tested problems. The framework connects certified privacy accounting with optimization through nonlinear training dynamics.