Adaptive Hyperparameter Selection for Differentially Private Gradient Descent
Authors: Dominik Fay
Sindri Magnússon
Jens Sjölund
Mikael Johansson
Venue: Accepted by TMLR ()

Abstract: We present an adaptive mechanism for hyperparameter selection in differentially private optimization that addresses the inherent trade-off between utility and privacy. The mechanism eliminates the often unstructured and time-consuming manual effort of selecting hyperparameters and avoids the additional privacy costs that hyperparameter selection otherwise incurs on top of that of the actual algorithm.

We instantiate our mechanism for noisy gradient descent on non-convex, convex and strongly convex loss functions, respectively, to derive schedules for the noise variance and step size. These schedules account for the properties of the loss function and adapt to convergence metrics such as the gradient norm. When using these schedules, we show that noisy gradient descent converges at essentially the same rate as its noise-free counterpart.  Numerical experiments show that the schedules consistently perform well across a range of datasets without manual tuning.

Published in Transactions on Machine Learning Research (09/2023)
Adaptive Hyperparameter Selection for Differentially Private Gradient Descent
Dominik Fay
dominikf@kth.cc
Division of Decision and Control Systems KTH Royal Institute of Technology
Elekta
Sindri Magnússon
Snndri.mognussonddds.....
Deportment of Computer and Systems Sciences Stockholm Universily
Jens Sjölund
Lens.sjobundSkt.co
Department of Information Technology
Uppsala University
Mikael Johansson
makkelj@kkll.s
Division of Decision and Control Systems
KTH Rogal Institute of Technology
Reviewed on OpenReview: https: // openreview. net/ forum? id= LLXI5LL@2)
Abstract
We present an adaptive mechanism for hyperparameter selection diffcrentially private op- limization that addresses the inherent trade-off between utility and privacy. The mechanism eliminates the often unstructured and time-consuming manual effort of selecting hyperpa- rameters and avoids the additional privacy costs that hyperparameter selection otherwise incurs on lop of that of the actual algorithm.
We instantiate our mechanism for noisy gradient descent on non-convex, convex and strongly convex loss functions, respectively, to derive schedules for the noise variance and step size. These schedules account. for the properties of the loss function and adapt to convergence metrics such as the gradient norm. When using these schedules, descent converges at essentially the same rate as its noisc-frce counterpart. Numerical experiments show that the schedules consistently perform well across range of datasets without manual tuning.
show that noisy gradient
1 Introduction
In tandem with the successes of machine learning, driven in particular by ever larger and more data-hungry neural networks, there is mounting concern over privacy among both policymakers and the general public. Researchers have noticed, and the last few years have witnessed intense efforts at reconciling the competing demands of privacy and utility. A major line of work has focused on modifying the optimization procedure to obtain guarantees on differential privacy. These all face the question of how lo distribule the privacy budgel to achieve marimum utility? Typically, addressing this question boils down to the selection of hyperparameters that control the privacy-utility tradcoff. But ultimately finding reasonable values for these has, so far, been largely left as an exercise for the reader. In addition being mone-consuming, manual hyperparameter tuning also incurs extra (sometimes neglected) privacy cost top of the actual algorithm.

---

