When to spend privacy: optimal allocation in private learning

Umberto Biccari; Yongcun Song

cs.LGOct 29, 2026

When to spend privacy: optimal allocation in private learning

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.

Figures & tables

Approach	Temporal allocation	Joint schedule optimization	Terminal criterion	Privacy-valid selection	Schedule construction
[ 24 ]	Yes	No	No	Yes	Adaptive private line search
[ 19 ]	Yes	Yes	Upper bound	–	Analytical minimization of a utility bound
[ 10 ]	Yes	No	No	–	Prescribed clipping and noise schedules
[ 34 ]	Indirect	No	Validation	Yes	A priori privacy-utility parameter selection
Present work	Yes	Yes	Expected terminal loss	Yes	Terminal-loss optimization through nonlinear dynamics with exact-budget updates

Table 1. Comparison with representative approaches to temporal privacy allocation.

Panel of Figure 1 — Figure 1. Conceptual roadmap of the paper.

Notation	Meaning
$\mathbb{N}$	$\{1,2,\ldots\}$
$\llbracket q\rrbracket$ , $\llbracket q\rrbracket_{0}$	$\{1,\ldots,q\}$ and $\{0,\ldots,q-1\}$ , respectively, with $q\in\mathbb{N}$
$\llbracket q\rrbracket^{\leftarrow}$ , $\llbracket q\rrbracket^{\leftarrow}_{0}$	indices in $\llbracket q\rrbracket$ and $\llbracket q\rrbracket_{0}$ taken in reverse order, i.e., $q,\ldots,1$ and $q-1,\ldots,0$
$\left\\|\cdot\right\\|_{1}$ , $\left\\|\cdot\right\\|_{2}$ , $\left\\|\cdot\right\\|_{\infty}$	$\ell^{1}$ , $\ell^{2}$ and $\ell^{\infty}$ norms on $\mathbb{R}^{n}$ , respectively, with $n\in\mathbb{N}$
$\left\langle\cdot,\cdot\right\rangle$ , $\left\\|\cdot\right\\|_{\rm op}$	Euclidean inner product and induced operator norm
$I_{n}$	$n\times n$ identity matrix

Table 2. Summary of some notation employed in the paper.

Assumptions	Main role	Main results requiring them
(A1) - (A2)	Basic stochastic dynamics and moment control	Continuity of $J$ , basic control formulation Theorems 3.2 , 3.8 ; Propositions 3.4 , B.3 , B.5
(A3)	Integrability and continuity of the terminal objective
(A4) - (A5)	Coercivity and compactness of minimizing sequences	Existence and compactness of minimizers Proposition B.5 ; Theorems 3.8 , 3.9
(A6)	First-order sensitivity analysis	Adjoint gradient, KKT conditions, privacy-charge gradient Propositions 3.4 , 3.7 , Theorem 3.5 , Corollary 3.6
(A7)	Second-order regularity for optimization	Smoothness estimates needed for PB-AMD convergence Proposition C.1

Table 3. Analytical assumptions and the results in which they are used.

Panel of Figure 2 — Figure 2. Workflow of PB-AMD.

Task	Model and initialization	Parameters trained and perturbed	Learning rate
Tabular	Regularized logistic regression on generated data with correlated features and nonlinear feature interactions in the data-generating model	All model parameters	Constant
Fashion-constant	Softplus classifier on Fashion-MNIST, initialized randomly	All network parameters	Constant
Fashion-restart	Softplus classifier on Fashion-MNIST, pretrained on public data	All network parameters	Increased at a prescribed restart
Nonlinear head	Randomly initialized Softplus classifier applied to features from an extractor pretrained on public Fashion-MNIST data	Classification head only; the extractor is frozen	Constant

Table 4. Learning tasks, initialization, trainable parameters, and learning-rate settings.

Rule	Allocation principle
Uniform	Assigns $q_{t}=\rho_{\max}/T$ , providing the reference for assessing redistribution
Learning-rate allocation (LR)	Uses weights $w_{t}=\eta_{t}$ , isolating learning-rate scaling from subsequent training dynamics
Decay	Combines learning-rate scaling with subsequent regularization shrinkage alone
Linearized	Uses $w_{t}=\sqrt{a_{t}}$ with $a_{t}$ from ( 4.13 ), $W_{T}=\mathrm{Id}$ , and Jacobians evaluated along the public-design No-noise reference
Geometric	Uses $w_{t}=\eta_{t}e^{\gamma t/(T-1)}$ , with $\gamma$ selected by mean tracking error on public-design data

