---
kind: concept
slug: leave-one-out-analysis
title: Leave-one-out analysis
summary: >-
  Remove one row, entry or training record, recompute, and compare with the full result. In spectral analysis it is a proof technique for entrywise error bounds, which the monograph reports as much smaller than ℓ2 bounds. In membership inference it is the ideal reference: a model retrained without the record, which needs the other n−1 records, so attacks approximate it.
tags: [theory, perturbation-analysis, spectral-methods, privacy-auditing]
papers: ["2012.08496", "2111.09679"]
related: [spectral-methods, spectral-clustering, community-detection, membership-inference]
status: draft
updated_at: 2026-11-01
---

## Overview

Leave-one-out asks how much one piece of data moves a result. Remove that
piece, recompute the result, and compare it with the full one. The two papers
on this page use the idea for different ends.

In spectral analysis it is a proof device. Spectral estimators are usually
analysed in ℓ2 subspace distance, which says how far the whole eigenspace
moves. Many questions ask about one row or one entry instead, such as the
error of one item's estimated score. The monograph notes that for entrywise
questions a naive bound by the ℓ2 error is often loose by an order of
magnitude [arxiv:2012.08496 §4]. The leave-one-out technique removes the
influence of one row or entry, recomputes the estimate, and bounds the
difference. The card describes this as decoupling the statistical dependence
that a direct analysis would otherwise have to handle [arxiv:2012.08496 §4].
The monograph credits El Karoui et al. and Abbe et al. for the technique
[arxiv:2012.08496 §4].

In membership inference it is a reference experiment. The question is whether
a record was in the training set. The ideal test compares the model's loss on
that record with the loss of a model trained without it. That retraining needs
the other n−1 training records, which the attacker does not have, so the
attacks below approximate it [arxiv:2111.09679 §4.4] [arxiv:2111.09679 §4.5].

The invariant the spectral variants share is the comparison between the full
estimate and an auxiliary estimate built without the removed row or entry. The
cards do not reproduce the proof for each theorem, so the spectral variants cite
only the bound each theorem states.

## Variants

### Spectral: rank-1 denoising, entrywise bound

For a rank-1 symmetric target with leading eigenvector u*, the entrywise error
of the estimate u satisfies dist∞(u, u*) ≲ σ(√log n + √μ)/λ*, with failure
probability O(n⁻⁸), when σ√n ≤ c₀λ* [arxiv:2012.08496 §4.1]. Here μ is the
incoherence parameter defined for matrix completion [arxiv:2012.08496 §3.8].
Card: [Spectral Methods for Data Science: A Statistical Perspective](/papers/2012.08496).

### Spectral: general rank-r denoising, row-wise (ℓ2,∞) bound

After aligning the estimate with the target by the rotation sgn(H), the
row-wise error is bounded by (σκ√(μr) + σ√(r log n)) / ‖λr*‖, with failure
probability O(n⁻⁵), when σ√(n log n) ≤ c_σ · ‖λr*‖ [arxiv:2012.08496 §4.2].
The card gives a first-order approximation: uniformly across rows, U sgn(H) is
close to U* + E U* (Λ*)⁻¹ [arxiv:2012.08496 §4.2]. The paper uses this to
explain why the ℓ2,∞ error is smaller than the ℓ2 error [arxiv:2012.08496 §4.2].
Card: [Spectral Methods for Data Science: A Statistical Perspective](/papers/2012.08496).

### Spectral: general rank-r denoising, entrywise matrix bound

The error of the reconstructed matrix UΛUᵀ in the entrywise (ℓ∞) norm is
bounded by σκ²μr √(log n / n), under σκ√(n log n) ≤ c₁ · ‖λr*‖
[arxiv:2012.08496 §4.2]. This bound is stated for the matrix, not for the
eigenvectors.

### Spectral: matrix completion, row-wise and entrywise bounds

With n₁p ≥ C κ⁴μ²r² log n and n = n₁ + n₂, the ℓ2,∞ error is at most
κ²√(μ³r³ log n / (n₁²p)) and the ℓ∞ error at most
κ²μ²r²√(log n / (n₁³p)) · ‖M*‖, both with probability at least 1 − O(n⁻⁵)
[arxiv:2012.08496 §4.4]. The card states that the ℓ2,∞ error can be about √n₁
times smaller than the ℓ2 error, and the entrywise error about n₁ times smaller
than the Euclidean matrix error [arxiv:2012.08496 §4.4]. These are order
statements; the paper does not claim sharp constants [arxiv:2012.08496 §1.3].
Card: [Spectral Methods for Data Science: A Statistical Perspective](/papers/2012.08496).

### Spectral reference: ℓ2 perturbation without leave-one-out

The classical bounds need no leave-one-out argument. Davis–Kahan and Wedin
give dist(U, U*) ≤ 2‖E‖ / (|λr*| − |λr+1*|) when ‖E‖ is below
(1 − 1/√2) times the eigengap [arxiv:2012.08496 §2.3]. For singular subspaces,
Wedin's theorem gives the analogous form [arxiv:2012.08496 §2.4]. These bound
the subspace, not one row or entry.

### Membership inference: idealised leave-one-out reference (attack L)

Attack L trains reference models on the target's training set with the record
z removed [arxiv:2111.09679 §4.5]. It is the closest the paper gets to exact
leave-one-out. Because it needs the exact n−1 records, the authors use it only
as an upper reference, not as a practical attack [arxiv:2111.09679 §4.5].
Card: [Enhanced Membership Inference Attacks against Machine Learning Models](/papers/2111.09679).

### Membership inference: distillation approximation (attack D)

