Spectrum Is Not Enough: A Random-Matrix Account of Data-Free Preconditioning for Differentially Private Learning

Shilin Zhang; Kangning Wang

cs.LGOct 15, 2026

Spectrum Is Not Enough: A Random-Matrix Account of Data-Free Preconditioning for Differentially Private Learning

Authors: Shilin Zhang, Kangning Wang

Organizations: School of Electrical and Control Engineering, North China University of Technology, Beijing, China

Abstract

Data-free preconditioning builds the Kronecker factors of KFAC from synthetic probes instead of private data. DP-KFC validates a probe by matching the eigenvalue decay of the private factors; we turn this criterion into a random-matrix account of what a probe can reconstruct. A single dichotomy organizes it: in the factorization $A \otimes G$ , the error-signal factor $G$ and the architecture-determined bulk of the activation factor $A$ are reconstructible without data, while only the data-induced spikes of $A$ are not. We prove the $G$ half is data-insensitive up to an explicit error-energy bound, with zero violations over a full training trajectory across four modalities and a natural-image benchmark. We locate the failure boundary at a Baik-Ben Arous-Péché threshold: a bulk-only probe suffers an exact damage $s^2/(1-s^2)$ from a data-induced spike, which becomes invisible once it exceeds $(d/n)^{1/4}$ , confirmed on an injected-spike surrogate. Holding the probe spectrum fixed and varying only its eigenbasis, we show that spectral-shape matching is neither sufficient nor the operative object: a probe with a near-exact matched spectrum (log-ratio dispersion $0.02$ ) still inflates the residual $2 \times$ - $90 \times$ when its eigenvectors are random. A closed-form whitened-volume law explains this and predicts the within-spectrum ordering of the critical volume, though not its cross-dataset magnitude. Downstream, per-layer tuning does not transfer to accuracy and the headroom is a small oracle-minus-white gap. Under a privacy mechanism the source ordering survives while learning does, then inverts at a noise cross-over where the flat probe overtakes the matched ones.

Figures & tables

Fig. 1: Overview. (a) Data-free two-factor anatomy: the private mini-batch is unavailable, so a probe built from public or synthetic spectra supplies both Kronecker factors, combined into the preconditioner

\mathbf{M}=\widehat{\mathbf{A}}\otimes\widehat{\mathbf{G}}

applied blockwise per layer. (b) The basis-first inversion (input layer, eight dataset configurations): relative to the white probe, a probe with the matched spectrum in the aligned basis sits at

0.74

–

1.00\times

on every modality, while the same eigenvalues in a Haar-random basis inflate the bulk residual by

2.1\times

(PathMNIST) to

82.7\times

(DermaMNIST); the two arms share a bitwise-identical log-ratio dispersion (

0.286130

on DermaMNIST). (c) The whitened-volume law: relative bulk-residual damage against the number

K

of rotated top eigendirections; open circles mark the empirical

K^{\star}

(

128

on OCTMNIST and DermaMNIST,

192

on TissueMNIST,

320

on CIFAR-10, not reached on PathMNIST up to

K=512

). The closed form

\det\mathbf{M}=1

\mathbb{E}[\operatorname{tr}\mathbf{M}]=(\operatorname{tr}\Lambda)(\operatorname{tr}\Lambda^{-1})/d

predicts this ordering from the spectrum alone.

Fig. 2: Refinement of the failure boundary. (a) The exact threshold

s_{c}=\big(\sqrt{c}/(1+\sqrt{c})\big)^{1/2}

tracks the crossing-based empirical estimate across aspect ratios, while the leading-order form

c^{1/4}

overstates it. (b) The empirical threshold converges to the exact value as the dimension grows at fixed

c=0.25

. (c) For an anisotropic bulk the threshold is a functional of the bulk spectrum:

\beta_{c}/b_{+}\approx 0.49

for an isotropic bulk (with

\sqrt{c}=0.5

) and

\approx 2.24

for power-law bulks, independent of the exponent. Numbers from verify_boundary_law (MC, archived in figs/boundary_refine_data.json).

Fig. 3: Controlled verdict of the basis hypothesis. Left: bulk residual against the rotation scale

\theta

of the probe basis at fixed spectrum: the residual is a step function of basis mixing, while the spectral dispersion (right axis family) is bitwise invariant along the rotation. Right: the loss of Fourier concentration of the probe; the random-basis value is

\approx 8.5\times 10^{-3}

modality	oracle	white	global $\alpha^{\ast}$	tailored
DermaMNIST	$\mathbf{0.129}$	$0.104$	$0.115$	$0.111$
	$\pm.022$	$\pm.006$	$\pm.022$	$\pm.018$
