Instance encoding is a popular empirical technique for privacy enhancement when sharing data to an untrusted server. It transforms sensitive data through an encoding process before sharing, with the hope that the encoding process retains utility but makes it hard to reconstruct the original data. However, most work offers no theoretical guarantee that the encoding process is actually irreversible. A recent work derived a mean-squared error (MSE) bound limiting any adversary's reconstruction accuracy, offering one of the first theoretical results in this domain. This bound, however, has three critical limitations: it is often too loose, only works with randomized encoders (excluding many deterministic encoders practitioners use), and only bounds MSE. We introduce a family of new bounds that (1) are tighter, (2) applicable even to fully deterministic encoders, and (3) can extend beyond MSE to other norm-based similarity metrics, by properly accounting for the encoder's spectral structure. We evaluate our bounds across a range of encoders, datasets, and attacks, showing they hold consistently and improve upon the existing bound.
Figures & tables
Figure 1: The idea of instance encoding and its invertibility.
Figure 2: Our MSE bounds (solid blue line) closely lower-bound the attackers’ achievable MSE for all the attackers. Bound from Maeng et al. [ 35 ] (dotted line) becomes very loose when r<d and is always zero when σ=0 (no encoder randomness).
Figure 3: Our LPIPS bounds (solid blue line) are always met, and tight near m∼d . For m≪d , the bound is unfortunately looser and near-flat, being less informative than the MSE bounds. Still, this is the first working LPIPS bound to our knowledge.
Figure 4: MSE and LPIPS bound with different skewness α .
Figure 5: MSE bound vs. achieved MSE by the attacker.
Figure 6: LPIPS bound vs. achieved LPIPS by the attacker.
Figure 7: S quality check: all the eigenvalues μi of Σ1/2SΣ1/2 must be equal to or larger than 1.
Figure 8: Bound vs. attack MSE/LPIPS with while varying the number of data k used to estimate E[G] . Result from the CIFAR-10 dataset; MNIST dataset shows similar trends and is omitted for space.
Figure 9: LPIPS bounds with and without noise, under various threshold τ that splits between the range space and the null space (Section 6.4.3 ). Empirically, τ=10−4 seems to be a reasonable choice, where the bounds appear the tightest and never violated.
Figure 10: Visualization of the reconstructed images from Figures 2 (b–c) ( σ=10−3 ), along with each encoder’s RTC.
Figure 11: Visualization of the reconstructed images from Figures 2 (e–f) ( σ=0 ), along with each encoder’s RTC.
Figure 12: Same reference images from Figures 10 and 11 , compared with their class-mean images.
What can an adversary recover from a model trained with DP-SGD? Its (ε,δ) guarantee does not answer this question directly. We derive a distortion bound that can be computed before training and applies even to an adversary who observes the parameter trajectory during training, knows every other training record and the population distribution from which the training records are drawn. The analyst may choose the representation in which error is measured, allowing the bound to target the aspects of reconstruction that are privacy-sensitive in a given application. Our information-theoretic framework separates two contributions: the information about a record revealed by training, measured through conditional mutual information, and the uncertainty already present in the data distribution, measured through source entropy. Rate-distortion theory combines them into a lower bound on the expected error of every reconstruction attack. For DP-SGD, the leakage bound depends only on the sampling rates and noise multipliers, while the source entropy is lower-bounded from a sample with finite-sample confidence. An orthogonal block construction keeps the resulting bound informative for high-dimensional images. We instantiate the framework in pixel space and in LPIPS feature space, obtaining, to our knowledge, the first lower bound on reconstruction distortion measured directly by LPIPS. On a range of image datasets the bounds establish non-trivial unavoidable expected reconstruction error within heuristically recommended privacy-budget ranges and beyond. Experiments compare the bounds with strong reconstruction attacks and identify the principal sources of the remaining slack.
Henry Bourne, Robert F. Allison
Department of Mathematics The University of Bristol Beacon House, Queens Road, Bristol, BS8 1QU, United Kingdom
Algorithmic stability refers to the property of an algorithm being insensitive to perturbations of the input data, where the type of perturbation may vary depending on the setting. In this work, we develop a general framework to quantify the extent to which any ensembling strategy defined via averaging can yield stability guarantees for any type of data perturbation. Our main theoretical result is a guarantee on the stability of this ensembled algorithm, given in terms of the norm of a certain covariance operator that describes the ensembling process. We show how our general framework yields interpretable and intuitive insights in several examples of perturbations of practical interest, and provides much sharper guarantees than those obtained from privacy considerations.
In this work, we study the information bottleneck under perfect privacy, with particular emphasis on the active-rate regime, where the representation-rate constraint is binding and directly limits the achievable utility. The goal is to construct a representation that preserves utility-relevant information while remaining statistically independent of a sensitive variable. This exact independence requirement introduces an additional constraint beyond the classical rate-relevance tradeoff and must be explicitly incorporated into the optimization. To this end, we develop an alternating direction method of multipliers (ADMM)-based method tailored to the resulting problem structure. Under suitable regularity conditions, we establish global convergence of the generated sequence, characterize its convergence rate through the Kurdyka-Lojasiewicz exponent, and extend the analysis to inexact block updates.
Junle Zhong, Mohamad Assaad, Sreejith Sreekumar
Laboratoire des Signaux et Syst`emes (L2S), CNRS, CentraleSup´elec, Universit´e Paris-Saclay, 91190 Gif-sur-Yvette, France