Differentially private optimization for non-decomposable objective functions
Authors: Weiwei Kong
Andres Munoz medina
Mónica Ribero
Venue: ICLR 2025 Poster (2025)
Keywords: Differential privacy
private learning
contrastive learning.
Primary area: alignment, fairness, safety, privacy, and societal considerations
TL;DR: We introduce a differentially private optimization algorithm for common loss functions that do not decompose as per-example loss (such as similarity based loss functions) that outperforms previous approaches.

Abstract: Unsupervised pre-training is a common step in developing computer vision models and large language models. In this setting, the absence of labels requires the use of similarity-based loss functions, such as the contrastive loss, that favor minimizing the distance between similar inputs and maximizing the distance between distinct inputs. As privacy concerns mount, training these models using differential privacy has become more important. However, due to how inputs are generated for these losses, one of their undesirable properties is that their $L_2$ sensitivity grows with the batch size. This property is particularly disadvantageous for differentially private training methods, such as DP-SGD. To overcome this issue, we develop a new DP-SGD variant for similarity based loss functions --- in particular, the commonly-used contrastive loss --- that manipulates gradients of the objective function in a novel way to obtain a sensitivity of the summed gradient that is $O(1)$ for batch size $n$.  We test our DP-SGD variant on some CIFAR-10 pre-training and CIFAR-100 finetuning tasks and show that, in both tasks, our method's performance comes close to that of a non-private model and generally outperforms DP-SGD applied directly to the contrastive loss.

