SPEAR++: Scaling Gradient Inversion via Sparsely-Used Dictionary Learning

AI summary

Authors: Alexander Bakarsky (ETH Zurich), Dimitar I. Dimitrov (INSAIT, Sofia University "St. Kliment Ohridski"), Maximilian Baader (ETH Zurich), Martin Vechev (ETH Zurich, INSAIT) arXiv: 2510.24200v1 [cs.LG], 28 Oct 2025

Overview

Research area: Privacy and security of Federated Learning, specifically gradient inversion attacks (GIAs) on neural network gradients, combined with sparse dictionary learning from signal processing and computer science.

Technical level: Advanced. The paper builds directly on a line of theoretical results about gradient decompositions, assumes familiarity with SVD, Riemannian optimization on the hypersphere, and sparse dictionary learning, and its core argument rests on matrix-rank and kernel arguments.

One-sentence scope: The paper replaces the exponential-in-batch-size search procedure of the SPEAR attack with sparse dictionary learning techniques, yielding a scalable exact gradient inversion attack, SPEAR++, that reconstructs client data from much larger batches while preserving robustness to differential privacy noise and FedAvg aggregation.

What This Paper Is About

Federated learning lets clients train a shared model without sending their raw data, but gradient inversion attacks show that a curious server can sometimes reconstruct private client data from the gradients clients send back. The prior SPEAR attack (Dimitrov et al.) gave exact reconstruction on linear layers with ReLU activations, but its runtime grows exponentially with the client batch size b, making it impractical beyond tiny batches such as b = 24. SPEAR++ reframes the recovery of the hidden disaggregation matrix as a sparsely-used dictionary learning problem, which admits efficient non-convex optimization, and thereby scales the attack to batches roughly an order of magnitude larger.

Key Contributions

1. Explicit connection between dictionary learning and gradient inversion. The authors formalize the recovery of the disaggregation matrix Q as a dictionary learning problem, where the ReLU-induced sparsity of the activation gradient ∂L/∂Z plays the role of the sparse coefficient matrix and Q⁻¹ acts as the complete dictionary.

2. Substitution of SPEAR's exponential sampling with first-order optimization. Instead of sampling random submatrices of L until the assumptions of SPEAR's Theorem 3.3 hold, SPEAR++ optimizes over the ℓ₂ hypersphere using convex surrogates of the ℓ₀ norm (notably ℓ₁), with a sampling-based rounding step for smooth surrogates.

3. Extensive experimental evaluation of dictionary recovery variants. The paper compares surrogate losses (ℓ₁, LogCosh h_μ, and −ℓ₄) and optimizers (Riemannian Adam versus projected gradient descent) across batch sizes b from 15 to 210 and network widths m of 200, 1000, and 4000.

4. Demonstrated robustness under defenses. Experiments on differentially private (DP-SGD) gradients with clipping C and noise σ, and on FedAvg updates with varying numbers of local epochs E and mini-batch sizes b_mini, show comparable robustness to SPEAR while supporting much larger batches.

Main Findings

• Better scaling, polynomial in b. The authors report a polynomial runtime relationship in the batch size b for SPEAR++, in contrast to the exponential relationship reported in SPEAR. They note that SPEAR's runtime for b = 24 is already prohibitively long (referring to Figure 4 in Dimitrov et al.).

• ℓ₁ is the strongest surrogate overall. In Table 1, the ℓ₁ loss with no rounding reached PSNR 124.24 and 100% accuracy at b = 100, m = 4000; PSNR 120.86 and 100% accuracy at b = 150, m = 4000; and PSNR 45.34 with 7% accuracy at b = 210, m = 4000. LogCosh h_μ was competitive at smaller widths (PSNR 121.50, 98% accuracy at b = 20, m = 200) but collapsed at larger batches (e.g., PSNR 13.80, 0% accuracy at b = 210, m = 4000). The −ℓ₄ loss performed worst, reaching only PSNR 14.29 and 0% accuracy at b = 20, m = 200, so the authors did not pursue it further.

