SPEAR: Exact Gradient Inversion of Batches in Federated Learning
Authors: Dimitar Iliev Dimitrov
Maximilian Baader
Mark Niklas Mueller
Martin Vechev
Venue: NeurIPS 2024 poster (2024)
Keywords: Federated Learning
Exact Gradient Inversion
Gradient Leakage
Privacy
Attack
Primary area: privacy
TL;DR: We present the first algorithm for exact gradient inversion on batch sizes $>1$ to reconstruct inputs in the honest-but-curious federated learning setting.

Abstract: Federated learning is a framework for collaborative machine learning where clients only share gradient updates and not their private data with a server. However, it was recently shown that gradient inversion attacks can reconstruct this data from the shared gradients. In the important honest-but-curious setting, existing attacks enable exact reconstruction only for batch size of $b=1$, with larger batches permitting only approximate reconstruction. In this work, we propose SPEAR, *the first algorithm reconstructing whole batches with $b >1$ exactly*. SPEAR combines insights into the explicit low-rank structure of gradients with a sampling-based algorithm. Crucially, we leverage ReLU-induced gradient sparsity to precisely filter out large numbers of incorrect samples, making a final reconstruction step tractable. We provide an efficient GPU implementation for fully connected networks and show that it recovers high-dimensional ImageNet inputs in batches of up to $b \lesssim 25$ exactly while scaling to large networks. Finally, we show theoretically that much larger batches can be reconstructed with high probability given exponential time.

SPEAR: Exact Gradient Inversion of Batches in Federated Learning
Dimitar I. -Dimitrov', Maximilian Baader?, Mark Niklas Müller
Martin Vechev2
INSAIT, Sofia University "St. Kliment Ohridski" 2 ETTH Zurich
LogicSttr.ai
{dimitar tar. www.ve.diiittovieeee.... rov (mbaader, mark. mueller, martin. www.ev)@inf..tth........ 2
Abstract
Federated learning a framework for collaborative machine learning where clients only share gradient updates and not their private data with server. However, it was recently shown that gradient inversion attacks can reconstruct this data from the shared gradients. In the important honest-but-curious setting, existing attacks enable exact reconstruction only for batch size of b = 1, with larger batches permitting only approximate reconstruction. In this work. propose SPEAR, the first algorithm reconstructing whole batches with 1 exactly. SPEAR combines insights into the explicit low-rank structure of gradients with sampling-basee algorithm. Crucially, we leverage ReLU-induced gradient sparsity to precisely filter out large numbers of incorrect samples, making final reconstruction step tractable. We provide an efficient GPU implementation for fully connected networks and show that it recovers high-dimensional ImageNet inputs in batches of up to b 25 exactly while scaling to large networks. Finally, we show theoretically that much larger batches can be reconstructed with high probability given exponential time.
Introduction
Recon. (SPEAR ours)
Federated Learning has emerged the dom- inant paradigm for training machine learning models collaboratively without sharing sensitive data [2]. Instead, a central server sends the cur- rent model to all clients which then send back gradients computed on their private data. The server aggregates the gradients and uses them to update the model. Using this approach sensitive data never leaves the clients' machines, aligning it better with data privacy regulations such as the General Data Protection Regulation (GDPR) and California Consumer Privacy Act (CCPA).
Approximate
Recen.
Original
Image
Figure I: A sample of four images from a batch of b = 20, reconstructed using SPEAR (top) the prior state-of-ther -f--hh-artttt Geiping et al. [1] (mid), compared to the ground truth (bottom).
Gradient Inversion Attacks Recent work has shown that an honest-but-curious server can use the shared gradient updates to recover the sensitive client data [3, 4]. However, while exact reconstruction [5, 6], was assumed be infeasible for larger batches. This led to a line of research on approximate methods that sacrificed reconstruction quality order to recover batches of b > inputs [7, 9]. In this paper we challenge this fundamental assumption and, for the first time, show that exact reconstruction is possible for batch sizes b > 1.
was shown to possible for batch sizes of
This Work: Exact Reconstruction of Batches We propose the first gradient inversion attack reconstructing inputs exactly for batch sizes b > in the show the resulting reconstructions versus approximate methods [1] for batch b = 20 images.
setting. In Fig. 1, we
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Our approach leverages two key properties of gradient updates in fully connected ReLU networks: First, these gradients have a specific low-rank structure due to small batch sizes b < n, m compared Second, the (unknown) gradients with
to the input dimensionality and the hidden dimension respect to the inputs of the first ReLU layer are sparse due to the ReL.U function itself. We combine these properties with ideas from sparsely-used dictionary learning [10] to propose a sampling-basee -aaed algorithm, called SPEAR (Sparsity Exploiting Activation Recovery) and show that it succeeds with high probability for b < m. While SPEAR scales exponentially with batch size b, we provide highly parallelized GPU implementation, which empirically allows us to reconstruct batches of size up to b - 25 exactly even for large inputs (IMAGENET) and networks (widths up to 2000 neurons and depths up to 9 layers) in around one minute per batch.
Main Contributions:
The first gradient inversion attack showing theoretically that exact reconstruction of complete batches with size b> 1 in the nonest-but-curiou setting is possible.
SPEAR: a sampling-basee based algorithm leveraging low rankness and Rel.U-induced sparsity of gradients for exact gradient inversion that succeeds with high probability.
A highly parallelized GPU implementation of SPEAR, which we empirically demonstrate to be effective across wide range of settings and make publicly available on GitHub.
2 Method Overview
R
L
We first introduce our setting before giv- ing high-level overview of our attack SPEAR, whose sketch is shown in Fig. 2.
SVD
iii.
iv.
4
- +
Groedy Selection
[L
& Scaling
43
ac
Setting We consider neural network I containing a linear layer = Wx +
7m
4
b followed by ReLU activations y ReLU(zz) trained with a loss function L. Let now X E TR Rx to the linear layer Z with weights W E Rmxxn bias b E RT and output Z E Rmabb Further, let Y E Rm be the result of applying the ReLU activation to Z, i.e., Y = ReLU(2 Z) and assume b < m, n. The goal of SPEAR is to recover the inputs X (up to permutation) given the gradients aw and ac (see Fig. 2, i). ab
Sampling
Filtering
à be a batch of b inputs (b)
AC Figure 2: Overview of SPEAR. The gradient W is de- composed to and Sampling gives N proposal direc- tions, which we filter down to c candidates via a sparsity criterion with threshold T *m. A greedy selection method selects batchsize directions. Scale recovery via ab re- turns the disaggregation matrix Q and thus the inputs X.
(b).
ac
Row- Decomposition We first show that the weight gradient
ac = ac x T naturally SW
82
has low rank b I m,n (Theorem 3.1) and can therefore be decomposed as ow LE IR mxb and R gbxa using SVD (Fig. 2, ii). We then prove the existence disaggregation matrix Q = (qil (b) E (R), allowing us to express the inputs as X Q R and activation
dc = LR with
8C gradients as OZ LQ (Theorem 3.2). Next, we leverages the sparsity of az to recover Q exactly.
8C
ReLU Induced Sparsity We show that ReLU layers induce sparse activation gradients ac 32 (Sec. 3.2). We then leverage this sparsity to show that, with high probability, there exist sub- matrices LA E b-11 of L, such that their kernel is an unscaled column q: of our disaggregation matrix Q, i.e., ker (La) = span (q:), for all i E {l,..., b} (Theorem 3.3). Given these unscaled colmuns g., we recover their scale by leveraging the bias gradient ab
ac (Theorem 3.5).
Sampling and Filtering Directions To identify the submatrices LA of L which induce the direc- tions T. we propose a sampling approach (Sec. 4. We randomly sample b 1 rows of L to obtain an L and thus proposal direction प. ker (L) (Fig. 2 ii). Crucially, the product L 82. recovers a column of the sparse activation gradient 8C for correct directions of and a dense linear combination of such columns for incorrect ones. This sparsity gap allows the large number N of proposal directions obtained from submatrices LA to be filtered to 2 b unique candidates (Fig. 2 iv).
ac
32
2

---

Greedy Direction Selection We now have to select the correct b directions from our set of c candidates (Fig. 2, v). To this end, we build an initial solution Q' from the directions inducing the highest sparsity in &C 32 LQ', To assess the quality of this solution Q', we introduce the sparsity ac'
matching score which measures how well the sparsity of the activation gradients az matches the ReLU activation pattern induced by the reconstructed input X = Q' R. Finally, we greedily optimize Q' maximize the sparsity matching score, by iteratively replacing an element q of Q' with the candidate direction q yielding the greatest improvement in a until convergence. We can then validate the resulting input X Q- We formalize this as Alg. Sec. and show that it succeeds with high probability for b < m.
1 R by checking whether it induces the correct gradients.
3 Gradient Inversion via Sparsity and Low-Rankness
In this section, we will demonstrate that both low rankness and sparsity arise naturally for gradients of fully connected ReLU networks and explain theoretically how recover X. Specifically, in Sec. 3.1, we first argue that DC ac X follows direcity from the chain rule. We then show that for every decomposition SW reconstruct X = R and ac
aw az
LR, there exists an unknown disaggregation matrix Q allowing us to OZ = LQ. The remainder of the section then focuses on recovering Q. To this end, we show in Sec. 3.2 that ReLU layers induce sparsity in ac which we then leveraged in Sec. 3.3 to reconstruct the columns of Q up to scale. Finally, in Sec. 3.4, we show how the scale of Q's columns can be recovered from BC Unless otherwise noted, we defer all proofs to App. B.
&c
3.1 Explicit Low-Rank Representation of ac DW
We first show that the weight gradients 0c can be written as follows:
SW
Theorem 3.1. The network's 's gradient w.r.f. the weights W can be represented the matrix product:
OC Oc
az x"
(I)
aw
For batch sizes b < n. m. the dimensionalities of Oc mxb and X E Runb in Eq. 1 directly yield that the rank of ac JW
most b. This confirms the observations Kariyappa et al. [9] and shows
that X and ac correspond to a specific low-rank decomposition of ac JZ
JW.
To actually find this decomposition and thus recover X, we first consider arbitrary decomposition of the form aL decomposition obtained via the reduced SVD decomposition of ac aw USV by setting
ow LRR where L E mxb and R E Rgxxn are of maximal rank. We chose the US and R StV, where U E n S E Rxbb and V E & We now show that there exists an unique disaggregation matrix Q recovering X and ac from L and 8Z
oc Theorem 3.2. If the gradient 87 and the input matrix X are of full full-rank and b S n, m, then there exists an unique matrix Q E R of full-rank s.t. ac = LQ and X = =Q R. a2
Theorem 3.2 is a direct application of Lemma B. shown in App. B, a general linear algebra result stating that under most circumstances different low-rank matrix decompositions can be transformed into each other via an unique invertible matrix. Crucially, this implies that recovering the input X and the gradient Oc matrices is equivalent to obtaining the unique disaggregation matrix Q. Next, we show how the ReLU-induced sparsity patterns in ac or X can be leveraged to recover Q exactly. 8z
oz
3.2 ReL.U-Inuuced Sparsity
8C (if the ReLU activation succeeds ReI.U activation layers can induce sparsity both in the gradient a2 the considered linear layer) or in the input (if the ReL.U activation precedes the linear layer).
Gradien Sparsity If a ReLU activation succeeds the linear layer, i.e., Y = ReLU(Z), we have 0c 82 @Y entry indicating if the corresponding entry in Z is positive. At initialization, roughly half
= Oc о || where @ is the elementwise multiplication and 11 [|] is a matrix of Os and 1s with of the entries in Z are positive, making az sparse with 0.5 of the entries 0.
dC
3

---

Input Sparsity ReLUs also introduce sparsity if the linear layer in question is preceded by a ReLU activation. Here, X = (eLU(()) will again be sparse with ~ 0.5 of the entries = 0 at initialization.
Note that for all but the first and the last layer of fully connected network, we have sparsity in both, X and &c 82 Due to the symmetry of their formulas in Theorem 3.2, our method can be applied in 2c all three arising sparsity settings. In the remainder of this work, we assume w.l.o.g. that only az is sparse, corresponding to the first layer of a fully connected network. We now describe how to leverage this sparsity compute the disaggregation matrix and thus recover the input batch X.
3.3 Breaking Aggregation through Sparsity
Our exact recovery algorithm for the disaggregation matrix Q is based on the following insight:
If we can construct two submatrices A E R and A E Rb-1xb by choosing - 1 rows with the same indices from ac and L, respectively, such that A has full rank and an all-zero 7th column, az then the kernel ker (LA) of A contains a column qi of Q up scale. We formalize this follows:
Theorem 3.3. Let A E R be submatrix of Oc oz s.t. its ith column is O for some E {1.....b} .b. X, X,and be full rank and Q be as in Theorem 3.2. Then, there exists a full-rank
Further, les 02' submatrix LA E Rb-1xb of L s.t. span(q:) = kcr (c)(LA) for the 1th column qi of Q = (q1 ... qb)-
Proof. Pick an {I....,bb] 6}. By assumption, there exists a submatrix
1bb of 2C of rank 02
b b-1 whose 7th column is 0. To construct A. we take rows from L with indices corresponding to A's 0C and X have full rank, by Theorem 3.2, we know that oc JZ As oZ A LAQ. Multiplying from the right with e, yields 0 Ae; LAQe; JZ LQ. and hence
row indices in 0C
L and hence ker LA) 2 span(q:). Further, as rank (A) = b - and rank(Q) QQ) = b. we have that rank LA) =
b 1. By the rank-nullity theorem dim (ker( LA)) and hence ker LA) span(q:) (.
ac is not known priori, we can not simply search for such set of rows. Instead, we have to sample submatrices A of L at random and then filter them using the approach discussed in Sec. 4. However, will show in Sec. 5.2 that we will find suitable submatrices with high probability for b < m due to the sparsity of 0c and the large number (tm)) of possible submatrices. We will now az discuss how to recover the scale of the columns qi given their unscaled directions 9; forming Q.
As 32
3.4 Obtaining Q: Recovering the Scale of columns in Q
Given set of b correct directions Q (q1 lqb), reconstruct X, as follows. We first represent the correctly scaled columns as qi = 8; qi with the unknown scale parameters 9; R. Now, recovering the scale is equivalent computing all 8g. To this end, we leverage the gradient w.r.t. the bias dc
recover their scale, enabling to
Theorem 3.4. The gradient w.r.t the bias b can be wrilten in the form ab
0C
8C az
Thus, the coefficients s; can be calculated as: Theorem 3.5. For any left inverse L of L. we have
Q
- L
I. Cc
8b
Theorem 3.5 allows us directly obtain the true matrix Q Q diag(s)...... ..) from the unscaled matrix Q We now discuss how to recover Q via sampling and filtering candidate directions q;
4 Efficient Filtering and Validation of Candidates
In the previous section, we saw that given the correct selection submatrices L L, we can recover Q directly. However, we do not know how to pick L, priori. To solve this, we rely sampling approach: We first randomly sample submatrices LA of and corresponding direction candidates q spanning ker( Le)(LA). However, checking whether o' is a valid direction is not straightforward as we do ac and hence can not observe A directly reconstructing dc not know OZ
oz = LQ requires the full Q

