# Weights Shuffling for Improving DPSGD in Transformer-based Models

Jungang Yang
Shanghai Jiao Tong University
<EMAIL_ADDRESS>Zhe Ji
Shanghai Jiao Tong University
<EMAIL_ADDRESS>Liyao Xiang
Shanghai Jiao Tong University
<EMAIL_ADDRESS>
###### Abstract

Differential Privacy (DP) mechanisms, especially in high-dimensional settings,
often face the challenge of maintaining privacy without compromising the data
utility. This work introduces an innovative shuffling mechanism in
Differentially-Private Stochastic Gradient Descent (DPSGD) to enhance the
utility of large models at the same privacy guarantee of the unshuffled case.
Specifically, we reveal that random shuffling brings additional randomness to
the trajectory of gradient descent while not impacting the model accuracy by
the permutation invariance property — the model can be equivalently computed
in both forward and backward propagations under permutation. We show that
permutation indeed improves the privacy guarantee of DPSGD in theory, but
tracking the exact privacy loss on shuffled model is particularly challenging.
Hence we exploit the approximation on sum of lognormal distributions to derive
the condition for the shuffled DPSGD to meet the DP guarantee. Auditing
results show that our condition offers a DP guarantee quite close to the
audited privacy level, demonstrating our approach an effective estimation in
practice. Experimental results have verified our theoretical derivation and
illustrate that our mechanism improves the accuracy of DPSGD over the state-
of-the-art baselines on a variety of models and tasks.

##  I Introduction

Recent work has revealed that trained neural networks pose great threats in
leaking sensitive training data. Differential Privacy (DP) [14] serves both as
a measure to quantify the upper bound of such information leak, and as
mechanisms to ensure any individual sample’s impact on the model is
negligible. The core principle of DP is to introduce random perturbation to
the queried data, effectively preventing the disclosure of an individual
sample. Differentially-private models have shown some defensive capability
against privacy attacks including membership inference attacks [37, 38, 50],
gradient matching attack [55], input reconstruction attack [8], etc.

Among the DP mechanisms, Differentially-Private Stochastic Gradient Descent
(DPSGD) [1] emerges as an important one in privacy-preserving machine
learning. By clipping the gradients of each example and inserting randomized
noise to the clipped gradients in each training iteration, DPSGD ensures that
the published model satisfies DP over the private training dataset. However,
the conventional methods suffer significant accuracy losses due to the
overwhelming amount of noise inserted, especially on deep and large models.
Traditional DPSGD techniques, while effective in lower dimensions, struggle to
maintain data utility as the model size enlarges.

Many works have been devoted into tackling the high-dimensional issue in
DPSGD. Some have observed that the gradients of deep neural networks mostly
live on a very low dimensional manifold [41, 20, 30], and thus can be
compressed without hurting the model performance too much. Based on the
observation, a series of works [50, 51, 49, 54, 48] propose to replace the
full gradients with their low-dimensional projection to reduce the overall
noise added. Despite their impressive performance, most works avoid paying
privacy price for the acquisition of low-dimensional representations, either
by modifying the original model structure, or relying on auxiliary public data
to estimate the low-dimensional projecting subspace. These works hardly keep
the original training on large models as it is. Other works improve the
accuracy of DPSGD by hyperparameters tuning [10, 31]. However, hyperparameters
tuning consumes a great amount of computational resource in large-scale
training. Moreover, such solutions merely provide training tricks which may
not be transferable to other models.

We take a drastically different approach to mitigate the accuracy loss of
DPSGD on large models — rather than blaming on the high dimensionality, we
take advantage of it. As we observe, for large models, the possible number of
weights permutations could be huge, e.g., the permutation space for a billion-
level model such as GPT-2 is as large as $10^{9}!$. Hence if we could randomly
permute the model weights without affecting the model utility at each training
step, we would obscure the training trajectory thus gaining privacy with no
utility cost, alleviating the amount of additive perturbation noise.

One should note that there is a significant distinction between our
methodology and the existing shuffle model of privacy [5, 15, 9, 4, 24, 16].
The latter is a distributed model in which a shuffler permutes the locally-
differentially-private reports from different users for obfuscation. The
shuffled reports are then released to a server for analysis. It has been shown
that the random shuffling of inputs to locally private protocols amplifies the
privacy guarantee [17]. In contrast, our approach works in the central DP
scenario focusing on the shuffling of model weights instead of user data to
hide the original weights among a set of weights which are equivalent in
computing the output. The random shuffling enhances privacy as it obfuscates
the training trajectories on the dataset hereby preserving training data
privacy at a low accuracy cost. Moreover, we confront a unique challenge: the
existing shuffle model of privacy naturally preserves accuracy as the user
shuffling would not affect the computation, while a naive random shuffling of
model weights would totally destroy the model utility.

Fortunately, as we analyzed the mainstream neural architecture, we found that
multilayer perceptron (MLP) and Transformer encoder blocks, both taking a
large proportion of the model weights, satisfy permutation invariance
property. Specifically, if their weight matrices are permuted, the permutation
can be negated by an inverted permutation in the following layer without
disrupting the forward and backward propagation. Hence weight permutation
incurs zero accuracy loss on the inference or training of the model. Apart
from that, MLP and Transformer encoder blocks widely exist in the state-of-
the-art neural networks, especially large models with Transformer backbones,
and these parts of a network are mostly dense, creating a huge space for
permutation without any accuracy loss.

The primal challenge hence lies in quantifying the privacy guarantee brought
by random shuffling of model weights. According to previous study [44], random
shuffling introduces mixture distributions of which the tradeoff function is
lower bounded by the unshuffled case, indicating higher indistinguishability
of the former. However, the former works do not provide an explicit form of
the privacy guarantee achieved by shuffling. To vividly explain why mixture
distributions increase indistinguishability, we will show a toy example by
mixture of Gaussians.

To better illustrate our intuition, we employ the Gaussian distribution as a
toy example in Fig. 1. We have two points $(-2,0)$ and $(2,0)$ as the original
data, the additive Gaussian mechanism generates outputs following distribution
$\mathcal{N}((-2,0),I)$ and $\mathcal{N}((2,0),I)$ (left panel), respectively,
providing plausible deniability in discriminating the two points. The closer
the distance between the two distributions, the harder it is to discriminate.
What shuffling does is to draw the two distributions closer by randomly
permuting the data, i.e., the original $(2,0)$ has a half of the chance to be
revealed as $(0,2)$. With the noise, the distribution $\mathcal{N}((2,0),I)$
morphs into a Gaussian mixture centered at $(2,0)$ and $(0,2)$, and a Gaussian
mixture is created for $\mathcal{N}((-2,0),I)$ likewise. The measured
distribution-wise distance is shorter between the Gaussian mixtures than that
of the two original Gaussians, thereby enhancing the indistinguishability.

Figure 1: Left: two Gaussian distributions. Right: the distributions after
random shuffling. The $\mathcal{N}((-2,0),I)$ turns into a Gaussian mixture
distributed around $(-2,0)$ and $(0,-2)$ and similarly for
$\mathcal{N}((2,0),I)$. We estimate the distributional distances by
$\|P(x,y)-Q(x,y))\|_{F}$, where $\|\cdot\|_{F}$ means Frobenius norm, on an
area $x,y\in[-10,10]$. The measured distance on the left panel is 18.53 which
is larger than 13.96 of the right panel.

Yet, we encounter another challenge in accounting the privacy loss of the
Gaussian mixtures which contain sum of log-normal distributions without a
closed-form expression. We tackle the challenge by approximating the sum of
log-normal distributions and provide an analytical condition to meet
$(\varepsilon,\delta)$-DP. Based on the condition, we propose the shuffled
DPSGD mechanism, which takes one more step in each iteration of DPSGD: the
gradients and weights of MLP and Transformer encoder blocks get randomly
shuffled in each update. We compose the privacy loss over iterations by the
advanced composition and amplify privacy by subsampling [40], as other
accountant methods including moments accountant [1], RDP [32], GDP [12] have
limitations on noise distributions apart from Gaussian.

We verify the permutation invariance property, and compare the performance of
shuffled DPSGD with baselines on a variety of the state-of-the-art (large)
models and tasks. We also audit our mechanism by the current auditing tool,
showing that it indeed meets the privacy guarantee proposed. Experimental
results demonstrate that the shuffled DPSGD leads to superior model accuracy
to baselines at the same privacy level, especially when the privacy budget is
tight (low $\varepsilon$s). From the implementation perspective, our shuffling
mechanism incurs little overhead, readily to be deployed in the current DPSGD
framework.

Highlights of our contribution are as follows. First, we theoretically prove
that permutation of the outcome enhances the privacy guarantee, and propose
the approximated condition for $(\epsilon,\delta)$-DP to hold in the shuffling
case. Second, based on our theory and the permutation invariance property of
neural networks, we propose shuffled DPSGD which improves the privacy
guarantee over the conventional DPSGD. Finally, we verify our theory through
experiments and show the efficacy of our design in the real-world large model
private training.

##  II Related work

Differentially-Private Stochastic Gradient Descent (DPSGD) is a method for
protecting training data using differential privacy in machine learning [39,
1]. We will discuss the related works w.r.t. DPSGD.

DPSGD for natural language processing (NLP) tasks. Applying DPSGD to large
models is hard in that the high dimensionality of the model often results in
excessive amount of noise, leading to reduced model performance. Consequently,
existing works have explored various approaches to enhance the accuracy of
large models under differential privacy protection. For instance, studies [31,
2, 23, 48, 22] have focused on NLP tasks closely associated with large models.
To reduce the memory costs of DPSGD in training large models, Li et al.
introduced ‘ghost clipping’ [31], which significantly saves memory by fine-
tuning the weight coefficients without instantiating each sample gradient. He
et al. implemented a grouped and layered clipping mechanism [22], reducing the
memory overhead of DPSGD while achieving differentially-private training of
GPT-3 model (with 175B parameters). Hoory et al. designed a differentially-
private vocabulary algorithm [23], allowing training on a customized, domain-
specific vocabulary while maintaining privacy. Yu et al. adopted classic
compression methods in natural language processing (such as LoRA, Adapter, and
Compacter) as ‘plug-ins’ [48], efficiently perturbing the compressed module
instead to avoid overwhelming noise. By appropriately configuring
hyperparameters such as batch size, learning rate, etc., Anil et al. conducted
private pre-training [2], improving accuracy on masked language model BERT-
Large (with approximately 340M parameters). These methods alleviate the
accuracy degradation issue but alter either the original training process, or
the original model, or the hyperparameter setting.

DPSGD for computer vision (CV) tasks. Studies [29, 50, 19, 10, 6] have
primarily focused on large models in image processing tasks. Bu et al.’s work
[6] extended the ‘ghost clipping’ [31] to convolutional neural networks (CNNs)
like ResNet, reducing the computational overhead of DPSGD for CNNs. Another
series of works focus on model reparametrization. Yu et al. decompose each
weight matrix into the product of two low-rank matrices and a residual matrix
[50], reducing the overall noise by perturbing only the gradients of the low-
rank matrices. The noisy low-rank matrix gradients are then projected back to
update the original weight matrices. However, this method still incurs high
costs in weight reparametrization, and the noise could be amplified in
projection, leading to significant accuracy losses. Golatkar et al. proposed
an adaptive differential privacy algorithm [19], balancing data privacy and
model accuracy by compressing private data gradients guided by public data
gradient directions. Although such model compression-based works have improved
efficiency/accuracy to some extent, they have deviated from the original large
model training. In terms of hyperparameter configuration, De et al. found that
the choice of hyperparameters in DPSGD is crucial to the training outcome [10]
that, by selecting proper hyperparameters, their work achieves over 80%
accuracy on the fine-tuned pre-trained NFNet-F3 model on ImageNet. Similarly,
Kurakin et al. improve accuracy of the deep ResNet model on ImageNet [29] by
tuning hyperparameters.

Shuffle-DP. Since the proposal of the Encode, Shuffle, Analyze (ESA) system
[5], the previous line of Shuffle-DP [15, 9, 4] has mainly focused on reducing
the privacy budget of local differential privacy, where private data from
different users gets shuffled by a trusted third-party aggregator, adding
anonymity upon the original DP protection. That is to say, even in cases where
the true value is uploaded, the adversary cannot pinpoint which one is the
true value. Specifically, the anonymity brought by shuffling turns the
original $\varepsilon$-DP into $(\varepsilon^{\prime},\delta)$-DP with
$\varepsilon>\varepsilon^{\prime}$, and such a privacy loss bound is further
refined by works such as [16].

Our work follows a similar idea but takes a totally different approach. While
Shuffle-DP primarily targets LDP, our work is designed for DPSGD and does not
require a trusted third-party aggregator. We permute the model weights instead
of shuffling the dataset to get different sets of samples [24]. Moreover, the
permutation brings additional computational issue in model training scenarios.

##  III Preliminaries

This section introduces the basic concepts and definitions fundamental to our
study.

###  III-A Differential Privacy

Differential Privacy (DP) is a framework for quantifying the privacy
guarantees offered by a randomized mechanism. The definition of
$(\epsilon,\delta)$-differential privacy provides a measure of the likelihood
that an individual’s data can influence the output of an algorithm.

######  Definition 1 ($(\varepsilon,\delta)$-Differential Privacy [14]).

A randomized mechanism $M$ satisfies $(\varepsilon,\delta)$-differential
privacy if for any neighboring datasets ${X}$ and ${X}^{\prime}$ differing by
at most one unit, and for any possible output $\mathcal{O}$,

$\Pr(\mathcal{M}({X})\in\mathcal{O})\leq
e^{\varepsilon}\Pr(\mathcal{M}({X}^{\prime})\in\mathcal{O})+\delta.$ (1)

