Priced to Leak: Value–Inversion Coupling in Federated Data Valuation

Data valuation asks a simple economic question — which training samples, or which federated clients, actually improved the model? — but answering it exactly is computationally hopeless: the gold-standard Shapley value requires averaging a sample's marginal contribution over all $2^N$ subsets of the dataset, which is NP-hard and needs an exponential number of model retrainings (Scalability vs. Utility). The only practical escape in federated learning is to value the gradient updates themselves: the Federated Shapley Value (FSV) treats each round's client update as a player's move in a small cooperative game, cutting the cost to $O(\log^2 m)$ per round for $m$ clients with no extra communication (A Principled Approach to Data Valuation for Federated Learning). But the updates a valuation server must inspect are precisely the object that gradient-inversion attacks reconstruct: analytical attacks now recover batches of images pixel-perfectly from shared gradients, up to 210 CIFAR-10 images at once (SPEAR: Exact Gradient Inversion of Batches in Federated Learning, SPEAR++: Scaling Gradient Inversion via Sparsely-Used Dictionary Learning).

This proposal claims these two facts are not in tension by accident. The signal that makes a client's update valuable and the structure that makes it recoverable are, in ReLU networks, the same low-rank spectral object. If that is true, then any efficient server-side valuation that ranks contributions from raw updates is leaking by construction — and the interesting research question is not "how do we value data privately" but "where exactly on the value–leakage frontier can a mechanism sit." We propose to prove the coupling for tractable architectures, audit it empirically against exact attacks, and then build a projection-based valuation that exploits an asymmetry we expect in the frontier: contribution rankings survive aggressive degradation of the update spectrum, while exact inversion does not.

Core Claim

For a fully connected layer with ReLU activations, the gradient contribution of sample $i$ is a rank-one matrix $a_i \delta_i^\top$, where $a_i$ is the (roughly 50% sparse) vector of incoming activations and $\delta_i$ the backpropagated error vector; a batch of $b$ samples produces $G = A\Delta^\top = \sum_i a_i \delta_i^\top$. This is exactly the object SPEAR decomposes by singular value decomposition and ReLU-sparsity matching to isolate individual samples (SPEAR: Exact Gradient Inversion of Batches in Federated Learning), and inversion succeeds when the rank-one terms have large norms and near-orthogonal supports — the "low entanglement" condition identified by Concealing Sensitive Samples against Gradient Leakage in Federated Learning. Meanwhile, the per-round marginal value FSV assigns to client $i$'s update, for a smooth validation utility $u$ and learning rate $\eta$, is approximately

$$\phi_i^{(t)} \;=\; u\big(W^{(t)} + \eta \nabla W_i^{(t)}\big) - u\big(W^{(t)}\big) \;\approx\; \eta \big\langle \nabla W_i^{(t)},\, \nabla u(W^{(t)}) \big\rangle,$$

a linear functional of the same update. Both quantities grow with the magnitude of $a_i \delta_i^\top$; the "early bird" effect FSV documents — early-round updates showing inflated marginal utility (A Principled Approach to Data Valuation for Federated Learning) — should therefore coincide with the rounds where gradients are largest and inversion is easiest. Our claim has two parts. First, a positive coupling result: high marginal contribution predicts high exact-inversion success, because value and recoverability are both monotone in the dominant singular structure of the same rank-one terms. Second, an asymmetry result: the value signal is a low-dimensional alignment statistic that survives random subspace projection of the update, while SPEAR-class attacks need the full spectral and sparsity structure, which projection destroys. That asymmetry, if it holds, defines a favorable operating point for federated valuation.

The closest existing work must be distinguished carefully. Understanding Data Importance in Machine Learning Attacks: Does Valuable Data Pose Greater Harm? showed that high-Shapley samples are more vulnerable to membership inference, model stealing, and backdoors, but explicitly found global reconstruction attacks insensitive to sample importance — their open problem. We differ in two ways: they valued data with KNN-Shapley proxies on static embeddings, not per-round gradient valuations, and they tested generic model-level inversion, not exact per-sample batch inversion of the sort SPEAR performs. Our audit directly tests whether exact analytical attacks overturn their negative reconstruction finding, and our theory explains why the attack class matters. Leveraging gradient-derived metrics for data selection and valuation in differentially private training showed which valuation metrics survive DP noise but never evaluated inversion risk, leaving open whether their high-VoG outliers have distinctive reconstruction profiles — we test exactly that and use it as a second value axis. Understanding Deep Gradient Leakage via Inversion Influence Functions supplies the analytical tool we reuse: its $I^2F$ risk metric, built on a maximum-eigenvalue lower bound and computable over 500× faster than running an attack, becomes our cheap per-sample leakage covariate for measuring coupling at scale.