---

aL is To address this, we filter the majority of wrong proposals q using deduplication and a aparsity-based criterion (Sec. 4.1), leaving us with set of candidate directions C (1..)(.....))) We then select the correct directions in C greedily based on novel sparsity matching score (Sec. 4.2).
4.1 Efficient Filtering of Directions q'
Filtering Mixtures via Sparsity It highly likely (p- (1- ---r (1---- )o) that random submatrix of L will not correspond to an A with any O column. We filter these directions by leveraging the following insight. The kernel of such submatrices is spanned by a linear combination q' = E. azq, Thus Lq will be a linear combination of sparse columns of az As this sparsity structure is random, linear combinations will have much lower sparsity with high probability. We thus discard all candidates q with sparsity of Lq below a threshold т, chosen to make the probability of falsely rejecting a correct direction Pfr m) 2m Σ [! (f"), obtained from the cumulative distribution function of the binomial distribution, small. For example for m 400 and (T+ m) < 10-5, we have 0.395. We obtain the candidate pool C = {q] (q(e..e from all samples that were not filered this way.
Filtering Duplicates As it is highly likely to have multiple full-rank submatrices A, whose 1th column is O, we expect to sample the same proposal T multiple times. We remove these duplicates to substantially reduce our search space.
4.2 Greedy Optimization
While filtering duplicates and linear combinations significantly reduces the number of candidates, we usually still have to select a subset of b < c. Thus, we have (G) possible b sized subsets, each inducing a candidate Q' and thus X'. A naive approach is to compute the gradients for all X' and compare them to the ground truth. However, this is computationally infeasible even for moderate c.
To address this, we propose greedy two-stage procedure optimizing a novel sparsity matching score X, which resolves the computational complexity issue above while also accurately selecting the correct batch elements and relying solely on oz and Z'. As both can be computed directly via Q', the procedure is local and does not need to backpropagate gradients. Next, we explain the first stage.
ac
Dictionary Learning [10] As a first stage, we leverage a component of the algorithm proposed by Spielman et al. [10] for sparsely-used dictionary learning. This approach is based on the insight that the subset of column vectors B = h yielding the sparsest full-rank gradient matrix az HL often correct. As the scaling of q does not change the sparsity of the resulting 82 we can construct the subset 1 by greedily collecting the b directions 7 with the highest corresponding sparsity that still increase the rank of B. While this method typically recovers most directions q;, often misses directions whose gradients 0z,
AL are less sparse by chance.
Sparsity Matching We alleviate this issue by introducing a second stage to the algorithm where we greedily optimize novel correctness measure based solely on the gradients of the linear layer, which we call the sparsity matching coefficient X.
Definition 4.1. Let A_ be the number of non-positive entries in Z whose corresponding entries in ac 8Z
are O. Similarly, let X be the number of positive entries in Z whose corresponding entries in OL az
not O. We call their normalized sum the sparsity matching coefficient X:
+
m b
Intuitively, this describes how well the pre-activation values Z match the sparsity pattern of the ac induced by the ReLU layer (See Sec. 3.2). While this sparsity matching coefficient À can take values between 0 and is exactly À == for the correct X, if the gradient BY w.r.t. the ReLU output is dense, which is usually the case. We note that À can be computed efficiently for arbitrary full rank matrix Q' by computing ac' = LQ' and Z' W + (b) (b)...)b) for X Q R.
gradients az
dC
(b)
8z
To optimize X, we initialize Q' with the result of the greedy algorithm in Spielman et al. [10]. and then greedily swap the pair of vectors 7. improving À the most, while keeping the rank, until convergence.
5

---