Table 5. Baseline allocation rules compared with PB-AMD under a common certified privacy budget.

Figure 3. Single-instance exact-budget schedules at

\rho_{\max}=0.5

. LR coincides with Uniform in (a,b); the vertical dotted line in (c) marks the learning-rate restart.

	$\rho_{\max}=0.5$		$\rho_{\max}=0.25$
Comparator	Error reduction [95% CI]	Wins	Error reduction [95% CI]	Wins
LR	$7.72\ [6.03,9.41]$	$10/10$	$4.32\ [3.55,5.09]$	$10/10$
Decay	$7.85\ [6.15,9.55]$	$10/10$	$4.41\ [3.63,5.18]$	$10/10$
Linearized	$5.07\ [-2.10,12.23]$	$8/10$	$2.75\ [0.35,5.15]$	$7/10$
Geometric	$3.32\ [2.59,4.04]$	$10/10$	$2.16\ [1.77,2.56]$	$10/10$

Table 6. Nonlinear-head training: mean paired PB-AMD tracking-error reductions (%) on private training data relative to each comparator, with unadjusted

95\%

confidence intervals. Wins counts seeds with lower PB-AMD tracking error, out of ten per budget.

Figure 4. Nonlinear-head allocation: (a) instance-level PB-AMD tracking-error reductions relative to Linearized on private training data, for two independent groups of ten seeds; (b,d) schedules for instances A and B, selected as the largest-gain examples at their respective budgets, with charges divided by the uniform charge. Uniform and LR coincide; (c) PB-AMD-to-Linearized error ratios for the two fixed schedules in instance A on public-design data, comparing the reference linearized prediction with full nonlinear evaluation using fresh Gaussian paths. Positive reductions in (a) and ratios below one in (c) favor PB-AMD.

Figure 5. Test performance for Fashion-restart models trained on private data: means and pointwise

95\%

confidence intervals over ten problem seeds. Each noise schedule uses

256

Gaussian training runs per seed.

Figure 6. Solver convergence on public-design instances at

\rho_{\max}=0.5

: median normalized gap

G_{F_{M}}(q)/F_{0}

from ( 4.11 ), with inter-quartile bands over ten convergence instances per task. The horizontal dotted line is the

10^{-4}

timing target.

Appendix figures & tables6 assets

Supplementary material from the paper’s appendix.

Appendix

Task	Parameters	$T$	$b$	Learning rate $\eta_{t}$	$C_{\rm clip}$	$\lambda_{\rm reg}$
Tabular	64	60	256	$0.18$	$4$	$0.002$
Fashion-constant	6634	45	192	$0.15$	$1.75$	$10^{-4}$
Fashion-restart	6634	45	192	$0.02/0.075$	$1.75$	$10^{-4}$
Nonlinear head	86	120	384	$1$	$1$	$10^{-4}$

Appendix

Table 7. Training configurations. The restart uses

0.02

for

t<25

and

0.075

for

t\geq 25

, with

t=0,\ldots,T-1

Task	Optimization	Public validation	Private evaluation
Tabular	256	512	512
Fashion-constant/restart	8	48	256
Nonlinear head	128	256	512

Appendix

Table 8. Gaussian path counts for allocation-quality studies. The public diagnostic in Figure 4(c) also uses

512

independent paths.

Task	PB-AMD step	Minimum/fixed updates	PGD stepsize grid
Tabular	$0.005$	$180$	$\{3\cdot 10^{-5},10^{-4},3\cdot 10^{-4},10^{-3}\}$
Fashion-constant	$0.0005$	$100$	$\{3\cdot 10^{-6},10^{-5},3\cdot 10^{-5},10^{-4}\}$
Fashion-restart	$0.005$	$100$	$\{3\cdot 10^{-6},10^{-5},3\cdot 10^{-5},10^{-4}\}$