• Riemannian Adam generally beats projected gradient descent. In Table 2, RAdam reached PSNR 120.98 with 95% accuracy at b = 20, m = 200 versus PGD's PSNR 41.53 and 25% accuracy, and PSNR 125.18 with 100% accuracy at b = 65, m = 1000 versus PGD's PSNR 93.91 and 93%. The one exception is the b = 210, m = 4000 setting, where PGD achieved PSNR 88.36 with 77% accuracy while RAdam achieved PSNR 45.34 with 7% accuracy. The authors attribute this to the number of initializations and flag it as future work.

• An empirical upper bound on batch size per width. For each network width m, the authors observe a batch size beyond which reconstruction starts failing, and the ratio between that upper bound and m slowly decreases as m grows, suggesting a slightly worse than linear relationship. They note this is consistent with recent theoretical analysis of sparse dictionary learning.

• Competitive with prior-informed methods. The authors state that at b = 100, SPEAR++ produces similar recovery rates to the SPEAR+Geiping combination — which relies on image priors — while operating at half the network width (referring to Table 5 in Dimitrov et al.).

• Robustness to DP-SGD noise. In Table 3, with clipping C = 2 and noise σ = 1e-4 at b = 20, m = 200, SPEAR++ reached PSNR 31.90 with 75% accuracy; with σ = 1e-6 at b = 150, m = 4000 it reached PSNR 55.45 with 88% accuracy. The authors note the noise level for b = 20 is similar to the median of the absolute value of gradient entries, and that the median of gradients of a 4000-neuron-wide network is on the order of 1e-5.

• Robustness to FedAvg aggregation. In Table 4, with learning rate 1e-2, E = 3 local epochs and b_mini = 5 at b = 20, m = 200, the attack reached PSNR 67.81 with 75% accuracy; with E = 15 and b_mini = 30 at b = 150, m = 4000 it reached PSNR 63.71 with 92% accuracy. The authors state SPEAR's theoretical analysis and FedAvg extension remain valid for SPEAR++.

• Visual reconstruction quality at b = 210. Figure 1 shows all car images from a successfully reconstructed batch of size b = 210 from CIFAR-10 with network width m = 4000 using ℓ₁ loss and RAdam, which the authors describe as indistinguishable from the originals by humans.

Methodology in Plain English

The attacker knows the parameters W and b of a linear layer followed by ReLU, and observes the gradients ∂L/∂W and ∂L/∂b that a client sent. Prior theory says ∂L/∂W equals the unknown activation gradient ∂L/∂Z times the transposed input matrix Xᵀ. Because ReLU zeroes out roughly half of the entries of ∂L/∂Z, the input can in principle be recovered exactly by finding the right "disaggregation" matrix Q that lines up an SVD-based decomposition of the observed gradient with that sparse structure.

SPEAR found Q by repeatedly sampling submatrices of the left factor and computing their kernels — a procedure whose cost explodes with the batch size b. SPEAR++ instead treats the left factor L as a dictionary times a sparse coefficient matrix, and searches for individual columns of Q by minimizing a convex surrogate of the ℓ₀ norm over the unit sphere. Columns are found by running many random initializations through either Riemannian Adam (via the Geoopt package) or projected gradient descent, keeping candidates that are sparse enough and not already in the pool.

Two practical issues are handled explicitly. First, when the number of data samples m is not much larger than b, spurious local minima appear; the authors apply SPEAR's two-stage filtering, greedily swapping columns of a candidate matrix Q̄ to maximize the sparsity matching coefficient λ, and rescaling columns using the bias gradient. Second, smooth surrogates like LogCosh or −ℓ₄ have local minima that differ from those of ℓ₀, so the authors devise a scalable "rounding via sampling" procedure: compute y = Lq̂, pick the r indices of y closest to zero in absolute value, randomly sample b of them to form a submatrix L_A, and if its kernel is one-dimensional, take that direction as the exact sparse solution. The ℓ₁ loss needs no rounding because its local minima coincide with those of ℓ₀.