Final Algorithm and Complexity Analysis
In this section, we first present our final algorithm SPEAR (Sec. 5.1) and then analyse its expected complexity and failure probability (Sec. 5.2).
5.1 Final Algorithm
We formalize our gradient inversion attack SPEAR in Alg. 1 and out- line it below. First, compute the low-rank decomposition 0c LR
Algorithm 1 SPEAR
1:
function SPEAR( m, D, W, b, aW: 85
ac ac)
2:
L, R. f- LOWRANKDECOMPOSE (oW
aw dc of the weight gradient aw via duced SVD, allowing us to recover
3:
for i 1 to N do
4:
Sample a submatrix LA E RR of L
5:
7. ker( LA)
the batch size as the rank of SW (Line 2). We now sample (at most N) submatrices LA of L and com- pute proposal directions q; as their kernel ker( (A)) via SVD (Lines 4-
6:
Esparsity(Lon 2 T and gf E C then C (U
7:
8:
X, X' GREEDYFILT (L, R. W, b, C)
9:
if A- = 1 then return X'
10:
5). We note that our implementation
11:
end if
parallelizes both sampling and SVD
end if end for
computation (Lines 4-5) GPU.
We then filter the proposal directions 13:
X, X' f- GREEDYFILT (C)
q. based on their sparsity (Line 6), 15: return X"
adding them to our candidate pool C
they haven't 't been recovered already and are sufficiently sparse (Line 7). Once our candidate pool contains at least b directions, we begin constructing candidate input reconstructions X' using our two-stage greedy algorithm GREEDYFILTER (Line 8), discussed in Sec. 4.2. If this reconstruction leads to a solution with sparsity matching coefficient À 1, we terminate early and return the corresponding solution (Line 9). Otherwise, we continue sampling until we have reached N samples and return the best reconstruction we can obtain from the resulting candidate pool (Line 14). The pseudocode for COMPUTESIGNA (Alg. 2) and GREEDYFILTER (Alg. 3) are shown in App.
5.2 Analysis
In this section, we will analyze SPEAR w.r.t. the number of submatrices expect sample until we have recovered all b correct directions q, (Lemma 5.2), and the probability of failing to recover all b correct directions despite checking all possible submatrices of L (Lemma 5.3). For analysis of the number of submatrices we have to sample until we have recovered all b correct directions Z with high probability, we point to Lemma B.2. Further, as before, we defer all proofs also to App. B.
Expected Number of Required Samples To determine the expected number of re- quired samples until we have recovered the correct b direction vectors 7. first com- pute a lower bound on the probability q of sampling submatrix which satisfies the con- ditions of Theorem 3.3 for an arbitrary col- umn in Q and then use the coupon collector problem to compute the expected number of required samples.
Failure Probability Pfast
10a
Pra
10
3.
6
6 8
10-6
6 16
6 32
6 64
10-9. 0
80
160
240
Layer Width m
We can lower bound the probability of a sub- matrix E b randomly sampled as b- 1 rows of BC having exactly one all-zero column and being full rank as follows:
Figure 3: Visualizations of the upper bound (pth
dashed) on and approximation of (prr approx solid) the failure probability of SPEAR for different batch sizes and network widths m for pfr = 10-9.
8Z
Lemma 5.1. Let A bxb be submatrix of the gradient oz obtained by sampling b 1 OC is distributed i.i.d. as rows uniformly at random without replacement, where each element of 8z
ac
ac 82,, = Çlel with e ~ N(p 0, o² > 0) and ( ~ Bernoullip = 21) We then have the probability

---

q of A having exactly one all-zero column and being full rank lower bounded by:
b (1 (1-(3 06-1(1))0-1) > 2 (1-0030) 0.939
20-1
We can now compute the expected number of submatrices R-ocal we have draw until we have recovered all b correct direction vectors using the Coupon Collector Problem:
Lemma 5.2. Assuming i..dd submatrices A following the distribution outlined in Lemma 5. and using Alg. I, we have the expected number of submatrices Tioal required to recover all correct direction vectors as:
b-1
b
bHe 1 (blog(()) + +-b+ +
Titotal
q
q
where Hy is the tth harmonic number and y = 0.57722 the Suler-Mascheroni constant.
We validate this result experimentally in Fig. where observe excellent agreement for wide networks (m > 6) and obtain, e.g., Thoual ~ 1.8 x 10 for a batch size of b 16.
Failure Probability We now analyze the probability of SPEAR failing despite considering all possible submatrices L and obtain:
Lemma 5.3. Under the same assumptions as in Lemma 5.1, we have an upper bound on the failure probability Pial of Alg. even when sampling exhaustively as:
uh S (1
m
m 1: 2
- (1-0.9390-110
+ +1 +1-
k=b-1
where Pfr is the probability of falsely rejecting a correct direction q' via our sparsity filter (Sec. 4.1).
If we assume the full-rankness of submatrices A to i) occur with probability 1 ( 0 (1)) for 08-1 1 (1) se O (true for large 6 [11]) and ii) be independent between submatrices, we instead obtain:
approx Pial
Σ A==--
m 1 k
0.5 0.5 -.500-D(22)) +1 pp)))
2
We illustrate this bound in Fig. 3 and empirically validate this bound in Fig. and observe the true approx and plal
failure probability to lie between Piail
6 Empirical Evaluation
In this section, we empirically evaluate the effectiveness of SPEAR on MNIST [13], CIFAR-10 [14], TINYIMA- GENET [15], and IMAGENET [16] across wide range of settings. In addition to the reconstruction quality metrics PSNR and LPIPS, commonly used to evaluate gradient inver- sion attacks, we report accuracy the portion of batches for which we recovered the batch up numerical errors and the number of sampled submatrices (number of iterations).
Table 1: Comparison to prior work in the image domain.
Method
PSNR
Time/Batch
CI-Net [12] Sigmoid CI-Net [12] ReLU
38.0
hrs
15.6
1.6 hrs
Geiping et al. [1]
19.6
18.0 min
SPEAR (Ours)
124.2
2.0 min
Experimental Setup For all experiments, implementation of SPEAR. Unless stated otherwise, we run all experiments on CIFAR-10 batches of size b- 20 using 6 layer ReLU-activaeed FCNN with width rejection rate of Pfr S 10 15- We supply ground truth labels to all methods except SPEAR.
our highly parallelized PyTorch [17] GPU
200 and set achieve false
6.1 Comparison to Prior Work
In Table 1, we compare SPEAR against prior gradient inversion attacks from the image domain on the IMAGENET dataset rescaled 256 256 resolution. In particular, we compare Geiping et al. [1]', well as, the recent CI-Net [12]. As CI-Net only considers networks with the less common Sigmoid activations, we report its performance on both ReLU and Sigmoid versions of our network.
We use so-called "modem"" version of the attack from https: http:/ttww....ooooaaeeeee///eeee
7

---

We observe that while CI-Net obtains very good reconstructions with the Sigmoid net- work (PSNR of 38), SPEAR still achieves a much higher PSNR (124) as it exact. Further, for the more common ReLU acti-
Table 2: Results vs prior work in the tabular domain.
Method
Diser Ace (%)
Cont. MAE +
Time/Batch
Tableak [8] SPEAR (Ours)
97
4922.7
2.6 min
100
20.4
0.4 min
vations, the performance of CI-Net drops significantly to a PSNR < 16 compared to 19.6 for Geiping et al. [1]. Additionally. SPEAR is much faster compared to both Geiping et al. [1] and CI-Net, taking 10x and 100x less time, respectively. Finally, we want to emphasize that both prior works rely on strong prior knowledge, including label information and knowledge of the structure of images, whereas we assume no information at all about the data distribution and still achieve much better results in only fraction of the time taken.
To confirm the versatility of SPEAR, we compare it to the SoTA attack in the tabular domain, Tableak [8], in Table 2. We see that due to the exact nature of our attack, we recover both continuos and discrete features better on the ADULT dataset [18] with b = 16, while still being 6x faster.
Table 3: Reconstruction quality across 100 batches.
6.2 Main Results
Dataset
PSNR
LPPPS
Acc (%) f
Time/Batch
We evaluate SPEAR on MNIST, CIFAR-10, TINYIMAGENET and IMAGENET at two different res- olutions, reporting results in Ta- ble 3. Across datasets, SPEAR can reconstruct almost all batches perfectly, achieving PSNRs of 100 and above even batch size of b- = 20 for images as large as 720 x 720 in < 3 minutes. We provide additional results on heterogeneous data and trained networks in App. E, as well as, on the FedAvg protocol in App. F.
MNIST
99.1
NaN
99
2.6 min
CIFAR-10
106.6
1.16x
10-
99
1.7 min
TINYIMAGENET IMAGENET 224 x 224
110.7
1.62 10-4
99
1.4 min
125.4
1.05 10-
99
2.1 min
IMAGENET 720 x 720
125.6
8.08x10-11
99
2.6 min
Effect of Batch Size b We evaluate the effect of batch size on accuracy and the required number of iterations Mixal for a wide (m = 2000) and narrow (m = 200) network. While ni increases exponen- tially with b. for both networks, the narrower net- work requires about 20 times more iterations than the wider network (see Fig. 4). While trends for the wider network (m >> b) are perfectly described by our theoretical results in Sec. 5.2, some inde- pendence assumptions are violated for the narrower network, explaining the larger number of required iterations. While we can recover all batches per- fectly for the wider network, we see sharp drop in accuracy from 99% at = 20 to 63% at b = 24 (see Fig. 6) for the narrower network. This due to increasingly more batches requiring more than the N x 10 submatrices we sample at most.
1010_ Median # Iter.
real (Lemmn 5.2)
m 200
m 2000
10c-
10
10
15
20
25
Batch Size
Figure 4: Effect of batch size b on the num- ber of required submatrices. Expectation from Lemma 5.2 dashed and median (10th to 90th percentile shaded) depending network width m solid. We always evaluate 10a sub- matrices in parallel, explaining the plateau.
# Iter.
Acc [%]
Iter.
Acc [%]
Effect of Network Architecture We visualize the performance of SPEAR across different network widths and depths in Fig. 5. We observe that while accuracy independent of both (given sufficient width >> 6), the number of required iterations reduces with in- creasing width m. We provide further ablations on the effect of our two-stage filtering in App. E.3 and DPSGD noise in App. E.
10s
10
100
100
10?
50
10?
50
Mediam Water
Accuracy [%]
100 10a
10a
10
10*
2
Layer Width m
Network Depth L
Figure 5: Accuracy (green) and number of median iterations (blue) for different network widths m at L = 6 (left) and depths L at m = 200 (right).
Effect of Layer Depth Our experiments so far focused on recovering inputs to the first layer of FCNNs. However, SPEAR's capabilities extend beyond this, highlighted in Sec. 3.2. To
8

---

demonstrate this, we use SPEAR to reconstruct the inputs to all FC layers followed by ReLU activation in a 6-layer FCNN with a width of m = 400 at initialization.
The results, presented in Table 4, show that SPEAR suc-
Table 4: Effect of the attacked layer's
cessfully recovers the inputs to all layers almost perfectly. However, attacking later layers is more computationally ex- pensive. Specifically, the runtime for ( increases to 70 minutes/batch resulting in 17 batches that timed-out. This
depth (1 S 1 S 6) on reconstruction time and quality for 100 TINYIMA- GENET batches of size b = 20.
MAE 4
Acc(%) f
Time/Batch
increased computational cost due to the initialization of the network, which causes the outputs of later layers to be dominated by their bias terms with their inputs being almost
1
1.06 x 10-8 8
100
2.3 min
2
1.33 10
100
2.2 min
3
1.67 x 10-6
100
5.6 min
irrelevant. This issue is mitigated after few training steps,
4
2.80 x 10-6
99
19 min
as weights and biases adjust better reflect the relationships
5 3.04x
83
70 min
between inputs and outputs. We find that after 5000 gradient
steps the time per batch reduces to < min at an accuracy of > 95% for layer = 5.
6.3 Scaling SPEAR via Optimization-basee Attacks
As we prove theoretically in Sec. 5.2 and verify practically in App. E.5, in the common regime where the batch size 6 is much smaller than dimensions of the attacked linear layer w.h.p. the input information is losslessly represented in the client gradient. However, in practice for b >> 25 the exponential sampling complexity of SPEAR becomes a bottleneck that prevents the recovery of the input (see Fig. 4).
Table 5: Comparison between the reconstruction
quality of Geiping et al. [1] and version of SPEAR
that uses Geiping et al. [1] to speed up its search pro-
cedure evaluated on 10 TINYIMAGENET batches.
Method
b
m
Acc(%) f
PSNR
Geiping al. [1]
50
400
26.5
SPEAR + Geiping et al. []]
50
400
100
124.5
Geiping et al. [1]
100
2000
32.8
SPEAR + Geiping et al. [1]
100
2000
60
81.5
In this section, we propose a method for alleviating the exponential sampling complexity by combining SPEAR with an approximate reconstruction method to get prior on which submatrices LA satisfy the conditions of Theorem 3.3, i.c., have corresponding matrices A containing a O-column. To this end, we first obtain an estimate of the client pre-activation values Z based on the approximate input reconstructions from Geiping et al. [1]. As large negative antavativation values in Z are much more likely to correspond to negative pre-activation values in the true Z, and, thus, to Os in gradients ac
az. we record the locations of the 36 largest negative values for each column of Z. Importantly, by choosing the locations this way, ensure that each group of 3b locations correspond to locations of ac Restricting the sampling of the row indices of LA and A only within
likely Os in same column of 3Z each group of locations, ensures that LA is very likely to satisfying the conditions of Theorem 3.3.
We confirm the effectiveness of this approach in a preliminary study, shown in Table 5, that demon- strates the combined approach allows substantial increase in the batch size SPEAR can scale to (up to 100), thus effectively eliminating its exponential complexity. The results show that the combined approach drastically improves the reconstruction quality of Geiping et al. [1] as well, as unlike Geiping et al. [1], it achieves exact reconstruction. Importantly, we observe that even for the 4 batches SPEAR failed to recover in Table 5, SPEAR still reconstructs > 97 of the 100 directions qi correctly, suggesting that future work can further improve upon our results.
6.4 Feature Inversion in Convolutional Neural Networks
Following the Cocktail Party Attack (CPA) [9].
Table 6: Comparison between the reconstructions
we experiment with using SPEAR to recover
on VGG for Geiping et al. [1], CPA [9], and
the input features to the first linear layer of a pre-
SPEAR for 10 IMAGENET batches (b 16).
trained VGG16 convolutional network with size 25088 x 4096 for IMAGENET batches of b = 16 and use them in a feature inversion (FI) attack to approximately recover the client images. We show the results of our experiments, based on the CPA's code and parameters, in Table 6. We see the inverted features drastically improve quality of the final reconstructions, and that SPEAR achieves almost perfect feature cosine similarity, resulting in better overall reconstruction versus CPA.
Method
LPIPS
Feature Sim
Geiping al. [1] CPA[9] + Fl Geiping et al. [1]
0.562
0.388
0.939
SPEAR + Fl Geiping et al. [1]
0.362
0.984

---

7 Related Work
In this section, we discuss how we relate to prior work.
Gradient Inversion Attacks Since gradient inversion attacks have been introduced [3], two settings have emerged: In the malicious setting, the server does not adhere to the training protocol and can adversarially engineer network weights that maximize leaked information [19, 20, 21, 22]. In the strictly harder honest-bul-curione setting, the server follows the training protocol but still aims to reconstruct client data. We target the honest-but-curious setting, where prior work has either recovered the input exactly for batch sizes of b 1 [5, 6], or approximately for > 1 [1. 23, 7, 8, 9]. In this setting, we are the first to reconstruct inputs exactly for batch sizes b > 1.
Most closely related our work is Kariyappa et al. [9] which leverage the low-rank structure of the gradients to frame gradient inversion as a blind source separation problem, improving their approx- imate reconstructions, In contrast, we derive an explicit low-rank representation and additionally leverage gradient sparsity reconstruct inputs exactly.
Unlike long line of prior work, rely neither on any priors the data distribution [8, 24, 25, 26] nor on a reconstructed classification lahel [1, 27, 7, 23, 8]. This allows our approach to be employed in much wider range of settings where neither is available.
Defenses Against Gradient Inversion Defenses based on Differential Privacy [28] add noise to the computed gradients the client side, providing provable privacy guarantees the cost of significantly reduced utility. Another line of work increases the empirical difficulty of inversion by increasing the effective batch size, by securely aggregating gradients from multiple clients [29] or doing multiple gradient update steps locally before sharing an aggregated weight update [4]. Finally, different heuristic defenses such gradient pruning [3] have been proposed, although their effectiveness has been questioned [30].
Sparsely-used Dictionary learning Recovering the disaggregation matrix Q is related to the well-studied problem of sparsely-used dictionary learning. However, there the aim is to find the sparsest coefficient matrix (corresponding to our #z2 and dense dictionary (Q-1) approximately encoding signal (L). In contrast, do not search for the sparsest solution yielding an approximate reconstruction but solution that exactly induces consistent X and IC
a2. which happens to be sparse.
Sparsely-used dictionary learning is known to be NP-hard [31] and typically solved approximately [32, 10, 33]. However, under sufficient sparsity, it can be solved exactly in polynomial time [10]. ac While our 8z are not sparse enough, we still draw inspiration from Spielman et al. [10] in Sec. 4.
8 Limitations
We focus on recovering the inputs to fully connected layers with ReLU activations such as they occur at the beginning of fully connected networks as aggregation layers of many other architectures. Extending our approach to other layers an interesting direction for future work.
Further, our approach scales exponentially with batch size b. While SPEAR's massive parallelizability and its ability be combined with optimization-bart based attacks, as shown in Sec. 6.3, can partially mitigate the computational complexity. future research is still required to make reconstruction of batches of size b 100 practical.
Conclusion
We propose SPEAR, the first algorithm permitting batches of 6 > 1 elements to be recovered exactly in the
setting. We demonstrate theoretically and empirically that SPEAR succeeds with high probability and that our highly parallelized GPU implementation is effective across wide range of settings, including batches of up to 25 elements and large networks and inputs.
We thereby demonstrate that contrary to prior belief, an exact reconstruction of batches is possible in the honest-but-curion setting, suggesting that federated learning on ReLU networks might be inherently more susceptible than previously thought. To still protect client privacy, large effective batch sizes, obtained, e-g. via secure aggregation across a large number of clients, might prove instrumental by making reconstruction computationally intractable.
10

---

Acknowledgments
This research was partially funded by the Ministry of Education and Science of Bulgaria (support for INSAIT, part of the Bulgarian National Roadmap for Research Infrastructure).
This work has been done as part of the EU grant ELSA (European Lighthouse on Secure and Safe AI, grant agreement
101070617). Views and opinions expressed are however those of the authors only and do not necessarily reflect those of the European Union or European Commission. Neither the European Union nor the European Commission can be held responsible for them.
The work has received funding from the Swiss State Secretariat for Education, Research and Innova- tion (SERI).
References
[1] Jonas Geiping, Hartmut Bauermeister, Hannah Dröge, and Michael Moeller. Inverting gradients- how casy is it to break privacy federated learning? NeurIPS, 2020.
[2] Brendan McMahan, Fider Moore, Daniel Ramage, Seth Hampson, and Blaise Agtier y Arcas. Communication--ffiee learning deep networks from decentralized data. In AISTATS, 2017.
[3] Ligeng Zhu, Zhijian Liu, and Song Han. Deep leakage from gradients. In NeurIPS, 2019.
[4] Dimitar Iliev Dimitrov, Mislav Balunović, Nikola Konstantinov, and Martin Vechev. Data leakage in federated averaging. Transactions Machine Learning Research, 2022. ISSN 2835-8856. URL
[5] Le Trieu Phong, Yoshinori Aono, Takuya Hayashi, Lihua Wang, and Shiho Moriai. Privacy- preserving deep learning via additively homomorphic encryption. JEEE Trans. Inf. Forensics Secur,, (5), 2018.
[6] Junyi Zhu and Matthew B. Blaschko. R-GAP: recursive gradient attack privacy. In ICLR, 2021.
[7] Jiahui Geng, Yongli Mou, Feifci Li, Qing Li, Oya Beyan, Stefan Decker, and Chunming Rong. Towards general deep leakage in federated learning. arXiv, 2021.
[8] Mark Vero, Mislav Balunović, Dimitar I. Dimitrov, and Martin Vechev. Data leakage in tabular federated learning. ICMI,, 2022.
[9] Sanjay Kariyappa, Chuan Guo, Kiwan Maeng, Wenjie Xiong, G Edward Suh, Moinuddin K Qureshi, and Hsien-Hsin S Lee. Cocktail party attack: Breaking aggregation-base privacy in federated learning using independent component analysis. In International Conference on Machine Learning, pages 15884-15899, PMLR, 2023.
[10] Daniel A Spielman, Huan Wang, and John Wright. Exact recovery of sparsely-used dictionaries. In Conference on Learning Theory, pages 37-1. JMLR Workshop and Conference Proceedings, 2012.
[11] Konstantin Tikhomirov. Singularity of random bernoulli matrices. Annals of Mathematics, 191 (2):593-634, 2020.
[12] Chi Zhang, Zhang Xiaoman, Ekanut Sotthiwat, Yanyu Xu, Ping Liu, Liangli Zhen, and Yong Liu. Generative gradient inversion via over-vvvaneee wer-parameterized networks in federated learning. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 5126-5133 2023.
[13] Yann LeCun, Corinna Cortes, and CJ Burges. Mnist handwritten digit database. ATT Labs [Online]. Available: http://ann.lecun..co/eeed/
2, 2010.
[14] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[15] Ya Le and Xuan S. Yang. Tiny imagenet visual recognition challenge. CS 231N, 7(7), 2015.

---

[16] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large- scale hierarchical image database. 2009 IEEE conference on computer vision and pattern recognition, pages 245. leee, 2009.
[17] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Edward Z.. Yang, Zaccarry DeVito, Martin Raison, Alykhan Tejani, Sasank Chil- amkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An impera- tive style, begf--eeformance deep learning library. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' A'Alché-Buc, Emily B. Fox, and Roman Garnett, editors, Ad- vances in Neural Information Processing Systems 32: Annual Conference on Neural In- formation Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 8035,8035, 2019. URL http::://prooeednggs.ooo wttpurips.cccaapppeeeeeeeeeeeppe pc/papp//2119 http://bcca22ffee79992222fff2110 htwp2/77744-ssaratttttot.. Abstract.html
[18] Barry Becker and Ronny Kohavi. Adult. UCI Machine Learning Repository, 1996. DOI: https//tbb.or//1022444/////
[19] Franziska Boenisch, Adam Dziedzic, Roei Schuster, Ali Shahin Shamsabadi, Ilia Shumailov, and Nicolas Papernot. When the curious abandon honesty: Federated learning is not private. arXiv, 2021.
[20] Liam H. Fowl, Jonas Geiping, Wojeiech Czaja, Micah Goldblum, and Tom Goldstein. Robbing the fed: Directly obtaining private data in federated learning with modified models. In ICLR, 2022.
[21] Liam Fowl, Jonas Geiping, Steven Reich, Yuxin Wen, Wojtek Czaja, Micah Goldblum, and Tom Goldstein. Decepticons: Corrupted transformers breach privacy in federated learning for language models. JCLR, 2022.
[22] Yuxin Wen, Jonas Geiping, Liam Fowl, Micah Goldblum, and Tom Goldstein. Fishing for user data in large-batch federated learning via gradient magnification. In ICML, 2022.
[23] Hongxu Yin, Arun Mallya, Arash Vahdat, Jose M. Alvarez, Jan Kautz, and Pavlo Molchanov. See through gradients: Image batch recovery via gradinversion. CVPR, 2021.
[24] Mislav Balunović, Dimitar I. Dimitrov, Nikola Jovanović, and Martin T. Vechev. LAMP: extracting text from gradients with language model priors. In NeurIPS, 2022.
[25] Samyak Gupta, Yangsibo Huang, Zexuan Zhong, Tianyu Gao, Kai Li, and Danqi Chen. Recov- cring private text in federated learning of language models. Advances in Neural Information Processing Systems, 25:8130-8144 2022.
[26] Zhuohang Li, Jiaxin Zhang, Luyang Liu, and Jian Liu. Auditing privacy defenses in federated learning via generative gradient leakage. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pages 10132-10142, 2022.
[27] Bo Zhao, Konda Reddy Mopuri, and Hakan Bilen. idlg: Improved deep leakage from gradients. arXiv, 2020.
[28] Martín Abadi, Andy Chu, Ian J. Goodfellow, H. Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In CCS, 2016.
[29] Kallista A. Bonawitz, Vladimir Ivanov, Ben Kreuter, Antonio Marcedone, H. Brendan McMa- han, Sarvar Patel, Daniel Ramage, Aaron Segal, and Karn Seth. Practical secure aggregation for federated learning on user-held data. NIPS, 2016.
[30] Mislav Balunović, Dimitar Iliev Dimitrov, Robin Staab, and Martin T. Vechev. Bayesian framework for gradient leakage. In ICLR, 2022.
[31] Andreas M Tillmann. On the computational intractability of exact and approximate dictionary learning, IEEE Signal Processing Letters, 22(1):45 2014.
12

---

[32] Michal Aharon, Michael Elad, and Alfred Bruckstein. K-svd: An algorithm for designing overcomplete dictionaries for sparse representation. IEEE Transactions on signal processing. 54(11):43114433 2006.
[33] Ju Sun, Qing Qu, and John Wright. Complete dictionary recovery over the sphere i: Overview and the geometric picture. IEEE Transactions on Information Theory, 63(2):853 88448844,,,- 2016.
[34] Terence Tao and Van Vu. On random pm matrices: singularity and determinant. In Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, pages 431-440) 2005.
[35] Ravi Parameswaran. Statisties for experimenters: introduction design. data analysis, and model building. JMR, Journal of Marketing Research (pre-1986), 16(000002):291, 1979.
[36] Zac Chen. H2 Maths Handbook. Educational Publishing House, 2011.
13

---

A Broader Impact
In this work, we demonstrate that contrary to prior belief, an exact reconstruction of batches is possible in the honest-but-curiour setting for federated learning. As our work demonstrates the susceptibility of federated learning systems using ReLU networks, this work inevitably advances the capabilities of an adversary. Nonetheless, we believe this to be an important step in accurately assessing the risks and utilities of federated learning systems.
To still protect client privacy, large effective batch sizes, obtained, e.g., via secure aggregation across large number of clients, might prove instrumental by making reconstruction computationally intractable. As gradient information and network states can be stored practically indefinitely, our work highlights the importance of proactively protecting client privacy in federated learning not only against current but future attacks, This underlines the importance of related work on provable privacy guarantees obtained via differential privacy.
B Deferred Proofs
Theorem 3.1. The network's gradient w.r.t. the weights W can be represented as the matrix product:
UL
Oc
az X
(1)
aw
Proof. We will use Einstein notation for this proof:
dc
OL az,'
aw,
oz, k OW, 3
JC o(W, X
az
OW
AL ow, X
az OW; 3
OC ow, X
oz, ow.
OL 5 '5," th m
0ZK OC
02,' X,
Ac
(
oz,
We note that 6% is the Kronecker delta, that is 5, 1 if k = i and otherwise. Further, = 1 for all 1. Hence arrive at Eq. 1.
Lemma B.1. Let b, n. N such that b < m. Further, let A, L E mm and B, R E R be matrices of maximal rank, satisfying AB LRR. Then there exists a unique disaggregation matrix Q E GLa (R) s.t. A = LQ, and B Q R.
Proof. As b S and the matrices A E Rmxb and B E Rxxn have full rank, we know that there exists
a left inverse A E bbbxm for A: A A A In and
a right inverse B- R E R for B: BB R Ib.
Thus, it follows from
A LLRB R A LABB Ib.
that (A (A- RB-R We now set Q R.-R
14

---

This Q satisfies the required properties:
= = R:
R' AB B,
A = LQ:
A, Uniqueness: Assume we have Q1 and Q2 that satisfy LQ1 LQ₂ A. As L is of rank and S m, there exists a left inverse L- L. for L: L LL = Lb. Applying this left inverse to LQ LQ2, directly yields Q1 Q2. and hence get uniqueness.
LQ= LRB ABB
Theorem 3.4. The gradient w.r.t the bias b can be written the form ac 8h
az
Proof. We use again Einstein notation.
ac
0C Oz
0b.
a Ob,
0L O(W, X ! + 6
oZ,'
Öb;
OC 0b,6"
OZ Öb.
0L
OZ 5% '8'
ac 8¹.
Oz,"
This concludes the proof.
Theorem 3.5. For any left inverse L- L of L, we have
Q 1Q-1I L dc
Proof. The proof is straight forward. Using Theorem 3.4 and Theorem 3.2, we know that
Q L 1.
DC
Q
111-
0b
0z
Q
Q
Q Q diag 81 s6)
Lemma 5.1. Let A E 1Rb-1xb be submatrix of the gradient
8C obtained by sampling b 1 0C
O7 rows uniformly random without replacement, where each element of OZ is distributed i.i.d. as az of having exactly one all-zero column and being full rank lower bounded by:
ac <[cc with N(p o² > 0) and &~ Bernoullipp 2). We then have the probability
b
b
2 16-1
(1
1--6) 6 ob- (1))
0.939
2
15

---

b if the network has full Proof. We have the probability of one of the b columns being all zero as 2 rank, all other columns will not be all-zero.
Further, we have the probability of the submatrix 1 A.5 being full rank conditioned on column i being all-zero as the probability of the matrix described by remaining b columns being non- singular. This probability is 1 - (3 + 0b-1 [11] where limes+oe Ob- (1) = O, which can be bounde with 1 - 0.939 [34]. We thus obtain their joint probability as their product. C
Lemma 5.2. Assuming i..dd submatrices A following the distribution outlined in Lemma 5.1 and using Alg. I, we have the expected number of submatrices notll required to recover all b correct direction vectors as:
b-1 b
bibe 1 (blog(() + +7b 2),
Tignal
9
q
where Hg is the tth harmonic number and r x 0.57722 the Euler-Mascheroni constant.
Proof. As sample submatrices A uniformly random with replacement, assuming them to be i..d. is well justified for the regime of m >> b. The the number n of submatrices drawn between correct direction vectors qi thus follows Geometric distribution P/n k] = g(1 a)a-1 with success probability with expectation n² = [[[n] = As we draw correct direction vectors q
uniformly at random from the b columns Q, we have the probability of drawing a new direction vector qi as b- for & already drawn direction vectors. Again via the expectation of the Geometric distribution we obtain the expected number e* of correct direction vectors we have to draw until we have recovered all b distinct ones as the solution of the Coupon Collector Problem ex == Ek=o b- bH, R blog(b) + +
+ 2. The proof concludes with the linearity of expectation.
Maximum Number of Samples Required with High Probability We now compute the number of samples nooal required to recover all b correct directions with high probability - pp.
Lemma B.2. In the same setting as Lemma 5.2, we have an upper bound namaal on the number of submatrices we need to sample until we have recovered all b correct direction vectors by solving the following quadratic inequality for nootal
(blo((2b/p)) 1 Paaat
P
55
2
V 9)
where & is the cumulative distribution function of the standard normal distribution and p¹ p - 1 + 11--1 p.
Proof. At high level, bound the number of valid directions o we need discover until we recover all distinct ones and then the number of submatrices nyou we need to sample to obtain these dº directions, each with probability
2. before applying the union bound.
However, we first note that with probability direction due to a lack of induced sparsity and thus fail irrespective of the number of samples we draw. We thus correct our failure probability budget from p to p² = p - 1+ p,,)), using the union bound.
(1 - P)r)" we will (repeatedly) reject correct
We now show how to compute the upper bound on the number of correct directions c we need find until we have found all & distinct directions. To this end, we bound the probability of not sampling the thh direction q, after finding e candidates as p-i (1 f) -.. We then bound the probability of missing any of the directions using the union bound as p-anl S Ei= P-; be x We thus obtain the minimum number c of correct directions to find all distinct ones with probability at least n.
T as d² 2 b bogg22//p")
We can now compute the number 7 of samples required to find submatrices satisfying the condition of Theorem 3.3 for some with probability 1-f. -.. To this end, we approximate the Binomial distribution B(n, q) with the normal distribution A N(ng, ng(11 (1- - 4)) [35], which generally precise
if min(ng, níg 1)) > 9 [36], which holds for b > 5. We thus obtain the number of samples ni
16

---

required to find c valid directions with high probability 1 1 2/2 by solving 2/2 11( c c for Pooal which boils down to a quadratic equation.
V
By the union bound, we have that the total failure probability of not finding all b correct directions is at most p.
For a batch size of 10 and p = 10-$, we, e.g., obtain n = x 10*.
Lemma 5.3. Under the same assumptions as in Lemmna 5.1. we have an upper bound on the failure probability Pfud of Alg. even when sampling exhaustively as:
m k.
(1 2
0.939 (()))))) + -1- -1-(1-p)));
Pfall 1
b=
where Pfr is the probability of falsely rejecting correct direction q' via sparsity filter (Sec. 4.1)
Proof. We will first compute the probability of 8C not containing a submatrix A satisfying the az conditions of Theorem 3.3 for all i b) and then the probability of us failing discover despite exhaustive sampling.
We observe that the number of rows in 8z with zero 7th entry binomially distributed with success
probability 3. For each 2 b- 1, we can construct (a-1) submatrices A with an all-zero 1th column.
The probability of any such submatrix having full rank is 1 ( ob- (1)) [11, 34J.
0.939
We thus have the probability of dc containing at least submatrix A with full rank and all-zero az
7th column as -
0.93g(0-1)(
Using the union bound, thus obtain upper bound the probability of 8c submatrix with full rank and an all-zero thh column for all E (1.....b),
oz not containing any
To compute the probability of us failing to discover an existing submatrix despite exhaustive sampling, ac we first note that we have the probability Pfr an arbitrary column in 3Z being less sparse than our threshold т. Thus, with probability to it inducing an unusually dense column in ac
(1 - pfr) we will discard at least one correct direction due
az
We now obtain the overall failure probability via the union bound.
C Deferred Algorithms
Here, present the Algorithms COMPUTELAMBDR and GREEDY referenced in Sec. 5.1.
Algorithm 2 COMPUTELAMBDA
1: function COMPUTELAMBDACA R. W, b, DC
B) %6)
85:
2: Q+ FIXSCALE (B, L, 0c
3:
82
ac
+ L.Q
4:
X
+ Q-1
5:
Z W. X + (b) .). b))
6:
X Eis 1[Z,, < 0]
1[ ac
72.
7:
d Ens 1[2,,
1 ac
8Z
#
1+ x=+2
8:
m return À
9:
17

---

Algorithm 3 GREEDYFILT
function GREEDYFILTER W, .)
2:
3+0 0
3:
while rank of is B do
4:
Select the sparsest vector o. from C B
5:
B B {q.}
6:
if B is not of full rank then
7:
B {q.)
8:
end if end while
9:
10:
11:
À + COMPUTELAMBDA (L, R, W b, 06 :))
12:
while not changed do
13:
changed <- False
14:
for (g:- 9, in B (C ()) do
15:
B' B U
16:
X + COMPUTELAMBDA (L, R, W, b, OC ,B) 8b
17:
X' > then
18:
B - B'
19:
A+ X
20:
changed <- True
21:
end end for
22:
23:
end while
24:
Q < FIXSCALE (B, L, 36)
X 1-Q-
26:
return A, X
Table 7: Reconstruction quality across 100 batches.
Dataset
PSNR t
LPIPS
Acc (%) f
Time/Batch
MNIST
99.1 + 13.2
NaN
99
2.6 min
CIFAR-10
106.6 + 15.1
1.16x 1 10-1
99
1.7 min
TINYIMAGENET
110.7 + 12.8
1.62 (62xx00443.22
1.4 min
IMAGENET 224 224
125.4 + 11.2
1.05x 1
99
2.1 min
IMAGENET 720 x 720
125.6 - 8.1
8.1
8.08 13.000000
99
2.6 min
D Dataset Licenses
In this work, we use the commonly used MNIST [13), CIFAR- [14]. TINYIMAGENET [15] and IMAGENET [16] image datasets. No information regarding licensing has been provided on their respective websites. Further, we use Adult tabular dataset under the Creative Commons Attribution 4.0 International (CC BY 4.0) license.
E Deferred Experiments
E.1
Main Results with Error Bars
In this section, we provide the results from our main experiment in Table 3, alongside 95% confidence intervals.
E.2 Experiments on Leter--netro Data
In this section, we provide experiments on heterogeneous client data. In particular, we look at the extreme case where each client has data only from a single class. As label repetition makes optimization-based attacks harder [1, 23, 7], the results presented in Table for the TinylmageNet
18

---

Accuracy [%]]
100
75
1-Stage Greedy
2-Stage Greedy (ours)
50
2
13
24
Batch Size b
Figure 6: Effect of the second stage of our reconstruction algorithm discussed in Sec. 4.2, depending on the batch size b.
dataset show another advantage of our algorithm, namely, SPEAR works regardless of the label distribution, providing better reconstruction results compared Table 3 for single-label batches.
Table 8: Mean reconstruction quality metrics across 100 batches for batches only containing samples from only one class in the same setting as Table 3.
Dataset
PSNR 1
SSIM f
MSE
LPIPS 4
Acc (%)
TINYIMGNET
127.7
0.999717
4.80 10
10.36x10
E.3 Effectivness of our 2-Stage Greedy Algorithm
In this section, compare reconstruction success rate (accuracy) with and without the second stage of our greedy algorithm discussed in Sec. 4.2 in Fig. 6. We observe that the second stage filtering becomes increasingly important for larger batch size b.
E.4
Effeet of Training on SPEAR
107_ Ier
Sparsity Ace
[%)
# Iter.
Sparsity Ace [%]
100
107
100
Median Pattrr
10a
50
10
50
Accuracy [%]
Spersity [%]
10a
10
102
10
10
10a
103
10
Training Steps
Thaining Steps
(a) Training Set
(b) Test Sct
Figure 7: Effect of training (on MNIST) on the effectiveness of SPEAR at batch size 10 evaluated on the MNIST training (a) and test (b) sets.
In this section, we demonstrate how training effects SPEAR's performance. To this end, we train network on MNIST and evaluate SPEAR periodically during training both on the train and test datasets, visualizing results Fig. We observe that SPEAR performance is very similar between the two datasets we evaluate with the number of required steps by the algorithm being even lower those those on untrained networks. However, if the minimum column sparsity of 3Z drops significantly, as is the case for the checkpoints around 1000 training steps in the illustrated run. SPEAR's performance drops slightly.
Further, see that SPEAR performs very well trained networks,
19

---

E.5 Failure Probabilities
In this section, we validate experimentally our theoretical results on SPEAR's failure rate for several batch sizes b (Lemma 5.3). As this requires exhaustive sampling of all (,mh) submatrices of L we only consider small batch sizes b I 10 and networks m S 40. We show the results in Fig. 8 where we observe that the empirical failure probability (blue) with 95% Clopper-Pearson confidence bounds generally agrees with the analytical approximation (solid line) and always lies below the analytical upper bound (dashed line). We conclude that in most settings, the number of required samples rather than complete failure is the limiting factor for SPEAR'S 's performance.
Failure Probability
Failure Probability
1.0
1.0
Prait
aygrae P fail
0.5
0.5
P fail
0.0 3
0.0 5
20
40
20 Layer Width m
40
Layer Width m
(a) b = 2
(b) b bb=0 4
Failure Probability
Failure Probability
1.0
1.0
Pfal
Pfat
appras oz
approx P fail
P fail
0.5
0.5
Pfai
Pfail
0.0
0.0
7
20
40
10
20
40
Layer Width m
Layer Width m
b=) 6
(d) b
Figure 8: Empirical failure probability (blue) with 95% Clopper-Pearson confidence bounds (shaded blue) compared to the analytical upper bound (dashed line) and approximation (solid line) of the failure probability for different batch sizes b.
E.6 Results under DPSGD
In this section, we show experimental results on reconstructing images from gradients defended using DP-SGD [28]. In Table 9, we report results on the TINYIMAGENET dataset, b 20, with noise levels 5 1.0x 10-4 and gradient clipping that constrains the l norm of the composite gradient vector, combining the gradients of all layers,
maximum value of C E [1, 2]. We chose the maximum value a to be close to median gradient magnitude of the first linear layer which in our experiments was also 2 1.0 x 10-4 We chose the range for such that for the upper bound 2, most individual input gradients are not clipped, while for the lower bound 1 almost all are.
Adapting SPEAR to Noisy Gradients In the experiments presented in Table 9, we make several adjustments to SPEAR to better handle the noise added by DPSGD. First, we apply looser thresholds in our sparsity filtering at Line 6 in Alg. to account for the noise added to the sparse entries of 8C To account for the imperfect reconstructions in this setting, we also perform our early stopping RZ (Line 9 in Alg. 1) when the sparsity matching coefficient y reaches lower value than 1. Further, we sample matrices LA of larger size (b ++1 1 x b) to increase the numerical stability of our solutions under noise. While sampling larger LA more computationally expensive, as + 1 instead of entries in A are required to be correctly sampled as O, the resulting directions q: are more numerically stable as they are obtained as a solution of an overdetermined system of linear equations. Note that A is assumed to be of rank b- - 1, Theorem 3.3 remains valid for these larger matrices LA. Finally, due to our looser sparsity filtering described above we encounter more incorrect directions q,- We tackle this issuc by only keeping q; that correspond to matrices LA of rank exactly b 1. Under our
20