In the special case of $\delta=0$, we call
$\mathcal{M}~{}\varepsilon$-differentially private.

We define $l_{2}$-sensitivity on a pair of adjacent datasets which differ by a
single record:

######  Definition 2 ($\ell_{2}$-sensitivity).

The $\ell_{2}$-sensitivity of the query function $f({X})$ is defined as

$s_{2}(f)=\underset{d({X},{X}^{\prime})=1}{\sup}\|f({X})-f({X}^{\prime})\|_{2},$

where $\|\cdot\|_{2}$ is the $\ell_{2}$ norm.

DPSGD. In a deep learning task, the sensitive training dataset
$X=[x_{1},x_{2},\ldots,x_{N}]$ requires to be protected in $T$ iterations of
stochastic gradient descent. In each iteration, a batch of data $B$ of size
$|B|$ will be randomly selected to compute the gradient for weights
$W:g=1/|B|\sum_{x\in B}g(W,x)$, where $g(W,x)$ represents the gradient of the
individual record $x$ and the single $g$ represents the average gradient of
the batch. Since DP requires that the sensitivity of the outcome is bounded,
conventional DPSGD conducts per-sample clipping on the gradients of each $x$:

$\bar{g}(W,x)=g(W,x)/\max(1,\frac{\|g(W,x)\|_{2}}{C}),$ (2)

to ensure that the sensitivity of the gradient, or clipping value is $C$, and
thus the clipped batch gradient becomes $\bar{g}=1/|B|\sum_{x\in
B}\bar{g}(W,x)$. DPSGD mechanism $\mathcal{M}$ inserts noise to the batch
gradient: $\mathcal{M}(\bar{g})=\bar{g}+\frac{1}{|B|}z,$ where
$z\sim\mathcal{N}(0,\sigma^{2}C^{2}I)$ has the same shape with $\bar{g}$. The
standard deviation $\sigma$ of the noise is a constant decided by the privacy
budget $(\epsilon,\delta)$ and $C$.

###  III-B Model Structure

Here we give a detailed description of the common layer structures in large
models, including MLP and Transformer encoder blocks.

######  Definition 3.

We define MLP with two-layer linear projection as

$\displaystyle x_{t+1}=h(x_{t}W_{t}^{\top}+b_{t}),$ (3) $\displaystyle
x_{t+2}=h(x_{t+1}W_{t+1}^{\top}+b_{t+1}),$ (4)

where $W_{t}$ and $b_{t}$ is the weight and bias of $t$-th linear layer,
$W_{t+1}$ is the weight and bias of $(t+1)$-th linear layer and $h(\cdot)$ is
the activation function.

######  Definition 4.

Standard transformer encoder block [42] is a popular building block for neural
architectures, which contains multi-head attention and a MLP layer:

$\displaystyle\text{Attention}(Q,K,V)=\operatorname{softmax}\left(\frac{QK^{T}}{\sqrt{d_{k}}}\right)V,$
(5) $\displaystyle X_{t+1}=\left[A_{1},\ldots,A_{h}\right]W^{O},$ (6)
$\displaystyle\text{ where
}A_{i}=\text{Attention}\left(X_{t}W_{i}^{Q},X_{t}W_{i}^{K},X_{t}W_{i}^{V}\right),~{}i\in[h].$
(7)

The projections are parameter matrices $W_{i}^{Q}\in\mathbb{R}^{d_{m}\times
d_{k}},W_{i}^{K}\in\mathbb{R}^{d_{m}\times d_{k}},$
$W_{i}^{V}\in\mathbb{R}^{d_{m}\times d_{v}}$ and
$W^{O}\in\mathbb{R}^{hd_{v}\times d_{m}}$. $W^{O}$ means the output weight
matrix, and $d_{m},d_{k},d_{v}$ are the dimensions of the model, key, and
value, respectively.

We will prove the parameter permutation invariance under the shuffle mechanism
on these two types of layers.

###  III-C Sum of Log-Normal Distribution

######  Lemma 1 (F-W approximation of sum of lognormal distributions [18]).

Given $d$ i.i.d. normal distributions
$Y_{i}~{}\sim\mathcal{N}(\mu_{i},\sigma^{2})$ for $i=1,\ldots,d$. The sum of
$d$ log-normal random variables $S_{d}=\sum\limits_{i=1}^{d}e^{Y_{i}}$ can be
approximated by:

$S_{d}\approx
e^{Y},~{}\text{where}~{}Y\sim\mathcal{N}(\mu_{Y},\sigma_{Y}^{2}),$ (8)

given that

$\displaystyle\sigma_{Y}^{2}$
$\displaystyle=\log\left[(e^{\sigma^{2}}-1)\frac{\sum\limits_{i=1}^{d}e^{2\mu_{i}}}{(\sum\limits_{i=1}^{d}e^{\mu_{i}})^{2}}+1\right],$
(9) $\displaystyle\mu_{Y}$
$\displaystyle=\log\left[\sum\limits_{i=1}^{d}e^{\mu_{i}}\right]+\frac{\sigma^{2}}{2}-\frac{\sigma_{Y}^{2}}{2}.$
(10)

###  III-D Privacy Accountant

To track the privacy loss in DPSGD, Moments Accountant [1] and Renyi
Differential Privacy Accountant [32] are commonly used. These methods
accumulate the logarithm of the moments of privacy loss at each step, but have
the drawback of overestimating the privacy budget [26]. Therefore, Sivakan et
al. proposed the Privacy loss Random Variables (PRVs) Accountant in [21],
outperforming other accountant schemes in the context of DPSGD. This method
truncates and discretizes the Privacy Loss Random Variables (PRVs), and then
uses Fast Fourier Transform (FFT) to efficiently convolve the distributions of
the PRVs. Adapted from the PLD Accountant [26, 27, 25], the PRV Accountant
solves the problem in PLD Accountant that it cannot compose differentially-
private algorithms. However, the PRV Accountant is still limited in that it
cannot be applied to random variables of any distribution. Taking
generalizability and tightness of the bound into account, we choose advanced
composition [40] in this work:

######  Theorem 1 (Advanced Composition, Thm. 22 in [40]).

For $j\in[k]$, letting
$M_{j}:\mathcal{X}^{n}\times\mathcal{Y}_{j-1}\rightarrow\mathcal{Y}_{j}$ be
the randomized algorithm which is
$\left(\varepsilon_{j},\delta_{j}\right)$-DP, we inductively define
$M_{1\cdots j}:\mathcal{X}^{n}\rightarrow\mathcal{Y}_{j}$ by $M_{1\cdots
j}(x)=M_{j}\left(x,M_{1\cdots(j-1)}(x)\right)$, where $M_{1\ldots 0}(x)=y_{0}$
for some fixed $y_{0}\in\mathcal{Y}_{0}$. Then $M_{1\ldots k}$ is
$(\varepsilon,\delta)$-DP for any $\delta>\sum_{j=1}^{k}\delta_{j}$ with

$\varepsilon=\min\left\\{\sum_{j=1}^{k}\varepsilon_{j},\frac{1}{2}\sum_{j=1}^{k}\varepsilon_{j}^{2}+\sqrt{2\log\left(1/\delta^{\prime}\right)\sum_{j=1}^{k}\varepsilon_{j}^{2}}\right\\},$
(11)

where $\delta^{\prime}=\delta-\sum_{j=1}^{k}\delta_{j}$.

This Theorem provides a general composition method that can be applied to any
differential privacy mechanism. It is not limited to any specific
distribution, and thus we apply it in our proposed method to calculate the
privacy budget.

Moreover, we apply the Privacy Amplification by Subsampling (Thm. 29 in [40])
to amplify the privacy budget by batch sampling:

######  Theorem 2 (Privacy Amplification by Subsampling).

For dataset $x\in\mathcal{X}^{n}$, let $x_{U}\in\mathcal{X}^{n}$ denote the
entries of $x$ indexed by $U\subset[n]$ which is a random subset. That is,
$\left(x_{U}\right)_{i}=x_{i}$ if $i\in U$ and $\left(x_{U}\right)_{i}=\perp$
if $i\notin U$, where $\perp\in\mathcal{X}$ is some null value. Given
$M:\mathcal{X}^{n}\rightarrow\mathcal{Y}$ satisfying
$(\varepsilon,\delta)$-DP, we define
$M^{U}:\mathcal{X}^{n}\rightarrow\mathcal{Y}$ by
$M^{U}(x)=M\left(x_{U}\right)$. Let
$p=\max_{i\in[n]}\underset{U}{\mathbb{P}}[i\in U]$. Then $M^{U}$ is
$\left(\varepsilon^{\prime},\delta^{\prime}\right)$-DP for
$\varepsilon^{\prime}=\log\left(1+p\left(e^{\varepsilon}-1\right)\right)$ and
$\delta^{\prime}=p\cdot\delta$.

This theorem could be applied to amplify the privacy budget of each step in
DPSGD, where the random subset $U$ represents the batch sampled.

##  IV Methodology

This section delineates our approach. We begin with the motivation of using
shuffling to reinforce privacy, illustrate our shuffling mechanism, and then
provide the differential privacy guarantee of shuffled Gaussian — a Gaussian
mechanism with post shuffling.

Motivation. From the entropy perspective, shuffling would increase the
ambiguity of the outcome, thereby enhancing the privacy strength of the input.
Specifically, shuffling increases the randomness in data processing by
rearranging elements of the (noisy) output, which disrupts the potential
relation between the output and its private input, therefore reducing reliance
on the randomness of the additive perturbation noise. The result is a relaxed
constraint on the perturbation noise at the same level of privacy guarantee.

We take the Gaussian mechanism as an example for a deeper analysis. A Gaussian
mechanism composed by random shuffling is interpreted as a mixture of
Gaussian, where each shuffled noisy output appears with a certain probability.
Random shuffling turns a single-spike (Gaussian) distribution into a multi-
spike (mixture of Gaussian) one where each spike has a reduced magnitude
compared to the single spike. Thus the transformation from a Gaussian into a
mixture of Gaussian can be considered as distribution smoothing, making
adjacent distribution pairs harder to distinguish.

Meanwhile, it is also crucial to prevent shuffling to affect the actual SGD
procedures: no accuracy price should be paid for shuffling. We will show how
we achieve this in the following section.

###  IV-A The Shuffling Mechanism

Although the shuffling of the outcome would bring additional randomness, we
need to carefully implement it to avoid any model performance decline.
Inspired by the permutation equivariance property [46], we propose a weight
shuffling mechanism that does not alter the forward and backward propagation.
Our definition of permutation invariance is as follows:

######  Definition 5 (Weights Permutation Invariance).

For a model $f(W,x)$ with weights $W$ and input $x$, the permutation-invariant
set $\mathcal{P}_{s}$ is defined as

$\mathcal{P}_{s}=\\{P~{}|f(W,x)=f(P(W),x),\forall x\\}$ (12)

where the permutation $P$ denotes a mapping from a set to itself with a
permuted order.

Provided the definition, we now show two widely used network structures are
permutation-invariant.

######  Theorem 3 (MLP Permutation Invariance).

Let $W=\\{W_{t},W_{t+1},b_{t},b_{t+1}\\}$ be the parameters of MLP defined in
Def. 3, and $x=x_{t}$ be the input to the MLP. For any element-wise activation
function $h(\cdot)$ like ReLu, tanh and Softmax, MLP $f(W,x)$ is permutation-
invariant in both the forward and backward propagation if the following
permutation is applied:

$\displaystyle
P(W)=\\{P_{1}^{\top}W_{t},~{}b_{t}P_{1},~{}W_{t+1}P_{1},~{}~{}b_{t+1}\\},$
(13)

where $P_{1}$ is any permutation matrix.

The proof can be obtained by calculation, and we place it in Appendix A-A.

######  Theorem 4 (Transformer Permutation Invariance).

Let $W=\\{W_{i}^{K},W_{i}^{Q},W_{i}^{V},W^{O}\\}$ for $i\in[h]$ with $h$ heads
be the parameters of the transformer block defined in Def. 4. For any element-
wise activation function $h(\cdot)$ like ReLu, tanh and Softmax, the
transformer block is permutation-invariant in both the forward and backward
propagation if the following permutation is applied:

$P(W)=\\{W_{i}^{K}P_{1i},~{}W_{i}^{Q}P_{1i},~{}W_{i}^{V}P_{2},~{}P_{3}W^{O}\\},$
(14)

where $P_{1i}\in\mathbb{R}^{d_{k}\times d_{k}},P_{2}\in\mathbb{R}^{d_{v}\times
d_{v}},$ and

$P_{3}=\begin{bmatrix}P_{2}^{\top}&0&\cdots&0\\\ 0&P_{2}^{\top}&\cdots&0\\\
\vdots&\vdots&\ddots&\vdots\\\
0&0&\cdots&P_{2}^{\top}\end{bmatrix}\in\mathbb{R}^{hd_{v}\times hd_{v}}$ (15)

are any permutation matrices.

We also refer readers to the proof in Appendix A-B.

Although we merely define permutation invariance on two network structures,
the two structures widely exist in all types of neural networks. Particularly,
the transformer block constitutes a major component of the popular
Transformer-based large models. Hence a vast majority of the current large
models could permute all or a part of their parameters without altering their
outputs by Thm. 3 and 4.

Randomized shuffling. Since any permutation from $\mathcal{P}_{s}$ can be
chosen to apply to the model weights without changing the output, we sample a
permutation across all elements in $\mathcal{P}_{s}$ by a uniform
distribution. Therefore, all analysis is based on that the permutation is
uniformly sampled from $\mathcal{P}_{s}$ in the following. We start from a
simple case of shuffling a vector to analyze how random shuffling impacts the
output distribution, with Gaussian mechanism as an instance.

