The importance of feature preprocessing for differentially private linear optimization
Authors: Ziteng Sun
Ananda Theertha Suresh
Aditya Krishna Menon
Venue: ICLR 2024 poster (2024)
Keywords: private optimization
feature preprocessing
differential privacy
Primary area: societal considerations including fairness, safety, privacy

Abstract: Training machine learning models with differential privacy (DP) has received increasing interest in recent years. One of the most popular algorithms for training differentially private models is differentially private stochastic gradient descent (DPSGD) and its variants, where at each step gradients are clipped and combined with some noise. Given the increasing usage of DPSGD, we ask the question: is DPSGD alone sufficient to find a good minimizer for every dataset under privacy constraints? 

As a first step towards answering this question, we show that even for the simple case of linear classification, unlike non-private optimization, (private) feature preprocessing is vital for differentially private optimization.  In detail, we first show theoretically that there exists an example where without feature preprocessing, DPSGD incurs a privacy error proportional to the maximum norm of features over all samples. We then propose an algorithm called *DPSGD-F*, which combines DPSGD with feature preprocessing and prove that for classification tasks, it incurs a privacy error proportional to the diameter of the features $\max_{x, x' \in D} \|x - x'\|_2$. We then demonstrate the practicality of our algorithm on image classification benchmarks.

Published as a conference paper at ICLR 2024
THE IMPORTANCE OF FEATURE PREPROCESSING FOR DIFFERENTIALLY PRIVATE LINEAR OPTIMIZATION
Ziteng Sun, Ananda Theertha Suresh, Aditya Krishna Menon Google Research, New York {zi reigengsun, theertha, addiyyakmenoneeooogl.e.
ABSTRACT
Training machine learning models with differential privacy (DP) has received in- creasing interest in recent years. One of the most popular algorithms for training differentially private models is differentially private stochastic gradient descent (DPSGD) and its variants, where each step gradients clipped and combined with some noise. Given the increasing usage DPSGD, we ask the question: is DPSGD alone sufficient find a good minimizer for every dataset under privacy constraints? Towards answering this question, we show that even for the simple case of linear classification, unlike non-private optimization, (private) feature pre- processing is vital for differentially private optimization. In detail, we first show theoretically that there exists an example where without feature preprocessing. DPSGD incurs an optimality gap proportional to the maximum Euclidean norm features over all samples. We then propose an algorithm called DPSGD-F, which combines DPSGD with feature preprocessing and prove that for classifica- tion tasks, it incurs an optimality gap proportional to the diameter of the features xa || z' [|2- We finally demonstrate the practicality of our algorithm on image classification benchmarks.
INTRODUCTION
Differential privacy (DP) (Dwork et al., 2014) has emerged as one of the standards of privacy in machine learning and statistics. In machine learning, differentially private methods have been used to train models for language modelling (McMahan et al., 2018), image classification (De et al., 2022), generative diffusion (Ghalebikesabi al., 2023), and private fine-tuning Yu al. (2021); Li et al. (2021). We refer readers to Ponomareva et al. (2023) for detailed survey of techniques and current state of the art methods in private optimization. Following the influential work of Abadi et al. (2016), differentially private stochastic gradient descent (DPSGD) has emerged as one of the most popular algorithms for training private machine learning models and achieves state of the art results in several datasets (De et al., 2022: Ghalebikesabi et al., 2023).
There has also been a recent line of work that focuses on analyzing the theoretical performance of DPSGD and its variants, with particular focus convex models (Bassily et al., 2019; Feldman et al., 2020; Bassily et al., 2020; 2021b;a; Song et al., 2021b; Arora et al., 2022). has been shown that DPSGD and its variants can achieve min-max optimal rates for the task of DP empirical risk minimization and DP stochastic convex optimization under various geometries. Moreover, for convex generalized linear models, DPSGD has also been shown achieve dimennsion-iddeeenden convergence rate (Song et al., 2021b; Arora et al., 2022). This observation can be extended to general convex models under certain assumptions (Li et al., 2022).
Despite the practical success and appealing theoretical properties of DPSGD, recent empirical results have shown that they may learn good intermediate features in deep learning image classification tasks (Tramer & Bonch, 2021). In fact, it has been observed in Abadi et al. (2016) that performing a private PCA on the features before performing DPSGD can improve the performance of private training, which highlights that learned features may not be good. This raises fundamental question:
Can private feature preprocessing provably improve DPSGD?
There no clear intuitive answer to this question. On the one hand, feature preprocessing accelerates the convergence of gradient methods in optimization (LeCun al., 2002), which can help private

---

Published as a conference paper at ICLR 2024
optimization since the number of steps is constrained by the privacy requirement. On the other hand, private feature preprocessing will use a portion of the privacy budget, thus decreasing the privacy budget for the DPSGD phase.
As a first step towards answering this question, we show that for the simple task of linear private classification, unlike non-prine non-private convex optimization, feature preprocessing is necessary for private optimization to achieve near instance-optimal results. Our findings are as follows.
1. We provide example where DPSGD with any clipping norm, batch size, and learning rate incurs an error proportional to the maximum Euclidean' norm of feature vectors (Sec- tion 4).
2. We propose DPSGD-F, a new algorithm that combines both DPSGD and feature prepro- cessing. and show that the leading term of the error degrades proportional to the diameter of the dataset, which can be significantly smaller than the maximum norm (Section 5). cetemattion-hhhoretee lower bound
We also complement our result with a near-matching (Section 6).
3. We empirically validate our findings on a few standard datasets and show that DPSGD-F outperforms DPSGD on subset of the datasets. For the task of privately finetuning the last layer of pretrained model (using ImageNetI K) on CIFAR-100 under E = 1, our result improves the previous accuracy from 70.6% (De et al., 2022) to 71.6% (Section 7).
The rest of the paper is organized as follows. In Section 2, we outline the problem setting and in Section 3 discuss prior work and contribution. In Section we provide counter-example for DPSGD and in Section 5, we describe our new algorithm and its performance. In Section 6, we provide information theoretic lower bound. Finally, in Section 7, we demonstrate the practicality of the proposed algorithm on image elssification tasks.
PRELIMINARIES
Classification. Let X' denote the feature space and y [-1,1} be the of labels. Unless
otherwise specified, we set X' to be ball of radius R in d-dimensional space denoted by B (R). R).
Let be classifier that takes parameter and feature x and computes score h(8,z) R. The
performance of the classifier is measured by loss function &: IR. x margin loss (Bartlett et al., 2006) of the form
y - R+. We assume e is
e(h(O, ().00.).11 v) ply (0y)h(0,xx))
(1)
where o: R + R is typically a convex, non-incrgsingg function with a bounded value s(0) < oo O. Canonical examples of include the hinge loss (0=) [1 =]+, and the logistic loss (0()
log(1 + +
Let D ((1,, vi) )ej be training set of size n. Typically, the goal is to learn classifier by minimizing the average loss over all samples given by
L( D)
2h00.
VE(N)
We are interested in linear classification models that are described as follows. Let 0 = (w, b) e gd+1, where w E _d and E R, and h((w, 6), x.)) = w w-z; We further assume that ((h(0, x),, y) is convex in f, and that Vy, f(..2) y) is convex and G-Lipschitz in the first argument. The model can be viewed as a generalized linear model (GLM), with additional restrictions on the loss function. We denote the minimizer of the empirical loss by
03 E arg min L(0, D).
We will drop the subscript when the dataset is clear from context. The following assumption on the minimizer will be useful in our performance analysis. assumes that the minimizer not a trivial solution which does not separate any two data points in the dataset. This is reasonable assumption as long as E is a good proxy loss for classification.
Assumption (Nontrivial minimizer). The dataset D and loss function l satisfies that at the mini- mizer 6*, there exists x, x' E D such that
h(0 (r) h(0", x²) 0.
When unspecified, we use norm refer the Fuclidean norm by default.
2

---

Published as a conference paper at ICLR 2024
Algorithm Differentially private SGD (Abadi et al., 2016)
Input: Input: Dataset D = {x11 31), (#2, 12),..., (In, Nn)] of n points, privacy parameter E, 6, clipping norm C, step size 77, number of iterations T, batch size B 2 max(n///44,, 1}.
1: Set o² 8TC* log(1/6)
n'c 2: Choose an inital point 0y.
3: for = 0, ......... T 1 do
4: Sample batch B, of B data points with replacement.
5: For all i E B₁, compute the gradient VE(h(A, x;)) y:)-
6: Compute noisy clipped mean of the gradients by
gt = Br
(2)
iEB
7: Update the parameter by w(+1 wt 799t
8: end for
9: Return T= Σ wt
Differential privacy (DP) (Dwork et al., 2014). DP requires the optimization algorithm to output similar outputs for similar training datasets. More precisely, differential privacy is defined below.
Definition (Differential privacy). Let 'D be collection of datasets. An algorithm A: D R is (e, 8DP if for any datasets D and D' that differ by only one data point, denoted as DDD' = 1, and any potential outcome O the algorithm satisfies
(A(D)) E 0) S Pr (A(D')) E + +
Our goal is to find a Ppv that is (e. (c.5)-oo differrential private and minimizes the optimality gap w.r.. the empirical risk, which is also referred to as the privacy error,
( D)] min L),
where the expectation is over the randomness of the private algorithm.
Notations. We use Clip(æ, C') to denote the clipping operation with norm C, defined by
Clip(z, C)):= min {
C
||0||2
For vector of dimension d, we use (a, 1) refer the (d+ -idimension vector obtained from augmenting to æ. We use diam(D): max,,''D || - z' l|2 to denote the diameter of features in the dataset D. Given set of features T1. Z2.......:.. 2y from dataset D, let (DD denote the eigenbasis of E. Let M(D) be the projection operator to this eigenspace UD),, given by M(D) (D)(((()) Then, M(D) defines a seminorm given by
| = (D) 112.
RELATED WORK AND OUR CONTRIBUTION
Differentially private stochastic gradient descent (DPSGD). We start by describing the mini- batch variant of the DPSGD algorithm in Algorithm 1. The DPSGD algorithm is modification of the popular SGD algorithm for training learning models. each round, the individual sample gradients are clipped and noised to bound the per-round privacy loss (the influence of one data point). The overall privacy guarantee combines tools from privacy amplification via subsampling and strong composition (see Abadi et al. (2016)).
DPSGD has shown to achieve cimeension-indeeendeer convergence result for optimizing generalized linear models. The upper bound below is implied by Song et al. (2020, Theorem 4.1).
"Given vector space V over real numbers, seminorm V is nonnegative-valeed function Q such that for all x E and v V. Q(= v) -(e)) and for all u, U E V. Q(u v) 5 Q(a) + Q(v).
3

---

Published as a conference paper at ICLR 2024
Lemma (Song et al. (2020)). There exists an (E, instance of DPSGD, whose output satisfies,
p0r(,, D)] L(0 D) s 2G| 1l (Vro///aaii (ogn
ne
where G is the Lipschitz constant of the loss function. R = max; | and M M(D) with D' [[xx1) x D).
Note that in the analysis in Song al. (2020), the norm the gradients is bounded by GV R + 1, and the clip norm is chosen such that the gradients are not clipped. The above result is shown to be minimax optimal in terms of the dependence on the stated parameters. Recall that diam(D):= m&X o x2|2 denotes the diameter of feautures in the dataset D. So natural question is to ask is whether the dependence on R can be improved to diam (D), which can be useful in cases when dataset if more favorable e.g., when diam(D) < R. If yes, the improvement be achieved by DPSGD?
We answer the first question by proposing an algorithm that combines feature preprocessing and DPSGD, and improves the dependence on R to diam(D) in the leading term of the optimality gap, stated below.
Theorem 1. There exists an (s, diffferrnnt private algorithm DPSGD-F, which is combina-
tion of private feature preprocessing and DPSGD, such that when n = Ω [Vllog(1/]log R llo((d)
and & = =O1), the output prr satisfies
[0p D)] L))
=0 GI [0GG10TIN (Diam()) +
( (rrank(M) (1/0) log n²
R
log(n)
nE
ne
where M MD') with D' = ((x, x E DJ. As discussed before Lemma 3, v can be reduced to any inverse polynomial function of n. by increasing the requirement n by constant factor.
We will describe the algorithm and disuess the proof in Section The next theorem states that the first term in the above result is tight.
Theorem 2. Let A be any (e, DD optimization algorithm with = S e and S CE/n for some constant e >> O. There exists dataset D = { y.), E [n]] and loss function E(O 2, y) that is convex and G-Lipschitz loss functions for all y. which is of form Eq. (1), and
E [T(A(D)), D)] - I(0%, D) = 22 G. (C-diam(D) min { 1, ||0* Ia rrank(M M) )).
where M M(D) with D' [(x, 1) x E D}.
Moreover, we show that DPSGD must incur an error proportional to R by providing a counter- example in Section 4.
A MIANNTER-EXAPPON FOR DPSGD
We consider the simple case of binary classification with hinge loss. Let > 0. Let e1 and e2 denote two orthogonal basis vectors. Suppose dataset D' is partitioned into two equal parts D' and D' 1- each with size n/2. D' contains n/2 samples with μuf e2 and y = 1 and D' contains n/2 samples with x = μ Similarly, let the dataset D" is partitioned into two equal parts D and D" each with size n/2. D contains n1/2 samples with æ = μеj + E2 and y -1 and D", contains n/2 samples with = μed C2 and y 1. We assume there is no bias term for simplicity, iee., b 0². For any (1), (2)), let
and -1. A visualization of the dataset is provided in Fig. 1.
l(w v) max 1 v(w x), 0}.
The bias term can he added by assuming there is an additional entry with in the feature vector. The proof will go through similarly the optimal parameter has = O.
4

---

Published as a conference paper at ICLR 2024
(,.1),
(H.
O+ (-H,-11
(44-
Figure I: Feature vectors.
Figure 2: Gradient vectors.
Further, the average empirical loss on will be
L(w, D') = max 11 - (1) + w(2)). 03 + max + (mwа(1) - w(2)),
Observe that wn = (0, 1) has zero empirical loss for for dataset D' and w" (0, -0) has zero empirical loss for for dataset D" The next theorem states that DPSGD with any clipping norm, batch size, number of steps, learning rate and any initialization will not obtain nontrivial error on both D' and D when μ > NE.
Theorem 3. Let A be (E, 5--rivate DPSGD algorithm with any number of steps T, learning rate f, clipping norm C, and (possibly randomized) initialization wo. We have when n < p/e.
max [[] min L(w, D)) 2(1).
DE(D'D"M
w
The crux of the proof involves showing that if the initialization is "uninformative" for dataset, then DPSGD does not obtaín nontrivial error when μ > ne. Here by "uninformative", we mean for dataset D' and wo(2) 2 0 for dataset D Note that at least one of the above two conditions must hold. Below we give a high-level idea the proof. Since Dí and D'_, (and similarly DI and D" have the same 2=1), the performance of the final optimizer will depend mostly on the second parameter (2)). The following lemma can be proved.
we (wo(1), 1), (2)) satisfy that wp(2)
Lemma 2. For dataset D', let u be any iterate of the DPSGD algorithm, then
EE [LW,,, D') min L(w, D') > Pr (w(2) S 5).
Similarly, for dataset D"
E [[W, D")] min L(w, D 2 Pr (w 2 0).
We will focus on the case when (2) < and consider dataset D' and loss L(w, D'y*, It would be enough to show that for every iteration f, the parameter wi has a constant probability of being negative. The gradient of each individual loss functions satisfies that for (z, y) D', have
1 (1) w(2) 13 (-1--1 {1 [1 + w2) < 13 (H, -1) if (x. v) E D'
if (x, v) E D1,
Vil(w 2.
Hence the norm of the gradient vectors can be as large as 1 +I. By clipping the gradient to norm C, the 'signal' component of the gradient on the second coordinate will be decreased to Miinl,C///ie + 1J. However, in each iteration, DPSGD will add Gaussian noise with standard deviation proportional C/ns, which can be large compared to min(1, C/ V n22 + 1} when μ is large. When n < p/s, the total noise will dominate the signal, making the probability of wx < 0 nontrivial. We provide the complete proof in Appendix A.
DPSGD with better mean estimation algorithm. One attempt to solve the above issue is to replace Eq. (2) by recently proposed private mean estimation algorithms, which can improve the estimation error to scale with the diameter of the gradients (e.g.. in Karwa & Vadhan (2017); Huang al. (2021)). However, it unclear whether this will work. As shown in Fig. 2, the diameter the gradients can be proportional to the maximum norm of feature vectors instead of the diameter.
"When (2) will consider 1 and loss L(w, D instead.
5

---

Published as a conference paper at ICLR 2024
Algorithm 2 DPSGD with feature preprocessing (DPSGD-F).
Input: Input: Dataset D = { M1), (22, y2),..., (In, yn)] } of n points, E, Private mean es- timation algorithm Priv (Lemma 3). Private quantile esimation algorithm PrivQuantile (Lemma 4), DPSGD for GLM (Lemma 1).
1: Private mean estimation. Compute ü., the differentailly private mean of features in D with Lemma and privacy budget (e/3, 6/3).
2: Private quantile estimation. Let
{||x All2, E D} be the set of distances from the
feature vectors to the computed mean. Find a private quantile t set S using Lemma 4 with privacy budget (z/3, 6/3).
3: Translate and augment the dataset with bias. Preprocess the dataset by translation and ap- pending a constant feature т. Let D' ((1),1)),-.. y1),..,, (1r Un)3 where
z (z) 7)
4: Feature clipping. Let D (x*1 91 (2/2 1/2) ................................ (1% mn)]. where
x Clip 2 V2T)
5: DPSGD with preprocessed features. Compute an approximate minimizer Pp E Rd++1 of I(0, D") using the DPSGD algorithm for GLM in Lemma with (e/3, (e/3,6/3). 6: Returrn piv (Wpre ), where Uprv prv df and bprv 0prv [d + 1|T p..
In the next section, take advantage of the fact that the data points close in the fea- ture space, and design an algorithm that first privately preprocesses the features and then per- form DPSGD to achieve better bounds. In particular, the bound in Theorem I states that when max( (lo((())(() log(1 /ee Vu/e) & < p/e, the new algorithm achieves o(1) error, which is strictly better than DPSGD.
A FEATURE PREPROCESSING AUGMENTED DPSGD ALGORITHM
We propose new algorithm called DPSGD-F (Algorithm 2) that combines feature preprocessing and DPSGD. We show that the new algorithm can achieve the performance described in Theorem 1. We overview each step of the algorithm below and provide theoretical guarantees for each step. The detailed proofs are listed in Appendix B.
Private mean estimation of features. We first compute a differentially private mean of features using the instance-optimal mean estimation algorithm from Huang et al. (2021), who showed that the mean can be estimated efficiently with error proportional to the diameter of the dataset. The following result on private mean estimation follows by combining Theorem 3.3 and Remark 3.2 from Huang et al. (2021). Note that the result of Huang et al. (2021) is high-probability bound, which does not explicitly depend on R (or r(D) in their notation). To obtain in-expectation bound, choose a failure probability of 1 1/n2 in the proof and this results in the R/n2 term in Lemma This term be reduced any inverse polynomial function of n by inereasing the requirement in the assumption by a constant factor. We choose 1/n2 here mainly for presentation purpose. See Appendix B.1 for the detailed analysis.
Lemma (Appendix B.1). Lete I log(3/8) and 2 ( Vállog1/ log, logíd) for a sufficiently
large constant e, then there exists an 6/3,6/3)-Dr algorithm whose output j E (R) satisfies
2R
ElIl μ [|]2]] < diam +
n?
The above lemma implies that if n is large enough, A good approximation for μ and hence Ellaa - A]]2] < 2diam D)
2R
Vx, E D,
n²
Existing algorithms for differentially private ERM require the knowledge of dian(D). which is unknown. Hence, we compute estimate of diam(D) by private quantile estimation.

---

B[r|A] & max ||:; - i012 + n² Published as a conference paper at ICLR 2024
Private quantile estimation. Changing one sample in dataset change the diameter by R. Hence, the sensitivity of diam(D) is R and it difficult to estimate it privately with good accuracy. Instead we estimate the ((1((ne) quantile of I| All2 using Dick et al. (2023, Theorem 2).
Lemma (Appendix B.2). There exists a (E/3, 8/3) algorithm that finds a threshold T such that
2R
Let с = O() and Z, be the number of points such that |2 iill is larger than т, then EiZ, A S 125 log n.
Translated and augment dataset with bias. Another issue with the above mentioned approach is the scale of the bias term. If 0 (w, b). then the gradient with respect to w scales linearly in x, but fixed constant for This causes issues in the theoretical analysis. Hence, we construct an augmented dataset D) where x (x; i,, r). Note that x' E Rd+1, We also remove the bias term when optimizing over D' since we have already included bias term in the augmented features. This also guarantees that the norm of the gradient is bounded by ((r) with high probability. We show that we are not losing any information in translation and augmentation and hence the minimum value of empirical risk should remain the same. We formalize it in the next lemma.
Lemma 5. For any O (w, b), let f' (w, (b + ()/T), we have L(O, = L(6',
In particular, (w", ,b) is minimizer of D if and only (w", (b* + st /T) is minimizer of D'.
Proof. To prove the first result, observe that for any point (I, y) E D,
((h((1, b),t,,)),,),,)) = Φ(v (w x b))
<ly (w (x - ji) + + R)) o(y' (w.x' (b + T))
((h((w, (b x)/r),,'),'')
The second result follows by taking the minima over all (w, b) in the first result.
Recall that results privacy error involve the projector on the design matrix and the norm of the minimizer. Hence, we next provide connections between the rank of M (DD and MDD) and the norms of the minimizers of D and D'. The proof mainly follows from the fact that the translating and augmenting operations are performing the same linear operation on each data point, which won't t change the minimizer up scaling and the bias term.
Lemma 6 ((Appendix B.3)). Let MD) and MDD) be the projectors design matrices of non- augmented dataset D and augmented dataset D' respectively, then
rank(M((D)) S rank(M(()) +
Furthermore, let 8r and 8 be the empirical risk minimizers of D and D' respectively. If Assump- tion I holds then
E1100'11 TlA] < 1| max || 2:l12 2 12R
z.ED
n²
Feature clipping. As mentioned above, due to errors in previous steps, the le norm of the features may not be bounded with small probability. Hence, we clip the augmented features from dataset D' to obtain a dataset D Similar to the Lemma 6, we relate the rank of M (D') and M (D") next. The proof mainly follows from the fact that clipping will only change the scale of each feature vector but not their direction.
Lemma 7 (Appendix B.4). Let M(D" and MDD" be the projectors to the design matrices of datasets D' and D" respectively, then
rank(M(DD)) ran)(M((D)).
7

---

Published as a conference paper at ICLR 2024
DPSGD with preprocessed features. We next solve ERM using DPSGD algorithm D Since norm of the features are bounded by v2r, the gradients will be bounded by v2Gr. Furthermore, since the dataset is augmented, we don't include the bias term and treat weights as a vector in IR++1 The guarantee of DPSGD on these features follows from previous work Song et al. (2020, Theorem 4.1). Similar to Song al. (2020), the clipping norm is chosen to be v2Gr so that gradients are clipped in all steps.
Reverting the solution to the original space. The output of the DPSGD algorithm is in IR++1, and furthermore only works on the translated and augmented dataset D Hence, we translate it back to the original space, by appropriately obtaining Wpry and rescaling the bias.
The computation complexity of the algorithm the same as DPSGD since the preprocessing algo- rithms can all be implemented in time Ó(nd), which is less than that of the DPSGD phase. The proof of privacy guarantee in Theorem 1 follows directly from the composition theorem (Dwork al., 2014. Theorem 3.16). The utility guarantee follows from the above stated results and we provide the complete proof of in Appendix B.5.
6 LOWER BOUND
In this section, we prove Theorem 2, which shows that the performance of our algorithm is tight up to logarithmic factors. The proof follows almost immediately from Theorem 3.3 in Song et al. (2021a), with a slight modification to the label and loss function to make sure that it is a valid classification problem of form Eq. (I). We first state the result in Song al. (2021a) (a restated version of Theorem 3.3) below.
Theorem (Song et al. (2021a)). Let A be any (E, 8) algorithm with E I c and 6 I CE for some constant e > O. Let 1 < do I d be an integer. Let E be defined by E(O- xz V) = 00 x yl. Then there exists a data sei D = ((2s, M:), E [n]} such that the following holds. For all E [m], x; E {(0. 0), (1, ................. . 0), (0, 1,0, 0,................. 0), (O...., 1)} and yi E {0, 1). Let 0- = arg min [(;; D)
deR
(breaking ties towards lower [0]|2). We have |10" E [0, 1]4 and
D)] I. (6"; D) 2 Ω min {1, do
en }).
E T. (Projjo.nu(((D))))
where Proijo. (A(()) denotes the projection of A(D) to [0, 1jd.5
Proof of Theorem 2: Take the dataset D = ((r,, Wt), i E [n]] from Theorem 4, we can construct
dataset D' as following. Vi, let x = 24, y/ 2y, 1. Set ll (0-2) xx, y) max [1 y(20- x 1), 0}.
which is of the form Eq. (1). Then, for all 0 [0, 1]d, we have 0 x E [0, 1] and
2 20 = |20 x 1 1 yl
if y +1,
('(0 z,
20 r 220
vl if y 1.
Hence Vi E [n], (( 24.1/ v/)
120 x 1 v/1 2 xz Val. Moreover, it can be seen that
Vx E [0, 1] y E (+1,-) -1}
E' (Proj (j) v) < ( x. v)-
(4)
Hence the minimizer of L0; D') lies in [0, 1]d The above facts imply that 0* is also the minimizer of (0; D'), and by Theorem 4,
E I' (Proja. (A((")) D') L' ('(0) Ω min 1, do
})
Together with Eq. (4), we have
do
E ELL' (A(D), L' (0"; 2 min 1, en
'Theorem 3.3 in Song et al. (2021a) is stated without the projection operator while in fact the projection operator is used throughout the proof of Theorem B.1 and Theorem 3.3. Hence the stated result holds with no change the proof.
8

---

Published as a conference paper at ICLR 2024
Note that for all 0 R Vi [n], 110e (h(0, 1/212 2||2:|12 2. And the dataset satisfies that diam(D) I v2, rank (ank(i:=> Ei=
).r; s do. Moreover, ||0'| 110'12 la vdg. Hence have
[T' (A(D"), DJ) T,' (0"; D3) 2 Ω diam(D') min (1, 110 (M)
ne
The proof can be generalized to a general Lipschitz constant G and diam by rescaling.
EXPERIMENTS
We empirically demonstrate our findings by evaluating DPSGD and our proposed feature- normalized DPSGD (DPSGD-F*) for the task of training a linear classifier on three popular image classification datasets: (1) MNIST (Lecun et al., 1998); (2) Aishion-MNIST (Xiao al., 2017); (3) CIFAR- 100 (Krizhevsky et al., 2009) with pretrained features. For MNIST and Fashion-MNIST, we directly train linear classifier with the pixel-format images as inputs. For CIFAR-100, we use the features obtained from the representations in the penultimate layer in a WRN model pretrained on ImageNet (De et al., 2022). In this case, training a linear classifier using these features is equivalent to fine-tuning the last layer of the WRN model.
Table 1: Accuracy comparison on different datasets with different values of E and 5 = 10 10-5, CIFAR-100 is trained and tested using features pretrained on ImageNet (De et al., 2022). Each number is an average over 10 independent runs. The number in the parenthesis represents the stan- dard deviation of the accuracy under the optimal parameter settings.
Accuracy (e 1)
Accuracy (E = 2)
Non-private acc.
Dataset
DPSGD
DPSGD-F
DPSGD
DPSGD-F
SGD
MNIST
87.4 (0.1)
92.0 (0.1)
89.6 (1.2)
92.3 (0.1)
92.9 (0.1)
FMNIST
77.2 (0.4)
84.0 (0.1)
78.7 (0.4)
84.5 (0.2)
85.0 (0.1)
CIFAR- 100 (pretrained)
70.6 (0.3)"
71.6 (0.2)
73.8 (0.2)
74.4 (0.2)
78.5 (0.1)
Similar to De et al. (2022), for each combination of dataset, privacy parameter, and algorithm, we report the best accuracy obtained from a grid search over batch size, steps size, and number of epochs For DPSGD-F, preprocessing phase and the DPSGD phase. We leave choosing the parameters automatically as future direction. Detailed implementation and parameter settings are listed in Appendix C.
also did grid search over the allocation of privacy budget between the
Our results are listed in Table Our proposed algorithm consistently improves upon DPSGD for all three datasets under and = which empirically demonstrates theoretical findings.
8 DISCUSSION
In this work, we ask the fundamental question of whether DPSGD alone is sufficient for obtaining good minimizer for linear classification. We partially answer this question by showing that the DPSGD algorithm incurs privacy error proportional to the maximum norm of the features over all samples, where DPSGD with feature preprocessing step incurs a privacy error proportional to the diameter of the features, which can be significantly small compared to the maximum norm of features in several scenarios. Our preliminary experiments show that feature preprocessing helps in practice on standard datasets. Investigating whether these results can be extended to bigger datasets and beyond linear models remain interesting open questions.
We perform modified version of Algorithm 2, which better aligns with existing practical implementations DPSGD. See Algorithm for details. Note that the resulting algorithm is still a valid (c, 6) -iifferentially private.
7 "The reported accuracy using DPSGD De al. (2022) is 70.3%. We note that the improvement 70.6% due the fact that we using the privacy accoutant based on Privacy Loss Distributions (Meiser & Mohammadi, 2018; Sommer et al., 2019; Doroshenko et al., 2022), which leads a smaller noise multiplier under the same privacy budget. "The reported accuracy doesn't take into account the privacy loss in the hyperparamter tuning phase.

---

Published as a conference paper at ICLR 2024
REFERENCES
Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, llya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pp. 308 308-318, 2016.
Raman Arora, Raef Bassily, Cristóbal Guzmán, Michael Menart, and Enayat Ullah. Differentially private generalized linear models revisited. Advances in Neural Information Processing Systems, 15:22505-22511 2022.
Borja Balle and Yu-Xian Xiang Wang. Improving the Gaussian mechanism for differential privacy: Analytical calibration and optimal denoising. In Jennifer Dy and Andreas Krause (eds.), Pro- ceedings of the 35th International Conference on Machine Learning, volume 80 of Proceed- ings of Machine Learning Research, pp. 394 403. PMLR, 10-15 Jul 2018. URL https:
/ //proceedings.ml:: ptess Titeess/v0//ba www.////////aaeeeeee html.
Peter L. Bartlett, Michael I. Jordan, and Jon D. Mcauliffe. Convexity, classification, and risk bounds. Journal of the American Statistical Association, 101 1473))) 2006. ISSN 01621459. URL
http: / www. jstor. http:/saallle/eee st0o////eale//444.....
Raef Bassily, Vitaly Feldman, Kunal Talwar, and Abhradeep Guha Thakurta. Private stochastic convex optimization with optimal rates. In Advances in Neural Information Processing Systems, pp. 11279 11288, 2019.
Raef Bassily, Vitaly Feldman, Cristóbal Guzmán, and Kunal Talwar. Stability of stochastic gradient descent on nonsmooth convex losses. Advances in Neural Information Processing Systems, 33: 4381-4391, 2020.
Raef Bassily, Cristóbal Guzmán, and Michael Menart. Differentially private stochastic optimization: New results in convex and non-convex settings. Advances in Neural Information Processing Systems, 34:9317-9329, 2021a. 2021a.
Raef Bassily, Cristóbal Guzmán, and Anupama Nandi. Non-euclidean differentially private stochas- tic convex optimization. In Conference on Learning Theory, pp. 474 499. PMLR, 2021b.
James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman-Milne and Qiao Zhang. JAX: composable transformations of Python+NumPy programs, 2018. URL http:
//github com/ google/jar
Soham De, Leonard Berrada, Jamie Hayes, Samuel L Smith, and Borja Balle. Unlock- ing high-accuracy differentially private image classification through seale. arXiv preprint Stti:220041365500 2022.
Travis Dick, Alex Kulesza, Ziteng Sun, and Ananda Theertha Suresh. Subset-based instance opti- mality in private estimation. arXiv preprint arXiv:2303.0124 2023.
Vadym Doroshenko, Badih Ghazi, Pritish Kamath, Ravi Kumar, and Pasin Manurangsi. Connect the dots: Tighter discrete approximations of privacy loss distributions. Proceedings on Privacy Enhancing Technologies, 1:552-570, 2022.
Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 933-4):211440 2014.
Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimization: Optimal rates in linear time, 2020.
Sahra Ghalebikesabi, Leonard Berrada, Sven Gowal, Ira Ktena, Robert Stanforth, Jamie Hayes, Soham De. Samuel L Smith, Olivia Wiles, and Borja Balle. Differentially private diffusion models generate useful synthetic images. arXiv preprint arXiv:2302. 2023.
Google.
Tensorflow privacy,
2018.
URL
https: //:::///tt /github. com/ google/
di fffernentall ipprentayyy...../
10

---

Published as a conference paper at ICLR 2024
Ziyue Huang, Yuting Liang. and Ke Yi. Instance-optimal mean estimation under differential privacy. Advances in Neural Information Processing Systems, 34:25993 -00044 2021.
Peter Kairouz, Ziyu Liu, and Thomas Steinke. The distributed discrete gaussian mechanism for federated learning with secure aggregation. In International Conference on Machine Learning, pp. 5201-5212. PMLR, 2021.
Vishesh Karwa and Salil Vadhan. Finite sample differentially private confidence intervals, 2017.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Y. Lecun, L. Bottou, Y. Bengio, and P. Haffnne. cladient-basedd learning applied to document recog- nition. Proceedings of the IEEE, 86(1 1):2278-2222 1998. doi: 10. 1e.1109//7799....
Yann LeCun, Léon Bottou, Genevieve Orr, and Klaus-Robert Müller. Efficient backprop. In
Neural networks: Tricks of the trade, pp. 9-50. Springer, 2002.
Xuechen Li, Florian Tramer, Percy Liang, and Tatsunori Hashimoto. Large language models can be strong differentially private learners. In International Conference on Learning Representations, 2021.
Xuechen Li, Daogao Liu, Tatsunori B Hashimoto, Huseyin A. Inan, Janardhan Kulka- mi, Yin-Tat Lee, and Abhradeep Guha Thakurta. When does differentially pri- vate learning not suffer in high dimensions?
In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (eds.), Advances in Neural Infor- mation Processing Systems, volume 35, pp. 28616-28630. Curran Associates, Inc., cc/cccc//oeee httpppaprr..e pappr_filess///eaaaaaaaaaaeeeeee www.s//pppeeeee/e//ee// 2022. URL https:// http://pocceeiin........eeee Paper Conference F Paapraaeeeeepppe----orreeeeeeeee pdf.
H Brendan McMahan, Daniel Ramage, Kunal Talwar, and Li Zhang. Learning differentially private recurrent language models. In International Conference on Learning Representations, 2018.
Sebastian Meiser and Esfandiar Mohammadi. Tight on budget? tight bounds for r-fold approximate differential privacy. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, CCS '18, pp. 247-264, New York, NY. USA, 2018. Association for Computing Machinery. ISBN 978 4704569366900 doi: (0.11455/2433334.2437655 URL https: //doi. oegilorgg/1e 10. 44/324333355 01133323334333111333333 3243765.
Natalia Ponomareva, Hussein Hazimeh, Alex Kurakin, Zheng Xu, Carson Denison, H Brendan McMahan, Sergei Vassilvitskii, Steve Chien, and Abhradeep Thakurta. How to dp-fy ml: A practical guide to machine learning with differential privacy. arXiv preprint arXiv:2303.0065: 2023.
David Sommer, Sebastian Meiser, and Esfandiar Mohammadi. Privacy loss classes: The central limit theorem in differential privacy. Proceedings on Privacy Enhancing Technologies, 2019: 245-269, 04 2019. doi: 10.2478/popets-20199 2019-0099.
Shuang Song, Om Thakkar, and Abhradeep Thakurta. Characterizing private elipped gradient de- scent convex generalized linear problems. arXiv preprint arXiv:2006.06777 2020.
Shuang Song, Thomas Steinke, Om Thakkar, and Abhradeep Thakurta. Evading the curse of dimen- sionality in unconstrained private glms. Arindam Banerjee and Kenji Fukumizu (eds.), Pro- ceedings of The 24th International Conference Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pp. 2638-2646 PMLR, 13-15 Apr 2021a. URL https:tpp//.om.. http://occeeenngcccec/// mlr press / v130 song2la. .1t.mml..mmm..m.mmmmm.mmm......m
Shuang Song. Thomas Steinke, Om Thakkar, and Abhradeep Thakurta. Evading the curse of dimen- sionality in unconstrained private glms. In International Conference on Artificial Intelligence and Statistics, pp. 2638-2646, PMLR, 2021b.
Florian Tramer and Dan Boneh. Differentially private learning needs better features (or much more data). International Conference on Learning Representations, 2021. URL https:
/ /ppenrevieww net. hor//formmmmm/ deyorrrrgd..

---

Published as a conference paper at ICLR 2024
Han Xiao, Kashif Rasul, and Roland Vollgraf. Prahioo--miis a novel image dataset for benchmark- ing machine learning algorithms. CoRR, abs//770..0747, 2017. URL http::taatpi..oaeeeee////
abs/ abs/1708 07747.
Da Yu, Saurabh Naik, Arturs Backurs, Sivakanth Gopi, Huseyin A Inan, Gautam Kamath, Janardhan Kulkarni, Yin Tat Lee, Andre Manoel, Lukas Wutschitz, et al. Differentially private fine-tuning of language models. arXiv preprint arXiv:2110.06500, 2021.
A PROOF OF THEOREM
In the proof, we assume (2) S O and consider D = D'. The proof will follow similarly when (2) 2 and D D". We start by proving Lemma 2.
Proof of Lemma 2: Since max
0} is a convex function in we have
L(w, D) = max - (mrr() 1) + w(2)). 03 + 2 max (1 + (1rτ(1) - (2)),
2 max{ 1 (1r0(1) + (2)) + + (1 - =x))) .0}
2
max [1 w(
This implies that
E [ D)] min L(w, D) 2 E9 maxx - w(2),0}) 2 Pr (wx(2 S 0).
Note that the proof also applies to the final output A(D) + wi- And hence to prove Theorem 3, it would be enough to show that.
Pr
(2 00 -I())
In the later analysis, we will focus on the update process wy (2).. We will prove the following lemma:
Lemma 8. Let X be distributed /v(
7 with 0² = 0
c
C²
have
T Pr
Σ
(2)
(0)
20)
2 Pr(x Pr(X5O), 5).
Note that Lemma 8 would immediately imply the theorem by Chernoff's inequality. We then turn proving Lemma 8 below.
For (x, v) E D, we have
[1 [ (1) w(2) < <1} (-H, (f, E D1, {1 (-1w(11) + (2) < 1} (1,-1) if (x, E D_1.
Vul(u- x. v)
Let B, be the batch of users in iteration with B, = B, the averaged clipped gradient at each iteration will be
9x- = B
Σ
Tlip(we((u, x, C)
(2,y)EB,
1
min
1
Σ
(pw + we(() <1 (-M, -11) (11)-1))
B
V
(EnD)EBnnD
1
min
1,
C
Σ
1 1 1f-ww(1) + w(2) <1} (n, (p,-1) -1)
B
V +1
12

---

Published as a conference paper at ICLR 2024
Hence
(c(2)
1
C
min
1,
(1) (|B n Di (: + w2 < + 2-111 (- + +w(2) < 1))
BB
V
+1
1
C
2
min
1,
+
B
V +1
min
Vu²
Standard privacy analysis in DP-SGD (the setting of parameters in Algorithm 1 used in Bassily et al. (2019)) sets B 2 / 1} and adds Gaussian noise (N, o2)) with o²
STC log(1/)) to the averaged clipped gradient. Let N₂ denote the noise added at iteraction t, we nzg² have
(2+1(2) S (2) 17 min
1 +1
Hence have
C
(2( (
(2) +1
min
1
+ +N((2)
1r2 +
C
1-1 Σ N2(2)
tmin
Vn2
1=0
This implies:
T S
T 2
T-1 (T- 10
T Σ (2)
min
2 +1
T
Note that the right hand side a Gaussian distributed random variable with mean
n T+1 min
1, V and variance r? * Hence
3n2ga
Pr
(2) 50
T
T
+
C
4(T + 1)(2T + 1)C² log(1/0) =0)
< Pr
N
17
min
1,
u +1
3n?e²
C
16(2T + 1)C² log(1/0)
< Pr
N
min
1,
00
12
3(T + 1)n
This completes the proof of Lemma 8.
B MISSING PROOFS IN SECTION 5
B. PROOF OF LEMMA 3
Let E < (3/5) and let P 49 logg1//88
Let a
and 7())
log(2d33 ,, 2) log (d (24/222))/2,,) If 2 e vd (for a sufficiently large constant c), then
"A different privacy accounting method might give slightly improved result. But overall we will have SIC log(1/6) and our claim in Lemma won't change up to constant factors.
2 @
n²2
13

---

Published as a conference paper at ICLR 2024
by Theorem and Remark from Huang al. (2021), there exists p-zCDP algorithm that outputs á such that
(
11 - ill2 =
+(())) (
diam(D) D))log/)l/g/)
R n²
+
with probability at least - Let ((4) O ( diam(D) log(nd/()
R Hence, n
n
Blll All21 (-
[[f(()] 11-
f(C) + + f()))
$ S(C) + +2RG
where the first inequality follows by observing that both a and ş have norm most R. Setting S = कス yields,
d (L//nP)
diam(D) (o
2R
Ella - Alla) 5
V
+
n
n²
d
log(dn)
diam D) log(n5d)
2R
00
vp
n²
(Dam(D) (lgg)))))))))))) (oggg) (1/))
2R
S (V + llog(d)))
ne
n²
2R
diam
n2
where the last inequality follows based condition Note that n 2 c-7(1/n))V based on the assumption in the lemma. By (Kairouz et al., 2021, Lemma 4), this algorithm also (e/3, 8/3)- differentially private and hence the lemma.
B.2 PROOF OF LEMMA 4
Throughout the proof, assume j is fixed and prove the statement for any ý. Applying (Dick et al., 2023, Theorem 2) with = 0, b = R, privacy budget e/3, error probability Ç. a R/n² r 100 log n, yields that the output 7 satisfies the following: with probability at least 1 C. there exists r' such that
| + < n²
and there are at most log n + 6 log ç-R/n²
R 100 log log points with ||2; - All more
R than 7' and at least 100 log n 6 log n² points with ||,; - All less than r'. Let 7 = + n2 then J
satisfies the following: there are most 100 log + 9 log =² & points with ||:; Al]2 more than r and
at least 100 log log /" points with ||,; Áll greater than т. Let S be the set of points with norm larger than т. Let so be value we set later.
S|S]] = E s |
< E 100011s15 E[n1|s|2
S 8o + n Pr([S] 2 so).
Setting (= n/ and
100
log n +
24 log yields that
1 +
124
125
S <
log n S
log n.
72
14

---

Published as a conference paper at ICLR 2024
To prove the other result, let 51 be value which set later. Observe that
R
E
S
E
n
[
+
n²
R
|[fl|s| + 2B[
n²
R
M[max ||=; - 111221112201
+
n²
R
( + max || - M112 + n
Setting 81
100 log 24 log n yields that
2R
E[r] max ||; ~a/2
n²
B.3 PROOF LEMMA
For the augmented dataset D',
Σ (z: (1) -2)T
E, - nT²
T TEi (1. (1)
E x. iujt nppi nT (1)
nip nT( jt)
nr2
where 14 n2 E Zy. Hence we have (a))( S +D)) + rank(uuā rank(āpp T) + rank(Afī +2, where we use the fact that adding one column/row will at most increase the rank of matrix by one.
To prove the second result, note that by triangle inequality,
| 27 s ||w" ||2T + 16"11 Ir
S ||=0|127 - 16" IT,
where the second inequality follows from Lemma 5. We now bound the second term in the right hand side of the above equation. Observe that by Assumption 1, there exists and æy such that
w des + b0+ 2 0 and w xj + b O,
and hence
-w'x S b S -w" zjj
Hence,
w" (p - Hi) S b" + w² f S w" (ia - -I,);
Hence by Lemma 5,
|b¹ r = lb* + nr pil
< max w (fi xx4)
2DED
< I|w" l|2 max (1 - 1;:]12
(5)
2.ED
Combining the above two equations yield.
1|7 < || || + || ||a max (ā æ1)112
mED
|
1|a7 + |10* max [[ x;)ll2
2.D
Hence by Lemma 4
0 |2 < 1| ||0 ll2 max D.ED
(1
x2)ll2
2 R
< 21101112 Tee (1 22) +
n2
15

---

Published as a conference paper at ICLR 2024
B.4 PROOF OF LEMMA 7
T v > O. Hence Σ, 1 > 0, which implies E; || T > 0 and hence v E span(U (D"). Similar analysis from (D") to U (D") yields that span(U (D') (D"n(U(D")) and hence rank(M rank(M(("))
o E span(U(D'), then T E; s/
0 and hence E; x. "T
B.5 PROOF THEOREM
The proof of privacy guarantee follows directly from the composition theorem (Dwork al., 2014, Theorem 3.16). Note that for simplicity, we used composition theorem here. However in experi- ments, the recent technique of PLD accountant (Meiser & Mohammadi, 2018; Sommer al., 2019; Doroshenko et al., 2022) implemented in Google (2018) to compute privary paranters e and
We now focus on the utility guarantee.
Let 8" 8 9t be the empirical risk minimizers of D.D'.D" respectively. Let (D), M (D'). M(D)) be the design matrices datasets D, D, respectively. Due to feature-clipping. the gradient for any (x", E D" and 0, the gradient of E(h(0, (0)00,x)), v""" is upper bounded by
GI|z"|22 S V2GT.
Hence, by (Song et al., 2021a, Theorem 3. and Lemma 6,
Vrank log( (3/0)
[T prv: D") T,(0",, 22)
ne
Vrank(M) log(3/5)
s 10/2GT||0*11
(6)
ne
By Lemma and Equation 3,
B|r |0"||100*||211
w0|10'10
< 2 112 max (1 - x1) +
n²
112R
S 4 122iamm) D) +
n²
Substituting the above equation in equation 6 yields and taking expectation over D" yields
E[L(O" prv: - DD) = 60V2G110011 (diam D) Vrank(M)
R.
n2²
ME
Note ShangSong et al., 2021a, Theorem 3.1) states the bound in terms of empirical risk minimizer 6"* hut. the bound holds for any
16

---

Published as a conference paper at ICLR 2024
Let S be the set of samples which differ between D' and D By Lemma 6,
= B|L + + B| -
e(h(0" v.))).)) - e(h((0" 24)) Mi)
T2
EE
x B|L(0" D))] + E
1(h((0" ,x,'),)))) - -E(h(0" 2x)). va)
EES
"[L(6",D'))] +
Glh(6" ,x/) -110" at)1
iES
$ B[L(0" DDI E
Σ
G I 2411 + +100(T))
11
iE8
B| DD]] +
2G Σ
max Iw" (x) 20]1
T2
iES
1
< <E|L(0" D +
Σ iE
2G Iww 112 (Di + l1 - m2ll))
( B[L(0", .D']
2G
E
| 12 (diam(D) + |1 / p1l2))
n
LiES
2G w
E[ D')1 +
[E[[S]] A]] (diam(D) + || n1ll2ll
n
W 1^ BI D')] 250G log n Iww
ll
E ((diam(D) + 11 - 11112)1
B[L(0", D') + 250G log va ||ww"
12
2R
2diamm(D +
n
S LLL( (D)() + 500G log rall0* 1|2
22dia 2R
THE
n²
where (a) follows from Eq. (5), (b) follows from Lemma 5, (c) follows from Lemma 4, and (d)
follows from Lemma 3. We now bound in the other direction.
(B D")] = E[L(A" D')l + EE E
1
E(h(8 2²)), Un) E(h(0) xt), (()())p..=)))) vi)..
iES
Notice that if y: prv x!! < O. then y:0% pav
x S yrO
x. < 0. Hence,
E[L(AM pmr. D()] 2 E[L( prv: D')l + n2
E
Σ
e(h(0" prv. xz"'), E(h(0" fir: x1).
Seg 6t xx >0
1 E
> ELL(O% D')
E(h(O' press 22),
SE S:grew x
1 2 [T.. D')] [B(()(((0)))
2 EEL((" prv: D')l 125 log n (0))
ne where the last inequality follows from Lemma 4. Hence we have
2R EIT.(O D') T.(0",, D') < 500G log n 101101112 2diam ()) + n
125 log (00).
+
nCc
By Lemma 5, have E[ prv: D`)] L(0 D') (B(L(Opev D)1 L( D). This yields that
R n
(rank(M] log (3/8) + log n
co(0) ne
([ D)] - I((0, D) < cGI10*112 (diam(D) (D)
+
log n,
ne
17

---

Published as a conference paper at ICLR 2024
Algorithm 3 Modefied version of DPSGD with feature preprocessing (DPSGD-F"),
Input: Input: Dataset D = ((11,1) ) (22, y2)...., (In 3n } of n points; overall privacy budget E, 8; privacy budget for the preprocessing step F E (0, e); feature norm bound Cp: gradient clipping norm Cg: step size 7/. number of iterations T: batch size B.
I: Private mean estimation. Compute the noise multiplier of for the Gaussian mechanism with Ep and using analytical callibration for Gaussian mechanism Balle & Wang (2018), and com- pute
n
H; + N(0,orCyla))
2: Translate the features. Preprocess the dataset and obtain D = {(11, (4/n Hn)}, where
-
3: DPSGD with preprocessed features. Compute the privacy budget s' for the DPSGD phase using the PLD accountant in Google (2018) by setting (s, 6) as the overall privacy budget for the composition of both the mean estimation phase and DPSGD phase. Get an an approximate minimizer 6fm of L(A, D') using the DPSGD algorithm with privacy budget (5',8).
4: Return ppr (Wppr ) where Uprv 0prl1 d) and byr = 6nv [d + 1| N Uprv-
for a sufficient large constant c. The theorem follows by observing that for the minimum norm solution 8*, |10 ||2 Il..
C ADDITIONAL EXPERIMENT DETAILS.
In this section, we discuss the detailed implementation and parameter settings used in our experi- ments. We implement all algorithms and experiments using the open-source JAX (Bradbury et al., 2018) library, For privacy accounting, we use the PLD accountant implemented in Tensorflow Pri- vacy (Google, 2018). We first describe the implementation details of our experiments.
Feature normalization. For all three datasets, consider their normalzeed version, where we normalize the feature vectors to a fixed norm of C'p by the transformation below
CF
x
Tj
We treat Cp fixed constant, and hence this normalization step doesn't result in any privacy loss about the dataset.
Modifications to DPSGD-F. The version of DPSGD-F listed in Algorithm is mainly presented for ease strict theoretical analysis since existing analysis on DPSGD mainly assumse that the gradients are bounded and no clipping is needed during the DPSGD phase (Bassily et al., 2019; Feldman al., 2020; Bassily al., 2020; 2021b;a; Song et al., 2021b; Arora al., 2022). However, state-of-the-ar results from DPSGD usually uses the clipping version of DPSGD where gradient norm bound is assumed (De et al., 2022; Ghalebikesabi et al., 2023).
In our experiments, instead of directly implementing Algorithm 2, we perform the following modi- fications the experiments. The implemented version the algortihm described in Algorithm 3.
1. For the feature preprocessing step. when computing the mean, instead of using the adaptive algorithm Lemma 3, the algorithm directly applies Gaussian mechanism to the empirical mean since each feature is normalized to a fixed norm. We can use Gaussian mechanism for mean estimation since now the & sensitivity is bounded.
2. We skip the private quantile estimation and feature clipping step. Instead, only shift the features by the privately estimated mean and treat it as the input to the DPSGD phase. We then perform norm clipping on the gradients as in DPSGD.
18

---

Published as a conference paper at ICLR 2024
The privacy guarantee of Algorithm 3 directly follows from the of PLD accountant (Meiser & Mohammadi, 2018; Sommer et al., 2019).
Lemma 9. The oulput of Algorithm is (e, -'difffrrentialy private.
Each each combination of (ALGORITHM, e, DATASET), fix the clipping norm Ce be as suggested in De et al. (2022), and perform grid search over Cr, BATCH SIZE, LEARNING RATE, and NUMBER EPOCHS from the list below and report the best-achieved accuracy, similar De et al. (2022).
1. CF: 10, 100, 1000.
2. BATCH SIZE: 256, 512, 1024, 2048, 4096, 8192, 16384.
3. LEARNING RATE: 0.03125, 0.0625, 0.125, 0.25, 0.5, 1, 8, 16.
4. NUMBER OF EPOCHS: 20, 40, 80, 160, 320.
For DPSGD-F, we further add search dimension over the privacy budget Ey for the feature pre- processing step. And the list of candidates is chosen to be [0.02, 0.05, 0.1, 0.15, 0.2). In fact, for all experiments, the best accuracy achieved at either &r 0.02 or &r 0.05. This suggests that the feature preprocessing step actually doesn't 't use much of the privacy budget to improve the final accuracy.
Remark different concentration measures of the datasets. For the three considered datasets, below we compute a few distance measures that characterize how the dataset is concentrated, listed in Table 2. appears that compared diam(D); (D), E; ||ı;--1|| on the performance improvement from DPSGD-F compared DPSGD. The smaller 1 2ll2. the more improvement DPSGD-F has over DPSGD. This might be due to the fact that we are considering the gradient clipping version of DPSGD (Algorithm 3) instead of the feature clipping version (Algorithm 2) considered in the theoretical analysis. Better understanding of this phenomena an interesting future direction.
more indicative measure
n E, ||2
Table Different concentration measures of the datasets. Features in datasets are normalized to be of unit norm. μ denotes the mean of the dataset.
Dataset
diam (D)
max, || - Ml12
1 E,
11
1l/2
CIFAR- 100 (pretrained) i
1.56
0.77 1.10
0.9
MNIST
1.41
1.03
FMNIST
1.41
1.10
0.62
19


Reviews:
[{"review_id": "9hkvNC78Tc", "reviewer": "Reviewer_eA3j", "summary": "This paper proposes a differentially private SGD algorithm which pre-processes the features before gradient descent steps. It is shown that, in linear classification problems and under certain regimes of privacy parameters, the new algorithm converges to a solution with lower optimality gap that the standard mini-batch DP-SGD algorithm without feature pre-processing. The theoretical improvement is supported by numerical experiments on image data sets.", "questions": "Corresponding to the two points under \"Weaknesses\":\n\n* Does the claim that Theorem 1 improves over Lemma 1 require any condition on $\\text{rank}(M)$, $\\delta$, $n$, or other parameters?\n* What is the relationship, if any, between the benefit of feature pre-processing in linear classification and the \"importance of feature processing for differentially private linear optimization\" as the title says?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "* The paper's contribution is made very easy to understand by the side-by-side comparison between standard DP-SGD's optimality gap and the new algorithm's optimality gap. The paper is overall well-written.\n\n* The example on why DP-SGD's excess loss must scale with $R$ is simple yet effective.\n\n* There is an extensive set of numerical experiments supporting the theoretical results.", "weaknesses": "* On the improvement of Theorem 1 over Lemma 1, it appears that the comparison boils down to $\\text{diam}(D)\\sqrt{\\text{rank}(M)\\log(1/\\delta)} + R\\log n$ versus $R\\sqrt{\\text{rank}(M)\\log(1/\\delta)}$. While it is clear that, when the diameter is significantly smaller than $R$, the former's first term $\\text{diam}(D)\\sqrt{\\text{rank}(M)\\log(1/\\delta)}$ is dominated by $R\\sqrt{\\text{rank}(M)\\log(1/\\delta)}$, there is a lack of discussion on whether/why $R\\log n$ is also dominated by $R\\sqrt{\\text{rank}(M)\\log(1/\\delta)}$. The lower bound result, Theorem 2, did not address Theorem 1's second term scaling with $R\\log n$ either.\n\n* It is ambiguous whether the improvement afforded by feature pre-processing is specific to linear classification. The term \"linear optimization\" in the title and the sentence \" *even* for the simple case of linear classification ...\" in the abstract seem to suggest that there are reasons to believe the improvement can generalize to other settings. However, there is barely discussion of other settings in this paper. If there are reasons why feature pre-processing also improves over DP-SGD in other problems (or linear optimization in general), mentioning these reasons may significantly improve the paper's contribution.\n\n* A few minor points on writing: \n    * the phrase \"maximum norm of features\" in the abstract could be understood as \"$\\ell_\\infty$ norm of features\". It may help to say \"maximum Euclidean norm\" instead.\n    * The letter $G$ in Lemma 1 is quite far from the previous mention of $G$. It might help to define $G$ as the Lipschitz constant again in the theorem statement.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nFMPZgACqJ", "reviewer": "Reviewer_FnQ7", "summary": "This paper looks at the effect of feature pre-processing on the DP-SGD.\nSpecifically, they focus on the case of linear models and aim to show theoretically and empirically the impact of feature pre-processing.\nFirst, they give a counter-example to show the error of DP-SGD must be proportional to the maximum norm of the features.\nThen, they show that carefully pre-processing the features by subtracting the mean and shifting the bias by a private quantile estimation can reduce the error to be proportional to the dimension of the dataset.\nThe experiments show a clear improvement in accuracy while spending a minimal privacy budget on the feature pre-processing.", "questions": "Can the authors comment on the normalization issue?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper gives strong theoretical and empirical support for feature processing, a topic previously only reasoned about empirically. \n- The privacy utility trade-off is a significant roadblock in the adoption of DP-SGD, and this paper gives a simple solution to improve this trade-off and give a nice increase in accuracy.\n- The paper is very well written.", "weaknesses": "## Theory does not match experiments\nThe algorithm is significantly modified for the experiment section. It was clear that the algorithm analyzed was designed to make the theory work, and components were dropped or simplified for the experiments.\n\nThe part I am concerned about is the normalization of the features before computing the mean. The reason is that the normalization must be carried out in a private manner to allow for bounded sensitivity. The current version seems to assume a normalized dataset without accounting for any privacy budget to carry out the normalization. \n\n### Note\nI was unable to verify the proofs in this paper due to my lack of theoretical background. I apologize that I leave this verification to my fellow reviewers.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7lYchJGe7f", "reviewer": "Reviewer_m2H3", "summary": "The paper investigated the significance of feature processing in differentially private linear models. The authors introduced an algorithm named DPSGD-F, which incorporates a preprocessing procedure for feature clipping within DP-SGD. The authors theoretically demonstrated the relationship between the excess risk and the feature diameter. Furthermore, their empirical results suggested that DPSGD-F outperforms DP-SGD on datasets such as MNIST, FMNIST, and CIFAR-100 (pretrained).", "questions": "Please reference the weakness section.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Strengths:\n\n1. The authors introduced a novel variant of DPSGD known as DPSGD-F, which empirically outperforms DPSGD on particular datasets, and they supported the proposed algorithm with theoretical guarantees.\n\n2. The authors presented a counterexample illustrating situations where DP-SGD does not converge.", "weaknesses": "Weaknesses:\n\n1. I have several concerns regarding the motivation and theoretical results, which might undermine the paper's conclusion.  Below are some of my concerns about the counter example in Section 4 and Theorem 1 in Section 3.\n\n    a) In the counterexample, the condition $\\mu > n\\epsilon$ is required. However, if I understand Theorem 1 correctly, the second term in Theorem 1 becomes a constant when $\\mu > n\\epsilon$ since $R = \\sqrt{\\mu^2 + 1}$. Consequently, this counterexample may not convincingly imply that DPSGD-F is superior to DPSGD. It is recommended to address this concern during the rebuttal session.\n\n    b) The authors use this counterexample to emphasize the importance of feature diameter. Nevertheless, it appears that it's the angle between features for different classes, rather than the diameter itself, that is crucial. Particularly, when $\\mu$ is sufficiently large, the features for different classes become nearly identical because, in comparison to $\\mu e_1$, $e_2$ can be neglected. To make the counter example more convincing, please consider whether the example $x = e_1 + \\frac{1}{\\mu} e_2$ for $y=1$ and $x = e_1 - \\frac{1}{\\mu} e_2$ for $y=-1$ remains consistent when $\\mu$ is sufficiently large.\n\n    c) The upper bound in Theorem 1 is dimension-dependent since the authors required that $n\\geq O(\\sqrt{d}/\\epsilon).\n\n2. Given that the counterexample doesn't fully convince the reviewer, it is recommended that the authors conduct an empirical evaluation of DPSGD-F on a wider range of datasets. Specifically, it would be beneficial to compare the results with Table 1 in De et al.'s work (https://arxiv.org/pdf/2204.13650.pdf) using various choices of pretrained and finetuned datasets for further validation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "UVNjPIwhI8", "reviewer": "Reviewer_4bdB", "summary": "Differential privacy (DP) has been applied to many machine/deep learning tasks to keep privacy of dataset. DPSGD is one of the influential work to train private ML models. Although some theoretical works proves its convexity properties and leads the trend, DPSGD may not work well on raw features in image classification tasks. Beyond the DPSGD, this work demonstrates the feature preprocessing is necessary to optimize the performance of DPSGD by proposing a new algorithm - DPSGD-F as a combination of DPSGD and feature preprocessing.", "questions": "1. What is Omega tilde in Theorem 1?\n2. Can you explain more about what the “uninformative” means in the Theorem 3?\n3. For lemmas in Section 5, can you provide high level ideas of proofing for each one (probably one or two sentence per lemma) like you did in the Section 4 to make reader clearer about the correctness?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. Based on the proposed algorithm, this work does not only provide empirical results on specific image tasks, but it also provides theoretical guarantees on it step by step. It is really good to connect theory and practice in the research.\n2. The counter-example of DPSGD in Section 4 is innovative and looks solid to investigates its limitation seldom considered by other works (to my knowledge).", "weaknesses": "1. The study subject - linear model - is relatively simple and less representative compared to SOTA ML models, especially for image classification task.\n2. Except the Fashion-MNIST dataset (released in recent few years), original MNIST and CIFAR-100 datasets are relatively outdated compared to other image datasets.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)