---

assumption in Theorem 3.3, those are exactly the vectors q, that correspond to A of the correct rank b 1. Note that we apply these changes only for a >
Invariance to Gradient Clipping In Table 9, we observe that the quality of our reconstructions is affected by the clipping constant C. This not a coincidence, but rather a mathematical fact. To see this, note that the observed gradients w.r.t. W under clipping are given by:
OC
b
OC
Oc Oz.
aw
= Σ 1=1
OW:
=
X
where & E are the unknown to the attacker factors applied by the clipping procedure to each individual input gradient ac One adapt the proof to Theorem 3.1, show that aw
dc 8c X
aW. #c to be the clipped gradient w.r.t Z. consisting of the columns aZ. = c az. a2.
where we define
dc
ac
We also observe that one can adapt Theorem 3,4 to work directly on the clipped gradients as well, ec
resulting in the formula
for the clipped gradient w.r.t. b. The formula follows from the ec az
observation that in our setting the same clipping factor & is applied to the gradients of each layer, &c and BC including 26; aw. By applying the rest of the theoretical results of the paper without change but
on clipped gradients 32
#c instead of the original unclipped gradients az we conclude that SPEAR directly applicable on the clipped client gradient and that applying it on those still recover the true input matrix X without the need of knowing the clipping constants C,
ac
Robustness to Noise From Table 9, we observe that SPEAR is very robust to noise. We emphasize particular that even when noise similar size to the size of the gradients in expectation is applied, we still obtain reconstruction with PSNR > 28. This is similar to the PSNR of 29.3 that Geiping et al. [1] achieves *without any noise* which commonly considered unacceptable information leakage. These experiments suggest that to efficiently defend against SPEAR using noise, one needs to apply such high magnitudes that training will likely significantly impeded.
F SPEAR under FedAvg Updates
In this section, first demonstrate theoretically that SPEAR can be generalized to attack FedAvg [4] client updates, and then present empirical results confirming that SPEAR is indeed very effective under FedAvg protocols with different number of epochs ε, local client learning rates 7), and, even works, when mini-batches of size bmini are used.
Generalizing SPEAR to FedAvg Updates Assuming that a client uses all of its data points, X, in each local gradient step of the FedAvg protocol, i.e. Imiii = h, the client computes and subsequently shares with the server the following updated linear layer weights:
OL OWe
Oc oz
O Σ
ee -wo
W
X
W
X
az
where 8 is the global model sent by the server, We represent the local client weights after e client are the weight and output gradients at epoch
Bw Sc epochs, and ac and az
We empirically observe that sparsity patterns of the different local gradients a2 usually similar. This is expected as these patterns correspond to the ReI.U activation patterns for the layer outputs Ze (see Sec. 3.2) at different local steps which are computed on the same data X and with similar weights W As the sparsity patterns for the individual gradients are similar, their sum Σe= az= also shares this sparsity pattern and is, thus, also sparse. As the server knows W and can subtract it from the client's shared weights W and apply Theorem 3.3, as before, on the sparse matrix Σ ac matching coefficient a will typically not reach 1 for the final reconstruction in this setting, as there is some mismatch between the sparsity patterns the different output gradients ac az we have found
Oc
a2
8Z to obtain the corresponding matrix Q and client data X. We note that while sparsity
that SPEAR remains practically effective regardless.
21