We discuss how shuffling is integrated with a vectorized Gaussian mechanism.
In the conventional Gaussian mechanism, a zero-centered Gaussian noise vector
is added to the output vector (of the same size) to achieve DP. Our shuffled
Gaussian mechanism only takes one more step.

######  Definition 6 (Shuffled Gaussian).

A uniformly chosen random permutation $P\in\mathcal{P}_{s}$ turns vector
$y\in\mathbb{R}^{d}$ into vector $P(y)\in\mathbb{R}^{d}$. The shuffled
Gaussian is defined as $\mathcal{M}(y)=P(y)+z$, where
$z\sim\mathcal{N}(\bm{0},\sigma^{2}I)\in\mathbb{R}^{d}$. Letting the outcome
be the random variable $o=P(y)+z,$ its probability density function (PDF) is

$\displaystyle
p(o)=\frac{1}{|\mathcal{P}_{s}|}\sum_{i=1}^{|\mathcal{P}_{s}|}\frac{1}{(2\pi\sigma^{2})^{|\mathcal{P}_{s}|/2}}e^{-\frac{\|o-y^{(i)}\|^{2}_{2}}{2\sigma^{2}}},$
(16)

where $y^{(i)}$ is the $i$-th permutation of $y$ and $|\mathcal{P}_{s}|$
denotes the total number of permutations which meet Def. 5.

Without causing confusion, we use $P$ to both denote a deterministic
permutation as well as a random variable on $\mathcal{P}_{s}$. In the shuffled
Gaussian mechanism, the original output vector is first rearranged by a
permutation which is randomly sampled from $\mathcal{P}_{s}$, and then is
added a zero-centered Gaussian noise vector. Notably, the PDF of Eq. 16
remains the same if we choose to add noise before shuffling the noisy vector.
This is because the Gaussian noise $z$ is i.i.d. in each dimension.

###  IV-B Shuffling Improves Privacy

A vital point in our motivation is that the output distribution gets smoother
and the distribution-wise distance gets shorter by the shuffling mechanism. In
shuffled Gaussian, we consider the shuffling mechanism a post-processing step
of the Gaussian mechanism, and the shuffling mechanism does not access the
original data. Therefore, the shuffled Gaussian must at least satisfy the DP
that the pure Gaussian mechanism provides. In this section, we give the proof
that shuffled Gaussian indeed improves the privacy guarantee of the Gaussian
mechanism.

######  Theorem 5 (Comparison with Gaussian mechanism).

The privacy guarantee $\delta$ of the Shuffled Gaussian is smaller than or
equal to that of the Gaussian mechanism under the same $\epsilon$ for meeting
$(\epsilon,\delta)$-DP.

###### Proof.

According to Def. 6, the output distributions of the queries on $x$ and
$x^{\prime}$ are

$\displaystyle P\left[f(x)\right]+z$ $\displaystyle\triangleq
Y=\begin{cases}Y^{(i)}~{}~{}w.p.~{}\frac{1}{a},\end{cases}$ (17)
$\displaystyle Y^{(i)}\sim\mathcal{N}(f^{(i)}(x),\sigma^{2}I),i\in[a],$ (18)
$\displaystyle P\left[f(x^{\prime})\right]+z$ $\displaystyle\triangleq
Y^{\prime}=\begin{cases}Y^{\prime(i)}~{}~{}w.p.~{}\frac{1}{b},\end{cases}$
(19) $\displaystyle
Y^{\prime(i)}\sim\mathcal{N}(f^{(i)}(x^{\prime}),\sigma^{2}I),i\in[b].$ (20)

We use $a,b$ to denote the number of different permutations of
$f(x),f(x^{\prime})$, respectively. Let
$q(y)=\frac{1}{(2\pi\sigma^{2})^{d/2}}e^{-\frac{||y||^{2}}{2\sigma^{2}}}$ be
defined as the probability density function (PDF) of the $d$-dimensional
Gaussian distribution $\mathcal{N}(0,\sigma^{2}I_{d})$. Then the probability
density functions of $Y$ and $Y^{\prime}$, denoted as $p(y)$ and
$p^{\prime}(y)$, can be written as follows:

$\displaystyle p(y)=$
$\displaystyle\frac{1}{a}\sum\limits_{i=1}^{a}q(y-f^{(i)}(x))$ (21)
$\displaystyle=$
$\displaystyle\frac{1}{a}\sum_{i=1}^{a}\frac{1}{(2\pi\sigma^{2})^{d/2}}e^{-\frac{\|y-f^{(i)}(x)\|^{2}_{2}}{2\sigma^{2}}}\triangleq\frac{1}{a}\sum\limits_{i=1}^{a}q_{i}(y),$
$\displaystyle p^{\prime}(y)=$
$\displaystyle\frac{1}{b}\sum\limits_{i=1}^{b}q(y-f^{(i)}(x^{\prime}))\triangleq\frac{1}{b}\sum\limits_{i=1}^{b}q_{i}^{\prime}(y),$

Here, we define $q_{i}(x)=q(y-f^{(i)}(x))$ and
$q_{i}^{\prime}(x)=q(y-f^{(i)}(x^{\prime}))$. For any adjacent datasets, the
query outputs satisfying differential privacy is equivalent to having

$\displaystyle\Pr\left(P\left[f(x)\right]+z\in
O\right)-e^{\varepsilon}\Pr\left(P\left[f(x^{\prime})\right]+z\in
O\right)\leq\delta$
$\displaystyle\Leftrightarrow\delta=\sup_{O}\int_{O}p(y)-e^{\epsilon}p^{\prime}(y)\,\textrm{d}y,$
(22)
$\displaystyle\Leftrightarrow\delta=\int_{O^{*}}\frac{1}{a}\sum_{i=1}^{a}q_{i}(y)-e^{\epsilon}\frac{1}{b}\sum\limits_{i=1}^{b}q_{i}^{\prime}(y)\,\textrm{d}y$
(23)

where $O^{*}=\\{y\mid p(y)-e^{\epsilon}p^{\prime}(y)\geq 0\\}$. Letting $k$ be
the least common multiple of $a$ and $b$, we have

$\displaystyle\delta$
$\displaystyle=\int_{O^{*}}[\frac{1}{k}\sum_{i=1}^{k}q_{i}(y)-e^{\epsilon}\frac{1}{k}\sum_{i=1}^{k}q_{i}^{\prime}(y)]\textrm{d}y$
(24)
$\displaystyle=\int_{O^{*}}\frac{1}{k}\sum_{i=1}^{k}[q_{i}(y)-e^{\epsilon}q_{i}^{\prime}(y)]\textrm{d}y$
$\displaystyle=\frac{1}{k}\sum_{i=1}^{k}\int_{O^{*}}[q_{i}(y)-e^{\epsilon}q_{i}^{\prime}(y)]\textrm{d}y$
$\displaystyle\leq\frac{1}{k}\sum_{i=1}^{k}\int_{O_{i}^{*}}[q_{i}(y)-e^{\epsilon}q_{i}^{\prime}(y)]\textrm{d}y$
$\displaystyle\leq\frac{1}{k}\sum_{i=1}^{k}\delta_{0}=\delta_{0}.$

$O_{i}^{*}$ is defined as $\\{y|q_{i}(y)-e^{\epsilon}q_{i}^{\prime}(y)\geq
0\\}$ for all $i$, and $\delta_{0}$ is the largest $\delta$ among all pure
Gaussian mechanisms defined on $O_{i}^{*}$, which are the same in the
unshuffled case. Hence it is evident that the privacy guarantee improves by
shuffling. ∎

###  IV-C Privacy Guarantee of Shuffled Gaussian

Although Sec. IV-B provides evidence that shuffling improves the privacy
guarantee, it is still unclear how much improvement presented and how one can
manipulate that in practice. In this section, we offer a more precise, tighter
privacy guarantee for the shuffled Gaussian:

######  Theorem 6 (Privacy Guarantee of Shuffled Gaussian).

Given query function $f(x)\in\mathbb{R}^{d}$ on any adjacent datasets
$X,X^{\prime}$, and the Gaussian noise
$z\sim\mathcal{N}(\bm{0},\sigma^{2}I)\in\mathbb{R}^{d}$, the shuffled Gaussian
$\mathcal{M}(f(x))$ satisfies $(\varepsilon,\delta)$-differentially private if

$\begin{split}\Phi\left(\frac{\sigma_{Z_{1}}}{2}+\frac{\zeta_{1}-\epsilon}{\sigma_{Z_{1}}}\right)-e^{\epsilon}\Phi\left(\frac{\sigma_{Z_{2}}}{2}+\frac{\zeta_{2}-\epsilon}{\sigma_{Z_{2}}}\right)\leq\delta,\end{split}$
(25)

where $\Phi$ is the CDF of the standard Gaussian distribution, and

$\begin{split}\zeta_{1}&=-\log(1+(d-1)e^{-\frac{dcc^{\prime}}{(d-1)\sigma^{2}}}),\\\
\zeta_{2}&=-\log(1+(d-1)e^{-\frac{dc(c+c^{\prime})}{(d-1)\sigma^{2}}})-\frac{c^{2}}{\sigma^{2}},\\\
\sigma_{Z_{1}}^{2}&=\log\left[\frac{1+(d-1)e^{-\frac{2dcc^{\prime}}{(d-1)\sigma^{2}}}}{(1+(d-1)e^{-\frac{dcc^{\prime}}{(d-1)\sigma^{2}}})^{2}}(e^{\frac{c^{2}}{\sigma^{2}}}-1)+1\right],\\\
\sigma_{Z_{2}}^{2}&=\log\left[\frac{1+(d-1)e^{-\frac{2dc(c+c^{\prime})}{(d-1)\sigma^{2}}}}{(1+(d-1)e^{-\frac{dc(c+c^{\prime})}{(d-1)\sigma^{2}}})^{2}}(e^{\frac{c^{2}}{\sigma^{2}}}-1)+1\right],\end{split}$
(26)

where $\|f(x)-f(x^{\prime})\|_{2}\leq c,~{}\|f(x)\|_{2}\leq c^{\prime}$.

The detail of the computation and the proof are collected in Appendix A-C.
Here we present a sketch proof.

###### Proof.

At the beginning, a special case needs to be excluded from discussion, namely,
$f(x)$ and $f(x^{\prime})$ are both equal-entry vectors where random shuffling
cannot properly work, i.e., the vector does not change after shuffling. The
case is almost impossible to occur and is degraded to the unshuffled case.
Hence we ignore the special case.

We start from simplifying the criterion of $O^{*}$ in Eq. (23) as follows.

$\displaystyle p(y)-e^{\epsilon}p^{\prime}(y)\geq 0$ (27)
$\displaystyle\Leftrightarrow$
$\displaystyle\frac{\frac{1}{k}\sum_{i=1}^{k}e^{-\|y-f^{(i)}(x)\|_{2}^{2}/(2\sigma^{2})}}{\frac{1}{k}\sum_{i=1}^{k}e^{-\|y-f^{(i)}(x^{\prime})\|_{2}^{2}/(2\sigma^{2})}}\geq
e^{\epsilon},$ (28)

where $k$ is the least common multiple of $a$ and $b$. We define the
difference between the adjacent queries as $g=f(x^{\prime})-f(x)$, and for
convenience, we abbreviate $f^{(i)}(x)$ as $f^{(i)}$. Then Eq. (28) can be
written as

$\displaystyle\frac{\frac{1}{k}\sum_{i=1}^{k}e^{<y,f^{(i)}>/\sigma^{2}}}{e^{-(\|g\|^{2}_{2}+2<f,g>)/(2\sigma^{2})}\frac{1}{k}\sum_{i=1}^{k}e^{(<y,f^{(i)}>+<y,g^{(i)}>)/\sigma^{2}}}\geq
e^{\epsilon},$ (29)

By Lemma 3 (with a proof in Appendix A-C), a sufficient but not necessary
condition for the output $y\in O^{*}$ is

$\displaystyle
e^{-\epsilon+(\|g\|^{2}_{2}+2<f,g>)/(2\sigma^{2})}\geq\sum_{i=1}^{k}e^{(<y,g^{(i)}>)/\sigma^{2}}.$
(30)

With the inequality, we can derive a lower bound for $\delta$ as

$\displaystyle\delta=$
$\displaystyle\int_{O^{*}}\frac{1}{k}\sum_{i=1}^{k}q_{i}(y)-e^{\epsilon}\frac{1}{k}\sum_{i=1}^{k}q_{i}^{\prime}(y)\,\textrm{d}y$
(31) $\displaystyle\geq$
$\displaystyle\frac{1}{k}\sum_{i=1}^{k}\left[\Pr[\sum_{j=1}^{k}e^{(<Y^{(i)},g^{(j)}>)/\sigma^{2}}\leq
C(\epsilon)]\right]$ (32)
$\displaystyle-\frac{1}{k}\sum_{i=1}^{k}\left[e^{\epsilon}\Pr[\sum_{j=1}^{k}e^{(<Y^{\prime(i)},g^{(j)}>)/\sigma^{2}}\leq
C(\epsilon)]\right]$ (33)

where $C(\epsilon)=e^{-\epsilon+(\|g\|^{2}_{2}+2<f,g>)/(2\sigma^{2})}$. The
term $\sum_{j=1}^{k}e^{(<Y^{(i)},g^{(j)}>)/\sigma^{2}}$ is a typical sum of
log-normal distributions as
$<Y^{(i)},g^{(j)}>=\mathcal{N}(<f^{(i)},g^{(j)}>,\|g\|_{2}^{2}\sigma^{2})$ and
such a distribution does not have an explicit probability density function.
Thus we apply Lemma 1 to approximate it as a log-normal distribution:

$\displaystyle\sum_{j=1}^{k}e^{(<Y^{(i)},g^{(j)}>)/\sigma^{2}}\approx
e^{Z_{1}},~{}Z_{1}\sim\mathcal{N}(\mu_{Z_{1}},\sigma_{Z_{1}}^{2}),$ (34)
$\displaystyle\sigma_{Z_{1}}^{2}=\log\left[\frac{\sum_{j=1}^{k}e^{2\mu_{ij}}}{(\sum_{j=1}^{k}e^{\mu_{ij}})^{2}}(e^{\frac{\|g\|_{2}^{2}}{\sigma^{2}}}-1)+1\right],$
(35)
$\displaystyle\mu_{Z_{1}}=\log(\sum_{j=1}^{k}e^{\mu_{ij}})+\frac{\|g\|^{2}_{2}}{2\sigma^{2}}-\frac{\sigma_{Z_{1}}^{2}}{2};$
(36)

where $\mu_{ij}=\frac{<f^{(i)},g^{(j)}>}{\sigma^{2}}$. Therefore, the
probability distribution in Eq. (32) can be approximated as follows:

$\displaystyle\Pr[\sum_{j=1}^{k}e^{(<Y^{(i)},g^{(j)}>)/\sigma^{2}}\leq
C(\epsilon)]\approx\Pr[e^{\mathcal{N}(\mu_{Z_{1}},\sigma_{Z_{1}}^{2})}\leq
C(\epsilon)],$ (37)
$\displaystyle=\Pr[\mathcal{N}(\mu_{Z_{1}},\sigma_{Z_{1}}^{2})\leq\log
C(\epsilon)]=\Phi\left(\frac{\log
C(\epsilon)-\mu_{Z_{1}}}{\sigma_{Z_{1}}}\right)$ (38)
$\displaystyle=\Phi\left(\frac{\zeta_{1}-\epsilon}{\sigma_{Z_{1}}}+\frac{\sigma_{Z_{1}}}{2}\right),\text{where}~{}\zeta_{1}=-\log(\sum_{j=1}^{k}e^{\mu_{ij}})+\frac{<f,g>}{\sigma^{2}}.$
(39)

We define
$\mu_{ij}^{\prime}=\frac{<f^{(i)}(x^{\prime}),g^{(j)}>}{\sigma^{2}}$, and
$\sigma_{Z_{2}},\zeta_{2}$ by replacing $\mu_{ij}$ with $\mu_{ij}^{\prime}$ in
$\sigma_{Z_{1}},\zeta_{1}$, respectively. By approximating the probability
distribution in Eq. (33) similarly, we have

$\displaystyle\Pr[\sum_{j=1}^{k}e^{(<Y^{(i)},g^{(j)}>)/\sigma^{2}}\leq
C(\epsilon)]$ (40)
$\displaystyle-e^{\epsilon}\Pr[\sum_{j=1}^{k}e^{(<Y^{\prime(i)},g^{(j)}>)/\sigma^{2}}\leq
C(\epsilon)]$ (41) $\displaystyle\approx$
$\displaystyle\Phi\left(\frac{\sigma_{Z_{1}}}{2}+\frac{\zeta_{1}-\epsilon}{\sigma_{Z_{1}}}\right)-e^{\epsilon}\Phi\left(\frac{\sigma_{Z_{2}}}{2}+\frac{\zeta_{2}-\epsilon}{\sigma_{Z_{2}}}\right)\triangleq
h(\sigma_{Z_{1}},\sigma_{Z_{2}}).$ (42)

Finally, we estimate $\delta$ by deriving the upper bound for
$h(\sigma_{Z_{1}},\sigma_{Z_{2}})$ which is an approximated lower bound to
$\delta$. To this end, we establish the following lemma by analyzing the
property of $h$:

######  Lemma 2.

Given the definitiion of
$\sigma_{Z_{1}}^{2},\sigma_{Z_{2}}^{2},\zeta_{1},\zeta_{2}$ and the
constraints $\|g\|_{2}\leq c$, $\|f\|_{2}\leq c^{\prime}$,
$h(\sigma_{Z_{1}},\sigma_{Z_{2}})$ achieves the upper bound at $k=d$, where

$\displaystyle f=\sqrt{\frac{1}{d(d-1)}}c^{\prime}[(d-1),-1,\ldots,-1],$ (43)
$\displaystyle g=\sqrt{\frac{1}{d(d-1)}}c[(d-1),-1,\ldots,-1].$ (44)

Here $f$ and $g$ share the maximum value at the same dimension, not
necessarily the first one. Thereby one can derive the condition of Eq. (25)
and Eq. (26).

The detailed proof of the lemma is provided in Appendix A-D, which mainly
takes advantage of the monotonicity of $h$. ∎

Note that Thm. 6 is obtained at the worst case where the total number of
invariant permutations $|\mathcal{P}_{s}|$ is the least (except for the case
where all elements are the same). In general, to have the same
$(\varepsilon,\delta)$-DP held, the shuffled Gaussian requires a declining
noise magnitude $\sigma$ with the increase in the total number of permutations
$k$, or the dimensionality of the vector $d$. In fact, the noise variance
$\sigma^{2}$ in the shuffled Gaussian is approximately $O\left(\frac{1}{\log
d}\right)$. The result is interesting in indicating a lower level of privacy
budget $(\varepsilon,\delta)$ is required for the same amount of noise
($\sigma$) applied, illustrating shuffling indeed makes the output
distributions harder to distinguish, and the higher the query dimension, the
more difficult the discrimination.

In the following section, we will discussion how shuffling mechanism could be
applied to DPSGD. It should be noted that although the theorems we give here
is based on the vector form, the conclusion can be easily extended into matrix
form by reshaping matrices into vectors with one-to-one correspondence.

##  V Shuffled DPSGD

In this section, we introduce the shuffled DPSGD mechanism, including the
algorithmic detail, the privacy loss accountant, and its DP guarantee.

###  V-A The Algorithm

Shuffled DPSGD mostly follows the framework of DPSGD but introduces shuffling
to the permutation-invariant part of the neural network at each weights
update. Hence the privacy of gradients or weights in each iteration is
amplified through shuffling without accuracy decay. Alg. 1 for integrating the
shuffling mechanism into DPSGD involves several key steps. The first step is
to randomly initialize the model parameters $W_{0}$. In each iteration, a
random sample batch $L_{t}$ is selected with probability $|B|/N$, where $|B|$
is the batch size and $N$ is the total number of samples. Then the per-sample
gradients of $L_{t}$ are computed and clipped to ensure that the sensitivity
of each gradient is $c$. This per-example gradient clipping step aligns with
that of the normal DPSGD and ensures the condition of
$\|f(x)-f(x^{\prime})\|_{2}\leq c$ is satisfied in Thm. 6. The clipped
gradients are accumulated by batch, and the noise is added to the accumulated
gradients. An additional batch clipping (line 12) is required to meet the
constraint of $\|f(x)\|_{2}\leq c^{\prime}$ in Thm. 6.

As illustrated in the following section, we calculate the noise variance
$\sigma^{2}$ by $|B|,c,N$, training steps $T$ and $\varepsilon,\delta$ by the
specific privacy accountant we choose. Here we apply Advanced Composition and
Privacy Amplification by Subsampling for the accounting. If the noise variance
$\sigma^{2}$ is higher than the noise variance $\sigma_{0}^{2}$ calculated by
DPSGD, the algorithm will fall back to the original implementation of DPSGD.
Otherwise, a random shuffling step would be added upon noise addition before
weights update. It is worth noting that the random shuffling does not impact
the weight update as the permutation invariance property holds not only in the
forward but also in the backward propagation, according to Thm. 3 and 4.

Notably, we choose to add noise before shuffling ($P(y+z)$) instead of after
shuffling ($P(y)+z$) in Alg. 1. The former is more convenient in that we do
not need to shuffle the corresponding weights apart from permuting the
gradients. The two are equivalent as
$P(y+z)=P(y)+P(z),~{}P(z)\sim\mathcal{N}(\bm{0},\sigma^{2}I)$ following the
same distribution of $z$. This indicates $P(y+z)$ has the same distribution
with $P(y)+z$. Hence the change does not alter the privacy guarantee.

Algorithm 1 Shuffled DPSGD

0: (a) Training dataset $X$, (b) privacy budget $\varepsilon,\delta$, (c)
model weights $W$. (d) clipping value $c$, batch clipping value $c^{\prime}$,
batch size $|B|$, total $N$ examples, total $T$ training steps.

0: Private model weights $W_{T+1}$.

1: Initialize $W_{0}$ randomly

2: Compute $\sigma$ for shuffled-DPSGD by advanced composition and
subsampling.

3: Compute $\sigma_{0}$ for DPSGD by advanced composition and subsampling.

4: for $t\in[T]$ do

5: Sample $L_{t}\in X$ with sampling probability $|B|/N$

6: for $i\in[L_{t}]$ do

