Examples 12.8–12.9: linear regression on ℝ with the squared loss is not (agnostic) PAC learnable, neither over H = ℝ nor over H = [−1, 1]

Proved

UnderstandingML.linear_regression_not_learnable

by naimengye · Sep 24, 2026 · Mathlib 0df444a (Lean v4.33.1)

convex-learninglinear-regressionnonlearnability

Example 12.8 (Nonlearnability of Linear Regression Even If $d = 1$ ). Let $H = \mathbb{R}$ and the loss be the squared loss $\ell(w,(x,y)) = (wx - y)^2$ . For every deterministic algorithm $A$ there is a distribution on which $A$ fails; the problem is not PAC learnable. Example 12.9. The same holds for the bounded convex class $H = \{w : |w| \le 1\}$ .

Formally: AgnosticPACLearnable squaredLoss1 H fails for $H = \mathbb{R}$ and for $H = [-1, 1]$ (the learners of Definition 3.4 are deterministic).

Preamble

import Definitions.Def_UnderstandingML_Convex

open MeasureTheory
open scoped InnerProductSpace

Formal statement

namespace UnderstandingML

/-- **Examples 12.8–12.9** (pp. 164–166): nonlearnability of linear regression even if `d = 1`.
With `H = ℝ` and the squared loss `ℓ(w, (x, y)) = (wx − y)²`, the problem is not (agnostic) PAC
learnable; and neither is it with the bounded convex class `H = {w : |w| ≤ 1}`. (The learners of
Definition 3.4 are deterministic, as the book assumes.) -/
theorem linear_regression_not_learnable :
    ¬ AgnosticPACLearnable squaredLoss1 (Set.univ : Set ℝ) ∧
    ¬ AgnosticPACLearnable squaredLoss1 (Set.Icc (-1 : ℝ) 1) := by sorry

end UnderstandingML

Source

Shalev-Shwartz and Ben-David, Understanding Machine Learning: From Theory to Algorithms, Cambridge University Press 2014, doi:10.1017/CBO9781107298019, §12.2.1 pp. 164-166, Examples 12.8 and 12.9 with their proofs

Human review

Endorsed by Shuze Chen · Sep 25, 2026
Confirmed by the moderator at approval.
Endorsed by naimengye · Sep 25, 2026
Confirmed by the mission captain (proposal self-audit).

View graph