OCTMNIST	$\mathbf{0.124}$	$0.101$	$0.104$	$0.101$
	$\pm.009$	$\pm.009$	$\pm.007$	$\pm.003$
CIFAR-10	$\mathbf{0.176}$	$0.112$	$0.105$	$0.106$
	$\pm.010$	$\pm.005$	$\pm.012$	$\pm.012$

TABLE I: Downstream accuracy under four probe regimes (mean of the last three epochs of balanced accuracy, mean

\pm

std over ten seeds,

\sigma=0

DP-SGD, eight epochs). The oracle arm is an upper reference, not a method.

$\sigma$	$\varepsilon$	private	aligned	white
$0.0$	–	$0.322$	$0.329$	$0.130$
$0.1$	$1.1{\times}10^{4}$	$0.217$	$0.222$	$0.132$
$0.2$	$274$	$0.155$	$0.157$	$0.134$
$0.3$	$86$	$0.126$	$0.132$	$\mathbf{0.155}$
$0.5$	$16.6$	$0.110$	$0.114$	$\mathbf{0.128}$

TABLE II: Noise tolerance and the source-ordering cross-over (PathMNIST, four seeds, mean of the last three epochs, learning rate

0.03

; majority-class rate

0.143

;

\varepsilon

from RDP accounting). The matched sources lead below

\sigma=0.3

; the flat white probe leads above it.

Fig. 4: DP-noise mechanism experiment (75 runs). (a) Final test accuracy falls below the majority-class rate for every training source once

\sigma>0

. (b) On the true-DP models, noise first removes the activation-factor spike (top-1 fraction

0.330\to 0.025

) and later re-concentrates the error factor (

0.030\to 0.138

). (c) The log-ratio mismatch of the aligned public probe stays an order of magnitude below all alternatives at every

\sigma

, but the surviving structure is operationally irrelevant.

Appendix figures & tables14 assets

Supplementary material from the paper’s appendix.

Appendix

$\sigma$	$\varepsilon$ (RDP)	optimal order	steps
$0.0$	no formal guarantee	n/a	$948$
$0.5$	$16.556$	$1.9$	$948$
$1.0$	$2.350$	$6.6$	$948$
$2.0$	$0.780$	$18.0$	$948$
$4.0$	$0.338$	$36.0$	$948$

Appendix