7: Compute
$\mathbf{g}_{t}\left(x_{i}\right)\leftarrow\nabla_{W_{t}}\mathcal{L}(\left(W_{t},x_{i}\right)$

8:
$\overline{\mathbf{g}}_{t}(x_{i})\leftarrow{\mathbf{g}}_{t}(x_{i})/\max\left(1,\frac{\left\|{\mathbf{g}}_{t}(x_{i})\right\|_{2}}{c}\right)$

9: end for

10: Accumulate the clipped gradients over a batch
$\hat{\mathbf{g}}_{t}=\sum_{i}^{|B|}\overline{\mathbf{g}}_{t}(x_{i})$

11: if $\sigma<\sigma_{0}$ and $W_{t}$ is linear layer or Transformer block
then

12: Clip the batch gradient
$\overline{\mathbf{g}}_{t}=\hat{\mathbf{g}}_{t}/\max\left(1,\frac{\left\|\hat{\mathbf{g}}_{t}\right\|_{2}}{c^{\prime}}\right)$

13: Add noise
$\tilde{\mathbf{g}}_{t}=\frac{1}{|B|}\left(\overline{\mathbf{g}}_{t}+z\right)$,
where $z\sim\mathcal{N}(0,\sigma^{2}c^{2}I)$

14: $W_{t+1}\leftarrow P\left[W_{t}-\eta_{t}\tilde{\mathbf{g}}_{t}\right]$

15: else

16: Add noise
$\tilde{\mathbf{g}}_{t}=\frac{1}{|B|}\left(\hat{\mathbf{g}}_{t}+z\right)$,
where $z\sim\mathcal{N}(0,\sigma_{0}^{2}c^{2}I)$

17: $W_{t+1}\leftarrow W_{t}-\eta_{t}\tilde{\mathbf{g}}_{t}$

18: end if

19: end for

20: return $W_{T+1}$

###  V-B Privacy Budget Accountant

In assessing the privacy cost of DPSGD, the Moments Accountant [1], and the
Renyi Differential Privacy (RDP) Accountant [32] are widely recognized
methods. These approaches accumulate the logarithm of the moments of the
privacy loss variable at each iteration. However, they cannot accurately
estimate the privacy budget for the shuffled DPSGD due to the incompatibility
of the two accountant methods with the computation involving mixture of
Gaussian. Specifically, these algorithms both require an exponential
parameter, denoted as $\alpha$ in RDP and $\lambda$ in Moments Accountant. The
issue emerges when $\alpha$ or $\lambda$ is a non-integer, leading to
difficulties in expressing the PDF of the mixture of Gaussian. Even for
integers, it demands the trouble to calculate multivariate expansions for the
exponential parameter. All these complication hinders us from adopting their
accountant methods.

We have also considered privacy accountant methods such as PLDs [26] and PRVs
[27]. However, these techniques also encounter issues in computing Gaussian
mixture. For example, the PRVs method optimizes the privacy budget by
subsampling, but it produces results that are contradictory to the expected
behavior of Gaussian mixture, yielding higher privacy costs under fixed noise.
This is mainly due to the Fast Fourier Transform (FFT) transformation is
designed for Gaussian distribution, not applicable for the composition of
Gaussian mixture.

Therefore, we consider a general composition method that is irrelevant to the
underlying noise distribution. Hence we adopt the Advanced Composition from
Thm. 1 and the Privacy Amplification by Subsampling from Thm. 2 together for
calculating the privacy budget per training step. Specifically, we set an
identical privacy budget across all training steps, i.e.,
$\epsilon_{j}=\epsilon_{s},\delta_{j}=\delta_{s},\forall j\in[k]$. The
sampling rate $p=|B|/N$. By substituting
$\epsilon=\epsilon_{s},\delta=\delta_{s}$ into Eq. (25), we can compute the
noise variance $\sigma^{2}$ required for each training step under shuffling.

TABLE I: Model configurations and training hyperparameters. Shuffle ratio means the proportion of the weights that are shuffled by our mechanism in the model.  Model | #Trainable Param | Shuffle Ratio | Dataset | #Train Samples $N$ | Learning Rate | Epochs | $\delta$
---|---|---|---|---|---|---|---
ViT | 85.8M | 100% | CIFAR100 | 50,000 | $2\times 10^{-3}$ | 10 | $5\times 10^{-6}$
BERT RoBERTa |  110M 125M |  100% 100% | SST-2 | 67,349 | $5\times 10^{-4}$ | 3 | $1/(2N)$
QQP | 363,846 | $5\times 10^{-4}$ | 18 | $1/(2N)$
MNLI | 392,702 | $5\times 10^{-4}$ | 18 | $1/(2N)$
QNLI | 108,000 | $5\times 10^{-4}$ | 6 | $1/(2N)$
GPT-2 GPT-2-large |  124M 0.838B |  100% 100% | E2E | 42,043 | 0.002 | 10 | $8\times 10^{-6}$
DART | 60,591 | $5\times 10^{-4}$ | 15 | $10^{-5}$
TABLE II: Verifying permutation invariance on ViT and BERT in non-private and DPSGD modes.  Method | non-private | shuffled non-private | DPSGD | shuffled with same $\sigma$
---|---|---|---|---
| test loss | test accuracy | test loss | test accuracy | test loss | test accuracy | test loss | test accuracy
ViT | 0.6362 | 89.68% | 0.6362 | 89.68% | 1.330 | 85.56% | 1.330 | 85.56%
BERT | 0.2302 | 92.31% | 0.2302 | 92.31% | 1.054 | 87.38% | 1.054 | 87.38%

##  VI Experiments

We verify the theorems and evaluate the performance of the shuffled DPSGD in
this section. The experiments are designed to address the following key
research questions: (1) Does the shuffling mechanism guarantee weights
permutation invariance? (2) How does the F-W method perform in approximating
the sum of log-normal distributions? (3) What is the relationship among
$\sigma,\varepsilon,d$ in the shuffled setting? (4) How does the accuracy of
large models improve by Shuffled DPSGD? (5) How does Shuffled DPSGD perform
under auditing? (6) What is the overhead introduced by the shuffling
mechanism? The answers to these questions are listed from Sec. VI-B to Sec.
VI-G.

###  VI-A Experimental Setup

Models, datasets and tasks. We conduct comprehensive experiments on a range of
models, datasets, and tasks in both CV and NLP fields. The first category of
tasks is CV classification, the second being NLP classification and the third
one is text generation. For CV classification, we train ViT [13] to classify
the CIFAR-100 [28] dataset. For NLP classification tasks, we employ two models
BERT[11] and RoBERTa on four datasets: stanford sentiment treebank (SST-2),
quora question pairs (QQP), Question Natural Language Inference (QNLI), and
MultiNLI (MNLI) from the GLUE benchmark [43]. For the text generation task, we
use GPT-2 and GPT-2-large [36] to generate text given E2E [35] and DART [33]
datasets. ViT is pre-trained on ImageNet, whereas the rest models are adopted
from the pre-trained ones in the Huggingface library. We summarize the
configuration and training/fine-tuning hyperparameters in Table I.

Metrics. For the classification tasks of CV and NLP, we use the testing
accuracy as the evaluation metric. To verify the weights permutation
invariance of the shuffling mechanism, we additionally include loss as the
metric. As to the text generation tasks, BLEU and Meteor are employed as the
evaluation metrics. Except for the loss, a higher value indicates a better
performance for all metrics.

Baselines. We introduce the state-of-the-art works on DPSGD as baselines,
which are Ghost clipping [31] and MixOpt [7]. Ghost clipping and MixOpt are
algorithmically optimized for per-sample gradient calculation based on Opacus
[47] library. Opacus is a popular pytorch-based DPSGD code platform, which is
continuously updated, and offers three different privacy accountant methods:
RDP, GDP and PRV. RDP accountant is adopted in our experiments as the
accountant method for all baselines. In ghost clipping, the per-sample
gradients is clipped without being instantiated, thus saving both running time
and memory costs. MixOpt method is further improved from Book-Keep [6] (A
variant of ghostclipping) and provides a lighter running time overhead than
Book-Keep.

Implementation details. We run the experiments on Nvidia GeForce RTX 3090 GPU
except for training GPT-2 large on Nvidia A100 GPU. The implementation is
Pytorch-based. Baselines are reproduced in their respective environments. In
the hyperparameter setting of all NLP tasks, we set the clipping value to 0.1,
and fix $\delta$ to $1/(2N)$ where $N$ is the number of training samples in
each dataset. For CV tasks, we set the clipping value to 1, and fix
$\delta=5\times 10^{-6}$. Other hyperparameters are listed in Table I.

Shuffle implementation. For the implementation of the shuffling mechanism, we
perform permutation by creating random row and column indices for each weight
matrix, instead of directly performing matrix multiplications. This can
greatly reduce the time overhead of which the results can be found at Sec.
VI-G. The code detail is provided in Appendix B-A.

###  VI-B Verifying Permutation Invariance

We first show the permutation invariance holds by conducting experiments to
compare the difference in weights trained under shuffling and that without
shuffling. We fix the random seed for a straightforward comparison. By
calculating the $\ell_{2}$ norm of the weights difference pre- and post-
shuffling on ViT, we observed a significant discrepancy of 1063.02, showing
that the shuffling mechanism induces substantial perturbation in the model
weights.

Meanwhile, we verify permutation invariance by training ViT on CIFAR100 and
Bert on SST-2 in both non-private mode and differentially-private mode. The
same noise multiplier $\sigma$ (equivalent to $\varepsilon=1$ in normal DPSGD)
is applied and the random seed is fixed. The training results with or without
shuffling are listed in Table II, showing exactly the same test loss and
accuracy with shuffling or not. It is evidenced that applying the proposed
shuffling mechanism results in zero difference between the shuffled and
original model, indicating that the model is trained equivalently under
shuffling.

Figure 2: The comparison of different approximation methods for the sum of log-normal distribution. We set $\sigma=0.25$ and dimension $d=10^{8}$ to depict its CDF curve.  TABLE III: Accuracy (%) comparison of Shuffled DPSGD, Ghost clipping and MixOpt on CIFAR-100 classification tasks. The optimal performance is marked in bold. Model |  | $\varepsilon=0.1$ | $\varepsilon=0.5$ | $\varepsilon=1$
---|---|---|---|---
Non-private | Ghost | MixOpt | Shuffled-DPSGD | Ghost | MixOpt | Shuffled-DPSGD | Ghost | MixOpt | Shuffled-DPSGD
ViT | 89.68 | 1.20 | 1.26 | 67.31 | 72.99 | 72.98 | 75.17 | 75.53 | 75.55 | 75.61
TABLE IV: Accuracy (%) comparison of Shuffled DPSGD, Ghost clipping and MixOpt on NLP classification tasks. The optimal performance is marked in bold. Model | Datasets | Non-private | $\varepsilon=0.1$ | $\varepsilon=0.5$ | $\varepsilon=1$
---|---|---|---|---|---
Ghost | MixOpt | Shuffled-DPSGD | Ghost | MixOpt | Shuffled-DPSGD | Ghost | MixOpt | Shuffled-DPSGD
BERT | SST-2 | 92.32 | 69.27 | 64.56 | 87.5 | 86.58 | 87.38 | 88.42 | 88.19 | 86.93 | 88.30
QQP | 90.49 | 69.51 | 69.73 | 82.14 | 80.85 | 80.51 | 82.25 | 83.39 | 82.07 | 82.26
MNLI | 83.27 | 55.65 | 55.58 | 73.04 | 70.33 | 70.12 | 73.05 | 73.52 | 73.25 | 73.07
QNLI | 89.51 | 51.29 | 59.69 | 81.49 | 81.03 | 81.64 | 82.04 | 81.77 | 81.82 | 81.78
RoBERTa | SST-2 | 94.95 | 87.50 | 87.62 | 92.32 | 90.82 | 92.08 | 91.63 | 91.86 | 91.62 | 91.51
QQP | 91.50 | 68.19 | 68.28 | 83.59 | 80.67 | 80.51 | 83.37 | 83.39 | 83.20 | 83.35
MNLI | 87.49 | 55.11 | 53.03 | 79.29 | 78.14 | 78.01 | 79\. 21 | 79.78 | 79.84 | 79.38
QNLI | 93.56 | 73.86 | 73.86 | 85.67 | 85.22 | 85.92 | 85.94 | 85.59 | 86.14 | 85.76

###  VI-C Sum of Lognormal Approximations

We empirically evaluate the approximation error of the F-W method [18] used in
our mechanism, and compare it with different approximation methods including
Monte-carlo method, S-Y method, LSQ method [52] and KDE method [3]. Monte-
carlo method calculates the sum of randomly sampled log-normal variables and
repeats the procedure for 1000 times to depict the CDF curve. S-Y method
computes the distribution for the sum of log-normal iteratively. It first
computes the distribution for the sum of two log-normal random variables, and
then adds the third one up to compute the new distribution. The summation goes
iteratively until all $d$ log-normal random variables are summed up. LSQ
method leverages the least squares method to fit the sum of log-normal
distributions, whereas KDE method adopts the Gaussian kernel density
estimation method to fit the sum of log-normal distributions.

Here we consider the Monte-carlo method to be the closest to the groundtruth
distribution, but the method demands a very large number of samples to give an
accurate estimate. For example, sampling 1000 points for $d=10^{8}$ took 62
minutes, which is hardly fit for DPSGD. Except for the F-W method, all other
methods are numerical without any analytical form of the CDF. Furthermore, the
LSQ and KDE methods both depend on sampling which is too heavy-weighted even
if cutting down the number of samples.

The results are shown in Fig. 2. As we can see, the F-W method approximation
of the sum of log-normal distribution is sufficiently close to the ‘ground
truth’ (Monte-carlo). S-Y method provides poor performance at a lower value.
Although the LSQ method and KDE method have better performance, they require
sampling similar to Monte-carlo and do not have a closed-form expression.
Therefore, we conclude that the F-W method is the best choice for the
approximation of the sum of log-normal in our design.

Figure 3: Comparison of the relations between $\sigma$ and $\varepsilon$ in both unshuffled and shuffled DPSGD. For (a)-(e) we calculate different $\sigma$s with $\varepsilon\in\\{0.25,0.5,1,2,4\\}$. And ”GPT2-L E” represent the GPT-2-large model trained with E2E dataset and ”GPT2-L D” represent the GPT-2-large model trained with DART dataset.  TABLE V: Comparison of Shuffled DPSGD, Ghost clipping and MixOpt on GPT-2 and GPT-2-large. The optimal performance is marked in bold. Models | Datasets | Non-private | $\varepsilon=0.1$ | $\varepsilon=0.5$ | $\varepsilon=1$
---|---|---|---|---|---
Ghost | MixOpt | Shuffled-DPSGD | Ghost | MixOpt | Shuffled-DPSGD | Ghost | MixOpt | Shuffled-DPSGD
GPT-2 | DART(BLEU) | 62.00 | 1.91 | 0.92 | 38.73 | 23.71 | 33.51 | 40.56 | 40.94 | 32.49 | 42.68
DART (METEOR) | 0.474 | 0.005 | 0.008 | 0.333 | 0.298 | 0.318 | 0.3612 | 0.356 | 0.341 | 0.3859
E2E (BLEU) | 66.75 | 0.18 | 0.01 | 45.93 | 35.80 | 44.79 | 49.77 | 53.80 | 46.29 | 54.93
E2E (METEOR) | 0.4537 | 0.0201 | 0.0108 | 0.3119 | 0.2877 | 0.3091 | 0.3286 | 0.3328 | 0.3174 | 0.3436
GPT-2-large | DART(BLEU) | 66.28 | 5.74 | 4.73 | 53.45 | 47.28 | 46.27 | 54.77 | 52.36 | 52.63 | 53.97
DART (METEOR) | 0.521 | 0.073 | 0.045 | 0.4570 | 0.423 | 0.418 | 0.4791 | 0.449 | 0.450 | 0.4936
E2E (BLEU) | 68.80 | 0.21 | 0.09 | 63.46 | 30.97 | 33.82 | 64.51 | 45.42 | 45.55 | 65.02
E2E (METEOR) | 0.4625 | 0.0549 | 0.0487 | 0.3986 | 0.2410 | 0.2590 | 0.4195 | 0.3180 | 0.3231 | 0.4276

###  VI-D Relations of $\sigma,\varepsilon,$ & $d$

The theoretical relations of $\sigma,\varepsilon,d$ provided in Thm. 6 is too
complicated to tell straightforwardly. Hence we numerically show how the three
key parameters interact in the real settings.

Due to space limitation, we only display results of six representative
experiments, each with parameter size $d=$ 85.8M, 110M, 125M, 124M, 838M,
respectively. The $\sigma-\varepsilon$ curves are depicted in Fig. 3. We
observe that the shuffling mechanism has a significant impact on the privacy
accountant of DPSGD across all model sizes. From the figure, the $\sigma$s
almost flattened out across different $\varepsilon$s in shuffled mechanism,
leaving other factors like $d$ to blame for its change in values. As we focus
on the high privacy regime ($\varepsilon$ as low as $0.25$), we observe that,
the $\sigma$ in the shuffled DPSGD is merely 5-7% of that of the unshuffled.

It may be attributed to that the noise magnitude $\sigma$ at the order
$O(1/\sqrt{\log d})$, which is very small at extremely large $d$s. We can tell
that $d$ mainly appears along with $e^{\frac{1}{\sigma^{2}}}$ as
$(d-1)e^{-\frac{d}{(d-1)\sigma^{2}}}~{}\text{in}~{}\sigma_{Z_{i}},\zeta_{i}$,
where $i=1,2$. Therefore, if the model’s dimension reaches $10^{9}$, the
$\sigma$ is dominated by $d$ but not by the $\varepsilon$.

For a more straightforward demonstration, we show the heatmap in Fig. 4 to
present the relations of $\varepsilon,\sigma$ and dimensionality for shuffled
DPSGD. The column of $d=1$ represents the $\sigma$ of an unshuffled mechanism.
In the unshuffled case, $\sigma$ increases fast with the decrease of
$\varepsilon$. However, as dimensionality $d$ increases, $\sigma$ drops
drastically and the change in $\varepsilon$ barely affects $\sigma$.
Therefore, in the shuffled case, $d$ becomes the major impact factor to the
value of $\sigma$.

Figure 4: The $\sigma$s from the unshuffled ($d=1$) and shuffled DPSGD under
different $\varepsilon$s and $d$s.

###  VI-E Performance of Shuffled DPSGD

We evaluate the real-world performance of shuffled DPSGD in comparison with
the baselines on large-scale models. The results are reported according to the
categories of the tasks.

CV Classification. The setup of ViT follow the ViT checkpoint google/vit
-base-patch16-224 from Huggingface transformers library [45], pretrained on
ImageNet-21k and fine-tuned on ImageNet (also referred to as ILSVRC2012).
Since this pre-trained model is very powerful, easily reaching over $96\%$
accuracy under all circumstances on CIFAR-10, we hence omit the results but
select a more difficult task — 100-class classification on CIFAR-100 — for
performance test. The results in Table III show that our shuffled DPSGD
consistently outperforms all baselines under various $\varepsilon$s, and the
improvement is more significant at small $\varepsilon$ values. Particularly,
at $\varepsilon=0.1$ where both Ghost clipping and MixOpt have performance
close to random guesses, shuffled DPSGD enjoys a high accuracy well over
$60\%$.

However, such an improvement becomes marginal at large $\varepsilon$s. As we
analyze, this is mostly due to the inexact approximation of F-W method at
small $\sigma$s. In Thm. 6, the variance of per normal distribution in the sum
of log-normals is approximated as $\frac{c^{2}}{\sigma^{2}}$, which grows with
small $\sigma$s. As stated in [53], the F-W approximation method is quite
accurate when the variance of log-normal distributions is low but becomes less
accurate at a high variance. Hence, at small $\sigma$s, or large
$\varepsilon$s, the power of the approximation approach diminishes.

NLP Classification. We finetune a raw BERT checkpoint bert- base-uncased and a
RoBERTa checkpoint roberta-base in a differentially-private way for NLP
classification, in which both pre-trained models are available in the
Huggingface library. The results under all cases are presented in Table IV.
The trend is similar to CV classification, as our method almost always
achieves higher accuracy than baselines at the same privacy level. Notably,
our accuracy is merely $1-4\%$ shy of the non-private case, showing great
applicability of our method to privacy-preserving NLP tasks. In fact, in NLP
tasks, quite different from the CV task, the accuracy of our method is only
mildly affected by the $\varepsilon$ value. This reflects the results of Sec.
VI-D where $\varepsilon$’s impact on $\sigma$ gets weakened in the high-
dimensional case.

Table-To-Text Generation. We fine-tune the pre-trained model checkpoint gpt2
and gpt2-large from Huggingface in a differentially-private way. The results
are reported in Table V. It can be found that the performance of the shuffled
DPSGD is far superior to baselines, especially at $\varepsilon=0.1$. This is
in line with the analysis that the accuracy performance of our method is less
affected by the limited privacy budget thanks to shuffling. It is also clear
that the performance gap between the shuffled DPSGD and the non-private method
is smaller on GPT-2-large compared to GPT-2. In fact, at $\varepsilon=1$, the
performance of our method on GPT-2-large is very close to that of the non-
private case, demonstrating that our shuffling approach enjoys a unique
advantage on large models, verifying the intuition that the shuffled DPSGD
benefits from high-dimensional model weights.

TABLE VI: Auditing results of shuffled DPSGD on ViT, CIFAR100. Theoretical $\varepsilon$ | 0.5 | 1.0
---|---|---
Audited $\varepsilon$ | 0.4771 | 0.7005

###  VI-F Privacy Aduting of Shuffled DPSGD

So far, our privacy accountant relies on some relaxations and approximations.
We would like to see how our mechanism acts against real-world auditing. Hence
we implement the auditing method for DPSGD in [34], which presents the most
recent progress in DPSGD auditing as far as we know. We conduct auditing tests
in the training of ViT on CIFAR-100 under the theoretical $\varepsilon=0.5,1$
by shuffled DPSGD. A total of 10,000 training steps is performed to get the
records through ‘white-box access with gradient canaries.’ The setup of ‘Dirac
canary: All gradient values are zero except at a single index’ in [34] is
reused in our test with a batch size 1000 and epoch number 200 to get
sufficient observations.

We apply the auditing method to the shuffled DPSGD and obtain the auditing
$\varepsilon$s as

$\varepsilon=\max\left\\{\ln\left(\frac{1-{\alpha}-\delta}{{\beta}}\right),\ln\left(\frac{1-{\beta}-\delta}{{\alpha}}\right),0\right\\}$
(45)

where $\alpha$ and $\beta$ represent the type I error and type II error,
respectively. We compare the empirical $\varepsilon$s with the theoretical
values in Table VI. For $\varepsilon=0.5$, we eliminate cases where
$\alpha<4\times 10^{-4}$ and $\beta<4\times 10^{-4}$ to mitigate the impact of
inaccurate measurement of the small probability events. The audited
$\varepsilon$ is a reasonably close lower bound to the theoretical
counterparts.

This indicates that our privacy accountant for shuffled DPSGD provides
reasonably accurate estimations. However, there is still a discrepancy between
the theoretical and empirical $\varepsilon$ values, which can be attributed to
the approximations in the theoretical analysis and the fact that the audited
privacy level is mostly a lower bound to the actual privacy level.
Nevertheless, considering the limited observations ($10^{4}$), the auditing
results is acceptable as the gap between the audited and the theoretical upper
bound is not closed in [34] either.

TABLE VII: Time costs of different shuffling implementations. method | Times(ms)
---|---
Index shuffle | 0.9799
Matrix multiplication | 1316.6
Sparse matrix multiplication | 322.62
TABLE VIII: Average epoch time of running shuffled DPSGD. Model | Unshuffled | Shuffled
---|---|---
ViT, CIFAR | 2min25s | 2min42s
BERT, QNLI | 28min28s | 28min53s
RoBERTa, QNLI | 29min45s | 30min11s
GPT-2, E2E | 30min1s | 30min13s
GPT-2-large, E2E (on A100) | 43min25s | 44min29s

###  VI-G Overhead of Shuffled DPSGD

We compare the overhead of shuffling under different implementations: index
operations (our approach), matrix multiplication (torch.mm), and sparse matrix
multiplication (torch.sparse.mm) in randomly shuffling a $10,000\times 10,000$
matrix. We found that index operations greatly save the running time, which is
about 0.1% of that by matrix multiplication and 0.3% of that by sparse matrix
multiplication. The results are in Table VII.

The overall computational overhead of shuffled DPSGD is measured by the
average epoch running time as reported in Table VIII. All experiments are
conducted on a single RTX 3090 GPU except for GPT-2 large. We can see that the
additional overhead of shuffling is under 30 seconds except for GPT-2-large,
which is 64 seconds, mostly due to its billion-level parameters and the
enormous permutation space. Nevertheless, the shuffling overhead takes only
2.3% of the overall training time in shuffled DPSGD, which is almost
negligible in training.

##  VII Conclusion

We developed the theoretical condition for $(\epsilon,\delta)$-DP to hold
under shuffled Gaussian mechanism. Based on the theory, we proposed shuffled
DPSGD, a method that enhances the accuracy of DPSGD by incorporating a
shuffling mechanism to reduce the additive noise, thus boosting the overall
model performance. Our shuffling mechanism, designed to maintain weights
permutation invariance, is adaptable to a variety of up-to-date neural
networks. Experimental results confirmed our findings, and showed that
shuffled DPSGD significantly improves performance over baselines on large
models, highlighting its lightweighted implementation and running time
overhead.

## References

  * [1] M. Abadi, A. Chu, I. Goodfellow, H. B. McMahan, I. Mironov, K. Talwar, and L. Zhang, “Deep Learning with Differential Privacy,” in _Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security (CCS)_. ACM, 2016, pp. 308–318.
  * [2] R. Anil, B. Ghazi, V. Gupta, R. Kumar, and P. Manurangsi, “Large-scale differentially private bert,” in _Conference on Empirical Methods in Natural Language Processing_ , 2021.
  * [3] Ö. Askin, T. Kutta, and H. Dette, “Statistical quantification of differential privacy: A local approach,” in _43rd IEEE Symposium on Security and Privacy, SP 2022, San Francisco, CA, USA, May 22-26, 2022_. IEEE, 2022, pp. 402–421. [Online]. Available: https://doi.org/10.1109/SP46214.2022.9833689
  * [4] B. Balle, J. Bell, A. Gascón, and K. Nissim, “The privacy blanket of the shuffle model,” in _Advances in Cryptology – CRYPTO 2019_ , A. Boldyreva and D. Micciancio, Eds. Cham: Springer International Publishing, 2019, pp. 638–667.
  * [5] A. Bittau, U. Erlingsson, P. Maniatis, I. Mironov, A. Raghunathan, D. Lie, M. Rudominer, U. Kode, J. Tinnes, and B. Seefeld, “Prochlo: Strong privacy for analytics in the crowd,” in _Proceedings of the 26th Symposium on Operating Systems Principles_ , ser. SOSP ’17. New York, NY, USA: Association for Computing Machinery, 2017, p. 441–459. [Online]. Available: https://doi.org/10.1145/3132747.3132769
  * [6] Z. Bu, J. Mao, and S. Xu, “Scalable and efficient training of large convolutional neural networks with differential privacy,” in _Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28 - December 9, 2022_ , 2022. [Online]. Available: http://papers.nips.cc/paper\\_files/paper/2022/hash/fa5617c176e76fee83f3f9947fdf9f3f-Abstract-Conference.html
  * [7] Z. Bu, Y. Wang, S. Zha, and G. Karypis, “Differentially private optimization on large model at small cost,” in _International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA_ , ser. Proceedings of Machine Learning Research, A. Krause, E. Brunskill, K. Cho, B. Engelhardt, S. Sabato, and J. Scarlett, Eds., vol. 202. PMLR, 2023, pp. 3192–3218. [Online]. Available: https://proceedings.mlr.press/v202/bu23a.html
  * [8] N. Carlini, C. Liu, Ú. Erlingsson, J. Kos, and D. Song, “The secret sharer: Evaluating and testing unintended memorization in neural networks,” in _28th USENIX Security Symposium, USENIX Security 2019, Santa Clara, CA, USA, August 14-16, 2019_ , N. Heninger and P. Traynor, Eds. USENIX Association, 2019, pp. 267–284.
  * [9] A. Cheu, A. Smith, J. Ullman, D. Zeber, and M. Zhilyaev, “Distributed differential privacy via shuffling,” in _Advances in Cryptology – EUROCRYPT 2019_ , Y. Ishai and V. Rijmen, Eds. Cham: Springer International Publishing, 2019, pp. 375–403.
  * [10] S. De, L. Berrada, J. Hayes, S. L. Smith, and B. Balle, “Unlocking high-accuracy differentially private image classification through scale,” _arXiv preprint arXiv:2204.13650_ , 2022.
  * [11] J. Devlin, M. Chang, K. Lee, and K. Toutanova, “BERT: pre-training of deep bidirectional transformers for language understanding,” in _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL-HLT 2019, Minneapolis, MN, USA, June 2-7, 2019, Volume 1 (Long and Short Papers)_ , J. Burstein, C. Doran, and T. Solorio, Eds. Association for Computational Linguistics, 2019, pp. 4171–4186. [Online]. Available: https://doi.org/10.18653/v1/n19-1423
  * [12] J. Dong, A. Roth, and W. Su, “Gaussian differential privacy,” _Journal of the Royal Statistical Society_ , 2021.
  * [13] A. Dosovitskiy, L. Beyer, A. Kolesnikov, D. Weissenborn, X. Zhai, T. Unterthiner, M. Dehghani, M. Minderer, G. Heigold, S. Gelly, J. Uszkoreit, and N. Houlsby, “An image is worth 16x16 words: Transformers for image recognition at scale,” in _9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021_. OpenReview.net, 2021. [Online]. Available: https://openreview.net/forum?id=YicbFdNTTy
  * [14] C. Dwork, F. McSherry, K. Nissim, and A. Smith, “Calibrating noise to sensitivity in private data analysis,” in _Theory of cryptography conference_. Springer, 2006, pp. 265–284.
  * [15] U. Erlingsson, V. Feldman, I. Mironov, A. Raghunathan, K. Talwar, and A. Thakurta, “Amplification by shuffling: from local to central differential privacy via anonymity,” in _Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms_ , ser. SODA ’19. USA: Society for Industrial and Applied Mathematics, 2019, p. 2468–2479.
  * [16] V. Feldman, A. McMillan, and K. Talwar, “Hiding among the clones: A simple and nearly optimal analysis of privacy amplification by shuffling,” in _2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)_ , 2022, pp. 954–964.
  * [17] ——, “Hiding among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling,” in _2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)_. IEEE, 2022, pp. 954–964.
  * [18] L. Fenton, “The sum of log-normal probability distributions in scatter transmission systems,” _IRE Transactions on Communications Systems_ , vol. 8, no. 1, pp. 57–67, 1960.
  * [19] A. Golatkar, A. Achille, Y.-X. Wang, A. Roth, M. Kearns, and S. Soatto, “Mixed differential privacy in computer vision,” _2022 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , pp. 8366–8376, 2022.
  * [20] M. Gooneratne, K. C. Sim, P. Zadrazil, A. Kabel, F. Beaufays, and G. Motta, “Low-rank gradient approximation for memory-efficient on-device training of deep neural network,” _ICASSP 2020 - 2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , pp. 3017–3021, 2020.
  * [21] S. Gopi, Y. T. Lee, and L. Wutschitz, “Numerical composition of differential privacy,” _Advances in Neural Information Processing Systems_ , vol. 34, pp. 11 631–11 642, 2021.
  * [22] J. He, X. Li, D. Yu, H. Zhang, J. Kulkarni, Y. T. Lee, A. Backurs, N. Yu, and J. Bian, “Exploring the limits of differentially private deep learning with group-wise clipping,” in _The Eleventh International Conference on Learning Representations_ , 2023. [Online]. Available: https://openreview.net/forum?id=oze0clVGPeX
  * [23] S. Hoory, A. Feder, A. Tendler, S. Erell, A. Peled-Cohen, I. Laish, H. Nakhost, U. Stemmer, A. Benjamini, A. Hassidim, and Y. Matias, “Learning and evaluating a differentially private pre-trained language model,” in _Findings of the Association for Computational Linguistics: EMNLP 2021_. Punta Cana, Dominican Republic: Association for Computational Linguistics, Nov. 2021, pp. 1178–1189. [Online]. Available: https://aclanthology.org/2021.findings-emnlp.102
  * [24] P. Kairouz, B. Mcmahan, S. Song, O. Thakkar, A. Thakurta, and Z. Xu, “Practical and private (deep) learning without sampling or shuffling,” in _Proceedings of the 38th International Conference on Machine Learning_ , ser. Proceedings of Machine Learning Research, M. Meila and T. Zhang, Eds., vol. 139. PMLR, 18–24 Jul 2021, pp. 5213–5225. [Online]. Available: https://proceedings.mlr.press/v139/kairouz21b.html
  * [25] A. Koskela and A. Honkela, “Computing differential privacy guarantees for heterogeneous compositions using fft,” 2021.
  * [26] A. Koskela, J. Jälkö, and A. Honkela, “Computing tight differential privacy guarantees using fft,” pp. 2560–2569, 26–28 Aug 2020. [Online]. Available: https://proceedings.mlr.press/v108/koskela20b.html
  * [27] A. Koskela, J. Jälkö, L. Prediger, and A. Honkela, “Tight differential privacy for discrete-valued mechanisms and for the subsampled gaussian mechanism using fft,” pp. 3358–3366, 13–15 Apr 2021. [Online]. Available: https://proceedings.mlr.press/v130/koskela21a.html
  * [28] A. Krizhevsky, G. Hinton _et al._ , “Learning multiple layers of features from tiny images,” Citeseer, Tech. Rep., 2009.
  * [29] A. Kurakin, S. Chien, S. Song, R. Geambasu, A. Terzis, and A. Thakurta, “Toward training at imagenet scale with differential privacy,” _CoRR_ , vol. abs/2201.12328, 2022. [Online]. Available: https://arxiv.org/abs/2201.12328
  * [30] T. Li, L. Tan, Z. Huang, Q. Tao, Y. Liu, and X. Huang, “Low dimensional trajectory hypothesis is true: Dnns can be trained in tiny subspaces,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 2022.
  * [31] X. Li, F. Tramer, P. Liang, and T. Hashimoto, “Large language models can be strong differentially private learners,” in _International Conference on Learning Representations_ , 2022. [Online]. Available: https://openreview.net/forum?id=bVuP3ltATMz
  * [32] I. Mironov, K. Talwar, and L. Zhang, “Rényi differential privacy of the sampled gaussian mechanism,” _CoRR_ , vol. abs/1908.10530, 2019.
  * [33] L. Nan, D. R. Radev, R. Zhang, A. Rau, A. Sivaprasad, C. Hsieh, X. Tang, A. Vyas, N. Verma, P. Krishna, Y. Liu, N. Irwanto, J. Pan, F. Rahman, A. Zaidi, M. Mutuma, Y. Tarabar, A. Gupta, T. Yu, Y. C. Tan, X. V. Lin, C. Xiong, R. Socher, and N. F. Rajani, “DART: open-domain structured data record to text generation,” in _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL-HLT 2021, Online, June 6-11, 2021_ , K. Toutanova, A. Rumshisky, L. Zettlemoyer, D. Hakkani-Tür, I. Beltagy, S. Bethard, R. Cotterell, T. Chakraborty, and Y. Zhou, Eds. Association for Computational Linguistics, 2021, pp. 432–447. [Online]. Available: https://doi.org/10.18653/v1/2021.naacl-main.37
  * [34] M. Nasr, J. Hayes, T. Steinke, B. Balle, F. Tramèr, M. Jagielski, N. Carlini, and A. Terzis, “Tight auditing of differentially private machine learning,” in _32nd USENIX Security Symposium, USENIX Security 2023, Anaheim, CA, USA, August 9-11, 2023_ , J. A. Calandrino and C. Troncoso, Eds. USENIX Association, 2023, pp. 1631–1648. [Online]. Available: https://www.usenix.org/conference/usenixsecurity23/presentation/nasr
  * [35] J. Novikova, O. Dusek, and V. Rieser, “The E2E dataset: New challenges for end-to-end generation,” in _Proceedings of the 18th Annual SIGdial Meeting on Discourse and Dialogue, Saarbrücken, Germany, August 15-17, 2017_ , K. Jokinen, M. Stede, D. DeVault, and A. Louis, Eds. Association for Computational Linguistics, 2017, pp. 201–206. [Online]. Available: https://doi.org/10.18653/v1/w17-5525
  * [36] A. Radford, J. Wu, R. Child, D. Luan, D. Amodei, and I. Sutskever, “Language models are unsupervised multitask learners,” _OpenAI Blog_ , vol. 1(8):9, 2019.
  * [37] M. A. Rahman, T. Rahman, R. Laganière, and N. Mohammed, “Membership inference attack against differentially private deep learning model,” _Transactions on Data Privacy_ , vol. 11, no. 1, pp. 61–79, 2018. [Online]. Available: http://www.tdp.cat/issues16/tdp.a289a17.pdf
  * [38] A. Sablayrolles, M. Douze, C. Schmid, Y. Ollivier, and H. Jégou, “White-box vs black-box: Bayes optimal strategies for membership inference,” in _International Conference on Machine Learning_ , 2019.
  * [39] S. Song, K. Chaudhuri, and A. D. Sarwate, “Stochastic gradient descent with differentially private updates,” in _2013 IEEE Global Conference on Signal and Information Processing_. IEEE, 2013, pp. 245–248.
  * [40] T. Steinke, “Composition of differential privacy & privacy amplification by subsampling,” _ArXiv_ , vol. abs/2210.00597, 2022. [Online]. Available: https://api.semanticscholar.org/CorpusID:252683292
  * [41] . Thijs Vogels, . Sai Praneeth Karimireddy, and M. Jaggi, “Powersgd: Practical low-rank gradient compression for distributed optimization,” in _Proceedings of the Advances in Neural Information Processing Systems (NeurIPS)_ , 2019.
  * [42] A. Vaswani, N. M. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polosukhin, “Attention is all you need,” in _Neural Information Processing Systems_ , 2017.
  * [43] A. Wang, A. Singh, J. Michael, F. Hill, O. Levy, and S. R. Bowman, “GLUE: A multi-task benchmark and analysis platform for natural language understanding,” in _7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019_. OpenReview.net, 2019. [Online]. Available: https://openreview.net/forum?id=rJ4km2R5t7
  * [44] C. Wang, B. Su, J. Ye, R. Shokri, and W. Su, “Unified Enhancement of Privacy Bounds for Mixture Mechanisms via $f$-Differential Privacy,” _Advances in Neural Information Processing Systems (NeurIPS)_ , vol. 36, 2024\.
  * [45] T. Wolf, L. Debut, V. Sanh, J. Chaumond, C. Delangue, A. Moi, P. Cistac, T. Rault, R. Louf, M. Funtowicz, J. Davison, S. Shleifer, P. von Platen, C. Ma, Y. Jernite, J. Plu, C. Xu, T. L. Scao, S. Gugger, M. Drame, Q. Lhoest, and A. M. Rush, “Transformers: State-of-the-art natural language processing,” in _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations_. Online: Association for Computational Linguistics, Oct. 2020, pp. 38–45. [Online]. Available: https://www.aclweb.org/anthology/2020.emnlp-demos.6
  * [46] H. Xu, L. Xiang, H. Ye, D. Yao, P. Chu, and B. Li, “Permutation equivariance of transformers and its applications,” in _Proceedings of the IEEE / CVF Computer Vision and Pattern Recognition Conference_ , 2024.
  * [47] A. Yousefpour, I. Shilov, A. Sablayrolles, D. Testuggine, K. Prasad, M. Malek, J. Nguyen, S. Ghosh, A. Bharadwaj, J. Zhao, G. Cormode, and I. Mironov, “Opacus: User-friendly differential privacy library in pytorch,” in _NeurIPS 2021 Workshop Privacy in Machine Learning_ , 2021. [Online]. Available: https://openreview.net/forum?id=EopKEYBoI-
  * [48] D. Yu, S. Naik, A. Backurs, S. Gopi, H. A. Inan, G. Kamath, J. Kulkarni, Y. T. Lee, A. Manoel, L. Wutschitz, S. Yekhanin, and H. Zhang, “Differentially private fine-tuning of language models,” in _International Conference on Learning Representations_ , 2022. [Online]. Available: https://openreview.net/forum?id=Q42f0dfjECO
  * [49] D. Yu, H. Zhang, W. Chen, and T.-Y. Liu, “Do not let privacy overbill utility: Gradient embedding perturbation for private learning,” in _International Conference on Learning Representations_ , 2021.
  * [50] D. Yu, H. Zhang, W. Chen, J. Yin, and T.-Y. Liu, “Large scale private learning via low-rank reparametrization,” in _International Conference on Machine Learning_. PMLR, 2021, pp. 12 208–12 218.
  * [51] H. Zhang, I. Mironov, and M. Hejazinia, “Wide network learning with differential privacy,” _CoRR_ , vol. abs/2103.01294, 2021. [Online]. Available: https://arxiv.org/abs/2103.01294
  * [52] X. Zhang, “A survey of the sum of lognormal distribution and some recent results,” Ph.D. dissertation, University of British Columbia, 2022. [Online]. Available: https://open.library.ubc.ca/collections/ubctheses/24/items/1.0421709
  * [53] ——, “A survey of the sum of lognormal distribution and some recent results,” Ph.D. dissertation, University of British Columbia, 2022. [Online]. Available: https://open.library.ubc.ca/collections/ubctheses/24/items/1.0421709
  * [54] Y. Zhou, Z. S. Wu, and A. Banerjee, “Bypassing the ambient dimension: Private sgd with gradient subspace identification,” in _International Conference on Learning Representations_ , 2021.
  * [55] L. Zhu, Z. Liu, and S. Han, “Deep leakage from gradients,” in _Proc. of the Advances in Neural Information Processing Systems (NIPS)_ , 2019.

