SPEAR: Exact Gradient Inversion of Batches in Federated Learning

Authors: dimitar i dimitrov
maximilian  baader
mark niklas müller
martin  vechev
st  kliment ohridski
eth  zurich
logicstar  ai
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 16:32:28

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.

Main paper: 
 introduction: 
 Exact Recon. (SPEAR -ours)Recon. [1] Original Image Federated Learning has emerged as the dominant paradigm for training machine learning models collaboratively without sharing sensitive data [2] . Instead, a central server sends the current 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).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 was shown to be possible for batch sizes of b = 1 [5, 6] , it was assumed to be infeasible for larger batches. This led to a line of research on approximate methods that sacrificed reconstruction quality in order to recover batches of b > 1 inputs [7, 8, 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.This Work: Exact Reconstruction of Batches We propose the first gradient inversion attack reconstructing inputs exactly for batch sizes b > 1 in the honest-but-curious setting. In Fig. 1 , we show the resulting reconstructions versus approximate methods [1] for a batch of b = 20 images.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 to the input dimensionality n and the hidden dimension m. Second, the (unknown) gradients with respect to the inputs of the first ReLU layer are sparse due to the ReLU function itself. We combine these properties with ideas from sparsely-used dictionary learning [10] to propose a sampling-based 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 a 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.• The first gradient inversion attack showing theoretically that exact reconstruction of complete batches with size b > 1 in the honest-but-curious setting is possible. • SPEAR: a sampling-based algorithm leveraging low rankness and ReLU-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 a wide range of settings and make publicly available on GitHub.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 b > 1 in the important honest-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 ReLU-induced sparsity. We further claim we provide efficient GPU implementation recovering inputs to fullyconnected networks fast and precisely even for high-dimensional inputs when b ≲ 25.Our experiments in Sec. 6 show that for these batch sizes on high-dimensional 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. 
method overview: 
 Figure 2 : Overview of SPEAR. The gradient ∂L W is decomposed to R and L. Sampling gives N proposal directions, which we filter down to c candidates via a sparsity criterion with threshold τ * m. A greedy selection method selects batchsize b directions. Scale recovery via ∂L ∂b returns the disaggregation matrix Q and thus the inputs X.We first introduce our setting before giving a high-level overview of our attack SPEAR, whose sketch is shown in Fig. 2 .Setting We consider a neural network f containing a linear layer z = W x + b followed by ReLU activations y = ReLU(z) trained with a loss function L. Let now X ∈ R n×b be a batch of b inputs to the linear layer Z = W X +(b| . . . |b), with weights W ∈ R m×n , bias b ∈ R m and output Z ∈ R m×b . Further, let Y ∈ R m×b be the result of applying the ReLU activation to Z, i.e., Y = ReLU(Z) and assume b ≤ m, n. The goal of SPEAR is to recover the inputs X (up to permutation) given the gradients ∂L ∂W and ∂L ∂b (see Fig. 2, i ).Low-Rank Decomposition We first show that the weight gradient ∂L ∂W = ∂L ∂Z X ⊤ naturally has a low rank b ≤ m, n (Theorem 3.1) and can therefore be decomposed as ∂L ∂W = LR with L ∈ R m×b and R ∈ R b×n using SVD (Fig. 2 , ii). We then prove the existence disaggregation matrix Q = (q 1 | . . . |q b ) ∈ GL b (R), allowing us to express the inputs as X ⊤ = Q -1 R and activation gradients as ∂L ∂Z = LQ (Theorem 3.2). Next, we leverages the sparsity of ∂L ∂Z to recover Q exactly.ReLU Induced Sparsity We show that ReLU layers induce sparse activation gradients ∂L ∂Z (Sec. 3.2). We then leverage this sparsity to show that, with high probability, there exist submatrices L A ∈ R b-1×b of L, such that their kernel is an unscaled column q i of our disaggregation matrix Q, i.e., ker(L A ) = span(q i ), for all i ∈ {1, . . . , b} (Theorem 3.3). Given these unscaled colmuns q i , we recover their scale by leveraging the bias gradient ∂L ∂b (Theorem 3.5).To identify the submatrices L A of L which induce the directions q i , we propose a sampling approach (Sec. 4.1): We randomly sample b -1 rows of L to obtain an L A and thus proposal direction q ′ i = ker(L A ) (Fig. 2 iii). Crucially, the product Lq ′ i = ∂L ∂zi recovers a column of the sparse activation gradient ∂L ∂Z for correct directions q ′ i 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 L A to be filtered to c ≳ b unique candidates (Fig. 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 b directions inducing the highest sparsity in ∂L ∂Z ′ = LQ ′ . To assess the quality of this solution Q ′ , we introduce the sparsity matching score σ which measures how well the sparsity of the activation gradients ∂L ∂Z ′ matches the ReLU activation pattern induced by the reconstructed input X ′⊤ = Q ′-1 R. Finally, we greedily optimize Q ′ to maximize the sparsity matching score, by iteratively replacing an element q ′ i of Q ′ with the candidate direction q ′ j yielding the greatest improvement in σ until convergence. We can then validate the resulting input X ⊤ = Q -1 R by checking whether it induces the correct gradients. We formalize this as Alg. 1 in Sec. 5 and show that it succeeds with high probability for b < m.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 no 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 a 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 a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a 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 of the proposed algorithms and how they scale with dataset size.• 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, a 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 important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
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 we recover X. Specifically, in Sec. 3.1, we first argue that ∂L ∂W = ∂L ∂Z X T follows direclty from the chain rule. We then show that for every decomposition ∂L ∂W = LR, there exists an unknown disaggregation matrix Q allowing us to reconstruct X ⊤ = Q -1 R and ∂L ∂Z = 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 ∂L ∂Z , 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 ∂L ∂b . Unless otherwise noted, we defer all proofs to App. B.We first show that the weight gradients ∂L ∂W can be written as follows: Theorem 3.1. The network's gradient w.r.t. the weights W can be represented as the matrix product:EQUATIONFor batch sizes b ≤ n, m, the dimensionalities of ∂L ∂Z ∈ R m×b and X ∈ R n×b in Eq. 1 directly yield that the rank of ∂L ∂W is at most b. This confirms the observations of Kariyappa et al. [9] and shows that X and ∂L ∂Z correspond to a specific low-rank decomposition of ∂L ∂W . To actually find this decomposition and thus recover X, we first consider an arbitrary decomposition of the form ∂L ∂W = LR, where L ∈ R m×b and R ∈ R b×n are of maximal rank. We chose the decomposition obtained via the reduced SVD decomposition of ∂L ∂W = U SV by setting L = U S 1 2and R = S 1 2 V , where U ∈ R n×b , S ∈ R b×b and V ∈ R b×n . We now show that there exists an unique disaggregation matrix Q recovering X and ∂L ∂Z from L and R: Theorem 3.2. If the gradient ∂L ∂Z and the input matrix X are of full-rank and b ≤ n, m, then there exists an unique matrix Q ∈ R b×b of full-rank s.t. ∂L ∂Z = LQ and X T = Q -1 R. Theorem 3.2 is a direct application of Lemma B.1 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 ∂L ∂Z matrices is equivalent to obtaining the unique disaggregation matrix Q. Next, we show how the ReLU-induced sparsity patterns in ∂L ∂Z or X can be leveraged to recover Q exactly.ReLU activation layers can induce sparsity both in the gradient ∂L ∂Z (if the ReLU activation succeeds the considered linear layer) or in the input (if the ReLU activation precedes the linear layer).Gradien Sparsity If a ReLU activation succeeds the linear layer, i.e., Y = ReLU(Z), we have∂L ∂Z = ∂L ∂Y ⊙ 1 [Z>0], where ⊙ is the elementwise multiplication and 1 [Z>0] is a matrix of 0s and 1s with each entry indicating if the corresponding entry in Z is positive. At initialization, roughly half of the entries in Z are positive, making ∂L ∂Z sparse with ∼ 0.5 of the entries = 0.Input Sparsity ReLUs also introduce sparsity if the linear layer in question is preceded by a ReLU activation. Here, X = ReLU( Z) 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 a fully connected network, we have sparsity in both, X and ∂L ∂Z . Due to the symmetry of their formulas in Theorem 3.2, our method can be applied in all three arising sparsity settings. In the remainder of this work, we assume w.l.o.g. that only ∂L ∂Z is sparse, corresponding to the first layer of a fully connected network. We now describe how to leverage this sparsity to compute the disaggregation matrix Q and thus recover the input batch X.Our exact recovery algorithm for the disaggregation matrix Q is based on the following insight:If we can construct two submatrices A ∈ R b-1×b and L A ∈ R b-1×b by choosing b -1 rows with the same indices from ∂L ∂Z and L, respectively, such that A has full rank and an all-zero i th column, then the kernel ker(L A ) of L A contains a column q i of Q up to scale. We formalize this as follows:Theorem 3.3. Let A ∈ R b-1×bbe a submatrix of ∂L ∂Z s.t. its i th column is 0 for some i ∈ {1, . . . , b}. Further, let ∂L ∂Z , X, and A be of full rank and Q be as in Theorem 3.2. Then, there exists a full-rank submatrixL A ∈ R b-1×b of L s.t. span(q i ) = ker(L A ) for the i th column q i of Q = (q 1 | • • • |q b ).Proof. Pick an i ∈ {1, . . . , b}. By assumption, there exists a submatrix A ∈ R b-1×b of ∂L ∂Z of rank b-1 whose i th column is 0. To construct L A , we take rows from L with indices corresponding to A's row indices in ∂L ∂Z . As ∂L ∂Z and X have full rank, by Theorem 3.2, we know that ∂L ∂Z = LQ, and hence A = L A Q. Multiplying from the right with e i yields 0 = Ae i = L A Qe i = L A q i , and hence ker(L A ) ⊇ span(q i ). Further, as rank(A) = b -1 and rank(Q) = b, we have that rank(L A ) = b -1. By the rank-nullity theorem dim(ker(L A )) = 1 and hence ker(L A ) = span(q i ).∂Z is not known a priori, we can not simply search for such a set of rows. Instead, we have to sample submatrices L A of L at random and then filter them using the approach discussed in Sec. 4. However, we will show in Sec. 5.2 that we will find suitable submatrices with high probability for b < m due to the sparsity of ∂L ∂Z and the large number m b-1 of possible submatrices. We will now discuss how to recover the scale of the columns q i given their unscaled directions q i forming Q.Q Q Q: Recovering the Scale of columns in Q Q Q Given a set of b correct directions Q = (q 1 | • • • |q b ), we can recover their scale, enabling us to reconstruct X, as follows. We first represent the correctly scaled columns as q i = s i • q i with the unknown scale parameters s i ∈ R. Now, recovering the scale is equivalent to computing all s i . To this end, we leverage the gradient w.r.t. the bias ∂L ∂b :Theorem 3.4. The gradient w.r.t. the bias b can be written in the form∂L ∂b = ∂L ∂Z 1 . . . 1 .Thus, the coefficients s i can be calculated as:Theorem 3.5. For any left inverse L -L of L, we have s1 . . .s b = Q -1 L -L ∂L ∂bTheorem 3.5 allows us to directly obtain the true matrix Q = Q diag(s 1 , . . . , s b ) from the unscaled matrix Q. We now discuss how to recover Q via sampling and filtering candidate directions q i .Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Answer: [Yes]Justification: We provide proofs for our 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 crossreferenced. • 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 if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition. • Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced. 
efficient filtering and validation of candidates: 
 In the previous section, we saw that given the correct selection of submatrices L A , we can recover Q directly. However, we do not know how to pick L A a priori. To solve this, we rely on a sampling approach: We first randomly sample submatrices L A of L and corresponding direction candidates q ′ spanning ker(L A ). However, checking whether q ′ is a valid direction is not straightforward as we do not know ∂L ∂Z and hence can not observe A directly as reconstructing ∂L ∂Z = LQ requires the full Q.To address this, we filter the majority of wrong proposals q ′ using deduplication and a sparsity-based criterion (Sec. 4.1), leaving us with a set of candidate directions C = {q ′ j } j∈{1,...,c} . We then select the correct directions in C greedily based on a novel sparsity matching score (Sec. 4.2).4.1 Efficient Filtering of Directions q q q ′ Filtering Mixtures via Sparsity It is highly likely (p = (1 -1 2 b-1 ) b ) that a random submatrix of L will not correspond to an A with any 0 column. We filter these directions by leveraging the following insight. The kernel of such submatrices is spanned by a linear combination q ′ = i α i q i . Thus Lq ′ will be a linear combination of sparse columns of ∂L ∂Z . 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 p f r (τ, m) = 1 2 m ⌊m•τ ⌋ i=0 m i , obtained from the cumulative distribution function of the binomial distribution, small. For example for m = 400 and p f r (τ, m) < 10 -5 , we have τ = 0.395. We obtain the candidate pool C = {q ′ j } j∈{1,...,c} from all samples that were not filered this way.Filtering Duplicates As it is highly likely to have multiple full-rank submatrices A, whose i th column is 0, we expect to sample the same proposal q ′ i multiple times. We remove these duplicates to substantially reduce our search space.While filtering duplicates and linear combinations significantly reduces the number c of candidates, we usually still have to select a subset of b < c. Thus, we have c b 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 a greedy two-stage procedure optimizing a novel sparsity matching score λ, which resolves the computational complexity issue above while also accurately selecting the correct batch elements and relying solely on ∂L ∂Z ′ 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.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 = {q ′ i } b i=1 , yielding the sparsest full-rank gradient matrix ∂L ∂Z is often correct. As the scaling of q ′ i does not change the sparsity of the resulting ∂L ∂Z , we can construct the subset B by greedily collecting the b directions q ′ i with the highest corresponding sparsity that still increase the rank of B. While this method typically recovers most directions q i , it often misses directions whose gradients ∂L ∂zi are less sparse by chance.We alleviate this issue by introducing a second stage to the algorithm where we greedily optimize a novel correctness measure based solely on the gradients of the linear layer, which we call the sparsity matching coefficient λ. Definition 4.1. Let λ -be the number of non-positive entries in Z whose corresponding entries in ∂L ∂Z are 0. Similarly, let λ + be the number of positive entries in Z whose corresponding entries in ∂L ∂Z are not 0. We call their normalized sum the sparsity matching coefficient λ:λ = λ -+ λ + m • b .Intuitively, this describes how well the pre-activation values Z match the sparsity pattern of the gradients ∂L ∂Z induced by the ReLU layer (See Sec. 3.2). While this sparsity matching coefficient λ can take values between 0 and 1, it is exactly λ = 1 for the correct X, if the gradient ∂L ∂Y 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∂L ∂Z ′ = LQ ′ and Z ′ = W X ′ + (b| . . . |b) for X ′⊤ = Q ′-1 R.To optimize λ, we initialize Q ′ with the result of the greedy algorithm in Spielman et al. [10] , and then greedily swap the pair of vectors q ′ i improving λ the most, while keeping the rank, until convergence.Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?Answer: [Yes] Justification: We provide code in the accompanying GitHub repository. Further, Sec. 3 we give all technical details needed to reimplement our algorithm. Finally, in Sec. 6 we explain in detail how our experiments were performed. 
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).Algorithm 1 SPEAR1: function SPEAR( m, n, W , b, ∂L ∂W , ∂L ∂b ) 2: L, R, b ← LOWRANKDECOMPOSE ( ∂L ∂W )3:for i = 1 to N do 4: Sample a submatrix L A ∈ R b-1×b of L 5: q ′ i ← ker(L A ) 6: if sparsity(Lq ′ i ) ≥ τ * m and q ′ i / ∈ C then 7: C ← C ∪ {q ′ i } 8: λ, X ′ ← GREEDYFILT (L, R, W , b, ∂L ∂b , C) 9:if λ = 1 then return X ′We formalize our gradient inversion attack SPEAR in Alg. 1 and outline it below. First, we compute the low-rank decomposition ∂L ∂W = LR of the weight gradient ∂L ∂W via reduced SVD, allowing us to recover the batch size b as the rank of ∂L ∂W (Line 2). We now sample (at most N ) submatrices L A of L and compute proposal directions q ′ i as their kernel ker(L A ) via SVD (Lines 4-5). We note that our implementation parallelizes both sampling and SVD computation (Lines 4-5) on a GPU. We then filter the proposal directions q ′ i based on their sparsity (Line 6), adding them to our candidate pool C if they haven'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 COMPUTESIGMA (Alg. 2) and GREEDYFILTER (Alg. 3) are shown in App. C.In this section, we will analyze SPEAR w.r.t. the number of submatrices we expect to sample until we have recovered all b correct directions q i (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 an analysis of the number of submatrices we have to sample until we have recovered all b correct directions q i with high probability, we point to Lemma B.2. Further, as before, we defer all proofs also to App. B. To determine the expected number of required samples until we have recovered the correct b direction vectors q i , we first compute a lower bound on the probability q of sampling a submatrix which satisfies the conditions of Theorem 3.3 for an arbitrary column i in Q and then use the coupon collector problem to compute the expected number of required samples.We can lower bound the probability of a submatrix A ∈ R b-1×b , randomly sampled as b -1 rows of ∂L ∂Z , having exactly one all-zero column and being full rank as follows:Lemma 5.1. Let A ∈ R b-1×b be submatrix of the gradient ∂L ∂Z obtained by sampling b -1 rows uniformly at random without replacement, where each element of ∂L ∂Z is distributed i.i.d. as∂L ∂Z j,k = ζ|ϵ| with ϵ ∼ N (µ = 0, σ 2 > 0) and ζ ∼ Bernoulli(p = 1 2). We then have the probability q of A having exactly one all-zero column and being full rank lower bounded by:q ≥ b 2 b-1 1 -( 1 2 + o b-1 (1)) b-1 ≥ b 2 b-1 (1 -0.939 b-1 ).We can now compute the expected number of submatrices n * total we have to draw until we have recovered all b correct direction vectors using the Coupon Collector Problem: Lemma 5.2. Assuming i.i.d. submatrices A following the distribution outlined in Lemma 5.1 and using Alg. 1, we have the expected number of submatrices n * total required to recover all b correct direction vectors as:n * total = 1 q b-1 k=0 b b -k = bH b q ≈ 1 q (b log(b) + γb + 1 2 ),where H b is the b th harmonic number and γ ≈ 0.57722 the Euler-Mascheroni constant.We validate this result experimentally in Fig. 4 where we observe excellent agreement for wide networks (m ≫ b) and obtain, e.g., n * total ≈ 1.8 × 10 5 for a batch size of b = 16.We now analyze the probability of SPEAR failing despite considering all possible submatrices of L and obtain: Lemma 5.3. Under the same assumptions as in Lemma 5.1, we have an upper bound on the failure probability p ub fail of Alg. 1 even when sampling exhaustively as:p ub fail ≤ b 1 - m k=b-1 m k 1 2 m 1 -0.939 (b-1)( k b-1 ) + 1 -(1 -p f r ) b ,where p f r is the probability of falsely rejecting a correct direction q q q ′ via our sparsity filter (Sec. 4.1).If we assume the full-rankness of submatrices A to i) occur with probability 1 - [11] ) and ii) be independent between submatrices, we instead obtain:( 1 2 -o b-1 (1)) b-1 for o b-1 (1) ≈ 0 (true for large bp approx fail ≈ 1 - m k=b-1 m k 1 2 m 1 -0.5 (b-1)( k b-1 ) b + 1 -(1 -p f r ) b .We illustrate this bound in Fig. 3 and empirically validate this bound in Fig. 8 and observe the true failure probability to lie between p approx fail and p ub fail . In this section, we empirically evaluate the effectiveness of SPEAR on MNIST [13] , CIFAR-10 [14], TINYIMA-GENET [15] , and IMAGENET [16] across a wide range of settings. In addition to the reconstruction quality metrics PSNR and LPIPS, commonly used to evaluate gradient inversion attacks, we report accuracy as the portion of batches for which we recovered the batch up to numerical errors and the number of sampled submatrices (number of iterations). 
empirical evaluation: 
 Experimental Setup For all experiments, we use our highly parallelized PyTorch [17] GPU implementation of SPEAR. Unless stated otherwise, we run all experiments on CIFAR-10 batches of size b = 20 using a 6 layer ReLU-activated FCNN with width m = 200 and set τ to achieve a false rejection rate of p f r ≤ 10 -5 . We supply ground truth labels to all methods except SPEAR.In Table 1 , we compare SPEAR against prior gradient inversion attacks from the image domain on the IMAGENET dataset rescaled to 256 × 256 resolution. In particular, we compare to Geiping et al.[1]1 , as 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 observe that while CI-Net obtains very good reconstructions with the Sigmoid network (PSNR of 38), SPEAR still achieves a much higher PSNR (124) as it is exact. Further, for the more common ReLU activations, 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 10× and 100× 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 a 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 6× faster. We evaluate SPEAR on MNIST, CIFAR-10, TINYIMAGENET and IMAGENET at two different resolutions, reporting results in Table 3 . Across datasets, SPEAR can reconstruct almost all batches perfectly, achieving PSNRs of 100 and above even at a batch size of b = 20 for images as large as 720 × 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. total increases exponentially with b, for both networks, the narrower network 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 independence assumptions are violated for the narrower network, explaining the larger number of required iterations. While we can recover all batches perfectly for the wider network, we see a sharp drop in accuracy from 99% at b = 20 to 63% at b = 24 (see Fig. 6 ) for the narrower network. This is due to increasingly more batches requiring more than the N = 2 × 10 9 submatrices we sample at most. We visualize the performance of SPEAR across different network widths and depths in Fig. 5 . We observe that while accuracy is independent of both (given sufficient width m ≫ b), the number of required iterations reduces with increasing width m. We provide further ablations on the effect of our two-stage filtering in App. E.3 and DPSGD noise in App. E.6.Our experiments so far focused on recovering inputs to the first layer of FCNNs. However, SPEAR's capabilities extend beyond this, as highlighted in Sec. 3.2. To demonstrate this, we use SPEAR to reconstruct the inputs to all FC layers followed by a ReLU activation in a 6-layer FCNN with a width of m = 400 at initialization. The results, presented in Table 4 , show that SPEAR successfully recovers the inputs to all layers almost perfectly. However, attacking later layers is more computationally expensive. Specifically, the runtime for l = 5 increases to 70 minutes/batch resulting in 17 batches that timed-out. This increased computational cost is 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 irrelevant. This issue is mitigated after a few training steps, as weights and biases adjust to better reflect the relationships between inputs and outputs. We find that after 5000 gradient steps the time per batch reduces to < 1 min at an accuracy of > 95% for layer l = 5. As we prove theoretically in Sec. 5.2 and verify practically in App. E.5, in the common regime where the batch size b 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 ).In this section, we propose a method for alleviating the exponential sampling complexity 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. 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 pre-activation values in Z are much more likely to correspond to negative pre-activation values in the true Z, and, thus, to 0s in gradients ∂L ∂Z , we record the locations of the 3b largest negative values for each column of Z. Importantly, by choosing the locations this way, we ensure that each group of 3b locations correspond to locations of likely 0s in same column of ∂L ∂Z . Restricting the sampling of the row indices of L A and A only within each group of locations, ensures that L A 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 demonstrates the combined approach allows a 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 q i correctly, suggesting that future work can further improve upon our results.Table 6 : Comparison between the reconstructions on VGG16 for Geiping et al. [1] , CPA [9] , and SPEAR for 10 IMAGENET batches (b = 16).LPIPS ↓ Feature Sim ↑ Geiping et al. [1] 0.562 -CPA [9] + FI + Geiping et al. [1] 0.388 0.939 SPEAR + FI + Geiping et al. [1] 0.362 0.984Following the Cocktail Party Attack (CPA) [9] , we experiment with using SPEAR to recover the input features to the first linear layer of a pretrained VGG16 convolutional network with size 25088 × 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. 
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-but-curious 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 b > 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 to 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 approximate reconstructions. In contrast, we derive an explicit low-rank representation and additionally leverage gradient sparsity reconstruct inputs exactly.Unlike a long line of prior work, we rely neither on any priors on the data distribution [8, 24, 25, 26] nor on a reconstructed classification label [1, 27, 7, 23, 8] . This allows our approach to be employed in a 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 on the client side, providing provable privacy guarantees at 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 as 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 ∂L ∂Z ) and dense dictionary (Q -1 ) approximately encoding a signal (L). In contrast, we do not search for the sparsest solution yielding an approximate reconstruction but a solution that exactly induces consistent X and ∂L ∂Z , 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] . While our ∂L ∂Z are not sparse enough, we still draw inspiration from Spielman et al. [10] in Sec. 4. 
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 or as aggregation layers of many other architectures. Extending our approach to other layers is an interesting direction for future work.Further, our approach scales exponentially with batch size b. While SPEAR's massive parallelizability and its ability to be combined with optimization-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 b > 1 elements to be recovered exactly in the honest-but-curious setting. We demonstrate theoretically and empirically that SPEAR succeeds with high probability and that our highly parallelized GPU implementation is effective across a 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-curious 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. 
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 to our attack in App. E.6Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.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 to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to 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 as 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 to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: 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, or scraped datasets)?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 a best faith effort.12. Licenses for existing assets • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to 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. 
 
 Appendix: In this work, we demonstrate that contrary to prior belief, an exact reconstruction of batches is possible in the honest-but-curious 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 a 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.Theorem 3.1. The network's gradient w.r.t. the weights W can be represented as the matrix product:EQUATIONProof. We will use Einstein notation for this proof:∂L ∂W j i = ∂L ∂Z l k ∂Z l k ∂W j i = ∂L ∂Z l k ∂(W m k X l m + b k δ l ) ∂W j i = ∂L ∂Z l k ∂W m k X l m ∂W j i = ∂L ∂Z l k ∂W m k ∂W j i X l m = ∂L ∂Z l k δ i k δ m j X l m = ∂L ∂Z l i X l j = ∂L ∂Z l i (X T ) l j .We note that δ i k is the Kronecker delta, that is δ i k = 1 if k = i and 0 otherwise. Further, δ l = 1 for all l. Hence we arrive at Eq. 1.Lemma B.1. Let b, n, m ∈ N such that b < n, m. Further, let A, L ∈ R m×b and B, R ∈ R b×n be matrices of maximal rank, satisfying AB = LR. Then there exists a unique disaggregation matrixQ ∈ GL b (R) s.t. A = LQ, and B = Q -1 R.Proof. As b ≤ n, m and the matrices A ∈ R m×b and B ∈ R b×n have full rank, we know that there exists• a left inverse A -L ∈ R b×m for A: A -L A = I b and • a right inverse B -R ∈ R n×b for B: BB -R = I b .A -L LRB -R = A -L ABB -R = I b , that (A -L L) -1 = RB -R . We now set Q = RB -R .This Q satisfies the required properties: Proof. We use again Einstein notation.• B = Q -1 R: Q -1 R = A -L LR = A -L AB = B, • A = LQ: LQ = LRB -R = ABB -R = A, • Uniqueness: Assume we have Q 1 and Q 2 that satisfy LQ 1 = LQ 2 = A. As L is of∂L ∂b i = ∂L ∂Z l k ∂Z l k ∂b i = ∂L ∂Z l k ∂(W m k X l m + b k δ l ) ∂b i = ∂L ∂Z l k ∂b k δ l ∂b i = ∂L ∂Z l k δ i k δ l = ∂L ∂Z l i δ l .This concludes the proof.Theorem 3.5. For any left inverse L -L of L, we have s1 . . .s b = Q -1 L -L ∂L ∂bProof. The proof is straight forward. Using Theorem 3.4 and Theorem 3.2, we know that ). We then have the probability q of A having exactly one all-zero column and being full rank lower bounded by:Q -1 L -L ∂L ∂b = Q -1 L -L ∂L ∂Z 1 . . . 1 = Q -1 L -L LQ 1 . . . 1 = Q -1 Q 1 . . . 1 = Q -1 Q diag(s 1 , . . . , s b ) 1 . . . 1 = s1 . . .q ≥ b 2 b-1 1 -( 1 2 + o b-1 (1)) b-1 ≥ b 2 b-1 (1 -0.939 b-1 ).Proof. We have the probability of one of the b columns being all zero as b 2 b-1 if the network has full rank, all other columns will not be all-zero. Further, we have the probability of the submatrix 1 A>0 being full rank conditioned on column i being all-zero as the probability of the matrix described by remaining b -1 columns being nonsingular. This probability is 1 - [11] where lim b→∞ o b-1 (1) = 0, which can be lower-bounded with 1 -0.939 b-1 [34] . We thus obtain their joint probability as their product.( 1 2 + o b-1 (1)) b-1Lemma 5.2. Assuming i.i.d. submatrices A following the distribution outlined in Lemma 5.1 and using Alg. 1, we have the expected number of submatrices n * total required to recover all b correct direction vectors as:n * total = 1 q b-1 k=0 b b -k = bH b q ≈ 1 q (b log(b) + γb + 1 2 ),where H b is the b th harmonic number and γ ≈ 0.57722 the Euler-Mascheroni constant.Proof. As we sample submatrices A uniformly at random with replacement, assuming them to be i.i.d. is well justified for the regime of m ≫ b. The the number n of submatrices drawn between correct direction vectors q i thus follows a Geometric distribution P[n = k] = q(1q) k-1 with success probability q with expectation n * = E[n] = 1 q . As we draw correct direction vectors q i uniformly at random from the b columns of Q, we have the probability of drawing a new direction vector q i as b-k b for k already drawn direction vectors. Again via the expectation of the Geometric distribution we obtain the expected number c * of correct direction vectors we have to draw until we have recovered all b distinct ones as the solution of the Coupon Collector Problemc * = b-1 k=0 b b-k = bH b ≈ b log(b) + γb + 1 2 .The proof concludes with the linearity of expectation.We now compute the number of samples n p total required to recover all b correct directions with high probability 1p. Lemma B.2. In the same setting as Lemma 5.2, we have an upper bound n p total 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 n p total p 2 ≤ Φ b log(2b/p * )n p total q n p total q(1q), where Φ is the cumulative distribution function of the standard normal distribution andp * = p -1 + (1 -p f r ) b .Proof. At a high level, bound the number of valid directions c p we need to discover until we recover all b distinct ones and then the number of submatrices n p total we need to sample to obtain these c p directions, each with probability 1 -p 2 , before applying the union bound. However, we first note that with probability 1 -(1p f r ) b we will (repeatedly) reject a correct 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 + (1p f r ) b , using the union bound.We now show how to compute the upper bound on the number of correct directions c p we need to find until we have found all b distinct directions. To this end, we bound the probability of not sampling the i th direction q i after finding c candidates asp ¬i = (1 -1 b ) c ≤ e -c b .We can then bound the probability of missing any of the b directions using the union bound as p ¬all ≤ b i=1 p ¬i = be -c p b . We thus obtain the minimum number c p of correct directions to find all b distinct ones with probability at least p * 2 as c p ≥ b log(2b/p * ). We can now compute the number n p total of samples required to find c p submatrices satisfying the condition of Theorem 3.3 for some i with probability 1-p 2 . To this end, we approximate the Binomial distribution B(n, q) with the normal distribution N (nq, nq(1q)) [35] , which is generally precise if min(nq, n(q -1)) > 9 [36] , which holds for b ≥ 5. We thus obtain the number of samples n p total required to find c p valid directions with high probability 1 -p * 2 by solving p * 2 = Φ( c p -n p total q √ n p total q(1-q)) for n p total which boils down to a quadratic equation. 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 b = 10 and p = 10 -8 , we, e.g., obtain n ≈ 4 × 10 4 . Lemma 5.3. Under the same assumptions as in Lemma 5.1, we have an upper bound on the failure probability p ub fail of Alg. 1 even when sampling exhaustively as:p ub fail ≤ b 1 - m k=b-1 m k 1 2 m 1 -0.939 (b-1)( k b-1 ) + 1 -(1 -p f r ) b ,where p f r is the probability of falsely rejecting a correct direction q q q ′ via our sparsity filter (Sec. 4.1).Proof. We will first compute the probability of ∂L ∂Z not containing a submatrix A satisfying the conditions of Theorem 3.3 for all i ∈ {1, . . . , b} and then the probability of us failing to discover it despite exhaustive sampling.We observe that the number k of rows in ∂L ∂Z with a zero i th entry is binomially distributed with success probability 1 2 . For each k ≥ b -1, we can construct k b-1 submatrices A with an all-zero i th column. The probability of any such submatrix having full rank is 1 -( 1 2 -o b-1 (1)) b-1 > 1 -0.939 b-1 [11, 34].We thus have the probability of ∂L ∂Z containing at least one submatrix A with full rank and an all-zero i th column asm k=b-1 m k 1 2 m 1 -0.939 (b-1)( k b-1 ) .Using the union bound, we thus obtain an upper bound on the probability of ∂L ∂Z not containing any submatrix A with full rank and an all-zero i th column for all i ∈ {1, . . . , b}.To compute the probability of us failing to discover an existing submatrix despite exhaustive sampling, we first note that we have the probability p f r of an arbitrary column in ∂L ∂Z being less sparse than our threshold τ . Thus, with probability 1 -(1p f r ) b we will discard at least one correct direction due to it inducing an unusually dense column in ∂L ∂Z . We now obtain the overall failure probability via the union bound.Here, we present the Algorithms COMPUTELAMBDA and GREEDYFILTER referenced in Sec. 5.1.Algorithm 2 COMPUTELAMBDA 1: function COMPUTELAMBDA(L, R, W , b, ∂L ∂b , B) 2: Q ← FIXSCALE (B, L, ∂L ∂b ) 3: ∂L ∂Z ← L • Q 4: X T ← Q -1 • R 5: Z = W • X + (b| . . . |b) 6: λ -← i,j 1[Z i,j ≤ 0] • 1[ ∂L ∂Zi,j = 0] 7: λ + ← i,j 1[Z i,j > 0] • 1[ ∂L ∂Zi,j ̸ = 0] 8: λ ← λ-+λ+ m•b 9: return λ Algorithm 3 GREEDYFILT 1: function GREEDYFILTER(L, R, W , b, ∂L ∂b , C) 2: B ← {} 3:while rank of B is B do 4:Select the sparsest vector q ′ i from C \ B 5:B ← B ∪ {q ′ i } 6:if B is not of full rank then 7:B ← B \ {q ′ i } 8:end if9:end while 10: 11:λ ← COMPUTELAMBDA (L, R, W , b, ∂L ∂b , B) 12:while not changed do 13:changed ← False 14:for(q ′ i , q ′ j ) in B × (C \ B) do 15: B ′ ← B \ {q ′ i } ∪ {q ′ j } 16: λ ′ ← COMPUTELAMBDA (L, R, W , b, ∂L ∂b , B ′ ) 17:if λ ′ > λ then end for 23:end whileQ ← FIXSCALE (B, L, ∂L ∂b )25:X T ← Q -1 • R 26:return λ, X In this work, we use the commonly used MNIST [13] , CIFAR-10 [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.In this section, we provide the results from our main experiment in Table 3 , alongside 95% confidence intervals.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 8 for the TinyImageNet dataset show another advantage of our algorithm, namely, SPEAR works regardless of the label distribution, providing even better reconstruction results compared to Table 3 for single-label batches. In this section, we 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. In this section, we demonstrate how training effects SPEAR's performance. To this end, we train a network on MNIST and evaluate SPEAR periodically during training both on the train and test datasets, visualizing results in Fig. 7 . We observe that SPEAR performance is very similar between the two datasets we evaluate on. Further, we see that SPEAR performs very well on trained networks, with the number of required steps by the algorithm being even lower those those on untrained networks. However, if the minimum column sparsity of ∂L ∂Z drops significantly, as is the case for the checkpoints around 1000 training steps in the illustrated run. SPEAR's performance drops slightly.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 m b-1 submatrices of L we only consider small batch sizes b ≤ 10 and networks m ≤ 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 performance. 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 σ ≤ 1.0×10 -4 and gradient clipping that constrains the ℓ 2 norm of the composite gradient vector, combining the gradients of all layers, to a maximum value of C ∈ [1, 2] . We chose the maximum value σ to be close to median gradient magnitude of the first linear layer which in our experiments was also ≈ 1.0×10 -4 . We chose the range for C 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. 1 to account for the noise added to the sparse entries of ∂L ∂Z . To account for the imperfect reconstructions in this setting, we also perform our early stopping (Line 9 in Alg. 1) when the sparsity matching coefficient γ reaches a lower value than 1. Further, we sample matrices L A of larger size (b + 1 × b) to increase the numerical stability of our solutions under noise. While sampling larger L A is more computationally expensive, as b + 1 instead of b -1 entries in A are required to be correctly sampled as 0, the resulting directions q i are more numerically stable as they are obtained as a solution of an overdetermined system of linear equations. Note that if A is assumed to be of rank b -1, Theorem 3.3 remains valid for these larger matrices L A . Finally, due to our looser sparsity filtering described above we encounter more incorrect directions q i . We tackle this issue by only keeping q i that correspond to matrices L A of rank exactly b -1. Under our assumption in Theorem 3.3, those are exactly the vectors q i that correspond to A of the correct rank b -1. Note that we apply these changes only for σ > 0.Invariance to Gradient Clipping In Table 9 , we observe that the quality of our reconstructions is not affected by the clipping constant C. This is 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:∂ L ∂W = b i=1 c i ∂L ∂W i = b i=1 c i ∂L ∂Z i X i ,where c i ∈ R are the unknown to the attacker factors applied by the clipping procedure to each individual input gradient ∂L ∂Wi . One can adapt the proof to Theorem for the clipped gradient w.r.t. b. The formula follows from the observation that in our setting the same clipping factor c i is applied to the gradients of each layer, including ∂L ∂b i and ∂L ∂Wi . By applying the rest of the theoretical results of the paper without change but on clipped gradients ∂ L ∂Z , instead of the original unclipped gradients ∂L ∂Z , we conclude that SPEAR is 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 i .Robustness to Noise From Table 9 , we observe that SPEAR is very robust to noise. We emphasize in particular that even when noise of similar size to the size of the gradients in expectation is applied, we still obtain a reconstruction with PSNR > 28. This is similar to the PSNR of 29.3 that Geiping et al. [1] achieves *without any noise* which is 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 be significantly impeded.In this section, we 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 E, local client learning rates η, and, even works, when mini-batches of size b mini 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. b mini = b, the client computes and subsequently shares with the server the following updated linear layer weights:W E = W 0 -η E e=1 ∂L ∂W e = W 0 -η E e=1 ∂L ∂Z e • X T = W 0 -η E e=1 ∂L ∂Z e • X T ,where W 0 is the global model sent by the server, W e represent the local client weights after e client epochs, and ∂L ∂W e and ∂L ∂Z e are the weight and output gradients at epoch e. We empirically observe that sparsity patterns of the different local gradients ∂L ∂Z e are usually similar. This is expected as these patterns correspond to the ReLU activation patterns for the layer outputs Z e (see Sec. 3.2) at different local steps which are computed on the same data X and with similar weights W e . As the sparsity patterns for the individual gradients are similar, their sum E e=1 ∂L ∂Z e also shares this sparsity pattern and is, thus, also sparse. As the server knows W 0 and it can subtract it from the client's shared weights W E and apply Theorem 3.3, as before, on the sparse matrix E e=1 ∂L ∂Z e to obtain the corresponding matrix Q and client data X. We note that while our sparsity matching coefficient σ will typically not reach 1 for the final reconstruction in this setting, as there is some mismatch between the sparsity patterns of the different output gradients ∂L ∂Z e , we have found that SPEAR remains practically effective regardless. We note that SPEAR can be even be generalized to FedAvg protocols that use random mini-batches X e of size b mini < b sampled from X at each local step. This is the case, as each local client gradient ∂L ∂W e = ∂L ∂Z e (X e ) T , can be represented as ∂L ∂Z e X T , where ∂L ∂Z e is derived from ∂L ∂Z e by adding 0 columns at batch positions corresponding to batch elements not in X e . Importantly, as ∂L ∂Z e only adds 0 columns to ∂L ∂Z e , the sparsity of ∂L ∂Z e can only increase, allowing to conclude thatE e=1 ∂L ∂Z eremains sparse, and, thus, Theorem 3.3 can still be applied to it.Experiments with FedAvg Updates Next, we show empirically the effectiveness of SPEAR for FedAvg updates. In Table 10 , we show the results of attacking clients with b = 20 datapoints from the TINYIMAGENET dataset for different number of local client epochs E. We observe that even for E = 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 ∂L ∂Z e compared to others, resulting in their sum being much less sparse. Further, Table 10 11 . We observe that even for large learning rates SPEAR still recovers its inputs well, showing that while the individual weights W e can change a lot, their induced sparsity on ∂L ∂Z e remains consistent.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 et al. [1] on the TINYIMAGENET batch first shown in Fig. 1 . In Fig. 9 we operate in the same setting as Table 8 , namely batches of only a single class. We observe that while some images are reconstructed well by Geiping et al. [1] , most of the images are of poor visual quality, with some even being hard to recognize. In contrast, all of our reconstructions are pixel perfect. This in particular also means, that SPEAR's reconstructions improve in fine-detail recovery even upon the well recovered images of Geiping et al. [1] . This is expected as our attack is exact (up numerical errors).Further, to show the results in Fig. 9 are representative, in Fig. 10 -12 we provide additional visualizations of the reconstructions obtained by SPEAR corresponding to the 10 th ,50 th , and 90 th percentiles of the PSNRs obtained in the TINYIMAGENET experiment reported in Table 3 . We observe that only 1 sample has visual artefacts for the 10 th percentile batch (top left image in Fig. 10 ) and that the 50 th and 90 th percentile batches contain only perfect reconstructions. We theoreticize that the visual artefact in Fig. 10 is a result of a numerical instability issue and that using L A 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 q i from the batch gradient. In Fig. 13 , we show the only such batch for the TINYIMAGENET experiment reported in Table 3 . The batch has 2 wrong directions and 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 2 images are affected by the failure.Exact Reconstruction (SPEAR -ours)Exact Reconstruction (SPEAR -ours)Original ImageFigure 10 : Visualisation of the images reconstructed by SPEAR from the batch whose PSNR is at the 10 th percentile based on the set of 100 TINYIMAGENET reconstructions reported in Table 3 . 3 . 3 . 3 , where not all recovered directions q ′ i are correct. SPEAR recovered 2/20 wrong directions, resulting in the left most images being wrongly recovered.• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly 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 be 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 are not attained by the paper.• The answer NA means that the paper does not include experiments.• If the paper includes experiments, a No answer to 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 to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be accomplished in various ways.For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it 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 one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example 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 NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).We use so-called "modern" version of the attack from https://github.com/JonasGeiping/breaching 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 1. The theoretical analysis only considers the ReLu and fully connected layer.
