How to Spend Your Privacy Budget Wisely: Optimal Allocation Strategies for Differentially Private Learning

In Differentially Private Stochastic Gradient Descent (DP-SGD), privacy accounting tells us how much privacy budget has been consumed cumulatively, but it cannot answer a more critical question: how should a fixed privacy budget be allocated across iteration after iteration? A recent paper treats noise variance scheduling as an open-loop control problem and, under the constraint of zero-Concentrated Differential Privacy (zCDP), provides an optimization framework for privacy budget allocation.

The Limitations of Privacy Accounting and the Scheduling Problem

DP-SGD protects privacy by adding Gaussian noise to gradients, and privacy accounting tools (such as Rényi DP or zCDP) can precisely compute cumulative privacy loss. However, the training process often involves tens of thousands of iterations, and how the noise variance is chosen at each iteration directly affects the model's final utility.

Existing approaches typically use a fixed noise multiplier or simple decay strategies, lacking theoretical guarantees of optimality. The paper points out that under a fixed total privacy budget, the temporal scheduling of noise variance is a control problem that has not been sufficiently explored. The authors model the complete Gaussian noise variance schedule as open-loop control and explicitly incorporate the scheduling choice into the optimization under zCDP constraints.

Zero-Concentrated Differential Privacy (zCDP) is a privacy definition proposed by Bun and Steinke that constrains privacy loss through Rényi divergence. Compared with traditional (ε, δ)-DP, zCDP has two key advantages: first, it can tightly characterize the privacy loss of Gaussian mechanisms, and DP-SGD happens to use Gaussian noise; second, it has good composition properties, meaning that the privacy loss of multiple iterations can simply be added together. Under the zCDP framework, if a Gaussian mechanism satisfies ρ-zCDP, its noise variance is proportional to the square of the sensitivity and inversely proportional to ρ. The total privacy budget is usually denoted as ρ_total, and each iteration of DP-SGD consumes a portion of ρ, with the sum of ρ over all iterations constituting the total budget. It is precisely this additivity that makes it possible to model budget allocation as an optimization problem—the authors can optimize the noise variance at each iteration under the constraint that the total ρ is fixed.

Exact-Budget Simplex and the PB-AMD Algorithm

For the expected quadratic terminal tracking objective, the paper proves a key property: every local minimum exhausts the certified privacy budget. This means that the optimal schedule does not "save" budget but uses it up. As a result, the problem is transformed into an optimization over an exact-budget simplex constraint.

To solve this problem, the authors propose the Privacy-Budget Adjoint Mirror Descent (PB-AMD) algorithm. It combines pathwise adjoint gradients with entropy updates, strictly maintaining the total budget while keeping noise variance positive and satisfying the privacy budget lower bound. Theoretical analysis shows that under regularity and coercivity assumptions, the optimal schedule exists and the budget is stable, the utility from design to training is stable, and stationarity guarantees are given in the deterministic, stochastic, and sample-average senses.

The adjoint method is a classical technique for solving optimal control problems of constrained dynamical systems. For discrete-time iterative processes, the adjoint method introduces Lagrange multipliers (i.e., adjoint variables) to transform the original problem into a joint solution over the state trajectory and the adjoint trajectory. Specifically, the forward pass computes the state (model parameter) trajectory, and the backward pass computes the adjoint variables; combining the two yields the gradient of the objective with respect to the control variables (here, the noise variance). Compared with directly applying automatic differentiation to the unrolled iteration graph, the adjoint method's memory overhead scales linearly rather than quadratically with the number of iterations, making it better suited to DP-SGD scenarios with tens of thousands of iterations. The "adjoint gradients" in PB-AMD use exactly this technique to efficiently compute the gradient of the terminal tracking objective with respect to the noise variance schedule, and then combine it with the entropy update of mirror descent to ensure positivity of the noise variance and the budget constraint.

Square-Root Allocation Law and Experimental Validation

Under a linear-quadratic simplification, the paper derives an explicit square-root allocation law: the noise variance (or the allocation of privacy budget) is inversely proportional to the square root of the iteration step. This simple rule provides intuitive guidance for practical tuning—more budget can be spent early in training, and noise can be gradually reduced later.

The experimental section compares multiple allocation rules. On the tracking task, PB-AMD outperforms several baseline allocation strategies; in the learning-rate restart setting, the method shows better predictive performance than uniform allocation, while the performance of learning-rate allocation is close to it. Under the condition of achieving the same stationarity tolerance, PB-AMD's scheduling optimization time is lower than that of projected gradient descent. These results show that connecting certified privacy accounting with nonlinear training dynamics through optimization is feasible and effective.

The linear-quadratic (LQ) simplification refers to approximating the nonlinear training dynamics as a control problem with linear state transitions and a quadratic terminal cost. In the DP-SGD scheduling problem, the LQ simplification assumes that the update of model parameters depends approximately linearly on the gradient, and the terminal tracking error is measured by a quadratic form. This simplification is very standard in control theory because the LQ problem has an analytical solution that can reveal the structural properties of the optimal schedule. The paper derives the square-root allocation law precisely under the LQ simplification: the noise variance is inversely proportional to the square root of the iteration step. This rule can be intuitively understood as follows: as training approaches the terminal point, the terminal tracking objective is more sensitive to noise in later iterations, so a smaller noise variance (i.e., less privacy budget) should be allocated later, while earlier iterations can tolerate larger noise. This analytical solution also provides a theoretical benchmark for the numerical results of PB-AMD.

Implications for Privacy-Preserving Machine Learning Practice

The value of this work lies in bridging the gap between privacy accounting and training optimization. Traditionally, the privacy budget is regarded as a resource to be "saved," but the paper proves that the optimal strategy is precisely to exhaust the budget—the key is when and how to spend it. The square-root allocation law provides engineers with a plug-and-play scheduling template, while PB-AMD provides a general solver for more complex scheduling needs.

Of course, this framework currently mainly targets Gaussian noise and zCDP constraints, and relies on a quadratic terminal tracking objective. Further extension is still needed for more general loss functions and privacy definitions. But in any case, it opens a new perspective: privacy protection is no longer merely the cost of adding noise, but a control variable that can be actively optimized.

One-line Summary

The paper models DP-SGD noise variance scheduling as open-loop control under zCDP constraints, proposes the PB-AMD algorithm, and derives a square-root allocation law.

Paragraph Summary

The paper points out that existing privacy accounting can only compute cumulative privacy loss and cannot guide how to allocate a fixed privacy budget across DP-SGD iterations. The authors treat Gaussian noise variance scheduling as an open-loop control problem, establish an optimization framework under zero-Concentrated Differential Privacy (zCDP) constraints, and prove that every local minimum exhausts the privacy budget, thereby transforming the problem into exact-budget simplex optimization. To this end, they propose the PB-AMD algorithm, which combines adjoint gradients with entropy updates to ensure budget stability and stationarity. Under a linear-quadratic simplification, they derive a square-root allocation law: the noise variance is inversely proportional to the square root of the iteration step. Experiments show that PB-AMD outperforms baselines on the tracking task, and its scheduling optimization time is lower than that of projected gradient descent, bridging the gap between privacy accounting and training optimization.