Corollary 23 — every learner's expected ℓ∞^ε-robust error is ≥ (1 − 1/d)½ when n ≤ ε²σ²/(8 log d)
ProvedRobustGeneralization.GaussLower.corollary23_robust_error_lower_boundLet be any learning algorithm, that is, a map from samples in to a binary classifier . Let and . Draw , then draw i.i.d. samples from the -Gaussian model, and set . If
then the expected -robust classification error of , averaged over and the samples, is at least
This is the paper's lower bound for the Gaussian model. With , the sample size at which standard learning succeeds, robust learning needs on the order of samples to get below error . That is a polynomial gap in between standard and robust generalization.
Formalization Note The learner is a function of the samples only, and is required to be jointly measurable in (samples, input); this is the only condition on it. is the natural logarithm, and Lean's conventions and apply. So for the hypothesis forces . The bound is then at (the space is a point) and at , and both are true. The expected error is the one in the definitions file: a lower integral of outer probabilities, so a lower bound on it is the strong form.
import Mathlib import Definitions.Def_RobustGeneralization_GaussLower_Model open MeasureTheory ProbabilityTheory open scoped ENNReal
namespace RobustGeneralization.GaussLower
theorem corollary23_robust_error_lower_bound (d n : ℕ)
(g : (Fin n → E d × Bool) → E d → Bool)
(hg : Measurable (fun q : (Fin n → E d × Bool) × E d => g q.1 q.2))
(σ ε : ℝ) (hσ : 0 < σ) (hε : 0 ≤ ε)
(hn : (n : ℝ) ≤ ε ^ 2 * σ ^ 2 / (8 * Real.log d)) :
ENNReal.ofReal ((1 - 1 / (d : ℝ)) * (1 / 2)) ≤ expRobErr g σ ε := by sorry
end RobustGeneralization.GaussLower
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.