Published as a conference paper at ICLR 2025
DIFFERENTIALLY PRIVATE OPTIMIZATION FOR NON- DECOMPOSABLE OBJECTIVE FUNCTIONS
Weiwei Kong, Andrés Muñoz Medina & Mónica Ribero Google Research New York, NY, USA [we deeieeiknn,, ammedina, mmribero@@google.com
ABSTRACT
Unsupervised pre-training is common step in developing computer vision mod- els and large language models. In this setting, the absence of labels requires the use of similarity-based loss functions, such contrastive loss, that favor mini- mizing the distance between similar inputs and maximizing the distance between distinct inputs. As privacy concerns mount, training these models using differen- tial privacy has become more important. However, due to how inputs are gener- ated for these losses, one of their undesirable properties is that their L2 sensitivity grows with the batch size. This property is particularly vintavauts for dif- ferentially private training methods, such DP-SGD. To overcome this issue, we develop new DP-SGD variant for similarity based loss functions - in particular, the commonly-use
contrastive loss that manipulates gradients the objective function in novel way to obtain sensitivity of the summed gradient that is (1) for batch size n. We test our DP-SGD variant on some CIFAR- 10 pre-training and CIFAR- finetuning tasks and show that, in both tasks, our method's 's per- formance comes close that of a non non-private model and generally outperforms DP-SGD applied directly to the contrastive loss.
INTRODUCTION
Foundation models - large models trained in unsupervised manner to be fine-tuned on specific tasks have become one of the cornerstones of modern machine learning. These models generally outperform other approaches in multiple tasks, ranging from language generation, to image classi- fication and speech recognition. In fact, models such as LaMDA (Thoppilan et al., 2022), BERT (Devlin et al., 2019), GPT (Radford et al., 2018) and diffusion models (Saharia et al., 2022; mid- journey) interact with millions of users per day. Due to the complexity of these models, there are multiple concerns in the privacy community that these models may memorize some of the training data. For models trained on user-generated content, this may result in a catastrophic privacy breach, where the model may unintentionally reveal private information about user. Recent work from Shokri et al. (2017) and Balle et al. (2022) showed that these risks are not just theoretical concern and that it is possible to know whether a particular example was in dataset for training the model and (ii) reconstruct training data using only black-box access to the model.
Differential privacy provides an theoorici guarantee that the model does not depend drastically on any example (Dwork et al., 2006) and the aforementioned work also showed that these attacks become significantly harder when models are trained using differential privacy.
Consequently, private training methods have received considerable attention from the privacy com- munity the past decade. Some of the foundational work on this area was established by Chaudhuri et al. 12 which provided algorithms for private learning with convex loss functions and Abadi et al. (2016) which proposed the differentially private stochastic gradient descent (DP-SGD) algo- rithm for privately training neural networks. Multiple lines of work have stemmed from this research area, ranging from tighter privacy analysis (Ghazi et al., 2022) to more efficient implementations of DP-SGD (Li et al., 2021). However, most of the literature on private machine learning makes one crucial assumption about the objective function they are trying to minimize: the objective decom- poses sum (or average) of example level losses. This assumption drastically simplifies the

---

Published as a conference paper at ICLR 2025
sensitivity analysis (how the objective changes changes point in the dataset) of DP-SGD algorithm.
In this work, focus models that are trained using non-decomposable objective functions. That is, a function that cannot be described as sum (or average) individual losses. Our study is motivated by the use of contrastive losses (Oord et al., 2018; Chen al., 2020a;b) for pre-training foundation models. Contrastive losses generally compare each example against all other examples in the batch and adding or removing example function in unpredictable ways. This type of behavior generally makes it hard, if not impossible, train models privately. In this work, we show that common non non-eecomposable losses have crucial property that makes them amenable to private training. Our contributions are summarized as follows:
batch of examples can affect the objective
We provide general framework for measuring the sensitivity of DP-SGD for certain decomposable losses.
We show how to apply this framework to two common non-decomposable losses: con- trastive loss and spreadout (regularization) loss (Zhang al., 2017).
We conduct experiments on privately pre-training large image classification models (a generic embedding model and Resnet18) and show that we can achieve performance com- parable to non-prioe non-private pre-training. Our experiments analyze the performance simple pre-training as well as fine tuning on downstream task.
2 PRELIMINARIES
Notation. Denote [n] : (1, (1,...,1)) IR to be the set of real numbers, and Rd R where the Cartesian product is taken times.
Given feature space X', such as space of images sentences, focus unsupervised learning of embedding models Qn. X' + Rd parametrized by w E W where W is a parameter space W C RP.
Let X = +() C C''x x A' be batch with n records, such that x; and x are similar (positive pairs) in the feature space. These positive pairs can correspond, for instance, two version of the same image, sentence and its translation on different language or an image and its caption. Let be function measuring similarity of two points in Rd common objective is to find parameter w E W that preserves the similarities defined by pairs in X.
S: IRd x Rd
Given vectors 21...., Fn E Rd, define x (.1,..., Fn)) and denote their embeddings as pw (I (x1)........... (I.)).
Given embeddings u, U1, U/ .......U Rd. define the similarity profile of respect to Ui.... Uyn for S the vector (mm v) of similarities between u and the first m vectors in v. Formally, (u, v) E R where entry j E [m] is defined (S e)); S(u, 0y). common similarity mmth
function is the cosine similarity given by
S coss
(u, v)ls
Vj E [n].
Given a dataset X = ((xi, ) and family of loss functions ((),n) R + R that calculate the loss the similarity profile of point x, based the n points batch X, define
z( (im)
(w) = (d,w I Pw .... (x.)))
x (w) = g(im)) (1.N) (w),
(im)
(1)
Lx (x( = Σ LX (bm)
for E [n]. The similarity terms z (1.m)) (w).... z(n.n) (w) IR" are commonly referred to as con- trastive logits. Given 7) 0, contrastive loss models, which aim to minimize Lx (w), are typically
2

---

Published as a conference paper at ICLR 2025
trained iteratively using stochastic gradient descent (SGD) follows:
W/ = -
Organization. The rest of this section reviews some key concepts used to develop our proposed scheme. Section 3 reviews related works. Section 4 gives the main technical results and the proposed scheme that implements DP-SGD for general contrastive losses. For brevity, we leave the proof of these results for the Appendix at the end of this paper. Section 5 presents numerical experiments on CIFAR 10 and CIFAR I00, as well as a brief discussion on numerical bottlenecks. Finally, Section gives few concluding remarks.
2.1 DIFFERENTIAL PRIVACY
Let 2 denote arbitrary space and let D (21,..., 2 denote dataset. We say that datasets
D and D' are neighbors if DU {2++1} for some 2n+1 E Z. A mechanism M: - - O is a randomized function mapping dataset some arbitrary output space O. Let e, 6 0. We say that mechanism M is (e, 8) ))diffferentiall private (Dwork et al., 2006) if for all neighboring datasets D, D' and all S C O the following inequality holds;
P(M(D) E Se P(M((D)) E S 6
A simple way of ensuring that mechanism is differentially private is by using the following process. Definition 2.1 (Gaussian Mechanism). Let e, 5 > O and J: Z" + Rd,, and denote A2( (Df f(2')l2 be the Lz-sensitivity of the function f. For & NN),,)) the mechanism defined by
M(D) = J(D) + A2(S),
(c, ddifferrret private for an appropriate' choice of
Our primary goal in this paper is to implement Gaussian mechanism for the function X + VLx(w) where Lx (w) is as in (1).
2.2 LOSS FUNCTIONS
Definition 2.2 (Canonical contrastive loss). The (canonical) contrastive loss function is given by (w) in (1) with (()))()) log(e E
The above loss essentially treats the unsupervised learning problem classification problem with classes, where the pair (x;,x() has a positive label and (I;;, has a negative label for all j + i.
Contrastive loss is widely used by the vision community (Oord al., 2018; Chen et al., 2020a;b; Radford et al., 2021) and has been shown to be extremely successful at obtaining pre-trained models for image classification.
Definition 2.3 (Spreadout regularizer loss). The spreadout regularizer loss is given by Lx(w) in (1) with g(f.)) (Z) Ejts Z3/(r 1).
The spreadout regularizer commonly used when training embedding models for computer vision (Zhang et al., 2017; Yu et al., 2020). used as a method to promote orthogonality in the embedding space among dissimilar objects the whole feature space.
Definition 2.4 (Summed loss from per-example loss). Lei Z = ((11))) y........................ (Iis Un)) be dataset of features and label pairs. Given a set of per-example loss functions ( ) corresponding to the examples in Z, the summed loss function is Kz(w)= = =E= (w)
2.3 NAIVE CLIPPING SCHEMES
Before presenting our scheme, we discuss some naive approaches for bounding the sensitivity of contrastive loss gradients during DP-SGD training.
See, for example, Balle Wang (2018).
3

---

Published as a conference paper at ICLR 2025
We first review how DP-SGD is typically applied for the summed loss (Kz(w) in (2.4). It can be shown that the precise Le-sensitivity of (Kz(w) in DP-SGD is generally hard to estimate in deep learning settings (Latorre et al., 2020; Shi et al., 2022). As a consequence, for given a L2- sensitivity bound B on VKz(w)) practitioners usually clip the per-example gradients V.2g(") by the bound B and apply the Gaussian mechanism differentially private (DP) gradient that is passed to DP-SGD. This is motivated by the fact that adding or removing an example from the dataset Z will not change the norm of the DP gradient (and, hence, its sensitivity) by more than B. Also, notice that the standard deviation of the Gaussian mechanism's 's noise is Bo which is independent of the sample size n.
the sum of the clipped gradients to obtain the
Let us now compare the above results with the Ly-sensitivity of a similar scheme for contrastive loss functions Lx (w) as (1). For neighboring datasets X {(1,, af)) and X +())) the sensitivity of Lx (w) is given by
|VVxx (w) (w))ll)]l
V (n.
(w)
V (ia) 1i
where ((:7)) (w) is as in (1). Similar to the per-example loss, for a given L--sesiitivtyy bound B, we could consider clipping the "per-example" gradient terms {V L (6.m) (w))²= (for DP-SGD on dataset X) and ( (0-=)))))) [w)) (for DP-SGD on dataset X²) by B and applying the appropriate Gaus- sian mechanism. However, applying the triangle inequality to the bound in (2), the Lz-sensitivity of the resulting scheme is On.B). As consequence, the standard deviation of the Gaussian mecha- nism's 's noise is (n) which is ((n) worse than for per-example losses.
As another alternative (Huai et al., 2020; Kang et al., 2021), one could directly clip VLx (wx) or VLx (w)) by B and apply the Gaussian mechanism to these clipped gradients with standard deviation of O (see (2)). However, we show in our experiments section that this approach, nicknamed Naive-DP, does not materially reduce the value Lx (w), even when varying the batch size or the clip norm value.
Our proposed scheme aims to provide the first DP-SGD scheme which materially reduces the loss value (x( without requiring a dependence on the batch size n in the underlying Gaussian mechanism's noise.
RELATED WORK
Contrastive learning has had large impact on unsupervised pretraining of computer vision models (Chen et al., 2020a;b) and representation learning for language models (Logeswaran & Lee, 2018; Chidambaram et al., 2018), or both (Radford et al., 2021). Fang et al. (2020); Giorgi et al. (2020); Wu et al. (2020) use contrastive loss function for pre-training and fine-tuning BERT with data augmentation. More recently it has been used for reinforcement learning with BERT-type models (Banino et al., 2021).
In the private setting, the majority of the work has been focused on improving the original implemen- lation of DP-SGD (Abadi et al., 2016) for decomposable losses. Research has particularly focused on tighter privacy guarantees on DP-SGD via advanced privacy accounting methods (Mironov, 2017; Ghazi et al., 2022) or solving computational issues, for example associated with gradient clipping (Goodfellow, 2015), or improving a specific models efficiency and scalability such as privately pre- training T5 (Ponomareva al., 2022). For non-decomposable losses, some researchers have studied private learning from pairwise losses in the convex and strongly convex case (Huai et al., 2020; Xue et al., 2021) and test only in a diabetes dataset. Later works (Yang et al., 2021; Kang et al., 2021) obtain similar results for the non-convex case; these approaches circumvent clipping by assuming access to the Lipschitz constant of the loss function, which depends on the encoder function (typ- ically deep neural network). However, this Lipschitz constant is generally not easy estimate (Latorre et al., 2020; Shi et al., 2022).
Xu al. (2022) learn private image embeddings with user-level differential privacy, but avoid un- supervised training and, consequently, avoid non-decomposable loss functions such as contrastive and triplet loss. Instead, this work relays a supervised multi-class classification problem, and avoids
4

---

Published as a conference paper at ICLR 2025
dependencies among different records, at the cost of labeling the data. Similarly, Yu al. (2023) train ViP, a foundation model for computer vision but replace the contrastive (non-dccomposable loss with instanco-separable loss. Li et al. (2022) propose noising the similarity matrix between pairs of inputs and compute a noisy loss function. They combine this with a noisy gradient but assume per-gradient bounded sensitivity.
Orthogonal works study attacks to embedding models. For instance Song Raghunathan (2020) showed that when trained without differential privacy, embedding models can be inverted. More specifically, model attacks are able to recover members from the training set when the attack are designed to recover information from embeddings trained with contrastive loss (Liu et al., 2021). To prevent specific attacks Rezaeifar et al. (2022) developed an architecture that learns an obfuscator that prevents reconstruction or attribute inference attacks. He & Zhang (2021) quantifies the expo- sure risk under contrastive learning losses and develops an adversarial training procedure to mitigate the risk. However, none of these approaches provide differential privacy guarantees. Finally, Wu et al. (2022) explores contrastive learning in federated settings, where users feed user-embedding: the negative samples are created at the server with the differentially private embeddings sent by the users.
4 BOUNDING PAIRWISE-CONTRIIUTION
This section first introduces condition on the family of loss functions {g(5,)) } that, when combined with a clipping operation on the gradient of the similarity between each pair of records, permits the derivation of DP-SGD variant that benefits from increasing the batch size when using similarity based loss functions.
We start by deriving expression for the gradient of L in Lemma 4.1 that highlights the dependence on the gradient of pairwise similarity values S( (z:), (x'g)) By leveraging this decomposition, find a bound
the overall loss L gradient's sensitivity in Theorem 4.2. Finally, combine these two facts to produce a differentially private optimization algorithm for similarity based loss functions. We defer proofs to the supplementary material.
4.1 COMPUTING GRADIENT SENSITIVITY
Lemma 4.1 below shows that the gradient of a similarity based loss function can by expressed in terms of the pairwise similarity gradients (( (x(()
Lemma 4.1. Let Cx(w) and (() (w) be as (1), and denote
(w) z((m)) (w), (w),
(w) = 12 (hm)) (w)l) (2x), P- (z))).
Then,
v= = Oglia) (Z:(w)
V (w).
az%
We describe conditions the family (f(bm)) function that allow to derive bound on the Le-sensitivity of V V (w).
Theorem 4.2. Let Lx (w) and Z be as in Lemma 4.1, let C R be compact set, and let z' E Cn-11 Rm E C, and z (n) E C". Assume that for all i E [ni] the family of functions
(g(im) (iN))NNN satisfies
(z) Öz,
(eli
n
aglive
n Σ
(c(
L,
Σ j=1
< G1,
< G2,
(4)
Oz,
Ozj
Ozm
where L, Gr, and G2 can depend n. If 1 ||2 S B for every i and j. then the Lo La-sensitivity of x (w) can be bounded as
A2(x
(G G2 (n 1)L)
5

---

Published as a conference paper at ICLR 2025
We now ready to present main algorithm. Before proceeding, the following two corollaries show that one can obtain a private estimate of the gradient of the training loss by clipping the pairwise similarity gradients and applying Gaussian mechanism.
Corollary 4.3. Let B > O, 2 E Rd, Cx [x(w) and z be as in Lemma 4.1, and let Clip (x) == min [B/[|=]|, 1) x denote the vector clipped to have norm at most B. If the family of functtoos {(85)) R-11 satisfy the conditions of Theorem 4.2. Then, the function
)l (2,(w))
X
Clipg ( (w))
(5)
az
has L2 sensitivity bounded by (G1 + G2 (n 1)
Corollary 4.4. family of loss functions g(t.m)) satisfies the conditions of Theorem 4.2, then each iteration of Algorithm satisfies (c, -..-fffferetti privacy? for /log(1.25/8))/
Proof. The proof is immediate since each step of the algorithm corresponds to the Gaussian mech- anism with noise calibrated to the sensitivity of the mechanism.
Moreover, in the following lemmas, we present how condition (4) holds with L = O(1/n) for the contrastive and spreadout regularizer losses under cosine similarity. Consequently, this ensures that the Le-sesiitivity given by (2) is independent of n.
Lemma 4.5. (Contrastive loss) Let g65,) be in Definition 2.2 with S S Then glim))
satisfies the conditions of Theorem 4.2 with
(n 2)e²
G ( (1+
(6)
c2 2 (n 10111
Lemma 4.6. (Spreadout loss) Let g(im)) be as in Definition 2.3 with Sth S cast Then ((.m) satisfies the conditions of Theorem 4.2 with G + G2 + (n - 1)L < 6.
4.2 MAIN ALGORITHM
We present Log our proposed DP-SGD scheme in Algorithm 1. The algorithm specifically receives batch size n, learning rate (or schedule) 17, number of iterations T, constants G G2. and I, defined in Theorem 4.2, and the similarity gradient clip norm B. It then computes the sensitivity of the overall gradient C (line 2).
The algorithm proceeds to the training loop where, at each iteration f, it samples batch of size n. Then, instead of per-example gradients, it computes similarity gradients gi (line 6), clips all gi vectors to obtain a bounded gradients Pij. and computes an approximate gradient for L using (5) (line 9). Finally, it applies noise (line 9) and updates the model (line 10).
While algorithm 1 uses SGD the gradient step, the model update in line 10 can be passed to other gradient based optimizers such as Adagrad (McMahan Streeter, 2010; Duchi et al., 2011) or Adam (Kingma, 2014) 4). Remark that all previous work privacy accounting for DP-SGD also applies to our algorithm as each iteration simply generates a private version of the gradient of the batch loss.
NUMERICAL EXPERIMENTS
This section presents numerical experiments that compare the practical viability of our proposed DP-SGD variant (Logit-DP), the implementation of DP-SGD (Naive-DP) which clips the aggre- gated gradient the batch level, and non-private SGD (Non-Private). Specifically, we examine several training and testing metrics pre-training and fine-tuning tasks applied to the CIFARI0 and CIFARI00 datasets using a generic embedding net model and a ResNet18 model without batch
A slightly tighter relation between o and can be given using the results on the analytic Gaussian mecha- nism of Balle & Wang (2018). 8).

---

Published as a conference paper at ICLR 2025
Algorithm 1: Logit-DP
Input: Sensitivity bound B > sensitivity constants G1. G2, 0, dataset
D a batch size n, iteration limit T 2 1, stepsize > 0, noise multiplier
o 0, model
Output: Embedding model Pwr
Initialize weights wo in Φ;
Compute gradient sensitivity C = (G1 G2 +nL)
for t t= 1.2.... T 1 do
Sample batch X (01, (Ins =2/]];
for i,j = ...,,,? do
Compute similarity gradients V V (w;) = V w. S( (zi), Sw.( (2z));
Clip gradients obtain Clipg VZ min [1 VZ
B
end
Compute I using (5) Compute noisy gradient ğ - 9 + Y with Y ~ (O, xC1)):
10
Update the model W++1 = W, 79:
end
normalization layers, their standard implementation isn't privacy-preserving: in table 3 in the ap- pendix we show the effect removing these layers. All DP methods chose a noise multiplier so that e-DP is achieved for 5.0. The details of the embedding models, the hyperparameters of the each variants, and the training setups for each task are given in the supplementary material. Our code is publicly available at https: / higghuu.......g/ggg com/ /oogle weweeeeeeeeeehheeeeeeeeeeeeeeeee egooeaccchoogeeeeeeeeeeoooooooee wtt.:/ooeoooeeeerrrrt.eee t tree/ master/ logit_ds
The last subsection describes strategies manage memory requirements encountered as training scales to larger models and datasets.
5.1 PRE-TRAINING ON CIFARI0
In these experiments, all DP-SGD and SGD variants were given model Φ, which was either generic embedding model ResNet18 model without batch normalization layers. Each variant was tasked with minimizing the contrastive loss described in Example 2.2 for the examples in the CIFARIO 10 dataset. For testing/evaluation metries. we examined the quality of the embedding model under k-nearest neighbors (k-NN) classifier for 3.
Figure presents the observed (relative) training loss values over the number of examples seen so far for ten different training runs using the generic embedding model and the effect of batch size on Naive-DP. In particular, the plot in Figure demonstrates that Naive-DP's loss value mostly unchanged for large batch sizes and noisy for small batch sizes. Table I presents the relative averaged test metrics at the last evaluation point.
Similar trends to Figure were observed for the ResNet18 model.
Table I: Relative aggregate CIFARIO test metries generated by the confusion matrix C at the last test point over ten runs. Each aggregate metric divided by the corresponding one Roi-Private. Aggregate accuracy defined as >, Cu/ En,, Ci averaged over all runs. The recall, precision, and F3 scores are the average of the best observed metric over all ten CIFARIO classes.
Embedding Net Metrics
ResNet18 Metries
Accuracy
Recall
Precision
Fg Score
Accuracy
Recall
Precision
Fg Score
Logit-DP 0.819
0.855
0.812
0.831
0.730
0.871
0.695
0.768
Naive-DP
0.827
0.827
0.812
0.820
0.599
0.672
0.699
0.685
Non-private 1.000
1.000
1.000
1.000
1.000
1.000
1.000
1.000
For additional reference, have the following figures and tables in the supplementary material. Each variant's confusion matrices at the last evaluation point are in Figures 3-4. The (absolute) means and standard deviations of the test metries at the last evaluation point are in Table 3. Finally,

---

Published as a conference paper at ICLR 2025
Relative Contrastive Loss Values
Relative Cross- Cross-Entropy Loss Values
Reletive Loss Value
1.08
Relative Loss Value
1.06
1.0
1.04
0.8
1.02
0.6
Number of Examples (in thousands)
10
15
30
35
Number of Exampies (in thousainds)
Logit-DP
Naive-Do
Non-Private
1000
10003
Figure 1: (Left) Relative CIFARIO training loss over ten runs. Relative loss is defined as the observed training loss divided by the minimum loss observed across all runs and all variants, Shaded regions bound the observed loss values over the runs, while the the dark lines represent the average relative loss observed far. (Right) Single runs Naive-DP with the same settings as the left graph but with different batch sizes The n 1000 and n 10000 form mostly overalapping lines.
the relative training loss over runtime and the training speed over number of examples seen is given in Figure 5.
5.2 FINE-TUNING ON CIFAR 100
Pre rre-trained foundational models are often non non-privee con--iiivtlly fine-tuned on classification tasks for local use and, consequently, are not required to be privately optimized. In these experiments, we test the ability of the privately pre-trained embedding model adapt new tasks. All variants were given the generic embedding model + from Subsection 5.1 and multilayer fully-connected model V.. They were then tasked with non-privately minimizing the cross-entropy loss generated by the com- bined model 4 V on the CIFAR 100 dataset to predict the coarse label of the input (20 categories), under the condition that the weights in & were frozen, i.c., could not be updated.
Relative Cross-Entropy Loss Values
1.20
Relative Loss Value
1.15
1.05
1.00
500
Number Examples (in thousands)
Logit-Di DP
Naive DP
Non Private
Figure 2:
Relative CIFAR100 training loss for single run. Relative loss is defined as the observed training loss loss observed across all variants. Lightly colored lines are the true loss values, while
divided by the minimum the dark lines smoothed loss values generated by third-order Savitzky- Golayyy-GGyaaaa filter with sliding window 100 observations.
For reference, we present each variant's (absolute) test metrics - at the last evaluation point in Table 4 of the supplementary material.
5.3 MEMORY BOTTLENECK AND POTENTIAL FIX
In our implementation of Logit-DP (Algorithm 1), computational bottleneck was the materializa- tion of the n² logit gradients (gij in Algorithm 1) for a batch n examples, which were needed to compute the final aggregated gradient (g in Algorithm 1). A potential solution is to compute gra-
8

---

Published as a conference paper at ICLR 2025
Table Relative CIFAR100 test metrics generated by the confusion matrix C. the last test point run. Each metric divided by the corresponding one non while top recall, precision, and F3 scores are the best observed metric over all CIFAR 1000 classes.
non- private SGD, Accuracy defined as E, Ca/ Ei, Co
Embedding Net Metrics
Accuracy
Recall
Precision
Fg Score
Logit-DP
1.013
0.969
0,954
0,981
Naive-DP
0.946
1.296
0.665
0.911
Non-private
1,000
1.000
1,000
1.000
dients Púy sequentially. While addressing the memory bottleneck, this solution is computationally inefficient in terms of runtime.
Below, we describe an alternative approach for computing 9 and argue that more efficient for certain choices ...- Consider the function
(x = ΣΣ (w(l))
==1
where Aay are fixed, realev weights given by
dg(s.n)
aZ (S" (S" m (2ra), T (xff))) A=== Ty min {
B
Tij
Vi,
and note that 9 VFx (w) (ef. (5)). In view of the previous identity, an alternative approach to computing ğ is to first compute each Ady and then compute VFx(w).
This new approach has the following advantages: (i) given Aij. the memory and runtime cost of computing the gradient of Fx (w) is on the same order of magnitude as computing the gradient of [(w, X) = Σi=1 g(t.n) (I (x;), P (xx))) when both methods employ backpropagation, (ii) the memory cost of storing the weights Aig is only On22), and (iii) the costs of computing the weights Xı requires only computing the n² scalar pairs (Tij- (1 II) rather than computing the n? gradients 9iz of size |w| as in Algorithm 1.
The last advantage is of particular interest, as there are well-known methods Goodfellow (2015); Lee & Kifer (2020); Rochette et al. (2019) in the literature efficiently computing the norms |1 without materializing each Oiy- For example, some of these methods decompose Pij into a low-rank representation Pij U. VJ for low-rank matrices U2 and Vij, and then exploit the identity
11 2| = |1 VJ12 (UJUU V.).))
When Ui and Vy are column vectors, the last expression above reduces can be substantially more efficient than first materializing Pij = Uis VT and then computing [Ia correct implementation of this technique far from trivial, and leave this future research.
11,, which
CONCLUDING REMARKS
As observed in Section 3, naive implementations DP-SGD for similarity- losses are in- effective because the standard deviation of the noise in the Gaussian mechanism grows with n. Experiments in the previous section show that even with careful hyperparameter tuning, the loss remains nearly constant during pre-training. These results are even more pronounced for Resnet18. 8,, when the number of model parameters large. Fine-tuned models using Naive-DP also perform less effectively compared to both the non-private baseline and the Logit-DP algorithm.
Careful analysis these losses and their decomposition shows that by clipping logit gradients, Logit-DP obtains sensitivity that is constant on the batch size, considerably reducing the magnitude
of the noise added to privatize the gradient. These insights expand the suite of tasks that can be trained in privacy preserving way with only marginal drops in accuracy. Work more efficient implementations these algorithms is an interesting avenue of future work and we introduced several concrete ideas the end of the previous section.

---

Published as a conference paper at ICLR 2025
REFERENCES
Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, llya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. Conference on Computer and Communica- tions Security (SIGSAC), 2016.
Borja Balle and Yu-Xiang Wang. Improving the Gaussian mechanism for differential privacy: An- alytical calibration and optimal denoising. In International Conference on Machine Learning (ICML), 2018.
Borja Balle, Giovanni Cherubin, and Jamie Hayes, Reconstructing training data with informed adversaries. In 2022 IEEE Symposium on Security and Privacy (SP). IEEE, 2022.
Andrea Banino, Adrià Puidomenech Badia, Jacob Walker, Tim Scholtes, Jovana Mitrovic, and Charles Blundell. Coberl: Contrastive bert for reinforcement learning. arXiv preprint
arXiv:2107.05431, 2021.
Kamalika Chaudhuri, Claire Monteleoni, and Anand D Sarwate. Differentially private empirical risk minimization. Journal of Machine Learning Research, 2011.
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. In International Conference on Machine Learning (ICML), 2020a.
Ting Chen, Simon Kornblith, Kevin Swersky, Mohammad Norouzi, and Geoffrey E Hinton. Big self-supervised models are strong semi-supervised learners. Advances in neural information pro- cessing systems, 33, 2020b.
Muthuraman Chidambaram, Yinfei Yang, Daniel Cer, Steve Yuan, Yun-Hsuan Sung, Brian Strope, and Ray Kurzweil. Learning cross-lingual sentence representations via a multi-task dual-encoder model. arXiv preprint 1810 12836, 2018.
Jacob Devlin, Ming-Wor Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of deep bidirectional transformers for language understanding. In Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, 2019.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(7), 2011.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, 2006.
Hongchao Fang, Sicheng Wang, Meng Zhou, Jiayuan Ding, and Pengtao Xie. Cert: Contrastive self-supervised learning for language understanding. arXiv preprint 200.::2000.127666. 2020.
Badih Ghazi, Pasin Manurangsi, Pritish Kamath, Ravi Kumar Ravikumar, and Vadym Doroshenko. Connect the dots: Tighter discrete approximations of privacy loss distributions. arXiv preprint arXiv:2207.043880 2022.
John Giorgi, Osvald Nitski, Bo Wang, and Gary Bader. Declutr: Deep contrastive learning for unsupervised textual representations, arXiv preprint arXiv:2006.0365) 2020.
Ian Goodfellow. Efficient per-example gradient computations. arXiv preprint arXiv:1510.0170
2015.
Xinlei He and Yang Zhang. Quantifying and mitigating privacy risks of contrastive learning. In Conference on Computer and Communications Security (SIGSAC), 2021.
Mengdi Huai, Di Wang, Chenglin Miao, Jinhui Xu, and Aidong Zhang- Pairwise learning with differential privacy guarantees. Conference on Artificial Intelligence (AAAI). 34, 2020.
Yilin Kang, Yong Liu, Jian Li, and Weiping Wang. Towards sharper utility bounds for differentially private pairwise learning. arXiv preprint 200.::2200003000 2021.
10

---

Published as a conference paper at ICLR 2025
Diederik P Kingma. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
Fabian Latorre, Paul Rolland, and Volkan Cevher. Lipschitz constant estimation of neural networks via sparse polynomial optimization. In International Conference on Learning Representations (ICLR), 2020.
Jaewoo Lee and Daniel Kifer. Scaling up differentially private deep learning with fast per-example gradient clipping. arXiv preprint S1ti::2009.031000 2020.
Wenjun Li, Anli Yan, Di Wu, Taoyu Zhu, Teng Huang, Xuandi Luo, and Shaowei Wang. Dpel: Contrastive representation learning with differential privacy. International Journal of Intelligent Systems, 2022.
Xuechen Li, Florian Tramer, Percy Liang, and Tatsunori Hashimoto. Large language models can be strong differentially private learners. arXiv preprint arXiv:2110.05679, 2021.
Hongbin Liu, Jinyuan Jia, Wenjie Qu, and Neil Zhenqiang Gong. Encodermi: Membership in- ference against pre-trained encoders in contrastive learning. In Conference Computer and Communications Security (SIGSAC), 2021.
Lajanugen Logeswaran and Honglak Lec. An efficient framework for learning sentence representa- tions. arXiv preprint arXiv: 02893,, 2018.
H Brendan McMahan and Matthew Streeter. Adaptive bound optimization for online convex opti- mization. arXiv preprint arXiv: 2010.
midjourney. Midjourney. midjourney, com. Accessed: 2023-05-11.
Ilya Mironov. Rényi differential privacy. In IEEE computer security foundations symposium (CSF), 2017.
Aaron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predic- tive coding. arXiv preprint urXiv: 1807.03748 2018
Natalia Ponomareva, Jasmijn Bastings, and Sergei Vassilvitskii. Training text-to-text transformers with privacy guarantees. In Findings of the Association for Computational Linguistics: ACL 2022, pp. 2182-2193, 2022.
Alec Radford, Karthik Narasimhan, Tim Salimans, Ilya Sutskever, Improving language under- standing by generative pre-training. OpenAl, 2018.
Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. Learning transferable visual models from natural language supervision. In International Conference Machine Learning (ICML), 2021.
Shideh Rezaeifar, Slava Voloshynovskiy, Meisam Asgari Jirhandeh, and Vitality Kinakh, Privacy- preserving image template sharing using contrastive learning. Entropy, 2022.
Gaspar Rochette, Andre Manoel, and Eric W Tramel. Efficient per-example gradient computations in convolutional neural networks. arXiv preprint arXiv:
2019.
Chitwan Saharia, William Chan, Saurabh Saxena, Lala Li, Jay Whang, Emily Denton, Kamyar Ghasemipour, Raphael Gontijo Lopes, Burcu Karagol Ayan, Tim Salimans, et al. Photorealistic text-to-image diffusion models with deep language understanding. Advances in Neural Informa- fion Processing Systems, 2022.
Zhouxing Shi, Yihan Wang, Huan Zhang, J Zico Kolter, and Cho-Jui Hsich. Efficiently computing local lipschitz constants neural networks via bound propagation. Advances in Neural Informa- fion Processing Systems, 2022.
Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. Membership inference at- tacks against machine learning models. 2017 IEEE symposium on security and privacy (SP). IEFF, 2017.
11

---

Published as a conference paper at ICLR 2025
Congzheng Song and Ananth Raghunathan. Information leakage in embedding models. In Confer- ence on Computer and Communications Security (SIGSAC), 2020.
Romal Thoppilan, Daniel De Freitas, Jamie Hall, Noam Shazeer, Apoorv Kulshreshtha, Heng- Tze Cheng, Alicia Jin, Taylor Bos, Leslie Baker, Yu Du, al. LaMDA: Language Models for Dialog Applications. arXiv preprint arXiv:2201.08233 2022.
Chuhan Wu, Fangzhao Wu, Tao Qi, Yongfeng Huang, and Xing Xie. Fedel: Federated contrastive learning for privccy-prsseving recommendation. arXiv preprint arXiv:2204. 09850, 2022.
Zhuofeng Wu, Sinong Wang, Jiatao Gu, Madian Khabsa, Fei Sun, and Hao Ma. Clear: Contrastive
learning for sentence representation. arXiv preprint arXiv:20/2. 2020.
Zheng Xu, Maxwell Collins, Yuxiao Wang, Liviu Panait, Sewoong Oh, Sean Augenstein, Ting Liu, Florian Schroff, and H Brendan McMahan. Learning to generate image embeddings with user- level differential privacy. arXiv preprint arXiv:2211.0084 2022.
Zhiyu Xue, Shaoyang Yang, Mengdi Huai, and Di Wang 0015. Differentially private pairwise learning revisited. In IJCAI, 2021.
Zhenhuan Yang, Yunwen Lei, Siwei Lyu, and Yiming Ying. Stability and differential privacy of stochastic gradient descent for pairwise learning with non-smooth loss. In Conference on Artificial Intelligence and Statistics (AISTATS), 2021.
Felix Yu, Ankit Singh Rawat, Aditya Menon, and Sanjiv Kumar. Federated learning with only positive labels. In International Conference on Machine Learning (ICML), 2020.
Yaodong Yu, Maziar Sanjabi, Yi Ma, Kamalika Chaudhuri, and Chuan Guo. Vip: A differentially private foundation model for computer vision. arXiv preprint arXiv:2306. 08844,, 2023.
Xu Zhang, Felix X Yu, Sanjiv Kumar, and Shih-Fu Chang. Learning spread-out local feature de- scriptors. In IEEE International Conference Computer Vision, 2017.
12

---

Published as a conference paper at ICLR 2025
SUPPLEMENTARY MATERIAL FOR DP-SGD FOR NON-DECOMPOSABLE OBJECTIVE FUNCTIONS
A PROOFS
Proof of Lemma 4.1. Denote
= 1 [nn := (0-1(( (x)() E ER""!.
for all i. Using the chain rule, the gradient of Lx(w) on batch [ can be computed as
VLx(w) Σ Velia) T
The conclusion now follows by combining the above expression with the fact that DZ ((V2))T ;..:; (V2x))))
Proof of Theorem 4.2. For ease of notation, let Zx Z (w), - = and
exx g(im)) (Zx),
x ( 1) ( . x
(()-1)))
and similarly for the gradicnts of these functions in w. Using Lemma 4.1, the lg sensitivity of VLx is
n
delimn)
m-ln-1
a
(v(x)
V
VZ
azy
aZi
The above expression can be broken down into the following terms:
dd
pll
aelim)
1e(cmn11)
A2 (Zxx)
AZA
dzy
in
0z
Ozk
X
TI
T2
We now use the triangle inequality to bound each term.
a
aefn.n)
ae(r.)) a7n
aeln.n) azn
||Ti|| =
V TM
BSGB
a7
j=l
Similarly, using the same approach, we obtain partial derivatives of the family {g(i.)) [
[22l S G,B. Finally, using the assumption on the
0elin-11
7>ll =
az%
azx
ae(i.m)
ae
affi.n-1) I)
V2
024
074
n- --1n-1
ae(im)
aefim-11)
B
oz%
azy
< (n 1)
Combining the above bounds yields the desired bound on A2(VLx)
13

---

Published as a conference paper at ICLR 2025
Proof of Lemma 4.5. It is straightforward to show that
aetinn)
e
2 n
k=
e
-,,,
j - i,
Øzj
n k=
otherwise.
then follows that
@e(nm)) (2)
n
e
Fm Ek=1
1
Ozj
e
E
==
Note that Σj=1 e / k= e = 1 - e / E*t, since the n terms constitute probability
distribution summing to 1. Thus,
ae(m.n)
=2(1-
=2
e:n
Özg
Σ e
+1
Σ k= e
Σ Ex=r
E#k
Denoting Pr. e*n / E we have that
ap(m.)) (2)
G1 =
22 - Pn)
(8)
θzj
Next, we look into G2 Σi= (0e(im) (2) /2zzl. In this case,
agthni (z)
n-1
(n - 1)e2
Ozn
k==
cth
- e
i=1
and, hence,
G2 (n 1)pn-
Finally, for the condition on the difference we have that for all i E [n].
de(in-11(2)
(e(
0z,
Ozj
e
e
==1
2k
Σ
2k
k=
Σ
k== 2k
where we removed the absolute value on the last term since all values are positive. We observe that the first term up to and the last one corresponds to 1 c /E o#h Pu. Hence, the above expression is given by
L=
=1 (1 Pn)) Pn-
(10)
e*
km
Combining (8), (9), and (10), we have
G1 + G2 (n 1)L 2(1 P..) (n 1)p, + (n - 1)p, 2(1 + (n - 2)px))
Since the contrastive loss uses the cosine similarity, we have that the inputs (21...., 2n) given to g(tm)) satisfy |2,| for all Consequently, the last term is maximized when 2n = 1 and 24
for k < n - 1, yielding
G + G2 (n 1) 1
2)e
-2(1
(1+
(n 2)
c c - 1)e
+ (n 1)
where we multiplied by e the numerator and denominator on the last step. The result follows from theorem 4.2.
14

---

Published as a conference paper at ICLR 2025
Proof of Lemma 4.6. Let calculate the values of L, G1, G2 that make this function satisfy the conditions of Theorem 4.2. Let x = (z', 2n) then we have that
( ae(im-1)(22)
2
2
2
dzj
Ōzj
1 73
2 23
(n 1) 2) Zgg
for j o and 0 otherwise. For any C' S m=x Rjj we then have:
(z)
ae(in (2())
R=1
2
20
1zyl
L
0zj
Ozj
(n 1)(n - 2)
n1
j7
Similarly we have
(z)
aglin) (z)
Σ
20 =: G1,
Σ
20
=: G2
Ozj
dzj
and, hence, G + G2 + (n - 1)L < 6C. Since the cosine similarity implies ži 1, holds that C and the result follows.
((0(x)),(<}}))
15

