Lifted-plane range in a sub-instance
DefinitionSampleRemoval_Supplement_IsLiftedPlaneRangeOnleast-squaresoptimizationp2o-gran-per-chapterp2o-plan-paperp2o-v1robustness-auditsample-removal
A retained set is a lifted-plane range relative to a finite sub-instance when some strict plane cut selects exactly its saddle lifts:
Taking gives the paper's ordinary lifted-plane range; allowing a stated expresses Theorem 5.7's persistence claim.
Definition code
import Mathlib
set_option autoImplicit false
namespace SampleRemoval.Supplement
/-- `S` is a lifted-plane range relative to the finite sub-instance `U`: one strict plane cut in
the saddle lift selects exactly `S` among `U` (Xu, Gao, Hu, STOC 2027 submission, §5.3, p.10
(PDF p.12)). Taking `U=univ` is the paper's ordinary lifted-plane range. -/
def IsLiftedPlaneRangeOn {n : ℕ} (p : Fin n → ℝ × ℝ) (U S : Finset (Fin n)) : Prop :=
S ⊆ U ∧ ∃ c : Fin 4 → ℝ, ∀ i ∈ U,
(i ∈ S ↔ c ⟨0, by omega⟩ * (p i).1 * (p i).2 + c ⟨1, by omega⟩ * (p i).1 +
c ⟨2, by omega⟩ * (p i).2 + c ⟨3, by omega⟩ < 0)
end SampleRemoval.Supplement
Source
Xu, Gao, Hu, Rounding, Ranges, and Exact Sample-Removal Audits for Least Squares, STOC 2027 submission (manuscript sha256 dcd33acebc1ccdc626c7ee41bfabc29795abe2e1cd9267d8cbd66d98f81c4b26), Section 5.3, p.10 (PDF p.12)