2. The method only seems to be effective for a small batch size, even though it has already been a big progress.
questions: 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: limitations: See weakness.
paper_summary: paper_summary: This paper introduces a novel approach to input reconstruction for neural networks, focusing specifically on linear layers followed by ReLU activations. 
The key aspects of this method are:

Low-rank decomposition: The authors leverage low-rank matrix decomposition techniques to simplify the representation of the linear layer's weight matrix.

ReLU 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.

Efficient 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.

Input 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.
strength_weakness: strength_weakness: 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. 

Interesting idea but miss some experiments and discussion: 

1. 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

2. 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?

If the result is limited to the first fc layer, then it has some interesting innovation in method design but is not really practical. 

Also, if authors can provide more no cherry-picking visualization results on different fc layers or fc after conv for different datasets in the appendix,?

For 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.

[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.
questions: questions: See above.
limitations: limitations: See above.
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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.

- 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.
questions: questions: - When the batch size increases, is there a trade-off scheme that sacrifices the fidelity of recovered images but reduces the running time?

- Can the algorithm deal with normalization layers?

- Can the algorithm be adapted to convolutional networks and (vision) transformers?
limitations: limitations: The paper discussed limitations.
paper_summary: paper_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.
strength_weakness: strength_weakness: Please refer to the Questions part.
Minor problem: It is recommended that the work should be double-checked in case of typos or compiling errors.
- Line 79 typo
- Line 125 typo
- Line 149 abnormal block
questions: 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.
- For experiments in 6.2, are the image labels known for the reconstruction ahead of time? 
- 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: limitations: The proposed method only works for FCNs.

Comments: comment: We deeply appreciate the reviewer’s effort in reviewing our paper and code. We are thankful for their insightful questions, the 
answers of which we will incorporate into the next revision of our paper. Below we respond to their additional questions above:

**Q1:  For VGG-16, what is the shape of the attacked linear layer?**

We use the standard ImageNet VGG-16 from torchvision, which uses AdaptiveAvgPool2d(7, 7), resulting in 25088 input features for the attacked linear layer. The attacked linear layer has 4096 output neurons. We will clarify this.

**Q2: Computing $Q_\text{opt}$ in the main file of the attack is confusing**

We agree with the reviewer that computing $Q_\text{opt}$, as one of the first things we do in our main can give the wrong impression we use the ground truth $Q$ in our reconstruction. We emphasize this is **not the case** as the reviewer correctly noticed, and we apologize for the confusion this has caused. We compute $Q_\text{opt}$ so that our sampling function *getQBarUniqueCol*, based on Theorem 3.3, in sparse\_gradient\_reconstruction.py can display how many directions were recovered correctly in real-time. This is incredibly valuable for debugging and monitoring the progress of our method. $Q_\text{opt}$ is also used to report the success of the different filtering stages of SPEAR described in Section 4 of the paper. This is done in the function *summarizeQ* in sparse\_gradient\_reconstruction.py, and it is useful for both debugging and for creating Figure 6 in Appendix E.3. We reiterate that $Q_\text{opt}$ is not used for any other purpose in our code. Before making our code public, we will do our best to restructure the code such that $Q_\text{opt}$ is only used at the end of the reconstruction for evaluation to avoid confusion.
I did run the code provided by the author again, and the reconstruction results are fantastic. I am willing to raise my score since the authors addressed all the questions I asked. I believe this method is ground-breaking for gradient inversion attacks in general.  Other recent works tend to use diffusion/GAN to enhance their reconstruction results, but this work perfectly reconstructs the linear layer's result and demonstrates the possible vulnerability of LL in many NN architectures. 


 I just had a few detailed questions regarding implementation:

1. For VGG-16, are you running at linear shape = 1 1 4096 layer?
2. for implementation part, could you put Q_opt sperate only for extra evaluation function? I was confused and first thought you directly used GT in the reconstruction process.