Lemma 7, p. 13 — the worst case of CMP lies in the Clusters-and-Opt-on-Axes classes
ProvedLearnAugFL.CMP.lemma_7Throughout, carries the Euclidean distance ; is a profile of preferred locations; is a confidence parameter with an integer; is the utilitarian social cost; is an optimal (cost-minimizing) location; and is the location chosen by the Coordinatewise Median with Predictions (CMP): each coordinate is the lower median of the values formed by the agents' coordinates and copies of the prediction's coordinate. The ratio is .
Fix .
- (consistency) If satisfies for every (prediction ), then CMP is -consistent: for every profile and every optimal location of ,
- (robustness) If satisfies for every , then CMP is -robust: for every profile , prediction and optimal location .
Lemma 7 reduces the analysis of CMP to one-parameter families of instances; with Lemma 8 it gives Theorem 9.
Formalization Note The optimal location is taken as any with IsOpt P o (a minimizer of ; it is unique unless the points are collinear). The confidence enters through Admissible c n k: and copies of the prediction. Ratios are real quotients ratio P ô o k; on every family used here the optimal cost is positive (if all points sat at , CMP would return because ), so no ratio is a junk . The page's ", CMP is -consistent" is stated in implication form (every bound on the class is a bound everywhere), which does not presuppose that the maximum is attained. The proof on p. 22 ends "CMP is -consistent", a slip for -robust.
import Mathlib import Definitions.Def_LearnAugFL_CMP_Setting
namespace LearnAugFL.CMP
theorem lemma_7 (c : ℝ) (hc0 : 0 ≤ c) (hc1 : c < 1) :
(∀ α : ℝ,
(∀ (m k' : ℕ) (Q : Fin m → Pt), COA_C c m k' Q →
ucost Q (cmp Q !₂[0, 1] k') ≤ α * ucost Q !₂[0, 1]) →
∀ (n k : ℕ), Admissible c n k → ∀ (P : Fin n → Pt) (o : Pt), IsOpt P o →
ucost P (cmp P o k) ≤ α * ucost P o) ∧
(∀ β : ℝ,
(∀ (m k' : ℕ) (Q : Fin m → Pt), COA_R c m k' Q →
ucost Q (cmp Q 0 k') ≤ β * ucost Q !₂[0, 1]) →
∀ (n k : ℕ), Admissible c n k → ∀ (P : Fin n → Pt) (ô o : Pt), IsOpt P o →
ucost P (cmp P ô k) ≤ β * ucost P o) := by sorry
end LearnAugFL.CMP
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.