Attack D approximates leave-one-out without the other n−1 records. It trains
distilled models on random population data, labelled with the target model's
outputs, and uses their losses on the record to set the threshold. The
threshold therefore depends on the target model and the record together
[arxiv:2111.09679 §4.4]. The Purchase100 setups use 999 distilled models
[arxiv:2111.09679 app. B.2]. On Purchase100 setup II, at false-positive rate
0.3, D and attack L agree on 0.804 of records, while S and P agree on 0.892
(author-reported) [arxiv:2111.09679 §5.3] [arxiv:2111.09679 tab. agreement].
The paper says D is not an exact leave-one-out oracle, and that its
approximation error may explain its lower true-positive rate at very small
false-positive rates [arxiv:2111.09679 §5.2].
Card: [Enhanced Membership Inference Attacks against Machine Learning Models](/papers/2111.09679).

### Membership inference: per-record reference models (attack R)

Attack R trains reference models on random population subsets and sets one
threshold per target record from their losses on that record
[arxiv:2111.09679 §4.3]. It does not need the other training records. Its
results are in the same card as D. On Purchase100 the authors report that R and
D reach more than ten times the true-positive rate of S and P below a
false-positive rate of 0.2 [arxiv:2111.09679 §5.2]. The paper calls R slightly
better than D at the smallest false-positive rates [arxiv:2111.09679 §5.2].
Card: [Enhanced Membership Inference Attacks against Machine Learning Models](/papers/2111.09679).

## When to use which

| Situation | Use | Why |
|---|---|---|
| Only the overall subspace error matters | ℓ2 perturbation bounds (Davis–Kahan, Wedin) [arxiv:2012.08496 §2.3] [§2.4] | Simplest statement; needs the eigengap to exceed the noise. |
| The error of one row or entry matters, such as one item's score | Row-wise or entrywise bounds [arxiv:2012.08496 §4.1] [§4.2] [§4.4] | The card says a naive ℓ2 bound is often loose by an order of magnitude for entrywise questions [arxiv:2012.08496 §4]. |
| Matrix completion with per-row or per-entry accuracy goals | §4.4 bounds | They need n₁p ≥ C κ⁴μ²r² log n, a stronger sample condition than the ℓ2 bounds in [arxiv:2012.08496 §3.8]. |
| Noise entries are dependent (for example, blind deconvolution) | Not covered by these bounds | The ℓ∞ and ℓ2,∞ theory assumes independent entries; the dependent case is an open problem [arxiv:2012.08496 §4] [§5]. |
| Eigengap is small compared with the noise | Neither variant applies as stated | The theorems require the gap to exceed the noise. The 2×2 example shows that a leading eigenvector can rotate by a right angle [arxiv:2012.08496 §2.3]. |
| Numerical constants are needed | Not available | The constants in the theorems are "sufficiently large" or unstated [arxiv:2012.08496 §1.3] [§5]. |
| Ground truth for a membership audit, and the exact other training records are available | Attack L [arxiv:2111.09679 §4.5] | It is the leave-one-out reference itself, but the paper uses it only as an upper reference. |
| Membership audit without the other training records, with query access to the target's outputs on population data | Attack D [arxiv:2111.09679 §4.4] [§5.2] | It approximates leave-one-out without those records. It needs many distilled models per target [arxiv:2111.09679 app. B.2], and the approximation is imperfect [arxiv:2111.09679 §5.2]. |
| Membership audit at low false-positive rates, with population data and the target's loss on the record | Attack R [arxiv:2111.09679 §4.3] [§5.2] | Reported to beat S and P at low false-positive rates, though the result is author-reported. Below one over the number of samples, the threshold needs smoothing [arxiv:2111.09679 app. B.3]. |

## Implementation sketch

Leave-one-out is a proof device in the spectral variants, so this sketch lists
only the steps the card attributes to the technique. The card does not give the
exact construction of the auxiliary estimate for each theorem. The membership
variants are experiments, not bounds, and are described in their variant
sections above.

```pseudocode
# Leave-one-out bound on the error of row l  [arxiv:2012.08496 §4]
# Input:  M = M* + E (symmetric, n x n), target rank r, row index l
# Output: a bound on the row-l error of the estimate U
# Step 1: remove the influence of row and entry l  [arxiv:2012.08496 §4]
M_l = M with the influence of row and entry l removed
# Step 2: recompute the top-r eigenvectors from the modified matrix  [§4]
U_l = top-r eigenvectors of M_l
# Step 3: align U with U* by the rotation sgn(H), where H = Uᵀ U*  [§4.2]
R = sgn(H)
# Step 4: uniformly over rows, U R is close to U* + E U* (Λ*)⁻¹  [§4.2]
# Step 5: bound the row-l error using that first-order term  [§4.2] [§4.4]
row_error(l) ≈ || (E U* (Λ*)⁻¹)[l] ||
```

## Contradictions

No numerical disagreement between the two papers. They use the term for
different objects: a proof step for eigenvector error in the monograph, and an
experimental reference for membership in the membership card. Results from one
do not carry over to the other. Within the membership card, the paper says that
attack D is not an exact leave-one-out oracle [arxiv:2111.09679 §5.2]; this is
a stated limit, not a contradiction.

## Papers

- [Spectral Methods for Data Science: A Statistical Perspective](/papers/2012.08496): a monograph whose §4 gives the leave-one-out row-wise and entrywise bounds for denoising and matrix completion; no code is published with it.
- [Enhanced Membership Inference Attacks against Machine Learning Models](/papers/2111.09679): uses idealised leave-one-out retraining (attack L) as its reference and proposes distillation (attack D) and per-record reference models (attack R) as practical attacks; author code is at a pinned commit.