DP-SGD Without Clipping: The Lipschitz Neural Network Way
Authors: Louis Béthune
Thomas Massena
Thibaut Boissin
Aurélien Bellet
Franck Mamalet
Yannick Prudent
Corentin Friedrich
Mathieu Serrurier
David Vigouroux
Venue: ICLR 2024 poster (2024)
Keywords: lipschitz neural networks
dp-sgd
privacy
robustness
Primary area: societal considerations including fairness, safety, privacy
TL;DR: Lipschitz neural networks can be trained with DP guarantees without gradient clipping

Abstract: State-of-the-art approaches for training Differentially Private (DP) Deep Neural Networks (DNN) face difficulties to estimate tight bounds on the sensitivity of the network's layers, and instead rely on a process of per-sample gradient clipping. This clipping process not only biases the direction of gradients but also proves costly both in memory consumption and in computation. To provide sensitivity bounds and bypass the drawbacks of the clipping process, we propose to rely on Lipschitz constrained networks. Our theoretical analysis reveals an unexplored link between the Lipschitz constant with respect to their input and the one with respect to their parameters. By bounding the Lipschitz constant of each layer with respect to its parameters, we prove that we can train these networks with privacy guarantees.  Our analysis not only allows the computation of the aforementioned sensitivities at scale, but also provides guidance on how to maximize the gradient-to-noise ratio for fixed privacy guarantees. To facilitate the application of Lipschitz networks and foster robust and certifiable learning under privacy guarantees, we provide a Python package that implements building blocks allowing the construction and private training of such networks.