Research Program

The first workstream is theoretical. Within the linear-utility, single-layer ReLU setting where both FSV's per-round game and SPEAR's algebra are exactly solvable, we will derive a coupling inequality: a lower bound on $\phi_i^{(t)}$ in terms of the singular values of $a_i \delta_i^\top$, combined with the $I^2F$-style eigenvalue lower bound on reconstruction fidelity, so that both value and invertibility are bounded below by the same functional. The honest caveat is that these are correlated lower bounds, not equivalent quantities — value depends on alignment with the validation gradient direction, inversion on within-batch orthogonality — so the coupling is statistical, and the theory should yield a quantitative correlation prediction rather than an identity. We will also check the theory's temporal prediction: coupling strength should peak in early training rounds, where the early-bird effect and large gradient norms coincide.

The second workstream is the empirical audit. We stratify CIFAR-10 and MNIST training data by two independent value axes — KNN-Shapley computed on frozen pretrained embeddings, whose anomaly-detection signals transfer to deep models (Efficient Task-Specific Data Valuation for Nearest Neighbor Algorithms, Scalability vs. Utility), and Variance of Gradients, which survives DP noise where gradient norms do not (Leveraging gradient-derived metrics for data selection and valuation in differentially private training) — then run SPEAR, SPEAR++, and $I^2F$ on batches drawn from matched high- versus low-value strata. The measurable prediction is that exact-recovery rate and $I^2F$ risk are ranked by value stratum, most strongly in early rounds. A secondary check replicates the "privacy onion" dynamic of Understanding Data Importance in Machine Learning Attacks under exact attacks: after removing the top-value stratum, inversion vulnerability should migrate to the newly-promoted samples.

The third workstream is the mechanism and the frontier. Instead of the server seeing raw $\nabla W_i$ (as FSV requires) or nothing at all (as secure aggregation enforces), clients transmit updates projected onto a shared random $r$-dimensional subspace before optional Gaussian noise — building on the observation of Memory-Efficient Differentially Private Training with Gradient Random Projection that projection before DP preserves training utility and flattens the gradient's singular spectrum. The server runs per-round Shapley on the projected updates at FSV's existing complexity. The deliverable is a measured frontier: Spearman correlation of projected-update valuations against ground-truth FSV rankings, plotted against exact-recovery rate of SPEAR++ on projected updates, swept over $r$ and noise scale $\sigma$. The hypothesis is asymmetric degradation — rankings remain faithful at projection dimensions where dictionary-learning inversion collapses. If instead both collapse together, that is the impossibility-side result: efficient valuation from updates is inseparable from leakage, and the field should route around gradients entirely.

Baselines

The do-nothing reference is raw FSV: the server inspects unmodified per-client updates and computes per-round Shapley values exactly as in A Principled Approach to Data Valuation for Federated Learning. By construction this achieves perfect ranking fidelity (it defines the ground truth) and maximal leakage, so it anchors both axes of the frontier; a random-ranking valuation anchors the utility floor. The strongest existing competitor is isotropic differential privacy with VoG-based valuation: Leveraging gradient-derived metrics for data selection and valuation in differentially private training reports that VoG selection achieved SSIM = 1.0 between $\epsilon = 1$ and $\epsilon = 8$ on CIFAR-10 while standard gradient-norm rankings dropped to 0.355 — the best documented evidence that any valuation signal survives DP noise. We will run DP-SGD/DP-Adam plus VoG in our identical federated simulation, with the same client count, rounds, compute, and an equal tuning budget over clipping bound and $\sigma$, and evaluate both its ranking fidelity (Spearman $\rho$ against noise-free FSV) and its leakage (SPEAR++ recovery on the noised updates — relevant because Bordetsky et al. report SPEAR-class attacks resist standard clipping and low noise (SPEAR)). We beat this baseline if at matched ranking fidelity our projected valuation yields strictly lower exact-recovery rate, or at matched recovery rate strictly higher fidelity. The key ablation replaces the random subspace projection with isotropic Gaussian perturbation matched in effective information removed (same effective dimension, same DP $\epsilon$ where applicable): this isolates whether the favorable frontier point comes from the spectral structure of the degradation — destroying dominant singular directions and sparsity patterns — or merely from any noise at all. If the isotropic ablation matches the projection mechanism, the proposal's central ingredient is wrong and we will say so. A fourth reference point, DP-TKNN-Shapley (A Privacy-Friendly Approach to Data Valuation), is not runnable in our setting — it assumes a trusted server holding raw embeddings and a clean validation set — but we report its design as the boundary case: private scores, no gradient valuation at all.

Why not just…?

