Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Corollary 23 — every learner's expected ℓ∞^ε-robust error is ≥ (1 − 1/d)½ when n ≤ ε²σ²/(8 log d)

Proved
RobustGeneralization.GaussLower.corollary23_robust_error_lower_bound

by mikedeng1 · Sep 27, 2026 · Mathlib 0df444a (Lean v4.33.1)

adversarial-robustnesslower-boundp2o-batch-p200ap2o-gran-per-chapterp2o-plan-paperp2o-v1sample-complexity

Let gng_ngn​ be any learning algorithm, that is, a map from n≥0n \ge 0n≥0 samples in Rd×{±1}\mathbb R^d \times \{\pm 1\}Rd×{±1} to a binary classifier fnf_nfn​. Let σ>0\sigma > 0σ>0 and ε≥0\varepsilon \ge 0ε≥0. Draw θ∼N(0,I)\theta \sim \mathcal N(0, I)θ∼N(0,I), then draw nnn i.i.d. samples from the (θ,σ)(\theta, \sigma)(θ,σ)-Gaussian model, and set fn=gn(samples)f_n = g_n(\text{samples})fn​=gn​(samples). If

n ≤ ε2σ28log⁡d,n \ \le\ \frac{\varepsilon^2 \sigma^2}{8 \log d},n ≤ 8logdε2σ2​,

then the expected ℓ∞ε\ell_\infty^\varepsilonℓ∞ε​-robust classification error of fnf_nfn​, averaged over θ\thetaθ and the samples, is at least

(1−1d)12.\Big(1 - \frac1d\Big)\frac12 .(1−d1​)21​.

This is the paper's lower bound for the Gaussian model. With σ=c1d1/4\sigma = c_1 d^{1/4}σ=c1​d1/4, the sample size at which standard learning succeeds, robust learning needs on the order of ε2d/log⁡d\varepsilon^2\sqrt d/\log dε2d​/logd samples to get below error 12\frac1221​. That is a polynomial gap in ddd 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. log⁡\loglog is the natural logarithm, and Lean's conventions log⁡0=log⁡1=0\log 0 = \log 1 = 0log0=log1=0 and x/0=0x/0 = 0x/0=0 apply. So for d∈{0,1}d \in \{0, 1\}d∈{0,1} the hypothesis forces n=0n = 0n=0. The bound is then 12\frac1221​ at d=0d = 0d=0 (the space R0\mathbb R^0R0 is a point) and 000 at d=1d = 1d=1, 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.

Preamble
import Mathlib
import Definitions.Def_RobustGeneralization_GaussLower_Model

open MeasureTheory ProbabilityTheory
open scoped ENNReal
Formal statement
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
Source
Schmidt, Santurkar, Tsipras, Talwar, Mądry, Adversarially Robust Generalization Requires More Data, arXiv:1804.11285v2, p. 30, Corollary 23
Human review
  • Endorsed by Shuze Chen · Sep 27, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Sep 27, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me