If the algorithm cannot find enough linearly independent candidates, it augments its basis with an orthonormal basis of the complement, enabling partial reconstruction rather than outright failure.

Why This Matters

The paper argues that exact, domain-agnostic gradient inversion on ReLU-activated linear layers is not merely a theoretical curiosity: by removing SPEAR's exponential dependence on batch size, it makes realistic batch sizes attackable. The experiments use batches of up to b = 210 on CIFAR-10 with a 4000-neuron-wide first layer, and the attack still partially succeeds under DP-SGD noise and under FedAvg aggregation with 15 local epochs. This shifts the practical risk assessment of federated deployments and reduces the need for per-deployment empirical testing, since the attack rests on a formal analysis rather than pure data optimization.

Real-world applications affected:

• Federated learning deployments in regulated sectors, where the paper cites data-sharing policies and regulations such as the GDPR and the CCPA as motivation for federated training in the first place.
• Medical or institutional settings where clients hold sensitive records and rely on federated training to avoid centralizing data.
• Any deployment that exchanges gradients or model updates with a coordinating server that could behave as an honest-but-curious adversary.
• Systems that apply DP-SGD noise or FedAvg aggregation as privacy defenses, since the paper tests exactly those defenses.

Industry relevance: The results suggest that defenses such as DP noise and local aggregation steps do not by themselves prevent exact or near-exact reconstruction, so federated learning operators must consider the batch size and layer width of their updates as part of their privacy budget, and may need defenses beyond noise and aggregation.

Future Directions

• Understanding the optimizer crossover at large batches. The authors explicitly leave as future work the investigation of why PGD outperformed Riemannian Adam at b = 210, m = 4000, and hypothesize that RAdam would match or exceed PGD with more initializations for both algorithms.
• Theoretical characterization of the batch-size limit. The observed empirical upper bound on b for each m, and its slightly worse than linear relationship to m, is connected to recent theoretical analysis of sparse dictionary learning but is not derived by the authors.
• Extending beyond the first layer. The attack recovers either client data (if the linear layer is first) or intermediate features; the authors point to using those features with an approximate attack, as described in Section 6.4 of Dimitrov et al., leaving the practical pipeline for deeper layers open.
• Broadening defenses tested. Only DP-SGD noise (with clipping C = 2 and two noise levels) and FedAvg aggregation were evaluated; other defenses and larger or differently distributed noise remain untested, and partial reconstruction when the candidate rank is insufficient is described as a fallback rather than a solved case.

Target Audience

Researchers and practitioners working on federated learning privacy, gradient leakage, and trustworthy machine learning, particularly those with a background in linear algebra, optimization, or sparse coding. Security engineers assessing the risk of specific federated deployments, and theoretically inclined readers interested in dictionary learning's application to inverse problems, will also find it valuable. Readers seeking a non-technical introduction to gradient inversion should start with the prior SPEAR paper and survey work rather than this one.

Authors’ abstract

Federated Learning has seen an increased deployment in real-world scenarios recently, as it enables the distributed training of machine learning models without explicit data sharing between individual clients. Yet, the introduction of the so-called gradient inversion attacks has fundamentally challenged its privacy-preserving properties. Unfortunately, as these attacks mostly rely on direct data optimization without any formal guarantees, the vulnerability of real-world systems remains in dispute and requires tedious testing for each new federated deployment. To overcome these issues, recently the SPEAR attack was introduced, which is based on a theoretical analysis of the gradients of linear layers with ReLU activations. While SPEAR is an important theoretical breakthrough, the attack's practicality was severely limited by its exponential runtime in the batch size b. In this work, we fill this gap by applying State-of-the-Art techniques from Sparsely-Used Dictionary Learning to make the problem of gradient inversion on linear layers with ReLU activations tractable. Our experiments demonstrate that our new attack, SPEAR++, retains all desirable properties of SPEAR, such as robustness to DP noise and FedAvg aggregation, while being applicable to 10x bigger batch sizes.