Min-plus convolution of group deletion curves
DefinitionSampleRemoval_Supplement_minPlusleast-squaresoptimizationp2o-gran-per-chapterp2o-plan-paperp2o-v1robustness-auditsample-removal
For a total deletion count , the min-plus convolution is
Thus is the least total within-group cross-scatter obtainable with exactly deletions distributed across the groups.
Formalization Note The infimum is used for , when the finite allocation family is nonempty.
Definition code
import Mathlib
import Definitions.Def_SampleRemoval_Supplement_totalObs
import Definitions.Def_SampleRemoval_Supplement_deletionCurve
set_option autoImplicit false
namespace SampleRemoval.Supplement
/-- The min-plus convolution `Λ(K)` of the group deletion curves: the minimum total cross-scatter
over allocations of exactly `K` deletions (Xu, Gao, Hu, STOC 2027 submission, §4, p.7
(PDF p.9)). Statements use `K≤n`, for which the allocation family is finite and nonempty. -/
noncomputable def minPlus {Γ : ℕ} (M : FixedEffectsModel Γ) (K : ℕ) : ℝ :=
sInf {z : ℝ | ∃ k : Fin Γ → ℕ, (∀ g, k g ≤ M.nobs g) ∧
∑ g, k g = K ∧ z = ∑ g, deletionCurve M g (k g)}
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)