DP-SGD WITHOUT CLIPPING: THE LIPSCHITZ NEURAL NETWORK WAY
Louis Béthune
Thomas Masséna
Thibaut Boissin *
Aurélien Bellet
Franck Mamalet $
Yannick Prudent
Corentin Friedrich 4
Mathieu Serrurier f
David Vigouroux 1
ABSTRACT
State-of-the-ae approaches for training Differentially Private (DP) Deep Neural Networks (DNN) face difficulties to estimate tight bounds on the sensitivity of the network's layers, and instead rely on process of per-sample gradient clipping. This clipping process not only biases the direction gradients but also proves costly both in memory consumption and in computation. To provide sensitivity bounds and bypass the drawbacks the clipping process, we propose to rely on Lipschitz constrained networks. Our theoretical analysis reveals unexplored link between the Lipschitz constant with respect to their input and the one with respect their parameters. By bounding the Lipschitz constant of each layer with respect to its parameters, we prove that we can train these networks with privacy guarantees. Our analysis not only allows the computation of the aforementioned sensitivities scale, but also provides guidance on how to maximize the gradient-to-nois ratio for fixed privacy guarantees. The code has been released as a Python package available at
htwp:a/cooo/olueeeeeeeeeeee 11pp-pp
INTRODUCTION
The field of differential privacy seeks to enable deep learning on sensitive data, while ensuring that models do not inadvertently memorize reveal specific details about individual samples in their weights. This involves incorporating architectures and training algorithms, whose most popular example Differentially Private Stochastic Gradient Descent (DP-Se (DP-SGD) (Abadi et al.) (2016). One main drawback of classical DP-SGD methods that they require costly per-sample backward processing and gradient clipping. this paper, we offer new method that unlocks fast differentially private training through the use of Lipschitz constrained neural networks.
mechanisms into the design of deep learning
Differential privacy. Informally, differential privacy (DP) is a definition that bounds how much the change of a single sample dataset affects the range of a stochastic function (here, the training algorithm). This definition is largely accepted as strong guarantee against privacy leakages under various scenarii, including data aggregation or post- pest-processing (Dwork et al. 2006).
In this paper focus supervised learning tasks: assume that the dataset D is finite collection of input/label pairs ID = {[x1 J)),,..... (NN, )x))- The definition DP relies on the notion of neighboring datasets, i.e datasets that vary by most example. We highlight below the central tools related to the field, inspired from Dwork et al. (2014).
Definition ((E, AAprrxxxiee Differential Privacy). Two datasets D and D' are said to be neighboring for the "add/remove-one" relation they differ by exactly one sample: (D' D = where e denotes the symmetric difference between sets. Let e and 5 be two non non-negative sealars. An
'Equal contribution.
1 IRIT, Université Paul Sabatier, Toulouse.
I IRT Saint Exupéry, Toulouse.
6 Inria, Université de Montpellier.

---

model DP Sequential (1 f step 1: use DP Sequential to build a model
4 step 2: add Lipschitz layers of known sensitivity
DP_ BoundedInput (han
28, 1), upper_ upper_bound-20.).
DP_ SpectraiConv2D (araioooovo(iittsssllssesa (filters=16, pernel_sizers use_blas=False),
DP GroupSort
DP Flatten()),
DP SpectraalDense
do p_.pprammtttsss-pppppaaattteeeee dataset_mee L
} # step 4: compile the model, and choose any first order optimizer (tau=20.), model 2ode1.fit fit ( # step 5: train the model and measure the DP guarantees crain_dataset, validation -aaaationdddtt-val litta-valddttsett epochs-num_epochs, callbacks- [DP Accountant ()
model. compile (loss=DP_Taute)
Figure 1: An example of usage of our framework 1ip-dp, illustrating how to create small Lipschitz VGG and how to train under (e. guarantees while reporting (c, values.
algorithm A is (e, for any two neighboring datasets 'D and D', and for any S C range( (A):
P[A(D) S] S e P[A(D') E S) +
A popular rule of thumb suggests using c S 10 and 5 < + with N the number of records (Ponomareva et al. 2023) for mild guarantees. In practice, most classic algorithmic procedures (called quertes in this context) do not readily fulfill the definition for useful values of (e, 8): in particular, randomization mandatory. A general recipe to make a query differentially private to compute its sensitivity A. and to perturb its output by adding a Gaussian noise of predefined variance 5² A2 where the (c, 6) guarantees depend on a, yielding what called Gaussian mechanism (work et al. 2006).
Definition 2 (ly-sensitivity). Let M be query mapping from the space of the datasets to R. Let N be the set of all possible pairs of neighboring datasets D.D'. D'. The l2 sensitivity of M is defined by:
A(M)
sup D.D'EN
JIM(D) ([M((M))MUUU (M(D))M(D')l2>
This randomization comes at the expense of "utility", ",, i.e the usefulness of the output for downstream tasks (Alvim at 2012). The goal then strike balance between privacy and utility, ensuring that the released information remains useful and informative for the intended purpose while minimizing the risk of privacy breaches. The privacy/utility trade-off yields a Pareto front, materialized by plotting against measurement of utility, such as validation accuracy for classification task.
Differentially Private SGD. The SGD algorithm consists of a sequence queries that (i) take the dataset in input, sample minibatch from it. and return the gradient of the loss evaluated on the minibatch, before (ii) performing descent step following the gradient direction. In "add-remove" neighhoring relations, if the gradients are bounded by K 0. the sensitivity of the gradients averaged on minibatch size is
K/ K/b. DP-SGD (Abadi et al.) 2016) makes each of these queries private by resorting to the Gaussian mechanism. Crucially, the algorithm requires a bound on gradient norms [V, 1)ll2 < C. This upper bound on gradient norms is generally unknown in advance, which leads practitioners clip it C' 0, in order bound the sensitivity manually. Unfortunately, this creates a number of issues: 1. Hyper-papn srper-paraaeeer search on the broad-range clipping value C required train models with good privacy/utility trade-offs (Papernot & Steinke (022). 2. The computation of per-sample gradients is expensive: DP-SGD is usually slower and consumes more memory than vanilla SGD, particular for the large batch sizes often used private training (Lee Kifer 2021).3 3. Clipping the per-sample gradients biases their average (Chen et al. 2020). This is problematic as the average direction is mainly driven by misclassified examples.
An unexplored approach: Lipschitz constrained networks. To avoid these issues, we propose to train neural networks for which the parameter-we wise gradients are provably and analytically bounded during the whole training procedure, in order to get rid of the clipping process. This allows for efficient training of models without the need for tedious hyper-parameee reason why this approach has not been expermmented much in the past is that upper bounding the
optimization. The main
2

---

gradient of neural networks is often intractable. However, by leveraging the literature on Lipschitz constrained networks introduced by Amil et al. (2019), we show that these networks have computable bounds for their gradient's 's norm. This yields tight bounds on the sensitivity of SGD steps. making their transformation into Gaussian mechanisms inexpensive - hence the name Clipless DP-SGD. Thus, approach is qualitatively different from methods that replace clipping with re- re-normalization (Bu 2022b; Yang et al. 2022), or from those that aim to reduce its time and memory footprint (Li iet al.
al.
2021 Bu al. 2022a He et al. 2022; Bu et al. 2023). comparison is made in Appendix A.5
The Lipschitz constant of a function and the norm of its gradient are two sides of the same coin. The function f Im - IR" is said É-Lipschitz for l2 norm if for every 2, y R we have [[(()) - -f(y I f|| po--yl 2l12. Per Rademacher's 's theorem Simon et al. (1983), its gradient is bounded: [V=.]|] S l. Reciprocally, continuous functions with gradient bounded by are E-Lippchitz.
A feedforward neural network of depth D, with input space X' C R", output space y c R (e.g logits), and parameter space C R2, , is parameterized function f θ X + y defined by the sequential composition of layers f1 ..... JD:
f(0, x)) == (fD o f2(22) (1))
(3)
The parameters of the layers are denoted by = (0a) E O. For affine layers, it corresponds to bias and weight matrix 0₂- = (Wa: ba). For activation functions, there are no parameters: 0g Ø. Feedforward networks include notably Fully Connected networks, CNN, Resnets, or MI.P mixers. Definition 3 (Lipschitz with the additional constraint that each layer Za + fa(Oa, xa) == ya is La-Lipcchitz for all 0g- Consequently, the function x +> f(0,x)) is 8-Lipschitz with f = E X
neural network). Lipschitz networks are feedforward networks,
tn for all 0 E O.
The literature has predominantly focused investigating the control of Lipschitzness with respect to the inputs (i.e bounding / primarily motivated by concerns of robustness (Szegedy et al. 2014 al. 2019a Fazlyab et al. 2019). or improved generalization (Bartlett et al. 2017 Béthune et al. 2022). However, in this work. we will demonstrate that it is also possible to control Lipschitzness with respect to parameters (i.e bounding Vef), which is essential for ensuring privacy. Our first contribution will point out the tight link that exists between those two quantities. The closest work to ours is(Saavit & Gjura (2019), where a Lipschitz network used as a general function approximator of bounded sensitivity V f x)) ||,. but to this day the sensitivity of the gradient query + (0, itself remains largely unexplored. The idea of using automatic diffcrentiation to compute sensitivity
bounds has also been discussed in Ziller et al. 1 and Usynin et al. (2021)
Contributions. While the properties of Lipschitz constrained networks regarding their inputs are well explored, the properties with respect to their parameters remain non-trivial. This work provides a first step to fill this gap: our analysis shows that under appropriate architectural constraints, a I-Lipschitz network has tractable, finite Lipschitz constant with respect to its parameters, which allows for easy estimation of the sensitivity of the gradient computation queries. Our contributions are the following:
1. We extend the field of applications of Lipschitz constrained neural networks. We extend the framework to compute the Lipschitzness with respect to the parameters. This general framework allows to track layer-wise sensitivities that depends on the loss and the model's structure. This is exposed in Section 2 We show that SGD training of deep neural networks can be achieved without per-sample gradient clipping using Lipschitz constrained layers. 2. We establish connections between Gradient Norm Preserving (GNP) networks and improved privacy/utility trade-offs (Section T.... To the best of our knowledge, we are the first ones to produce neural networks benefiting from both Lipschitz- based robustness certificates and privacy guarantees.
3. Finally, Python package companions the project, with pre-computed Lipschitz constants for each loss and each layer type. This is exposed in Section 3.2 It covers widely used architectures, including VGG, ResNets or MLP Mixers. Our package enables the use of larger networks and larger batch sizes, as illustrated by our experiments in Section
2 CLIPLESS DP-SGD WITH L-LIPSCHITZ NETWORKS
Our framework relies the computation of the maximum gradient norm of a network w.n.t its parameters to obtain a per-layer sensitivity Ag. It is based on the recursive formulation of the chain rule involved in backpropagation and requires some natural assumptions that we highlight below.
3

---

Forward input bounds
max [-
[[fa(0,,)]]]
X d-1
Xa
DP Layer xa)
Backpropagate gradient bounds
Gd-1
Gd
B (0...)
dxr
Sensitivity
(0,.2) 06,
A
Inis
Figure 2: Backpropagation for bounds (Algorithm
computes the per-layer sensitivity Ad-
Requirement (Lipschitz loss.). The loss function 9 + L(.. y) must be L-Lipschitz with respect to the logits for all ground truths E V. This is notably the case of Categorical Sofimax-Crossentrpyy
The Lipschitz constants of common supervised losses has been computed and reported in the appendix. Requirement 2 (Bounded input). There exists Xg such that for all X' we have |>>|| S Xo-
There exist numerous approaches for the parametrization of Lipschitz networks, such differentiable re-parametrization (aka "trivialization") like Miyato et al. (2018); Anil et al. (2019), optimization matrix manifolds (Absil et al., (2008) direct parametrization (Meunier et al. 2022 Wang &
Manchester 2023) or projections (Arjovsky et al. 2017). We can distinguish two strategies:
With a differentiable reparamctrization II RP θ where 0 = (I)::: the weights 0 are used during the forward pass, but the gradients are turns the training into an unconstrained optimization problem on the landscape of L fo II.
to 0 through II. This
2. With suitable projection operator IT IR" O: this is the celebrated Projected Gradient Descent (PGD) algorithm (Bubeck et al. 2015) applied on the landscape of L f.
Option requires the analysis of the Lipschitz constant II. If @ is convex, then II I-Lipschitz w.r.t the projection norm, otherwise the Lipschitz constant is generally unknown. For simplicity, option 2 will be the focus our work.
Requirement 3 (Lipschitz projection). The Lipschitz constraints must be enforced with projection operator IRP + O. This corresponds to Tensorflow constraing and Pytorch hooks. Projection is post-processing (Dwork et al. 2006) of private data: it induces privacy leakage.
To compute the per-layer sensitivities, our framework mimics the backpropagation algorithm, where Vector-Jucobian products (VJP) replaced by Sealar-Scalar products of element-wise bounds. For an arbitrary layer 2a + Fa(Oa,za) := Ya the operation is sketched below, as a simple consequence of Cauchy-Schward inequality:
Vz (V C) Ofa
0fa Oxa
& V Ba Cl2
X
(4)
Oxy
Vector-Jncobian product: backpropagute gradients
Scalar-Scalas product: backpropagate
The notation 1/122 must understood as the spectral norm for Jacobian matrices, and the Euclidean norm for gradient vectors. The scalar-scalar product is inexpensive. For Lipschitz layers, the spectral norm of the Jacobian dz is kept constant during training with projection operator IT. The bound of the gradient with respect to the parameters takes a simple form:
Ofa
Vl, I |V p. Cllz
x
(5)
00,
This term can be analytically bounded, exposed in the following section.
2.1 BACKPROPAGATION FOR BOUNDS
The pseudo-code Clipless DP-SGD is sketched in Algorithm 2 The algorithm avoids per-sample clipping by computing per-layer bound the element-wise gradient norm. The computation of this
4

---

per-layer bound is described by Algorithm| I to compute the spectral norm of the Jacobian of each layer with respect to imput and parameters.
(graphically explained in Figure 2)
Crucially, it requires
Input bound propagation (line 2). We compute Xa- =| [l For activation functions it depends on their range. For linear layers, it depends on the spectral norm of the operator itself. This quantity can be computed through the SVD or Power Iteration (Trefethen & Bau 2022 Miyato et al.) 2018), and constrained during training using projection operator II. In particular, covers the case of convolutions, for which tight bounds are known (Singla & Feizi 2021a). For affine layers, it additionally depends on the magnitude of the bias |bal|-
Remark (Tighter bounds in literature). Exact estimation of the Lipschitz bound is notoriously an NP-hard problem, proven by (Virmaux & Scaman 2018). Algorithm 2 can be seen an extension of their AutoLip algorithm to the case of parameters, while their work focused on Lipschimess with respect to the input. Although libraries such as Decomon (Airbus) 2023) or auto-LiRPA (Xu et al. 2020) provide lighter bounds for X via linear relaxations (Singh et al. 2019 Zhang et | 2018). our approach capable of delivering practically fighter bounds than worst-case scenarios thanks to the projection operator 11, while also being significantly less computationally expensive. Moreover, hybridizing our method with scalable certification methods can be a path for future extensions.
Computing maximum gradient norm (line 6). We now present how to bound the Jacobian
0fa(0..)) 09g
In neural networks, the parameterized layers f(0, x) (fully connected, convolutions) are bilinear operators. Hence, we typically obtain bounds of the form:
Ô ff((Os, x)) a0a
- < 0a)llle K(fa, 0u)aa.1
(6)
where ((a,, 0a) is constant that depends on the nature of the operator. Xa- is obtained in line with input bound propagation. Values of K (Ja, 0a) for popular layers are reported in the appendix.
Backpropagate cotangent vector bounds (line 7.
Finally, we bound the Jacobian (Ba.a) For
Bh
activation functions, this value can hard-coded, while for affine layers it the spectral norm of the linear operator. Like before, this value is enforced by the projection operator II.
Algorithm 1 Backpropagation for Bounds
Input: Feed-forward architecture f(8.-) = fn (fp. o... (0
Input: Weights 0 = (01, 02... ..))). input bound Xo
1: for all layers S d < D) do
2: Xd + max
| [[(((a, 22
> Input bounds propagation
3: end for
4: G +t- L/b.
> Lipschitz constant of the (averaged) loss for batchsize b
5: for all layers D 2 221 do
6: Dd + G max
> Compute sensitivity from gradient norm
|
D0
7: G+G max
(0..a...)) 0x
Gla.
Backpropagate cotangent vector bounds
|| 1SXa-1
8: end for
9: return sensitivities A, A2 A,
Privacy accounting for Clipless DP-SGD. We keep track of (e, dDDP values with privacy accountant (Abadi et al.) 2016), by composing different mechanisms. For a dataset with N records and batch size b, it relies on two parameters: the sampling ratio p = N and the "noise multiplier" defined as the ratio between effective noise strength & and sensitivity A. We propose two strategies to keep track of (e, 5) values as the training progresses, based on either the "per-layer" sensitivities Ad (composition of Gaussian mechanisms), or by aggregating them into "global" sensitivity A= VV,, AZ (single isotropic Gaussian mechanism). We rely on the aut outodg |ibbaay as it uses the Rényi Differential Privacy (RDP) adaptive composition theorem [Mironov] (017). that ensures tighter bounds than naive DP composition. Following standard practices of the community (Ponomareval
https:/ thub. wwwpbb/.wom//xxia/////atttte distributed under Apache License 2.0.
5

---

Algorithm 2 Clipless DP-SGD with per-layer sensitivity accounting
Input: Feed-forward architecture f(0,-) -)= = fo (0p, .... o fi (01,))
Input: Initial weights 0 = (0,,01.... 0D), learning rate noise multiplier a.
1: repeat
2:
A1 1...4........ AD < Backpropagation for Bounds (f, x)
3: Sample a batch B { 1. ), (I2, 92)..... (Zb, }b)}
4:
Compute the averaged gradient for each layer 9d == Ei Vo,
5:
Sample per-layer noise: Sa (0, oAa).
6:
Perform perturbed gradient step: 0₂ +- Oa- nigs + Cd).
7:
Enforce Lipschitz constraint with projection: Oa (Ta))).
8: Compute new (e, 6)-DP guarantees with privacy accountant.
9:
until privacy budget (e, has been reached.
al. 2023), used sampling without replacement at each epoch (by shufiling examples), but we reported assuming Poisson sampling to benefit from privacy amplification (Balle et al.) 2018).
SIGNAL-TO-NOISE RATIO ANALYSIS
We discuss how the tightness of the bound provided by Algorithm can be controlled.
3.1 THEORETICAL ANALYSIS OF CLIPLESS DP-SGD
In cases we can manually derive the bounds across diverse configurations.
Theorem (informal) 1. Gradient Norm of Lipschitz Networks. Assume that every layer fa is K K-Lipschilz, i.e =.... =...=ip>> In
Assume that every bias bounded by B. We further assume that each activation is centered at zero (i.e fa = O, like ReLU, (roupSort...).Then the global upper bound of Algorithm@cca be computed analytically, as follows:
1. If K < 1 we have: [[ x), y)ll2 O (L (K + 1)).
Due the KD < 1 term this corresponds vanishing gradient phenomenon (Pascanu al. 2013
The oulput of the network is essentially independent of its inpul, and training is nearly impossible.
2. If K 1 have: VoL(f( 1) O (I.KD (Xo B 1)).
Due to the KD > 1 term this corresponds to an exploding gradient phenomenon (Bengio al.
1994). The upper bound becomes vacuous for deep networks: the added noise will be too high.
If = we have: [oL(f(() v) = o (VD XovD VBXoD + BD3/2)
which for linear layers without biases further simplify to O(LVD(1 + Xo)).
The formal statement can found in appendix. We see that most favorable bounds are achieved by 1 I-Lipschitz neural networks with 1-Lipschitz layers. In classification tasks, they are expressive as conventional networks (Béthune et al. 2022). Hence, this choice of architecture is not at the expense of utility. Moreover accuracylrobustness trade-off exists, determined by the choice of loss function (Béthune et al., 2022). However, setting K = merely ensures that || Vr < 1, and in the worst-case scenario we could have || |/V'/'| < almost everywhere. This results in situation where the bound of case in Theorem i not tight, leading to an underfitting regime as in the case K 1. With Gradient Norm Preserving (GNP) networks, we expect to mitigate this issue.
Controlling K with Gradient Norm Preserving (GNP) networks. GNP (Li et al. 2019a) net- works are 1-Lipschitz neural networks with the additional constraint that the Jacobian of layers consists of orthogonal matrices. They fulfill the Eikonal equation 0fa(O..za)
for any interme-
dza 1l
diate activation fa(aa, As consequence, the gradient of the loss with respect the parameters

---

is bounded by
i Afa(Os: vaa) 00d a
0fa(Oa. Fd) 00d
Vo..
V yD C1I
II AeiSD
V yn C|
(7)
Or,
which for weight matrices Wa further simplifies to V[V ClI
Fd-1) Il. We see that this upper bound crucially depends on two terms than can be analyzed separately. On the one hand, 1 Id-1)]l depends on the scale of the input. On the other, | ClI depends on the loss, the predictions and the training stage. We show below how to intervene on these two quantities.
< V Lll
Controlling Xo with input pre-processing. The weight gradient norm || Ww,C/ indirectly depends on the norm of the inputs. Multiple strategies are available to keep this norm under control: projection onto the ball ('norm clipping") ) or projection onto the sphere ("normalization"). In the domain of natural images, this result sheds light on the importance of color space: RGB, HSV, etc. Empirically, a narrower distribution of input norms would make up for tighter gradient norm bounds.
Controlling T. with the hybrid approach: loss gradient clipping As training progresses, the magnitude of C tends to diminish when approaching local minima, falling below the upper bound and diminishing the signal to noise ratio. Fortunately, for Lipschitz constrained networks, the norm of the seementwise-gradiee remains lower bounded throughout (Béthune et al., (022). Since the noise amplitude only depends on the architecture and the loss, and remains fixed during training, the loss with the best signal-to-noins to-se ratio would be a loss whose gradient norm w.r.t the logits remains constant during training. For the binary classification case, with labels y E (-1,+ this yields the loss L y) = yý. that arises in Seantorovic--Rubinntei duality (Villani 2008):
inf (ew))-((xx(((t)) (iPP = 7. (EC(-Li(D,.))
where Wi(P, is the Wasserstein-1 distance between the two classes P and Q.
Another way to ensure high signal-to-noise ratio is to diminish the noise and clip the gradients of the loss w.r.t the logits. We emphasize that this is different from the clipping of the "parameter gradient" VeL done DP-SGD. Here, any intermediate gradient f&f can be clipped during backpropagation. This can be achieved with special "clipping layer" that behaves like the identity function at the forward pass, and clips the gradient during the backward pass. DP-SGD the clipping is applied on the element-wiss gradient Vw, L of size b x h22 for matrix weight Wa E Rh and batch size b. and clipping it can cause memory issues or slowdowns (Lee & Kifer 2021). our case, V C is of size b x h: this is far smaller, especially for the last layer. Moreover, this clipping is compatible with the adaptive clipping introduced by (Andrew et al., 2021}: the quantiles of || V CII can be privately estimated for a small privacy budget. This allows to effectively reduce the noise while ensuring that most of the gradients remain unbiased. Furthermore, this bias of this clipping can be characterized.
Proposition (informal) 1 (Bias of loss gradient clipping in binary classification tasks). Let LBC be the binary cross-entropy loss, with sigmoid activation. Assume that the loss gradient (w.rt the logits) V yg [L y) is clipped to norm at most C >>0 0. Then there exists C² >> 0 such that for all C S C' gradient descent step with the clipped gradient is identical in direction to the gradient descent step obtained from the loss LKR(0
R( v) -- .g..
As observed in Serrurier et al. (021) and Béthune et al. (2022) this descent direction yields classifiers with high certifiable robustness, but lower clean accuracy. Therefore, in practice, we set the adaptive clipping threshold at not less than the 90%-th quantile to mitigate the bias and avoid utility drop.
3.2 LIP-DP LIBRARY
To foster and spread accessibility, we provide an open source TensorFlow library for Clipless DP- SGD training named 1 lip-dp, with Keras API. The code is available at httpt:tt:///// / com com/Algue-Rythree 1 Its usage is illustrated in Figure We rely on the deel-11 lig library Semurier et al. 2021) enforce Lipschitz constraints in practice, with Reshaped Kernel
pddp- 58A1 distributed under MIT License.
https://giittbbb.cmm/deee-- distrihuted under MIT License.
7

---

1.00
Validation AUROC 1
Dataset
Size
Dim. 6
0.90
Clipless DP-SGD
DP-SGD
ALOI
39,627
27
10-s
56.5
56.2
0.70
campaign
32,950
10-5
90.0
82.2
0.60
celeba
162,079
10 6
96.6
96.5
0.50
census
239,428
500
10-6
92.5
Validate
0:40
Clipless DP:SGD: Pareto frant (2016)
donors
495,460
10-6
100.0
100.0
magic
15.216
5
90.7
89.7
Bu et (2019)
shuttle
39,277
5
98.3
99.4
0.20
Chen & Lee (2020)
skin 196,045
3
10
100.0
99.8
0.10
Papernot (2021)
Feldman Zrnic (2020)
yeast 1,187
8
10
66.8
75.1
(a) AUROC values (in for models trained under
0.0
1.0
1e-5
2.0
3.0
6)DP privacy with on binary classification tasks
tabular data from Adbench datasets Han et al. (2022) We random stratified split into train (80%) validation (20%).
(b) Pareto front Mnist. Each green dot corre- sponds to (val. acc, c) pair from an epuch.
Figure 3: Comparison of the utility of DP-SGD and Clipless DP-SGD on tabular and image data.
Orthogonalization (RKO) for fast and near-orthogonal convolutions Lii al. 2019b). The Lipschitz constraint is enforced by using activations with known Lipschitz. constant la (most activations fulfill this condition), and by applying projection constraints correspond to spectrally normalized matrices Yoshida & Miyato (017);; Bartlett et al.
1² θ on the weights of affine layers. These
(2017). since for affine layers we have la |Wall 22= == max [Walll2 and therefore ||=|||
[[all S
l. We rely Power Iteration for fast computation of the spectral
The leading eigenvector
is cached from a step to another to speed-up computations. The seminal work of Anil et al. (2019)
proved that universal approximation the set of é-Lipschitz functions was achievable by this family
of architectures. In practice, GNP networks are parametrized with GroupSort activation Anil et al. (2019; Tanielian & Biau (2021), Householder activation Mhammedi al. (2017) and orthogonal weight matrices Li et al. 2019abb)
Remark 2 (GNP networks limitations). Strict orthogonality is challenging to enforce, especially for convolutions for which it is still an active research area (see Trockman & Kolter (2027); Singla & Feizi (2021b); Achour et al. (2022); (Singla & Feizi 2:02)]: Xu et al. (2022) and references therein). Our line of work traces an additional motivation for the development of GNP and the bounds will strengthen as the field progresses. Concurrent upproaches bused on regularization (Gulrajani el al.
2017
Cisse el al. 2017: Gouk et al. (027)) fail to produce formal guarantees.
4 EXPERIMENTAL RESULTS
We validate our implementation with speed benchmark against competing approaches, and we present the privacy/utility Pareto fronts that can be obtained with GNP networks.
4.1 EVALUATION OF PRIVACY, ACCURACY AND ROBUSTNESS
For the comparisons, we leverage the DP-SGD implementation from Opacus. We perform search over broad range of hyper- the privacy loss that may induced by this syper-parameter search, which is a limitation per recent studies like Papernot& & Steinke (2022) or Ding & Wu (2022).
values: the configuration is given in Appendix D We ignore
Accuracy and Privacy. We validate the performance of our approach on tabular data from Adbench suite (Han et al. 2022) using a MLP, and report the result in Table 3a For MNIST (Fig. 3b we use Lipschitz LeNet- like architecture.
Robustness and Privacy. One of the most prominent advantage of Lipchitz networks is their ability to provide robustness certificates against adversarial attacks, and was the primary motivation for
their development (Szegedy et al. 2014| Li et al., 2019a Fazlyab et al. 2019). For a é-Lipschitz classifier f, with predictions & arg max; J& the decision is invariant under perturbation of norms smaller than 1 (fx(z) arg max, fe (z)). Therefore, for each perturbation radius r
8

---

0.55
Robustness radius
0,50
Validation accuracy
0.45
0.40
1/255
0.35
== 2/255
0.30
0.25
8/253
0.20
16/255
0.15
Algorithm
0.10
[Lipschitz] Clipless DP-SGD
0.05
[Unconstrained] DP-SGD
2.0
4.0
10.0
12.0 14.0
Privacy budget & at 6 le
Figure Privac/accurayy/obsttess trade-off on Cifar-10: We report the pareto front of robustness certificates at different radii r for Lipschitz constrained networks, while unconstrained networks cannot produce robustness certificates. Models are trained in an "out pre-training, data augmentation and no handcrafted features. To ensure fair comparison between algorithms, we perform 30 repetitions with Bayesian optimizer to select the best prpper-prramters.
box setting": no
can measure the accuracy of the perturbed network, and we report these results in Fig. The computation the certificates straightforward, while methods applicable to conventional networks (like randomized smoothing (Cohen et al. 2019) interval propagation, see remark T are expensive. This suggests that robust decisions and privacy are not necessarily antipodal objectives, contrary to what was observed in [Song et al. (201)). The work of Wu al. (2023) also study the link between certified robustness and privacy, albeit through the lens of adversarial training (Zhang et al. 2019).
4.2 SPEED AND MEMORY CONSUMPTION
We benchmarked the median runtime per batch of vanilla DP-SGD against the of Cli- pless DP-SGD, on a CNN architecture and its Lipschitz equivalent respectively. The ex- periment
GPU with 48GB video memory. We compare against the im- plementation of t tf_privacy, opacus and optax. In order to allow fair com- parison, when evaluating Opacus, reported the runtime with respect the logical batch size, while capping the physical batch size to avoid Out Of Memory error (OOM).
B
An advantage of the projection over per- sample gradient clipping is that its cost is in- dependent of the batch size. Fig validates that our method scales much better than vanilla DP. SGD, and is compatible with large batch sizes. It offers several advantages: firstly, a larger batch size contributes to a decrease of the sensitivity x 1/b, which diminishes the ratio between noise and gradient norm. Secondly, the batch size increases, the variance decreases at the parametric rate O ((VT) (as demonstrated in ap- pendix [. aligning with expectations. This observation does not apply to DP-SGD: clipping biases the direction of the average gradient, as noticed by Chen al. 2020
[opacus]
[lo-db] Cipless DP-SGD
[optax] DP SGD
prhayyl DP
Median Runtime
parameters
130K
1.5
510K
2,000K
0.
[imi:: 48616)
0.0
Figure 5: Our approach outperforms concur- rent frameworks terms runtime and mem- ory: we trained CNNs (ranging from 130K to 2M parameters) on CIFAR-10 10, and report the median batch processing time (including noise, and con- straints application II or gradient clipping).
LIMITATIONS, FUTURE WORK AND BROADER IMPACT
Our framework offers a novel approach to address differentially private training, but also introduces new challenges. Clipless DP-SGD replaces bias of optimizer with bias in function space (as

---

discussed in Appendix A.4). We primary rely on GNP networks, where high performing architectures are quite different from the usual CNN architectures. This serves as (1) a motivation to further develop Gradient Norm Preserving architectures. As emphasized in Remark 2 anticipate that progress in these areas will greatly enhance the effectiveness of our approach. Additionally, to rely projections, necessitating additional efforts to incorporate "trivializa- tions" tions" Trockman & Kolter (2021); Singla & Feizi (2021b). Finally, as mentioned in Remark our propagation bound method can be refined. Comparison of Clipless DP-SGD with recent methods based on back-propagatiee propagation, in particular Bu et al. (223). is discussed in appendix A.5 Furthermore, the development of networks with known Lipschitz constant with respect to parameters a ques- tion of independent interest, making 1 lip-dp (2) useful tool for the study of the optimization dynamics Lipschitz constrained neural networks.
meet requirement
CONTRIBUTIONS
The design and the theoretical analysis has been conducted by Louis Béthune and Thomas Masséna. The lip-dp package has been created by Louis Bethune, Thomas Masséna, and Thibaut Boissin. The experiments have been run by Louis Béthune, Thomas Masséna, Thibaut Boissin, Yannick Prudent, and Corentin Friedrich. Proofreading, writing, and feedback are joint contribution of all authors.
ACKNOWLEDGMENTS
Louis thanks Fabian Pedregosa for its detailed feedback. The authors thank Agustin Picard for its proofreading.
This work has benefited from the Al Interdisciplinary Institute ANITI, which is funded by the French "Investing for the Future PIA3" program under the Grant agreement ANR-19-P3IA-0004, The authors gratefully acknowledge the support of the DEEL project
This work was supported by grant LNR-20-CE23-0015 (Project PRIDE) and the ANR 02-PECY-0002 IPOP (Interdisciplinary Project on Privacy) project of the Cybersecurity PEPR.
httpp::/ http://wwwwwwwwd.eeee deel /
10

---

REFERENCES
Martin Abadi, Andy Chu, lan Goodfellow, 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-318, 2016.
P-A Absil, Robert Mahony, and Rodolphe Sepulchre. Optimization algorithms on matrix manifolds. Princeton University Press, 2008
El Mehdi Achour, François Malgouyres, and Franck Mamalet. Existence, stability and scalability of orthogonal convolutional neural networks. The Journal of Machine Learning Research, 23(1): 15743-15798, 2022.
Airbus. Decomon.
com http:/tuw...oom/iiiis///eeeettte 2023.
Mário S Alvim, Miguel E Andrés, Konstantinos Chatzikokolakiss Pierpaolo Degano, and Catuscia Palamidessi. Differential privacy: on the trade-off between utility and information leakage. In Formal Aspects of Security and Trust: 8th International Workshop, FAST 2011, Leuven, Belgium, September 12 12-14, 2011 Revised Selected Papers 8, pp. 39-54. Springer, 2012.
Galen Andrew, Om Thakkar, Brendan McMahan, and Swaroop Ramaswamy. Differentially private learning with adaptive clipping. Advances in Neural Information Processing Systems, 34:17455- 17466, 2021.
Cem Anil, James Lucas, and Roger Grosse. Sorting out lipschitz function approximation. In International Conference on Machine Learning, pp. 291-301. PMLR, 2019.
Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial networks. In International conference on machine learning, pp. 223. PMLR, 2017.
Borja Balle, Gilles Barthe, and Marco Gaboardi. Privacy amplification by subsampling: Tight analyses via couplings and divergences. Advances Neural Information Processing Systems, 31, 2018.
Peter L Bartlett, Dylan J Foster, and Matus Telgarsky. Spectrally-normaaizze margin bounds for neural networks. In Proceedings of the 3 International Conference on Neural Information Processing Systems, pp. 6241-6250, 2017.
Yoshua Bengio, Patrice Simard, and Paolo Frasconi. Learning long-term dependencies with gradient descent is difficult. IEEE transactions on neural networks, 5(2):157-166, 1994.
Louis Béthune, Thibaut Boissin, Mathieu Serrurier, Franck Mamalet, Corentin Friedrich, and Al- berto Gonzalez Sanz. Pay attention to your loss understanding misconceptions about lipschitz neural networks. Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022. URL hattps:/ mett/forum21d=RRIIDEER
Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration inequalities: A nonasymptotic
theory of independence. Oxford university press, 2013.
Olivier Bousquet and André Elisseeff. Stability and generalization. The Journal of Machine Learning Research, 2:499-526, 2002.
Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
Zhiqi Bu, Jialin Mao, and Shiyun Xu. Scalable and efficient training of large convolutional neural networks with differential privacy. Advances in Neural Information Processing Systems, 35:
88305-38318, 2022a.
Zhiqi Bu, Yu-Xiang Wang, Sheng Zha, and George Karypis. Automatic clipping: Differentially private deep learning made easier and stronger. arXiv preprint arXiv:2206.07/166 2022b.
Zhiqi Bu, Yu-Xiang Wang, Sheng Zha, and George Karypis. Differentially private optimization large model at small cost. In International Conference on Machine Learning, pp. 3192-3218. PMLR, 2023.
11

---

Sébastien Bubeck et al. Convex optimization: Algorithms and complexity. Foundations and Trends@ in Machine Learning, 8(3-4):231-357, 2015.
Xiangyi Chen, Steven Z Wu, and Mingyi Hong. Understanding gradient clipping in private sgd:
geometric perspective. Advances in Neural Information Processing Systems, 33:13773-13782 2020.
Moustapha Cisse, Piotr Bojanowski, Edouard Grave, Yann Dauphin, and Nicolas Usunier. Parseval networks: Improving robustness to adversarial examples. International Conference on Machine Learning, pp. 854 863. PMLR, 2017.
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. In Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 1310-1320. PMLR, 2019.
Soham De, Leonard Berrada, Jamie Hayes, Samuel Smith, and Borja Balle. Unlocking high- accuracy differentially private image classification through scale. arXiv preprint 133330 2022.
Youlong Ding and Xueyang Wu. Revisiting hyperparameter tuning with differential privacy, arXiv preprint arXiv:2211.0183) 2022.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3, pp. 265-284 Springer, 2006.
Cynthia Dwork, Aaron Roth, al. The algorithmic foundations differential privacy. Foundations and Trends in Theoretical Computer Science, 9(3-4):211 4)7211-4077 2014.
Mahyar Fazlyab, Alexander Robey, Hamed Hassani, Manfred Morari, and George Pappas. Efficient and accurate estimation of lipschitz constants for deep neural networks. Advances in Neural Information Processing Systems, 32, 2019.
David Goldberg. What every computer scientist should know about Seating-poine arithmetic. ACM computing surveys (CSUR), (3(1):5-48, 1991.
Henry Gouk, Eibe Frank, Bernhard Pfahringer, and Michael J Cree. Regularisation of neural networks by enforcing lipschitz continuity. Machine Learning, 110:393-44 416, 2021.
Ishaan Gulrajani, Faruk Ahmed, Martin Arjovsky, Vincent Dumoulin, and Aaron C Courville. Improved training of wasserstein gans. In Advances in Neural Information Processing Systems, volume 30, pp. 5767-5777. Curran Associates, Inc., 2017.
Songqiao Han, Xiyang Hu, Hailiang Huang, Mingqi Jiang, and Yue Zhao. Adbench: Anomaly detection benchmark. In Neural Information Processing Systems (NeurIPS), 2022.
Jiyan He, Xuechen Li, Da Yu, Huishuai Zhang, Janardhan Kulkarni, Yin Tat Lee, Arturs Backurs, Nenghai Yu, and Jiang Bian. Exploring the limits of differentially private deep learning with group-wise clipping. In The Eleventh International Conference on Learning Representations, 2022.
Hadi Jooybar, Wilson WL Fung, Mike O' O'Connor, Joseph Devietti, and Tor M Aamodt. Gpudet: a deterministic gpu architecture. In Proceedings of the eighteenth international conference on Architectural support for programming languages and operating systems, pp. 1-12, 2013.
Jaewoo Lee and Daniel Kifer. Scaling up differentially private deep learning with fast per-example gradient clipping. Proceedings on Privacy Enhancing Technologies, (121(1), 2021.
Lisha Li, Kevin Jamieson, Giulia DeSalvo, Afshin Rostamizadeh, and Ameet Talwalkar. Hyperband: A novel bandit-busee approach to hyperparameter optimization. The Journal of Machine Learning Research, (8())6765-6811 2017.
12

---

Qiyang Li. Saminul Haque, Cem Anil, James Lucas, Roger B Grosse, and Jöm-Henrik Jacobsen. Preventing gradient attenuation in lipschitz constrained convolutional networks. In Advances in Neural Information Processing Systems (NeurlPS), volume 32, Cambridge, MA, 2019a. MIT Press.
Shuai Li, Kui Jia, Yuxin Wen, Tongliang Liu, and Dacheng Tao. Orthogonal deep neural networks.
IEEE transactions pattern analysis and machine intelligence, 43(4):1352 1368, 2019b.
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.
Colin McDiarmid et al. On the method of bounded differences. Surveys in combinatories, 141(1): 148-188, 1989.
Brendan McMahan, Daniel Ramage, Kunal Talwar, and Li Zhang. Learning differentially private recurrent language models. In International Conference on Learning Representations, 2018.
Laurent Meunier, Blaise Delattre, Alexandre Araujo, and Alexandre Allauzen. A dynamical system perspective for lipschitz neural networks. In International Conference on Machine Learning, pp. 15500. PMLR, 2022.
Zakaria Mhammedi, Andrew Hellicar, Ashfaqur Rahman, and James Bailey. Efficient orthogonal parametrisation of recurrent neural networks using householder reflections. International Conference on Machine Learming, pp. 2401-2409. PMLR, 2017.
Ilya Mironov. Rényi differential privacy. In 2017 IEEE 30th computer (CSF), pp. 263-275. IEEE, 2017.
symposium
Ilya Mironov, Kunal Talwar, and Li Zhang. Réenyi differential privacy of the sampled gaussian mechanism. arXiv preprint arXiv:/900 10530, 2019.
Takeru Miyato, Toshiki Kataoka, Masanori Koyama, and Yuichi Yoshida. Spectral normalization for generative adversarial networks. arXiv preprint arXiv:1802.05957 2018.
Nicolas Papernot and Thomas Steinke. Hyperparameter tuning with renyi differential privacy. In International Conference on Learning Representations, 2022. URL httt:tt:t//peeereee//
net/ Foormmid== 70L8 10081pp900 pD
Nicolas Papernot, Abhradeep Thakurta, Shuang Song, Steve Chien, and Úlfar Erlingsson. Tempered sigmoid activations for deep learning with differential privacy. In Proceedings of the AAAI Conference Artificial Intelligence, volume 35, pp. 9312-9321, 2021.
Razvan Pascanu, Tomas Mikolov, and Yoshua Bengio. On the difficulty of training recurrent neural networks. In International conference on machine learning, pp. 1310-1318. Pmlr, 2013.
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 2rX.5:2303.0065. 2023.
Tom Sander, Pierre Stock, and Alexandre Sablayrolles. Tan without burn: Scaling laws of dp-sgd. arXiv preprint arXiv:2210.03400 2022.
Mathieu Serrurier, Franck Mamalet, Alberto González-Sanz, Thibaut Boissin, Jean-Michel Loubes, and Eustasio Del Barrio. Achieving robustness in classification using optimal transport with hinge regularization. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 505-514, 2021.
Yonadav Shavit and Boriana Gjura. Exploring the use of lipschitz neural networks for automating the design of differentially private mechanisms. Technical report, Technical Report, 2019.
Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. Membership inference attacks against machine learning models. In 2017 IEEE symposium on security and privacy (SP), pp. 3-18. IEEE, 2017.
13

---

Leon Simon et al. Lectures geometric measure theory. The Australian National University, Mathematical Sciences Institute, Centre ..., 1983.
Gagandeep Singh, Timon Gehr, Markus Püschel, and Martin Vechev. An abstract domain for certifying neural networks. Proceedings of the ACM on Programming Languages, 3(P0PL) 2019.
S Singla and S Feizi. Fantastic four: Differentiable bounds on singular values of convolution layers. In International Conference on Learning Representations (ICLR), 2021a.
Sahil Singla and Soheil Feizi. Skew orthogonal convolutions. In International Conference on Machine PMLR, 2021b.
Learning, pp.
Sahil Singla and Soheil Feizi. Improved techniques for deterministic 12 robustness. arXiv preprint arXiv:2211.08453, 2022.
Jasper Snoek, Hugo Larochelle, and Ryan P Adams. Practical bayesian optimization of machine learning algorithms. Advances in neural information processing systems, 25, 2012.
Liwei Song and Prateek Mittal. Systematic evaluation of privacy risks of machine learning models. In 30th USENIX Security Symposium (USENIX Security 21). pp. 2615-2632, 2021.
Liwei Song, Reza Shokri, and Prateek Mittal. Privacy risks of securing machine learning models against adversarial examples. In Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, pp. 241-257, 2019.
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In International Conference Learning Representations, 2014. hetlhhtp:///rxeee
Qiaoyue Tang and Mathias Lécuyer. Dp-sgd-If: Improving utility under differentially private learning via layer freezing. openreview preprint, 2022. URL
COLECLTHF'bN
Ugo Taniclian and Gerard Biau. Approximating lipschitz continuous functions with groupsort neural networks. In International Conference on Artificial Intelligence and Statistics, pp. 442-450. PMLR, 2021.
Iya O Tolstikhin, Neil Houlsby, Alexander Kolesnikov, Lucas Beyer, Xiaohua Zhai Thomas Un- terthiner, Jessica Yung, Andreas Steiner, Daniel Keysers, Jakob Uszkoreit, et al. Mip-mixer: An all-mlp architecture for vision. Advances in neural information processing systems, 34:24261- 24272, 2021.
Florian Tramer and Dan Bonch. Differentially private learning needs better features (or much more data), 2021.
Lloyd N Trefethen and David Bau. Numerical linear algebra, volume 181. Siam, 2022.
Asher Trockman and J Zico Kolter. Orthogonalizing convolutional layers with the cayley transform. In International Conference on Learning Representations, 2021. URU/attps:/opeeeevieee
met//ooumm: 1 JEHV
Dmitrii Usynin, Alexander Ziller, Moritz Knolle, Andrew Trask, Kritika Prakash, Daniel Rueckert, and Georgios Kaissis. An automatic differentiation system for the age of differential privacy. arXiv preprint arXiv:2109.10573 2021.
Cédric Villani. Optimal transport: old and new, volume 338. Springer Science & Business Media, 2008.
Aladin Virmaux and Kevin Scaman. Lipschitz. regularity of deep neural networks: analysis and efficient estimation. Advances in Neural Information Processing Systems, 31, 2018
Ruigang Wang and Ian Manchester. Direct parameterization of lipschitz- bounded deep networks. In International Conference Machine Learning, pp. 36093-361 10. PMLR, 2023.
14

---

Yu- Yu-Xiang Wang, Borja Balle, and Shiva Prasad Kasiviswanathan. Subsampled rényi differential privacy and analytical moments accountant. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 1226-1235. PMLR, 2019.
Jiapeng Wu, Atiyeh Ashari Ghomi, David Glukhov, Jesse C Cresswell, Franziska Boenisch, and Nicolas Papernot. Augment then smooth: Reconciling differential privacy with certified robustness. arXiv preprint arXiv:2306.066 08656, 2023.
Kaidi Xu, Zhouxing Shi, Huan Zhang, Yihan Wang, Kai- Wei Chang, Minlie Huang. Bhavya Kailkhura, Xue Lin, and Cho-Jui Hsieh. Automatic perturbation analysis for scalable certi- fied robustness and beyond. Advances in Neural Information Processing Systems, 13:1129-1141, 2020.
Xiaojun Xu, Linyi Li, and Bo Li. Lot: Laser-wise orthogonal training improving 12 certified robustness. arXiv preprini arXiv:2210.116200 2022.
Xiaodong Yang, Huishuai Zhang, Wei Chen, and Tie-Yan Liu. Normalized//lippee sgd with per- turbation for differentially private non-convex optimization. arXiv preprint arXiv:2206. 13033, 2022.
Yao- Yuan Yang, Cyrus Rashtchian, Hongyang Zhang, Russ R Salakhutdinov, and Kamalika Chaud- huri. A closer look at accuracy vs. robustness. Advances in Neural Information Processing Systems, 33, 2020.
Samuel Yeom, Irene Giacomelli, Matt Fredrikson, and Somesh Jha. Privacy risk in machine learning: Analyzing the connection to overfitting. In 2018 IEEE 31st computer security foundations symposium (CSF), pp. 268-282. IEEE, 2018.
Yuichi Yoshida and Takeru Miyato. Spectral norm regularization for improving the generalizability of deep learning. arXiv preprint arXiv: 1705. 10941, 2017.
Ashkan Yousefpour, Igor Shilov, Alexandre Sablayrolles, Davide Testuggine, Karthik Prasad, Mani Malek, John Nguyen, Sayan Ghosh, Akash Bharadwaj. Jessica Zhao, Graham Cormode, and llya Mironov. Opacus: User-friendly differential privacy library in Py'Torch, arXiv preprint arXiv:2109.1 12298, 2021.
Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric Xing, Laurent El Ghaoui, and Michael Jordan. Theoretically principled trade-off between robustness and accuracy. In International conference on machine learning, pp. 7472-7482. PMLR, 2019.
Huan Zhang, Tsui-Wei Weng, Pin-Yo Yu Chen, Cho-Jui Hsieh, and Luca Daniel. Efficient neural network robustness certification with general activation functions. Advances in neural information processing systems, 31, 2018.
Yuqing Zhu and Yu-Xiang Wang. Possion subsampled rényi differential privacy. In International Conference on Machine Learning, pp. 7634-7642. PMLR, 2019.
Yuqing Zhu and Yu-Xiang Wang. Improving sparse vector technique with renyi differential privacy. Advances in Neural Information Processing Systems, 0-222299-22555 2020.
Alexander Ziller, Dmitrii Usynin, Moritz Knolle, Kritika Prakash, Andrew Trask, Rickmer Braren,
Marcus Makowski, Daniel Rueckert, and Georgios Kaissis. Sensitivity analysis in diffcrentially private machine learning using hybrid automatic differentiation. arXiv preprint arxiv:2107.04200 2021.
15

---

CONTENTS
Introduction
2
Clipless DP-SGD with E-Lipschitz networks
2.1
Backpropagation for bounds
3
Signal-to-noise ratio analysis
3.1
Theoretical analysis Clipless DP-SGD
3.2
Lip-dp library
4
Experimental results
Evaluation of privacy, accuracy and robustness
4.2
Speed and memory consumption
Limitations, future work and broader impact
Definitions and methods
18
A.I
Additionnal background
18
A.I.I
Lipschitz neural networks background
18
A.1.2
Gradient Norm Preserving networks
18
A.1.3
Background on Differential Privacy
19
A.2
Privacy accounting of Clipless DP-SGD
20
A.3
Robustness certificates of Lipschitz constrained networks
20
A.4
Bias of Clipless DP-SGD
21
A.5
Efficiency of gradient clipping
21
B I.
Lipdp tutorial
21
B.
Prerequisite: building a E-Lipschitz network
23
B.2
Getting started
................................
23
B.3
Image spaces and input clipping
25
B.3.1
Color space representations
................................
25
B.3.2
Input clipping
25
B.4
Practical implementation of Residual connections
25
B.5
Loss-logits gradient clipping
27
B.5.1
Possible improvements
28
Computing sensitivity bounds
28
Lipschitz constants of common loss functions
28
Layer bounds
30
C.2.1 Dense layers
30
16

---

C.2.2 Convolutions
31
C.2.3
Layer normalizations
32
22,4
MLP Mixer architecture
33
Tightness in practice
33
D Experimental setup
35
Tabular data
35
D.2
Pareto fronts
................................
36
D.2.1
Hyperparameters configuration for MNIST
37
D.2.2
Hyperparameters configuration for FASHION-MNIST
37
D.2.3
Hyperparameters configuration for CIFAR-
37
D.3
Contiguration of the "speed" experiment
38
Compatibility with literature improvements
38
D.5
Drop-in replacement with Lipschitz networks in vanilla DPSGD
39
D.6 Extended limitations
39
Proofs of general results
41
Variance of the gradient
Background for main result
42
Main result
42
17

---

A DEFINITIONS AND METHODS
A.1 ADDITIONNAL. BACKGROUND
The purpose of this appendix provide additionnal definitions and properties regarding Lipschitz Neural Networks, their possible GNP properties and Differential Privacy.
A.1.1 LIPSCHITZ NEURAL NETWORKS BACKGROUND
For simplicity of the exposure, we will focus on feedforward neural networks with densely connected layers: the affine transformation takes the form of matrix-vector product h ++ Wh. In Section C.2 we tackle the case of convolutions / + V/ + with kernel V.
Definition 4 (Feedforward neural network). feedforward neural network of depth T, with input space X C R and with parameter space @ C IR, is parameterized function O x X y defined by the following recursion:
ho(x) I, h₂(r) == oz)(x))
=x(x) == W;he-1(z) + dt,
[(0, x)) == (T))
(9)
The set of parameters is denoted as (W, bi)sTTT-+ the output space as D C CRK (e.g logits), and the layer-wise activation as R R...
Definition 5 (Lipschitz constant). The function f R + R is said I-Lipschitz for l2 norm for every x, y E tM we have:
(1(()) [())l12 < 1|| yl1-- Per Rademacher's 's theorem Simon et al. (1983), its gradient is bounded: [ S I. Reciprocally, continuous functions gradient bounded by 1 are L-Lipschitz.
(10)
Definition (Lipschitz neural network). A Lipschitz neural network is feedforward neural network with the additional constraints:
the activation function a is S-Lipschitz. This is standard ussumption, frequenily fulfilled in practice.
the affine functions + Wx + b are ULLipschitz, ie [ < U. This is achieved in practice with spectrally normalized matrices Yoshida & Miyato (2017) Bartlett et al. (2017). The feasible set is the ball { ([[W])2 U} of radius U (which is convex), subset of thereof (not necessarily convex).
As a result, the function + f(0,z) ((UUS)-Lipschitz.ffo Lipschitz all E e.
Two strategies available to enforee Lipschitzness:
1. With a differentiable reparametrization IT: RRP θ where 0 (T)):: the weights 0 are used during the forward pass, but the gradients are pack-propagated to 0 through 11. This turns the training into unconstrained optimization problem on the landscape of [ f 11.
2. With suitable projection operator 11: R + O: this is the celebrated Projected Gradient Descent (PGD) algorithm Bubeck et al. (2015) applied on the landscape of L f.
For arbitrary re- ce-parametrizations, option can cause some difficulties: the Lipschiz constant of 11 is generally unknown. However, if θ is convex then II is 1 I-Lipschitz (with respect to the norm chosen for the projection). To the contrary, option elliciss broader set of feasible sets O. For simplicity, option 2 will be the focus of our work.
1.1.2 GRADIENT NORM PRESERVING NETWORKS
Definition (Gradient Norm Preserving Networks). GNP networks are 1-Lipschitz neural networks with the additional constraint that the Jacobian of layers consists of orthogonal matrices:
Qfa Fx,
O
=
(11)
Oxa
18

---

Layers (d)
Adaptive composition
Stochastic batches
Composition scross train steps
(a, 83-RDP
(Re, 83-RP
(a. 6) RDP
(ay, R-RDP
Train steps
Gaussian mechanism of sensitivity Ad
Non isotropic
Subsampling Mechanism
(t)
Gaussian Mechanism
Figure 6: Accountant for locally enforced differential privacy. (i) The gradient query for each layer made private using the Gaussian mechanism Dwork et al. (2014); (ii) their composition across the layers of the whole network can be from amplification via sub-sampling Balle et al. (2018); (iv) the train steps are composed over the course of training.
isotropic Gaussian mechanism, (iii) that benefits
This is achieved with GroupSort activation Anil et al. (2019). Tanielian & Biau (027)) Householder activation Mhammedi et al.) (2017), and orthogonal weight matrices Li al. (20
orthogonal
convolutions (see Achour et al.) (2022); y Singla & Feizi (2022) ; u et al. [0022 and references therein).
Without biases these networks are also norm preserving: [ (1,000))
|0||
The of orthogonal matrices (and its generalization the Stiefel manifold Absil et al. (2008) is not convex, and not even connected. Hence projected gradient approaches are mandatory: for re-parametrization methods the Jacobian D0 consequences sensitivity.
AM may be unbounded which could have uncontrollable
A.1.3 BACKGROUND ON DIFFERENTIAL PRIVACY
Definition 8 (Neighboring datasets). A labelled dataset 'D is a finite collection of input/label pairs D = ((11, y1), (22, (2), ...)................. yN)). Two datasets DD and DD' are said to be neighbouring if they differ by at most one sample: D' D (2',, (2), -(zi, y.).
The sensitivity is also referred algorithmic stability Bousquet & Elisseeff (2002), bounded differences property in other fields McDiarmid et al. 1989). We detail below the building a Gaussian mechanism from arbitrary query of known sensitivity.
Definition 9 (Gaussian Mechanism), Let lz-sensitivity A()), a Gaussian mechanism adds noise sampled from (0, o())))( to the query J. Property 1 (DP of Gaussian Mechanisms). Let G(f). be Gaussian mechanism of le-sensitivity S2(f) adding the noise (00 o.))(f)) to the query f. The DP guarantees of the mechanism are given by the following continuum: /2. log(1.22 (1225/8)/e.
R be query accessing the dataset of known
SGD is composition of queries. Each of those query consists of sampling minibatch from the dataset, and computing the gradient of the loss on the minibatch. The sensitivity the query is proportional to the maximum gradient norm 1, and inversely proportional to the batch size b. By pertubing the gradient with Gaussian noise of variance o² 12 fz the query is transformed into Gaussian mechanism. By composing the Gaussian mechanisms we obtain the DPSGD variant, that enjoy (c. 8D guarantees.
Proposition (DP guarantees for SGD, adapted from Abadi et al. (2016).). Assume that the loss fulfills C 2)ll2 I l, and assune that the network is trained on a dataset of size N with SGD algorithm for steps with noise scale (10, o²) such that:
16K WKK/Tloog (2/5) log (1.25T /
(12)
Ne
Then the SGD training of the network is 8)-P)
19

---

A.2 PRIVACY ACCOUNTING OF CLIPLESS DP-SGD
The "global" strategy. This strategy simply aggregates the individual sensitivities Aa of each layer to obtain the global sensitivity of the whole gradient vector A 2 A The origin of the clipping-basee version of this strategy can be traced back to McMahan et (2018). With noise variance A² we recover the accountant that comes with DP-SGD. It tends to overestimate the true sensitivity (in particular for deep networks), but its implementation is straightforward with existing tools. We detail in Algorithmp the the global variant of our approach.
The "per-layer" strategy. Recall that we are able to characterize the sensitivity A of every layer of the network. Hence, can apply a different noise to each of the gradients. We dissect the whole training procedure in Figure 6
1. On each layer, we apply a Gaussian mechanism with noise variance o²
2. Their composition yields an other Gaussian mechanism with non isotropic noise.
3. The Gaussian mechanism benefits from privacy amplification via subsampling (Balle et al. 2018) thanks to the stochasticity in the selection of batches of size b p.V.
4. Finally epoch is defined as the composition of T sub-samples mechanisms.
At same noise multiplier o, "per-layer" strategy tends produce higher value of per epoch than the "global" strategy, but has the advantage over the latter to add smaller effective noise Ç to each weight. Different layers exhibit different maximum gradient bounds and turn this implies different sensitivities. This also suggests that different noise multipliers can be used for each layer. This open extensions for future work.
For practical computations, we rely on the aut outodp library (Wang et al. 2019 Zhu & Wang 2019 2020) as it uses the Rényi Differential Privacy (RDP) adaptive composition theorem (Mironov 2017 Mironov et al. 2019), that ensures tighter bounds than naive DP composition.
Algorithm 3 Clipless DP-SGD with global sensitivity accounting
Input: Feed-forward architecture f(--)) = fr+1 (0r+1,-) fr (Or, o.... fo Input: Initial weights Op, learning rate scheduling noise multiplier o.
1: repeat
2: Ag... AT+1 + compute compute_gradient (ounds(f.X)
3: Sample a batch B, { y1), (z2,, y2),.... ... (Is, yb)}
4: Compute the mean gradient the batch for each layer t:
9. = b :=1
Σ ((h..)))
5: For each layer of the model, get the theoretical bound of the gradient:
V1 S < b. V C(ir, yi ye) S A..
6: Update Moment accountant state with global sensitivity A = 3
E
T+1
A?
7: Add global noise N0, 20 A/b to each weights and perform projected gradient step:
0, + 11(0, 7(.. ()).
8: Report new (c, DDP guarantees with accountant. until privacy budget (c, 8) has been reached.
9:
A.3 ROBUSTNESS CERTIFICATES OF LIPSCHITZ CONSTRAINED NETWORKS
The temperature parameter r of softmax has strong influence the certificates. The models with the most robust decisions are not the ones with the best clean accuracy, which is compliant with the observations of Béthune al. (2022).
20

---

Memhership
Softmax Temperature
Certifiable accuracy at radius r r/255
Inference Attacks
0
r
r=
4
= 8
16
AUROC
Adv.
0.01
47.4
5.9
0.1
0.0
0.0
0.0
59.8
23.9
0.22
44.4
39.1
34.2
24.9
11.5
0.8
50.1
15.0
0.40
41.6
38.4
35.6
29.6
19.1
5.3
50.0
11.3
0.74
38.4
36.4
34.7
30.9
24.1
13.0
$1.9
20.5
2.77
33.3
32.2
31.2
29.3
25.9
18.8
52.5
21.3
5.40
32.5
31.4
30.4
28.8
25.5
19.7
59.7
23.6
Table I: Certifiable accuracy scores under (20.0, 10 10- D)-DP training on Cifar-10 dataset. For
each targeted robustness radius r/255, we optimize over softmax-crossennin -rossentropy temperature т, and report the best value. We also monitor the best AUROC and the best attacker Advantage (Adv.)|Yeom Yeom al. (2018) achieved by two popular membership inference attacks: threshold attacks [Song Mittal (202 and a logistic regression shadow model Shokri et al. (0117).
A.4 BIAS OF CLIPLESS DP-SGD
Clipless DP-SGD also exhibits bias, but this bias takes a different form than the bias induced by clipping in DP-SGD.
The bias the optimizer. In DP-SGD (with clipping) the average gradient is biased by the elementwise clipping. Therefore, the clipping may slow down convergence or lead to sub-optimal solutions.
The bias of the model in the space in Lipschitz networks. This bias of the model, of the optimizer. It has been shown that any classification task could be solved with a I-Lipschitz classifier (Béthune
al., (022), and in this sense, the bias induced by the space of 1-Lipschitz functions is not too severe. Better, this bias is precisely what allows to produce robustness certificates, see for example Yang et al. (2020).
Finally, there is the implicit bias. is induced by given architecture on the optimizer, which can have strong effects on effective generalization. For neural networks (Lipschitz or not), this implicit bias is not fully understood yet. But even large Lipschitz models, it seems that the Lipschitz constraint biases the network toward better robustness radii but worse clean accuracy, as frequently observed in the relevant literature.
Therefore, these biases influence the learning process differently, and they constitute two distinct (not necessarily exclusive) approaches. We illustrate the difference between these paradigms in Figure 7
A.5 EFFICIENCY OF GRADIENT CLIPPING
Beyond the conventional implementation of gradient clipping that can be found in Opacus Tf- privacy, recent developments proposed more efficient forms clipping, or to get rid of the clipping introduced by Abadi et al. (2016) and to use renormalization instead.
In this regard, we can mention the works of Bu al. (2022b) or Yang et al. (202)) that study alternative implementations of clipping based on renormalization, which climinates the need to tune the clipping value, with convergence guarantecs.
Other works study the alternative implementation of clementwise clipping to reduce the computational cost, like Bu et al. (2022a), Li et al. (2021) He et al. (2022), and Bu et al. (2023). Taking inspiration from Bu et (2023) summarize each one in Tables and
B LIPDP TUTORIAL
This section gives advice how start your DP training processes using the framework. Moreover, it provides insights into how input pro-procsssing, building networks with Residual connections and Loss-logits gradient clipping could help offer better utility for the same privacy budget.
21

---

Instantiating per-sample gradient
Instantiating non-DP gradient
Overhead
Storing every layer's gradient
Number of pack-propagations
independent
batch size
non-DP DP
X
X
TF-Privacy, like Abadi et al. 2016)
X
B
Opacus Youserpour
al.
2021)
V
X
FastGradClip (I Lce & Kifer 2021
X
X
2
X
GhostClip (Li ct al. 2021 Bu ct al.
2022a
X
X
V
I
X
Beek-neeping [B el al. 2023
X
X
X
X
Clipless w/ Lipschitz (ours)
X
X
V
Clipless GNP (ours)
X
Table 2: Comparison of DP-SGD against existing techniques of literature. Clipless DP-SGD is the only technique whose time/memory overhead depends exclusively on weight matrices but not the batch size.
Time Complexity Overhead
Memory Overhead
non-DP
TF-Privacy, like Abadi et al.
2016
(BBTpd
Opacus YYuueepour al. 2021
(dBTpd)
O (Bpd)
FastGradCIip (Lee & Kiler
2021
(BBTpd)
O (Bdd
GhostClip (Li et al. 2021; Bu et 2022a)
O (BT BT
(
Book-Keeping (Bu et al. 2023)
O O(BTpd) (UU
O B min(pd, T2))
Clipless w/ Lipschitz (ours)
Clipless w/ GNP (ours)
OlUpd + V pd min(p. d))
0
Table 3: Time and memory costs for each method for feedforward networks. We assume weight matrices of shape p x d, and a physical batch size For images, is width. U is number of iterations in Power Iteration algorithm, and V the number of iterations in Björck projection. Typically U, V < 15 in practice. The overhead is taken relatively to non-DP training without clipping. This table is largely inspired from Bu al. (2023).
Blased trajectory in large fumction space
Unbiased trajectory in smaller function space
Conventional deep neural networks
Conventional deep neural networks
0,
Lipschitz deep
neural networks
Blased gradient [clipped]
Unbiased gracient
θ
Unbissed gradient
Figure 7: Comparison between the bias DP-SGD with clipping, and Clipless DP-SGD, One an instance of optimizer bias, and the other of function space bias.
22

---

B.1 PREREQUISITE: BUILDING É-LIPSCHITZ NETWORK
As per def 3 I-Lipschitz neural network of depth d can be built by composing V/ layers. In the rest of this section we will focus on 1-Lipschitz networks (rather than controlling we control the loss to obtain the same effects Béthune et al. (0222). In order to do the strategy consists in choosing only 1 1-Lipschhtzz activations, and to constrain the weights of parameterized layers such that it can only express I-Lipschitz functions. For instance normalizing the weight matrix of dense layer by its spectral norm yield I-Lipschitz layer (this, however cannot be applied trivially on convolution's 's kernel.. In practice we used the layers available in the open-source library deel-lip. In practice, when building a Lipschitz network, the following block can be used:
Dense layers: are available as SpectralDense or QuickSpectralDense which apply spectral normalization and Björck orthogonalization, making them GNP layers.
Relu activations replaced by Groupsor12 activations, and such activations are GNP, preventing vanishing gradient.
pooling layers are replaced with ScaledL2NormPPolingg which is GNP since it performs the operation x + (I|=m||b l22m where is the multi-index of patch of contiguous pixels.
normalization layers like BatchNorm are not K-Lipschitz. We did not accounted these layers since they can induce a privacy leak (as they keep a rolling mean and variance). A I-Lipschitz drop-in replacement is studied in C.2.3 The relevant literature also propose drop-in replacement for this layer with proper sensitivity accounting.
Originally, this library relied on differentiable re-parametrizatioon, since it yields higher accuracy outside DP training regime (clean training without noise). However, our framework does not account for the Lipschitz constant of the re-parametrization operator. This is why we provide QuickSpectralennse and QuickSpectralCom22D layers to enforce Lipschitz constraints, where the projection is enforced with tensorflow constraint. Note that SpectralDense and SpectralConv20 can still be used with a Condense through the differentiable re- p-parametrization. However this last solution, while being closer to the original spirit of deel-lip, is also less efficient in speed benchmarks.
to enforce the projection, and bypass the back paopaaropngttion
The Lipschitz constant of each layer is bounded by 1, since each weight matrix is divided by the largest singular value Fmax. This singular value is computed with Power Iteration algorithm. Power Iteration computes the largest singular value by repeatedly computing Rayleigh quotient asssociated to a vector u, and this vector eventually converges to the eigenvector umax associated to the largest eigenvalue. These iterations can be expensive. However, since gradient steps are smalls, the weight matrices W, and Ws+1 remain close to each other after a gradient step. Hence their largest eigenvectors tend be similar. Therefore, the eigenvector tmmax be memorized at the end of each train step, and re-used as high quality initialization at the next train step, in a "lazy" fashion. This speed-up makes the overall projection algorithm very efficient.
B.2 GETTING STARTED
The framework we propose is built to allow DP training of neural networks in fast and controlled approach. The tools we provide are the following
1. A pipeline to efficiently load and pre-process the data of commonly used datasets like MNIST, FashionMNIST and 1I
2. Configuration objects to correctly account DP events we provide config objects to fill in that will
3. Model objects on the principle of Keras' model classes we offer both a DP_ DP_Model and DP Sequential class to streamline the training process.
4. Layer objects where we offer a readily available form of the principal layers used for DNNs. These layers are already Lipschitz constrained and possess class specific methods to access their Lipschitz constant.
5. Loss functions, identically, we offer DP loss functions that automatically compute their Lipschitz constant for correct DP enforcing.
23

---

We highlight below example of full training loop Mnist with lip-dp library. Refer to the "examples" folder the library for more detailed explanations in a jupyter notebook.
dp parameters DPParameters
noise_mulee mess__mltippieer22.1 delta=lc-5,
epsilon_may
input_ upper__pper____ upper_bound bound 20.0
ds ds_train, destest dataset metadata = Load_and prepare_ data
"mnist", batch_size-1000, drop_remaindez-True,
bound [aand___ttbood___ll___lllll
input_upper_boond
)
construct DP_ Sequenttiii model DP Sequential
1ayers-[
layers. DD {P_BouneedInput
input_shae saapeeddattset_mttaddeee input_iptttti shapee apper_bounde
input_ upper bound
layers. DP QuickSpectralConv22)
filters-32,
kernel_sizert
kernel_init strides-1, use bie_bias=
)
layers. DP_ Dtt...osorrooott[[]
layers DP Scaledd2NorrPPoooinggg (pool_size=2 strides=2),
layers DP QuickSpectzalconv22)
filters-64,
kernel_size-3,
strides=1,
use bias=False,
),
layers. BB__DD_________ (2)
layers DP SealeettNNomooooongg00 (pooolongepppoo_siieeeieeee strides-2),
layers. 2tt_laFaFeeee))
layers. DD_ QuickSpectralleense (512),
layers DP GroupSort (2),
Layers quickSpectralDense (dataset metadata. classes),
1,
dp ppp_araattessss__paaatttess, dataset_ iataaatt_mtaatttdddttseeeeeaaee
model. @odel.compile
loss=lcsses. DP htg.ruugeeeggggallrrstttttoooto
optimizer=tf. keras www.ooiiiiiis.......... SGD (Learming_rate-e-44, nomentun=0.9).
metrics= ("acuurac""
model. summary() ()
num num_epochs get_max_epoch (epsi ca_max, model)
24

---

HSBIHSV:
1500
YIG: 1724
accurences
110 18:4
Number of magee
YUV: 17.4
YUA 1213
1250
Grayscale: 17.-4
3000
Creystale: 22:55
1000
Theoretccal bound: 135.06
750
2000
1000
Gradient Norm
(a) Input norms.
(b) Gradient norms.
Figure 8: Histogram of norms for different image space CIFAR-10 images. We see that for GNP networks the distribution of dataset norms have a strong influence on the norm of the individual parameterwise gradient norms of missclassified examples. The global gradient bound is equal to 135.66 on this architecture: less than two times the maximum empirical bound of 73.
hist = model.
ds ds_train, epochs=nun epochs,
validttio__dtaard_teett. callbacks-(
i accounting is done thanks to a callback
DP Accountant (log__n==looginng)
},
B.3 IMAGE SPACES AND INPUT CLIPPING
Input preprocessing can be done in completely dataset agnostic way (i.e without privacy leakages) and may yield positive results on the models utility. We explore here the choice of the color space, and the norm clipping of the input.
B.3.1 COLOR SPACE REPRESENTATIONS
The color space of images yield very different gradient norms during the training process. Therefore, we can take advantage of this to train our DP models more efficiently. Empirically, Tigures[8aJand and [b] show that some color spaces yield narrower image norm distributions that happen to be more advantageous to maximise the mean gradient norm to noise ratio across all samples during the DP training process of GNP networks.
B.3.2 INPUT CLIPPING
A clever way to narrow down the distribution of the dataset's norms would be to clip the norms of the input of the model. This may result in improved utility since a narrower distribution of input norms might maximise the mean gradient norm to noise ratio for misclassified examples. Also, advocate for the use of GNP networks as their gradients usually turn out to be closer to the upper bound we are able to compute for the gradient. See Figure 9a and 9b
B.4 PRACTICAL IMPLEMENTATION OF RESIDUAL CONNECTIONS
The implementation of skip connections is made relatively straightforward in our framework by the make res i duals method. This function splits the input path in two, and wraps the layers inside the residual connections, illustrated in figure 10
from 1ipép.1ayers import make residuals
25

---

spectral
3000
11#2
danse, spectral spectral_denss_2. 1946
Number cl occurence
d 6a1
1200
2000
1000
Theoeetkcal hound 78.38 for each lager
800
1500
800
500
Gracient Norm
Gradient Norm
(a) Conventional network.
(b) Gradient Norm Preserving network.
Figure 9: Gradient norms of fully-connected networks CIFAR-10. We see that GNP networks exhibit a qualitatively different profile of gradient norms with respect to parameters, sticking closer to the upper bound we able to compute for the gradient norm. The GNP network does not biases, therefore all layers hare the same bound of 78.38 for their gradient norm. Not too far away from the maximum empirical bound of 56 initialization.
Conv2D
DP lp_SpiitResidual
DP WrappedResidual
DP MP_MereRRssidall
make_residuue
Figure 10: Implementation of a skip connection in the lip-dp framework. The meta block DP WrappedResidual handle the forward propagation and the backward propagation of pairs of bounds (one for each computation path) by leveraging the forward and the backward of sub- blocblocs. tuple of input bounds at the forward, and collapse the
DP SplitResidual handle the creation tuple of gradient bounds into a scalar at the backward, while DP_ MP_MergeRssidun does the opposite. All those operations are wrapped under the convenience function make residuasss
## Manual implementation of residual connection:
layers IDP SpLitResidual (),
DP "_NNrappeeHessduual dual (DP rpickkppectraalonvv22 (16, (3, 3)
du__rrappedResidualll (DP (DP_
(DP_rrouosorrrr GrtppSorrrrrtttteeoeo (2)),
DP op_MergeResiduall ('d-iip-dddd)
# equivalently, with helper function:
layers make residuals(
DP QuickSpectzalConv2) (16, (3, 3),
DP Gr..pSorrrrtttooo (2)
})
By using this implementation, the sensitivity of the gradient computation and the input bounds to each layer are correctly computed when the model's 'ss path is split. This allows for fairly easy implementations of models like the MLP-Mixer and ResNets. Since convolutional models may suffer from gradient vanishing and that dense based models are relatively restrictive in terms of architecture, implementing skip connections could be useful feature for framework.
26

---

B.5 LOSS-LOGITS GRADIENT CLIPPING
The advantage of the traditional DP-SGD approach is that through hyperparameter optimization on the global gradient clipping constant, we indirectly optimize the mean signal to noise ratio on missclassified examples. However, this clipping constant is not really explainable and rather just an empirical result of optimization on a given architecture and loss function.
Importantly, our framework is compatible with more efficient and explainable form of clipping. As more and more examples are correctly classified, the magnitude of | tend to diminish over the course of training, quickly falling below the upper bound and diminishing the gradient norm to noise standard deviation ratio. Gradient clipping strategy is still available in our framework. But instead of clipping the parameter gradient VoL. any intermediate gradient C can be clipped during backpropagation. Indeed, by introducing a "clipping layer" that behave like identity function at the forward pass, and clip the gradient during the backward pass, we able to clip the gradient of the loss on the final logits for a minimal cost.
Indeed, in this case the size of the clipped vector is the output dimension (g], which is small for lot of practical regression and classification tasks. For example in CIFAR-10 the output vector is of length 10. This scales better with the batch size than the weight matrices that are typically of sizes 64 x 64 or 128 x 128. More precisely, in vanilla DP- SPD the per-weight gradient clipping is applied on the batched gradient Vw,,C which is a tensor of size b 122 for matrix weight Wa E Rexh In privacy it is not unusual to have 6 and h in the [102, 10 range. Clipping this vector can cause memory issues or slowdowns Lee & Kifer (202T). However V / is of size 6 x h which is significantly cheaper to clip. Note that the resulting "gradient" vector is not true gradient anymore in strictly mathematical sense, but rather a "descent direction" Boyd & Vandenberghe (2004).
Furthermore, if the gradient clipping layer is inserted on the tail of the network (between the logits and the loss) we can characterize its effects on the training, in particular for classification tasks with binary cross-entropy loss.
We denote by C(Clipp(() identity x + x at the forward, and clips the gradient norm C > in the backward pass:
(0) the loss wrapped under a DP_ pl_CliGrradiet layer that behaves like
Va (C(Clip(())) = min (1,
V ( vg((o)
(13)
VgC(ÿ)
min (IV
(14)
V+C(0)|
We denote by 9(ū) the unit norm vector v.C(S) [V,,( Then:
vg (C(ClipS (i)) min (IVv C)
Proposition 2 (Clipped binary cross-entropy loss is the Wasserstein dual loss). Let LBCE - -log (a (ūn)) be the binary cross-entropy loss, with (ūy) T+exp(-in)) the sigmoid activation, assuming discrete labels y E (-1,+1)- Assume examples are sampled from the dataset DD Let x0,2z) = f(0,a x) be the predictions at input I E D. Then for every C > 0 sufficiently small, gradient descent step with the clipped gradient V VoEp (DCCCCC (ÿ. v))] is identical to the gradient ascent step obtained from Kantorovich- Rubinstein
inntonoiic--Rubinsteenn loss CKR(D.0) 3) by.
Proof. In the following use the short notation L in place of L Assume that examples with labels +1 (resp. -1) are sampled from distribution P (resp. Q). By definition:
Vo (ů. v))] Vo [ x), +1)) + (c- -1))))
Observe that the output of the network is a single scalar, hence g(0) E [-1,+1]. We ap- ply the chainrule VoL y o(0) min (V) We note R(g = min (()), C) > O and we obtain:
VoE, CoLlIC(CCip (g. v))] = Vo (60 C x) E. 11.. (15)
27

---

Observe that the value of g can actually be deduced from the label y, which gives:
VoED L(ü: v)] = -Bg- [R( Vo) x)] + E C)VoS(0, Observe that the function + V (()) piecewise-continouss when the loss ÿ + L(y y) is piecewise continuous. Observe that VV (()) is non zero, since the loss L. does not achieve its minimum over the open set (-o0, + to0), since (ū) E (0,1). Assuming that the data æ E D lives in compact space (or equivalently that P and Q have compact support), since + [v,((i) is piecewise continuous (with finite number of pieces for finite neural networks) attains its minimum C" > 0. Choosing any C C" implies that R(ú, C) = C, which yields:
(16)
V VgED (CClip ( (0. v))l = -E PEE.r(CVVooe of x)] + E Bz- -B -C (E. Vof (E. -
This corresponds to a gradient ascent step of length C on the Sutttrovvic-RRubinseee (KR) objective LKR(ū v) fy. This loss is named after the Kantorovich Rubinstein duality that arises in optimal transport, than states that the Wasserstein-1 distance is a supremum over I-Lipschitz functions:
(P,QQQ FEI-Lip(D.R)
sup
En- [=])]] [
(17)
Hence, with clipping C small enough the gradient steps are actually identical to the ones performed during the estimation of Wasserstein-1 distance.
The adaptive clipping of Andrew al. (2021) takes the form of Gaussian mechanism the implementation of the RDP accountant is straightforward.
In future works, other multi-class losses be studied through the lens of per-example clipping. Our framework permits the use of gradient clipping while at the same time faciliting the theoretical anaysis.
B.5.1 POSSIBLE IMPROVEMENTS
Our framework is compatible with possible improvements in methods of data pre-processing. For instance some works suggest that feature engineering is the key to achieve correct utility/privacy trade- off Tramer& & Bonch (2021) some other work rely heavily over-parametrized networks, coupled with batch size De et al. (2022). While we focused on providing competitive and reproducible baselines (involving minimal preeppoccssing and affordable compute budget) work is fully compatible with those improvements. Secondly the field of GNP networks (also called orthogonal networks) is still active field, and methods to build better GNP networks will improve the efficiency of our framework ( for instance orthogonal convolutions Achour et al. (2022 Li et al. ( Trockman & Kolter ) & Feizi (2021b) are still an active topic).
(2019b) Li et al. (2019a) Finally some optimizations specific to our framework can also be developed: a scheduling of loss- logits clipping might allow for better utility scores by following the declining value of the gradient of the loss, therefore allowing for better mean signal to noise ratio across a diminishing number of miss-classified examples. Observe that our framework is also compatible with other ideas, such as the progressing freezing of deeper layers proposed by Tang & Lécuyer (202)).
C COMPUTING SENSITIVITY BOUNDS
C.1 LIPSCHITZ CONSTANTS OF COMMON LOSS FUNCTIONS
This section contains the proof's related the content of Table 4 Our framework wraps over some losses found in deel-lip library, that are wrapped by our framework to provide Lipschitz constant automatically during backpropagation for bounds.
Multiclass Hinge
This loss, with min margin m is computed in the following manner for a one-hot encoded ground truth vector y and logit prediction ÿ
LMH (ann(ū.) (ū.v) v) = (Inax(0, 2 91-91), max(O, m
2 - -.-
And || 2 Cun 2 & |1 Therefore Ia
28

---

Loss
Hyper-parameters
L y)
Lipsehitz bound
Softmax Cross-entropy
temperature
y" log softmax (g)t)ax(g/T)))
V2/T 1/ 1/Xmio
Cosine Similarity
bound Xii >> 0
y'v
max
Xmm
Multiclass Hinge
margin m N/A
max (0,
Uc- hSiSK
{Ū. y)
margin m > 0
Hinge Santorovvic-RRubesseee
a.Lar v) + CMKR(U, y)
1 + a
regularization
Table 4: Lipschitz constant of common supervised classification losses used for the training of Lipschitz neural networks with & classes. Proofs in Section C.1
Multiclass Kantorovich Rubenstein This loss, computed in a one-versus all manner, for one-hot encoded ground truth vector y and logit prediction y
LMKR(Ú. y) {ú) V1 ........ 2h yn)}
Therefore, by differentiating, also get LKR 1.
Multiclass Hinge Kantorovitch Rubenstein This loss, is computed in the following manner for one-hot encoded ground truth vector y and logit prediction ğ
LMHKR(0.9) 8) aCMu (b.9) CMKRR(,,))
By linearity get LIKR = 1.
Cosine Similarity Cosine Similarity is defined in the following manner element-wise:
Los(9.v) 12
And y is one-hot encoded, therefore Los(ū. v) T Therefore, the Lipschitz constant of
this loss dependant on the minimum value of ÿ. reasonable assumption would be Va E
X Xmin S ||ar||2 I X Mmax- Furthermore, if the networks are Norm Preserving with factor K, we ensure that:
KX min l1 S KX
Which yields: Lcs KXmmn The issue is that the exact value of K is never known in advance since Lipschitz networks are rarely purely Norm Preserving in practice due to various effects (lack of tightness in convolutions, or rectangular matrices that can not be perfectly orthogonal).
Realistically, we propose the following loss function in replacement:
Di
Lx- Cx-cs(Ú.v) max max(XX XXin 111122)
Where K an input given by the user, therefore enforcing Tx- KXmmn
Categorical Cruss-entropy from logits The logits are mapped into the probability simplex with the Softmax function TR (0, k We also introduce temperature parameter 0, which hold signifance importance in the accuracy/robustnes tradeoff for Lipschitz networks as observed by Béthhne et al. (2022). We assume the labels discrete, one-hot encoded: do not cover the case of label smoothing.
exp(Tū;) S Σ Exp((T(s)
(18)
29

---

Hyper
(0,
Layer
parameters
1-L-ipscitz dense
none
Convolution
window
RKO convolution
image size H W 1/((1
window $
(h
(1
far
2H
2W
Table Lipschitz constant with respect to parameters in common Lipschitz layers. We report only the multiplicative factor that appears in front of the ipput norm ||a|||.
Hyper
Layer
parameters
Oz
Add bias
none
1
I-Lipschitz dense
none
RKO convolution
none
1
Layer centering
none
Residual block
none
2
ReLU, GroupSort
none 1
softplus, sigmoid, tanh
Table 6: Lipschitz constant with respect to intermediate activations.
We denote the prediction associated to the true label j as SJ1. The loss is written as:
( = log(S)+).
(19)
Its gradient with respect to the logits is:
V&C = T(S - SS
ifj= otherwise
(20)
The temperature factor 7 a multiplication factor than can be included in the loss itself, by using 1 instead of C. This formulation has the advantage of facilitating the tuning of the learning rate: this is the default implementation found in deel-lip library. The gradient can be written vectorized form:
VgC = S ((j=st)
By definition of Softmax have EjØØ+ 57 5 1. Now, observe that S (0,1), and
consequence (S,+ 1)² < 1. Therefore || Eieji $3 + (Sz+ - 1)2 < 2. Finally |V 2 and LOCE V2.
C.2 LAYER BOUNDS
The Lipschitz constant (with respect to input) of each layer of interest is summarized in table 6 while the Lipschitz constant with respect to parameters is given in table 5
C.2.1 DENSE LAYERS
Below, we illustrate the basic properties of Lipschitz constraints and their consequences for gradient bounds computations. While for dense layers the proof is straightforward, the main ideas can be re-used for all linear operations which includes the convolutions and the layer centering.
Property 2. Gradients for dense Lipschitz networks. Let E BC be data data-point in space of dimensions C E N. Let W E RCXF be the weights of a dense layer with F features outputs. We bound the spectral norm of the Jacobian
D(WT x)
< ||11|2-
(21)
OW
2
30

---

Proof. Since W + W x is linear operator, its Lipschitz constant is exactly the spectral radius:
[ W z122 II(W W') |W W 12 12|a=|2 |W 2
|
I|W W
| W
Finally, observe that the linear operation x + W x is differentiable, hence the spectral norm of its Jacobian equal its Lipschitz constant with respect norm.
C.2.2 CONVOLUTIONS
Property 3. Gradients for convolutional Lipschitz networks. Let RSCC be data-po ttia-point with channels C' E N and spatial dimensions N. In the case of a time serie S is the length of the sequence, for image S HW is the number pixels, and for video S = HWN N is the number of pixels times the number of frames. Let V E RaxCxP be the weights of a convolution with:
window size E (e.g fwe in 2D or hwnn in 3D),
with C input channels,
with F N output channels.
we don't assume anything about the value of strides. Our bound is typically tighter for strides= and looser for larger strides.
We denote the convolution operation as (v= * * SxC + RXF with either zero padding, either circular padding, such that the spatial dimensions are preserved. Then the Jacobian of convolution operation with respect to parameters is bounded:
V = x)
12 S V8
(22)
NV
Proof. Let = a E RXF be the output of the convolution operator. Note that y can be uniquely decomposed as sum of output feature maps Σ/= od where yd E Sx F is defined as:
(w'r Vif for all 1 isis (v0) =0 if +
Observe that (y")Ty" 0 whenever f + f'. As consequence Pythagorean theorem yields 1lyl Ef=1 llv l2.. Similarly we can decompose each output feature map as sum of pixels r ΣS E y where nd SxF fulfill:
(ypr) (yPS) los = ypf
if if p.j # f. otherwise.
Once again Pythagorean theorem yields || = -E 1= 1 12. remains to bound yd appropri- ately. Observe that by definition:
p = (V x) = (w-r) [T (s)).
where y E R is slice of v corresponding to output feature map f. and ['[s] E R denotes the patch of size s centered around input element For example, in the case of images with = 3 x 3, p are the coordinates of pixel, and [?(s] [s] are the input feature maps of 3 pixels around it. We apply Cauchy- Schwar-Sc
31

---

By summing pixels obtain:
11
112
|| Σ
|. (s) 1111:
(23)
p=1
P
1lul2
11:)
|,00 (s]
1))))
(24)
llll2 <
V
12
| [s] [s]]|
(25)
The quantity of interest is > S-m1 |>*[s]] used in the computation. With zero circular padding, the norm of the patches cannot exceed those of input image. Note that each pixel belongs atmost & patches, and even exactly s patches when circular padding is used:
whose squared norm is the squared norm of all the patches
S
S S 10
Σ
s 8|
Note that when strides>1 the leading multiplicative constant is typically smaller than s, so this analysis can be improved in future work to take into account strided convolutions. Since v is linear operator, its Lipschitz constant is exactly its spectral radius:
( x) (VV 2)]l2
[I
V
V
V112||0112
V
12
12
V
12
Finally, observe that the convolution operation V is differentiable, hence the spectral norm of its Jacobian equal to its Lipschitz constant with respect to l2 norm:
V x))
12 S 12/22/22
important case of interest are the convolutions based on Reshaped Kernel Orthogonalization (RKO) method introduced by et al. (2019)). The kernel Vi is reshaped into 2D matrix of dimensions (sC's x F) and this matrix is orthogonalised. This not sufficient to ensure that the operation & +> +ur is orthogonal however it is 1-Lipschitz and only approximately orthogonal under suitable re-scaling by N > 0.
Corollary (Loss gradient for RKO convolutions.). For RKO methods in 2D used in Serrurier et al. (2027). the convolution kernel is given by + No where V is orthogonal matrix (under RKO)
and N > a factor ensuring that x. +> T * x is 1-Lipschitz operation. Then, for RKO convolutions
without strides we have:
V
x
12
1
(26)
2V
(1
(h-1)
w
2H
where (H, W) are image dimensions and (h, w) the window dimensions. For large images with small receptive field (as it is often the case), the Taylor expansion in h < H and w & W yields a factor of magnitude (h-1) (w-1)
+ O (w--1) 1)(A-1)) 1.
4H
4W
8HW
C.2.3 LAYER NORMALIZATIONS
Property 4. Bounded loss gradient for layer centering. Layer centering is defined as f(z) I En= 24)1 where 1 is a vector full of ones, and acts as "centering" operation along some channels (or all channels). Then the singular values of this linear operation are:
σ1 = 0, and 02 = 03
=
(27)
In particular 31 1/
32

---

Proof. It clear that layer normalization is an affine layer. Hence the spectral norm of its Jacobian coincides with its Lipschitz constant with respect to the input, which itself coincides with the spectral norm of f. The matrice M associated to f is symmetric and diagonally dominant since |ل=س| - - It follows that M is semi-definite positive. In particular all its eigenvalues Xn are non negative, Furthermore they coincide with its singular values: Ø; X Observe that for all E I we have f(r1) O, i.e the operation is null on constant vectors. Hence A1 = 0. Consider the matrix M - 1: its kernel is the eigenspace associated to eigenvalue 1. But the matrix M- I =1 =111 a rank-one matrix. Hence its kernel is of dimension n 1, from which
A
follows that 22 = An 02
=
C.2.4 MLP MIXER ARCHITECTURE
The MLP-mixer architecture introduced in Tolstikhin al. (202T) consists of operations named Token mixing and Channel mixing respectively. For token mixing, the input feature is split in disjoint patches on which the same linear opration applied. It corresponds equal to the kernel size. convolutions on a reshaped input, where patches of pixels are "collapsed" in channel dimensions. Since the same linear transformation is applied on each patch, this can be interpreted block diagonal matrix whose diagonal consists of W repeated multiple times. More formally the output of Token mixing takes the form of f(z)= == [WT ø1, W "2"=22.... zz.... W' x,. where [1,, T2....... ., is the input, and the x; 's are the patches (composed of multiple pixels). Note that [=) < E || = | layer 1-Lipschitz it the
convolution with a stride
= [| [ If || 1 then the norm preserving. Same reasoning apply for Channel mixing. Therefore architecture is I-Lipchitz and the weight sensitivity is proportional to ||-|||
Lipschitz MLP mixer: We adapted the original architecture order to have an efficient 1 1-Lipschitz version with the following changes:
Relu activations were replaced with GroupSort, allowing better gradient norm preservation,
Dense layers replaced with their GNP equivalent,
Skip connections available (adding 0.5 factor to the output in order to ensure 1 1-lipschitz condition) but architecture perform as well without these.
Finally the architecture parameters were selected as following:
1. The number of layer is reduced to a small value (between and 4) to take advantage of the theoretical sensitivity bound.
2. The patch size and hidden dimension are selected to achieve sufficiently expressive network (a patch size between 2 and achieves sufficient accuracy without over-fitting, and a hidden dimension of 128-512 unlocks allows batch size).
3. The channel dim and token dimensions are chosen such that weight matrices are square matrices (exact gradient norm preservation property requires square matrices).
C.3 TIGHTNESS IN PRACTICE
In our experiments on Cifar- 10 the best performing architecture was MLP Mixer with a single block of mixing. We measure the theoretical bounds with our framework at the start of training in Fig. 11 and at the end of training in Fig. 12
We see that the last layer benefits from bounds that are quite tight (around 30% to 50%) whereas the tightness drops for the deeper layers in MLP blocks (less than 10%). The explanation is that the bound
@Sa(Oa:)) d0g
||
Od)
(28)
might be overly pessimistic, because of the Xa-1 term, especially since Cauchy-Schward inequality is a "best-case bound" (i.e assuming that all vector involved in the inner product are co-linear), and do not account for the possible orthogonality between Fy and the cotangent vector. Nonetheless, with ratio of 4% we that the noise and the gradient norm are of similar amplitude soon as
33

---

Ratio between elementwise empirical gradient theoretical bound, epach
densse/ernel
den1e 1.kernel
dense 2/kernel
1.2
1.50
1.50
1.0
1225
1.00
0.15
0.4
3.50
0.50
0.2
3.25
0.25
danso, 3/kernel
demss 4 Wekrrl
denso, 5/Kemnel
2.0
0.25
1.5
1.5
0.20
Densky
Dencey
Densky
1.0
0.15
0.10
0.5
0.05
Figure 11: MLP Mixer on Cifar-10, first epoch.
Ratio between elementwise empirical gradient theoretical bound, epoch 221
dense/kemell
dense Likernel
dense 2/kernl
1.50
1.25
1.0
1.25
1.00
Dersity
0.8
0.75
0.75
0.50
0.4
0.2
0.25
dense 3ikernel
demse 4rkernel
dense 5/kemne
2.0
1.5
1.5
Donskt
1.0
Dansty
0.15
1.0
0.05
Figure 12: MLP Mixer on Cifar-10, last epoch.
34

---

Validation AUROCT f
Wallelock Runtime
Dataset
Samples
Features
Clipless DP-SGD
Clipless
DP-SGD
DP-SGD
DP-SGD
ALOI
39,627
27
10
56.5
56.2
159.1
11.3
campaign
32,950
62
10 5
90.0
82.2
155.6
11.8
celeba
162,079
39
10-6
96.6
96.5
41.1
34,6
census
239,428
500
10 6
92.5
820.0
79.8
donors
495,460
10
10
100.0
100.0
257.9
90.2
magic
15,216
10
90.7
89.7
89.9
56.0
shuttle 39,277
9
10
98.3
99.4
11.1
6.8
skin 196,045
3
10 10-6
6
100.0
99.8
54.2
40.2
yeast 1,187
8
10 10
66.8
75.1
22.1
5.6
Table 7: Best validation AUROC values (in %) for models trained under (e, 6D-DP privacy with with DP-SGD and Clipless DP-SGD, on binary classification tasks of tabular data from Adbench datasets Han et al. (2022). We use a random 80/20% stratified split into train/val.
MAGIC.GAMMA
CAMPAIGN
CELEBA
1.00
1000
1.00
Validalien AURO 6
0.90
0.50
0.80
0.60
0.60
0.50
0.50
0.50
0.40
0.40
0.40
0.30
0.30
0.30
0.20
0,20
0,20
0.10
0.30
0:30
Ea 0= 01
aa 0= 01
E 1e
DONORS
YEAST
CENSUS
1.00
100
1:00
Velidetio AUROC
0.90
0,90
0.50
0.80
0.80
0.50
0.70
0.50
0.60
0.60
0.60
0.30
0.30
0.30
0.20
0.20
0.20
0.10
0.10
0:30
[Lipschitz] Clipless DR-SGD
[Unconstrained] CPSCD
aat 1.
at
1
SHUTTLE
SKIN
ALOI
1.00
1:00
100
Validatton AUROC
0.90
0.90
0.50
0.80
0.50
0.50
0.70
0.70
0.30
0.60
0.60
0.60
0.50
0.30
0.50
0.50
0.20
0.20
0.20
0.10
0.10
0.30
0.2
0.4
0.6
0.8
1.0
0.2
0.4
0.6
0.8
1.0
0.2
0.4
0.6
1.0 1e
0.8
1e
eat
1e
E
Figure 13: Pareto front of AUROC values on tabular data.
the batch size exceed 1/0.04 25 examples, which is clearly our case with batch sizes that easily exceed 2, 500 on Cif
D EXPERIMENTAL SETUP
D.1 TABULAR DATA
Instead of monitoring the median result, also look for the best in each sweep, along with the average runtime. The results are also report graphically in Fig. [3 The hyper-parameters are
reported in Table
35

---

Hyper-Parameter
Minimum Value
Maximum Value
Input Clipping
None
Batch Size
512
10
Loss Gradient Clipping
automatic (90%-th percentile)
(BCE)
10-2
100
Learning Rate
0.00001
1.0
Table Hyper-parameter of Clipless DP-SGD for the Tabular experiment.
1.00
0.80
0.00
leecionn Accurdc)
0.70
0.70
Velldeeton Accurecy
0.60
0.60
0.50
0.50
0.40
0.40
Abadi (2016)
Cliptess
0.30
Cliptass D0-GGD
1201
Perato from
0.30
Bu et sl. 12019)
0.20
(2019)
Chen 12020)
Clipuess DP Pareto
0.10
Papernot (2023)
12020)
Papernot (20211
0.30
11
2.0
0.0
1.0
2.0
3.0
4.0
5,0
6.0
7.0 8.0
(a) MNIST.
(b) F-MNIST.
(c) CIFAR-10.
Our framework paints a clearer picture of the privacy/utility trade-off. We trained models in an "out of the box setting" (no pre-training, no data augmentation and no handcrafted features) on multiple tasks, Each green dot corresponds to an (accuracy, c) pair from an epoch of one of the runs, while the blue line is the Pareto front (convex hull of all the dots). While our results align with the baselines presented in other frameworks, we recognize the importance of domain-specifie Papernot et al. (202T); [Tramer]
Figure 14:
engineering. this regard, we find the innovations introduced & Boneh (2021); De et al. (2022) and references therein highly relevant. These advancements demonstrate compatibility with our framework and hold potential for future integration.
D.2 PARETO FRONTS
We rely on Bayesian optimization Snoek et al. (2012) with Hyper-band Li ct al. (2017) heuristic for early stopping. The influence of some hyperparameters has to be highlighted to facilitate training with our framework, therefore we provide table that provides insights into the effects of principal hyperparameters in Figure 15] Most hyper- parameters extend over different scales (such as the learning rate), so they are sampled according log- uniform distribution, to ensure fair covering of the search space. Additionnaly, the importance of the softmax cross-entropy temperature has been demonstrated in previous work Béthune et al. (2022).
Hyperparameter Tuning
Influence utility
Inffuence on privacy leakage per step
Increasing Batch Size
Beneficial: decreases the sensitivity.
Detrimental: reduces the privacy amplification by subsampling. No influence
Loss Gradient Clipping
Beneficial: tighter sensitivity bounds. Detrimental: biases the direction of the gradient.
Clipping Input Norms
Detrimental: destroy information, but may increases generalization
No influence
Figure 15: Hyperparameter table: Here, we give insights on the influence of some hyper- parameters on utility and privacy.
36

---

D.2.1 HYPERPARAMETERS CONFIGURATION FOR MNIST
Experiments are rum on NVIDIA GeForce RTX 3080 GPUs. The losses we optimize are either the Multiclass Hinge Kantorovich Rubinstein loss or the 7 CCE.
Hyper-Paramette
Minimum Value
Maximum Value
Input Clipping
10
Batch Size
512
10a
Loss Gradient Clipping
automatic (90%-th percentile)
(HKR)
10
2, 0.0% x 10
7 (CCE)
10
1,8 8 x 10
The sweeps were run with MLP or ConvNet architectures yielding the results presented in Figure 14a
D.2.2 HYPERPARAMETER CONFIGURATION FOR FASHION-MNIST
Experiments are on NVIDIA GeForce RTX 3080 GPUs. The losses we optimize are the Multiclass Hinge Kantorovich Rubinstein loss, the т CCE or the K-CosineSimilarit custom loss function.
Minimum Value
Maximum Value
Input Clipping
10-1
Batch Size
5.0
10S
10
Loss Gradient Clipping
automatic (90%-th percentile)
a (HKR)
10
2.0 x 10
(CCE)
10
4.0 10'
K (K-CS)
10-2
1.0
simple ConvNet architecture, in the spirit of VGG (but with Lipschitz constraints), was chosen to all sweeps yielding the results we present in Figure 14b
D.2.3 HYPERPARAMETER CONFIGURATION FOR CIFAR-10
Experiments are rum on NVIDIA GeForee RTX 3080 3090 GPUs. The losses we optimize are the Multiclass Hinge Kantorovich Rubinstein loss, the т CCE or the K-CosineSimilarit custom loss function. They yield the results of Figure 14c
Parameter
Minimum Value
Maximum Value
Input Clipping
10-2
Batch Size
512
10a
Loss Gradient Clipping
automatic (90%-th percentile)
(HKR)
10-2
2.0 10y
(CCE)
10
3.2 10'
K (K-CS)
10-2
1.0
The sweeps have been done on various architectures such Lipschitz VGGs, Lipschitz ResNets and Lipschitz MLP Mixer. We can also break down the results per architecture, in figure [6] The MLP MLP_Mixer architecture seems yield the best results. This architecture exactly GNP since the orthogonal linear transformations are applied disjoint patches. To the contrary, VGG and Resnets are based on RKO convolutions which are not exactly GNP. Hence those preliminary results are compatible with our hypothesis that GNP layers should improve performance. Note that these results are expected to change as the architectures are further improved. It is also dependant of the range chosen for hyper-parameters. We do not advocate for the use of an architecture another, and believe many other innovations found in literature should be included before settling the question definitively.
For the vanilla implementation of SGD we rely on Opacus library. We use the default configuration from the official tutorial on Cifar-10, and we define the syrem-parameters for the grid search below:
37

---

1.00
Uipschitz Architecture
0.90
VGG
MLPMixer
Resnet
Va Balcaoon accuracy
Clipless
Yu al. (2019)
Chen et al. (2020)
0.60
Papernot
0.50
0.40
0.30
0.20
at 1e
Figure 16: Accuracy/Privacy tradeoff Cifar-10, split down per architecture used. While some architectures seems to perform better than others, we don't 't advocate for the use of one over another. The results may not translate all datasets, and may be highly dependant the range chosen for hyper-parameters. While this figure provides valuable insights, identifying the best architecture is left for future works.
Parameter
Minimum Value
Maximum Value
Input
RGB standardized
Batch Size
500
5000
Noise Multiplier
Automatic
Epochs
400
Maximum
0.01
100
Gradient norm
Learning rate
0.00001
D.3 CONFIGURATION OF THE "SPEED" EXPERIMENT
We detail below the environment version of each experiment, together with Cuda and Cudnn versions. We rely on a machine with 32GB RAM and NVIDIA Quadro GTX 8000 graphic card with 48GB memory. The GPU uses driver version 495. 195.29.05. 29.05, cuda 11.5 (October 2021) and cudnn 8.2 (June 2021). We use Python 3.8 environment.
For Jax, we used jax 0.3.17 (Aug 31, 2022) with jaxlib 0.3.15 (July 23, 2022), flax 0.6.0
(Aug 17, 2022) and optax 1.4.0 (Nov 21, 2022).
For Tensorflow, we used tensorflow 2.12 (March 22, 2023) with tensorflow_privee 0.7.3 (September 1, 2021).
For Pytorch, we used Opacus 1.4.0 (March 24, 2023) with Pytorch (March 15, 2023).
For lip-dp we used deel-lip 1.4.0 (January 10, 2023) on Tensorflow 2.8 (May 23, 2022).
For this benchmark, used among the most recent packages pypi. However the latest version of tensorflow privacy could not be forced with pip due to broken dependencies. This issue arise in clean environments such the one available in google colaboratory.
D.4 COMPATIBILITY WITH LITERATURE IMPROVEMENTS
Many method from the state of the art are based on improvement over the DP-SGD baseline. this section will review these improvements and check the compatibility with our approach.
Adaptive clipping. As discussed in 3.1 or approach can benefit from adaptive clipping. Similarly this can be done in more efficient way.
38

---

Influence of Multiple Augmentations CIFAR-10 Pareto front.
0.50
0.45
Validation accuracy
0.40
0.35
0.30
0.25
0.20
Augmentations
0.15
0.10
Multiple (x2)
0.05
Multiple (x4)
12.0
Privacy budget at 6 1
Figure 17: Pareto front on Cifar-10 with the multiple augmentations trick De et al. (2022).
Multiple augmentations We tested adding "multiple augmentation" introduced by De et al. (0022) on our approach but did not yield improvements (see Appendix[17] This is probably due to the fact that train architecture from scratch: doing require architecture that requires minimum amount steps to converge. Such architecture are too small and not able to learn an augmented dataset those more prone under-fitting. Another reason is that in vanilla DP-SGD the elementwise gradients of each augmentation can be averaged before the clipping operation, which has no consequences on the overall sensitivity the gradient step. Whereas our case, the average is computed after the loss gradient clipping.
Fine tuning a pretrained backbone: Clipless DP-SGD can work with pre-trained backbone, however, the fine-tuned layers must be 1-lipschitz. This can yield 2 approaches:
Using 1-lipschitz backhone: We can then fine tune the whole network and benefits from pre-training. Unfortunately there is no I-lipschitz backbone available for the moment.
Using an unconstrained backbone: Our approach can work with an unconstrained feature extractor using the following protocol: 1. the last layers are dropped and replaced with I-Lipschitz classification network. 2. An input clipping layer added at the beginning of the classification head to ensure that the inputs bounded. This approach was tested using a MobilenetV2 backbone. Results are reported in Figure 18
D.5 DROP-IN REPLACEMENT WITH LIPSCHITZ NETWORKS VANILLA DPSGD
To highlight the importance of the tight sensitivity bounds Aa obtained by our framework, we perform an ablation study by optimizing GNP networks using "vanilla" DP-SGD (with clipping), in Figure 19a and 19h
Thanks to the gradient clipping of DP-SGD (see Algorithm 4 Lipschitz networks can be readily integrated in traditional DP-SGD algorithm with gradient clipping. The PGD algorithm is not mandatory: the propapaoonn can be performed within the computation graph through iterations of Björck algorithm (used in RKO convolutions). This does not benefit from any particular speed-up over conventional networks quite to the contrary there an additional cost incurred by enforcing Lipschitz constraints in the graph. Some layers of deel-lip library have been recoded in Jax/Flax, and the experiment was run in Jax, since Tensorflow was too slow.
We the Total Amount of Noise (TAN) heuristic introduced in Sander et al. (2022) heuristi- cally tune hyper-parameters jointly. This ensures fair covering of the Pareto front.
D.6 EXTENDED LIMITATIONS
The main weakness of our approach is that it crucially rely on accurate computation of the sen- sitivity A. This task faces many challenges in the context of differential privacy: floating point
39

---

Utility/Privacy tradeoff on CIFAR-10
1.00
validation accuracy
0.90
ClipLess DP-SGD mobilenet finetuning
0.80
0.70
0.60
0.50
0.40
0.30
0.20
0.5
1.0
2.0
4.0 E at 5 = 1e-5
8.0
Figure 18: Finetuning of a MobilenetV2 with Clipless DP-SGD. A Lipschitz MLP (1 or layers, and GroupSort activation) is trained using the backbone as feature extractor. The backbone is not fine-tuned as it is not Lipschitz. Therefore a plateau exists, depending on the quality of the feature extractor.
Algorithm 4 Differentially Private Stochastic Gradient Descent DP-SGD
Input: Neural network architecture (()-) Input: Initial weights Oo. learning rate scheduling number of steps N, noise multiplier a, L2 clipping value C.
1: repeat
2: for all <t - do
3: Sample batch
B; = (x1, 81), (I2, y2)...., (xb, yo).
4: Create microbatches, compute and clip the per-sample gradient of cost function:
Va, L(ui, vi)
Tt.i == min(C, oV, C(u v1)l
Vo, C(ss, 34)l
5: Perturb each microbatch with carefully chosen noise distribution (V(0,())
Jr.5 ge. by.
6: Perform projected gradient step:
0 + 11(0; n()r..).
7:
end for
8:
until privacy budget (c, has been reached.
40

---

1.00
UnittyPraary TrAcHOff MINIST
1.00
Unirty/reecy tradeoff CIFAR-10
DPSCD Paneto tront
0.90
0.80
Pepemot
Kause at al. (2021)
6,70
0.10
De et al. (2022)
tel Accure
0.60
0.50
0.50
0.40
6.20
DPSGD for GNP, Parcto Fortt
0.20
0.10
01
0.5
1.5 2.0
2.5
0.5
1.0
2.0
80
at 20--11m 10
r 10
(a)
(h)
Figure 19: Privacy/utility trade-off for Gradient Norm Preserving networks trained under "vanilla" DP-SGD (with gradient clipping). Each green dot corresponds to single epoch of one of the runs. Trajectories that end abruptly are due to the automatic early stopping of unpromising runs. Note that clipping + orthogonalization have a high runtime cost, which severely limits the number of epochs reported.
arithmetic is not associative, and summation order can have dramatic consequences regarding numerical stability Goldberg (99T). This is further amplified on the GPUs, where some operations are intrinsically non deterministic Jooybar et al. (2013). This well known issue is already present in vanilla DP-SGD algorithm. Our framework adds an additional point of failure: the upper bound of spectral Jacobian must be computed accurately. Hence Power Iteration must be run with sufficiently high number iterations to ensure that the projection operator II works properly. The (e, d)DP certificates only hold under the hypothesis that all computations correct, numerical errors induce privacy leakages. Hence we check empirically the effective norm of the gradient in the training reported during ours experiments, which
loop at the end of each epoch. No certificate violations suggests that the numerical errors can be kept under control.
E PROOFS OF GENERAL RESULTS
This section contains the proof' of results that are either informally presented in the main paper, either formally defined in section A.5
E. VARIANCE OF THE GRADIENT
The result mentionned in section 3.1 is based on the following result, directly adapted from a classical
result on concentration inequalities.
Corollary 2. Concentration of stochastic gradient around its mean. Assume the samples (x, v) are i..d and sampled from an arbitrary distribution We introduce the V y VoL(v, y) which function of the sample (xr, y), and its expectation ((2,))~DD (te.))-DVooll VoL(, y)}. Then for all u 2 2 the following inequality hold:
1 P( Σ
vb (u
2 Vb
-ーーーol øll uk) S exp
1
(29)
Proof. The result an immediate consequence of Example 6.3 p167 in Boucheron et al.)
2013) We
apply the theorem with the centered variable X; {(g - g) that fulfills condition X 2K
S with
e; = since [[g:]] < K. Then for every >
we have: vb
1
vb 8K2
2K ) vb
P(I
Ø
1) exp
(1
(30)
We conclude with the change of variables *
41

---

E.2 BACKGROUND FOR MAIN RESULT
The informal Theorem requires some tools that we introduce below.
Additionnal hypothesis for GNP networks. We introduce convenient assumptions for the purpose of obtaining tight bounds in Algorithm 2
Assumption (Bounded biases). We assume there exists B > O such that that for all biases ba we have ||ba|| B. Observe that the ball {1]b|/2 S B} of radius B is convex set.
Assumption 2 (Zero preserving activation). We assume that the activation fulfills a (0) O. When S-Lipschitz this implies [o(x))] S S|| for all x. Examples of activations fulfilling this constraints ReLU, Groupsort, GeLU, ELU, tanh. However it does not work with sigmoid softplus.
We also propose the assumption 3 for convenience and exhaustivity.
A Assumption 3 (Bounded activation). We assume it exists G > 0 such that for every X and every 1 DddsDe D we have:
Ihall S and
| S.
(31)
Note that this assumption implied by requiremen!
2
assumption
7 as illustrated in proposition
In practice assumption can be fulfilled with the of input clipping and bias clipping. bounded activation functions, or layer normalization. This assumption can be used as a "shortcut" in the proof of the main theorem, avoid the "propagation of input bounds" step.
E.3
MAIN RESULT
We rephrase in rigorous manner the informal theorem of section 3.1 The proofs given in section order to simplify the notations, we use x= Xu in the following.
Proposition 3. Norm of intermediate activations. Under requirement
assumptions
we have:
||vlll S S|1=el S (US)) (x (x-1)
SB (x-1-SU) 1-SU +
SB S-SU iUUS
(32)
SSX + +IB
otherwise.
In particular if there are no biases, i.e if B 0, then |hlll s S11ael1 I SX.
Proposition can be used to replace assumption 3
Proposition 4. Lipschitz constant dense Lipschitz networks with respect parameters. Let f(--)) be Lipschitz neural network. Under requirement 2 assumptions 1 1 1 T
2
have for every
2f(0,z) 2)
112 S (SU)
(33)
bb.
05 xx) aW.
1l2 <
(34)
In particular, for every x E X, the function + f(0, x0) is Lipschitz bounded.
Proposition 4 suggests that the scale of the activation ||/ || must be kept under control for the gradient scales to distribute evenly along the computation graph. It can be easily extended to general result on the per sample gradient of the loss, theorem T
Theorem 1. Bounded loss gradient for dense Lipschitz networks. Assume the predictions are given by Lipschitz neural network f:
= f(0,ar).
(35)
Under requirements assumptions loss gradient is bounded:
there exists a K > ffror all (z. EX θ the
| VVoC(. y)1l2 & K.
(36)
Let SU be the maximum spectral of the Jacobian between two consecutive layers.
42

---

If 1 then we have:
K O LSXVT LL LBST
(37)
cinicttioon The case S = 1 is of particular interest since it covers most activation function (L.e ReLU, GroupSorr):
K k-O +LWT+LXVE LVBXT+++ +BB*
(38)
Further simplification possible if we assume 0, a network without biases:
= K (LTT((+)))
(39)
If a > 1 then we have:
[eC((.))]2 -
a(SB a
SB)+ Va -1
(40)
Once again B = 0 (network with no bias) leads to usesul simplifications:
(oo((,,)) o L T+1
((a--
VTX+- v
(41)
We notice that when a > there is an exploding gradient phenomenon where the upper bound become vacuous.
a < then we have:
1 (VoC(D.))22 o (Iat (XVT+ + (1 a²)
v(1 a.) ))
XSB V Vat
SB
L
+
(1 (1- -1-o)v1-
(42)
For network without biases we get:
I. (IaXXVT++ V(1- - a)3
VoC(ū.))22
(43)
The case & is a vanishing gradient phenomenon where [[VoL(j, v) is now independent of the depth T and of the input scale X.
Proof. The control of gradient implicitly depend the scale of the output of the network every layer, hence it is crucial to control the norm of each activation.
Lemma (Bounded activations). IʃUS for every 1 S1
+
have:
|| S0* (
SB
B
x SU
+ 1 SU
(44)
USS = we have:
|| X
(45)
In every case we have | S S1|=.]]-
Lemma proof.
From assumption] 2 we assume that is S-Lipschitz, we have:
|heell [[a(())] (|0(()) o00)| < Sl
(46)
Now, observe that:
|| = [|W + bet1l |l < ||
W + ||4 || & US|| + B.
(47)
Let u1 UX B and w++1 SUU, B be linear recurrence relation. The translated sequence B
U4 su is geometric progression of ratio SU, hence 4, (UX++ B 1- +
B
B
SU
Finally conclude that by construction ||=:|| S ut-
43

---

The activation jacobians can be bounded by applying the chainrule. The recurrence relation obtained the one automatically computed with back proppaaaaat
Lemma (Bounded activation derivatives). For every T +
2
we have:
Oz. 0z
S (SU)
(48)
Lemma proof. The chain rule expands as:
Oz.-
0z. Th.-1 0zg-1 1
(49)
0z.
1h.-1 1 0zg-1 Ozt
From Cauchy-Schwand inequality get:
82.
Oz.
Ihs
82s-1 |1. Oz
|| -
1
1-11
(50)
021
0hg-1
02,-1
Since S-Lipschitz, and ||Wal| s U, and by observing that that:
0= 0zg
we obtain by induction
Oh. ah+ s (SU)
(51)
The derivatives of the biases are a textbook application of the chainrule.
Lemma (Bounded bias derivatives). For every we have:
(o..C(D s ((SU)++1-
(52)
Lemma proof. The chain rule yields:
02T+1 Ozr
Vn, ((i.)) (V
(53)
0z Ob.
Hence we have:
Øzt+1 ||
02t 0z ab.
| C(0 |V r)
||.
(54)
We conclude with Lemma that states [[V vl < L and by observaing that 2b,
|| (2ry-1
I (US) with requirement
that states
1.
We can now bound the derivative of the affine weights:
Lemma (Bounded weight derivatives). For every T+12123 2 we have:
SB
+ +LSSUT++I+ SB
ww, v)) < L(SU)T x T ST
S-SU when SU + 1,
(55)
IVw,C(0.v) < LS + (t (t- 1)B) when SU =
(56)
(57)
In every case:
w. ((0.v)) v)ll < L(SU)
(58)
Lemma proof. We proceed like in the proof of Lemma and we get:
02r+1
Oz,
Vw. C(. mlIl < |V CG
(59)
Zz,
aw,
Which then yields:
Oz Vw. ((. T(SU)
||- aw.
(60)
44

---

Now, for 1+12+ according to Lemma
we either have:
dz: OW;
(x
SB
SB
|1-11| S 51 (SU)-
(61)
1 SU
1 SS
or, when US 1:
2zt aw,
- 1h, = 2112-11 = SX + ( 1ft 2.
(62)
X otherwise.
(63)
dw,
Now, the derivatives of the loss with respect to each type of parameter (i.e W, or by) are know, and they can be combined retrieve the overall gradient vector.
= (W), b2). (WT+1,bT-1))
(64)
We introduce a SU.
Case a = The resulting norm is given by the series:
T+1
|VoC(D 2)11
Σ
Vb,
(65)
(1+ + T+1
222
(1
(66)
t=
T
272
1+x² Σ
(1+ (SX uSBB3
(67)
==1
T
1+ + Σ
S1+ (x² +2uBX + u² +u²²)))
(68)
T(T 1)(
1+ + +(1+55x3) BXT
+ +1) S2
6
(69)
Finally:
\VoL(..vll + + XS
(70)
(LX - I/XXST LBST
(71)
This upper bound depends (asymptotically) linearly of L, X, S. B, //, when other factors are kept fixed to value.
45

---

Case # 1.
We introduce B
SB
1-a"
T+1
VoC(D.))lE
Σ
Vb, by
[(. v)ll Vw.
(72)
T+1
- 1?
a 2T
(((X- - -3)+++++0 +3) + aa2-21)
(73)
t=1
Σ - (11X-88²+ + 3)a + g2 =2)
(74)
S 2 27
(T (T+ + - -333 Σ
a
(82 +1) Σ
a
22
(75)
4=0
#=0
(1Y
a²
$ "F
(T+ 1)(1 + 3)3
+ (Ba
+ 1)
a
a
(76)
Finally:
1)(X - +) B)B a (2) (VoC(0.)) s La La'V(r (T++)(XX-
a (222)
a + (3² 1)
a²
(77)
Now, the situation is a bit different for a < and a > 1. One case corresponds to exploding gradient, and the other vanishing gradient.
When a < 1 we necessarily have 3 > 0, hence we obtain a crude upper-bound:
1 [Vo(( o (Io" La XVT+ (1 a2)
(V
X
v(-a))
SB
b
aT
(1 avvi
(78)
Once again B (network with no bias) leads to useful simplifications:
0
VeL(i. o (IaTXVin (1-a)3
L
(79)
This is typical case of vanishing gradient since when T >> 1 the upper bound does not depend on the input scale X anymore.
Similarly, we perform the analysis for
1, which implies 3 < 0. yielding another bound: (
-Oaa aT (La-) (SB)+
(VTlax+ + SB)+ + a(SB + a:)
VoL(i.)) O
(80)
Va
Without biases get:
VoC(D.v)12 = o 0 a
(
VTX +
(81)
a-1
va
We recognize an exploding gradient phenomenon due to the a" term
Propositions and were introduced for clarity. They are simple consequence of the Lemmas used in the proof of Theorem I
The informal theorem of section 3.1 is based on the bounds of theorem I that have been simplified. Note that the definition of network differs slightly: in definition 3 the activations and the affines layers are considered independent and indexed differently, while the theoretical framework merge them into and hy respectively. sharing the same index t. This is without consequences
realize that K = U = S and 2T = D then (US)2 = a² = K2 leads to 2T = K?, The leading constant factors based value have been replaced by 1 since they do not affect the asymptotic behavior.
46


Reviews:
[{"review_id": "AUBCySyD9N", "reviewer": "Reviewer_ah9n", "summary": "This paper presents DP-SGD without gradient clipping, achieved through gradient norm preservation, a method that has not been explored in the existing DP-SGD literature.", "questions": "How can we ensure a fair experimental comparison? Specifically, tuning hyperparameters also consumes the DP budget. Did you take into account such DP costs in your experiments and results?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "This paper introduces a novel approach in the DP-SGD literature by offering DP-SGD without clipping through gradient norm preservation, a method that has not been explored before.", "weaknesses": "To validate the effectiveness of the proposed methods, it is essential to conduct a more comprehensive experimental evaluation.", "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": "vY2uR0Uq0N", "reviewer": "Reviewer_L744", "summary": "In this work, the authors introduce Clipless DP-SGD, an approach for training neural network models with differentially private stochastic gradient descent, without the need to apply clipping to the parameter gradients.\nTo achieve this, the authors leverage existing theory on Lipschitz neural networks, which they extend to compute Lipschitz constants with respect to the parameters (instead of w.r.t. the inputs, which has already been studied in the literature).\nThis enables them to compute per-layer sensitivities, for a range of common feedforward architectures, without requiring gradient clipping.\nThe authors evaluate their approach on a range of benchmark datasets, where they observe a competitive performance compared to DP-SGD.", "questions": "I have the following questions for the authors regarding this work:\n\n__Clarification on pareto fronts:__\nTo my understanding, the pareto fronts shown correspond to the convex hull of the green points.\nThe authors explain that the green points themselves correspond to a pair of validation accuracy and $\\epsilon$ parameter from a given epoch.\nDo these points correspond to all epochs across all Bayesian optimisation runs, as explained in appendix D2?\nCan the authors comment on the extent of the privacy leakage that would result from selecting a particular model from the pareto front?\n\n__Extending this to other architectures, e.g. transformers:__\nThe approach developed in this paper applies to feedforward networks, which admittedly cover a significant range of existing architectures.\nCan the authors comment on whether it is possible to extend their method to other popular architectures, such as transformers or graph neural networks?\nIt is unclear to me how the ideas developed here can be extended to, for example, cases where the internal representation of the network depends on the input datum itself.\n\n__How tight are the derived sensitivities in practice?__\nCan the authors comment on how tight the derived sensitivities are in practice?\nIn particular, how large are the gradient norms encountered during training, compared to the derived sensitivities.\n\n\nIn addition, I would like to point out the following typos and suggestions:\n\n- __Typo:__\nIn def. 3, \"there is no parameters\" should be \"there are no parameters.\"\n- __Suggestion:__\nIt might be worth separating the definition of Lipschitz networks from regular feedforward networks, keeping two separate definitions, or making the first part of the definition part of the text.\n- __Typo & suggestion:__\nIn Theorem 1, \"centered in zero\" should be \"centered at zero.\"\nAlso you could change \"expanded analytically.\" to \"computed analytically, as follows:\"\n- __Typo:__\nIn page 7, \"for Lipschitz constrained network\" should be \"for Lipschitz constrained networks\".", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "In my view the main strengths of the paper are as follows:\n\n__Eliminating the need to tune $C$ and reducing gradient bias:__\nOne important benefit of Clipless DP-SGD is that it does not involve a clipping threshold $C,$ and as such it does not require tuning this parameter.\nThis is particularly useful since, to extract strong performance out of DP-SGD, selecting an appropriate value for $C,$ i.e. tuning it, is necessary.\nPerforming this tuning naively would result in privacy leakage since updating $C$ requires querying the data.\nClipless DP-SGD elegantly circumvents this issue by eliminating clipping altogether.\nAnother benefit of removing clipping, as the authors note, is that this eliminates the associated bias that is introduced in the gradients, potentially making optimisation easier, though to my understanding the effect of eliminating this bias has not been explicitly examined in the paper.\n\n__Reduced runtime and memory requirements:__\nAnother benefit of the proposed method is the fact that, while DP-SGD computes per-sample gradients and clips these separately before averaging, Clipless DP-SGD operates on the averaged loss directly, without computing per-sample gradients.\nAs a result, Clipless DP-SGD offers both a lower memory footprint as well as faster runtimes than regular DP-SGD.\nThe favourable runtime and memory requirements of the proposed method are illustrated in figure 3 (though it should be noted that different implementations on different back-ends may not be directly comparable).\n\n__Originality and relations to existing work:__\nIn my assessment the contribution made in this paper is both original and creative, since computing Lipchitz constants with respect to the network parameters does not seem to have been studied in the literature before.\nThe authors build on existing literature on Lipchitz networks and extend it in a valuable way.\n\n__Codebase contribution:__\nThe authors provide a codebase for differentially private Lipchitz models, $\\texttt{lip-dp}$ which is a valuable contribution in itself, and may be especially useful to practitioners.\n\n__Quality of exposition and rigour:__\nI found the main text well written and relatively easy to read considering its technical content.\nThe method is well motivated and well explained, and although I have not examined the proofs very closely, the exposition in the main text seems sound.", "weaknesses": "In my view, the paper does not present critical weaknesses, though two points that I think are important to consider are:\n\n__Performance compared to existing methods:__\nIt seems that, while the current method eliminates the need for clipping (thereby simplifying the tuning procedure and removing gradient bias), it still performs worse than existing methods on datasets beyond MNIST, sometimes by a large margin (see figure 13 in the appendix).\nIt is not entirely clear which design choice is responsible for this gap in performance, though the Lipschitz constraints imposed on the network is a likely candidate.\nGiven this, it is not entirely clear how competitive the proposed method would be compared to existing methods, on more realistic tasks.\n\n__Hyperparameter tuning:__\nWhile Clipless DP-SGD removes the need for tuning the clipping threshold, it still appears to require a large amount of hyperparameter tuning in order to extract good performance (see figure 3 in the main text, and figure 13 in the appendix).\nAs a result, this can lead to increased computational costs as well as privacy leakage, since the current method does not account for leakage due to hyperparameter tuning.\nIt is not fully obvious how Clipless DP-SGD compares to existing methods under a like-for-like compute resources and privacy leakage due to tuning.", "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": "bm1DWsfemy", "reviewer": "Reviewer_GMKM", "summary": "This paper studies to train Lipschitz neural networks with DP, so as to avoid using per-sample gradient clipping. It gives theorems of the tradeoff between privacy and utility, as well as a Python package that efficiently implement the proposed algorithms. Empirical results on toy datasets show some promise of this new method.", "questions": "See Weaknesses.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "Overall, the paper is well-polished and rigorous. I appreciate the careful layout of the requirements and proper introduction of Lipschitz literatures.", "weaknesses": "I have some concerns about the claims made in this work, in addition to some minor issues.\n\n1. The significance of this work is based on the hypothesis that per-sample gradient clipping is inefficient. This has been emphasized in the abstract and in the paragraph below Definition 2, in which the authors wrote \"Hyper-parameter search on the broad-range clipping value C is required...The computation of per-sample gradients is expensive\". However, this is mistaken. DP-SGD does not need to tune the clipping value (see \"Automatic clipping: Differentially private deep learning made easier and stronger\" and \"Normalized/Clipped SGD with Perturbation for Differentially Private Non-Convex Optimization\"). DP-SGD/AdamW can be as fast and memory efficient as standard SGD, while maintaining the same DP accuracy. Many papers that use ghost clipping can achieve this (see \"Differentially Private Optimization on Large Model at Small Cost\", \"Exploring the Limits of Differentially Private Deep Learning with Group-wise Clipping\", \"LARGE LANGUAGE MODELS CAN BE STRONG DIFFERENTIALLY PRIVATE LEARNERS\", \"Scalable and Efficient Training of Large Convolutional Neural Networks with Differential Privacy\"), improving the speed from 1.7X slower than non-DP to 1.1X. It would be inappropriate if the authors only refer to the older works like Kifer's and Opacus.\n\n2. Another issue is to claim per-sample clipping introduces bias and not to fully discuss the bias of Clipless DP-SGD. The gradient bias does exist, but may not be the reason of slow convergence. Furthermore, I believe Clipless DP-SGD also introduces some bias, in the form of network architecture by moving from regular ResNet to GNP ResNet. It would not be fair to discard the clipping by the current discussion in Theorem 1.\n\n3. The empirical results in this work are not convincing, focusing only on toy datasets, restricted layer types (not including embedding layer that is vital to language model and vision transformer), and toy models (e.g. Figure 5, model size 2M). I wonder whether the new method can benefit from large scale pretraining?", "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)