Lemma 8, p. 13 — COA instances attaining √(2c²+2)/(1+c) for consistency and √(2c²+2)/(1−c) for robustness
ProvedLearnAugFL.CMP.lemma_8Throughout, 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 .
Let be a confidence for which some instance size is admissible ( for some ). Then
- there is an instance with
- and an instance with
In the paper the instances are: points at each of and at ; respectively at each of and at . They show that the bounds of Theorem 9 are tight.
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 quantifies over all but every instance requires ; the hypothesis that some makes an integer (i.e. is rational) is that standing assumption made explicit. The instances may have any number of agents.
import Mathlib import Definitions.Def_LearnAugFL_CMP_Setting
namespace LearnAugFL.CMP
theorem lemma_8 (c : ℝ) (hc0 : 0 ≤ c) (hc1 : c < 1) (hc : ∃ n₀ k₀ : ℕ, Admissible c n₀ k₀) :
(∃ (n k : ℕ) (P : Fin n → Pt), COA_C c n k P ∧
ratio P !₂[0, 1] !₂[0, 1] k = Real.sqrt (2 * c ^ 2 + 2) / (1 + c)) ∧
(∃ (n k : ℕ) (Q : Fin n → Pt), COA_R c n k Q ∧
ratio Q 0 !₂[0, 1] k = Real.sqrt (2 * c ^ 2 + 2) / (1 - c)) := by sorry
end LearnAugFL.CMP
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.