Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Collections

Understanding Machine Learning

Shalev-Shwartz and Ben-David's Understanding Machine Learning: PAC learning, VC dimension, and the fundamental theorem of statistical learning.

23 completed missions

Missions

1–23 of 23
Open0Completed23All23
🏆Completed
Machine LearningProbabilityStatistics·Captain: naimengye

Understanding Machine Learning XXV: PAC-BayesTextbook

The MDL and Occam principles of Chapter 7 rank hypotheses by description length and pay for a hypothesis according to its rank. Chapter 31 of Shalev-Shwartz and Ben-David, Understanding Machine Learning: From Theory to Algorithms (doi:10.1017/CBO9781107298019), generalizes this to the PAC-Bayesian approach of McAllester: prior knowledge is a prior…

6 thms4 active usersReviewed
🏆Completed
CombinatoricsMachine LearningOptimization·Captain: naimengye

Understanding Machine Learning XV: Neural NetworksTextbook

A feedforward neural network is a directed acyclic graph of neurons, each computing a fixed scalar activation of a weighted sum of its inputs; fixing the graph and the activation and letting the weights vary gives a hypothesis class. Chapter 20 of Shalev-Shwartz and Ben-David, Understanding Machine Learning: From Theory to Algorithms (doi:10.1017/CBO97811072…

8 thms4 active usersReviewed
🏆Completed
CombinatoricsMachine LearningProbability·Captain: naimengye

Understanding Machine Learning XXI: Covering NumbersTextbook

Chapter 26 bounded the rate of uniform convergence by the Rademacher complexity; Chapter 27 of Shalev-Shwartz and Ben-David, Understanding Machine Learning: From Theory to Algorithms (doi:10.1017/CBO9781107298019), introduces a second, metric measure of the size of a set of vectors, its covering numbers N(r,A)N(r, A)N(r,A), the smallest number of Euclidean balls of…

7 thms3 active usersReviewed
🏆Completed
Machine LearningProbabilityStatistics·Captain: naimengye

Understanding Machine Learning XIX: Generative ModelsTextbook

The book is discriminative almost throughout: it learns predictors, not distributions, following Vapnik's advice not to solve a more general problem as an intermediate step. Chapter 24 of Shalev-Shwartz and Ben-David, Understanding Machine Learning: From Theory to Algorithms (doi:10.1017/CBO9781107298019), presents the generative alternative: assume a…

11 thms3 active usersReviewed
🏆Completed
Machine LearningOptimizationProbability·Captain: naimengye

Understanding Machine Learning XVIII: Dimensionality ReductionTextbook

Dimensionality reduction maps data in Rd\mathbb{R}^dRd to Rn\mathbb{R}^nRn, n≪dn \ll dn≪d, by a linear map x↦Wxx \mapsto Wxx↦Wx, for computational reasons, for generalization (Chapter 19's curse of dimensionality) and for interpretability. Chapter 23 of Shalev-Shwartz and Ben-David, Understanding Machine Learning: From Theory to Algorithms (doi:10.1017/CBO9781107298019), studies…

7 thms3 active usersReviewed
🏆Completed
CombinatoricsMachine LearningOptimization·Captain: naimengye

Understanding Machine Learning XVII: ClusteringTextbook

Clustering is the most widely used tool of exploratory data analysis and, at the same time, the least well defined: similar points should share a cluster and dissimilar points should not, but similarity is not transitive while cluster membership is, and without labels there is no ground truth against which to evaluate a proposed grouping. Chapter 22 of…

7 thms3 active usersReviewed
🏆Completed
CombinatoricsMachine LearningProbability·Captain: naimengye

Understanding Machine Learning XXIV: Compression BoundsTextbook

The book has characterized learnability through uniform convergence and through stability; Chapter 30 of Shalev-Shwartz and Ben-David, Understanding Machine Learning: From Theory to Algorithms (doi:10.1017/CBO9781107298019), gives a third sufficient condition, compression: if a learning algorithm's output can be reconstructed from a small subsequence of kkk tr…

10 thms2 active usersReviewed
🏆Completed
CombinatoricsMachine LearningProbability·Captain: naimengye

Understanding Machine Learning XXIII: Multiclass LearnabilityTextbook

Chapter 17 introduced multiclass prediction; Chapter 29 of Shalev-Shwartz and Ben-David, Understanding Machine Learning: From Theory to Algorithms (doi:10.1017/CBO9781107298019), asks the two questions the fundamental theorem answered for binary classes: which classes of multiclass predictors are PAC learnable with respect to the 0–1 loss, and with what…

15 thms2 active usersReviewed
🏆Completed
CombinatoricsMachine LearningProbability·Captain: naimengye

Understanding Machine Learning XXII: Proof of the Fundamental TheoremTextbook

Chapter 6 stated the fundamental theorem of statistical learning: a binary class is learnable if and only if its VC dimension is finite, with sample complexity Θ((d+ln⁡(1/δ))/ϵ2)\Theta((d + \ln(1/\delta))/\epsilon^2)Θ((d+ln(1/δ))/ϵ2) in the agnostic case and Θ((dln⁡(1/ϵ)+ln⁡(1/δ))/ϵ)\Theta((d\ln(1/\epsilon) + \ln(1/\delta))/\epsilon)Θ((dln(1/ϵ)+ln(1/δ))/ϵ) in the realizable case. Chapter 28 of Shalev-Shwartz and Ben-David, Understanding…

11 thms2 active usersReviewed
🏆Completed
Machine LearningProbabilityStatistics·Captain: naimengye

Understanding Machine Learning XX: Rademacher ComplexitiesTextbook

Chapter 4 showed that uniform convergence suffices for learnability; Chapter 26 of Shalev-Shwartz and Ben-David, Understanding Machine Learning: From Theory to Algorithms (doi:10.1017/CBO9781107298019), measures its rate. The representativeness of a sample, sup⁡h∈H(LD(h)−LS(h))\sup_{h \in H}(L_D(h) - L_S(h))suph∈H​(LD​(h)−LS​(h)), is the quantity that controls the excess risk of ERM, and the…

10 thms2 active usersReviewed
🏆Completed
CombinatoricsMachine LearningOptimization·Captain: naimengye

Understanding Machine Learning XVI: Online LearningTextbook

In PAC learning the learner receives a batch of examples, learns, and only then predicts. Online learning has no such separation: on each round the learner receives an instance, predicts its label, and then sees the true label, and the goal is to make few mistakes over the whole sequence, with no statistical assumption whatsoever on how the sequence is…

10 thms2 active usersReviewed
🏆Completed
Machine LearningProbabilityStatistics·Captain: naimengye

Understanding Machine Learning XIV: Nearest NeighborTextbook

Every learning paradigm of the book so far, ERM, SRM, MDL, RLM, is defined by a hypothesis class: the learner searches a predefined set of functions. Nearest Neighbor is the first method that is not. It memorizes the training set and labels a new point by the labels of its closest neighbors, on the assumption that the features are relevant to the labels in…

9 thms2 active usersReviewed
🏆Completed
CombinatoricsMachine LearningOptimization·Captain: naimengye

Understanding Machine Learning XIII: Multiclass Prediction and RankingTextbook

Binary classification is the exception in practice; most prediction tasks have many labels, a structured label space, or ask for a ranking. Chapter 17 of Shalev-Shwartz and Ben-David, Understanding Machine Learning: From Theory to Algorithms (doi:10.1017/CBO9781107298019) extends linear predictors to these settings through one idea: a class-sensitive…

12 thms2 active usersReviewed
🏆Completed
Machine LearningOptimization·Captain: naimengye

Understanding Machine Learning XII: Kernel Methods and the Representer TheoremTextbook

Chapter 15 bounded the sample complexity of large-margin halfspaces by the norms of the data and of the separator, independently of the dimension. Chapter 16 of Shalev-Shwartz and Ben-David, Understanding Machine Learning: From Theory to Algorithms (doi:10.1017/CBO9781107298019) removes the remaining obstacle to using halfspaces in very high-dimensional…

8 thms2 active usersReviewed
🏆Completed
Machine LearningOptimizationStatistics·Captain: naimengye

Understanding Machine Learning XI: Support Vector Machines and MarginTextbook

The sample complexity of learning halfspaces in Rd\mathbb{R}^dRd grows with ddd, which is bad news when features are many or infinite. Chapter 15 of Shalev-Shwartz and Ben-David, Understanding Machine Learning: From Theory to Algorithms (doi:10.1017/CBO9781107298019) introduces the support vector machine, the learning rule that replaces dimension by geometry.…

15 thms2 active usersReviewed
🏆Completed
Machine LearningOptimizationProbability·Captain: naimengye

Understanding Machine Learning X: Gradient Descent, Subgradients and Stochastic Gradient DescentTextbook

Chapter 13 showed that convex-Lipschitz-bounded and convex-smooth-bounded problems are learnable by regularized loss minimization; Chapter 14 of Shalev-Shwartz and Ben-David, Understanding Machine Learning: From Theory to Algorithms (doi:10.1017/CBO9781107298019) shows how to learn them with the simplest possible algorithm. Gradient descent moves against…

12 thms2 active usersReviewed
🏆Completed
Machine LearningOptimizationProbability+1·Captain: naimengye

Understanding Machine Learning IX: Convex Learning Problems, Regularization and StabilityTextbook

Chapters 12 and 13 of Shalev-Shwartz and Ben-David, Understanding Machine Learning: From Theory to Algorithms (doi:10.1017/CBO9781107298019) leave binary classification for the general framework in which a hypothesis is a vector w∈Rdw \in \mathbb{R}^dw∈Rd and the loss ℓ(w,z)\ell(w, z)ℓ(w,z) is a convex function of www. Convexity makes the ERM problem tractable (Lemma 12.11), but…

13 thms2 active usersReviewed
🏆Completed
CombinatoricsMachine LearningStatistics·Captain: naimengye

Understanding Machine Learning VII: Boosting and AdaBoostTextbook

Boosting answers a question raised by Kearns and Valiant: can a learner that is only slightly better than random guessing be turned into one that is arbitrarily accurate? Chapter 10 of Shalev-Shwartz and Ben-David, Understanding Machine Learning: From Theory to Algorithms (doi:10.1017/CBO9781107298019) defines γ-weak learnability (Definition 10.1), the PAC…

8 thms2 active usersReviewed
🏆Completed
Machine LearningOptimizationStatistics·Captain: naimengye

Understanding Machine Learning VI: Linear Predictors, the Perceptron and Least SquaresTextbook

Part II of Shalev-Shwartz and Ben-David, Understanding Machine Learning: From Theory to Algorithms (doi:10.1017/CBO9781107298019) turns from the theory of learnability to hypothesis classes that can actually be learned by algorithms, and it starts with the family that almost every practical method is built on: linear predictors. Chapter 9 introduces the…

8 thms2 active usersReviewed
🏆Completed
Machine LearningProbabilityStatistics·Captain: naimengye

Understanding Machine Learning V: Nonuniform Learnability, Structural Risk Minimization and Minimum Description LengthTextbook

The fundamental theorem of Mission IV says that a class of binary classifiers is PAC learnable exactly when its VC-dimension is finite. That leaves out classes one would like to learn, such as all polynomial classifiers over the line, whose VC-dimension is infinite although each degree separately is learnable. Chapter 7 of Shalev-Shwartz and Ben-David, Under…

12 thms2 active usersReviewed
🏆Completed
Machine LearningProbabilityStatistics·Captain: naimengye

Understanding Machine Learning III: The No-Free-Lunch TheoremTextbook

Missions I and II of this series showed that finite hypothesis classes are learnable, with and without the realizability assumption, by empirical risk minimization. Chapter 5 of Shalev-Shwartz and Ben-David, Understanding Machine Learning: From Theory to Algorithms (doi:10.1017/CBO9781107298019) asks the converse question: is prior knowledge, in the form of…

5 thms2 active usersReviewed
🏆Completed
Machine LearningProbabilityStatistics·Captain: naimengye

Understanding Machine Learning II: Learning via Uniform ConvergenceTextbook

Mission I of this series set up the statistical learning framework of Shalev-Shwartz and Ben-David, Understanding Machine Learning: From Theory to Algorithms (doi:10.1017/CBO9781107298019) and proved, in the book's Chapters 2 and 3, that finite classes are PAC learnable under the realizability assumption. Chapter 4 removes that assumption. Its idea is the…

5 thms2 active usersReviewed
🏆Completed
Machine LearningProbabilityStatistics·Captain: naimengye

Understanding Machine Learning I: The Statistical Learning Framework, ERM and Finite ClassesTextbook

Chapters 2 and 3 of Shalev-Shwartz and Ben-David, Understanding Machine Learning: From Theory to Algorithms (Cambridge University Press, 2014, doi:10.1017/CBO9781107298019), set up the framework in which the whole book asks what learning is. A learner sees a sample drawn independently from an unknown distribution over examples, chooses a hypothesis from a…

3 thms2 active usersReviewed

Top contributors

RankContributorAccepted solutionsSubmitted problems
1GAGabewhigham1397
2NINickrobbins9580
3MRmrfancypants10
3WIWillR10
5NAnaimengye0205

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