##  Appendix A Proofs of Theorems

###  A-A Proof of Theorem 1

###### Proof.

As we have

$\displaystyle
P(W)=\\{P_{1}^{\top}W_{t},~{}b_{t}P_{1},~{}W_{t+1}P_{1},~{}~{}b_{t+1}\\},$
(46)

we can get the following equations by substituting the above into Eq. 3 and 4:

$\displaystyle h(x_{t}W_{t}^{\top}P_{1}+b_{t}P_{1})=x_{t+1}P_{1},$ (47)
$\displaystyle h(x_{t+1}P_{1}P_{1}^{\top}W_{t+1}^{\top}+b_{t+1})=x_{t+2}.$
(48)

Therefore, the forwarding result is still $x_{t+2}$, satisfying forward
invariance.

For the backward propagation, we can get the gradients as:

$\displaystyle\frac{\partial x_{t+2}}{\partial W_{t+1}P_{1}}=\frac{\partial
x_{t+2}}{\partial W_{t+1}}\frac{\partial W_{t+1}}{\partial
W_{t+1}P_{1}}=\frac{\partial x_{t+2}}{\partial W_{t+1}}P_{1},$ (49)
$\displaystyle\frac{\partial x_{t+2}}{\partial b_{t+1}}=\frac{\partial
x_{t+2}}{\partial b_{t+1}}$ (50) $\displaystyle\frac{\partial
x_{t+2}}{\partial P_{1}^{\top}W_{t}}=\frac{\partial x_{t+2}}{\partial
W_{t}}\frac{\partial W_{t}}{\partial
P_{1}^{\top}W_{t}}=P_{1}^{\top}\frac{\partial x_{t+2}}{\partial W_{t}},$ (51)
$\displaystyle\frac{\partial x_{t+2}}{\partial b_{t}P_{1}}=\frac{\partial
x_{t+2}}{\partial b_{t}}\frac{\partial b_{t}}{\partial
b_{t}P_{1}}=\frac{\partial x_{t+2}}{\partial b_{t}}P_{1}.$ (52)

