CS Paper Radar

A Theoretical Reduction From Membership Inference to Reconstruction Attacks Against Learners

Amnon Levi, Yuval Dagan

cs.LG ·submitted 2026-11-08 23:08 UTC · v1
theory

Abstract

We study reconstruction attacks, which recover training data from a learned model. In our adversarial model, the adversary designs a hard instance, drawn from a parameterized family of data distributions, and is given the parameter used to generate it. Our main contribution is a general reduction showing that, in this model, membership inference (determining whether a given datapoint was used for training) implies reconstruction: for a training set of size $n$, a membership test with recall at least $q(n)$ and false-positive rate $O(δ^2/n^2)$ yields a reconstruction algorithm that, with probability $1 - O(δ)$, outputs only training points, and recovers $Ω(n \cdot q(n))$ of them in expectation. This reduction applies to any learning algorithm. For stochastic convex optimization (SCO), we make the reduction computationally efficient over exponentially large domains via structured distributions whose support is partitioned into polynomially many categories of exponentially many elements each, so that reconstruction iterates over categories rather than the full support. Combining this with an existing membership inference result for SCO, we prove that any learning algorithm achieving low excess risk over all distributions admits a polynomial-time reconstruction attack recovering $Ω(n)$ training points, even when the underlying distribution has exponentially large support.

Comment
23 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Efficient Robust Learning at the Information-Theoretic Limit

cs.DS cs.LGstat.ML ·2026-09-15 ·Adam R. Klivans, Konstantinos Stavropoulos, Sergei Tikhonov, Arsen Vasilyan
similarity 0.67
Abstract · Corrected the arXiv abstract to match the pdf

In an important recent work, Blanc (2026) gave an algorithm for robustly learning Boolean concept classes with respect to a fixed distribution that outputs a (randomized) classifier achieving the optimal error of $η+ \varepsilon$ where $η$ is the noise rate. In contrast, it is well known that deterministic hypotheses cannot achieve error less than $2η+ \varepsilon$. Blanc's algorithm is computationally inefficient, and the main problem left open in his work is to find a polynomial-time algorithm given access to an oracle for empirical risk minimization (ERM). Here we resolve this problem and give such an algorithm. Additionally, we give an efficient algorithm (no ERM oracle required) for robustly learning any function class that admits low-degree polynomial approximators with respect to hypercontractive distributions. This captures basic settings including halfspaces with respect to Gaussian marginals. Our techniques make new connections to various types of online convex optimization algorithms. As a surprising consequence, we show that efficient SQ learnability in the agnostic setting implies efficient learning with contamination (with respect to Gaussians or uniform over the hypercube).

0.19

From Pixels to Privacy-Sensitive Features: An Information-Theoretic Framework for Reconstruction Bounds

cs.LG stat.ML ·2026-10-09 ·Henry Bourne, Robert F. Allison
theory similarity 0.64
Abstract · 40 pages, 9 figures

What can an adversary recover from a model trained with DP-SGD? Its $(\varepsilon,δ)$ 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.

0.22

A Sharp Transition in Data Reconstruction under Differential Privacy

cs.LG cs.AIstat.ML ·2026-09-29 ·Max Cairney-Leeming, Simone Bombari, Marco Mondelli
similarity 0.64
Abstract

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

0.05

Mitigating Black-Box Score-Based Query Attacks via Gradient Confusion

cs.LG cs.AIcs.CR ·2026-10-12 ·Ali Javeri, Javad Hezareh, Radin Shahdaei, AmirMahdi Sadeghzadeh
similarity 0.63
Abstract

Score-based black-box adversarial attacks pose a serious threat to deployed machine learning systems by exploiting repeated model queries to craft adversarial examples, requiring neither access to model parameters nor architecture. Existing defenses predominantly rely on stochastic output perturbations, which fail to prevent determined attackers from recovering stable gradient estimates by increasing query budgets or averaging over randomness. In this work, we propose the Gradient Confusion Defense (GCD), a retraining-free, deterministic test-time wrapper that actively shapes the probability vector returned to querying adversaries. By solving a constrained optimization problem grounded in the model's Jacobian, GCD aligns the exposed logit-gradient with a target confusion direction that is maximally misaligned with the true adversarial loss gradient---increasing the query complexity of attacks without sacrificing predictive utility or top-1 accuracy. We provide rigorous theoretical analysis demonstrating that GCD provably slows gradient-estimation-based attacks and induces systematic accept/reject errors in random search-based attacks, with the confusion effect amplifying as the fraction of defended queries increases. Extensive experiments on CIFAR-10 and ImageNet across multiple architectures (ResNet-18, ResNet-50, ViT-B/16) and four state-of-the-art attacks confirm these predictions: GCD achieves state-of-the-art robustness, while incurring zero clean accuracy degradation. %Crucially, unlike randomization-based defenses, GCD's deterministic structure provides resilience against adaptive attacks that exploit stochasticity, making it well-suited for security-critical deployment settings.

0.12

Closed-Form Noise Calibration Against Membership Inference for Random-Allocation DP-SGD