Published in Transactions on Machine Learning Research (09/2023)
Differential privacy (DP) and empirical risk minimization (ERM) two key concepts in the field of privacy- preserving machine learning. The prototypical algorithm for DP-ERM is Noisy Stochastic Gradient. Descent [Song et al. 2013 Bassily et al.) 2014 variants of which have been successfully applied in various domains such as medical imaging (Kaissis et al. 2021 Ziller et al. 2021 Adnan et al.) 2022) and large language models McMahan et al. 2018): Basu et. al. (2021).
). The standard result for excess empirical risk d dimensions and a sample size N that achieves O (()))(NN) for convex losses (Bassily et al., 2014), and ((d/(uN22)) for Lipschitz-smooth j-strongly convex losses (Kifer et al. 2012) under (e, 6)-PP. These bounds are worst- case optimal, i.e. they match known lower bounds (Bassily et al. 2014). Although they can be achieved with a uniform privacy budget allocation, a number of recent works have provided empirical evidence that adaptive schedules can improve performance on more typical machine learning problems, such as generalized linear problems and deep learning Lee & Kifer 2018 Song et al. 2020 Zhang el. al. 2021 Mohapalra et al. 2022
The main hyperparameters for Noisy SGD are the step size and the noise scale, i.c., the amount of random noise added to each gradient update. Common approaches for selecting hyperparamelerss for differentially private algorithms include differentially private model selection from private candidates via grid search (Yu
ct al. 2019 or search with random stopping (Liu & Talwar 2019 Papernot & Steinke 2022 Koskela & Kulkarni 2023) as well as Bayesian optimization (Avent et al., 2020j. However, these approaches are
generally time-consuming and incur an additional privacy cost. In this work, we propose a simple strategy for hyperparameter selection that avoids both the additional computational cost and the privacy cost. In summary, our contributions are as follows:
1. We propose conceptual framework for tuning time-van varying hyperparameters by optimizing, each step, the primacy-utility ratio (PUR).
2. We derive schedules for Lipschitz-smooth losses, showing that the optimal noise variance is propor- lional to the squared gradient norm. We specialize the schedules to non-convex, convex and strongly convex cases. contrast to existing works on noisy gradient methods, the proposed schedules attain the same convergence speed as their noise-free counterparts.
3. To obtain rigorous privacy guarantees, we upper bound the gradient norm to derive data-ind iatta-indepeddent versions of the above schedules while retaining the same convergence rate as the data data-dependent ones.
Experiments across multiple datasets show that our schedules are least as good as using an optimally tuned constant noise variance, even when the privacy cost of hyperparameter tuning is ignored.
The remainder of the paper is organized as follows: In Section on convex optimization and differential privacy. In Section 3 we introduce our framework for adaptive hyperparameter selection, and present our theoretical results. We show a summary of our theoretical results in Tables I and - We complement this with experimental results in Section [ and discuss our results in Section 5 together with suggestions for future work. We conclude with discussion of related work in
2 we provide some necessary background
Section 0 Additional numerical results and proofs are provided in Appendices A and respectively.
2
Background
We begin by defining core concepts from convex analysis and then summarize main results from differential privacy that we later use in our analysis.
Convex optimization In convex optimization we typically consider functions that have one or more of the following three properties:
Definition 1 (L-Lipschitz continuity). A function f C + R is L-Lisschitz continuous if
(f()) f(x) Tlly - xll for all x, C.
2

---

Published in Transactions on Machine Learning Research (09/2023)
Definition 2 (u-strong convexity). A differentiable function f C R is p-strongly conver if
f(y) 2 f(x) + (Vf(z), -z) 2 2||² for all z, C.
Definition 3 (M-smoothness). A differentiable function f C R M-smooth if
M f(y) f(z) + (V 2) 1g z||² for all 2, z,y E.
Note that if function f differentiable and I-Lipschitz, then gradient norm bounded by L. f is additionally convex then its gradient is Lipschitz-continuuus. Likewise, if f is convex and M-smooth then it is also L-Lipschitz (Boyd & Vandenberghe 2014). However, in either case, the best known bound on M (or L) for any particular function f may be stronger than the bound implied by L (or M, respectively).
Differential privacy The form of privacy we ultimately want to achieve is (e, 8)-differential privacy, which is defined formally as follows.
Definition ((difiirirrrtttii privacy (Doork et al. 2006)). Let ~x be a symmetric relation on a set X. A randomized function M X + Y is - -differentially private if for all x ~xx x' and all measurable S SYY
Pr[M(x) e S) E E
Most differential privacy mechanisms are based on bounding the influence of individual data points on the output of a function, which captured by the notion of sensitivity.
Definition (Sensitivity). Let ~x be a symmetric relation on set X. The sensitivily of function f:X-1 + Y with respect to ~x is defined
A sup 2~xx'
11(x))
In this work, we take the ~xx to be the replacement relation, i.e. x ~xx x' x' is obtained from x by replacing one data entry with another. Of particular interest to ERM the arithmetic mean f(z zN) 1/N Σn. In defined over a bounded convex set which has scnsitivity A D/N where maxg,zed lly 2|| is the diameter of C.
In the context of differential privacy, random perturbation of deterministic function f(x) is referred to mechanism M(x). In particular, we focus the Gaussian mechanism M(x; fx) + Ç where inde- pendent and identically distributed Gaussian noise Ç ~ (0 is added to the output of a deterministic function f-
Apart from (c, oddifferentl privacy, several variants of differential privacy have emerged that better cater the characteristics of more restricted classes of noise distributions, In particular, the properties of the Gaussian mechanism well-described by zero-concentrated differential privacy.
Definition 6 (Zero-concentrated differential privacy (Bun & Steinke, 2016 Let -x be symmetrie relation on set X. A randomized function M: : X + Y is p-2CDP if for all x'xx,
(a(M())) M((()) ap for all a>
where Da is the Rényi divergence of order a.
Specifically, the Gaussian mechanism with variance o² satisfies p-zCDP for p A/(20²) where A is the sensitivity of f. The Gaussian mechanism also satisfies (c, DD for <> 2 and < 1.
A convenient. properly of zCDP is that composition is linear, in other words, an adaptive sequence of mechanisms (,,) jointly satisfies p-zCDP if each M, satisfies pcD2DD and = Σ; P.P. A reference for the above claims relating to (c, and p>CCDP can be found in c.g. Dwork Roth (2014) and Bun & Steinke (2016), respectively. A comparison between the various notions of differential privacy can be found in Desfontaines & Pejó (2020).
3

---

Published in Transactions on Machine Learning Research (09/2023)
Excess loss
Iterations
Tocal gradient evaluations
Bassily et al.
(2014)
dlor' n NN
N²
N
Wang et al. (017)
log Ne va
Nr Vd
NE N log
N
d
Ours
C
N V/
22N2:
DN
Table 1: Comparison of DP-ERM algorithms for convex, Lipschitz, Lipschitz-smooth loss functions. The first column refers to the excess empirical risk. The second and third column refer to the number of iter- coaonnaiaassss nceded to achieve the loss listed in the first column. All entries are upper bounds and should be read as (()) where the Lipschitz constant L, Lipschitz-smoothuss constant M and the second privacy parameter are treated as constants. When given, it refers guarantee terms of p-zCDP instead of (e, oD- The dependence on is stated for the "high-privacy" regime (e + 0). For the "low- privacy" regime (e + oc), replace e² with c.
Excess loss
Iterations
Local gradient evaluations
Bassily et al.
(2014)
logg N N422
N
N2
Wang et al.
(017))
dlogg N N=
log
N²2 d
N log Ne d
Hong ct al.
2022)
Nºp log d
Vog
Nºp d'
N
Ours
log(cN2)
N N)
2 :
N
Lower bound
N22a
Table 2: Comparison DP-ERM algorithms for strongly convex, Lipschitz, Lipschitz-smooth loss functions. The first column refers to the excess empirical risk. The second and third column refer to the number of iterations/ iterations/evaluation evaluatioos needed to achieve the loss listed in the first column. All entries except for the last row upper bounds and should be read O(-) where the Lipschitz constant L, Lipschitz-smootthness constant M, strong convexity constant the second privacy parameter 5 are treated as constants. When p is given, it refers to a guarantec in terms of p-2CDP instead of (c, 8)DP. The dependence on is stated for the "high-privacy" regime (e - 0). For the "low-privacy" regime (e + oo), replace e² with e.
3 Adapting Hyperparameters to the Privacy-Utility Ratio
We consider the problem of differentially private empirical risk minimization (DP-ERM). That is, we want to minimize the empirical risk
F(0) N Σ f(0; n
(1)
over a parameter vector 0 E R for a dataset. æ,, EN E X, under the constraint that 0 preserve (e, 8)- differential privacy. To this end, we revisit the differentially private gradient descent (DP-GD) algorithm, which consists of noisy gradient steps
441 ( + G~
(2)
with time-varying step sizes T/t and noise variances of.

---

Published in Transactions on Machine Learning Research (09/2023)
3.1
Main Idea
The main idea is to select the step size in and noise standard deviation o, that, at each step, minimize the privacy loss per unit of utility improvement. We call this the privacy-utility ratio (PUR) and define it as
PUR(a.. - P(o))
u))
for suitably chosen functions U( qe) and P(az) corresponding, respectively, to utility improvement and privacy cost. The utility function can incorporate convergence information such as the gradient norm objective value. Thereby, minimizing the PUR allows us to adapt the privacy budget to the optimization progress. For instance, we might expect that later stages the optimization require higher precision since, typically, the gradient norm tends to zero as we approach the optimum.
We measure the utility improvement U( ne) via a descent lemma that bounds the expected loss improve- ment in the next iteration, which can be derived from analytical properties of the loss function F. Although, the associated privacy cost P(a,) is independent of the step size Ta, its exact form depends the variant of differential privacy we choose to apply. Again, we ultimately want to ascertain (e, (e.f)-diiffrenniall privacy, which permits simple expression for the privacy cost, see Section 3.2
Based on the above choices of utility and privacy, we derive step-wise optimal schedules for selecting the hyperparameters (8) and o²) and analyze their convergence rates. In Section 3.3 we first consider the setting where the utility improvement depends directly on convergence information such as the gradient norm. This is, however, an idealized setting since the gradient norm itself is data-dependent and hence sensitive information. In order to overcome this limitation, in Section 3.4 replace this dependence with bound to arrive at a data-independent schedule. Curiously, our analysis shows that the data-independent schedule attains essentially the same convergence rate as the data-dependent one.
3.2 Privacy cost
Our approach to deriving a privacy cost function is based on the (e, 6)-DP privacy cost of the Gaussian mechanism under a Lipschitz assumption on the loss function, which is a common approach in the literature (Sogg et al. 2013: Bassily et al., 2014). If the example-level loss f(: :.,,) is I-Lipschitz for all ans then it follows from Equation that the full gradient V of the empirical risk has sensitivity 2L/N. Therefore, by the classical analysis of the Gaussian mechanism, 0.-1 computed via Equation [rom O, preserves (e, O)DP
for any
2L <1
ot V 2 logg01220000))
Ne
Note that the constraint < 1 only needs to be satisfied for individual iterations. As long as reasonable ("single-digit") total privacy budget is imposed, it is unlikely that we violate this constraint, given that we can expect to perform a large number of iterations. For the sake of tractability, we choose to drop the constraint and define our privacy cost function as
P(at) = C
with 12loc=/lloo((e (2log(1.256-1) 2L
(4)
We emphasize that the constraint is enforced in our subsequent privacy analysis, it is only dropped while we develop a suitable heuristic.
3.3 Data-dependent selection
We use the assumption that F M-smooth to formulate a descent lemma for estimating the expected improvement in the objective function for a given stop-size and noise variance. Specifically, for a single update step, we have the following result:
Lemma 1. Let F be M-smooth. If Bst1 is computed via Equation
then
(FF( - F(0++1) 10, 2 1)t
[VF(
do? 2
(5)
5

---

Published in Transactions on Machine Learning Research (09/2023)
We use the lower bound the expected improvement from Lemma | as utility function,
M |FF())]
M
Uo Ne: 0
1)
2 ni
2 n/
Note that the need to evaluate the gradient norm
[|F makes this function data dependent.
Equippod with this utility function and the privacy cost from Equation can find the hyperparameters that minimize the privacy-ulility ralio. The result is caplured by the following proposition:
Proposition 1 (Data-dependent schedule). The Priuacy-uiility ratio PUR(o,, me) is minimized by
VF()0)) and Y) 2M
1
Ot =
Vd
(6)
There multiple observations worth highlighting about this schedule:
First, it is remarkably simple the step size is constant and the noise standard deviation is directly proportional to the gradient norm. The reason for the former is that the optimal step size for an arbitrary d, depends on the "signal-to-noise ratio" || (F.)) (see Equation 12 When the noise standard deviation is proportional to the gradient norm, the signal-to-noise ratio is constant and therefore the optimal step size is constant.
Second, most of the prior work differentially private gradient crasient-based optimization considers decaying step size and constant noise variance. In contrast, Proposition suggests that the roles should be reversed the step size should be constant and the noise variance should be decaying.
Third, the schodule is independent of the privacy parameters and 6, which means that the chosen privacy budget determines the time horizon T. Again, this contrasts with prior work which fixes the time horizon T and scales the noise variance to meet the privacy budget.
Finally, the schedule is data dependent, because the gradient norm [|F(()))] is required to compute the noise standard deviation. This is not particularly surprising given that we allowed the expected utility improvement U to depend on 0r, but it has an important practical implication: The schedule itself exhibits a privacy leakage that must be accounted for. This is the subject of Section 3.4
Before moving on to the inteeinnd schedule, we first state the convergence rate of the algorithm when using the above schedule, assuming oracle access to the gradient norm ||FF(())]
Proposition 2 (Data-dependent convergence rate). Let F be M-smooth and 0s+1 be computed recursively vio Equation with 17 1/(2M) and o = [VF then
(a) for (possibly) non-convez F,
T T
4M (F((o) - F*)
E
[VF(0))
(7)
T
(b) if F is conver and the ilerates salisfy 1|0 0 < R
4M R
[(F()r) Fd1 -
(8)
T
(c) if F is p-stroogly convex,
<<11111101 (1- 2M
E (
(F(0n) F*),
(9)
where Ft is the minimal empirical risk.

---

Published in Transactions on Machine Learning Research (09/2023)
The convergence rates remarkably close to those for the non-private gradient descent algorithm: for convex losses, the convergence rate is (1/(() in both cases. For strongly convex losses, it is O(r*) where == - p/M in the non non-private case and r = - m/(MM) in the private case, meaning that the private version only needs approximately twice as many iterations to reach the same accuracy. This is because log(1 - 11/M) ~ 2 log(1 μ/(2M)), unless M/μ is very small.
3.4 Data- Data-independen selection
In this section, we derive a dala-innepenneent version of the PUR-optimal schedule and analyze its conver- gence. In summary, the main results are that the data-independent schedule (a) converges at essentially the same rate as the data-dependent schedule in terms of iterations, and (b) has similar privacy-utility conver- gence as recent work on strongly convex losses (Hong et al. 2022 while additionally permitting an upper bound on non-convex and (non-strongly) convex losses.
We begin by deriving the data-independent schedule. Recall from Proposition that the PUR-optimal schedule og at time t is proportional to the gradient norm |[. Proposition 2 shows that this schedule exhibits essentially the same convergence rate as non-private GD. While this bound is stated terms of excess risk, similar results are known for the gradient norm in non-private GD: the gradient norm converges at rate of O(1/t) for convex losses and O(r") for strongly convex losses, where = p/M. The idea for data-inee inteiindeeenddntt schedule is then to use these upper bounds proxy for the gradient norm itself. This leads to the following result.
Proposition (Data-in) inteeedddeeendentt convergence rate). Let F be M-smooth and 0,41 computed via Equation with T): 1/(2M), then
(a) if oz
4M / F"
Vdt
1 T
IVF(0))1
8(7 (Fo,)) - F*)
E
3T
(b) if F conver, az
4MR dd
and the ilerates salisfy 100, 0-1l S R
[[F(OT) F*] 16M It
3T
(c) if F p-strongly convex and a, (F((0)) F*) (1 H/(2M))*/d,
(1F(0T)-F"1 (1- 2M ) (F(00)-17)
(10)
where F* is the minimal empirical risk.
Remarkably, the data-independent schedule achieves the same convergence rate as the data-dependent sched- ule, up to small multiplicative factor.
Having removed the data dependence, we are now able to analyze the privacy loss of the algorithm. The analysis follows standard arguments: Each iteration has constant sensitivity, and the noise variance from Proposition 3 is such that releasing the noisy gradient satisfies ((")-2CCDP and ((1/rr))-ZCDPP, respectively in the convex and strongly convex cases. Accumulating the privacy loss across T iterations, and combining the result with Proposition 3 yields the following proposition.
Proposition 4 (Privacy-utility convergence). Let F be M-smooth and f be L-Lipschite. If ff41 is computed vio Equation with 1/ = 1/(2M), then the iterates 0,,..., jointly satisfy (r.5)-DP. In particular,
(a) if 0:
4M /M/FFOR F( ddt
then, after T M - (+)/(I iterations,
T
8
2
+1)
(F(0o) - F2d 8pN2M² M2
E
V
VF))1
T
3
3

---

Published in Transactions on Machine Learning Research (09/2023)
(b) F is convez,
4 it and the iterates satisfy ||0,- 181-811 I R, then, after T - 8pN2M R (L'dd Vät
ileralions,
L2MRd
[[ F7] - -
3
pN2
(c) if F is H-strongly convex and ot = (2 - F*) (1 -1 (/22))/ then, after log (u(F(())-F"") (10g 2x-1) iterations,
2d12
E [FF(OT) - 5 Ltd
(11)
N2
where M/p.
Here, F" is the minimal empirical risk and p +-+2 2 1ogg-11
The upper bound strongly convex losses is optimal, in the sense that it is the same order known lower bounds (Bassily et al., 2014). In contrast to previous work that also achieved this (Hong et al. 2022 we additionally have an upper bound on convex and non-convex losses. Note that the convex upper bound scales with V/ pNz- This because the privacy loss grows as O(T3) while the excess loss, even in the non-private case, only decreases as (1/TT).
We provide comparison between Proposition 4 and results from previous work in Tables aadd in terms of simplified order bounds.
4 Experiments
We evaluate the performance of the proposed hyperparameter schedules synthetic and real-world datasets, convex and strongly convex loss functions. The primary purpose of our experiments is to verify whether the proposed antomatic hyperparameter selection can consistently outperform hyperparameters found via exhaustive search.
Loss function
We consider regularized logistic regression
f(0: Zn. Un) = log (1 exp(-yn2,, 0)) + 11012
with feature vectors nn {z Rd || < 2} and labels yn {-1,1} and regularization parameter
A M 0. The corresponding empirical risk F is convex, L-Lipschitz and M Mssmooth with XR + Z and M A + Z /4, where R is upper bound on ||0 ll If X > 0 then F is also X-strongly convex.
We compare the privacy-utility performance of our adaptive, data-independent schedules (cf. Proposition to that of the constant schedule o, = a for a wide range of values of a E {0.001, 0.01, 0.1, 1.0). Furthermore, we include a non-gradin grrddiettddeseeeee baseline, namely output perturbation, which first solves the optimization problem non-privately via an arbitrary solver and then adds noise to the solution. In particular, we use the black-box output perturbation algorithm for convex, Lipschitz ERM objectives from Lowy & Razaviyayn 22021, Algorithm 6). Finally, we also show the hypothetical privacy-utility performance of the data-dependent schedule (Equation 6), assuming oracle access to the gradient norm.
Baselines
Regarding the data-inden iata-inndeen schodule, note that the regularization paramcter À determines which sched- ule we apply: The schedule for strongly convex losses is used when X > 0, and the schedule for convex losses for À = 0. We use the same step size = 1/(2M) in all runs. The privacy cost is computed in the same way for all gradient perturbation methods: The per-iteration costs are aggregated via zCDP composition, 1.1/N)ddifeerentia privacy. For output perturbation, we use the privacy analysis of
and then converted
Lowy & Razaviyayn 2021
8

---

Published in Transactions on Machine Learning Research (09/2023)
=
0.1
10a
Adaptive (independent) Adaptive (dependent)
10
0=0,001
0.01
||
o= 0.1
10
1.0
10 -
10 -4
10
10a
Adaptive (independent)
Adaptive (dependent)
0.001
0= 0.01
0.1
0= 1.0
10
10 2
5
10
15
20
0
5
10
15
20
Figure 1: Convergence of the gradient plotted against privacy expenditure for various noise schedules. The lines shown are the median of 120 repetitions. The shaded area is the inter-quartile range. Some schedules exceed the maximum number iterations before reaching e = 20. The data-dependent schedule assumes oracle access the gradient norm. Top: Synthetic datasct. Bottom: Iris dataset. Left column: Convex objective (A = 0). Right column: Strongly convex objective (A 0.1).
Adaptive
10a
constant
Output perturbation
F(8) -10)=F+ Fx
10a
10
0
2
8
10
E
Figure 2: Excess loss for the CIFAR-10 dataset with ScatterNet features. Best constant refers to the constant schedule with best noise variance in hindsight. The shaded area is the inter-quartile range.
Datasets We repeat our experiments on six different datasets. All datasets are preprocessed such that the feature vectors 2n have mean and unit variance.

---

Published in Transactions on Machine Learning Research (09/2023)
We generate synthetic data for binary classification problem follows: The feature vectors 2n are drawn independently from multivariate Normal distribution in (0, Σ) with covariances Eij for * j and En = 2. The labels yn are generated as follows: Nn Zn Bernoulli(p) if
(Zn, 1) I 0, otherwise N., Zn ~ Bernoulii -p). We generate N = 10* examples with = 2 and p = 0.1.
The CIFAR-10 dataset (Krizhevsky 2009 Chapter 3) consists of = 60,000 images of size 3072 in 10 classes. We consider binary classification task: We set N. for the class "airplane", and Yn -1 for all others.
The MNIST dataset (LeCun al. 1998) consists of N 60,000 images of handwritten digits of size d 784. We consider binary version of this task: We set y, 1 for the digit 0, and yn - for all others.
The Iris dataset (iisher 1936) contains data of N 150 examples of Tris flowers characterized by d = numerical attributes. We consider the task of distinguishing Tris Sctosa (y,. = 1) from Iris Versicolour and Iris Virginica (y, = -1).
The UCT ML Breast Cancer Wisconsin Diagnostic dataset (uua & Grafi 2017 henceforth "Breast cancer", contains data for a binary classification task. It consists of = 569 examples (357 negative, 212 positive) with 30 numerical features correspouding to various measurements of tumors. We y, 1 for malignant tumors, and yn -1 for benign tumors.
The KDD Cup '99 (Bay al. 2000) dataset contains data for an intrusion detection task. It consists of 699,691 data with d = 4 attributes, of which 0.3% anomalies (y,, = 1). We sub-sample the dataset to N 70,000.
ScatterNet features In addition to the raw features, we also consider features extracted by a Scattering Network (ScatterNet) (Oyallon Mallat] 2015). ScatterNet features have recently been demonstrated be highly effective for differentially private image classification (Tramer & Boneh 202I). ScatterNet is an expansive, Wavelet-based transform that extracts features of size (C 81, H/4,W channels, width W and height H.
W/4 W/4) from images with C
Results First, we compare our adaptive schedules for DP-GD to constant schedules. We show the con- vergence of the gradient norm as a function the privacy expenditure in Figure [ for two datasets (rows) and two loss functions (columns). The plots are obtained by tracking the cumulative privacy cost across the iterations of the algorithm. The lines shown are the median of 120 repetitions. Recall that for the data- the assumption that the gradient. norm is available show the empirical risk at two privacy levels for all datasets in Table 3
dependent schedule, the privacy cost is caleulated privacy cost. Furthermore, The Best constant column shows the risk of the constant schedule with the best noise variance known in hindsight. The Ours column refers to the data-independen schedule.
0.1.1 0.1
20
Ours
Best constant
Ours
Best constant
Synthetic MNIST
0.5090
0.5307
0.5087
0.5087
1.0058
0.9449
0.6510
0.5822
Iris
0.6465
0.6809
0.2778
0.2782
Breast Cancer
1.1656
0.8651
0.2399
0.2437
KDD Cup '99
0.5864
0.5914
0.5401
0.5402
Table 3: Empirical risk for various datasets. Best constant refers to the constant schedule with best noise variance in hindsight. Lower value highlighted in bold.
Next, we compare to output perturbation on the CIFAR-10 dataset with ScatterNet features using le reg- ularization with 10. The excess risk at various privacy levels shown in Figure g The encess with respect to the regularized non-private solution. Best constont again refers to the constant schedule with best noise variance in hindsight.
10

---

Published in Transactions on Machine Learning Research (09/2023)
5 Discussion and Future Work
In this work, we have proposed the PUR as a criterion select time-varying hyperparameters in differen- tially private iterative optimization algorithms. The PUR can be computed from descent lemma, that is, a bound on the per-step objective improvement, and the per-step privacy loss associated with the selected hy- perparameters. We have instantiated this framework for DP-GD on non-convex, convex and strongly convex functions, respectively. In this setting, the PUR-optimal hyperparameters achieve the same convergence rate as non- non-private GD in terms of iterations, and, in the case of strong convexity, also the optimal privacy-utility convergence. In the case of non-strongly convex functions, the privacy-utility convergence we have been able to establish is suboptimal. This might not be limitation of PUR in general, but rather a consequence of choosing GD as the optimization algorithm. It is known that SGD has substantial privacy benefits over GD via privacy amplification by sub-sampling (Bassily et al. 2014) and by iteration (Feldman et al. 2020). and we expect that the PUR framework can be applied to these algorithms as well.
In general, PUR-optimal hyperparameters are data dependent, which makes the derivation of the privacy guarantee non-trivial. We have addressed this issue by substituting the gradient norm with an analytical upper bound, but other approaches are certainly conceivable. Note that the privacy leakage from the gradient norm is the highest when we are close to the optimum. This is because, when 0, is sufficiently close to the optimum, there is a neighboring dataset which 0, is optimal. In that case, the norm of the neighboring gradient at 0, is zero, hence, the added noise in the neighboring scenario would also be zero. A potential workaround to this problem could consist of enforcing a lower bound on the noise variance for small gradients, while letting the data-dependent term dominate for large gradients.
Due to the generality of the PUR framework, future work could apply it to a range of other optimization algorithms and objective families. Descent lemmas are known for a variety of optimization settings (Bert-
sckas 1997 Bauschke et al., 2017 Korba et al. 2020 Khirirat et al. 2021 Arora et al., 2022). This suggests that PUR-optimal hyperparameters could be derived for non-smooth problems as well.
Finally, it might improve the hyperparameter selection to consider optimization problems over longer time horizon T > 1. Idcally, we would like to minimize the excess loss under a privacy constraint. Although analytical bounds for excess loss are only available under strong assumptions (see e.g. Hong et al.] (2022)) ) we may hope to find a tractable approximation numerically. A possible relaxation of this problem might be to minimize a weighted sum of privacy loss and utility improvement, as is common in the field of multi-objective optimization [Miettinen 1998)
6 Related Work
A number of recent works have considered approaches to allocating the privacy budget non-uniformly across iterations in differentially private optimization. They broadly fall into two categories: (i) approaches that adapt the noise variance, and (ii) gradient-clipping approaches that adapt the clipping threshold. In this section, we summarize them and discuss their relation to our work.
Adaptive noise Lee & Kifer 2018 perform an adaptation of the noise variance and step size. The step size is chosen at each iteration by grid search over a predefined range via the Noisy Argmax mechanism. The noise variance is reduced by a constant factor whenever a noisy gradient does not lead to a decreased objective value. Yu et al. (2019) consider two strategies for adapting the noise variance, and compare them empirically for deep learning tasks. The strategies under investigation are (i) adjusting the noise variance periodically by monitoring the loss a public validation dataset, and (ii) pre-defined schedules for the noise variance. The decay rate is found via differentially private model selection. A geometrically decaying noise variance has also been considered by Du et al. (2021), and by Zhang et al. (2021) for deep learning. Feldman et al. (2020) consider a variant of Proxinal Noisy SGD with variable batch sizes, step sizes and noise variances. Their privacy guarantees make no strong assumptions on the noise sequence, but the convergence rate is derived for a constant noise sequence with varying batch size and stop size. Their convergence guarantce holds for convex Lipschitz- Lipschitz-smoothi objectives. Hong et al. (2022) derive a noise sequence by minimizing an analytical upper bound the excess loss after T steps. Their analysis requires number
11

---

Published in Transactions on Machine Learning Research (09/2023)
of assumptions the loss function, namely convexity, Lipschitz- Lipschitz-smoothhes and the Polyak-Toojasiewie condition (Polyak 1963). In contrast, our approach can be applied to any loss function for which a descent lemma can be established, which includes a much broader family of losses.
Adaptive clipping Closely related to adaptive noise selection the method of adaptive gradient clipping, Gradient clipping has been used in DP-ERM to make loss functions that do not have a bounded gradient amenable to gradient perturbation (Abadi al., 2016). The privacy guarantce seales with the clipping threshold. Hence, adaptive gradient clipping is alternative way to adjust. the allocation of the privacy budget across iterations. For deep learning, Abadi et al. (2016) proposes to group the gradient components by the network layer they correspond to, and clip each group individually. [Andeew et al. (2021) set the clipping threshold to a quantile of the gradient norm distribution. The quantile is estimated from past gradients via Online Gradient. Descent (Shalev-Shwartz, 2012). While most works focus on the & norm of the gradient, Pichapati et al. (2019) instead use a coordinate-wise adaptive clipping threshold. [Son et al. (2020) study the convergence of adaptive clipping for (convex and non-convex) generalized linear models. Finally, we remark that there is ongoing line of work studying the convergence properties of clipped SGD outside the context of diffcrential privacy (Zhang al. 2020b Mai & Johansson 2021
Other adaptive differentially private optimizers include differentially private versions of AdaGrad (Duchi et al. 2010 2011 Asi et al. 2021) and Adam (Kingma & Ba 2015), which adapt to the problem geometry, and A ADADP (Koskela & Honkela 2020) which adapts the stop size by thresholding the difference between
a full gradient step and two half-steps.
Acknowledgments
This work was partially supported by the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation. This research has been carried out as part of the Vinnova Competence Center for Trustworthy Edge Computing Systems and Applications at KTH Royal Institute of Technology. We would like to thank Tobias Occhtoring and Joakim da Silva for helpful discussions.
References
Martin Abadi, Andy Chu, Ian J. Goodfellow, H. B. McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang, Deep learning with differential privacy. Proceedings of the 2016 ACM SIGSAC Conference Compuler and Commanications Security, 2016.
Mohammed Adnan, Shivam Kalra, Jesse Cresswell, Graham W Taylor, and Hamid R Tizhoosh. Federated learning and differential privacy for medical image analysis. Scientific reports, 12(1):1953, 2022.
Galen Andrew, Om Thakkar, Brendan McMahan, and Swaroop Ramaswamy. Differentially private learn- ing with adaptive clipping. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wort- man Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 17455- 17466. Curran Associates, Inc., 2021. URL 0lcff00af66402244477777444774773
.pdf
Sanjeev Arora, Zhiyuan Li, and Abhishek Panigrahi. Understanding gradient descent on the edge stability in deep learning. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 1024. PMLR, 17-28 Jul 2022. URL https:/7 proceedings mlr. press/v162. wtt.///rrr22aa... html
Hilal Asi, John C. Duchi, Alireza Fallah, Omid Javidbakht, and Kunal Talwar. Private adaptive gradient methods for convex optimization. ArXiv, abs/2106.13756 2021.
Brendan Avent, Javier González, Tom Diethe, Andrei Palcyes, and Borja Balle. Automatic discovery of privacy-utility pareto fronts. Proc. Priv. Enhancing Technol, 2020 4)):5223, 2020. doi: 10.2478/ popels-2020-0060. URL URLhtttss: htttps://dot http:///o..oo//..///// 24782 http:ppppts222-0000000
12

---

Published in Transactions on Machine Learning Research (09/2023)
Racf Bassily, Adam D. Smith, and Abhradcep Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. In 55th IEEE Arenual Symposium on Foundalions of Compuler Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pp. 464 473. JEEE Computer Society, 2014. doi: N0.1109/FOCS.A 2014.56. URL httpp:://ooi wrt./...../////1/..
1109/FOCSS 2014.55 56.
Priyam Basu, Tiasa Singha Roy, Rakshit Naidu, Zümrüt Müftüoglu, Sahib Singh, and Fatemchsadat Mireshghallah. Benchmarking differential privacy and federated learning for BERT models. CoRR, abs/2106.1330 13973, 2021. URL. hattps://aatt http://aaxvvv..o http://rri.o.oooaa/////// /206 13973
Heinz H Bauschke, Jérôme Bolte, and Mare Teboulle. A descent lemma beyond lipschitz gradient continuity; first-order methods revisited and applications. Mathematics of Operations Research, 42(2):330- 040:3388-,,,00 2017.
Stephen D. Bay, Dennis Kibler, Michael J. Pazzani, and Padhraic Smyth. The uci kdd archive of large data sets for data mining research and experinentation. SIGKDD Explor. Newsl, 2(2):81 dee 2000. ISSN
1931-0145. doi:
URL https:///or http:////oio.og//..../o 1111/111999.38811111 381030
Dimitri P Bertsekas. Nonlinear programming. Journal of the Operational Research Society, 48(3):334 334, 1997.
Stephen P. Boyd and Lieven Vandenberghe. Conver Optimization. Cambridge University Press, 2014. ISBN 978-0-521-83378-3, doi: 10.007//C100778011184444 URL https://web.stanford htt.:///taaa.d.ddeeu//////////// cvxbook/
Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Martin Hirt and Adam Smith (eds.), Theory of Cryptography, pp. 635-658 Berlin, Heidelberg, 2016. Springer Berlin Heidelberg. ISBN 978-3-662-53641-4,
Damien Desfontaines and Balázs Pejó. Sok: Differential privacies. Proc. Priv. Enhancing Technol, 2020 288 313, 2020, doi: 10.2478 10.2478/popets- popppsoppptto000
URL
htt:://ii..oo.....a//////////pp/ 2020000028
Jian Du, Song Li, Fengran Mo, and Siheng Chen. Dynamic differential-privacy preserving SGD, CoRR, abs/2111.00113, 2021. URL https:///aati:ii http::///awww..o///a////////////
Dheeru Dua and Casey Graff. UCT machine learning repository, 2017. URL http:://archive.iss.eee edu/
John C. Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. In Adam Tauman Kalai and Mehryar Mohri (eds.), COLT 2010 The 23rd Conference on Learning Theory, Haifa, Israel, June 27-29, 2010, pp. 257-269. 269. Omnipress, 2010. URL
http://colt2011 hwifa. il. ibm. http://pppre/.00111/prrreeeeeeee .acpsss.pppfpppp #page=2=26
John C. Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and doi: (1.5555/1953048.22220 URL
stochastic optimization. Mach. Learn. Res., 12:2121 2159, 2011.
https://dl.. acm. http://o///.....55////// 2021006
2021068
Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci., 9(3-4):111-477 2014. doi: 10.1561/0400000044 URL ftttps://ao..org/00...3
0400000042
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3, pp. 284.284. Springer, 2006.
Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimization: optimal rates linear time. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pp. 439 449, 2020.
R. A. Fisher. The use of multiple measurements in taxonomic problems. Annals of Eugenics, 7(2):179- 1888 1936. doi: https: https://doi.orgg// 11.1111111111111111111 1809 1936...11.... URL http:://oniineelbrary...ttt com/doi/abs/10 1ttp:/....1111////11111 1111/jjjjjjjj......... 1869 1936. tb02137.5
13

---

Published in Transactions on Machine Learning Research (09/2023)
Junyuan Hong, Zhangyang Wang, and Jiayu Zhou. Dynamic privacy budget allocation improves data efficiency of differentially private gradient descent. In FAccT '22: 2022 ACM Conference on Fairness, Accountability, and Transparency, Seoul, Republic of Korea, June 21 24, 2022, pp. 11 11-35. ACM, 2022.
doi:
URL https://doi.orgee httpa//rrr.....1/55331133331 35330000
Georgios Kaissis, Alexander Ziller, Jonathan Passerat-Palmbach, Théo Ryffel, Dmitrii Usynin, Andrew Trask; Tonésio Lima Jr, Jason Mancuso, Friederike Jungmann, Marc-Matthias Steinborn, al. End-to-end privacy preserving deep learning on nulti-institutiinall medical imaging. Nature Machine Intelligence, 3 (6):473 1844, 2021.
Sarit Khirirat, Sindri Magnússon, Arda Aylekin, and Mikael Johansson. A llexible framework for communication-efficee machine learning. In Proceedings of the AAAI Conference on Artificial Intel- ligence, volume 35, pp. 8101 8109, 2021.
Daniel Kifer, Adam D. Smith, and Abhradeep Thakurta. Private convex optimization for empirical risk minimization with applications to high-dimensional regression. In Shie Mannor, Nathan Srebro, and Robert C. Williamson (eds.), COLT 2012 The 25th Annual Conference on Learning Theory, June 25- 27, 2012, Edinburgh, Scotland, volume 23 of JMLR Proceedings, pp. 25.1-25.40. JMLR.org, 2012. URL
http: http:///oooeeedg..coo mlr. wwwps///weeeeeppe htt////ierr////ifrr22....
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Yoshua Bengio and Yann LeCun (eds.), 3rd International Conference on Learning Representations, 1CLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015. http://t://arxi
http//bbs/111..... 6980.
Anna Korba, Adil Salim, Michael Arbel, Giulia Luise, and Arthur Gretton. A non-asymptotic anal- ysis for stein variational gradient descent. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Had- sell, Maria-Florina Balcan, and Hsuan-Tien Lin (eds.), Advances in Neural Information Processing Systems 33: Annual Conference Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020. URL
Antti Koskela and Antti Honkela. Learning rate adaptation for differentially private learning. In AISTATS, 2020.
Antti Koskela and Tejas Kulkarni. Practical differentially private hyperparameter luning with subsampling, CoRR, abs/ 0bbs/2331.19998 2023. doi: 10.48550 00.44550//ariiv2225 www..xv.201.111990 URL/ttpp::/ddot org/10. hetg//..8550///// 48550/arXiv. arrii. 2301 11989
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, 2009. URL
http://www. cs. toronto.oo...... wwwpattt.eddu-rri/eeeaaaaeae featurgs--eaute--eeeee 2009-00099T0 2009-TR. TR.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient- learning applied to document recognition. Proc. IEEE, 86(11):2278 2222242,,, 1998.
doi: 10.1109/5.726791. URL https:
//doi 1ttp:/.0.119/55.72550
Jacwoo Loe and Daniel Kifer. Concentrated differentially private gradient descent with adaptive per-itcration privacy budget. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledgge Dis- covery & Data Mining, pp. 1656-1665, 2018.
Jingcheng Liu and Kunal Talwar. Private selection from private candidates. In Moses Charikar and Edith Cohen (eds.), Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenir, AZ, USA, June 23-26, 2019, pp. 298 309. ACM, 2019. doi: 10.1145/33 /////333336.3333337 URL https:///oi..... org/oor///00.... /00 /145//1111/66.... 3316377
Andrew Lowy and Meisam Razaviyayn. Output perturbation for diffcrentially private convex optimization with improved population loss bounds, runtimes and applications to private adversarial training. CoRR, abs/2102.04474, 2021. URL. https: //trxx/a.vvvv///////// /ttp///xv.orrgaaaa//////aaaaaaaa httggaab/21102/2 04704
14

---

Published in Transactions on Machine Learning Research (09/2023)
Vien V. Mai and Mikael Johansson. Stability and convergence of stochastic gradient clipping: Beyond lipschitz continuity and smoothness. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 1325-73335 PMLR, 18-24 Jul 2021. URL http:::/pproeeeeng.s .lr.. wttp://s.w.........eeeeeeeeeseee aetass/v139// 00399//ma22a..i..
Brendan McMahan, Daniel Ramage, Kunal Talwar, and Li Zhang. Learning differentially privale recurrent language models. In International Conference on Learning Representations (ICLR), 2018. URL https:
//openreview wwt.://ddfadddBJJFFF220.
Kaisa Micttinen. Nonlinear maltiobjective optimization, volume 12 of International series in operations research and management science. Kluwer, 1998. ISBN 978-0-7923-8278-2
Shubhankar Mohapatra, Sajin Sasy, Xi He, Gautam Kamath, and Om Thakkar. The role of adaptive optimizers for honest private hyperparameter selection. In Thirty-Sinth AAAT Conference on Artificial Intelligence, AAAI 2022, Thirty-Fourte Conference on Innovative Applications of Artificial Intelligence, TAAI 2022, The Twelveth Symposium on Educational Advances in Artificial Intelligence, EAAI 2022 Virtual Event, February 22- March 1, 2022, pp. 7806-7813. AAAI Press, 2022. doi: 10.1609 40.1609/aaai.vo aaai.v3617 20749. URL https://dor org/ 10. 1609/ aaai v3617 20749
Edouard Oyallon and Stéphane Mallat. Deep roto-translation scattering for object classification. In IEEE Conference on Compuler Vision and Pallern Recognition, CVPR 2015, Boston, MA, USA, June 7-12, 2015, pp. 2865 2873. IEEE Computer Society, 2015. doi: (LLL00/CVVR.2015.... //doi.org//i 10. 1109/CVPR. 2015. 7298904
URL https:
Nicolas Papernot and Thomas Steinke. Hyperparameter tuning with renyi differential privacy. In The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview.net, 2022. URL https:://openrevieee htwp://wwweeeeeeeeeeeeooorrrrrae set//forumiid==70811ppp23
Venkatadhecraj Pichapati, Ananda Theertha Suresh, Felix X. Yu, Sashank J. Reddi, and Sanjiv Kumar. AdaCliP: Adaptive clipping for private SGD. CoRR, abs/1908.07643. 2019. URL http://arxiv.. org/
abs/1908.07644 07643
Boris Teodorovich Polyak. Gradient methods for the minimisation of functionals. USSR Computational Mathematics and Mathemattcall Physics, 3(4):864 878, 1963.
Shai Shalev-Shwartz. Online learning and online convex optimization. Foundations and Trends in Machine Learning, -92) 2012. ISSN 1935-8237. doi: 10.15611/2000000088. URL http://xxxxxooooggg.. 1561/2200000018
Shuang Song, Kamalika Chaudhuri, and Anand D. Sarwate. Stochastic gradient descent with differentially private updates. In 2013 IEEE Global Conference on Signal and Information Processing, pp. 245-248, 2013. doi: Ltt.o///oobalS1P201.......
Shuang Song, Om Thakkar, and Abhradeep Thakurta. Characterizing private clipped gradient descent on convex generalized linear problems. CoRR, abs/ abs/2006.06688, 2020. URL 06783
Florian Tramer and Dan Boneh. Differentially private learning needs better features (or much more data). Tn 9th International Conference Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021. URL http::///ppaaaeeeeeeerr/////rrrr
Di Wang, Minwei Ye, and Jinhui Xu. Differentially private empirical risk minimization revisited: Faster and more general. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett (eds.), Advances in Neural Information Processing Sys- tems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp. 2722 2722-2731, 2017. URL httpps://proceedingn http:/cceddng...uur.......peappp 1as
Abstractt....................a html
15

---

Published in Transactions on Machine Learning Research (09/2023)
Lei Yu, Ling Liu, Calton Pu, Mehmet Emre Gursoy, and Stacey Truex. Differentially private model publishing for deep learning- In 2019 TEEE Symposium on Securily and Privacy, SP 2019, San Prancisco, CA, USA, May 19-23, 2019, pp. 332 349. LEEE, 2019. doi: 10.1109/9PP2211.00001 URL https://doi. 10. 1109/SP. 2019 00019
Bohang Zhang, Jikai Jin, Cong Fang, and Liwei Wang. Improved analysis of clipping algo- rithms for non-convex optimization. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (eds.). Advances in Neural Information Processing Sys- tems 33: Annual Conference on Neural Information Processing Systems 2020, NewrIPS 2020, De- cember 6-12, 2020, virbual, 2020a. URL 0 Abst:aatt--atttttt......
Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaie. Why gradient clipping accelerates training: A theoretical justification for adaptivity. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.nct, net, 2020b. URL URL hattps://openrevleew...t
forum?id=BJgan Sorum''d=BJJgxXPVWss
Xinyue Zhang, Jiahao Ding, Maoqiang Wu, Stephen T. C. Wong, Hien Van Nguyen, and Miao Pan. Adap- live privacy preserving deep learning algorithms for medical data, In 2021 IEEE Winler Conference on Applications of Computer Vision (WACV), pp. 1168- 1177, 2021. doi: 10.1109/ C04.8330.2022000000000
Alexander Ziller, Dmitrii Usynin, Rickmer Braren, Marcus Makowski, Daniel Rueckert, and Georgios Kaissis. Medical imaging deep learning with differential privacy. Scientific Reports, 11(1):1-8, 2021.
A Additional figures
In Figure 3
we show the gradient norm plots for the experiment described Section for the remaining three datasets.
B
Proofs
B.1 Lemma
Proof. Since F is M-smooth, we have
M F(0(+1) s F((,) 77 (VF(0) + ()) VF(0.) + ll((VF(()) + 2.)1
2 =(({.) ne (IVF + VF((.)) M
[n(((F()))) + +.11.
Note that the variance of of the noise &e is itself a random variable. This because we choose ds as a function of Or, which is random. Conditional on the values of O, and at, the noise Çr has zero mean and variance of, and is independent of F(.))) We take conditional expectation
M E (FF(0++1) 01 S E. F(O.) n (IVF((0)) + G. VF())) In.(VF(()) + +G)1 0,,
= =(())) - Th (F))) + M nh (IVF [[IGe]] oo]).
2
[| 2 oi] = do? and rearrange to using E [T 0z = [G a. VF(..) = 0. Now, we use
obtain:
E ((,)))) F(f++1) 10, 00, 2 1t 2 nh |[VE(0))12 M do ;
M
16

---

Published in Transactions on Machine Learning Research (09/2023)
logistic(A 0.0)
logistic(A 0.1)
10
open loop (1.0)
open loop (1.0)
(5.0)
loop
consiant (0.001)
constant (0.001)
constant (0.01)
constant (0.01)
constant (0.1)
10
constant (0.1)
(1.0)
10-2
200
400
600
800
1000
1200
1400
200
400
600
800
1000
1200
1400
(a) KDD Cup dataset
logistic(A 0.0)
logistic(A 0.1)
open loop (1.0)
open loop (1.0)
closed loop
60-10
closed loop
constant (0.001)
constant (0.001)
6x 10
constant (0.01)
constant (0.01)
constant (0.1)
4x-10-1
constant (0 (0.1)
(1.0)
(1.0)
l/zz||
4x
3x
3x
2 10
10
10
200
400
600
800
1000
1200
1400
0
200
400
600
800
1000
1200
1400
Eyeak
Eyeak
(b) MNIST dataset
logistic(A
logistic(A 0.1)
open loop (1.01
open loop (1.0)
10a
closed loop (5.0)
10a
closed loop (5.0)
(0.001)
constant
constant (0.01)
constant I (0.01)
constant (0. 1)
constant (0.1)
constant (1.0)
constant (1.0)
Ippell
[peill
10-1
10-1
200
400
600
800 Sweak
1000
1200
1400
200
400
600
800
1000
1200
1400
Sweak
(c) Breast cancer dataset
Figure 3: Results for additional datasets.
17

---

Published in Transactions on Machine Learning Research (09/2023)
B.2 Proposition 1
Proof. Since P does not depend on Wht we can first maximize U with respect to nh, which is attained by
(12)
M (1+ dof [L+
Inserting this into Equation
g leads to an expression of the form
PUR(o,) = (I]VF(0:))]=0; + +
where e is constant. This is minimized by o, VF(()))I/Vd Insertion into Equation 12 completes the result.
B.3 Proposition 2
Proof. We start from Lemma and insert the schedule from Equation 6 into Equation 5 which gives conditional expectation
1 IVF()))
( E (F(0.) F(0++1) O2, 0z) 2
4M
that is, the expected improvement taken over single iteration. In order to average over the randomness of the entire algorithm, we apply the law of total expectation to obtain
E S SB((O.)) 4M
[IVF(()))
(13)
Now, we separate the three cases.
(a) We sum both sides of Equation 13 over == . to obtain
E [[F(Or+1) < [[F(O))
4M E
Σ EIVF(0))1
We lower-bound E [F( 2 F and rearrange to obtain
4M (F(O)) - FF
E
IVF())1
T
T
(b) By convexity, F(0) F(0*) VF (0 0*) for all 0 E Rd and Cauchy-Schwarde implies that
F(0) -(0))F(0")) F(0') S 0 [(]]
We take 8 0g and invoke the assumption that ||A, 00 R, which yiclds
VF(0)) (F(O.) F2)
(14)
R²
Now, by taking expectation and applying Jensen's inequality, we have
E [F(,) - =
E VFF())
(15)
R22
Plugging this bound back into Equation 13 yields the iterate relationship
E [FF(0++1))
< E((())
E [(F(O)) F
4MR
18

---

Published in Transactions on Machine Learning Research (09/2023)
Letting V, E [F((s) F*), we can write this
V4+1 S
4M V?
and apply Lemma 6 of Khirirat et al. (2021) to obtain
1
E (F(()) F*] +
E (F,()) F+]
4MR
E [F(()) - F+]
4M
4M R2
E [F(())) - -F*] S
(c) By strong convexity, ||VF 2 2p (F(O.) F+). Inserting this into Equation 13
E [[ 1)] S E [F()
E [F) - F*..
2M
Letting V22 = EE (e)):) - F",, we can write this as
V4+1 S (1-
1 V4.
2M
The result follows by recursion.
B.4
Lemma 2
Lemma 2. Let V, be sequence in Rzo that satisfies
1 -, Vo Ve+ S V - vV? + 11 for g>0, 0505 5
1
(16)
q
Then,
V, S
(17)
qt'
Proof. First, consider the upper bound in Equation
16 as function W2 R - R of Vi:
Wi(a) g9a +atrt
W, is a concave quadratic maximized by
1 a" arg max W.
1
Wi(a")
+ rl. -2.
(18)
2q
4q
The proof is by induction. We begin by verifying that
1
2 4
Vi s Wi =
+
<
<
4g
4g
Now, assume that. Equation 17 holds for some 2 We distinguish two cases.
First, if t 2 4 then V, is smaller than the maximizer of W
2
V s
gt
29
19

---

Published in Transactions on Machine Learning Research (09/2023)
Consequently, W411 is monotonically increasing on [0, gel: hence
2
2
4
r
V4+1 S WV+1(Vi & We+1
+
qt
gt
qta
(t + 1)2²
Using the fact that 1/8 1/t + 1/(t + 1), it follows that
2
1
4
V1+1 -
+
f2
t+
gt2
(t
(t+1)) 1)2
2
q( + 1)
2
q o(t+1) +)'
where the second inequality follows from $ 1/4- Second, if t $ 3 then we can use the global maximizer to bound V441:
+r(t +) (t 1)a + 4rq
2 (t 1++ 8(t S(++1) + 4rg
Ve+1 S W(a")
4q
4g(t 1)2
q(t+1)
4q + 1)2
The numerator of the second term is convex quadratic. Over t [0,3], 3], it is maximized by t = 0, which leads to
2
4rq 4q + 1)
Vi-1 -
(t
We can see that second term is negative because rg $ 1, so it can be dropped to conclude V4+1 - 2/g(t + 1).
B.5 Proposition 3
Proof. As with Proposition ion 2 bound the various quantities in order to arrive at a recursive bound on E [F(O,) - F=). Again, we separate the convex and strongly convex case.
the general proof idea is to apply the descent lemma to the schedule and then
(a) Starting from Lemma inserting the schedule a 4M / F( F-
and taking expectation leads to
Vat
2M(F((b) -F))
E <E( 8M
+ 82
Now, we sum both sides over obtain
T +
T 2M F²)
VF(0))
8M
t
Noting that Σi= 1/t² < Ei= 1/p= =x//6, we bound the last term obtain
3
T
M(F(0)) F
[F 1]] < EE [F())]
E
|FFO))
8M
3
Now, we lower-bound F(Or+1) 2 F and rearrange to obtain
M () - F*)
E
T
3T
t=0
20

---

Published in Transactions on Machine Learning Research (09/2023)
(b) Starting from Lemma inserting the schedule or to
4M v
and 1/ 1/(2M) and taking expectation leads
2M
E &
E [IVF(O))] +
(19)
8M
12
Analogously to Equation
15
we can bound E [[)) to obtain
3 SMR
2M
E S
B[F(O.) F=1
12
which we can write as
2MR
Ve+1 3 V2
V? +
8MR
82
Applying Lemma 2 yields the result.
(c) We apply Lemma 1 with the schedule take expectation to oblain
-F)
F*) -1)(2- and 1/(2M), and
3
VF))I + 8M (20) - -F*) (1- 1
E ( S
8M
2k
where we write x M/n. We bound the gradient norm by ||FF 24 (F(Or) F*) due strong convexity:
3
(F(Oo) F*) (1
E [F((+++1] & [F(OO]]
E (F(O.) F*] + 4x
(20)
4k
2x
Now we can show the result by induction. Suppose is true for E [F(0.)) - F*I S P*) (1 apply the induction hypothesis to obtain
> that
) Then, we can subtract F from both sides of Equation 20 and
B[F(O++1) - FF) S (1
3
(F(Og) F*) (1-
4rc
Ax
= =FF(O)) - FF) (1
1
t+1
2x
which is what we wanted to show. The initial case 0 can be verified via the descent lemma.
B.6 Proposition
Proof. We begin with the privacy analysis. We first analyze the privacy loss in terms of xCDP, then convert to the corresponding (e, DP... Each iteration of the algorithm is application of the Gaussian mechanism to the gradient VF(0,) = 1/N f(A;; x.). Since f is L-Lipschitz, the sensitivity of VF with respect to replacement of one data entry is A 2L/N. Adding noise with variance of preserves Pr2CDDP with Pe = A A2/(()?) ( Composition over iterations means that the full algorithm preserves
zCDP with
21 T
1
p
N2
o
(21)
Now we specialize this guarantee for the noise schedules under considcration.
For (a) we have
d
T
o
(6(2(
F*)
1=1
t=1
21

---

Published in Transactions on Machine Learning Research (09/2023)
Note that E, < T Plugging back into Equation 21 we have
1.2d T
P
822 - FF)
That is, we can run T = Inserting this into the excess risk bound from Proposition
(F F² (/L'd) iterations until the privacy budget is exhausted. we conclude
3
T
8( ( M/72 ()((())) - EA)
IVF(0)11
3
x P
-1)
(F(0o) F 22L
3 3
8pNaM²
For (b), the proof is analogous to (a), but using the noise schedule and excess risk bound for the convex case.
For (c) the argument follows a similar structure. The algorithm is p-2CDP for
d d P 2p F²)
Σ (1-
1
2k
where M/p. This is geometric scries p a Dt pr with constants 1/(1 1 1/(xx)). Therefore,
d2a/2 2uF(0))-F") and
p T+1 r
0
(r - -1)- r
Note that r/(r - 1) 2x, therefore
= 2ak(r" T
1)
2akr""
dA2
-T
1-
2μ (F(0o) F²))
2k
Via Proposition 3p, we have
dA
5 2pl [F(rr) F+]
d
E[F - F*] s
241
The corresponding 8P guarantees are p 2/ p 0
22


Reviews:
[{"review_id": "9sKjj2GrIC", "reviewer": "Reviewer_455j", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths of the paper:\n1. The proposed privacy-utility ratio framework seems interesting and can be an independent interest.\n2. The privacy and utility guarantees of the proposed adaptive approach have been established.\n3. Experiments validate the effectiveness of the proposed method.\n\nWeakness of the paper:\n1. There is no improvement in the theoretical utility guarantees compared to existing methods.\n2. The privacy guarantees rely on the smoothness assumption.\n3. There is no comparison with some existing baselines.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the problem of differentially private gradient descent (DP-GD) in (strongly) convex settings. More specifically, the authors propose using an adaptive way to add random noise in DP-GD, with the goal of attaining improved utility guarantees in the theoretical analysis as well as practical applications.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I have the following main questions that need to be addressed in the current paper:\n1. More justification needs for the privacy-utility ratio framework. The current form lacks consideration of the iteration number, which accounts for the main part of the privacy loss.\n2. According to Proposition 4, the results hold for specific $\\epsilon$ since $\\epsilon$ further depends on other parameters (e.g., d, L, T, etc.). Can you give a result that holds for any choice of $\\epsilon$?\n3. According to Proposition 4, the privacy guarantee relies on strong assumptions. For example, it requires the function to be smooth, which is not required by the previous methods. If we can assume that the function is smooth, we can directly use the output perturbation methods in [1] to achieve strong privacy and utility guarantees for DP-GD. In this case, we don't even need to tune anything. In addition, it is very hard to implement the proposed method since we don't know the smoothness parameter for general problems. \n4. According to Proposition 4, how can the condition $\\\\|\\theta_t-\\theta^*\\\\|\\leq R$ hold for convex problems?\n5. For the experiments, the authors should consider comparing with the methods developed in [1] and Lee & Kifer (2018).\n6. In general, I don't understand the benefits of the proposed method. On the one hand, the results do not improve over previous guarantees. On the other hand, we still need to tune hyper-parameters in practice since the smoothness parameter is unknown for general problems.\n\nReferences:\n1. Zhang, Jiaqi, et al. \"Efficient private ERM for smooth objectives.\" Proceedings of the 26th International Joint Conference on Artificial Intelligence. 2017.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "ZKrKImYVIi", "reviewer": "Reviewer_WeLj", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: This work is clearly written and rigorous as far as I can tell, e.g. the discussion of constraint $\\epsilon<1$ in Section 3.2 and the careful discussion from the data-dependent selection to the data-independent one. Especially, the introduction of privacy-utility ratio (PUR) in Section 3 is interesting. I am impressed by the elegant selection of $\\sigma$ and $\\eta$ in Equation (6) and the similarity in performance between data-dependent and data-independent selection.\n\nWeaknesses: One limitation of this work is the convex (and smooth) setting. While I understand that this is necessary to derive theoretical results, the experiments are much less significant since the model is a simple logistic regression and does not reflect the necessity of a better hyperparameter selection. In other words, there are several aspects missing or good-to-have in this work. (1) In the convex loss setting, one can still consider the neural networks, which is the motivation in the first sentence of the first section. I.e., the hyperparameter selection is more of an issue when the model is larger. Notice that in linear probing (fine-tuning only the last layer of a network), this is essentially a convex setting and can lead to state-of-the-art accuracy in computer vision (e.g. https://arxiv.org/abs/2205.02973). This would enhance the paper to go beyond toy datasets like MNIST. (2) Beyond the convex loss setting, e.g. the deep learning setting, it seems possible to derive a result similar to (https://arxiv.org/abs/2206.07136) following the analysis in this work. (3) There are non-gradient based methods to solve a logistic regression in a differentially private way, to which this work should be compared.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work proposes an adaptive mechanism to select two hyperparameters in DP optimization: the noise scale and learning rate. In particular, the authors introduce PUR to maximize the trade-off between utility and privacy. The proposed method is supported in theory and experiments under the convex (even sometimes strongly convex) losses.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See weaknesses above.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "d925KRDEY0", "reviewer": "Reviewer_g8Jn", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper studies an important problem under the most commonly studied assumptions. The two hyperparameters considered in this paper are the learning rate and the step size. \n\nThe paper is very well written, and quiet easy to ready and follow. I really liked this aspect of the paper. The proofs all seem to be correct. \n\nCan the authors give a reason why they have a worse excess risk guarantee for convex, Lipschitz, and Lipschitz smooth functions? ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper makes several contributions:\n1. A conceptual framework for tuning hyperparameters by optimizing the privacy-utility ratio.  \n2. Use this framework on convex and strongly convex losses.\n3. Give convergence rate for both data-independent and data-dependent scheduling. \n4. Provide extensive experiments to substantiate their results. \n\n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The paper is well written and I approve of accepting the paper in the current format. ", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers recommend accepting the paper, on the condition that the authors add the experiments they have promised to add in the final version.

I thus recommend acceptance conditioned on minor revision of adding the promised new experiments.
Decision: Accept (poster)