Group deletion curve
DefinitionSampleRemoval_Supplement_deletionCurveleast-squaresoptimizationp2o-gran-per-chapterp2o-plan-paperp2o-v1robustness-auditsample-removal
The deletion curve of group records the smallest cross-scatter after exactly deletions:
It isolates every group's contribution before the curves are combined by min-plus convolution.
Formalization Note The real infimum is used only for , when the finite candidate family is nonempty and the infimum is attained.
Definition code
import Mathlib
import Definitions.Def_SampleRemoval_Supplement_withinCross
set_option autoImplicit false
namespace SampleRemoval.Supplement
/-- The group deletion curve `f_g(k)`, the minimum within-group cross-scatter after deleting
exactly `k` of the `n_g` observations (Xu, Gao, Hu, STOC 2027 submission, §4, p.7 (PDF p.9)).
**Formalization Note** It is represented by the real infimum of the finite nonempty family of
subsets of cardinality `n_g-k`; statements only use `k≤n_g`, which ensures that family is
nonempty and makes this infimum the paper's minimum. -/
noncomputable def deletionCurve {Γ : ℕ} (M : FixedEffectsModel Γ) (g : Fin Γ) (k : ℕ) : ℝ :=
sInf {z : ℝ | ∃ A : Finset (Fin (M.nobs g)), A.card = M.nobs g - k ∧ z = withinCross M g A}
end SampleRemoval.Supplement
Source
Xu, Gao, Hu, Rounding, Ranges, and Exact Sample-Removal Audits for Least Squares, STOC 2027 submission (manuscript sha256 dcd33acebc1ccdc626c7ee41bfabc29795abe2e1cd9267d8cbd66d98f81c4b26), Section 4, p.7 (PDF p.9)