Lemma 27, p. 23 — moving a point towards the optimum without changing CMP's output strictly worsens a ratio above 1
ProvedLearnAugFL.CMP.lemma_27Throughout, 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 , a prediction , a profile with optimal location , an agent with , and with (a point of the segment ). If CMP's output does not change, , and , then
where both ratios are measured against (which remains optimal for the new profile by Lemma 26).
The lemma drives every "move a point towards the optimum" step of the worst-case reduction.
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 hypothesis makes the segment nonempty, as the page presupposes.
import Mathlib import Definitions.Def_LearnAugFL_CMP_Setting
namespace LearnAugFL.CMP
theorem lemma_27 (c : ℝ) (hc0 : 0 ≤ c) (hc1 : c < 1) {n k : ℕ} (hnk : Admissible c n k)
(P : Fin n → Pt) (ô o : Pt) (hP : IsOpt P o) (i : Fin n) (hi : P i ≠ o)
(s : ℝ) (hs0 : 0 < s) (hs1 : s ≤ 1)
(hf : cmp P ô k = cmp (Function.update P i (P i + s • (o - P i))) ô k)
(hr : 1 < ratio P ô o k) :
ratio P ô o k < ratio (Function.update P i (P i + s • (o - P i))) ô o k := by sorry
end LearnAugFL.CMP
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.