cs.LG cs.CR ·2026-10-07 ·Murat Bilgehan Ertan, Marten van Dijk
similarity 0.62
Abstract

DP-SGD protects training data by adding Gaussian noise to clipped gradients. The amount of noise is usually chosen by running a numerical privacy accountant inside a search. We study DP-SGD with random allocation, where each epoch uses every record once, at a randomly chosen step. For this setting we give a one-line formula that bounds the accuracy of every membership inference attack (MIA) on the trained model. With $M$ steps per epoch, $E$ epochs and noise multiplier $σ$, and with membership and non-membership equally likely a priori, the attack accuracy is at most $\frac12+\frac14\sqrt{(1+(e^{1/σ^2}-1)/M)^E-1}$. The formula comes from the chi-square divergence between a Gaussian distribution and a Gaussian mixture that dominates random allocation. It is interpretable and gives $σ$ in about a microsecond. Where applicable, our formula needs at most about half the noise of the state-of-the-art closed-form bound. To measure how close the bound is, we also derive an exact expression for the attack accuracy of these two distributions and evaluate it numerically. Calibrating to this exact expression requires $13.0\%$ to $20.2\%$ less noise than the formula in our main experiments, and since it is exact, no accountant that knows only $M$, $E$ and $σ$ can certify a smaller $σ$. In training, the resulting $σ$ outperforms the formula and matches a published accountant in test accuracy. It is found in seconds and certified in minutes, whereas every search we ran with that accountant took longer or returned at least $0.62\%$ more noise. We show that MIAs on the trained models stay below the bound.

0.29

Preventing Model Extraction in Contextual Linear Optimization

cs.LG math.OC ·2026-10-21 ·Adam N. Elmachtoub, Tianyi Lin, Wenxuan Liu
theory similarity 0.62
Abstract · 25 pages, 11 figures

Consider a contextual linear optimization problem, where a predict-then-optimize (PTO) system returns optimal decisions without revealing the cost vectors used in its downstream linear program. Our focus is on how to prevent attackers, who can submit context queries, from extracting the underlying prediction model. Although the cost-to-decision map is many-to-one, observations across contexts can reveal the underlying prediction model. For linear models, we provide sufficient conditions where the attacker can learn the model up to positive scaling by only observing the decision. These conditions motivate an adaptive attack that alternates inverse optimization with boundary sampling, i.e., using context queries leading to decision boundaries of the current attacker model. To prevent extraction, we propose a mechanism that perturbs decisions only when the predicted cost vector is near a decision boundary. We establish a regret bound in terms of the perturbation radius. For the attackers that fit the defended responses as optimal decisions under the evaluation distribution, we also prove a lower bound on expected extraction error. Experiments on synthetic instances and real data quantify the security-performance trade-off of the defense mechanism and illustrate that our defense can increase the extraction error.

0.18

Cascading Gradient Inversion via LT-Code Inspired Peeling in Federated Learning

cs.LG cs.AIcs.CR ·2026-09-09 ·Saeed Shariati, Mohsen Alambardar Meybodi
similarity 0.62
Abstract

Federated learning shares model updates rather than raw data, yet these updates can be inverted to reconstruct the clients' training data. Analytic reconstruction attacks, which invert a gradient in closed form, degrade as the batch grows: prior single-round attacks recover only about half of a batch of size $100$ even when the attacker fully controls the network parameters, and known upper bounds limit what any such method can recover. We establish a connection between gradient inversion and the theory of erasure-correcting codes, and use it to construct attacks that exceed these bounds. Our attacks recover batches exactly, together with every sample's label, from a single FedSGD round, and certify each recovery without ground-truth data. On eight image and tabular benchmarks they outperform prior single-round attacks by a wide margin. Even a passive attacker who only observes an honestly trained network recovers $94$--$100\%$ of ImageNet batches at sizes up to $128$, more than prior single-round attacks achieve even with active manipulation of the model, and in the active setting more than $90\%$ is recovered at batch sizes of several hundred. These results show that the privacy leakage of federated learning has been underestimated.

0.21

A Certified Robustness Framework for Backdoor Poisoning Attacks using $f$-Divergences

cs.LG cs.CR ·2026-10-26 ·Evan Rose, Alina Oprea
similarity 0.62
Abstract · 39 pages, 3 figures, 7 tables

Machine learning systems trained on untrusted data are vulnerable to data and backdoor poisoning attacks, in which an adversary corrupts training and test samples to manipulate predictions at inference time. Randomized smoothing yields provable defenses against such attacks, but existing applications to train-time robustness are limited to specific threat models and smoothing mechanisms. We propose a general framework that allows expressing complex adversary constraints on the number of corrupted training examples, feature and label perturbation magnitudes, and test-time corruptions. Our framework randomizes inputs by combining data subsampling with feature, label and test-sample noising. We develop a composable certification procedure based on $f$-divergences that handles arbitrary combinations of threat models and noising strategies, and recovers several prior certification regimes exactly as special cases. We demonstrate our framework experimentally by certifying, for the first time, robustness under general $\ell_p$-constrained poisoning adversaries under bagging with additive Laplace, Gaussian, and Uniform noises.

0.21