---

Table 9: Reconstruction quality across 100 batches of size = 20 computed on TINYIMAGENET for
gradients computed with DPSGD [28] with different noise levels and gradient clipping levels C.
Method
C
a
PSNR f
Ace (5)
Geiping et. al
0.00
0
29.3
100
SPEAR (Ours)
1.00
0
118.2
100
SPEAR (Ours)
1.25
0
118.1
100
SPEAR (Ours)
1.50
0
118.5
100
SPEAR (Ours)
1.75
0
118.7
100
SPEAR (Ours)
2.00
0
118.0
100
SPEAR (Ours)
1.00
5.0 10
38.6
99
SPEAR (Ours)
1.25
5.0x
40.4
98
SPEAR (Ours)
1.50
100
41.9
SPEAR (Qurs)
1.75
5.0x
42.2
97
SPEAR (Ours)
2.00
5.0%
42.0
96
SPEAR (Ours)
1.00
1.0
38.2
99
SPEAR (Ours)
1.25
1.0x10
40.0
98
SPEAR (Ours)
1.50
1.0x
38.5
99
SPEAR (Ours)
1.75
10x10-1
39.2
99
SPEAR (Ours)
2.00
100
39.6
SPEAR (Ours)
1.00
5.0
32.3
97
SPEAR (Ours)
1.25
5.0
33.5
98
SPEAR (Ours)
1.50
5.0x10-5
344
99
SPEAR (Ours)
1.75
5.0x
34.6
100
SPEAR (Ours)
2.00
50
34.1
100
SPEAR (Ours)
1.00
1.0
29.7
98
SPEAR (Ours)
1.25
100100
29.3
97
SPEAR (Ours)
1.50
100
29.9
SPEAR (Ours)
1.75
1.0
10-4
29.4
98
SPEAR (Ours)
2.00
1.0
28.7
95
We note that SPEAR can be even be generalized to FedAvg protocols that use random mini-batee batches X of size mini sampled from X each local step. This is the case, as each local client gradient ac ac aw: az: (X*)T, can be represented as 02
0c X", where 0c is derived from OZ OC by adding 0 ac columns at batch positions corresponding to batch elements not in X Importantly, as U2 only dc adds 0 columns to az., the sparsity az= can only increase, allowing to conclude that Σ.=1 a2 remains sparse, and, thus, Theorem 3.3 can still be applied to it.
aZ=
02
Experiments with FedAvg Updates Next, we show empirically the effectiveness of SPEAR for FedAvg updates. Table 10, we show the results of attacking clients with 6 20 datapoints from the IINNNMTG dataset for different number of local client epochs E. We observe that even for = 50 gradient steps we recover data from most batches, with quality similar to the quality achieved when attacking individual gradients. This is expected as Theorem 3.3 still holds, as described in the previous paragraph. The slight dip in the fraction of reconstructed batches for larger number of steps E can be attributed to some client batches inducing larger discrepancy between the sparsity patterns of 0C compared to others, resulting in their sum being much less sparse. Further, Table 10 also a2 shows that SPEAR can attack client updates that take 6/ 6mmm = 4 local steps per epoch for & = 20 epochs. Interestingly, while total of 80 gradient steps are taken in this scenario the results are closer the b 20, m 20 setting, instead of the bmini 20, E 50 setting. This can be explained by the increased sparsity of the individual expanded gradients ac
az
Finally, experiment with different local client learning rates and show the results in Table 11. We observe that even for large learning rates SPEAR still recovers its inputs well, showing that while the individual weights W can change a lot, their induced sparsity on azc remains consistent.
dc
G Additional Visualisations
In this section we present additional visualisations of the reconstructions obtained by SPEAR. First, in Fig. 9 we show an extended comparison between the images recovered by our method and Geiping
22