TABLE III: Privacy budget of the DP-noise mechanism experiment (PathMNIST,

n=20000

, batch

256

T=948

\delta=5\times 10^{-5}

$\sigma$	top-1 ( $A$ , L2)	top-1 ( $G$ )	$\beta_{o}$	$\beta_{g}$
$0.0$	$0.330\pm.018$	$0.203\pm.042$	$-0.695$	$-0.746$
$0.5$	$0.025\pm.001$	$0.030\pm.006$	$-0.265$	$-0.561$
$1.0$	$0.020\pm.001$	$0.038\pm.008$	$-0.264$	$-0.737$
$2.0$	$0.019\pm.001$	$0.093\pm.043$	$-0.264$	$-1.057$
$4.0$	$0.018\pm.001$	$0.138\pm.067$	$-0.263$	$-1.632$
aligned-probe $\mathrm{lr\_std}$ (L2): $0.028$ – $0.037$ at all $\sigma$

Appendix

TABLE IV: Live-oracle spectral statistics of Section VIII (private-oracle source, PathMNIST).

\beta_{o}

and

\beta_{g}

are the live tail exponents of the activation and error factors; top-1 fractions are spike shares of the live spectrum.

source	$\sigma=0$	$0.5$	$1.0$	$2.0$	$4.0$
private oracle	$0.264$	$0.099$	$0.105$	$0.105$	$0.103$
public (aligned)	$0.267$	$0.101$	$0.099$	$0.101$	$0.100$
public (OCTMNIST)	$0.252$	$0.101$	$0.101$	$0.098$	$0.098$
synthetic $1/f$	$0.119$	$0.086$	$0.147$	$0.145$	$0.126$
synthetic white	$0.133$	$0.148$	$0.153$	$0.130$	$0.121$

Appendix

TABLE V: Final test accuracy by source and noise multiplier (Section VIII ; majority-class rate

0.143

quantity	value
configurations	$72$
energy-bound violations	$0$
$\eta$ -bound violations	$0$
max ratio to (i) bound	$6.4\%$
median ratio to (i) bound	$0.15\%$
$\eta$ at epoch $0$ / $16$	$0.904$ / $0.655$

Appendix

TABLE VI: Error-energy bound calibration (exp. trajectory record).

Fig. 5: Activation-spectrum matching: the oracle tail exponent

\beta_{o}

steepens from the first hidden layer to the output layer on every modality, while the reachable range of the

\alpha\in[0,3]

probe family is a narrow band. The layer-optimal probe exponent tracks the oracle exponent only where the two ranges overlap.

Fig. 6: Downstream transfer test. Left three panels: balanced accuracy curves under the four probe regimes. Right: accuracy deltas against the white baseline with seed-combined standard errors. Per-layer tailoring does not improve on a single global exponent.

modality	$\beta_{o}$ (input)	$K^{\star}$	res. at $K{=}512$
OCTMNIST	$-2.23$	$128$	$32.6\times$
DermaMNIST	$-2.06$	$128$	$54.0\times$
TissueMNIST	$-1.78$	$192$	$6.0\times$
CIFAR-10	$-1.58$	$320$	$1.9\times$
PathMNIST	$-1.08$	not reached	$1.0\times$

Appendix

TABLE VII: Critical misaligned volume

K^{\star}

from the dense scan

K\in\{8,\dots,512\}

(first

K

with relative damage above

5\%

), against the input-layer tail exponent

\beta_{o}

of the private bulk (the scan is performed at the input layer). Damage beyond

K^{\star}

grows superlinearly on steep spectra and is bounded by the Haar-basis asymptote.

Fig. 7: Volume scan of the misaligned subspace. Relative bulk residual against the number

K

of rotated top eigendirections. The critical volume moves monotonically with the steepness of the data spectrum, and the bottom-block arm stays mild everywhere.

Fig. 8: Eigenvalue diagnostics invert in the steep regime: layer-wise Spearman correlation between spectral dispersion and the bulk residual over the extended probe grid. Negatives concentrate at flat inputs, overly steep inputs, and steep output layers.

$s$	$0.0$	$0.25$	$0.5$	$0.6$	$0.7$	$0.75$	$0.85$	$1.0$	$1.25$	$1.5$
top-1/bulk	$1.004$	$1.004$	$1.005$	$1.017$	$1.126$	$1.259$	$1.865$	$783.8$	$783.8$	$783.8$

Appendix

TABLE VIII: Injected-spike sweep (

d=784

n=4096

d/n=0.191

, predicted

s_{c}=0.661

): ratio of the sample top eigenvalue to the bulk edge, mean over

3

seeds. The ratio jumps between

s=0.6

(below threshold) and

s=0.7

(above threshold); at

s\geq 1

the population covariance is rank-one and the ratio saturates at

d

dataset	psdF	psdR	eigR	white	psdR/psdF
PathMNIST	$0.981$	$2.22$	$2.19$	$0.981$	$2.3\times$
OCTMNIST	$1.043$	$56.55$	$53.78$	$1.399$	$54.2\times$
DermaMNIST	$0.968$	$86.89$	$80.87$	$1.097$	$89.8\times$
TissueMNIST	$0.932$	$30.36$	$28.78$	$1.025$	$32.6\times$
CIFAR-10 (32px subset)	$0.941$	$31.11$	$29.73$	$1.012$	$33.1\times$
CIFAR-100 (10 classes)	$0.972$	$18.67$	$19.52$	$0.982$	$19.2\times$

Appendix

TABLE IX: Universality across eight dataset configurations (Section VI-C ).

Fig. 9: Dataset sweep behind Table IX : input-layer bulk residual by probe family over eight dataset configurations. The Fourier-aligned profile (psdF) tracks the white baseline on every configuration; the Haar-basis variants separate on all but the near-isotropic PathMNIST input spectrum.

dataset	arch	psdF	psdR	white	psdR/psdF
PathMNIST	MLP	$0.981$	$2.22$	$0.981$	$2.3\times$
PathMNIST	CNN	$0.120$	$0.494$	$0.497$	$4.1\times$
DermaMNIST	MLP	$0.968$	$86.89$	$1.097$	$89.8\times$
DermaMNIST	CNN	$0.119$	$0.668$	$0.671$	$5.6\times$
CIFAR-100	MLP	$0.972$	$18.67$	$0.982$	$19.2\times$
CIFAR-100	CNN	$0.099$	$0.607$	$0.610$	$6.2\times$

Appendix

TABLE X: Architecture control (Section VI-C ).

Fig. 10: Architecture sweep behind Table X : on the convolutional oracle the Haar-basis probe collapses onto the white-noise baseline while the Fourier-aligned probe sits at one quarter to one sixth of it; on the MLP oracle the Haar mismatch amplifies further.

Kronecker-Factored Approximation

See all 14 papers

May 13, 2026

DP-KFC: Data-Free Preconditioning for Privacy-Preserving Deep Learning

Differentially private optimization suffers from a fundamental geometric mismatch: deep networks have highly anisotropic loss landscapes, yet DP-SGD injects isotropic noise. Second-order preconditioning can resolve this, but estimating curvature typically requires private data (consuming privacy budget) or public data (introducing distribution shift). We show that the Fisher Information Matrix decouples into architectural sensitivity, recoverable via synthetic noise, and input correlations, approximable from modality-specific frequency statistics. We propose DP-KFC, which constructs KFAC preconditioners by probing networks with structured synthetic noise, requiring neither private nor public data. Empirically, DP-KFC consistently outperforms DP-SGD and adaptive baselines across diverse modalities in strong privacy regimes (

\varepsilon \leq 3

). DP-KFC matches private-data preconditioners while public-data variants degrade by up to

4.8\%

, showing that curvature can be estimated without consuming privacy budget or introducing distribution shift. This enables privacy-preserving learning in specialized domains (e.g., medical applications) where regulatory constraints make data scarce.

Marc Molina Van den Bosch, Riccardo Taiello, Albert Sund Aillet +3

CERN, Geneva, Switzerland · BCN MedTech, Department of Engineering, Universitat Pompeu Fabra, Barcelona, Spain · ICREA, Barcelona, Spain

Differentially Private Stochastic Gradient Descent Kronecker-Factored Approximation Privacy-Preserving ML

Ask PDF

Sep 29, 2026

A Sharp Transition in Data Reconstruction under Differential Privacy

Data reconstruction attacks have empirically been successful in recovering training samples from learned models, raising privacy concerns and motivating defenses with guarantees that remain valid against future threats. While differential privacy (DP) provides formal protection, choosing the privacy budget remains a challenge: small budgets severely reduce utility, but it is hard to quantify how large the budget can be without allowing accurate reconstruction. In this work, we study informed attackers who aim to reconstruct a single

d

-dimensional training sample from a

ρ

-zero-concentrated DP model, knowing all other training data. Our main contribution is to establish a sharp transition at

ρ\asymp d

for data reconstruction: on the one hand, we derive entropy-based lower bounds for any private mechanism and any attack, characterizing a set of target priors for which reconstruction is information-theoretically impossible for

ρ\ll d

; on the other hand, we analyze a simple attack on private linear regression with output perturbation, showing that reconstruction is practically feasible for

ρ\gg d

. Remarkably, the transition moves to

ρ\asymp s

for data lying in an

s

-dimensional subspace, demonstrating that the privacy budget guaranteeing adequate protection must be assessed in terms of the effective dimension of the data. We validate our findings via experiments on synthetic data and natural images (CIFAR-10, ImageNet).

Max Cairney-Leeming, Simone Bombari, Marco Mondelli

Institute of Science and Technology Austria

Adversarial Attacks Training Data Reconstruction Attacks Differential Privacy Information-Theoretic Lower Bounds

Ask PDF

May 18, 2026

Beyond Square Roots: Explicit Memory-Efficient Factorization for Multi-Epoch Private Learning

Correlated-noise mechanisms are among the most promising approaches for improving the utility of differentially private model training, but rigorous guarantees require explicit, analyzable factorizations, and practical deployment requires memory efficiency. Recent works have developed banded inverse factorizations, which address both requirements by exploiting a banded structure in the correlation matrix. The bandwidth controls the size of the noise buffer used to correlate noise across iterations, and thus governs the tradeoff between utility and memory cost. Existing factorizations highlight this tradeoff: DP-

λ

CGD achieves high memory efficiency by using only a one-step noise buffer, but this limits its utility gains, while the banded inverse square root (BISR) factorization exploits larger correlation windows and is asymptotically optimal for large bandwidths but performs poorly at low bandwidths. We propose

γ

-BIFR, a unified generalization of both factorizations. In the low-memory, low-bandwidth regime,

γ

-BIFR significantly improves RMSE, amplified RMSE, and private training performance, while yielding tighter theoretical guarantees for multi-participation error in multi-epoch training.

Nikita P. Kalinin, Aki Rehn, Joel Daniel Andersson +2

Institute of Science and Technology Austria · University of Helsinki

Differentially Private Stochastic Gradient Descent Differential Privacy Memory-Efficient Training Matrix Factorization

Ask PDF

Abstract

Kronecker-Factored Approximation

Explore similar work

DP-KFC: Data-Free Preconditioning for Privacy-Preserving Deep Learning

A Sharp Transition in Data Reconstruction under Differential Privacy

Beyond Square Roots: Explicit Memory-Efficient Factorization for Multi-Epoch Private Learning