Leave-one-out analysis

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 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 2012.08496 §4. The monograph credits El Karoui et al. and Abbe et al. for the technique 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 2111.09679 §4.4 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₀λ* 2012.08496 §4.1. Here μ is the incoherence parameter defined for matrix completion 2012.08496 §3.8. Card: Spectral Methods for Data Science: A Statistical Perspective.

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*‖ 2012.08496 §4.2. The card gives a first-order approximation: uniformly across rows, U sgn(H) is close to U* + E U* (Λ*)⁻¹ 2012.08496 §4.2. The paper uses this to explain why the ℓ2,∞ error is smaller than the ℓ2 error 2012.08496 §4.2. Card: Spectral Methods for Data Science: A Statistical Perspective.

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*‖ 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⁻⁵) 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 2012.08496 §4.4. These are order statements; the paper does not claim sharp constants 2012.08496 §1.3. Card: Spectral Methods for Data Science: A Statistical Perspective.

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 2012.08496 §2.3. For singular subspaces, Wedin's theorem gives the analogous form 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 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 2111.09679 §4.5. Card: Enhanced Membership Inference Attacks against Machine Learning Models.

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 2111.09679 §4.4. The Purchase100 setups use 999 distilled models 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) 2111.09679 §5.3 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 2111.09679 §5.2. Card: Enhanced Membership Inference Attacks against Machine Learning Models.

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 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 2111.09679 §5.2. The paper calls R slightly better than D at the smallest false-positive rates 2111.09679 §5.2. Card: Enhanced Membership Inference Attacks against Machine Learning Models.

When to use which

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.

# 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 2111.09679 §5.2; this is a stated limit, not a contradiction.

Papers

• Spectral Methods for Data Science: A Statistical Perspective: 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: 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.