---

Published as a conference paper at ICLR 2025
B EXPERIMENT DETAILS
This appendix gives more details about the numerical experiments in Section 5. All models were trained on a single NVidia VI00 GPU using cloud computing platform with 512 GB RAM.
B. PRE-TRAINING ON CIFARIO
Model Specification, Dataset Details, and Hyperparameters
For reproducibility, we now give the details of the model, the hyperparameters of the above variants, and the training setup. The generic embedding net model consists of three 2D convolution layers followed by one embedding layer. The convolution layers used 3-by-3 kernel with stride 2, ReLU output activation function, Kaiming normal kernel initializer, and (sequentially) chose out- put channels of 8, 16, and 32, respectively. The embedding layer generated an output of dimension 8 and used Xavier- normal initializer.
normall
The learning rates for Logit-DP, Naive-DP, and Non-Private were 10-2, 10-2. and 10-3, respec- tively, for the generic embedding net experiments and 10-4 10-3 and 10-2, respectively, for the ResNet18 experiments. All variants used the standard Adam optimizer for training and used the canonical 80-20 train-test split of the CIFARIO IO dataset. However, Logit-DP used 25 and 100 gradi- ent accumulation steps for the generic embedding net and ResNet18 experiments, respectively. The batch size during training was 10, 000 and 000 for the generic embedding net and ResNet18 ex- periments, respectively, and the entire testing dataset was used for evaluating test metrics. Moreover, each variant was run for 20 and epochs over the entire training dataset for the generic embedding net and ResNet18 8 experiments in Table 1, respectively.
For the DP variants, we fixed the desired lz sensitivity Logit-DP, respectively, in the generic embedding net experiments and 10 and 10-5, respectively, the ResNet18 experiments. All DP methods chose a noise multiplier so that e-DP was achieved for 5.0.
10-4 and 10-5 for Naive-DP and
Finally, all hyperparameter tuning was done through grid search of various learning rates (10-5 10 .... 10 9) and &2 sensitivities (10-6, 10-5 ..... 10 10-"),
B.2 FINE-TUNING ON CIFAR100
Model Specification, Dataset Details, and Hyperparameters
For reproducibility,
give the details of the model, the hyperparameters of the above vari- ants, and the training setup. V/ is three-layer fully-connected neural network whose layer output dimensions are 64, 32, and 20 in sequence.
The learning rate for all variants was 10-2 All variants used the standard Adam optimizer (iteration scheme) for training and used the canonical 80-20 train-test split of the CIFAR 100 dataset. The batch size during training was 400 and the entire testing dataset was used for evaluating test metrics. Moreover, each variant was run for ten epochs over the entire training dataset.
For the DP variants, we fixed the desired & sensitivity to be 1.0 and chose a noise multiplier so that DP was acheived for 5.0. All hyperparameter tuning was done through grid search of various learning rates (10-4, 10 10-3, 10 10-2) and l sensitivities (10-2, 10-1 10").
16

---

Published as a conference paper at ICLR 2025
C ADDITIONAL FIGURES AND TABLES
100
111
111
323
LIG
65.5
Min
0.00
DED
150
356
350
120
124
353
226
357
215
123
240
200
Cet
250
Core
Deee
Dag
230
Dag
1lg
mng
S82
536
Home
126
329
T25
ter
04 Foo Thophess
CA New Day happerod Tracc Polktee
Goar
Tock
Figure 3: Averaged CIFARIO 10 confusion matrices at the last testing step for the generic embedding net experi- ments. Values are rounded down to the nearest whole number.
Loge:
Nalve DP
530
403
NaT PlNVDo
225
DXS
LCC
255
355
LCE 150
Cat
1K9
35T
160
112
JS:
AUN
SKY
227
212
110
Dap
4-4
74
LED
230
227
337
115
XX5
Drige
5AO
345
383
252
25
75
322
7og
192
192
213
250
Pog
2M6
117
Hare
IK7
222
3X7
300
222
345
TM
38
41
Tracc
Trch
Cut Core Prodectr tibe!
Prodcted lifel
Prodite lchil
Figure 4: Averaged CIFARIO confusion matrices at the last lesting step for the ResNet18 experiments. Values are rounded down to the nearest whole number.
17

---

Published as a conference paper at ICLR 2025
Embedding Metrics (mean standard deviation)
Accuracy
Recall
Precision
Fg Score
Logit-DP
0.173 / 0.002
0.254 / 0.006
0.251 / 00.005
0.253 / 0.004
Naive-DP
0.174 / 0.002
0.242 0.005
0.245 / 0.006
0.243 / 0.005
Non-private
0.212 / 0.003
0.300 / 0.010
0.312 / 0.0010
0.306 / 0.010
R8sNet18 Metrics (mean standard deviation)
Accuracy
Recall
Precision
Fg Score
Logit-DP
0.202 / 0.000
0.325 0.0013
0.013
0.268 / 70.013
0.291 / 0.0013
Naive-DP
0.169 0.003
0.269 0.006
0.284 00.010
0.276 / 0.008
Non-prive Non-private
0.278 / 0.008
0.389 / 0.013
0.388 / 00.11
0.388 / 0.010
(- BBN
Non-private
0.274 /.000
0.402 / 0.016
0.418/0.015
0.41 141/0.014
(+ BN)
Table 3: Aggregate CIFARIO metrics generated by the confusion matrix C the last test point over ten runs. Accuracy defined as Σ; Ca/ Ei, Cig- The recall, precision, Fg scores are over the hest observed metric over all ten CIFARI0 classes. Non-privant (+BN) and Non-Private (-BN) denote the standard and modified architecture without BatchNorm layers respectively.
Average train ng times
Loss over time
example
0.010
1.850
0.006
0.006
1.800
1.775
0.004
1.750
0.002
1.725
0.000
200
400
800
800
1000
4000
6000
8000
10000
Number of Examples (in thousands)
Runtime (seconds)
Logit-DP
Legit-OP
Figure 5: Training time related plots for small embeddding net model on CIFAR10 over ten runs. (I.eft) Number of seconds per example over the number of examples seen. Shaded regions bound the observed values, while the dark lines represent the averaged values. (Right) Average training losses over the average runtime.
Embedding Net Metries
Accuracy
Recall
Precision
Fa Score
Logit-DP
0.169
0.432
0,308
0.336
Naive-DP
0.158
0.578
0.215
0.313
Non-private
0.167
0.446
0.322
0.343
Table 4: CIFARI00 test metrics generated the confusion matrix C at the last point Ac- curacy is defined as Σ, Ca/E, Σn, Ci while top recall, precision, and Fa scores the best observed metric over all CIFARI00 classes.
18

---

Published as a conference paper at ICLR 2025
Relative Contrastive Loss Values
1.10
Belative Loss value
1.08
1.06
1.04
1.02
1.00
1000
2000
3000
4000
5000
Number Examples
Logil-DP
Neive-DP
Mon-Private
Figure 6: Relative loss CIFARIO 100 epochs. This extended training (ef. Figure 1, left) demon- strates that performance Logit-DP is not solely due early stopping.
19


Reviews:
[{"review_id": "EFi9e2oXR1", "reviewer": "Reviewer_EWmR", "summary": "The paper presents a new variant of Differentially Private Stochastic Gradient Descent (DP-SGD) designed for similarity-based loss functions, such as contrastive loss, which are common in unsupervised pre-training. The core claimed contribution is a modified DP-SGD method that achieves sensitivity of $O(1)$ for the summed gradient with respect to batch size. The paper also provides experimental validation of this new method on CIFAR-10 and CIFAR-100, showing performance close to non-private models and generally better than the naive DP-SGD approach.", "questions": "A few missing references on unsupervised DP-SGD pre-training:\n\n[PBV2022] Training text-to-text transformers with privacy guarantees. Ponomareva, N., Bastings, J., and Vassilvitskii, S.  In Findings of the Association for Computational Linguistics: ACL 2022, pp. 2182–2193, 2022.\n\n- [YSM+2024] ViP: A Differentially Private Foundation Model for Computer Vision. Yaodong Yu, Maziar Sanjabi, Yi Ma, Kamalika Chaudhuri, Chuan Guo Proceedings of the 41st International Conference on Machine Learning, PMLR 235:57639-57658, 2024.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- The problem is very well-motivated. Differentially private pre-training is an important and interesting direction for learning foundation models privately. Most existing work [PBV2022, YSM+2024] focus on training decomposable loss with DP-SGD. Investigating new efficient and effective techniques for training DP models with non-decomposable loss is very important.\n\n\n*References*\n\n[PBV2022] Training text-to-text transformers with privacy guarantees. Ponomareva, N., Bastings, J., and Vassilvitskii, S.  In Findings of the Association for Computational Linguistics: ACL 2022, pp. 2182–2193, 2022.\n\n[YSM+2024] ViP: A Differentially Private Foundation Model for Computer Vision. Yaodong Yu, Maziar Sanjabi, Yi Ma, Kamalika Chaudhuri, Chuan Guo. Proceedings of the 41st International Conference on Machine Learning, PMLR 235:57639-57658, 2024.", "weaknesses": "The main question (and potential weakness) I have is: \n>Is the proposed method indeed independent of the batch size $n$? As proved in Theorem 4.2, the $L_2$ sensitivity is upper bounded by $(G_1 + G_2 + (n-1)L) B$, where $n$ is the batch size. Then as described in Lemma 4.5, for contrastive loss, $(G_1 + G_2 + (n-1)L) B$ is upper bounded by $B_{\\text{contrastive}}=2(1+\\frac{(n-2)e^2}{e^2+(n-1)})$. Therefore, when $n$ is large, isn't $B_{\\text{contrastive}} = O(n)$? And this is not independent of the batch size $n$. \n\nI may have some misunderstandings here. I would like have the authors to clarify this during the discussion. If the independent argument is correct, I would raise my score.\n\n(minor weakness) The proposed method is computationally more expensive than standard DP-SGD, I suggest the authors to provide some results on [training loss vs training time].", "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": "gCZKpk8ndw", "reviewer": "Reviewer_2dkT", "summary": "This paper proposes a variant of DP-SGD for loss functions that cannot be described as an average (or sum) of individual losses, such as contrastive loss and spread-out regularization. The authors apply a Gaussian Mechanism scheme, theoretically derive an upper bound for $L_2$-sensitivity and experimentally claim their findings on computer vision tasks.", "questions": "See Weaknesses.", "limitations": "", "rating": 1, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "**S1:** The method is consistent with prior studies on DP-SGD.\n\n**S2:** The implementation of the proposed Logit-DP algorithm is the same as for DP-SGD.\n\n**S3:** The authors also prove several lemmas regarding the conditions on $L_2$-sensitivity.", "weaknesses": "**W1:** The main theoretical findings of the paper focus only on \"vanilla\" contrastive loss and spread-out loss. However, there is an increasing demand for more sophisticated types of loss functions, such as SimCLR [1] and InfoNCE [2]. These functions align well with **Definition 2.2** and benefit from a large batch size. The paper lacks additional commentary on these and other contrastive objectives, for which analogous lemmas can be easily proved.\n\n**W2:** The experimental validation is unclear:\n\n- In Line 326 the authors note that they train model without BatchNorm layers because of they are not privacy-preserving, at the same time, no comparison is provided with a baseline model that includes BatchNorm.\n- Modern NLP and CV models often use transformer architectures that incorporate LayerNorm. Could the authors clarify whether they consider LayerNorm more privacy-preserving or not?\n-  It is hard to understand figures: in Figure 1 the authors report averaged relative loss along with its bounds/percentiles for Logit-DP, but no bounds/percentiles provided for Non-Private and Naive-DP. Also there are no mentioned standard deviation in all Tables, while it is obvious that the authors report an averaged results.\n- There are several drawbacks regarding the hyperparameters sweep: the authors train a ResNet18 model on CIFAR10 for only 2 epochs and a generic convolutional model for 20 epochs, whereas training from scratch on CIFAR10 typically requires hundreds of epochs. At the same time, they fine-tuned both the generic convolutional model and ResNet18 for 10 epochs, which is much longer than regular fine-tuning.\n- In Table 4, the authors report an accuracy score below 20% for the CIFAR100 fine-tuning task. Needs further clarifications.\n\n**W3:** In Lines 380-383, the authors do not address the issue of private fine-tuning of the publicly available (i.e., non-privately trained) model,  which is almost more popular in the community than private training from scratch. Additionally, the authors do not clarify what is meant by a ''privately pre-trained'' embedding model: how is it pre-trained?\n\n**W4:** The code is not publicly available.\n\n\n**Minor Comments:**\n\n**C1:** There is no need to write ''non-private'' twice in Line 405,  as the implication is clear that the Non-Private optimizer is SGD (Line 324).\n\n**C2:** The section title in Line 824 is incorrect; it should be  ''Fine-tuning on CIFAR100''.\n\n**C3:** In Line 834 you denote $L_2$-sensitivity as $\\ell_2$-sensitivity, which is not self-consistent.\n\n\n\n\n\n[1] Ting Chen, Simon Kornblith, Mohammad Norouzi, Geoffrey Hinton. ''A Simple Framework for Contrastive Learning of Visual Representations''. ICML 2020\n\n[2] Aaron van den Oord, Yazhe Li, Oriol Vinyals. ''Representation Learning with Contrastive Predictive Coding''.", "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": "aO1eQkbtyg", "reviewer": "Reviewer_e6qK", "summary": "This work studies DP optimization of non-decomposable functions in neural networks, trying to add less noise with respect to the batch size. A new algorithm with proofs are proposed with CIFAR experiments.", "questions": "See \"Weaknesses\".", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The paper is reasonably easy to follow and rigorous as far as I am concerned. A significant portion of the paper is devoted to background introduction. The empirical results are clear. The algorithmic limitation (the computation bottleneck) is carefully discussed.", "weaknesses": "The algorithm is not straightforward: $\\bar g$ comes from (5) which does not relate to $\\bar g$ explicitly nor to $\\bar g_{ij}$ in the line above. There should be a hidden for loop between line 4 and 5 in Algorithm 1 (for i,j in 1...n) to highlight the computational bottleneck.\n\nThe experiments are not very convincing, especially given the first sentence in abstract \"Unsupervised pre-training is a common step in developing computer vision mod- els and large language models.\" Some experiments are fine-tuning not pre-training, and no language modeling is shown. I would encourage the authors to enhance the experiments with ImageNet (at least a subset) or Transformers.\n\nMinors: \n1. Most new contents are only presented after page 4, which may come too late and is slightly distracting.\n\n2. Title should not use abbreviations like DP and, since the method applies to other optimizers besides SGD, maybe the title can highlight this.\n\n3. Line 3 of Algorithm 1, the for loop counting is incorrect.", "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": "ZjbwAIGiiy", "reviewer": "Reviewer_chx4", "summary": "This papers discusses the challenge of training computer vision and language models with differential privacy, especially when using unsupervised pre-training and similarity-based loss functions like contrastive loss. The primary issue with contrastive loss in a privacy-preserving setting is that its sensitivity increases with the batch size, which negatively impacts differentially private methods like DP-SGD (Differentially Private Stochastic Gradient Descent). To address this, the authors propose a modified DP-SGD method specifically designed for similarity-based losses, achieving a constant sensitivity level regardless of batch size. Their experiments on CIFAR-10 and CIFAR-100 datasets demonstrate that this approach nearly matches the performance of non-private models and surpasses the results of directly applying DP-SGD to contrastive loss.", "questions": "n/a", "limitations": "", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The paper considers developing DP algorithms for problems where the objective function is coupled, which often happens in problems with contrastive loss. The setting appears to be new, and the algorithms are specifically design and analyzed for this class.", "weaknesses": "However, the derivation of the \\ell_2 sensitivity is rather trivial, and the resulting algorithm is still just a simple variation of the traditional DP-SGD algorithm. Most of the derivations are mechanical. I do not see too much insights or contribution in this work. Further, the paper has not been well-written, as there are places that have obvious typo and inconsistencies. For example in line 156 Eq. (2.4) has been mentioned, but no (2.4) has been defined, nor the gradient of K_z(w) has been defined either.", "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": "wonXOsZXya", "reviewer": "Reviewer_BSWK", "summary": "This paper presents a variant of DPSGD tailored for DP-training with non-decomposable loss functions, such as the CLIP loss. The authors theoretically bound the l2 sensitivity of the gradient, demonstrate the privacy guarantee, and introduce their Logit-DP algorithm. They also discuss prior methods like per-batch and per-sample clipping and evaluate their approach on CIFAR-10 pretraining and CIFAR-100 finetuning tasks.", "questions": "1. The main result, Theorem 4.2, seems to be a simple expansion with some triangle inequlities. Much of the theoretical complexity is deferred to parameters L, G1, and G2, which seem to be technical artifacts rather than providing meaningful generalization of the theory.\n\n2. The algorithm involves per-sample clipping, computing the batch gradient using Theorem 4.2, and adding noise. This approach somehow feels somewhat redundant to me, as it seems to enforce clipping of the per-sample loss explicitly. Since per-batch clipping alone should suffice to ensure privacy (see [1]), it seems that per-sample clipping is not an essential requirement from a privacy perspective, but rather a technical necessity due to the proof requiring bounded per-sample gradients. While the authors discuss the empirical limitations of per-sample clipping (see 5 below), it would be helpful if the authors could further clarify the reasoning behind this choice, particularly any theoretical intuitions beyond this empirical justification.\n\n3. The DP guarantee in Corollary 4.4 also seems loose. The noise magnitude of order $n \\sqrt{\\log(1/\\delta)} / \\epsilon$ could be reduced to $\\sqrt{\\log(1/\\delta)} / \\epsilon$, similar to [1], given that the loss is not divided by $1/n$, while the loss in [1] is divided by $1/n$.\n\n4. The paper lacks discussion on the privacy-utility tradeoff. While noise can always be added to ensure privacy, it’s crucial to evaluate its impact on model performance.\n\n5. In Sections 5.1 and 5.2, the values of $\\epsilon$ is missing (maybe I missed it...?) Additionally, the authors suggest that “clipping the batch gradient (which they term Naive-DP) does not significantly reduce $L_X(w)$, regardless of batch size or clip norm.” They imply that Naive-DP leads to poor convergence: excessive noise for small batches and stability issues for large batches. However, is there a rationale beyond Figure 1? Also, was the learning rate kept constant across different batch sizes? Typically, larger batch sizes requires larger learning rates (see [2]).\n\n6. Lastly, in Figure 2, Logit-DP performs better than the non-private model, which seems counterintuitive.\n\n\n[1] Huang et al. Safeguarding Data in Multimodal AI: A Differentially Private Approach to CLIP Training, https://arxiv.org/pdf/2306.08173\n[2] Ponomareva et al. How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacy, https://arxiv.org/pdf/2303.00654", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The problem addressed is both important and practically valuable, and the method provides an interesting solution for DP-training models with non-decomposable losses, such as CLIP-based VLMs.", "weaknesses": "See below.", "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)