Improving the Privacy and Practicality of Objective Perturbation for Differentially Private Linear Learners
Authors: Rachel Emily Redberg
Antti Koskela
Yu-Xiang Wang
Venue: NeurIPS 2023 poster (2023)
Keywords: differential privacy
empirical risk minimization
objective perturbation
TL;DR: We provide the old-school objective perturbation mechanism with new privacy analyses and computational tools.

Abstract: In the arena of privacy-preserving machine learning, differentially private stochastic gradient descent (DP-SGD) has outstripped the objective perturbation mechanism in popularity and interest. Though unrivaled in versatility, DP-SGD requires a non-trivial privacy overhead (for privately tuning the model’s hyperparameters) and a computational complexity which might be extravagant for simple models such as linear and logistic regression. This paper revamps the objective perturbation mechanism with tighter privacy analyses and new computational tools that boost it to perform competitively with DP-SGD on unconstrained convex generalized linear problems.

Improving the Privacy and Practicality of Objective Perturbation for Differentially Private Linear Learners
Rachel Redberg UC Santa Barbara
Antti Koskela Nokia Bell Labs
Yu-Xiang Wang UC Santa Barbara
Abstract
In the arena of trivacy-presenvee machine learning, differentially private stochastic gradient descent (DP-SGD) has outstripped the objective perturbation mechanism popularity and interest. Though unrivaled in versatility. DP-SGD requires a non-trivial privacy overhead (for privately tuning the model's hyperparameters) and a computational complexity which might be extravagant for simple models such as linear and logistic regression. This paper revamps the objective perturbation mechanism with tighter privacy analyses and new computational tools that boost it to perform competitively with DP-SGD unconstrained convex generalized linear problems.
Introduction
The rise of deep neural networks has transformed the study of differentially private learning no less than any other area of machine learning. Differentially private stochastic gradient descent (DP-SGD) (Song et al., 2013 Bassily et al., 2014: Abadi et al. (0166) has thus gained widespread appeal as versatile framework for privately training deep learning models.
How does DP-SGD fare on simpler models such as linear and logistic regression? The verdict is unclear. Clearly an algorithm capable of privately optimizing non-convex functions represented by millions of parameters is up to the computational task of fitting a linear model. A more pressing concern is that DP-SGD is up to too much. Look, for example, at the algorithm's 's computational complexity: DP-SGD requires Onn²) steps achieve the optimal excess risk bounds for DP convex empirical risk minimization (Bassily et al. 2014).
DP-SGD furthermore takes after its non-private counterpart in sensitivity hyperparameters. A poor choice of learning rate or batch size, for instance, could lead to suboptimal performance or slow convergence. There are well-established procedures for hyperparameter optimization that typically involve evaluating the performance of the model trained using different sets of candidate hyperparameters. But with privacy constraints, there is a catch: tuning hyperparameters requires multiple passes over the training dataset and thereby constitutes a privacy cost.
At best, existing work tends to circumvent this obstacle by optimistically assuming the availability of a public auxiliary dataset for hyperparameter tuning. More often the procedure for private hyperparameter selection is left largely to the reader's imagination. Only recently have Liu & Talwar (2019) and subsequently Papernot & Steinke 2022) studied how to obtain tighter privacy loss bounds for this task beyond standard composition theorems.
In the meantime, objective perturbation (Chaudhuri et al. 2011 Kifer et al. 2012) has been to some extent shelved historical curiosity. Sifting through the literature, find that opinions are divided: some tout objective perturbation as "[o]ne of the most effective algorithms for differentially private learning and optimization" (Neel et al. 2020), whereas other works (Wang al. 2017) dismiss
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

objective perturbation as being impractical and restrictive. Some empirical evaluations YYu et al. 2019; McKenna et al., 202T) suggest that DP-SGD often achieves better utility in practice than does objective perturbation; others (Iyengar et al. 2019) report the opposite.
Our goal in this paper is to lay some of this debate rest and demonstrate that for generalized linear problems in particular, objective perturbation can outshine DP-SGD.
1.1 Our Contributions
We establish an improved 6D bound for objective perturbation via privacy profiles, a modern tool for privacy accounting that bounds the hockey-stick divergence. The formula can be computed numerically using only calls Gaussian CDFs, We further obtain dominating pair of distributions as defined by Zhu et al. (2022) which enables tight composition and amplification by subsampling of the privacy profiees.
We present a novel Rényi differential privacy (RDP) (Mironov, 2017) analysis of the objective perturbation mechanism. Using this analysis, we show empirically that objective perturbation performs competitively against DP-SGD with "honestly" [ tuned hyperparameters. The tightest analyses to date of private hyperparameter tuning the RDP bounds derived in Papeerott & Steinke (002)). This tool allows us to empirically evaluate objective perturbation against DP-SGD
level playing field (Section(5).
We fix a decade-old oversight in the privacy analysis of objective perturbation. Existing literature overlooks nuanced argument in the privacy analysis of objective perturbation, which requires a careful treatment the dependence between the noise vector and the private minimizer. Without assuming GLM structure, the privacy bound of objective perturbation is subject to a dimensional dependence that has gone unacknowledged in previous work
We introduce computational tools that expand the applicability of objective perturba- tion a broader range loss functions. The privacy guarantees of objective perturbation require the loss function to have bounded gradient. Our proposed framework extends the Approximate Minima Perturbation framework of [yengar et al. (2019) to take any smooth loss function as a blackbox, then algorithmically ensure that has bounded gradient. We also provide a computational guarantee On log n) on the running time of this algorithm, in contrast the (n²) complexity of DP-SGD for achieving information- -theoretic limits.
1.2 A Short History of DP Learning
Differentially private learning dates back Chaudhuri et al. (201I) which extended the output perturbation method of Dwork et al.) (2006) to classification al algonthmss and also introduced objective perturbation. In its first public appearance, objective perturbation required gamma-din distribbbet noise; Kifer et al. (2012) provided a refined analysis of the mechanism with Gaussian noise, which is the entry point into our work.
Differentially private stochastic gradient descent (DP-SGD) (Song et al.) 2013 Bassily et al. 2014 Abadi et al. 2016) brought DP into the fold of modern machine learning. allowing private training of models with arbitrarily complex loss landscapes that can scale to enormous datasets. DP-SGD adds Gaussian noise at every iteration an aggregation of clipped gradients, and thus privacy analysis for DP-SGD often boils down to finding tight composition bounds (of the subsampled Gaussian mechanism).
The initial version of DP-SGD based on the standard strong composition (Bassily et al. 2014] is not quite practical, but that has changed, thanks community effort in developing modern numerical privacy accounting tools in the past few years. These include the moments accountant that composes Renyi DP functions (Abadi al. 2016 Wang et al.) 2019: Mironov et al., 2019) and the Fourier accountant (also known as PLV or PLD accountants) that directly compose the privacy
profiles (Sommer et al.) 20199; Koskela al. 2020 Gopi et al. [222 Zhu et al.) (0022). It is safe to conclude that the numerically computed privacy loss of DP-SGD using these modern tools is now very precise.
"Honest" hyperparameter tuning is a term coined by Mohapatra et al. 2022).
"hh concurrent work of Agarwal al. 2023) has independently identified this bug well.

---