Appendix

Table 9. Utility solver settings. PB-AMD checks the KKT tolerance after the listed minimum update count; PGD and penalty use the listed fixed count.

$\beta$	1	3	10	100	1000	10000
Tabular Adam stepsize	$.04$	$.04$	$.035$	$.025$	$.015$	$.008$
Full-network/head Adam stepsize	$.035$	$.032$	$.025$	$.017$	$.01$	$.006$

Appendix

Table 10. Penalty candidates. Each column specifies one pair of penalty weight and Adam stepsize, not a Cartesian-product grid.

Figure 7. Raw penalty charge divided by the prescribed budget: medians and ranges over three budgets and ten seeds. Ratios above the dashed line at one violate the prescribed budget.

Check	Value	Scope
Maximum fixed-path KKT residual	$5.00\times 10^{-5}$	$90$ returned schedules
Maximum budget error after mirror updates	$2.22\times 10^{-16}$	$90$ PB-AMD runs
Relative objective gap to water-filling	$7.67\times 10^{-16}$	One LQ instance

Appendix

Table 11. Stationarity of the returned schedules for

F_{M}

, budget preservation, and agreement with the analytical LQ objective.

Differentially Private Stochastic Gradient Descent

Differentially private stochastic gradient descent (DP-SGD) protects training data by clipping per-example gradients, adding calibrated noise, and accounting for privacy loss.

See all 53 papers

Adaptive Methods Are Preferable in High Privacy Settings: An SDE Perspective
Mar 3, 2026Enea Monzio Compagnoni, Alessandro Stanghellini, Rustem Islamov +2Differentially Private Stochastic Gradient Descent Differential Privacy
University of Basel, Switzerland · University of Zürich, Switzerland
Efficient privacy loss accounting for subsampling and random allocation
Feb 19, 2026Vitaly Feldman, Moshe ShenfeldDifferential Privacy Privacy-Utility Tradeoff
Apple · The Hebrew University of Jerusalem · *Work partially done while author was an intern at Apple.
Private Decentralized Optimization with Noise Reduction and Bias Correction
Sep 23, 2026Yizhao Fan, Wenjian Luo, Jiaojiao ZhangDifferential Privacy Variance Reduction
Harbin Institute of Technology, Shenzhen · Great Bay University

Mar 3, 2026J/K move · Enter open · S save

Adaptive Methods Are Preferable in High Privacy Settings: An SDE Perspective

Enea Monzio Compagnoni, Alessandro Stanghellini, Rustem Islamov, Aurelien Lucchi+1

University of Basel, Switzerland · University of Zürich, Switzerland

Differentially Private Stochastic Gradient Descent Differential Privacy Adaptive Gradient Methods

Open paper AskPDF arXiv

Differential Privacy (DP) is becoming central to large-scale training as privacy regulations tighten. We revisit how DP noise interacts with adaptivity in optimization through the lens of stochastic differential equations, providing the first SDE-based analysis of private optimizers. Focusing on DP-SGD and DP-SignSGD under per-example clipping, we show a sharp contrast under fixed hyperparameters: DP-SGD converges at a Privacy-Utility Trade-Off of

\mathcal{O}(1/\varepsilon^2)

with speed independent of

\varepsilon

, while DP-SignSGD converges at a speed linear in

\varepsilon

with an

\mathcal{O}(1/\varepsilon)

trade-off, dominating in high-privacy or large batch noise regimes. By contrast, under optimal learning rates, both methods achieve comparable theoretical asymptotic performance; however, the optimal learning rate of DP-SGD scales linearly with

\varepsilon

, while that of DP-SignSGD is essentially

\varepsilon

-independent. This makes adaptive methods far more practical, as their hyperparameters transfer across privacy levels with little or no re-tuning. Empirical results confirm our theory across training and test metrics, and empirically extend from DP-SignSGD to DP-Adam.

Abstract

Differentially Private Stochastic Gradient Descent

Explore similar work

Adaptive Methods Are Preferable in High Privacy Settings: An SDE Perspective

Efficient privacy loss accounting for subsampling and random allocation

Private Decentralized Optimization with Noise Reduction and Bias Correction