Why not just use bigger batches? Because exact inversion is already a solved problem at federated batch scales: SPEAR recovers batches up to $b = 25$ pixel-perfectly (PSNR > 100) in about 2 minutes, where optimization-based attacks needed over 18 minutes to produce only blurry approximations at PSNR ≈ 19.6 (SPEAR), and SPEAR++ scales exact recovery to $b = 210$ CIFAR-10 images in polynomial time (SPEAR++). Batch averaging deters the old attacks, not the current ones; our threat model must include them.

Why not just add standard DP noise? Three documented failures. Isotropic DP destroys the valuation signal itself — the "DP-smudge" result, where gradient-norm ranking overlap collapses to SSIM 0.355 even as VoG survives (Leveraging gradient-derived metrics...). It protects unfairly — under identical noise, MNIST digits '5' and '8' remain far easier to recover than others because risk concentrates along specific Jacobian singular vectors, not isotropically (Understanding Deep Gradient Leakage via Inversion Influence Functions). And at the noise scales small enough to preserve utility, SPEAR-class attacks maintain high fidelity through clipping and modest noise (SPEAR). Still, this is a real threat: if the isotropic ablation in our experiments matches the projection mechanism at equal budget, the structural story collapses and the honest conclusion is that calibrated DP is enough.

Why not just prune the high-value, high-risk samples? Two reasons, both measured. Removing the top-value layer does not remove the vulnerability: the privacy-onion effect shows that previously low-value samples inherit top-tier importance and vulnerability, creating an evolving attack frontier (Understanding Data Importance in Machine Learning Attacks). And pruning destroys the thing valuation exists to price: removing the top 25% of VoG-identified samples — the "useful difficulty" outliers — dropped CIFAR-10 test accuracy from 66.7% to 61.7% at $\epsilon = 8$ (Leveraging gradient-derived metrics...). Our audit experiment will additionally measure, for the first time, whether the onion dynamic persists under exact attacks rather than membership inference.

Why not just use secure aggregation and let clients score themselves? This is the closest competing mechanism: the Fair-Private and Everybody-Else metrics of Private and Robust Contribution Evaluation in Federated Learning are secure-aggregation-compatible and linear-time. But EE deliberately sacrifices the null-player axiom to resist strategic self-inflation, the schemes require local evaluation against exchanged intermediate checkpoints whose own leakage is unanalyzed, and leave-one-out style local scoring fails in non-IID federated data and correlates poorly with true Shapley rankings, as both that paper and the FSV paper document (A Principled Approach to Data Valuation for Federated Learning). Our mechanism keeps server-side, axiom-compatible per-round Shapley and quantifies its leakage instead of assuming it away; the frontier measurement is exactly the comparison these papers lack.

Proposed Experiments

All experiments run in a federated simulation on CIFAR-10 (primary; every reference number above is CIFAR-10-based) with MNIST as a secondary check of class-heterogeneous leakage, using a fully connected ReLU network where SPEAR's guarantees hold exactly, plus a small convolutional setting where we rely on SPEAR++ and $I^2F$. We simulate 20–100 clients in non-IID shards, mirroring the scales at which FedBary completed 100-client valuation in 21–60 minutes where exact Shapley was infeasible (Data Valuation and Detections in Federated Learning); we track wall-clock cost to confirm the projection step does not push valuation back toward the exponential wall. Three decisive checks. First, coupling: across value strata and training rounds, the rank correlation between value score and inversion outcome (exact-recovery indicator at PSNR > 100, and $I^2F$ risk) — the theory predicts positive correlation, strongest early; if SPEAR recovery is value-blind, the coupling claim is refuted and we report it, noting it would confirm Wen et al.'s negative reconstruction finding extends to exact attacks. Second, the frontier: sweep projection dimension $r$ and noise $\sigma$, plotting Spearman $\rho$ against ground-truth FSV versus SPEAR++ exact-recovery rate, with the DP-plus-VoG baseline and the isotropic ablation on the same axes; success is a mechanism point with $\rho \geq 0.9$ and near-zero exact recovery where the DP baseline fails at least one axis at matched budget. Third, dynamics: iterate the onion procedure under the mechanism, testing whether valuation-guided removal shifts inversion vulnerability to the next stratum, and whether the mechanism's protection degrades gracefully as the value distribution re-forms. Membership inference at 1% false positive rate serves as a secondary privacy metric, benchmarked against the 10.2× TPR gap between high- and low-importance samples reported for CIFAR-10 (Understanding Data Importance in Machine Learning Attacks). No reported result found on Lacuna for SPEAR-class exact recovery on projected or subspace-degraded gradients, which is precisely the measurement this proposal is designed to supply.