Therefore, the gradients have the same permutation order with the weights, and
thus the results of the backward propagation are not changed. ∎

###  A-B Proof of Theorem 2

###### Proof.

For the permuted attention block, we simplify the inner product of QK to get:

$W_{i}^{Q}P_{1i}P_{1i}^{\top}W_{i}^{K\top}=W_{i}^{Q}W_{i}^{K\top}.$ (53)

Hence, we get:

$\displaystyle\operatorname{softmax}\left(\frac{X_{t}W_{i}^{Q}W_{i}^{K\top}X_{t}^{\top}}{\sqrt{d_{k}}}\right)X_{t}W_{i}^{V}P_{2}=A_{i}P_{2}.$
(54)

Combining $A_{i}$s together according to the definition of attention, and
multiplying the result with $W^{O}$, we have:

$\displaystyle\left[A_{1}P_{2},\ldots,A_{h}P_{2}\right]P_{3}W^{O}=\left[A_{1},\ldots,A_{h}\right]W^{O}=X_{t+1}.$
(55)

Therefore, we can get the result of shuffling does not alter from the original
one in the forwarding pass.

For the backward propagation, we get that the gradients as:

$\displaystyle\frac{\partial X_{t+1}}{\partial W_{i}^{Q}P_{1i}}=\frac{\partial
X_{t+1}}{\partial W_{i}^{Q}}\frac{\partial W_{i}^{Q}}{\partial
W_{i}^{Q}P_{1}}=\frac{\partial X_{t+1}}{\partial W_{i}^{Q}}P_{1i},$ (56)
$\displaystyle\frac{\partial X_{t+1}}{\partial W_{i}^{K}P_{1i}}=\frac{\partial
X_{t+1}}{\partial W_{i}^{K}}\frac{\partial W_{i}^{K}}{\partial
W_{i}^{K}P_{1i}}=\frac{\partial X_{t+1}}{\partial W_{i}^{K}}P_{1i},$ (57)
$\displaystyle\frac{\partial X_{t+1}}{\partial W_{i}^{V}P_{2}}=\frac{\partial
X_{t+1}}{\partial W_{i}^{V}}\frac{\partial W_{i}^{V}}{\partial
W_{i}^{V}P_{2}}=\frac{\partial X_{t+1}}{\partial W_{i}^{V}}P_{2},$ (58)
$\displaystyle\frac{\partial X_{t+1}}{\partial P_{3}W^{O}}=\frac{\partial
X_{t+1}}{\partial W^{O}}\frac{\partial W^{O}}{\partial
P_{3}W^{O}}=P_{3}\frac{\partial X_{t+1}}{\partial W^{O}}.$ (59)

