How many reference samples does a membership inference attack really need?

The attacker can need more data than the trainer

A membership inference attack receives a model output and a target individual, and must decide whether that individual was in the training data or is an independent draw from the same population. The paper asks how many independent reference samples from that population the attacker needs, calling this the sample complexity of membership inference.

The answer is a lower bound. For Gaussian mean estimation in d dimensions, with n training samples and an estimator whose error is allowed to include an extra term scaled by ρ, the paper shows that Ω(n + n²ρ²) reference samples can be necessary for any attack that competes with an attacker who knows the distribution exactly. The interesting case is ρ much larger than n^(-1/2): then n²ρ² is ω(n), and the reference set must be asymptotically larger than the training set. The bound is stated for the regime where the dimension is at least roughly n + n²ρ², the threshold at which a fully informed attacker can succeed at all.

A weak success criterion still yields a strong bound

The paper defines an m-sample-based attack as a function that takes m reference samples, the released estimate μ̂, and a target point, and outputs IN or OUT. Success is deliberately modest: the false positive rate on an independent sample must be at most 0.49, and the true positive rate on each training point must be at least 0.51. Because the paper proves a lower bound, this weak requirement makes the result stronger, and the authors note it also covers the small false-positive rates, such as 1%, used in empirical work.

The estimator class is also restricted to noise-addition mechanisms: the output is the sample average plus independent zero-mean noise. The accuracy target is measured in Mahalanobis norm, with expected squared error at most dρ² + d/n. That expression separates the unavoidable sampling error d/n from the additional error the parameter ρ controls, which is why ρ, not just n, drives the sample requirement.

Knowing the covariance collapses the requirement

The paper's second result isolates the source of the cost. If the attacker knows the population covariance but not the mean, every successful attack needs only Ω(min{n, 1/ρ²}) reference samples in the regime where d is about n + n²ρ², and the earlier attack of Dwork et al. achieves this, so the bound is tight. More generally, an m-sample attack exists only if d is at least on the order of n + n²ρ² + n²/m.

Comparing the two theorems gives the paper's sharpest internal contrast. For ρ larger than 1/√n, knowing the covariance reduces the required reference samples from Ω(n²ρ²) to O(n). The authors conclude that estimating the population covariance is what makes membership inference expensive in the unknown-covariance setting. This is an interpretation the paper derives from the comparison of its own two bounds, not a separate experiment.

Current attacks use only linear-size reference sets

The paper separates two forms of test. A general test may use the population in both the test statistic and the threshold. The restricted form used by prevailing practice computes a statistic that does not depend on the population and uses reference samples only to calibrate a threshold. For a constant false-positive rate such as 5%, that calibration needs O(1) independent model retrainings, hence O(n) reference samples, and for this restricted form Θ(n) samples are as good as knowing the distribution itself.

The lower bound says that ω(n) samples can enable attacks where O(n) samples fail. The authors therefore argue that audits built on restricted attacks may underestimate privacy risk, and that attacks exploiting distribution knowledge in new ways are worth exploring. They mention quadratic approximations to the loss as a promising direction, while noting that such tests would not necessarily perform well on the mean estimation problem studied here, because the loss's Hessian is data-independent.

The result rules out a family, not one mechanism

The bound is not a statement that one fixed algorithm is hard to attack. It holds even when attention is restricted to the specific estimator that adds noise with covariance proportional to the unknown population covariance, but the proof works by constructing a hard distribution over pairs of populations and algorithms. The authors state that giving a separation based on a single mechanism remains an open question.

The bound is also not tight everywhere. When d is much larger than n + n²ρ², a straightforward attack that estimates the covariance to rescale the data and then applies the earlier test uses Θ(d) reference samples, leaving a gap to the lower bound. The paper characterizes the sample complexity completely only in the regime where d is comparable to n + n²ρ². The constants are not optimized, and the numerical parameter settings used to drive the total variation distance below 0.02 are chosen for proof convenience.

Treat reference-set size as a threat-model choice

The decision-relevant split is between ρ near or below n^(-1/2) and ρ clearly above it. In the first case the lower bound stays on the order of n, and linear-size reference sets are not obviously inadequate. In the second, the requirement grows like n²ρ², and an audit that supplies only O(n) reference samples is testing a strictly weaker attacker than the best one the paper's bound permits.

The paper's priority is therefore not that membership inference is stronger than believed in every setting, but that the gap depends on which quantity the attacker must learn. When the covariance is known, O(n) samples suffice and current practice is aligned with the tight bound. When the covariance is unknown and the estimator's added error exceeds sampling error, the reference requirement can exceed the training set size, and the honest reading of an O(n)-sample audit is a lower bound on risk rather than a measurement of it.

Sources used in this answer