---

Table 10: Reconstruction quality across 100 FedAvg client updates computed on TINYIMAGENET batches of size b 20 for different number of epochs & and different mini batch sizes bmini-
Umini
PSNR
Acc (%)
0.01
20
97.8
97
0.01
20
103.9
100
0.01
10
20
106.7
99
0.01
20
20
108.90
98
0.01
50
20
104.9
90
0.01
20
5
106.7
97
Table 11: Reconstruction quality across 100 FedAvg client updates computed TINYIMAGENET batches of size b = 20 for different local client learning rates
7
Omini
PSNR
Ace (%) 1
0.1
20
119.3
95
0.01
20
103.9
100
0.001
20
85.5
100
Exact Reconstruction (SPEAR
Approximate Recon. [1]
Original Image
Exact Reconstruction (SPEAR
Approximate Recon.
[1]
Original Image
Figure 9: The reconstructions of all images from Fig. I, reconstructed using our SPEAR (top) or the prior state-of-the-arr Geiping et al. [1] (mid), compared to the ground truth (bottom).
et al. [1] on the TINYIMAGENET batch first shown Fig. In Fig. we operate in the same setting Table 8, namely batches of only single class. We observe that while some images reconstructed well by Geiping et al. [1], most the images are of poor visual quality, with some even being hard to recognize. In contrast, all of our reconstructions means, that SPEAR'S ' reconstructions improve in fine-detail recovery even upon the well recovered images of Geiping al. [1]. This is expected
pixel perfect. This in particular also
attack exact (up numerical errors).
Further, to show the results in Fig. are representative, in Fig. 10-12 we provide additional visualiza- tions of the reconstructions obtained by SPEAR corresponding to the thth th and 90th percentiles experiment reported in Table We observe that
of the PSNRs obtained in the TINYIMAGENT only 1 sample has visual artefacts for the 10th percentile batch (top left image in Fig. 10) and that the 50th and thth percentile batches contain only perfect reconstructions. We theoreticize that the visual artefact in Fig. 10 is result of numerical instability issue and that using L of bigger size as described in App. E.6 one could further alleviate it in exchange of additional computation.
Finally, we demonstrate what happens to SPEAR reconstructions in the rare case when the algorithm fails to recover all correct directions y from the batch gradient. Fig. 13, we show the only such batch for the TLNYIMAGENT experiment reported in Table 3. The batch has 2 wrong directions and
23

---

still achieves an average PSNR of 91.2 (the worst PSNR obtained in this experiment), which is still much higher compared to prior work. Further, all but images are affected by the failure.
Exact Reconstruction (SPEAR ours)
Original Image
Exact Reconstruction (SPEAR
Original Image
Figure 10: Visualisation of the images reconstructed by SPEAR from the batch whose PSNR is the 10th percentile based on the set of 100 TINYIMAGENET reconstructions reported Table
Exact Reconstruction (SPEAR
Original Image
Exact Reconstruction (SPEAR ours)
Original Image
Figure 11: Visualisation of the images reconstructed by SPEAR from the batch whose PSNR is at the 50th percentile based on the of 100 TINYIMAGENET reconstructions reported Table 3.
Exact Reconstruction (SPEAR - ours)
Original Image
Exact Reconstruction (SPEAR ours)
Original Image
Figure 12: Visualisation of the images reconstructed by SPEAR from the batch whose PSNR is at the 90th percentile based on the set of 100 TINYIMAGENET reconstructions reported in Table 3.
24

---

Exact Reconstruction (SPEAR - ours)
Original Image
Exact Reconstruction (SPEAR ours)
Original Image
Figure 13: Visualisation of the images reconstructed by SPEAR from the only batch from the 100 TINYIMAGENET reconstructions reported in Table 3, where not all recovered directions 76 are correct. SPEAR recovered 2/20 wrong directions, resulting the left most images being wrongly recovered.
25

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The main claim of our abstract and introduction sections is that we introduce the first algorithm to reconstruct whole batches of data exactly when 6 > in the important nonest-but-curious setting. To this end, we provide high-level overview of our algorithm SPEAR in Sec. 2 and deeper technical explanation in Sec. 3 that lays in great mathematical details how and why our algorithm is able to recover user data under ReLUUinduced sparsity. We further claim we provide efficient GPU implementation recovering inputs to fully- connected networks fast and precisely even for high- nigh-dimensional inputs when b S 25. Our experiments in Sec. 6 show that for these batch sizes on high--dimessioall inputs like IMAGENET images our algorithm is significantly faster compared to prior work, while also recovering the images up to numerical precision. Finally, we claim that our method, despite its exponential runtime, can in theory recover the client inputs for much larger batch sizes b under sufficient compute. These claims are supported by our theoretical analysis in Sec. 5.2 and our experiments in Sec. 6.3.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should elearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as it is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We discuss our limitations in a separate limitation section (Sec. 8). The broader impact of our work is discussed in App. A.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
26

---

If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: We provide proofs for theorems either immediately following the theorems themselves or in App. B. We explicitly state all theorem assumptions.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [Yss]
We provide code in the accompanying GitHub repository. Further, Sec. 3 we give all technical details needed reimplement our algorithm. Finally, in Sec. 6 explain in detail how our experiments were performed.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often good way to accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (c.g., in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
27

---

(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily
model architecture, the paper should descrihe the architecture clearly and fully.
(c) the contribution is a new model (e.g.. a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (c.g., with an open- open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers have some path reproducing verifying the results. 5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: We provide the code the accompanying GitHub repository alongside instal- lation instructions and example commands. We rely only on publicly available datasets.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cc.
for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: / //niss cc/publu wubblic/guiiee /eguude//oeeeuunnnnnnnn CodeSubmisss ssiinsssssooooo licy for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification:
Yes we list all details of our experiments in Sec. 6.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
28

---

Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: We provide error bars for our main experiments in App. E. as well as, our failure probability verification experiments in App. E.5. We didn't provide error bars for our other experiments due to computational limitation.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: We provide information about the amount and types of compute needed to conduct our experiments in Sec. 6.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurin: cc/puulic/Etthicsuuieel....
Answer: [Yes]
Justification: This paper does not introduce new models or datasets. We use only standard datasets in our experiments and provide discussion of their licenses in App. D. We discuss our broader impact on privacy of federated learning in App. A.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
29

---

If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: We provide discussion of our broader impact in App. A. We discuss possible mitigations our attack in App. E.6
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (c.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [Yes]
Justification: Our code is publicly available at our GitHub repository under license that only permits educational and academic uses and explicitly forbids malicious uses including obtaining, accessing, or disclosing private or confidential information about individuals.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
30

---

Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We use only standard datasets in our experiments and provide discussion of their licenses in App. D.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We do not introduce new datasets models. We provide the code in GitHub repository alongside instructions for installations.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/codeemoodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether how consent was obtained from people whose asset used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
31

---

15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
32


Reviews:
[{"review_id": "w7RgAC1GNZ", "reviewer": "Reviewer_Brdw", "summary": "The paper presents SPEAR, a novel algorithm for exact gradient inversion of batches in federated learning. Unlike previous methods, SPEAR achieves exact reconstruction for larger batches by leveraging low-rank structure and ReLU-induced sparsity in gradients. The authors provide a theoretical foundation and an efficient GPU implementation, demonstrating the effectiveness of their approach on high-dimensional datasets and large networks.", "questions": "SPEAR is effective for a moderate batch size of b < 25. What are the possible reasons to prevent the batch size to become larger?", "limitations": "See weakness.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1. The paper introduces a significant advancement in gradient inversion attacks by enabling exact reconstruction for batch sizes greater than one.\n2. The authors provide a strong theoretical basis for their method, including proofs of the low-rank nature of gradients and the sparsity induced by ReLU activations.", "weaknesses": "1. The theoretical analysis only considers the ReLu and fully connected layer.\n2. The method only seems to be effective for a small batch size, even though it has already been a big progress.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the very positive review and are excited that the reviewer finds that SPEAR marks a significant advancement for gradient inversion. We are also happy to read that the reviewer attests that our method builds on a strong theoretical basis and credits our soundness, presentation and contribution. We answer all of the reviewer's questions in the general response: \n\n**Q1: SPEAR is effective for a moderate batch size of b < 25. What is preventing SPEAR from scaling beyond this?**\n\nPlease see our detailed reply in the main response (Q1). \n\n**Q2: Can SPEAR handle activations beyond ReLU?**\n\nPlease see our detailed reply in the main response (Q2). \n\n**Q3: Can SPEAR handle layers other than fully connected layers?**\n\nPlease see our detailed reply in the main response (Q3). \n\nWe are happy to discuss any remaining questions or follow-up questions the reviewer might have.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "HZVNgoZzUs", "reviewer": "Reviewer_38cL", "summary": "This paper introduces a novel approach to input reconstruction for neural networks, focusing specifically on linear layers followed by ReLU activations. \nThe key aspects of this method are:\n\nLow-rank decomposition: The authors leverage low-rank matrix decomposition techniques to simplify the representation of the linear layer's weight matrix.\n\nReLU sparsity exploitation: The method takes advantage of the sparsity induced by the ReLU activation function following the linear layer. This sparsity provides additional constraints that aid in the reconstruction process.\n\nEfficient disaggregation algorithm: A core contribution of the paper is an efficient algorithm for searching the columns of the disaggregation matrix Q. This matrix plays a crucial role in the reconstruction process.\n\nInput reconstruction: By combining these elements, the authors demonstrate a method to reconstruct input examples from the output of a linear layer followed by a ReLU activation.", "questions": "See above.", "limitations": "See above.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Its a really interesting idea to reconstruct from gradients and provide a mathematical explanation of previous work [1] (from the paper’s citation) and this work.\n\nProof is clean and precise. Also discuss many settings, like layer width and batch size. It also provides a theory bound for failure probability in reconstruction attacks.\n\nThe reconstruction result and reuse quality for reconstruction images are really good.\n\n[1] Kariyappa, Sanjay, et al. \"Cocktail party attack: Breaking aggregation-based privacy in federated learning using independent component analysis.\" International Conference on Machine Learning. PMLR, 2023.", "weaknesses": "It performs better than [1] in the reconstruction result, but the batch size would be a bottleneck since the method is bound by batch size to resolve, and [1] can reach out to batch size > 64 easily. \n\nInteresting idea but miss some experiments and discussion: \n\n1. It only provides experiments run on 1st linear layer setting. However, in many NN designs,  linear layers are usually after the conv layer or before softmax. Could you provide a more detailed discussion about using your method for linear layer after conv layers in more practical setting? like [9]’s section 4\n\n2. In the supplement code section, it only provides experiments based on relu1 and fc1, Could you run quick experiments and report performance on different/later fc layers?\n\nIf the result is limited to the first fc layer, then it has some interesting innovation in method design but is not really practical. \n\nAlso, if authors can provide more no cherry-picking visualization results on different fc layers or fc after conv for different datasets in the appendix,?\n\nFor E6 DPSGD part, usually sigma = 1*10-4 is considered to be really large eps and too little noise, which is not considered practical privacy protection. For DPSGD on  linear layer NN, sigma = 0.01 with some reasonable setting can be considered as eps = 80–100 ( I might calculate wrong but its around that number), which is still not useful for DPSGD.\n\n[1] Kariyappa, Sanjay, et al. \"Cocktail party attack: Breaking aggregation-based privacy in federated learning using independent component analysis.\" International Conference on Machine Learning. PMLR, 2023.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive review and are glad to read they found our contribution really interesting, the proofs clean and precise and the reconstruction quality really good. \n\n**Q1: Can SPEAR scale to batch sizes greater than 64?**  \nYes, we address this in the general response (Q1). Specifically, we show that SPEAR can leverage optimization-based methods to scale to significantly larger batch sizes while still providing (almost) perfect reconstruction. \n\n**Q2: Can SPEAR handle a linear layer that is preceded by a conv layer?**  \nYes. We added an experiment showing perfect reconstruction results for VGG16 and $b=20$ in Table 1 in the rebuttal PDF. Please refer to Q3 in the general response for more information about this experiment. \n\n**Q3: Can you provide experiments, where SPEAR reconstructs inputs to linear layers that are not the first one?**  \nYes. We consider a 6-layer network with 400 neurons in each layer and a batch size of 20 and report the mean absolute error (MAE) to the original activations in Table 2 in the rebuttal PDF. Our experiments indicate that we can recover almost all inputs to all layers (almost) perfectly. Please refer to Q3 in the main rebuttal for more details about this experiment. \n\n**Q4: Are the provided visualizations representative? Can the authors provide more visualizations of the SPEAR’s results?**  \n\nWe want to clarify that the visualizations provided in Figure 1 of the main paper are a subsample of the visualizations provided in Figure 9 in Appendix G, where we visualize the corresponding full batch. The batch in Figure 9 is representative as it was randomly chosen and has a PSNR similar to the overall PSNR mean. To reaffirm this point, we provide further batch visualizations in Figures 1-3 in the rebuttal PDF. These visualizations are in the same setting as Figure 1 of the main paper, but their corresponding batches are chosen to represent the $10^{\\text{th}}$,$50^{\\text{th}}$, and $90^{\\text{th}}$ percentiles of the obtained PSNRs in this experiment. We observe that only 1 sample is not perfectly reconstructed for the $10^{\\text{th}}$ percentile batch (which we show in its corresponding figure) and that the $50^{\\text{th}}$ and $90^{\\text{th}}$ percentile batches contain only perfect reconstructions. \n\nFurther, we note that Figure 10 in Appendix G visualizes the batch on which SPEAR performed the worst on TinyImageNet. Manual inspection showed that its poor performance is caused by SPEAR failing to recover one of the directions $\\overline{q}_i$. We will clarify these points and provide further visualizations in the next version of the paper.\n\n**Q5: What is SPEAR’s performance under rigorous DPSGD guarantees?**  \nWe want to clarify that the results in Appendix E.6 were obtained by adding Gaussian noise to the gradient, as a viability test of SPEAR’s robustness against noisy gradients. Specifically, we did not do the gradient clipping necessary for DPSGD. We will clarify this in the paper and also provide new experiments, showing SPEAR’s results in the DPSGD setting alongside the corresponding  $(\\epsilon,\\delta)$ guarantee.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7421HERaP2", "reviewer": "Reviewer_LPF2", "summary": "This paper studied the gradient inversion problem in federated learning. In particular, an honest-but-curious server follows the federated training protocol but aims to infer private information from gradients collected from clients. The paper proposed a novel approach, SPEAR, that exploits the low-rank and sparsity properties of gradients corresponding to linear layers with ReLU activations, and recovers input data of batch size greater than 1 almost perfectly with high probability. The algorithm is a combination of matrix decomposition and a optimisation-based filtering procedure. The performance of the algorithm is explained by theoretical analysis and empirical evaluations, which is significantly better than previous methods that struggle to deal with large batch sizes.", "questions": "- When the batch size increases, is there a trade-off scheme that sacrifices the fidelity of recovered images but reduces the running time?\n\n- Can the algorithm deal with normalization layers?\n\n- Can the algorithm be adapted to convolutional networks and (vision) transformers?", "limitations": "The paper discussed limitations.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- Recovering batched images from gradients has been a challenging task. The algorithm introduced in this paper is built on insightful observations on the gradients and solid theoretical justifications, which can inspire further work in this area.\n\n- The proposed algorithm works well empirically, under necessary requirements such as fully connected networks and moderate batch size. Sufficient ablations are provided to evaluate different aspects of the algorithm.\n\n- The exposition of the paper is nicely structured.", "weaknesses": "- The effectiveness of the algorithm relies on the assumption that the first layer of the network is a linear layer (while for linear layers in the middle or at the end of the network the algorithm can only recover the intermediate input to those layers, not the original images). However, this is not the case for many popular convolutional networks for image tasks. The application of the algorithm is restricted and it can be easily defended in practice.\n\n- The running time of the algorithm is exponential in the batch size, and the success probability may drop significantly for large batch size. Moreover, it is not clear if the algorithm is effective for high-resolution datasets like ImageNet.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive review. We are happy to read that they find our contribution insightful and inspiring future work and credit our significantly better performance and theoretical analysis. Further, we are glad the reviewer deems the paper nicely structured. \n\n**Q1: Can the exponential sample complexity of SPEAR be improved? Is the probability of failure a bottleneck in practice?**\n\nYes, the exponential sample complexity can be addressed, as we discuss in the general response (Q1). Specifically, there we show that SPEAR can leverage optimization-based methods to circumvent the exponential sampling-based information retrieval to scale to much larger batch sizes while still providing (almost) perfect reconstruction, and we clarify that the failure probability is not currently a bottleneck (see also Figure 3 in the main paper).\n\n**Q2: Is the algorithm effective for high-resolution datasets like ImageNet?** \n\nAs highlighted in the abstract, SPEAR reconstructs batches of sizes up to 25 on ImageNet exactly. We provide more corresponding results in Section 6.2 (Main Results). Specifically, we run experiments on the commonly used resolution of 224x224 for ImageNet and also on a 720x720 high-resolution setting to showcase our scalability even further. We note that this is, as shown in Table 3, at the very moderate cost of a runtime increase from 2.1 minutes to 2.6 minutes per batch. This is significantly faster than prior work as shown in Table 1, where we compare various works on ImageNet using a resolution of 256x256. Could the reviewer clarify the question in case we misunderstood it? \n\n**Q3: Does the effectiveness of the algorithm rely on the assumption that the first layer of the network is a linear layer?**\n\nNo. As discussed in Q3 of the main response, SPEAR can be efficiently applied to any linear layer that precedes or follows ReLU activations to obtain that layer’s inputs. Even when the attacked layer is in the middle of the network the intermediate inputs recovered via SPEAR pose an increased risk to the privacy of the client data. We demonstrate the practicality of using SPEAR on linear layers in the middle of the network by attacking VGG16, as shown in Table 1 in the rebuttal PDF. See Q3 of the main response for further details.\nFurther, we emphasize that our method is a significant theoretical advancement over prior work, providing novel insights into the gradient leakage problem as acknowledged by the reviewers. We focus on ReLU with linear layers to open the field for further research. There is already very promising future research building on the insights gained in this work. See our answer to Q6. \nFinally, for tabular datasets, networks starting with a linear layer are common. In this setting SPEAR outperforms all prior work by a wide margin in terms of input reconstruction quality and speed, particularly when no further priors are given. \n\n**Q4: When the batch size increases, is there a trade-off scheme that sacrifices the fidelity of recovered images but reduces the running time?**\n\nYes, the threshold we use to test if an entry in $L \\overline q_i$ is 0 can be tuned. As we use this test to filter out wrong proposal directions (see Section 4.1), high thresholds can permit directions computed in a numerically unstable way (e.g. due to applying Theorem 3.4 on matrices $L_A$ that are not so well-conditioned), leading to lower reconstruction quality but faster runtime. While tuning this threshold can yield a noticeable speedup, it does not address the exponential nature of our algorithm\nHowever, if one would like to resolve the exponential runtime of SPEAR, we propose a combination with an optimization-based method to get priors on the signs of $Z$. Please see our reply to question Q1 in the main response, where we discuss in detail how this allows SPEAR to scale to significantly larger batch sizes while retaining exact reconstruction.\n\n**Q5: Can the algorithm deal with normalization layers?** \n\nAs Batch-Norm layers compute batch statistics at training time and then use these statistics to normalize the activations, they entangle the gradients of all batch elements. This makes the analysis of the gradient structure significantly more complex and prevents us from directly applying SPEAR as now the output of the BN rather than the linear layer has sparse gradients. On the other hand, this normalization and rescaling allows us to compute a very precise estimate of the expected sparsity for the ReLU inputs $Z$ and thus improve our filtering described in Section 4. While we have promising initial results addressing this issue, SPEAR requires significant non-trivial adaptations for BN-layers, which we believe is an interesting item for future work.\n\n**Q6: Can the algorithm be adapted to convolutional networks and (vision) transformers?** \n\nYes, there is recently published work on Transformers relying on insights from this work, that also significantly outperforms all prior work. We contacted the chair to share this work with you. For applications to convolutional networks, please see our reply to Q3 in the main response.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "788IALxzfu", "reviewer": "Reviewer_Xnvh", "summary": "This paper presents a novel method to recover batched input data from gradients in fully-connected networks. Based on a detailed analysis of the rank of gradients, it utilizes matrix decomposition to first figure out the batch size and then recover the input tensor through sparsity. Good comparisons with previous methods have demonstrated the performance of such a method.", "questions": "- It seems this work relies highly on the sparsity. What if the activation function is sigmoid, leakyReLU, tanh, etc? These activations do not directly filter out negative inputs and return 0s, which may affect the sparsity property.\n- For experiments in 6.2, are the image labels known for the reconstruction ahead of time? \n- Why is it that this method may fail when batchsize is larger than 25? In my personal view, more insights could be covered about this direction in the failure probability part.", "limitations": "The proposed method only works for FCNs.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- Good writing. The structure is well-organized.\n- It is of great value to discover the mathematical relationships within the gradient matrixes, and then use matrix decomposition to solve this problem.\n- Comparisons with previous methods, both in the image and tabular data domains, make this work convincing.", "weaknesses": "Please refer to the Questions part.\nMinor problem: It is recommended that the work should be double-checked in case of typos or compiling errors.\n- Line 79 typo\n- Line 125 typo\n- Line 149 abnormal block", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their very positive review. We are particularly happy to read that the reviewer assesses our contribution to be of great value and finds the comparison to related work convincing. We will include all proposed writing suggestions. We now address all questions of the reviewer. \n\n**Q1: Can SPEAR handle activation functions different from ReLU?**\n\nWe direct the reviewer to our previous answer to question **Q2** in the general response. In this work, we focus on the most common ReLU activation as it is the most relevant one in practice. Further, we believe that transferring our insights to other activations is a valuable item for future work. \n\n**Q2: For experiments in 6.2, are the image labels known for the reconstruction ahead of time?**\n\nNo, we do not require the knowledge of labels at all. We do want to emphasize that the only prior we utilize is the ReLU-induced sparsity. \n\n**Q3: Why can SPEAR fail when the batch size is larger than 25? Is this handled by the probability of failure analysis?**\n\nWe refer the review to our answer to Q1 in the main response. As outlined there, the failure probability for reasonable network widths is not a significant bottleneck for the batch sizes we experimented with. Instead, the bottleneck is the number of submatrices $L_A$ one needs to sample to recover all the correct directions $\\overline{q}$, which is analyzed in Lemma 5.2. In practice, we limit this number to fit in a reasonable time limit and we report a failure otherwise. We emphasize that SPEAR, in theory, is capable of recovering inputs for batch sizes $> 25$ provided enough time. As outlined in the general response to Q1, one can use approximate reconstruction methods to guide the search for those submatrices, lifting the restriction, and allowing exact reconstructions for batch sizes as large as 100. Finally, we provide experiments in Appendix E5, showing that the predicted failure probabilities agree well with empirical results for small to moderate layer widths.\n\nWe are happy to discuss any remaining or follow-up questions the reviewer might have.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for their positive and helpful feedback. We are encouraged they consider our work to mark a significant advancement (Brdw), provide valuable insight (LPF2, Xnvh), our theory to be well founded (Brdw, 38cL), our presentation to be good (Brdw, LPF2, Xnvh) and our reconstruction results to look really good (38cL, Xnvh). Based on the reviewers' suggestions, we conducted a range of additional experiments, reporting results in the attached PDF. Below, we address the topics we found to be shared amongst reviewers or ones we believe are of major importance.

**Q1: What prevents SPEAR from scaling to larger batch sizes, and how can this limitation be overcome? (Reviewers Brdw, 38cL, LPF2, Xnvh)**  
First, we would like to highlight that in the common regime where the batch size is small in comparison to the dimensions of the linear layer, we prove that w.h.p. the input information is losslessly represented in the gradient (see Figure 3). SPEAR is not failing for large batch sizes because the relevant information can not be retrieved but solely because we set a timeout on sampling as exponentially many samples would be required. A theoretical analysis of this is provided in Lemma 5.2. 

This exponential sampling complexity can be addressed by combining SPEAR with an approximate reconstruction method to get a prior on which submatrices $L_A$ satisfy the conditions of Theorem 3.3, i.e., have corresponding matrices $A$ containing a 0-column. Using approximate, optimization-based input reconstruction techniques we can estimate the pre-activation values $Z$ and thus positions of $0$s in $\tfrac{\partial \mathcal{L}}{\partial Z}$. We can now use the estimated locations of the 0 entries in $\tfrac{\partial \mathcal{L}}{\partial Z}$ to directly sample $L_A$ matrices for which Theorem 3.3’s prerequisites are likely satisfied, drastically speeding up SPEAR’s information retrieval. 

We confirm the effectiveness of this approach in a preliminary study, shown in Table 3 in the rebuttal PDF, allowing SPEAR to scale to batch sizes beyond 100. Specifically, we use the modern version of Geiping et al. [1] to get priors on $Z$ and considered the most negative entries of the approximated $Z$ to be the ones with the highest likelihood of actually being negative. We consider a network with $m=2000$ and 6 layers, and batches of 100 TinyImageNet images. There, Geiping has a PSNR of 32.8 while SPEAR reconstructs 6 out of 10 random batches exactly (PSNR of 120) and reconstructs 98 or 99 directions correctly on the remaining four batches, leading to an overall PSNR of 81.5. These results confirm that SPEAR can be effectively scaled to larger batches, with further optimizations being left to future work.

**Q2: The work is restricted to ReLU activations. Can you handle other activations, including sigmoid, leakyReLU, tanh, etc? (Reviewers Brdw, Xnvh)**  

In this work, we focus on ReLU activations as they are the most relevant activation function in practice. However, more broadly, the core of our method is to utilize low rankness and priors on the activation function in order to not need priors on the client input data. While the low-rankness can directly be transferred to other activations, we believe extending the priors to other activations makes for an interesting future work item. We emphasize that SPEAR is the first exact method to reconstruct network inputs from gradients originating from batches with a batch size greater than 1.

**Q3: Is SPEAR applicable to architectures that do not have a fully connected layer immediately following their input? (Reviewers Brdw, 38cL, LPF2)**  

Yes, it is. While the evaluation primarily focuses on recovering inputs to the first FC layer of a fully connected network with ReLU activations, our method allows the recovery of inputs of any FC layer preceded or followed by a ReLU activation regardless of the architecture used, as emphasized in Section 3.2. This is demonstrated in Table 2 in the rebuttal PDF, where we successfully recover the inputs to all layers followed by a ReLU in a $L=6$ layer FC network with width $m=400$. While these intermediate layer inputs may not violate the client privacy as severely as directly obtaining the user data exactly, the authors of [9] demonstrate that recovering individual batch inputs to intermediate layers can further boost the performance of optimization-based gradient leakage attacks and poses additional privacy issues for the clients. 

Crucially, [9] makes this observation in the context of convolutional neural networks (CNNs). We also experimented with recovering the inputs to the FC layers in CNNs. Specifically, we attacked the first FC layer of a VGG16 network for ImageNet batches of size $b=20$. We present the results in Table 1 in the rebuttal PDF. Our results demonstrate that SPEAR recovers 100% of the individual linear layer inputs up to numerical precision. Thus, we are confident that SPEAR can improve optimization-based gradient leakage attacks for CNNs. We will add this to the paper.

Apart from CNNs, FC layers are the predominant layers for other domains, such as tabular data, where we significantly outperform the current state-of-the-art (Table 2, main paper). Further, for transformers, there is very promising follow-up work leveraging SPEAR’s insights to achieve state-of-the-art reconstruction of text by a wide margin. We have contacted the chair to share an anonymized copy of the follow-up work with you. All of this confirms the generality and applicability of SPEAR, as well as its significant impact on the field of gradient leakage. 

**Conclusion**  
We hope to have been able to address the reviewers’ questions and look forward to the discussion period.

Meta-review: This paper focuses on proposing inversion attacks on federated learning methods that can reconstruct this data from the shared gradients. Specifically, the authors propose SPEAR which is a novel algorithm for exact gradient inversion of batches in federated learning. Unlike previous methods, SPEAR achieves exact reconstruction for larger batches by leveraging low-rank structure and ReLU-induced sparsity in gradients. The authors further provide a theoretical foundation and an efficient GPU implementation, demonstrating the effectiveness of their approach on high-dimensional datasets and large networks.

After the rebuttal/discussion period, all the reviewers are now of the opinion that the paper provides a set of novel contributions that are carefully evaluated. Hence, I would like to recommend the paper to be accepted. I thank the authors for their great efforts in addressing all the concerns. I would further like to suggest that the authors revise the manuscript carefully to address all the comments.
Decision: Accept (poster)