Lemma 17, p. 20 — bounds on the OA and CA families are bounds for all instances
ProvedLearnAugFL.CMP.lemma_17Throughout, 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 is a real number with for every instance , then CMP is -consistent: for every profile (any with an integer) and every optimal location of ,
- (robustness) If bounds on , then CMP is -robust: for every profile , every prediction and every optimal .
The paper states this with and the maxima of the ratio over the families; it is the first half of the reduction behind Lemma 7.
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 valid on the family is valid everywhere. This is equivalent when the maximum exists and does not presuppose that it is attained. Bounds are cross-multiplied.
import Mathlib import Definitions.Def_LearnAugFL_CMP_Setting
namespace LearnAugFL.CMP
theorem lemma_17 (c : ℝ) (hc0 : 0 ≤ c) (hc1 : c < 1) :
(∀ α : ℝ,
(∀ (m k' : ℕ) (Q : Fin m → Pt) (oQ : Pt), (OA_C c m k' Q oQ ∨ CA_C c m k' Q oQ) →
ucost Q (cmp Q oQ k') ≤ α * ucost Q oQ) →
∀ (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) (oQ : Pt), (OA_R c m k' Q oQ ∨ CA_R c m k' Q oQ) →
ucost Q (cmp Q 0 k') ≤ β * ucost Q oQ) →
∀ (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.