Therefore, the gradients share the same permutation order with the weights,
demonstrating backward invariance in the weight update.

∎

###  A-C Proof of Theorem 6

######  Lemma 3.

Assuming $a_{1},a_{2},\ldots,a_{k}$ and $b_{1},b_{2},\ldots,b_{k}$ are
positive real numbers, we have

$\displaystyle\sum_{i=1}^{k}a_{i}\sum_{i=1}^{k}b_{i}\geq\sum_{i=1}^{k}a_{i}b_{i}.$
(60)

###### Proof.

Obviously,

$\displaystyle\sum_{i=1}^{k}a_{i}\sum_{i=1}^{k}b_{i}=\sum_{i=1}^{k}a_{i}b_{i}+\sum_{i\neq
j}a_{i}b_{j}>\sum_{i=1}^{k}a_{i}b_{i}.$ (61)

∎

Substituting Eq. (29) into the above inequality, we obtain

$\displaystyle\frac{\sum_{i=1}^{k}e^{<y,f^{(i)}>/\sigma^{2}}}{\sum_{i=1}^{k}e^{(<y,f^{(i)}>+<y,g^{(i)}>)/\sigma^{2}}}\geq\frac{1}{\sum_{i=1}^{k}e^{(<y,g^{(i)}>)/\sigma^{2}}}.$
(62)

Therefore, a sufficient condition for $O^{*}$ is to have

$\displaystyle\frac{1}{e^{-(\|g\|^{2}_{2}+2<f,g>)/(2\sigma^{2})}\sum_{i=1}^{k}e^{(<y,g^{(i)}>)/\sigma^{2}}}\geq
e^{\epsilon}$ (63) $\displaystyle\Leftrightarrow$ $\displaystyle
e^{-\epsilon+(\|g\|^{2}_{2}+2<f,g>)/(2\sigma^{2})}\geq\sum_{i=1}^{k}e^{(<y,g^{(i)}>)/\sigma^{2}}.$
(64)

###  A-D Proof of Lemma 2

###### Proof.

In
$h(\sigma_{Z_{1}},\sigma_{Z_{2}})=\Phi\left(\frac{\sigma_{Z_{1}}}{2}+\frac{\zeta_{1}-\epsilon}{\sigma_{Z_{1}}}\right)-e^{\epsilon}\Phi\left(\frac{\sigma_{Z_{2}}}{2}+\frac{\zeta_{2}-\epsilon}{\sigma_{Z_{2}}}\right)$,
for the definitions of $\zeta_{1},\zeta_{2},\sigma_{Z_{1}},\sigma_{Z_{2}}$, we
can easily derive

$\displaystyle\zeta_{1}\leq
0,~{}~{}\zeta_{2}\leq\zeta_{1}-\frac{\|g\|_{2}^{2}}{\sigma^{2}},$ (65)
$\displaystyle\log\left[\frac{1}{k}(e^{\frac{\|g\|_{2}^{2}}{\sigma^{2}}}-1)+1\right]<\sigma_{Z_{i}}^{2}<\frac{\|g\|^{2}_{2}}{\sigma^{2}},~{}~{}i=1,2.$
(66)

By analysis, we found $h(\cdot)$ is mostly influenced by the term
$\sum_{j=1}^{k}e^{2\mu_{ij}},\sum_{j=1}^{k}e^{\mu_{ij}},\sum_{j=1}^{k}e^{2\mu_{ij}^{\prime}},$
and $\sum_{j=1}^{k}e^{\mu_{ij}^{\prime}}$. Letting

$\displaystyle\bm{\mu}$
$\displaystyle=\left[e^{\mu_{i1}},e^{\mu_{ik}},\ldots,e^{\mu_{ik}}\right]\in\mathbb{R}^{k},$
(67) $\displaystyle A$
$\displaystyle=\text{diag}\\{e^{\frac{<g^{(i)},g^{(1)}>}{\sigma^{2}}},e^{\frac{<g^{(i)},g^{(2)}>}{\sigma^{2}}},\ldots,e^{\frac{<g^{(i)},g^{(k)}>}{\sigma^{2}}}\\}\in\mathbb{R}^{k\times
k},$ (68)

one can rewrite the terms as

$\displaystyle\sum_{j=1}^{k}e^{2\mu_{ij}}=\|\bm{\mu}\|^{2}_{2},~{}~{}\sum_{j=1}^{k}e^{\mu_{ij}}=\|\bm{\mu}\|_{1}$
(69)
$\displaystyle\sum_{j=1}^{k}e^{2\mu_{ij}^{\prime}}=\|A\bm{\mu}\|^{2}_{2},~{}~{}\sum_{j=1}^{k}e^{\mu_{ij}^{\prime}}=\|A\bm{\mu}\|_{1}.$
(70)

Substituting the above shorthand into the variables, we have

$\displaystyle\sigma_{Z_{1}}^{2}$
$\displaystyle=\log\left[\frac{\|\bm{\mu}\|^{2}_{2}}{\|\bm{\mu}\|_{1}^{2}}(e^{\frac{\|g\|^{2}}{\sigma^{2}}}-1)+1\right],$
(71) $\displaystyle\sigma_{Z_{2}}^{2}$
$\displaystyle=\log\left[\frac{\|A\bm{\mu}\|^{2}_{2}}{\|A\bm{\mu}\|_{1}^{2}}(e^{\frac{\|g\|^{2}}{\sigma^{2}}}-1)+1\right],$
(72) $\displaystyle\zeta_{1}$
$\displaystyle=-\log(\|\bm{\mu}\|_{1})+\frac{<f,g>}{\sigma^{2}},$ (73)
$\displaystyle\zeta_{2}$
$\displaystyle=-\log(\|A\bm{\mu}\|_{1})+\frac{<f,g>}{\sigma^{2}}.$ (74)

Since $\sigma_{Z_{1}}^{2}$ and $\sigma_{Z_{2}}^{2}$ only appear in $h(\cdot)$
as square root magnitudes, their influence is relatively small compared to the
changes in $\bm{\mu}$ and $A$. Therefore, we mainly consider the impact of
$\zeta_{1}$ and $\zeta_{2}$ on $h$. It is not difficult to see that the larger
the difference $\zeta_{1}-\zeta_{2}$, the greater the value of the function
$h$. Additionally, the larger $\zeta_{1}$ is, the greater the value of the
function $h$. Moreover, since $\|A\bm{\mu}\|_{1}\leq\|A\|_{1}\|\bm{\mu}\|_{1}$
holds by norm inequality, we have:

$\displaystyle\zeta_{2}\geq-\log\|A\|_{1}-\log(\|\bm{\mu}\|_{1})+\frac{<f,g>}{\sigma^{2}}=\zeta_{1}-\log\|A\|_{1}.$
(75)

By the definition of $A$, we have
$\|A\|_{1}=e^{\frac{\|g\|_{2}^{2}}{\sigma^{2}}}$, since
$e^{\frac{\|g\|_{2}^{2}}{\sigma^{2}}}$ is the maximal element in the diagonal
of $A$. The largest gap between $\zeta_{1}$ and $\zeta_{2}$ is achieved at
$\|A\bm{\mu}\|_{1}=\|A\|_{1}\|\bm{\mu}\|_{1}$ which holds under two
conditions: 1) $A=e^{\frac{\|g\|_{2}^{2}}{\sigma^{2}}}E$, where $E$ is the
identity matrix; 2) $A\bm{\mu}=e^{\frac{\|g\|_{2}^{2}}{\sigma^{2}}}\bm{\mu}$,
where $\bm{\mu}$ is an eigenvector of the matrix $A$ corresponding to the
eigenvalue $e^{\frac{\|g\|_{2}^{2}}{\sigma^{2}}}$. Below, we will discuss each
case separately and determine the conditions to achieve the maximum value of
$h$.

The first case implies that the inner products of $g^{(i)}$ and $g^{(j)}$ are
all equal to $\|g\|_{2}^{2}$, which is almost impossible for $k>1$. To exclude
the case where every $g^{(i)}$ is close to the vector $[1,1,\ldots,1]$, we
ensure that in the high-dimensional space, the probability that the angle
between $g^{(i)}$ and $[1,1,\ldots,1]$ being less than $\pi/4$ is almost zero.
Therefore, we will not consider this case here.

For the second case, it is clear that the eigenvectors of the diagonal matrix
$A$ are standard base vectors $e_{i}$ which has a 1 in the $i$-th position and
0 elsewhere. Therefore, the vector $\bm{\mu}$ is close to the direction of one
of these base vectors. According to the observation that the larger
$\zeta_{1}$ is, the larger the value of the function $h$ will be, and thus we
need to maximize $\zeta_{1}$.

Since

$\displaystyle\zeta_{1}$
$\displaystyle=-\log(e^{\frac{<f,g>}{\sigma^{2}}}+\sum_{j\neq
i}e^{\frac{<f^{(i)},g^{(j)}>}{\sigma^{2}}})+\frac{<f,g>}{\sigma^{2}}$ (76)
$\displaystyle=-\log(\sum_{j=1}^{k}e^{\frac{<f^{(i)},g^{(j)}>-<f,g>}{\sigma^{2}}}),$
(77)

the larger $<f,g>$ is, and the smaller $<f^{(i)},g^{(j)}>$ ($j\neq i$) is, the
larger $\zeta_{1}$ becomes. Moreover, as $<f^{(i)},g^{(j)}>$ is lower bounded
by

$\displaystyle e^{\mu_{ij}}=e^{\frac{<f^{(i)},g^{(j)}>}{\sigma^{2}}}\geq
e^{-\frac{\|f\|_{2}\|g\|_{2}}{\sigma^{2}}},$ (78)

the smaller the value of $k$, the larger $\zeta_{1}$ is, with the minimum
value of $k$ being $d$. Therefore, given the constraints $\|g\|_{2}\leq c$ and
$\|f\|_{2}\leq c^{\prime}$, we reformulate the problem to maximize the
following optimization problem:

$\displaystyle\text{maximize}~{}\sum_{j=1}^{k}(<f,g>-<f^{(i)},g^{(j)}>).$ (79)

Note that $<f,g>$ is maximized when $f$ and $g$ are of the same direction. The
original problem can be transformed into:

$\displaystyle\text{maximize}~{}k(<f,g>-<f^{(i)},\frac{1}{k}\sum_{j=1}^{k}g^{(j)}>)$
(80)

Since $f$ and $g$ are in the same direction, we must have
$<f^{(i)},\frac{1}{k}\sum_{j=1}^{k}g^{(j)}>\geq 0$. When
$<f^{(i)},\frac{1}{k}\sum_{j=1}^{k}g^{(j)}>=0$, $\zeta_{1}$ reaches its
maximum value. In this case, since $\frac{1}{k}\sum_{j=1}^{k}g^{(j)}$ is
parallel to $[1,1,\ldots,1]$, and $f$ and $g$ are in the same direction, then
$g\bot[1,1,\ldots,1]$. Meanwhile, since $k=d$ when $\zeta_{1}$ is maximized,
$g$ cannot be in any other form other than having one dimension different with
the rest being the same. Combining the two criteria, we could solve $g$ and
$f$ as

$\displaystyle f=\sqrt{\frac{1}{d(d-1)}}c^{\prime}[(d-1),-1,\ldots,-1]$ (81)
$\displaystyle g=\sqrt{\frac{1}{d(d-1)}}c[(d-1),-1,\ldots,-1].$ (82)

Under these conditions, we have

$\begin{split}\zeta_{1}&=-\log(1+(d-1)e^{-\frac{dcc^{\prime}}{(d-1)\sigma^{2}}}),\\\
\zeta_{2}&=-\log(1+(d-1)e^{-\frac{dc(c+c^{\prime})}{(d-1)\sigma^{2}}})-\frac{c^{2}}{\sigma^{2}},\\\
\sigma_{Z_{1}}^{2}&=\log\left[\frac{1+(d-1)e^{-\frac{2dcc^{\prime}}{(d-1)\sigma^{2}}}}{(1+(d-1)e^{-\frac{dcc^{\prime}}{(d-1)\sigma^{2}}})^{2}}(e^{\frac{\|g\|_{2}^{2}}{\sigma^{2}}}-1)+1\right],\\\
\sigma_{Z_{2}}^{2}&=\log\left[\frac{1+(d-1)e^{-\frac{2dc(c+c^{\prime})}{(d-1)\sigma^{2}}}}{(1+(d-1)e^{-\frac{dc(c+c^{\prime})}{(d-1)\sigma^{2}}})^{2}}(e^{\frac{\|g\|_{2}^{2}}{\sigma^{2}}}-1)+1\right],\end{split}$
(83)

which complete the proof. ∎

##  Appendix B Appendix of Experiments

###  B-A Python Code for Index Shuffling

⬇

def rearrange(matrix, row, column):

if row:

indices = torch.randperm(matrix.shape[0])

matrix = matrix[indices]

if column:

indices = torch.randperm(matrix.shape[1])

matrix = matrix[:, indices]

return matrix