Theorem 31 — every linear learner has expected ℓ∞^ε-robust error ≥ ½ − γ when n ≤ ε²γ²/(5000 τ⁴ log(4d/γ))
ProvedRobustGeneralization.BernLower.theorem31_linear_robust_error_lower_boundLet be a linear-classifier learning algorithm, i.e. any function that maps samples from to a weight vector . Choose uniformly at random from and draw independent samples from the -Bernoulli model, where ; let . Let and . If
then the linear classifier has expected -robust classification error at least :
With and constant this says that linear classifiers need on the order of samples (up to logarithmic factors) to be -robust in the Bernoulli model, while a single sample suffices for standard accuracy; it is the explicit form of the paper's Theorem 9.
Formalization Note The learner sees only the samples, never , and the error is averaged over the uniform prior on . The tie is classified as . The hypothesis is added: for the ball is empty, the robust error is , and the printed statement fails at . At , in Lean makes the right-hand side of the sample bound , forcing , where the claim holds.
import Mathlib import Definitions.Def_RobustGeneralization_BernLower_Model
namespace RobustGeneralization.BernLower
theorem theorem31_linear_robust_error_lower_bound (d n : ℕ)
(g : (Fin n → (Fin d → Bool) × Bool) → E d) (τ ε γ : ℝ)
(hτ : 0 < τ) (hτ' : τ ≤ 1 / 4) (hε : 0 ≤ ε) (hε' : ε < 3 * τ)
(hγ : 0 < γ) (hγ' : γ < 1 / 2)
(hn : (n : ℝ) ≤ ε ^ 2 * γ ^ 2 / (5000 * τ ^ 4 * Real.log (4 * d / γ))) :
1 / 2 - γ ≤ expRobErr g τ ε := by sorry
end RobustGeneralization.BernLower
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.