Because DP-SGD releases each intermediate model, the algorithm can stop after any number of iterations and simply accumulates privacy loss as goes. In contrast, the privacy guarantees of objective perturbation hold only when the output of the mechanism is the exact minima of the perturbed objective. This requirement is odds with practical convex optimization frameworks which typically use first-order methods to search for an approximate solution.
To remedy this, Iyengar
(2019) proposed an approach to approximately minimize perturbed objective function while maintaining privacy. Approximate Minima Perturbation (AMP) was intro- duced as a tractable alternative to objective perturbation whose privacy guarantees permit the output to be an approximate (rather than exact) solution to the perturbed minimization problem. In this paper we extend AMP to a broader range of loss functions: Algorithm cann be viewed special case of AMP with transformation of the loss function.
Preliminaries
2.1 Differential Privacy
Differential privacy (DP) (Dwork et al. 2006) offers provable privacy protection by restricting how much the output randomized algorithm can leak information about single data point.
DP requires a notion of how to measure similarity between datasets. We say that datasets Z and Z' are neighboring datasets (denoted or Z' Z { for some data entry 2.
Z') if they differ by exactly one datapoint z, i.e. Z' U {2}
Definition 2.1 (Differential privacy). A mechanism M: Z - R satisfies (c, didfffereen privacy for all neighboring datasets Z, Z' e and output sets S S R.
Pr [M E 5) S e Pr E S] + 6.
When > 0, M satisfies approximate DP. When 8 = 0, M satisfies the stronger notion of pure DP. We say that M is tightly (c, d)-PP if there is no 8' 5 for which M would be (c, 5',
In what follows, we overview two different styles of achieving DP guarantees: one via hockey-stick divergence, and the other via Rényi divergence.
2.1.1 DP via hockey-stick divergence
Definition 2.2 (Hockey-stich) divergence). Denote [x]+ = max(0, x} for x E R. For a > the hockey-stick divergence H. from distribution P to distribution Q is defined as
Ha(P)IQ) (P()) a Q(x)) dx.
Now (with some abuse of notation) we will discuss how to bound the hockey-stick divergence between distributions M(Z) and M(Z") via the concept of privacy profiles.
Definition 2.3 (Privacy profiles Balle et 2018). The privacy profile (c( of mechanism M defined as
8m(e) maxz~z He (M(Z))
Tight (c, 6D- bounds can then be obtained as follows.
Lemma 2.4 (Zhu et al. 2022 Lemma 5). Mechanism M satisfies (c, 6D- if any only if 2 (c)().
Dominating pairs of distributions are useful for bounding the hockey-stick divergence H.r (M()) M(')) accurately and, in particular, for obtaining tight bounds for compositions.
Definition 2.5 (Zhu al. 2022). A pair of distributions (P, Q) is a dominating pair of distributions for mechanism M: Z + R if for all neighboring datasets Z and Z' and for all a > 0,
HL(M(Z)(M(Z')) (PII)).
3

---

2.1.2 DP via Rényi divergence
Definition 2.6. (Rényi divergence.) Let > 0. For # 1, the Rényi divergence Da from distribution P to distribution Q is defined
I P(x) a1
Da(PIlQ) a log E
Q(x)
When a = 1, Rényi divergence reduces the Kullback-Leee Leibler (KI.) divergence:
P(z) ((x)
(i())) = Ex-P log
Rényi differential privacy (RDP) a relaxation of pure DP = 0) based on Rényi divergence.
Definition 2.7 (Rényi differential privacy). A mechanism M 2 + R. satisfies (ax, R)-Réy differential privacy if for all neighboring datasets 7, 7' 2,
Da (M(Z) M((z)) S,
RDP implies (c, for any 0 < 8 with min (c((:) + log(1 1//8//(00 1)}. Tighter but more complex conversion formulae were derived by |Blle et al. (2020) and Canonne et al. (2020).
which we adopt numerically in our experiments whenever approximate DP is needed.
2.2
Differentially Private Empirical Risk Minimization
We have a dataset Z Z and a loss function E(O; we want to solve problems of the form
arg min
E)0;;))
AE0
=EZ
where 2 = (x.y) y) E X' x y is a data point and r(0) is a regularization term. The feature space is X C Rd and the label space y C We will assume that ||æ/|2 S and lv| S
This work focuses on unconstrained convex generalized linear models (GLMs): we require that {()) and r(f) are convex and wiice-differentiable and that @ = Rd The loss function assumed to have GLM structure of the form E(O: 2) f(x" (:
Objective Perturbation Construct the perturbed objective function by sampling ~ NN(0,
C (0: (0: Z.
Σ 2E%
((0:2) 2 11
The objective perturbation mechanism (ObjPert) outputs 0P (Z) (z(
arg mingee L 7, b).
Theorem 2.8 (DP guarantees of objective perturbation (Kifer et al. 2012). Let E(0; 2) be conver and twice-differentiable such that [|V =)]l2 S L and V=E(0; =) B for all E and E x )
Then objective perturbation satisfies (c, 8)-DP when X >
28 and
Loog(2/8))+
Differentially Private Gradient Descent DP-SGD is differentially private version of stochastic gradient descent which ensures privacy by clipping the per-example gradients at each iteration before aggregating them and adding noise the result. The update rule iteration is given by
0.11 02 - T/t
Σ clip(Ve((;=)) N(0,0
where 77, is the learning rate at iteration t. B, is the current batch at iteration f, a is the noise scale, and clip function that bounds the norm of the per-example gradients.
3 Analytical Tools
Existing privacy guarantees objective perturbation mechanism (Chaudhuri et al., 2011 Kifer et al.) 2012) pre-date modern privacy accounting tools such as Rényi differential privacy and privacy profiles. In this section, we present two new privacy analyses of objective perturbation: an (c, DDP bound based on privacy profiles, and an RDP bound.

---

3.1 Approximate DP Bound
Theorem 3.1 (Approximate DP guarantees objective perturbation for GLMs), Consider a loss
function E(0; =) = f(x 0;y) with GLM structure. Suppose that J is 3-smooth and [[ 2) 1|2 S L
for all 0 E + and 2 E X x y. Fix X > 3. Let 2 0 and let غ = log 1 8
x
3 ==
c log (1- log
L? 20² and let P and Q be the density functions of (II, and N(0,0²)
respectively. Objective perturbation satisfies (c,8(e))-DP for
2 Hp: (PIl)). 8(c) (1 e1 +e e
if' 2 0, otherwise.
12 (PI(Q),
(3.1)
602
Notice that we can express 3.1 analytically using B. To obtain the bound 3.1 we repeatedly use the fact that the privacy loss random variable (PLRV) determined by the distributions N(1, of) and (0, o²) is distributed as N ((2 ) As the upper bound (3.1) is obtained using a PLRV that is certain scaled and shifted half-normal distribution, we can also find certain scaled and shifted half-normal distributions P and Q which give the dominating pair of distributions for the objective perturbation mechanism such that the hockey-stick divergence between P and is exactly the upper bound (.1 for all c (shown in the appendix).
3.2 Rényi Differential Privacy Bound
our sole objective is to obtain the tightest possible approximate DP bounds for objective perturbation, we can stop Theorem 3.1. Directly caleulating the privacy profiles of objective perturbation using the hockey-stick divergence, as in the previous section, will achieve this goal (until more privacy accounting tools come along).
In this section we turn instead to Rényi differential privacy. a popular relaxation of pure differential privacy (8 = 0) which avoids the "catastrophic privacy breach" possibility permitted by approximate DP (5 > 0). Below, we present an RDP guarantee for objective perturbation.
Theorem 3.2 (RDP guarantees of objective perturbation for GLMs). Consider a loss function e(0; 2) = [a 0:y) with GLM structure. Suppose that f is B-smooth and ||VE(0; z)ll2 S T. for all
0 E θ and z X x Y. Fix B. Objective perturbation satisfies (a,, C--RDP for any a > with
8
L
1
( [e
== -
+
log E
20
a-1
For a = 1, the RDP bound holds with
== log (1-2)
L
(o [exx]]
(1-))
+
20 + log E
One of our main motivations for improving the privacy analysis of objective perturbation comes from the observation that it can be competitive to DP-SGD when the privacy cost of hyperparameter tuning is included in the privacy budget. As the tightest results for DP hyperparameter tuning are stated in terms of RDP (Papernot & Steinke 2022), in our experiments perturbation to get a clear understanding of the differences in the privacy-utility trade-offs between these two approaches.
RDP bounds of objective
Remark 3.3. Privacy profile and RDP bounds (such as Theorems 3.1 and 3.2 are unified in the sense that they are both based on certain bound of the PLRV <2,2 (Definition K.4) for fixed pair of datasets 7, Z'. From Definitions 2.2 and 2.7 we see that for E RR the hockey-stick divergence
He (2.(M(Z) M(Z)) = Ee-M(2)
[ - (x
and for we have that the Rényi divergence is
( a log BanMiz) [eacz
5

---

3.3 Distance to Optimality
How close to optimal are the bounds Theorems 3.1 and 3.2 We can in fact show that the Gaussian mechanism is special case of the objective perturbation mechanism thereby providing lower bound on its approximate DP and RDP.
Example 3.4. Consider the loss function f(0;z) = x and choose neighboring datasets X = {z} and X' = D, for some x E R.. Fix X 0 and sample ~ NO0, (a))- Then the objective perturbation mechanism solves
A
1
(x(x) = arg min x 0
1011 + 666 =
i 1x +b),
BER
X 11011 + +000 -
(x(X"== = min
BER"
2
Observe that (X) NN(-rs, Fa and (x') NoO, LTa)- Following the problem set- [[V((0; S L. In this case, objective perlurbation reduces directly to the Gaussian mechanism with sensifivity A = - and noise scale x. Corollary 3.5. As consequence of Example 3.4 and the scaling invariance of the hockey-stick divergence, for all a > 1 we have the following:
ting described in Theorem 2.8 we have that
Ha (0 () 0 (Z)) (N &) ( Ha (IN(LL
The argument works the same for the Rényi divergence Dr which is similarly scaling-invarian Corollary 3.5 implies that we measure the tightness of the bounds given in Theorems 3.1 and 3.2 by comparing them to the tight bounds of the Gaussian mechanism B. with sensitivity and noise scale a.
This means that in Figure [ the hockey-stick divergence of the Gaussian mechanism is a lower bound on the hockey-stick divergence for objective perturbation. While hockey-stick divergence bound is unsurprisingly a bit tighter than the RDP bound for objective perturbation, we see that both significantly improve the classic (c, 8DD bounds of Kifer et al. (002)).
10a
Kifer
10
10
RDP for ObjPert
HS ObjPert
10
10-3
HS GM
10-5
10-7
Kifer et al.
10-7
RDP for ObjPert
10->
HS for ObjPert
10
HS for GM
10-11
10-11
0.4
0.8
1.2
0.2
0.6
1.0
Figure 1: Comparison of different (c, 8)-bounds for objective perturhation: the (c, 6bouund by Kifer
et al. 2012) given in Thm. 2.8 the RDP bound of Thm. 3..2 the approximate DP bound of Thm. 3.1
using the hockey-stick divergence and the approximate DP lower bound obtained using the hockey- stick divergence and Cor. 3.5 Left: o 5.0, f 1.0 and À = 20.0. Right: a = 10.0, = 1.0 and 5.0.
Remark 3.6. The RDP and approximate DP bounds in this section require careful analysis of the dependence between the noise vector and the private minimizer gP. In the appendix, we show how the GLM assumption simplifies this issue.
4 Computational Tools
In this section we present Algorithm I. which extends the Approximate Minima Perturbation of Iyengar et al. (2019) to handle loss functions with unbounded gradient.

---

Approximate minima The privacy guarantees of objective perturbation hold only when its output is an exacr minimizer of the perturbed objective. Approximate Minima Perturbation (AMP) (yengar et al. 2019) addresses this issue by finding an approximate minimizer to the perturbed objective, then privately releases this approximate minimizer with the Gaussian mechanism.
Gradient clipping DP-SGD requires no a priori bound on the gradient of the loss function; at each iteration, the algorithm clips the per-example gradients above pre-specified threshold in order to bound the gradient norms. We extend this same technique to objective perturbation.
Given loss function E(f;2) and clipping threshold C, transform the gradient of ((8;2) as follows:
VE(O; =)
if [[ S C. [[((()))) VE(0;2) if [V C.
(0:20))) =
Then we can define the aggregation of clipped gradients as VLc () = V(c(02)) =EZ
The aggregation of clipped gradients VLc Z) corresponds to an implicit "clipped "aapeddgradient" objective function (0; Z). For convex GLMs, Song et al. (2020) define this function precisely and show that retains convexity and GLM structure the original objective function [(; Z). We furthermore demonstrate that this function retains the same bound / on the Lipschitz smoothness
(Theorem E.3
Algorithm ! extends the privacy guarantees of AMP (Iyengar et al. 2019) to loss functions with unbounded gradient. Notice that for smooth loss functions with gradient norm bounded by L, can set C L in order to recover Approximate Minima Perturbation.
Algorithm 1 Computational Objective Perturbation
Input: dataset Z; noise levels a, Jouz 3-smooth loss function E(.) regularization strength X; gradient norm threshold r; clipping threshold C.
1. Construct the set of clipped-gradies loss functions (fc(0;=) Z}.
2. Sample ~ oN
3. Let (0; b) EsEz (0(0; + 1011 - DTD.
4. Solve for such that CE Z)Ila ST.
Output: 0P + O0 Ta).
Theorem 4.1 (RDP guarantees of Algorithm| GLM structure, such that B-smooth. Fix x B. Algorithm 7 satisfies (a,e)-RDP for any with
Consider a loss function E(0; fxx ((x00;y) with
3 X
(0.()) [ +
2T
-lo 1
log E
2
X
Remark 4.2. Gradient clipping aside, our proof Theorem takes a different tack than the proof of Theorem 1 (for AMP) in Iyengar al. (2019). We observe that Algorithm [ is essentially adaptive composition of the objective perturbation mechanism and the Gaussian mechanism. We can write = ,²" + (Ō - oF)) to see that we are releasing two quantities: 0P (with objective perturbation) and the difference 0 - 8 (with the Gaussian mechanism). Algorithm I stops iterating only after the gradient norm |/ L Z)]l2 is below the threshold т. This along with the X-strong convexity of the objective function V CL (0; Z) ensures a bound on the &g 'g-sensitivity of the difference a- 0", so that we can apply the Gaussian mechanism.
4.1 Computational Guarantee
To achieve the optimal excess risk bounds for DP-ERN in the convex setting, DP-SGD clocks in at hefty O(n²) gradient evaluations (Bassily et al., 2014). has been an open problem to obtain optimal DP-ERM algorithms that runs in subquadratic time (Kulkarni et al. 2021). One of our contributions show that when we further restrict to smooth GI.M-losses (so ObjPert applicable) Algorithm can achieve the same optimal rate with only O(n log ra) gradient evaluations.
7

---

A formal claim and proof that Algorithm with appropriately chosen parameters achieves the optimal rate deferred Appendix The analysis is largely the same as those in (Kifer et al.) 2012) but with the bug fixed (details in Appendix G by adding GLM assumption.
The improved computational complexity is due to that algorithms to solve Step 4 of Algorithm Observe that (0; Z, b) has a finite-sum structure, we can employ the Stochastic Averaged Gradient (SAG) method (Schmidt et al. 2017) which halts in On log with high probability. Details are provided in Appendix
apply any off-the-shelf optimization
5 Empirical Evaluation
In this section evaluate Algorithm [against baselines: "dishonest" DP-SGD and "honest" DP-SGD. Dishonest DP-SGD does not account for the privacy cost of hyperparameter tuning; honest DP-SGD follows the private selection algorithm and RDP bounds from Papernot & Steinke (2022).
Our experimental design includes some guidelines in order to make it a fair fight. One of the strengths of Algorithm [ that we advocate for is its blackbox optimization. Whereas DP-SGD consumes privacy budget for testing each set of hyperparameter candidates, an advantage approximate minima perturbation is that the privacy guarantees
independent of the choice of optimizer used to solve for 9. We therefore test out any number of optimization hyperparameters for Algorithm a no additional privacy cost, provided that these parameters are independent of the privacy guarantee (e.g. learning rate, batch size). More specifically, once the loss function perturbed with the noise b in Algorithm 1 any 9 that satisfies the convergence guarantees with the tolerance parameter will have the RDP- -DPggaarattees of Theorem 4.1 and therefore we are free to also carry out tuning of the optimization algorithm without an additional privacy cost.
and
Because we are interested in measuring the effect of the privacy cost of hyperparameter tuning, we tune only the learning rate which does not affect the privacy guarantee of the base algorithm. This isolates the effect of pepraaarrerter tuning as we will need to appeal to Papernot Steinke (2022) to get valid DP bounds for DP-SGD, but Algorithm Menooym hyperparameter tuning "for free".
The following table summarizes the optimization-relttee parameters for all three methods.
Dishonest DP-SGD
Honest DP-SGD
Algorithm I
clipping
C= /2
C v2
C= v2
learning rate
log 10 ", 9,10-1
log(10 10 ..1011
Ameea(.08,.0 5))
grid size
$ == 10
~ Poisson (1) s.t. Pr K
0.9
8 = 10
optimizer
Adam
Adam
L-BFGS
convergence
after T iterations
after T iterations
VL ST
The choice of C /2 is natural value for logistic regression in that (V((0,2)]] v2 for all 8, 2 due to data-preprocessing and the bias term. Dishonest DP-SGD selects 10 learning rate candidates evenly log-spaced from the range of values between 10-8 8 and 10-1 -1 Honest DP-SGD selects learning rate candidates from the same range of values, but with granularity determined by random variable K sampled from the Poisson distribution Poisson(ı1) We select μ that with 90% probability, is larger than the grid size used for dishonest DP-SGD, resulting in R 15.4.
We use the Adam optimizer for both honest and dishonest DP-SGD For Algorithm I we use the L-BFGS optimizer whose second-ordes behavior allows us to get within a smaller distance to optimal (as required by Algorithm
For SGD we set the subsampling ratio such that the expected batch size is 256 and we run for 60 "epochs". . We calculate the number of iterations as T = 60 num_batches, where num num_ batcbestceessss is the number batches the training dataset (we pass the train loader through the Opacus privacy engine, so the size of each batch is random). To calibrate the scale of the noise for DP-SGD, we use
the analytical moments accountant (Wang et al. 2019) with Poisson sampling (7hu & Wang 2019
Mironov et al. 2019).
8

---

The parameters specific to AMP are Jout, the noise scale for the output perturbation step; and the gradient norm bound. larger will improve our computational cost, though our approximate minimizer d will farther away from the true minimizer P We can achieve smaller by choosing a larger oott, but this will mean that our release will be noisier. our experiments we fix 0.01 and Cott 0.15.
The privacy parameters of objective perturbation are the noise scale and the regularization strength A. Balancing these parameters is a classic exercise in bias-variane trade-off. A larger will allow us use less regularization, but if is too large then we risk adding too much noise the objective function and hurting utility.
Our strategy is find the smallest possible À such that isn't too large. To quantify when is "too large", we use the Gaussian mechanism as a reference point: the noise scale a for objective perturbation shouldn't be too much larger than the noise scale ag for the Gaussian mechanism. Let's say that the Gaussian mechanism with noise scale ag satisfies (t, d)-DP, then we want our a for (e, DDD objective perturbation satisfy fog for some small constant factor In experiments, we set f 1.3. 1.3.
For objective perturbation, (e.g., e, GG) that are independent the data. Likewise, the choices of Gott and are fixed across all datasets. This is noteworthy since A, out and each have effect the privacy guarantee, outside of the blackbox algorithm. Tuning these parameters on the data would require us to use the private selection algorithm.
thus select the privacy parameters and À using fixed values
Synthetic-L
Adult
84
90
Test Accuracy
Test Accuracy
82
80
80
DP-Adam (dishonest)
DP-Adam (dishonest)
78
70
Algorithm
Algorithm
DP-Adam (honest)
Adam (honest)
76
10:1
10"
10a
10
10a
10
Privacy-e
Privacy-e
Synthetic-H
Gisette
90
90
Test Accuracy
Test Accuracy
80
80
70
70
DP-Adam (dishonest)
DP-Adam (dishonest)
60
Algorithm
Algorithm
60
DP-Adam (honest)
DP-Adam (honest)
50
10-1
100
10a
10
10
10a
Privacy-e
Privacy
Figure Comparison of Algorithm againstt honest and dishonest DP-SGD baselines, varying E {0.025, 0.05, 0.1, 0.25, 0.5, 1.0, 2.0, 4.0, 8.0} and fixing 10-5 On all three methods, train the model for each learning rate on its grid (see Table and report the test accuracy for the best learning rate the grid. Results are averaged over 10 trials and the error bars both sides of the mean values depict 1.96 times the standard error, giving the asymptotic 95% coverage.
We evaluate our methods for binary classification on the Adult, Synthetic-L., Synthetic-H and Gisette datasets provided by Iyengar et al. (2019). We normalize each row z; to have unit norm. Note

---

that the assignment f Tæzlll doesn't tt require expending any privacy budget as each data point is transformed only by its own per-sample norm.
Table 1: Synthetic-L
Table 2: Adult
Dishonest
Alg 1
Honest
Dishonest
Alg 1
Honest
c
0.1
93.85%
90.05%
77.34%
c
0.1
81.61%
81.37%
78.32%
1
95.25
94.50%
93.15%
83.54%
83.18%
82.40%
8
95.43%
95.30%
95.17 %
8
84.19%
83.99%
83.66%
Results from Figure in numerical format for the low-dimensional datasets, Synthetic-L and Adult. For = 0.1, these can be cross-referenced with the results in Fig. 3 from (lyengar et al. 2019).
The experimental results shown in Figure Table | and dishonest DP-SGD is clearly the best-performing algorithm, when we account for the cost of hyperparameter tuning then Algorithm can typically best honest DP-SGD, This effect is especially pronounced under small e, for which diverting some of the limited privacy budget to hyperparameter tuning could be more impactful.
a consistent picture. While
Is it fair? Our experimental design aims to fairly compare ObjPert to DP-SGD. One limitation, however, is that the state-of-the-art tools for private hyperparameter tuning from Paperrott & Steinke (2022) are RDP bounds - and RDP is not state-of-the-ar for DP-SGD privacy accounting. At this moment, the tighest privacy accounting tool for DP-SGD is the PRV accountant from Gopi et al. (202I), which is the counterpart to our privacy profiles analysis for ObjPert (Theorem 3.1) Unfortunately, even though dishonest DP-SGD would benefit from using the PRV accountant, for private hyperparameter tuning we would then have to use the sub-optimal private selection bounds for approximate DP from Liu & Talwar (2019). In experiments we therefore
RDP-based privacy accounting for both Pbjiert and DP-SGD. Comparing DP-SGD with numerical composition against ObjPert with Theorem 3.1 will have to wait until more private selection tools are available.
One might also object that by tuning only the learning rate for DP-SGD, we didn't 't explore the full range of hyperparameters relevant to DP-SGD's performance. While tuning additional hyperparame- ters such as the batch size and number of epochs could benefit dishonest DP-SGD, it would likely worsen the privacy-utility tradeoff for honestly-tuned DP-SGD due the increased privacy cost of the hyperparameter tuning algorithm from Papernot & Steinke (002)).
6 Conclusion
One point that we really wanted to drive home is that while DP-SGD works extraordinarily well across wide variety of problem settings, it's not necessarily the best solution for every problem setting. But at the same time, DP-SGD has received the benefit of an enormous amount of attention that other DP learning algorithms haven't 't received. A goal of paper to hone in on particular problem setting and give a different algorithm the same star treatment.
Objective perturbation now boasts two new privacy analyses. One is an improved (e, 0)-D analysis based on bounding the hockey-stick divergence. The other is an RDP analysis which allows us to fairly compare objective perturbation against DP-SGD the workhorse of differentially private learning with honest hyperparameter tuning. We've also expanded the approximate minima perturbation algorithm of Iyengar et al. (2019) in order to encompass broader range of loss functions which need not have bounded gradient. Our algorithm moreover can be used in conjunction with SVRG to guarantee running time of O(n log n) to achieve the optimal excess risk bounds, improving on the On²)) computational guarantee of DP-SGD.
Acknowledgments
The work was partially supported by NSF Award #2048091.
10

---

References
Abadi, M., Chu, A., Goodfellow, I., McMahan, H. B., Mironov, I., Talwar, K., and Zhang. L. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference computer and communications security, pp. 308-318, 2016.
Agarwal, N., Kale, S., Singh, K., and Thakurta, A. Differentially private and lazy online convex optimization. In The Thirty Sixth Annual Conference on Learning Theory, pp. 4599-4632. PMLR, 2023.
Balle, and Wang. Y.X. Improving the gaussian mechanism for differential privacy: Analytical calibration and optimal denoising. In International Conference Machine Learning, pp. 394-403. PMLR, 2018.
Balle, B., Barthe, G., and Gaboardi, M. Privacy amplification by subsampling: Tight analyses via couplings and divergences. In Advances in Neural Information Processing Systems, pp. 6277-6287, 2018.
Balle, B., Barthe, G., Gaboardi, M., Hsu, J., and Sato, T. Hypothesis testing interpretations and renyi differential privacy. In International Conference on Artificial Intelligence and Statistics, pp. 2496-2506. PMLR, 2020.
Bassily, R., Smith, A., and Thakurta, A. Private empirical risk minimization: Efficient algorithms and tight error bounds. In 2014 IEEE 55th Annual Symposium Foundations of Computer Science, pp. 464-473. IEEE, 2014.
Bun, M. Dwork, C., Rothblum, G. and Steinke, T. Composable and versatile privacy via truncated cdp. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pp. 74 86, 2018.
Canonne, C. L., Kamath, G., and Steinke, T. The discrete gaussian for differential privacy. Advances in Neural Information Processing Systems, 33:15676-15688, 2020.
Chaudhuri, K., Monteleoni, C., and Sarwate, A. D. Differentially private empirical risk minimization. Journal of Machine Learning Research, 12(3), 2011.
Dwork, C., McSherry, F., Nissim, K., and Smith, A. Calibrating noise sensitivity in private data analysis. In Theory of cryptography conference, pp. 265-284. Springer, 2006.
Gopi. S., Lee, Y. T., and Wutschitz, L. Numerical composition of differential privacy. In Advances in Neural Information Processing Systems, 2021.
Iyengar, R., Near, J. P., Song, D., Thakkar, O., Thakurta, A., and Wang, L.. Towards practical differentially private convex optimization. In 2019 IEEE Symposium on Security and Privacy (SP), pp. 299-316. IEEE, 2019.
Kairouz, P., McMahan, B., Song, S., Thakkar, O., Thakurta, A., and Xu, Practical and private (deep) learning without sampling or shuffling. In International Conference on Machine Learning, pp. 5213-5255.. PMLR, 2021.
Kifer, D., Smith, A., and Thakurta, A. Private convex empirical risk minimization and high- dimensional regression. In Conference on Learning Theory, pp. 25-1. JMLR Workshop and Conference Proceedings, 2012.
Koskela, A., Jälkö, J., and Honkela, A. Computing tight differential privacy guarantees using FFT. In International Conference on Artificial Intelligence and Statistics, pp. 2560-2569. PMLR, 2020.
Koskela, A., Jälkö, J., Prediger, L., and Honkela, A. Tight differential privacy for discrete-valee mechanisms and for the subsampled gaussian mechanism using FFT. In International Conference Artificial Intelligence and Statistics, pp.
PMLR, 2021.
Kulkarni, J., Lee, T., and Liu, Private non-smooth erm and sco in subquadratic steps. Advances in Neural Information Processing Systems, 34:4053-4066 2021.

---

Liu. J. and Talwar, K. Private selection from private candidates. In Proceedings of the S1st Anmual ACM SIGACT Symposium on Theory of Computing, pp. 298-309, 2019.
McKenna, R., Paskov, H., and Talwar, K. practitioners guide to differentially private convex optimization. 2021.
Mironov, I. Rényi differential privacy. In 2017 IEEE 30th computer security foundations symposium (CSF), pp. 263-275. IEEE, 2017.
Mironov, I,, Talwar, K., and Zhang, I.. Rényi differential privacy of the sampled Gaussian mechanism. arXiv preprint arXiv:1908 10530, 2019.
Mohapatra, S., Sasy, S., He, X., Kamath, G., and Thakkar, O. The role of adaptive optimizers for honest private hyperparameter selection. In Proceedings of the aaai conference on artificial intelligence, volume 36, pp. 7806-7813, 2022.
Neel, S., Roth, A., Vietri, G., and Wu, S. Oracle efficient private non-convex optimization. In International Conference Machine Learning, pp. 7253-7252. PMLR, 2020.
Nguyen, L. M., Dijk, M., Phan, D. T. Nguyen, P. H., Weng, T.W., and Kalagnanam, J. R. Finite-sum smooth optimization with sarah. Computational Optimization and Applications, 82(3): 561-593, 2022.
Papernot, N. and Steinke, T. Hyperparameter tuning with Rényi differential privacy. In International Conference on Learning Representations, 2022.
Redberg, R. and Wang, Y.-X. Privately publishable per-instance privacy. Advances in Neural Information Processing Systems, 34, 2021.
Schmidt, M., Roux, N., and Bach, F. Minimizing finite sums with the stochastic average gradient. Mathematical Programming, 162:83-112, 2017. 2017.
Sommer, D. M., Meiser, S., and Mohammadi, E. Privacy loss classes: The central limit theorem in differential privacy. Proceedings on Privacy Enhancing Technologies, 2019(2)2455-66,, 2019.
Song, S., Chaudhuri, K., and Sarwate, A. D. Stochastic gradient descent with differentially private updates. In 2013 IEEE Global Conference on Signal and Information Processing, pp. 245-248. IEEE, 2013.
Song. S., Steinke, T., Thakkar, O., and Thakurta, A. Evading curse of dimensionality in unconstrained private glms via private gradient descent. arXiv preprint arXiv:2006. 067883, 2020.
Wang, D., Ye, M., and Xu, J. Differentially private empirical risk minimization revisited: Faster and more general. Advances in Neural Information Processing Systems, 30, 2017.
Wang, Y.-X., Balle, B., and Kasiviswanathan, S. Subsampled rényi differential privacy and analytical moments accountant. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 1226-1233 PMLR, 2019.
Yu, D., Zhang, H., Chen, W., Liu, T.-Y., and Yin, J. Gradient perturbation is underrated for differentially private convex optimization. arXiv preprint arXiv: 19111319 2019.
Zhu, Y. and Wang, Y.-X. Poisson subsampled Rényi differential privacy. In International Conference on Machine Learning, pp. 7634-7642, 2019.
Zhu, Y., Dong, J., and Wang. Y.-X. Optimal accounting of differential privacy via characteristic function. In International Conference Artificial Intelligence and Statistics, pp. 4782 4772-4817. PMLR, 2022.
12

---

Appendix
Table of Contents
Notation
14
Warm-up: Gaussian Mechanism
14
B.1 Privacy protile of the Gaussian Mechanism
14
B.2 RDP Analysis of the Gaussian Mechanism
14
RDP analysis of objective perturbation
Lincarized RDP Bound for Objective Perturbation
D Hockey-stick Divergence Analysis of Objective Perturbation
19
D.J Further Details on Hockey-stick Divergence Analysis
19
D.2 Proof of 3.eorem].1
20
D.3 Dominating Pairs of Distributions for the Objective Perturbation Mechanism
22
D.4 Auxiliary Lemma
23
RDP guarantee Algorithm]
24
Privacy Guarantee for Approximate Minima Perturbation
24
E.2
The "rrapied- Function
25
F
Computational Guarantee of Algorithm
26
F1 Tools from optimization
................................
27
Computational bounds for Stopping small gradient
27
G The GLM Bug
29
G.
Discussion
29
G.2 RDP bound for non MLM-GLMs
29
Empirical Risk Algorithm
Generalized Linear Model
31
Distance to Optimality
32
Bridging the Gap between Objective Perturbation and DP-SGD
32
J.1 RDP Objective Perturbation vs DPD
32
1.2 A Spectrum of Learning Algoritmms
Technical Lemmas & Definitions
34
K. Convex Optimization
34
Differential Privacy
34
13

---

A
Notation
Denote the following:
[()) Σ 4())) 1=1
-x( (()) + 1.
(0) L()) + 111111 + bTo, b b~N(00,0
0 arg min [(0), MER
0x arg min (0), DER4
P arg min (0).. BER
0 satisfies | /V S
0P = + b b2 NN, P Ta).
We take || to be the size of the data domain X, i.e. |||||| = sup ||]|| For conciseness of presentation we sometimes drop the dataset Z from the notation, e.g. we abbreviate L(0; Z) as L(0).
Sometimes (especially in the proofs that follow) we will abuse notation by overloading a function with its output, e.g. 0 is the output of objective perturbation and (*( is the objective perturbation mechanism.
B Warm-up: Gaussian Mechanism
We will get started by reviewing the RDP and privacy profile bounds for the Gaussian mechanism. Once warmed up. we then present the RDP and privacy profile bounds for objective perturbation in Sections[[and
Consider the Gaussian mechanism defined by ([())f(22)) (177)=W(0,,, o2)) for function Z R with global sensitivity A maxz=z [[f(Z) f(2')]22.
B.1 Privacy profile of the Gaussian Mechanism
Analytic Gaussian mechanism (Balle & Wang 2018).
Let P and Q be the density functions of (iA,, o²) and (0 o²), respectively. Then (P,Q) is dominating pair of distributions for M, and M tightly (c. ((e()))-D for
= ea
As 20
(- Ea
A1 20
8(e) H. -
e
(-2,
(B.1)
A
A,
where & denotes the CDF of the standard univariate Gaussian distribution.
We can analytically express a tight upper bound for the Gaussian mechanism above, but in general numerical methods are needed to evaluate the hockey-stick divergence for dominating pairs of distributions. This is discussed with more detail in Section
B.2 RDP Analysis of the Gaussian Mechanism
Theorem B.I (RDP guarantees of the Gaussian mechanism). The Gaussian mechanism M satisfies
A7a
(a, RDDD for 1 and e 2
14

---

C RDP analysis of objective perturbation
In this section we present the proof of Theorem 3.2 one of our main privacy results; an RDP bound on the objective perturbation mechanism.
Proof of Theorem 3.2 Recall from Definition 2.7 that the objective perturbation mechanism &P:
3 - RR satisfies ((n)i differential privacy if for all neighboring datasets Z and Z',
Da (ŌP (2) <(()).
Assume that Z E - and construct Z' = by adding datapoint to Z. Note that this convention (while convenient for writing down the PLRV of objective perturbation) comes with loss of generality, As consequence of asymmetry the upper bound on the RDP must satisfy
(Da(o"(2)) (2) Do (0)
s E(a)).
We will calculate the Rényi divergence Da (0 (2) || 0 (Z)) of objective perturbation under change of measure:
P(x)
1
P(x)
a-1
D. D. = a a-1
log E
log Egnp
Q(x)
a
Q(x)
(Z)=" Pr (2)
Let R(OP)=
be shorthand for the probability density ratio output OP. Then
(a(0((Z))) (2)11
a - log Bp (2)
R(0P)(aa-))
log (as|R(PP ((a0))a-)))
a log E BUr PpP- (6)(2)
c (11-1)log 1(0P)) [
log Eyr (0-
0
0 log Eyp E (2)
R((
Denote [(;; = Ezez 2(0:2) + 1110 and p(0, Z, = x²
-1 x.
From Lemma K.9 and the A-strong convexity of J(0; Z). we can bound μ((0, Z, 2) by |= +
A
We also know from the L--Lipshhizness of {(B: 2) and the B-smoothness of ((xT0:)) v) that [|V 2)l S L and f"(= S for all Idd and (a, v) E Z.
Then using the GLM assumption, from Redberg & Wang (2021) we can bound the absolute value of the log- probbabibyyy ratio for any 8" as
(z) = pr]
Pr
1
log Pr
< log (1- (x=:0(=00) ,2,=))
Ve :2)1
(P(Z') = gr
20
| log (1 (x (lTToP:v)ulee v)((0" 2,,2)
Ve(00
:2)
VJ ; " V :2)
20
< log (1 (1- 2
1
1
2 V) ;=)
2a
It is more challenging to find data data-independent bound for the third term due to the the shared dependence on 8".
'This is in contrast to the symmetry of the Gaussian mechanism M(Z) = S(Z) + +N(00 o La).
ad}
which case c(a) can be calculated exactly (a(,0,, || N((A,,
20
Da (Ni(A, o21a) A 14)))
15

---

Recall that b n~ (0(0, is the noise vector in the perturbed objective. By first-order conditions at the minimizer 8
b b= -==V] 2)
If PP were fixed (or if PP were independent to b), the quantity VJ V) :2) -b" V'((0)=)) would have been distributed as a univariate Gaussian (N VV ;1) Unfor- tunately in our 0 is random variable, and consequently we don't have the tools understand the distribution of J 2) 2)' = for an arbitrary loss function.
But using the GLM assumption the loss function,
write
VJ 2002))(((00 -b" (x"x0""00
Observe that x fixed w.r.t. b so that -b this scalar is a random variable that still depends b in complicated way, the worst possible dependence can be more easily quantified without incurring additional dimension dependence.
x ~ (O0, 0² 2= and f'(x"0, 0. y) is a scalar. So while
By the L-LLipschitz assumption and lab| s |a|lb], we obtain the following bound:
:z)
Op (0) =z)=
S V (1; x]
This is much better! By first-order conditions we can then see
L L = (V o2 ~ Half-Normal(o
-
Now we can bound
L
1
log R((0)) s - log
VJ(0"; "20://((220 ve(0";2)
+
+
X
20
a²
B
2
L
$ log
+
+
VJ(OP: ;
20
0²
Plugging in this bound on log R(OP)).
Da(0P 0 (Z)))
log E OF ( (2)
é 11 R[
(a- 1 loR(1 (1 +)1+ -
(a-1). 2a VJ(0 =))=
log E
Egrnn (d))))
L
1
log Bgr (g))))(2) [ (aa11) v (
:2) #1]
log
+
+
20
Let be the probability density function of ~ No 2 and pe the probability density 00
function of gP ~ (Z)).. We know from Lemmas K.6 and K.7 that 0e = dct ab
Öb, and
ab
pe (0)
det
Pa (b).
00
00
Øb
We also know from Lemma K.8 that
det
det
Øb
00
16

---

Using the change of variables b = -VJ(6P Z)
and b" x== -N o (= we have
Eg (2) { =1 =
(a-1)- :2) pe (0")
00
Rd
00
cla
det 00
Po (b)
det
0b
bb
caa11)
16"
Po (b)0b
JR"
(la-1)) ./ 16
(bnN((,,021))
[c
Eu-A110,071a
[ea-DDK1]
S E
(,
In the last line, we applied our assumption that || I and the fact that the MGF of half-normal R.V. increases monotonically when its scale parameter gets larger.
The above bound holds for the reverse Rényi divergence Do (0 (2)((2)))) (2)). Observe that
Da D0 (Z)) 0 (2)) S log BOP [ (aa-1)|log R(O"))]
P= (2))=""
This is because log
log R(OP) < log R(OP))
I. If we use the change of variables
(Z)
b = (e(;;; Z') for the reverse direction, the above calculation works out identically (the difference is that pe and the bijection between b and 0" are different under Z and Z' but the determinant of the mapping cancels out with its inverse just the same).
Da (aa (2) (10P Da (a (2) < <((a) for any neighboring
We've shown max
datasets Z and Z', where
E (a- ( (a
c(a) = -loo
1 X
+ 20
+
C.1 Linearized RDP Bound for Objective Perturbation
In our calculation of the RDP for objective perturbation, we needed to take an absolute value of the privacy loss random variable in order to handle negative values. But in doing so we end up with quantity that depends on the moments of the half-normal distribution rather than those of the normal distribution, which gives us a looser bound. Can we avoid having to make this compromise? In this section we demonstrate that a linearization of the first-order conditions on the perturbed and unperturbed objective functions provides more precise analysis of the PLRV of objective perturbation, translating tighter RDP bound in some regimes.
Recall that the objective perturbation mechanism is given by
("(Z) e(0: zi) アタ +
(C.I)
where N((00021)))
From the non-linearized RDP calculation, we know that for any neighboring datasets Z and Z',
Do 12) < - log (1-
1
log (s-,((0,021)) [cla-1)
20
where Pp is the output of the objective perturbation mechanism given the noise vector b. We can write
b7 Te((P) = 5' (((()) + +
17

---

The first term i = b" ( is a univariate Gaussian t ~ NN V ((())) because 0% is fixed w.r.t. b. We can bound the second term i2 = 6" [V((0") ve(02)) using our assumptions on the loss function {()).
By assumption, the loss function has GLM structure ((0;z) - f(x² 0; v). We can therefore write
6d (Ve(6")-vete 6" [f y) f'(x'' 07: [)
= 6z x (f' f' (x'00 01:
We have furthermore assumed that the function is 3-smooth, so that for any 2 = (x, y) and gp, O% E Rd we have
|0(=00p0)) f < 3 3 T - -xTOg
3
_ I0P x
871
We will next apply Taylor's Theorem to rewrite 8º 8 Recall that 6 is the minimizer of the perturbed objective:
8º arg min
Σ
n
X E(O: 2,)
1111 b'
(C.2)
and 0 is the minimizer of the (non-private) regularized objective:
A 0 arg min Σ (00;z))+
+
(C.3)
Parameterize the line segment between 0" and 08 by E [0, 1]. i.e. the line segment is -0)-00))+0 +0". By Taylor's Theorem, there exists 0' 1'( 02) + 0t for some 1' E [o, 1] such that
V((0") - VE(O3) = V'E(O') -2).
By first-order conditions Equations C.2 and C.3
VL(0P) + XO
(C.4)
VL(()) + A0 = 0.
(C.5)
Then subtracting Equation C.5 from Equation C4 we have that
VL(PP) VC(()) + A(0P 0%) + bb= 0.
(C.6)
Again applying Taylor's theorem, there exists 8" (0P - 07) + 0 for some t" E (0, 1) such that
V VL(6P) V(()) = 42 L(0") 02).
(C.7)
Putting together Equations C.6 and C.7 we then have
g 8 = (v"c(0") + -la) -'b. b.
(C.8)
So we now have
6T [
< 10 ToT (OP -05)
s </ TTTT (V2 ((0)) X12) -1a) b).
(C.9)
Note that since e² 0 for x E I. we have that E ||e0]] [e
Let = ((((0) and bT [Ve(OP)- - ve(0r). Then by Holder's inequality,
18

---

E c(a
a 1ja
(0
1)c
1
2 1)
E
(a
1]c
E
clpa pla
E
lllaa-g0 g/cc
By the GLM assumption, 6" 2)( f xx= 0):4)6" x. Then
E [c(ma-)) v=((")
Ei~Ni0,021a (e (000-p) atx (0 "212))"
(pa (pa-p)uz
Above, we' ve applied the assumption that ||>|| I and the fact that the MGF of normal R.V. increases monotonically when its scale parameter gets larger (Lemmal K.11). By Lemma K.9 we
|
have that T (V2L( + Ia) 2x =
From C.9 we also have
X²
BB--(0,021a)) (1=00))
< BB
Define 21 62 and 22 = x²' (V²C(0)) Ala) b. and observe
N 00,02|1=011
22 ~ N 00,02x (a))
1a)
Note that our approach below agnostic to the relationship between |²1| and [22| in reality, they depend each other through the noise vector b. Again applying the assumption ||>||| 1 and Lemma LeII (while not forgetting that the random variables 21 and 22 depend on each other through
b), get
(6, (000-))))0" (0" (V2
E ExL. (0000-)81e2111))
100 (0a-0)31ss|124
[go (ga-g) 9) 1z
EE~N(0.0') (100
So altogether, for p. such that + 1, we get
Da (2)
- -log logg (1-1)
1
I + a-
[clm--pa]]] Enn [cloa-0)807]
log E u~ (2)
202
D Hockey-stick Divergence Analysis of Objective Perturbation
D.I Further Details on Hockey-stick Divergence Analysis
Using dominating pairs of distributions (Def. 2.5 for all the individual mechanisms in an adaptive composition, we can obtain accurate (c, -bounds for the whole composition. For this end we need the following result.
19

---

Theorem D.1 Zhu et al. 2022). (P.Q) dominates M and (P', .P) dominates M' for all inputs of M', then (P P Q Q") dominates the adaptive composition M M'.
To get the hockey-stick divergence from P P' to Q x Q' into an efficiently computable form, we express it using called privacy loss random variables (recall Def. K.4). If P and Q are probability density functions, the privacy loss function P is defined as
Lr/Q(z) = log P(x) ((x)
and the privacy loss random variable (PLRV) wp/Q as
hP/Q = ( I P(x).
The ((e)-bounds can be represented using the following representation that involves the PLRV. Theorem D.2 (Gopi al. (202T). We have:
He. (PI())
E amp
1100
e-
(D.1)
Moreover, if w/ is the PLRV for the pair of distributions (P, Q) and wp' for the PLRV for the pair of distributions (P', Q'), then the PLRV for the pair of distributions (P PPPP. Q x Q') given by wr/Q + wP /Q'
By Theorem D.2, computing accurate boounds for compositions, it suffices that we can evaluate integrals of the form Exway tw.. [1 e Transform (FFT)-based method by Koskela et al. 2021p, I, where the distribution of each PLRV truncated and placed on an equidistant numerical grid over interval [- T., L.J. where >>> 0 is pre-defined parameter. The distributions for the sums of the PLRVs are given by convolutions of the individual distributions and can be evaluated using the FFT algorithm. By careful error analysis the error incurred by the numerical method can be bounded and an upper ò(e) -bound obtained. For accurately carrying out this numerical computation one could also use, for example, the FFT-based method proposed by Gopi et al. (202T)
For this we can use the Fast Fourier
D.2 Proof of Theorem 3.1
Before giving a proof to Thm. 3.1, we first give the following bound which is a hockey-stick equivalent of the moment-generating function bound given in Thm. 3.2
Lemma D.3. Let R. and let the objective perturbation mechanism 0P be defined in Section 2.2 Let ((0; 2) S L. and (2( < BIa for all 0 E O and z E X y. Then, for any neighboring
datasets Z and Z", we have:
Har (0P (Z)]16P(2)) (Z'))
Enowl - e e
(D.2)
where w ~ loog (1-
~|108
12 N
0²
Proof. The proof goes analogously to the proof of Thm. 3.2
Let Z and Z' be any neighboring
datasets. Following the proof of Thm. 3.2 denote the privacy loss
Pr 0
(2) -0
R(0)
Pr (P(Z")
By Thm. D.2 by using the reasoning of the proof of Thm. 3.2 for the moment-generating function,
have Her (2)]10P((2)) (Z')) = -E ( -o R(0)
E E - flog R((0]]]
(D.3)
s (n --- +)1 20 -1++
where the inequalities follow from the fact that the function f(x) = 11 cec-== is monotonically
increasing function w.r.t. 8 for all E R and from the bound for [R(0) used in the proof of Thm. 3.2
D
20

---

Proof of Theorem 3.7 We use Lemma D.3 and simply upper bound the right- hand side of the in-
equality (.2).
We first show that if ||||| S 1, then for all e E IR
E
[og(( (1- 2)| 20 Mio, 1=1222)
[1 - E "I+ S (too 222 |vro 2 -
e) (D.4)
Denote é= ccc
log 1 (1- 2)
20² Consider first the case é 2 0. Then, we have:
E
an [110, _
e-- 1og(1 (1- 8)1
20
22
I1 +
2. E
N 1 - 11-x,,11---91) -6
S E
No. ( [1 - +
E = - e1-e- ee log(1 (1 - f)1-
sn No.
-
20
22
(D.5)
where the first equality follows from the fact that for 2 é, the density function of the half-normal random variable is positive and 2 times the density of the corresponding normal distribution. The inequality follows from Lemma D.8 as
7 = fea0
000
E (0, 1=12
S 1m1ee (x) - =)=3) dx.
Next, consider the case & < 0. Then:
E sny Noo 101222 I e- (oo(1 1 f 20
f
f 0. 101320 (I) - (1oo 23 =) dx
* = 2.
0
f 12 (x) (1 c1- 10011-f0 -2 -+)1-111 11-22-- =) dx
110(1
S 2
sn/ ( c- |oo(1 (1- + 2 *T+
E
(D.6)
where the inequality follows from Lemma D.8 Inequalities Then, show that for all E IR,
D.5 and D.6 together give D.4).
2 H (PI()) (1-c9) cf) + c² 2. H 13 (PIIQ).
if 2 0, otherwise.
(C, :3 ( 11- =,
sn/[ing(1 1 2)1 2nd
Continuing from D.5). by change of variables, we see that for é 2 0,
2 N0 2 [1 ex -0|llog(1 +) 14
*I+ = 2 N 20 2
e-
1og(1 (1- -1+
2 H. (PIIQ).
where غ = log (1 3){
P is the density function of N ((, o²) and Q the density function of NO0.00) This follows from the fact that the PLRV determined by the pair (P, Q) is distributed as W 5.
Continuing from D.6), by change of variables (used after the third equality sign), we see that for EzO,
fo 12 (1) é (1og(1 2)1 222 -3) dr
2.
= 2. | f (x) dx dx-xx-21 10d (0,13 (x) - cf- dr
(I)
/ (, (x) 2. l (x) - =-) dx
= (1 - e (..2. J
) +el 2 Su La (x)
620 - dx
12
= (1 - e ) + t 2.
s~ii 62 12 ,1
0z.
2nd
(1 - c + 2 H 12
P P())),
220
21

---

where we again use the fact that the PLRV of the Gaussian mechanism with sensitivity L and noise scale distributed as ( L 20 g²)
D.3
Dominating Pairs of Distributions for the Objective Perturbation Mechanism
From Lemma D.3 and the inequality (D.4) we have that for all e E RR
He. (0" (Z) 0 (Z))) ww (1) 20 1
Thus, if we have distributions P and Q such that for all c CE R
He (Pl()) = E w>||ion( (1- --) + |N[o
-
then the pair (P, Q) is a dominating pair of distributions for the objective perturbation mechanism. Then, by Theorem D.2 we can use this distribution w also to compute (e, -b-bundss for compositions involving the objective perturbation mechanism. We give such a pair of distribution (P, Q) explicitly in Lemma De6]below.
In the following, we denote the density of a discrete probability mass by a Dirac delta function and use the indicator function for the continuous part of the density. The following result is straightforward calculation.
Lemma D.4. Let > O. Let P be the density function of W (0, (0, ie.
P(x)
(x))
(D.7)
V2T02
where (x(x) denotes the indicator function, i.e, 10, (z) 1f 2 0, else (x)))))()) = 0. Let
L > 0 and let Q be a density function, where part of the mass of P shifted to 000
2
Q(x) = Q(-00) - (x)
(x),,
(D.8)
2
where
Q(-00) =
20
dx.
2TO2
Then, we have that the PLRV w.
P
w log
P,
(D.9)
(xx)
is distributed as
1
1
N
0,
20
02
Proof. As P has its support on [D, oo), need consider the values of the privacy loss function P(x) only on [0, oo). We have, for all x 2 0,
log Q(x)
P(x) log Q(r) σ r +
L
20
Since P, that L I (o. 2 and the claim follows.
Remark D.5. In Lemma D.4 instead of shifting part of the mass of P to when forming Q, could place this mass anywhere on the negative real axis. This would not affect the PLRV w.
We can shift the PLRV w given by Lemma D.4 by scaling the distribution Q. We get the following. Lemma D.6. Let a > 0 and 0. Suppose P is the density function given Eq. D.7 and Q the density function
Q(x) = Q(-o0) 0 (x) + |log(1 [0)(1-+))
-(1-))
20
(x)00)))),
(D.10)
2TT²2
22

---

where
Q(- -(1-) -log(1 (1-
(1-e- 2)1.
2
-ie-2)22
dx
V2TT22
Then, the PLRV w determined by P and Q is distributed as
log (1- 8
1,2
1.2
w
+
N
0.
20
0²
Proof. Showing this goes the proof of Lemma D.4
We just now have that for all 0:
P(x)
log 1
I
L
log Q(x)
+
20
+
o²
a.
As corollary of Lemma D.6 and Thm. 2.4 we have:
Lemma D.7. Let k 24 and let for each i [k:]
Wi log 1 (1-2)++
1
1,2 N(0,
62)
202
such that wa are independent. Then, the k-wise adaptive composition of ((Z) is (c, for
5(e) E +...
*]+-
(D.11)
D.3.1 Numerical Evaluation of (c. (e.d)-Bounds for Compositions
Figure shows the result of applying the FFT-based numerical method of Koskela et al. (202I) for evaluating the expression (D.1T). We compare the resulting approximate DP bounds to those obtained from the RDP bounds combined with standard composition results (Mironov) 2017).
Notice that we could also carry out tighter accounting of the approximative minima perturbation (Section 4 by adding the PLRVs of the Gaussian mechanism to the total PLRV, similarly as RDP parameters of the Gaussian mechanism are added to the RDP guarantees of the objective perturbation mechanism (Theorem 4.1). Adding the Gaussian PLRV to the total PLRV using convolutions is straightforward using the method of Koskela et al. (2011)
D.4 Auxiliary Lemma
For Theorem 3.1
we need the following auxiliary result.
Lemma D.8. Denote (x)=((x) the density function of the normal distribution ((,, o²) and let c 2 Let g(x) be non-negative differentiable non-decreasing function (c, 2o). Then, if az S 02.
[
fn,z(()) g(x) do S 1 fmaz(z) g(z) dx.
Proof. By integration by parts, we have
[ [2) g(x) dr = + (.) (c)) - -f (x) g((x) dr,
(D.12)
where &b (x)) denotes the edf of N N(H, o2). A simple calculation shows that for all æ e E,
i 1 n
I 1 (x).
do
o2
Thus, o (c) is non-increasing function of a for all e 2 μ. Furthermore, the first term in D.12 a non-decreasing function of since g(e) is nog-negetive and the second term is non-decreasing function of a, since g' (z)) is negatege for all z E [c, oo).
23

---

10
10
10-5
10
RDP k
RDP k k=
10-9
RDP k =
RDP k
Hockey-stick = 1
10
Hockey-stick 2
10-13
Hockey-stick k =
Hockey-stick k 4
10-15
0.2
0.4
0.6
0.8
1.0
1.2
1.4
Figure 3: Comparison of our RDP bound (implied (c, 8)-P bound) and numerical PLRV
bound (D.1I) for different numbers of compositions k; when o 8.0, 3 1.0 and À = 10.0.
E RDP guarantee of Algorithm
In what follows, we will present (corrected) privacy guarantee for Approximate Minima Perturbation (i.e., Algorithm M without gradient clipping). We will then demonstrate that the "clipped-gradio" function (0) only bounds the per-example gradient norm by C, but also preserves other properties (i.e., 3-smoothness and GLM structure) required for the privacy guarantees stated in Theorem 3.2
E.1 Privacy Guarantee for Approximate Minima Perturbation
The proof of the privacy guarantee for Approximate Minima Perturbation (Iyengar et al. 2019), ie. Algorithm without gradient clipping, falls prey to the same trap previous work objective perturbation. In particular, we see that there a mistake Lemma IV.1, with the assertion that "we get the statement of the lemma from the guarantees of the Gaussian mechanism." " The Gaussian mechanism is inapplicable in Lemma IV.1 for similar reasons as discussed in Section
The proof of Theorem E. corrects this issue. We state it in terms of RDP, but it can also extend to approximate DP and other DP variants.
Algorithm 2 Approximate Minima Perturbation (Iyengar et al. 2019)
Input: dataset Z; noise levels a, Gouti 9-smooth loss function E(-) with Lipschitz constant L; regularization strength A; gradient norm threshold T.
Sample (0 La). Lz)).
Let L (0; 2) = Σsez 2)0;2) +
Solve for Ø such that [ 2) T..
Output PP 0 + (1, 2 Ia).
Theorem E (RDP guarantees Approximate Minima Perturbation). Consider the Approximate Minima Perturbation algorithm which satisfies (a, e)-RDP RDDPeff for any with
L log
[cla-1)x]] +
S -logg
+
20
a
(o.
20 out
24

---

Proof. Sample b ~ IO) and let (0; (.) := ExEz ((0;2) + 2 211011 + 6T i.e., the perturbed and regularized objective function used by ObjPert.
Let 0 = arg min L (0: Z. b). From Chaudhuri et al. (2011) Kifer et al. 2012) we know that there bijection b(0P; Z) from the output 8² the noise vector b.
Consider a blackbox algorithm (A(2,b) 6) which returns such that [0; S т. Deffnee query
qZ, (Z) PP.
where 8 (Z) is an abbreviation for 0 (Z, ZZ).
We assume that y can recover from the input OP via the bijection b(0P; ; Z), and hence has access to the perturbed objective function L (0; 7, b).
Notice that since LP is X-strongly convex, by applying the Cauchy-Schwarz inequality and by Definition K.3
we see that for any 0,, 02.
VI - VL (2)))
02112 (VCP (L-)))))) T (0) 02) 2 A|10 02112
Algorithm 0A(Z, b) guarantees that its output 0 satisfies V (0)1l2 and by first-order condi- tions on the perturbed objective function, V (0F; Z, b) 0. It follows that for any dataset Z and OP.
- s
X
Since the algorithm 8^ (Z, guarantees that ||@ has global sensitivity bounded by 27/A since
AP| 1|2 S 7/X, then conditioning on OP, .((2,0)
27
(P) & [[(AA ( ( [[00
Now, the algorithm that first draws b then outputs (A + NN00, La is equivalent to
First run ObjPert that returns 8P. Release Å ==](Z,,)) NN0,
Return 0" + Å.
This adaptive composition of ObjPert with the Gaussian mechanism. The third step post processing.
The privacy guarantee stated in Theorem E. is thus achieved by combining the results Theorem 3.2 (RDP of ObjPert), Theorem B. (RDP of the Gaussian mechanism) with A,, = 2r and Lemma K.5 (adaptive composition for RDP mechanisms).
E.2 The "rripeedd Function
The RDP guarantees of objective perturbation (stated in Theorem 3.2 require several assumptions
the loss function E(;: Z). If we can demonstrate that these properties are satisfied by the "clipped- gradient" loss function (0; Z), then the rest of the proof of Theorem 4.1 (the privacy guarantee of Algorithm I will follow directly from that.
In particular, need to show:
1. That (0; retains the convex GLM structure of the original function E(O; z).
2. That (0; 2) satisfies Vlc =)I|2 < C' for any 0,
3. That lo (0;00 has the same f-smoothness parameter the original function 2).:2).
25

---

4. That even though (c( ) is not twice- siiceeddifereetiable everywhere, the privacy guarantees of objective perturbation (whose proof involves a Jacobian mapping) still hold.
We will begin by stating a result from Song et al. 2020). Theorem E.2 (Sogg et al. [020] Lemma 5.1). Let f R +
IR be any convex function and let C' E R+
be any positive value. For any non-zero x E Rd define
C
Ag Age of(w)
UL
u <
|
C
Vg E 0
Uh u g >
||0||2
Uf is non-empry, let un sup supUti otherwise ur oc. UH is non-empry, let uy inf Un: otherwise un = 0c. For any non-zero a E IRd, let
TElla (u uL), for (-oo,up) f(u:y);
fc(u)
for (uL, uH)
|1=lla (u wH), for (0)
Define un (0) = x0 Then the following holds.
1. fc is convex.
2. Let E(0: (x,z)) = f(uz(0); y) for any 0, 2 = (z, y). Then we have
C
(0;=) min (0)l2)
0ol(0:2)
The first two desired properties of (0; 2), i.c. GLM structure and gradient norm bound C, follow directly from the above theorem. Next, will prove the third property of 3-smoothness. Theorem E.3. For a data point Suppose that f(x" 0:y) satisfies 3-smoothness. Then the "clipped-gradient gradient" function fx defined in Lemma 5.1 of Song et al. (2020) also satisfies B-smoothness.
(x,y), consider a function such that E(O: f(x y).
Proof. Because f is 3-smooth by assumption, we know that f(u) satisfies 3-smoothness for all (uz, wx). When u (-o0, uz) or when u E (0), the function fc(u) is linear in u and thus is 0-smooth (hence satisfying 3-smoothness).
Lastly, the proof of objective perturbation (see, e.g., Theorem 9 of Chaudhuri al. 2011)) requires that the loss function be wwice-differentaable Even though (c ) is not twice-differentee everywhere, the privacy guarantees of objective perturbation still hold. To show this, we can invoke Corollary 13 of Chaudhuri et al. (201T). This corollary assumes the Huber loss; for brevity, we will leave it as an exercise for the reader to verify that the proof also carries through for the "clipped- gradient" loss.
Computational Guarantee of Algorithm
In this section, we provide computational guarantee to Algorithm 1 in terms of the number of gradient evaluations on individual loss functions to compute the approximate minimizer for achieving (up to constant) the information-theoredicn limit.
Let (0) := Σ, (0) + 110112 + bTe, i.e., the perturbed and regularized objective function used by ObjPert. Let d-* be the output returned by the blackbox algorithm (-) described in Section Note the deviation from the notation used in the previous section.
Iyengar et al. (2019) proposed a procedure that keeps checking the gradients in an iterative op- timization algorithm and stops when the gradient is smaller than т. This always ensures that [V
And using tools from the next section, it can be proven that it implies that 1 < <// was previously stated. But how many iterations it takes for this to happen for specific algorithms was not explicitly considered.
26

---

F.1 Tools from convex optimization
We will need few tools from convex optimization.
Firstl,, under our assumption that &, is 3-smooth, f is n5 X-smooth and A-strongly convex. Let L == n3 + À shorthand.
By T-smmothness (gradient Lipschitzness), and the optimality of 0", we have that for any 0
||]](0)]|= - V(000 - L|10 - 0-112.
(F.I)
By X-strong convexity, get
X 10 11
X
((0) |
(F.2)
21
By strong convexity also implies that
| [V)) 2|1 1
(F.3
which is the quantity used to establish the global sensitivity of q(D, 0*) talked about earlier.
and
F3 sandwich
||0 0* in between by
| S(O)
[VS(
< |0 0-
F.2
Computational bounds for Stopping small gradient
F.. and F.2 together provides bounds for |/V [()] using either objective function or argument convergence (in square 22.)
f(0))l - min {
2L x (f(0) - f", -0
1-
Standard convergence results are often parameterized in terms of either suboptimality S(0) - or argument ||0 0² In the following we instantiate specific convergence bounds for deriving computation guarantees.
Gradient Descent.
If we run gradient descent with learning rate 1/L. for T iterations from Go, then
||0 - 11 < (1 À T 11
which implies that
[ ) 9-
This happens deterministically (with no randomness, or failure probability).
One may ask why
not running fixed number of iterations and directly applying the bound to ||0y-6" || in order to control the lg sensitivity. That works fine, except that we have an unconstrained problem and 0" be anywhere, thus there might not be fixed parameter T provide a required bound for all input 0". We also do not know where 0* is during the actual execution of the algorithm and thus cannot compute |/0g 0*| directly.
The "gradicnt-norm check" as a stopping condition from Iyengar et al. (2019) is nice because always ensures DP for any 0" (at price of sometimes running for a bit longer).
To ensure [[V]( S 7, the number of iterations
7 log( 191100-0
2(L
log( L' 0-112
2nf
(n. + x) 0"
log(
log(1 2
222
722
Since each gradient computation requires n incremental gradient evaluation, under the regime that À independent of n, under the choice that 1/c independent to n from the standard calibration, the total number of is therefore O(n² logn) n) for achieving n- for any constant > 0.
27

---

The quadratic runtime is not ideal, but can be improved using accelerated gradient descent which gives convergence bound of
[(0)) - -r 2 0²12
This would imply a computational guarantee of O 15 log The overall computation bound depends on ||@"|| which is random (due to objective perturbation). The dependence on ||0*|| is only logarithmic though.
Finite Sum and SAG. The result can be further improved if we uses stochastic gradient methods. However, the sublinear convergence of the above conversion rules somewhat challenging.
standard SGD or its averaged version makes the application
By taking advantage of the finite sum structure of f(0) one can obtain faster convergence.
First of all, the finite sum structure says that f(0) = Σ;= fi(0). our case, we can split the regularization and linear perturbation the data points, i.e.,
6²
[((0) = R((0) + 2n
1111
Check that it satisfies 3 A/n smoothness.
There long list of methods that satisfy the faster convergence for finite sum problems, e.g., SAG, SVRG, SAGA, SARAH and so on (see, e.g., Nguyen et al. [022] for recent survey). Specifically. Stochastic Averaged Gradient (Schmidt et al. 2017) (and similarly others with slightly different parameters) satisfies
EE [[(0T) S min A
1
1)T
(
3n (f(0o) - -²) -L/100 00
16L'
8n
Therefore, by we have
E [IV < mint
1
))T
- ()
3n 2
2
X
(1(0))
4L|100 - 1²)
16T. 8n
Note that each iteration costs just one incremental gradient evaluation, so to ensure EE [[(r))] y the computational complexity on the order of
max(n, - log nL max(m((f(0))) - fr 110 0-1133
This is (n log n) runtime to any 7 n for a constant >> 0.
On the other hand, the main difference from the gradient descent result that we only get convergence in expectation. By Markov's inequality
IP [[V] > > (1 min{ 1) (3
(S(O)) (
-
41| 00((2) = 6,
72
which implies high probability convergence naturally.
Theorem F.1. Assume À 2 B. The algorithm that runs SAG and checks the stopping condition
[[ S ty after every n. iteration will terminate with probability at least 5 in less than
n13 A }log (m,
(n,3 ( max (100 - 0- (O(0))
88
incremental gradient evaluations, where a universal constant.
The lower bounds for convex and smooth losses in differentially private ERM well-known (Bassily al. 2014) and it known that among GLMs, 0 from ObjPert achieves the lower bound with appropriate choices of X, a. Notably, x d/e for achieving an (e, 6D-
How to set y to achieve information-theoreee limit?
E Σ (((0)) min Σ (,( MinimaaEExess<nmiinilikkkk
28

---

Let θ 8r + NO, 2x²11) be the final output.
By the nG Lipschitzness of Eg li with high probability over the Gaussian mechanism, have that
Alogd
E (,00) - Σ 5 -10 100- 0rl))
nG
where p is the zCDP parameter for the Gausssian mechanism chosen to match the large part of the ObjectivePetturaation 's RDP bound, which increases the overall RDP by ap.
+ Valogd/e)
Thus, it suffices to take y = Mirimoxtxxxessmmnittaaakka////a
To conclude, the above results imply that the computationally efficient objective perturbation achieves the optimal rate under the same RDP guarantee with an algorithm that terminates in O log n) time with high probability.
G
The GLM Bug
G.1 Discussion
Limiting our main results to generalized linear models might appear restrictive - but we argue that the GLM assumption is not specific our paper, but rather has been lurking the objective perturbation literature for some time now.
Let's first take look Section 3.3.2 of Chaudhuri et al. (201T): Lemma 10 requires that the matrix E have rank at most 2, but this is not necessarily true without assuming GLM structure. This is used to bound the determinant of the Jacobian, and corresponds the first term of our bound in Theorem 3.2]
It is a similar story for bounding the log ratio difference between the noise vector densities under neighboring datasets, corresponding to the second and third terms of our bound in Theorem 3.2 Let's also revisit this line from the proof of Lemma 17 of the Kifer et al. (2012) paper: "Note that independent of the noise vector." " This is not true without assuming GLM structure! (In their proof, I' is the difference between the noise vectors under neighboring distributions. From first-order conditions at the minimizer of the perturbed objective, we can see that Ve(OP) where 8 is function of the noise vector b.
In fact, to our knowledge, [yyenaar al. (2019) was the first work to acknowledge the GLM assumption on objective perturbation. But their privacy proof also fails to handle the dependence on the noise vector! Theorems 3.2 and 3.1] we have included a careful analysis including discussion on how the GLM assumption removes this dependence.
G.2 RDP bound for non-GLMs
In this section generalize the RDP bound for objective perturbation general class of smooth convex losses.
We first state the following bound from Theorem 6 Theorem G.I.
(10P, ((zz) log
II
(F)))
_ vE(0P;2)1B
12)
20
j=1
where μ1 djnt VUOP; F ExEI Aaueuit Uj according to the eigendecomposition (2((0;2) = Ei=1 duaur.
Theorem G.2 (RDP bound for GLMS.). Let [[VE(0; S and V2((0;2) BIa for all 0 E θ and E X' x y. Objective perturbation satisfies (a, RRDD for any > 1 with
-dlog (1-2)
3 +
log E Ezaxa [ (a)1) 1
=
X
20
29

---

where Z ~ Xa if = V X/ and X; ~ NO, 1) for all i E [d]
The above follows from Theorem 6 in (Redberg & Wang 2021 applied to the analysis of Theorem
Proof.
We find that
d S
log(1 -1) s -dlog (1- 8 x)
- log
Σ log(1 F {n))
Σ ==1
/=1
We now need bound
a log E (
Recall that ~ (N0, r2 Using the first-order condition VJ((P) = and the Cauchy-Schwar inequality, have
b7 < - L||b|22
So
1 V 1 a a-1
log Exnxa [ela-t)
log
H
Excess Empirical Risk of Algorithm
Our goal in this section is find a bound on the excess empirical risk:
E C(OP; 2) L(0";
Theorem H.1. Let 0 be the output of Algorithm 1 and 0 = arg min C(0) the minimizer of the loss
function (()) -E (.) Denote
||x|| the diameter of the set X. We have
(n.51xx1 1| A)do?
C(O"; 2)
C( 2) S nL +oue
+
10
2X²
Proof. Following the proof of Theorem 2 from Iyengar al. 2019) (itself adapted from Kifer et al. 2012
we write
c(O") - L(0*) ( c(0P)) + (c(O") -(0)))
By the X-strong convexity of L., for any 0, 0r we have
(VC' (v=)())v<<(07)) VCP((P)) T (o-
2110 0
By first-order conditions, VCP(0P)= 0. Applying the Cauchy- Sench--Schwaz... inequality along with our stopping criteria on the gradient norm, we then have
||0 1l s +IvE (0)12 T X
Let by ~N oum Ia). Because L is n n.I.-Liscchit continuous, we have
(C(0P) (()P)) < n0 - -0p1/2
= nL 0 + b2 0º ||
5 nL (10- - 0" 112 + ||b2
< nL [ + [|belle)
A
30

---

By Lemma K.10
E nL (x= + [|balle] S nL ( + tou
To bound the expectation of L(PP) ((0*), we can write
L(OP) _(0)) = (E(0P) - -((()) + (Lx(0P) - Ex(03)) + (Ex(03) - (x(0))) + (Ex(0") - 2())))
Observe that
[(0P) - Ex(0") - 1110011 S0,
-
and that by optimality
0
arg min (x(0)) we have
DER
(x)) - (x(00) SO.
Observe also that
X
-x(0))-((0 2/11 1010-12
So
C(0P) - C(0") S Cx(0P) Lx(03)
2 1001/2
By Taylor's Theorem, for some A' E [0P.0z] we can write
(x(0P)- (x()) = vLX(0X) (0P - 0x)²
+ =110P= 0P - 0 1x
1
2
= 2 10 - -x
(H.1)
The last equality is due to optimality conditions. We can then bound
1 110" cx S (0) 0x11
|16122
$ (n31122123 + A)
X2
where b ~ _N(0, o21). Then taking the expectation,
(n + +))do
E [[xx(PP) [[C) <
2X2
Altogether then have
E [cC0P: 2)0 L(0": nL (I onne Vd)
(n.3 |X (n A)do²
+ 1010-
2X2
The optimal choice of A would then be A X Section
db
The optimal choice of is discussed in
10
F
H.1 Generalized Linear Model
With some additional assumptions and restrictions, we can get a tighter bound on [Cx(PP)]
Lx (O)).
We will assume GLM structure on f(.), i.e. ((0:2) f(xT0 0:y). We will further assume boundedness:
S f(x"0:)) 0: v) S C for some universal constants c, C R.. Applying Taylor's Theorem (in an argument similar to Equation C.8), we can show that for some 6" [0P 08
g 0 = V² 1b.
31

---

Note that by the GLM assumption, the cigendecomposition of (3) can be written as X (
Then plugging in from Equation H. and using the boundedness assumption on the loss f.
- 11 - 0
[x(0P) - (x(0)) b" (F(()))))))()()))(((<)))
D" (X"A(0")* )x + (X*A(""X* -la) A(0')++AIA -b
c (x"x x Ala) -1a C (x +1a) c- (x'x+xxx
C x
Then in expectation,
Co² ((xTx+N1a)
E [0P] Lx(0%)
c²
I Distance to Optimality
Consider the mechanism M(Z) f(Z) + ((0,02Ta) for a function f 2 2 Rd with sensitivity
A5 = L. From Balle & Wang 2018). we know that for any neighboring datasets and Z', the
A A2.zz 22.21
Maximizing the Rényi divergence D, (Z) || MZ')) over all neighboring datasets Z ~ Z' shows that the RDP for the Gaussian mechanism can be written as
privacy loss random variable of this mechanism is distributed as V
2
(a)
1
log
f 1) N
L L2
)²)
20 o²)
a -
I
cla-1iN (o.
1 02
log
202 Q-11
Thus the main deviations between the RDP bound for objective perturbation and that of the Gaussian mechanism are 1) the leading term (a function of 33 and that vanishes as we increase the regulariza- tion) and 2) the moment- -onnentgenerating function of the half-normal (instead of normal) distribution.
Figure ! plots the Rényi divergence c(a) := (M || MM(())) for the Gaussian mechanism ("normal)) "), the objective perturbation mechanism ("ObjPert"), and the mechanism obtained by adding noise from the half-normal distribution ("half-normal"".
We consider several different regimes of interest by varying the noise scale and the regularization strength A. There are several takeaways to observe:
The difference between the RDP for the half-normal mechanism and the RDP for the objective perturbation mechanism is due entirely to the leading term of the bound given in Theorem 3.2 which vanishes as À increases (Figures 4b and 4cp. For smaller À there is a constant "start-up" gap between the half-normal and Objpert RDP curves (best displayed in Figure 4b) which disappears for larger a, where the moments the half-normal distribution overwhelm the contribution of the leading term of the objective perturbation RDP.
2. As increases (e.g. between Figures 4c and 4a and between Figures 4d and 4b). the half-normal curve - and therefore also the ObjPert eurve doesn't 't converge with the normal curve until larger
J Bridging the Gap between Objective Perturbation and DP-SGD
J.1 RDP of Objective Perturbation DP-SGD
DP-SGD (for example, n² rounds of sampled Gaussian mechanism with Poisson sampling probability
1/n) is known to experience phase transition in its RDP curve: for smaller a, amplification by
Moor formally, we that the normal" mechanism is .M(2) = f(2) + |,/(0, where f Z +
R is the function wish to release.
32

---

half-normal
normal
ObjPert
divergence
10
half-normal
normal
ObjPert
10
157
alpha
alpha
(a) 100, À = 10
(b) 10,
half-normal
half-normal
normal
normal
ObjPert
ObjPert
124
157
divergence
1.7
10
18
157
127
alpha
alpha
(c) 10, X 10
(d) 1,X=1
Figure 4
sampling is effective, and the RDP of a DP-SGD mechanism behaves like a Gaussian mechanism with E(a) O 2+2 then it leaps up at certain and begins converging E(aa) 0
that does not benefit from sampling at all (Wang et al. 2019 Bun et al. 2018). In contrast, the RDP curve for objective perturbation defined by Theorem 3.2 converges to the RDP curve of the Gaussian mechanism c(a) = O 2 after certain point. Whereas DP-SGD offers stronger privacy parameters for small a, objective perturbation is stronger for large a, which offers stronger privacy Proposition 10).
protection for lower-probability events (see, e.g., Mironov 2017
CM
102
GM
OkpPert
ObjPert
107
10-1
10-1
10-2
10-3
10:
101
102
16a
10'
16
10"
107
10"
107
16"
10'
16*
(a) JlkiPPrtt
OTox
100:
(b) ObbjPett
Oax
40:p
0.1, (POP. s0D
0.5, dee 300
Figure 5: RDP curves of objective perturbation and DP-SGD.
33

---

J.2 A Spectrum of DP Learning Algorithms
We can also connect Algorithm to differentially private heegon-tee-rgllrizdd-eeedde (DP-FTRL) (Kairouz et al., (021). which uses a tree-based aggregation algorithm to privately release the gradients of the loss function as a prefix sum. This approach provides a competitive privacy/utility tradeoff without relying on privacy amplification or shuffling, which is often not possible in distributed settings. DP-FTRI. differs from DP-SGD by adding correlated rather than independent noise each iteration; Algorithm in contrast, differs from both by adding identical noise at each iteration.
K
Technical Lemmas & Definitions
K.1
Convex Optimization
We will give a short review of relevant concepts from convex optimization.
Definition K.1 (lz-Lipschitz continuity). A function f θ + is L-Lipschitz w.r.t. the fn-morm
over θ S R if for all 8, 02 E O, the following holds: [f(0)) - f(02) - L 82112.
Definition K.2 (8-smoothness). A differentiable function f θ - IR is 3-smooth over θ S B its gradient f is 3-Lipschitz, i.e. [V, vf()2) S B||0] 02112 for all 61, 02 e.
Definition K.3 (Strong convexity). A differentiable function f θ + IR is X-strongly convex over C Rd if for all 01, 0, E @: ((1)) 2 f(22) + VS())) (01 - 02) + 000 02 3
K.2 Differential Privacy
Definition K.4 (Privacy loss random variable). Let Pr [M(Z) 0) denote the probability density of the random variable M(2) at output 0. For a fixed pair neighboring datasets and Z', the privacy loss random variable (PLRV) of mechanism M 2 θ is defined as
Pr (2
2z (0) log Pr (M 0
for the random variable 0 ~ MMZ).
Lemma K.5 (Adaptive composition (RDP) (Mironov 2017 Let Mi 2 - R1 be (a, (1,61)-RDD)) and
M2 R1 x Z + R2 be (a,62)-RD)) R2)- Then the mechanism M = (m1, m2). where my ~ (7) and m2 MM(Z,mm). satisfies (ax, 61 R2)-RP
Lemma K.6 (Change of coordinates). Consider the map g X y between X' RRd and y Rd
that transforms = g(z). Then
dy dr
dy det
dr.
where det Oy dx
is the absolute value of the determinant of the Jacobian of the map
Ta Jas:
Dy /0xa
Qy
0ya/on
Sya /ama
Lemma K.7 (Change of variables for probability density functions.). Let g be a strictly monotonic function. Then for g(x),
Oy dr
px px(x) = det
py (2).
Lemma K.8. Let A be an invertible matrix. Then det A Lemma K.9 (Maximum Rayleigh quotient). For any symmetric matrix A dxd
A'
T Av
Amari
VER
T u
where Amar is the largest eigenvalue of A.
34

---

Lemma K.10 (Bound on the expected norm of multivariate Gaussian with mean 0.). Let NN o² Ia).. Then
E [[ol]]svvvl
Lemma K.11 (Gaussian MGF). Let X oN) μ B Ryo. The moment generating function of order is then MGF x (1) 2 So for any t Ryo and 01 < oz.
MGFx.00 (0) S (G)x,
where X1 ~N(H, of) and X2 ~ (N,,
Definition K.12 (Holder's Inequality) Let X, X,Y be random variables satisfying E [[|]] < oc, [ < co for and 1 =1 Then
E | S EEIP =
Definition K.13 (Rényi Divergence). Let P.Q be distributions with probability density functions P()). The Rényi divergence of order > between P and Q is given by
(P()) ]
P(x)
Da log E
a- log BexP
Q(1)
Lemma K.14 (MGF incquality for identical distributions). Let NO, o²).
Then
Euy [ellaallaa] s Ez (e(57)
Proof. Observe that for any b E IR, it holds that 2ab a² + 12. Applying this along with the Cauchy-Schwarz inequality,
Ex.y [1lz1
i eiv?
S
(eiv))
S Egg
By
Eg
35


Reviews:
[{"review_id": "9xQfHt1DoL", "reviewer": "Reviewer_MKLH", "summary": "The paper considers a practical perspective on privacy for unconstrained convex generalized linear problems.  While DP-SGD has been the workhorse for differential privacy in deep learning and prediction/classification problems, the authors suggest that objective perturbation might be more suitable for simpler models.  (Also to provide a more 'honest' privacy mechanism.)\nThe authors provide privacy bounds for objective perturbation based on Renyi DP.  Using the hockey-stick divergence, the authors provide a tighter $(\\epsilon,\\delta)$-DP bound. The authors also introduce computational tools to avoid the necessity of bounded gradient.\n\nThe paper is clear and enjoyable to read.  The authors perform a good analysis of DP in linear settings, and provide usable practical tools.  While the numerical results do not demonstrate a significant improvement with the proposed algorithm, the importance to using objective perturbation or looking beyond DP-SGD in practice is a valuable analysis.", "questions": "A gradient clipping parameter is used in the proposed algorithm - authors should explain why this does not lead a more 'dishonest' privacy mechanism.\n\nThe paragraph that explains the tuning of privacy parameter of objective perturbation (starting line 287, page 9) is not very clear.  How is it that the tuning is data-independent?\n\nThe results on the Adult dataset show that the proposed algorithm performs close to dishonest DP-SGD, but actually the accuracy values of all three methods are quite close.  For the synthetic dataset on the other hand, the algorithm doesn't show an improved performance, even over the honest method. Why is that?  Experiments on more datasets would be necessary to support the importance of objective perturbation.", "limitations": "The authors have not addressed limitations.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper is technically sound - the authors carry out a good analysis and propose an objective perturbation method using various frameworks such Renyi DP and the hockey-stick divergence.\nThe paper makes a meaningful contribution to the practical applicability of DP.", "weaknesses": "A gradient clipping parameter is used in the proposed algorithm - authors should explain why this does not lead a more 'dishonest' privacy mechanism.\n\nThe paragraph that explains the tuning of privacy parameter of objective perturbation (starting line 287, page 9) is not very clear.  How is it that the tuning is data-independent?\n\nThe results on the Adult dataset show that the proposed algorithm performs close to dishonest DP-SGD, but actually the accuracy values of all three methods are quite close.  For the synthetic dataset on the other hand, the algorithm doesn't show an improved performance, even over the honest method. Why is that?  Experiments on more datasets would be necessary to support the importance of objective perturbation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> A gradient clipping parameter is used in the proposed algorithm - authors should explain why this does not lead a more 'dishonest' privacy mechanism.\n\nThe clipping parameter $C$  is indeed a parameter that affects the privacy guarantees, and tuning it would have an additional privacy cost. However, for logistic regression (with a bias term), we have a natural choice $C = \\\\sqrt{2}$  for the clipping constant. Notice also that we are free to tune the rest of the hyperparameters of the optimizer (learning rate, batch size) \"for free”.\n\nWe wanted to fix $C$ across both algorithms so that we could isolate the effect of tuning optimization-related parameters (batch size, number of iterations) which don’t affect the privacy guarantee of objective perturbation / Algorithm 1, but do affect the privacy guarantee of DP-SGD. The clipping parameter $C$ would affect both algorithm’s privacy guarantees!\n\n> The paragraph that explains the tuning of privacy parameter of objective perturbation (starting line 287, page 9) is not very clear. How is it that the tuning is data-independent?\n\nLikely it will be clearer to state this as pseudo-code in the appendix, rather than trying to explain in words! What we meant is that we can choose the noise scale $\\\\sigma$ and the regularization strength $\\\\lambda$ without looking at the data.\n\nThe privacy guarantees of objective perturbation depend on $\\\\lambda$ and $\\\\sigma$. We don’t want to add too much bias (large $\\\\lambda$) because it will hurt utility, but if we set $\\\\lambda$ too small then there is a risk that our $\\\\sigma$ would need to become unreasonably large (and also hurt utility).\n\nHow do we quantify when $\\\\sigma$ is “too large”? We use the Gaussian mechanism as a reference point: the noise scale for objective perturbation shouldn’t be too much larger than the noise scale for the Gaussian mechanism. Let’s say that the Gaussian mechanism with noise scale $\\\\sigma_G$ satisfies ($\\\\epsilon, \\\\delta$)-DP, then we want our $\\sigma$ for ($\\\\epsilon, \\\\delta$)-DP objective perturbation to satisfy $\\\\sigma \\\\leq c \\sigma_G$ for some small constant factor $c$.\n\nSo our strategy is to find the smallest possible $\\\\lambda$ such that $\\\\sigma$ isn’t \"too large”. We can accomplish this using fixed parameters (e.g., $\\\\epsilon, \\\\delta, \\\\sigma_G$) that are independent of the data!\n\n> The results on the Adult dataset show that the proposed algorithm performs close to dishonest DP-SGD, but actually the accuracy values of all three methods are quite close. For the synthetic dataset on the other hand, the algorithm doesn't show an improved performance, even over the honest method. Why is that?\n\nWe agree that we need to scale up the experiments! Some issues there are\n\n1. *Poor choice of datasets*. In hindsight, the synthetic and Adult datasets are too simple to properly showcase the benefits of Algorithm 1 (and the disadvantages of DP-SGD). In this case tuning likely doesn’t matter too much as an extensive search isn’t necessary to find a good set of hyperparameters.\n2. *Searching the wrong regimes*. Our choice of $\\\\epsilon$ included some redundancies: Going from $\\\\epsilon = 1$ to $\\\\epsilon = 8$ didn’t make much difference in accuracy neither for DP-SGD nor Algorithm 1. Likely this is because the datasets were already “easy” and so more privacy budget after $\\\\epsilon = 1$ gave diminishing returns.  On the other hand, for both the synthetic and Adult datasets we saw the largest improvements for $\\\\epsilon= 0.1$ — our response to Reviewer udpp includes our intuition on why this is the case. So we plan to include more results on the small $\\\\epsilon$ regime. "}, {"review_id": "DlEDsgT5QZ", "reviewer": "Reviewer_udpp", "summary": "This paper derives new privacy analysis of the objective perturbation mechanism. Novel bounds are given for Rényi differential privacy and approximate differential privacy, that are tighter than existing bounds. A practical variant of objective perturbation (where the problem does not have to be solved exactly) is proposed, and evaluated numerically.\n", "questions": "1. Theorem 2.8 is stated for a fixed $\\epsilon$, while other theorems fix $\\sigma$ and express the privacy parameters ($\\alpha, \\epsilon$ or $\\delta$) as a function of $\\sigma$. What is the reason? It seems that unifying this would significantly help the discussion (e.g. by stating Theorem 2.8 for fixed value of $\\sigma$). Conversely, is it possible to give a closed-form for $\\sigma$ in Theorems 3.1 and 3.2?\n2. In Figure 1, it seems that the gap between Kifer's results and RDP/HS for ObjPert reduces as $\\sigma$ increases. Is it the case, and is it coherent with the theory? Are there some regimes where both analyses give equivalent results?\n3. Why is the comparison with DP-SGD with \"honest\"-tuning so important? It seems that empirical results are competitive even with the tuned DP-SGD, which hints that tuning is not so fundamental in the comparison between the two mechanisms.\n4. It is a bit weird to talk about \"DP-SGD with ADAM optimizer\" (e.g., this variant is not mentioned in [1]): what does it means? Why not compare with the usual DP-SGD?\n5. In general, SGD is known not to be the best optimizer for GLMs. Another approach, closely related to Objective Perturbation, that could be better, is *Output* Perturbation. Why not compare with Output Perturbation? Can the ideas in this paper be used to improve Output Perturbation? \n\n[1] Private empirical risk minimization: Efficient algorithms and tight error bounds, Raef Bassily et al., 2014.\n", "limitations": "The paper is mostly limited to GLMs, which is clearly stated by the authors. The baselines considered for comparing computational cost are a bit weak (e.g., DP-SGD from [1] does not assume smoothness), which reduces the strength of the argument on the computational cost.\n", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 4, "strengths": "1. The RDP analysis of objective perturbation is an interesting and original contribution, and the proposed analyses improve over existing results on the privacy of objective perturbation.\n2. A practical variant of the method is proposed, with a convergence criterion that allows tuning the hyperparameter of the underlying optimization sub-routine for free (in terms of privacy).\n3. Empirical results are quite convincing, matching the utility of DP-SGD without requiring a heavy tuning procedure.\n", "weaknesses": "1. The proposed method is compared with DP-SGD for non-smooth functions [1], which is a different setting. In the smooth setting, DP-SGD and its variants converge faster, which makes the argument that the proposed Objective Perturbation method is more computationally efficient vacuous. (In general, I don't find the discussion on computational cost is so useful, and it could be mostly removed to incorporate more discussion on other results.)\n2. Some literature on differentially private generalized models is missing. In particular, [2] could be a good baseline and is not mentioned in the paper.\n3. No closed-form on the value of $\\sigma$ required to obtain a given RDP or DP guarantee is provided. This makes the comparison with existing results a bit difficult.\n\nIn terms of structure, the paper is not too convincing: a large part of the contributions is deferred to the appendix, and references to appendix in the main text are vague. In general, results are presented without much discussions. In particular, Theorem 3.1 (central result of the paper) is presented without details on the comparison with Theorem 2.8; and Figure 1 is not discussed (and lacks a bit of details for proper understanding). It also seems that a title is missing between lines 184 and 185\n\nSome statements are also not very clear: the regularization $r(\\theta)$ disappears in the definition of $J^P$ (page 4); $\\hat \\theta$ in Corollary 3.4 seems to be the one from Example 3.3 but it is not stated; the problem considered in Figure 1 is not stated.\n\n[1] Private empirical risk minimization: Efficient algorithms and tight error bounds, Raef Bassily et al., 2014.\n[2] Differentially Private Generalized Linear Models Revisited, Raman Arora et al., 2022.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> The proposed method is compared with DP-SGD for non-smooth functions [1], which is a different setting. In the smooth setting, DP-SGD and its variants converge faster, which makes the argument that the proposed Objective Perturbation method is more computationally efficient vacuous. (In general, I don't find the discussion on computational cost is so useful, and it could be mostly removed to incorporate more discussion on other results.)\n\nWe are aware of some literature showing that DP-SGD runs in linear time if the objective is smooth, e.g.:\n\nWang, Di, Minwei Ye, and Jinhui Xu. \"Differentially private empirical risk minimization revisited: Faster and more general.\" Advances in Neural Information Processing Systems 30 (2017).\n\nThis paper presents a DP-version of SVRG, with a claim that DP-SVRG achieves nearly linear time complexity in getting to the information-theoretic limit. But the main result missed the nonlinear regime of amplification by sampling, i.e., when $\\\\epsilon$ is large, you do not get an amplification. For that reason, the linear-time complexity of DP-SVRG only applies to cases when $\\\\epsilon$ is as small as $1/n$. (This was not stated in their Theorem 4.3 and 4.4, but looking at the proof (Page 13 of [WYX'17]) shows that an additional condition of small $\\\\epsilon$ is needed.)  \n\nThe above confusion might have been popularized by the (very nice) paper by Kulkarni, Lee, and Liu (2021) who focused on the non-smooth case, but *incorrectly* cited [WYX'17] for obtaining a nearly linear time for DP-ERM with smooth/convex losses. \n\nThere is also this paper:\n\nFeldman et al. Private stochastic convex optimization: optimal rates in linear time. STOC 2020.\n\nBut they study only the DP-SCO setting which is not comparable to our DP-ERM setting.\n\nPlease let us know if we’ve missed any literature! We are ready to argue that smoothness doesn't actually help DP-SGD to get faster than O(n^2) :)\n\n> Some literature on differentially private generalized models is missing. In particular, [2] could be a good baseline and is not mentioned in the paper.\n\nThanks for this reference! It does indeed look very useful and relevant.\n\n> Theorem 2.8 is stated for a fixed $\\\\epsilon$, while other theorems fix $\\\\sigma$ and express the privacy parameters ($\\\\alpha$, $\\\\epsilon$ or $\\\\delta$) as a function of $\\\\sigma$. What is the reason? It seems that unifying this would significantly help the discussion (e.g. by stating Theorem 2.8 for fixed value of $\\\\sigma$). Conversely, is it possible to give a closed-form for $\\\\sigma$ in Theorems 3.1 and 3.2?\n\nStating $\\\\epsilon$ as a function $\\\\sigma$ in Thm. 2.8 is straightforward (it's already in the proof from Appendix C.1 of Kifer et al., 2012 ), in our notation, the expression is $\\epsilon = \\frac{L^2}{\\sigma^2} + \\frac{L}{\\sigma}\\sqrt{8\\log (2/\\delta)}$. We can state the bound for $\\\\epsilon$ instead as you suggested.\nComparing different bounds analytically is quite difficult, however we remark that the techniques behind Thm. 2.8, 3.1 and 3.2 are quite different (analytical bounds, RDP bounds, and $(\\\\epsilon,\\\\delta)$-bounds directly using the hockey-stick divergence, respectively) and this shows up in the numerically evaluated bounds of Figure 1 as well.\n\n> In Figure 1, it seems that the gap between Kifer's results and RDP/HS for ObjPert reduces as $\\\\sigma$\n increases. Is it the case, and is it coherent with the theory? Are there some regimes where both analyses give equivalent results?\n\nThis is a great question --- we likely can't give a really satisfying answer without digging into the proof details in Appendix C of the Kifer et al (2012) paper.  Our original inspiration for pursuing an RDP/HS analysis for ObjPert is that we noticed that some of the inequalities in the Kifer et al proofs looked pretty loose; it's possible that they are tighter in certain regimes.\n\n> It is a bit weird to talk about \"DP-SGD with ADAM optimizer\" (e.g., this variant is not mentioned in [1]): what does it means? Why not compare with the usual DP-SGD?\n\nWe wanted to emphasize that our choice of optimizer (Adam) was a hyperparameter. It is the usual DP-SGD mechanism for releasing stochastic gradient, then passed into the torch.optim.Adam instead of  torch.optim.SGD. This is the version implemented in Opacus.\n\n> Why is the comparison with DP-SGD with \"honest\"-tuning so important? It seems that empirical results are competitive even with the tuned DP-SGD, which hints that tuning is not so fundamental in the comparison between the two mechanisms.\n\nIn our experiments, tuning seems to be more important in the small $\\\\epsilon$ regime, where we speculate that DP-SGD has no privacy budget to spare. (Imagine the effect of taking \\\\$100 from a grad student vs a CEO. DP-SGD with small $\\\\epsilon$ is the grad student and DP-SGD with large $\\\\epsilon$ is the CEO.) We plan to look more closely into this small $\\\\epsilon$ regime.\n\n> In general, SGD is known not to be the best optimizer for GLMs. Another approach, closely related to Objective Perturbation, that could be better, is Output Perturbation. Why not compare with Output Perturbation? Can the ideas in this paper be used to improve Output Perturbation?\n\nIf we had to guess: our analysis techniques would likely make no difference, since the bound for output perturbation (at least, the Gaussian mechanism) is already tight. But the privacy analysis of output perturbation is based on the maximum gradient norm, so our gradient clipping technique could likely apply there. Thanks for this interesting line of thought!"}, {"review_id": "DL8QTgRAdw", "reviewer": "Reviewer_RDzn", "summary": "The paper revisits objective perturbation as a viable alternative to DP-SGD with tighter analysis and illustrating it competitiveness on a few problems.", "questions": "Please see \"weaknesses\" section", "limitations": "Yes", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper explores the interesting direction of fairly comparing objective perturbation and DP-SGD specifically. The paper has multiple strengths\n\n- Paper presents a novel analysis of objective perturbation using RDP, and extending it to an even tighter bound\n- It also empirically verifies that its competitive against DP-SGD, especially on lower epsilons, while having the advantage of \"free\" hyperparam tuning\n- Introduces an algorithm to expand the applicability of objective perturbation to a broad range of losses", "weaknesses": "Here are a few weaknesses:\n\n- Empirical evaluation of this method can be improved, I had following questions in this regard\n  - DP-SGD is known to work best with large batch sizes, I would suggest increasing batch size for for the baselines -- even better is to have a plot with varying batch sizes. Similar argument can made for number of iterations as well. \n  - Even though there is a good reason to use L-BFGS with Alg 1, including an ablation when using Adam with Alg 1 would be useful as a comparison.\n-  While not a major one for publication but a still a weakness: the function class that analysis applies to for objective perturbation is limited compared to DP-SGD.\n- Another weakness is Alg 1's either matches or performs worse against DP-SGD on epsilons > 0.1", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> DP-SGD is known to work best with large batch sizes, I would suggest increasing batch size for for the baselines -- even better is to have a plot with varying batch sizes. Similar argument can made for number of iterations as well.\n\nThe batch size and the number of iterations were simply reasonable sounding first choices (see e.g. the experiments by Abadi et al., 2016, Deep learning with differential privacy). If we tune the batch size and number of iterations in addition to the learning rate as well, it will likely worsen the privacy utility tradeoff for honestly tuned DP-SGD, as we need to sample much more hyperparameters (from a product grid, e.g.) and the privacy cost of the hyperparameter tuning algorithm by Steinke and Papernot (2022) increases.\n\n> Even though there is a good reason to use L-BFGS with Alg 1, including an ablation when using Adam with Alg 1 would be useful as a comparison.\n\nThanks for the suggestion! We don't *think* that using Adam instead of L-BFGS in Alg. 1 would affect the utility of the final result, as we are simply minimizing the (convex) perturbed loss function until the stopping criterion (determined by the tolerance parameter $\\tau$) is fulfilled. But it would be good to take a closer look!\n\n> Another weakness is Alg 1's either matches or performs worse against DP-SGD on epsilons > 0.1\n\nThis is likely due to the fact that the model accuracies in these examples do not really improve when going beyond $\\epsilon=1.0$ (notice that Alg. 1 is never significantly worse). We agree that improvements on DP-SGD seem to be biggest for small $\\epsilon$'s in these examples. We will add results for small $\\epsilon$-values."}, {"review_id": "jd6RXhCfN9", "reviewer": "Reviewer_eK3K", "summary": "The paper revisited a differentially private learning algorithm: objective perturbation. The authors gave an RDP analysis of objective perturbation and extended AMP to losses with unbounded gradients using clipped loss function.", "questions": "Please add more experiments if possible", "limitations": "Yes", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The main contributions of the paper are (1) RDP and HK analysis of objective perturbation; (2) an improved version of AMP which extends to losses with unbounded gradients.\n\nI really enjoyed reading the manuscript. The authors did a fantastic job telling the story why objective perturbation should regain attention from the community.\n\nThe analysis of HK and RDP bound, despite not challenging, are good contribution. Another contribution is that the authors found an unacknowledged subtlety in the analysis of objective perturbation and pointed out GLM assumption solved the issue.\n\nThe extended AMP is a direct combination of clipped loss function and AMP. Again, not too technically challenging, but solid contribution.\n\nAnother contribution is that the authors showed that objective perturbation is computationally more efficient than DP-SGD. ", "weaknesses": "1. Compared to the pretty theory and story-telling, the evaluation is somewhat weak. First, objective perturbation does not consistently show better performance than honest DP-SGD. Second, even in cases where objective perturbation wins, the winning is marginal. Third, objective perturbation is only evaluated on 2 toy datasets. More realistic datasets are preferred.\n2. The 3rd bullet point in the contribution list emphasized that there is neglected subtlety in the analysis of objective perturbation which might lead to dimensional dependence of PLRV and the paper fixed the issue without touching the topic in detail except a pointer to appendix in remark 3.5. I think this contribution deserves more space in the main text. \n3. typo: line 306 \"boudning\" -> \"bounding\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nThank you for the review, we are happy to hear you enjoyed reading the paper! \n\n> The 3rd bullet point in the contribution list emphasized that there is neglected subtlety in the analysis of objective perturbation which might lead to dimensional dependence of PLRV and the paper fixed the issue without touching the topic in detail except a pointer to appendix in remark 3.5. I think this contribution deserves more space in the main text.\n\nThank you for the feedback, we will give more space for this in the main text.\n\nOn the same subject, we also didn’t emphasize that Iyenger et al’s 2019 analysis inherited the mistake from the classical analysis. One of our other contributions was to provide a new privacy analysis of AMP that fixes this. We stated this only informally in Appendix H.2; the next revision of the paper will formalize this argument!\n\n>  the evaluation is somewhat weak.. objective perturbation does not consistently show better performance than honest DP-SGD... even in cases where objective perturbation wins, the winning is marginal... More realistic datasets are preferred...\n\nThe experimental evaluation is definitely a weakness! We are working on scaling up the experiments and the complexity of the datasets. In the meantime, we also plan to look more closely into the small $\\epsilon$ setting (e.g., $\\epsilon = 0.05, 0.01$) where we suspect that the effect of hyperparameter tuning is more pronounced.\n\n> typo: line 306 \"boudning\" -> \"bounding\"\n\nThanks, we will fix this."}, {"review_id": "83ipXkA0Us", "reviewer": "Reviewer_NU3P", "summary": "This paper presents a new privacy analysis for the objective perturbation method for learning differentially private linear models. The new analysis makes use of gradient clipping (similar to DP-SGD) and is shown to have a competitive performance with respect to DP-SGD, while exhibiting better behavior for hyperparameter tuning.  ", "questions": "The authors compared their results for the objective perturbation mechanism with the rather old results for DP-SGD (namely, Bassily et al., 2014). For the convex loss functions, there many more recent privacy analyses for DP-SGD in the literature. For instance, it would be important and insightful if the authors could compare their results with Altschuler and Talwar's result \"Privacy of Noisy Stochastic Gradient Descent: More Iterations without More Privacy Loss\". \n", "limitations": "Yes", "rating": 3, "confidence": 4, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "The problem that this paper sets out to address is very interesting and can potentially have (minor) practical implications. ", "weaknesses": "My main issue with this paper is the presentation: \nMany vague sentences, several terms are not properly defined, confusing notation, and several careless mistakes in mathematical definitions. \nI'll be more specific in the following:\n1. The first item in the contribution (line 47) states that the PLRV of the objective perturbation mechanism is \"almost\" Gaussian. The authors failed to elaborate on this point in the draft and it seems to be left to the reader's imagination. The second item (line 53): \"We establish even tighter ($\\epsilon, \\delta$)-DP\". Tighter compared to what. The fourth item (line 64) discusses \"weakly\" differentiable loss functions. What is a weakly differentiable function? \n2. The following terms were not defined: $\\epsilon(\\alpha)$, $L(\\theta, Z)$ (line 219),  \"privacy profile\" (i.e., Lemma  2.6 is very hard to understand without a precise definition of $\\delta(\\epsilon)$),  $\\tilde\\theta^P_T$ (in line 229), the set $\\mathcal X$ in Theorem 4.2, and also $\\hat \\theta^P(Z)$ and $\\hat \\theta^P(Z')$ in Corollary 3.4 (I suspect the authors meant $\\hat \\theta^P(X)$ and $\\hat \\theta^P(X')$ as defined in line 190). Finally, the identity $\\ell(\\theta, z) = \\ell(x^T\\theta, y)$ in line 141 is very confusing; again I think the authors meant $\\ell(\\theta, z) = f(x^T\\theta, y)$ for some functions $f$. \n 3. There are three ways a dataset is referred to in this paper: $Z\\in \\mathcal Z^n$, $Z\\in \\mathcal Z$, and $z\\in Z^n$!! The notation $\\mathbb E [e^{|\\mathcal N (0, \\sigma^2)|}]$ is not a proper mathematical notation! The authors should have clarified that $\\mathcal M(Z)$ denotes both a random variable (i.e., mechanism's output) and its distribution.\n4. The definition of R\\'enyi divergence in line 108 is WRONG (and the mistake was repeated more than 3 times throughout!!)  Another example: It is stated in line 225 that $\\tilde \\theta^P = \\theta^P + (\\tilde \\theta - \\theta^P)$, which implies $\\tilde \\theta^P = \\tilde \\theta$ (which is clearly wrong).\n\nThe second weakness is Algorithm 1: First of all, $\\gamma$ is one of the inputs but hasn't been used! Moreover, the definition of $\\tilde \\theta$ is cryptic. This is  the definition:  Solve for $\\tilde \\theta$  such that $|| \\nabla \\mathcal L_C^P(\\tilde \\theta; Z)||_2\\leq \\tau$. For a given $\\tau$, we might have (infinitely many) different such $\\tilde \\theta$.  \n\nThe third weakness of this work is the presentation of the main results. It is rather difficult to see the significance of the results compared to the existing privacy analyses of the objective perturbation method. The authors failed to put their results in the context of the known results, so the readers can appreciate them. In particular, it is particularly unclear how Algorithm 1 extends Iyengar et al.'s AMP. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your feedback! The notation went through a major overhaul during this paper’s lifespan and we obviously didn’t check for consistency as thoroughly as we should have. Our intention was to make this a fun read and we’re sorry to hear it missed the mark for you.\n\n>The first item in the contribution (line 47) states that the PLRV of the objective perturbation mechanism is \"almost\" Gaussian. The authors failed to elaborate on this point in the draft.\n\nThis PLRV is almost Gaussian as it is a shifted half-normal distribution. This is shown explicitly in the appendix (see for example the statement of Lemma E.6). It is also reflected in Thm. 3.1: the log moments are the log moments of a shifted half-normal distribution.\n\n“Almost Gaussian” is also demonstrated in Appendix I, “Distance to Optimality”, which plots the RDP bounds of objective perturbation against those of the Gaussian mechanism and shows that these differences vanish in certain regimes (e.g., large $\\alpha$).\n\nWe will make sure to state this more clearly in the main paper.\n\n> The second item (line 53): \"We establish even tighter $(\\epsilon,\\delta)$-DP\". Tighter compared to what. \n\nTighter compared to the RDP bound (mentioned in the previous point). We will re-write this to make it clearer.\n\n> The fourth item (line 64) discusses \"weakly\" differentiable loss functions. What is a weakly differentiable function?\n\nIt is a function that has a derivative in the sense of distributions. Weakly differentiable functions are differentiable except for sets of measure zero (the sign function is an example).\n\nBut you have a point that the “weakly differentiable” claim might not be appropriate in the introduction, given that our theoretical results don't require it directly. What we wanted to communicate is that Algorithm 1 applies to a broad class of loss functions which only need to satisfy $\\beta$-smoothness (including functions which are weakly differentiable). \n\n> The notation $\\mathbb{E}...$ is not a proper mathematical notation!\n\nWe will change this so that in the bound of Thm 4.1, for example, the last term is given as\n$$\n \\dfrac{1}{\\alpha - 1} \\log \\mathbb{E} \\left[e^{(\\alpha - 1)\\left| X \\right|} \\right],\n \\quad X \\sim \\mathcal{N}\\left(0, \\dfrac{L^2}{\\sigma^2}\\right).\n$$\n\n> The second weakness is Algorithm 1: First of all, $\\gamma$ is one of the inputs but hasn't been used!\n\nHere is again simply a typo: gradient norm threshold $\\gamma$ should be $\\tau$, we will fix this.\n\n> The third weakness of this work is the presentation of the main results.... In particular, it is particularly unclear how Algorithm 1 extends Iyengar et al.'s AMP.\n\nAs we explain in the appendix in Section F, the proof of Kifer et al. (2012) made a certain mistake about independence of random variables, and collapsing $d$-dim Gaussian to a $1$-dim Gaussian. Iyengar et al.'s analysis inherits this same mistake. It is one of our main contributions to provide a correct analysis and also give the AMP version of it.\n\n> Moreover, the definition of $\\tilde{\\theta}$ is cryptic... For a given $\\tau$, we might have (infinitely many) different such $\\tilde{\\theta}$.\n\nThe formulation here is vague by intention... This was also the case in Iyenger et al's AMP paper. Any $\\tilde{\\theta}$ that satisfies the condition (gradient norm less than $\\tau$) will have the rigorous privacy guarantees given by Thm. 4.1. The (blackbox) procedure for finding such $\\tilde{\\theta}$ is allowed to involve arbitrary data access and tuning.\n\n> The definition of R'enyi divergence in line 108 is WRONG \n\nThank you for pointing this out, the extra $\\log$ is simply a typo and will be fixed.\n\n> It is stated in line 225 that $\\tilde{\\theta}^P = \\theta^P + (\\tilde{\\theta} - \\theta^P)$, which implies $\\tilde{\\theta}^P = \\tilde{\\theta}$ (which is clearly wrong).\n\nThis is again simply a typo, $\\tilde{\\theta}$ should be written $\\tilde{\\theta}^P$.\n\n> The authors compared their results for the objective perturbation mechanism with the rather old results for DP-SGD (namely, Bassily et al., 2014)...it would be important and insightful if the authors could compare their results with Altschuler and Talwar's result \"Privacy of Noisy Stochastic Gradient Descent: More Iterations without More Privacy Loss\".\n\nFirst of all, we do not compare to the result of Bassily et al. (2014). As we state on line 280--281, for privacy analysis of DP-SGD we use the analytical moments accountant (Wang et al., 2019) with Poisson sampling (Zhu \\& Wang, 2019; Mironov et al., 2019).\n\nThe motivation for comparing against DP-SGD is the following. As we write on lines 36--38, empirical evaluations of (Yu et al., 2019; McKenna et al., 2021) suggest that DP-SGD often achieves better utility in practice than objective perturbation and Iyengar et al. (2019) report the opposite. However, as we explain Appendix Section F, Iyengar et al. (2019) have mistakes in their privacy analysis. Therefore, we think it is particularly interesting to compare to DP-SGD with the corrected privacy analysis of the objective perturbation.\n\nMoreover, looking at the analysis of Altschuler and Talwar (2022), (https://arxiv.org/pdf/2205.13710.pdf), we don't think their results are as comparable as they consider the projected noisy-SGD. In their RDP bounds there is always the diameter $D$ of the projection set that would need to be tuned as well.  For the parameter values we have, it is not clear if the convex analysis would improve upon the common (non-convex) DP-SGD RDP analysis. This is reflected in Thm. 1.3 by Altschuler and Talwar (2022), where the bound has the factor $\\min \\left(T, \\frac{D n}{L \\eta} \\right)$, where $n$ is the size of the dataset, $L$ the Lipscitz constant of the gradients and $\\eta$ the learning rate, and where $T$ is the number of training iterations and corresponds the result to the common RDP analysis of the Gaussian mechanism."}]

Author rebuttal:

Meta-review: While the paper has a negative score, in overall the reviewers and I think the contribution is significant enough. In particular, it points out a legitimate bug in a paper (http://proceedings.mlr.press/v23/kifer12/kifer12.pdf) written 11 years back. One point to mention is that the same idea of a fix for GLMs was presented in a COLT paper (https://proceedings.mlr.press/v195/agarwal23d.html) this year. However, the reviewers, and I  are willing to consider this paper to be independent, since the NeurIPS submission deadline was prior to COLT conference.
Decision: Accept (poster)