What a Machine Learning Textbook's Contents Page Says About the Field

Translation pending — read the English original while we localise.

Foundations of Machine Learning (second edition, MIT Press, 2018) by Mehryar Mohri, Afshin Rostamizadeh and Ameet Talwalkar defines learning as using experience to make accurate predictions, building a rigorous curriculum around sample complexity, Rademacher bounds, and theoretical guarantees.

Most books about machine learning begin with a promise about what you'll be able to build. This one begins with a definition and a list of the quantities that govern whether a learner succeeds. That ordering tells you what the authors think the subject is, and I think it's the right call. A field that sells itself on prediction owes its readers an account of when prediction can be trusted, and that account is what the book sets out to give.

This article reads the book through what its front matter, preface and opening pages actually say. That's a narrower exercise than reviewing every chapter, and it's honest about its limits: the sources here are the title page, the table of contents, the preface and the first stretch of the introduction. Within those limits there's a clear argument to follow. It concerns what machine learning is, what it depends on, what the authors chose to cover and what they chose to leave out.

A book with a precise pedigree #

Start with the facts that anchor the object. The book is titled Foundations of Machine Learning, and this is the second edition. It belongs to the Adaptive Computation and Machine Learning series, whose editor is Francis Bach. The authors are Mehryar Mohri, Afshin Rostamizadeh and Ameet Talwalkar. The publisher is The MIT Press, Cambridge, Massachusetts, and the copyright is held by the Massachusetts Institute of Technology, dated 2018. The hardcover edition carries ISBN 9780262039406.

Two production details are worth a sentence each. The book was set in LaTeX by the authors themselves, which fits a text dense with bounds, definitions and proofs, and it was printed and bound in the United States of America. Neither detail changes how you'd read the mathematics. But authors who typeset their own book have had their hands on every page, and in a book of this kind that is reassuring.

The origin of the material matters more. Most of it takes its origins in a graduate course, also called Foundations of Machine Learning, taught by the first author at the Courant Institute of Mathematical Sciences in New York University over the last fourteen years. That's a specific, checkable provenance. A textbook that grew out of fourteen years of teaching one course has presumably been shaped by what students found hard, and the exercises and appendices described below read that way. I'd be careful not to push the inference further than the source allows. The preface says where the material came from, and it doesn't say how many revisions the course went through or what students struggled with. What it does say is enough: this is course material, not a survey assembled from the literature.

The definition that does the heavy lifting #

Everything downstream depends on one sentence. Machine learning, the authors write, can be broadly defined as computational methods using experience to improve performance or to make accurate predictions.

Each noun in that sentence has work to do. "Computational methods" places the subject inside computer science. "Experience" is then pinned down: it refers to the past information available to the learner. The sentence leaves out any claim that the learner understands anything, and it says nothing about intelligence. A learner has past information and a target, which is improved performance or accurate prediction, and the whole discipline is about the relationship between the two.

I'd argue this is a more useful definition for technical readers and founders than the grander ones in circulation, because it points straight at the levers you control. If learning is a function of past information, then your use over the outcome sits in what information you collect and how much of it. The next claim in the text says as much: the quality and size of the data are crucial to the success of the predictions made by the learner. That statement is demonstrated in the text as a plain mechanism, with no qualifiers attached.

The authors also describe the techniques themselves. They are data-driven methods combining fundamental concepts in computer science with ideas from statistics, probability and optimization. That sentence doubles as a prerequisites list and a map of the field's neighbours. A team that wants to build learning systems is drawing on computer science, statistics, probability and optimization together. Treating any one of them as optional is a choice the book doesn't endorse.

One worked example: documents and topics #

The introduction grounds the definition in a concrete learning problem. Take a finite sample of randomly selected documents, each labelled with a topic. The task is to use that sample to predict the topic of unseen documents.

The setup repays a slow reading. The sample is finite, so the learner never sees everything. The documents are randomly selected, which is what lets a finite sample say something about the unseen ones. Each is labelled with a topic, so the learner has supervision. And the target is documents it hasn't seen, which is the difference between predicting and memorising.

The authors then draw out two things that make the task easier or harder. The first is size: clearly, the larger the sample, the easier the task. The second is label quality. The difficulty of the task also depends on the quality of the labels assigned to the documents in the sample, since the labels may not all be correct, and on the number of possible topics.

That sentence contains three separate dials. Sample size is one. Label correctness is another. The number of possible topics is the third. None of them is about the algorithm. They're all properties of the problem and the data, and they decide how hard the problem is before any method is chosen. For a founder deciding where to spend a budget, this is a pointed observation. If you can improve the labels or enlarge the sample, you're acting on the factors the authors name explicitly as determining difficulty.

The example also names its own task. Predicting the label of a document is also known as document classification, and the authors are quick to add that it's by no means the only learning task. That caution is easy to skip past. The document example is a vehicle, and the claim underneath it is general.

Three complexities, not two #

Here the book makes its most distinctive move, and it's easy to miss because it arrives as a short remark. Machine learning, the authors say, consists of designing efficient and accurate prediction algorithms. As in other areas of computer science, time and space complexity are critical measures of the quality of such algorithms. Anyone who has studied algorithms will recognise those two. How long does it take, and how much memory does it need?

Then comes the addition. Machine learning needs, additionally, a notion of sample complexity to evaluate the sample size required for the algorithm to learn a family of concepts. This is the measure that has no counterpart in a sorting routine. A sorting algorithm doesn't need to be told how many examples it requires. A learner does, because its output is a prediction about cases it hasn't seen, and the amount of experience behind that prediction is part of what you're paying for.

I'd put it this way: time and space tell you what an algorithm costs to run, and sample complexity tells you what it costs to teach. A learner that's fast but needs an impractically large sample isn't efficient in any sense that matters to the person collecting the data. Putting the third measure beside the other two is the book's way of saying that data is a resource with a price, to be budgeted like compute and memory.

The text continues in the same direction. More generally, theoretical learning guarantees for an algorithm depend on the complexity of the concept classes considered and the size of the training sample. That is a compact statement of what a guarantee is made of. There are two inputs, how rich the family of concepts is and how much training data you have, and a guarantee is a statement relating them to performance. Notice what this implies about the book's structure. The chapters that follow have to supply ways of measuring the complexity of a concept class, and the table of contents shows they do.

The authors also explain why the field sits where it does. Since the success of a learning algorithm depends on the data used, machine learning is inherently related to data analysis and statistics. The mechanism is stated plainly: success depends on data, therefore the subject is entangled with the disciplines that study data. I find this the most honest sentence in the introduction. It doesn't present statistics as a rival or an ancestor. It presents statistics as a consequence of what learning depends on.

Dimension	Time Complexity	Space Complexity	Sample Complexity
Operational Definition	Asymptotic running time required to output hypothesis $h$	Memory footprint necessary during training and evaluation	Number of training examples $m$ required to learn concept family
Governing Theory	Computational complexity (P vs NP, hardness of training)	Architecture memory constraints and cache locality	PAC learning, Rademacher complexity, and VC-dimension
Cost Implication	Server compute and GPU/CPU inference budget	RAM and on-chip SRAM capacity	Data collection, annotation, and labelling cost
Theoretical Role	Measures algorithmic runtime efficiency	Measures space resource efficiency	Determines generalization error and bounds over unseen data

The theoretical spine #

The preface states how the book is built. The first three or four chapters lay the theoretical foundation for the subsequent material. The table of contents lets us see what that foundation is made of, at least by title.

The first chapter in the contents list is titled "The PAC Learning Framework", and within it appear sections titled "Guarantees for finite hypothesis sets - consistent case" and "Guarantees for finite hypothesis sets - inconsistent case". The section names tell us two things. One is that the framework produces guarantees, which matches the introduction's emphasis. The other is that the guarantees are split by whether the case is consistent or inconsistent, and the book treats the two separately. I won't speculate about what the consistent and inconsistent cases contain, because the sources here give only the section titles. But the pairing shows the authors don't present a single clean theorem and move on. They give the harder, messier case its own section.

The next chapter listed is "Rademacher Complexity and VC-Dimension". Its sections cover Rademacher complexity, growth function, VC-dimension and lower bounds. Read against the introduction, this chapter is the natural answer to a question the introduction raises. If guarantees depend on the complexity of the concept classes considered, you need tools for measuring that complexity. Rademacher complexity, the growth function and the VC-dimension are listed as the sections that carry this load. The inclusion of lower bounds in the section list is also worth noting. A book that presents only upper bounds tells you what's achievable. One that includes lower bounds also tells you what isn't.

Then comes chapter 4, "Model Selection", with sections including empirical risk minimization (ERM) and structural risk minimization (SRM). We'll return to this chapter when we look at the second edition, because it's one of the places the new edition changes the most.

The structure is deliberate. Foundations first, then the machinery for measuring complexity, then model selection, and only after that the algorithms. It's a defensible way to teach, and it matches the book's own account of how it works: the opening chapters lay the theory, and the rest builds on it.

From theory to algorithms: support vector machines and kernels #

The contents list also names the algorithmic chapters that follow. One is titled "Support Vector Machines", with separable-case and non-separable-case sections. Each of those sections covers the primal optimization problem, support vectors and the dual optimization problem. Another is titled "Kernel Methods".

The shape of the support vector machine chapter is itself informative. The same three topics appear under both the separable and non-separable headings: the primal optimization problem, the support vectors and the dual optimization problem. That repetition suggests a parallel treatment, the same questions asked twice under different assumptions. The parallel mirrors the consistent and inconsistent split in the PAC chapter, so a pattern emerges across the book: a clean case first, then the case where the clean assumption fails.

I'd be wary of reading too much into a table of contents. It can tell us what the book covers and how it divides the material. It can't tell us how well any section is written, and nothing in these sources says so. What it does show is that the optimization language in the support vector machine chapter, primal and dual, links back to the introduction's description of the techniques as combining computer science with ideas from statistics, probability and optimization. The optimization strand of that list shows up concretely in these section titles.

The book also reserves a separate chapter for each of multi-class classification, ranking, and regression. That is a design decision worth defending. It would have been easy to treat these as footnotes to binary classification. Giving each a chapter of its own signals that the authors regard them as distinct problems with their own analysis, and it matches the stated goal of a unified presentation of multiple topics rather than a presentation favouring one viewpoint.

What the book chooses not to cover #

The most interesting passage in the preface is about omission. The book, the authors say, is a general introduction to machine learning that can serve as a reference book for researchers and a textbook for students. Having made that broad claim, they add a limit: they have chosen to omit a few important topics, including graphical models and neural networks.

Few textbooks say this so directly, and I'd argue the candour is a strength. A reader who knows in advance what is missing can plan around it. Someone who needs neural networks knows to look elsewhere, rather than discovering the gap in chapter nine.

The reasons are stated too. The omission is both for the sake of brevity and because of the current lack of solid theoretical guarantees for some methods. Two reasons are given. Brevity is a practical constraint on any book. The second reason is the one that tells you something about the book's philosophy.

Connect it back to the introduction. Theoretical learning guarantees are what this book is organised around. The guarantees depend on the complexity of concept classes and the size of the training sample, and the theoretical chapters come first because everything else is built on them. A method for which solid guarantees are currently lacking sits awkwardly in a book built this way. So the omission follows from the book's central commitment. It is consistent with the definition of the subject the authors chose to open with.

There is a point of care here. The text says "some methods", so the claim is about the lack of solid guarantees for some methods, not for all of the omitted topics, and it says "current", which ties the judgement to the time of writing. I'd resist the temptation to summarise this as "neural networks have no theory". That isn't what the source says. It says the guarantees for some methods are currently lacking, and that this, together with brevity, was why graphical models and neural networks were left out.

For technical readers choosing what to study, the practical consequence is simple. This book gives you the vocabulary of guarantees, and it tells you plainly which areas it doesn't cover.

What the second edition changes #

The second edition is more than a reprint with corrections. The preface lists additions, and each one tells us where the authors thought the first edition was thin.

The headline change is a full chapter on model selection, chapter 4, on a topic that the authors describe as important and that was only briefly discussed in the previous edition. The language is direct. They don't claim the first edition covered it well. They say it was only briefly discussed and that they've now given it a full chapter. The sections include empirical risk minimization (ERM) and structural risk minimization (SRM), as the contents list shows.

Why does model selection deserve the promotion? The sources don't say, and I won't invent a reason on the authors' behalf. But the placement is telling. Chapter 4 follows directly after the chapters on the PAC framework and on Rademacher complexity and VC-dimension, which put it inside what the preface calls the first three or four chapters that lay the theoretical foundation. So the authors didn't append model selection as an afterthought. They built it into the theoretical foundation.

The next additions are a new chapter on Maximum Entropy models, chapter 12, and a new chapter on Conditional Maximum Entropy models, chapter 13. Two entirely new chapters is a substantial expansion, and the book now devotes consecutive chapters to the pair.

The appendices change as well. The authors have added a full section on Fenchel duality to appendix B on convex optimization, and they have added appendix E on information theory. The book also includes an extensive appendix presenting a concise review of linear algebra. These changes point in a consistent direction: the supporting mathematics has grown alongside the chapters. Fenchel duality joins the convex optimization appendix, and information theory gets its own appendix. I'd resist saying that information theory is there specifically to support the Maximum Entropy chapters, since the sources state no such link, and the two additions appear in the preface as separate items. Their timing, in the same edition, is a coincidence I'll leave as one.

Who the book is for, and how it expects to be read #

The book states its audience: it is intended for students and researchers in machine learning, statistics and other related areas. That list includes statistics by name, which echoes the introduction's point that machine learning is inherently related to data analysis and statistics.

It also states what it assumes. The reader is expected to be familiar with basic concepts in linear algebra, probability, and analysis of algorithms. That is a short list, and it matches the introduction's list of ingredients, though not exactly. The introduction names computer science, statistics, probability and optimization as the sources of the techniques. The prerequisites name linear algebra, probability and analysis of algorithms. Optimization isn't among the prerequisites, and the book addresses that from the other side: appendix B covers convex optimization, with the new Fenchel duality section. Linear algebra is expected as background, and the book still provides the extensive appendix reviewing it. So the prerequisites and the appendices overlap by design, and a reader whose linear algebra has gone rusty has a concise review inside the same covers.

The pedagogy is stated plainly as well. Each chapter concludes with a series of exercises, with full solutions presented separately. That's a sensible arrangement for a book serving two audiences. A student can attempt the exercises and check against the solutions, and a researcher using the book as a reference isn't forced past worked answers on every page. Whether the solutions arrive as a separate volume or some other document, the source doesn't say, only that they're presented separately, so I'll leave that there.

Taken together, the audience, the prerequisites, the exercises and the appendices describe a book designed to be worked through. The fourteen years of teaching at the Courant Institute stand behind this design. A course that has been taught repeatedly tends to produce this kind of apparatus, though the preface doesn't claim that connection explicitly, and I'm offering it only as a reading of the evidence, not a finding.

The applications are broad, and the book says so #

A book this theoretical could be mistaken for something remote from practice. The introduction heads that off with a plain statement: machine learning admits a very broad set of practical applications. The one it names is text or document classification, which includes spam detection.

Spam detection is a good choice of example for a reason the authors' own framework explains. It's a document classification problem in exactly the sense of the earlier example: labelled documents in, predictions about unseen documents out. The sample-size and label-quality factors apply to it directly. A larger sample makes the task easier, and mislabelled messages make it harder. The number of possible categories is small, which, by the logic of the earlier passage, also bears on difficulty. I'm applying the book's stated factors to its stated example, and I'm not claiming anything about spam filters in the wild.

There's also a quiet argument in the placement of this passage. The authors introduce document classification as a learning task and then immediately note that it's by no means the only one. The applications are broad because the underlying definition is broad. Anything that fits "computational methods using experience to improve performance or to make accurate predictions" qualifies. That generality is also why the book bothers with theory. A framework meant to cover a very broad set of applications can't be tied to the details of any one, and guarantees stated in terms of concept-class complexity and sample size are exactly the kind that travel between problems.

The bet the book makes #

Pull the threads together and a coherent position emerges, which is more than the contents page of most textbooks can claim. The book defines learning in terms of experience and prediction. It names three complexities, time, space and sample, as the measures of quality. It ties guarantees to concept-class complexity and sample size, and it puts the theory that supplies those guarantees at the front. It then builds the algorithmic chapters on that base and says openly which popular areas it leaves out because the guarantees for some methods are, for now, not solid.

This is a bet on theory as the thing that lasts. I can see why a team of authors who spent years teaching a graduate course would make it. The bet has a cost, and the authors name it: the omissions of graphical models and neural networks are the price of insisting on solid guarantees. A reader should weigh that cost honestly. If your work is dominated by the omitted areas, this book is a foundation rather than a manual. If your work needs to reason about whether a learner will generalise from a finite sample, the book's vocabulary is the point of it.

For founders, the useful takeaway is the least glamorous one. The quality and size of the data are crucial to the success of the predictions, and the difficulty of a task depends on label quality and on the number of possible topics. Those are statements about inputs you can often influence. The book doesn't promise that any particular algorithm will rescue a thin or mislabelled sample, and it's right not to.

For technical readers, the more interesting question is the one the preface leaves open. The authors omitted some methods because of the current lack of solid theoretical guarantees. The word "current" frames that as a state of affairs at the time of writing, and the sources don't say whether, or how, it might change. What would it take for those guarantees to become solid enough to earn a chapter? The book can't answer that. By being exact about what it leaves out and why, it at least shows where to look.

What This Means by Sector #

The insistence on statistical learning guarantees and sample complexity provides actionable boundaries across several software and research domains.

Academic machine learning and curriculum design #

Pedagogical programmes must resist the pressure to treat machine learning as empirical prompt engineering or framework plumbing. Grounding students in the PAC framework, Rademacher complexity, and structural risk minimization establishes durable mathematical instincts that survive the churn of transient deep learning architectures.

Enterprise AI engineering and data valuation #

Engineering organisations deploying predictive systems often over-allocate capital to compute (model scale) while neglecting sample complexity and label fidelity. Because generalization error is bound strictly by the concept-class complexity relative to sample size, teams achieve superior ROI by investing in clean annotation and sample auditing rather than larger unregularized models.

Frontier AI research and model auditing #

As regulatory frameworks such as the EU AI Act mandate predictable bounds on automated decision systems, the statistical learning guarantees formalized in Foundations of Machine Learning become compliance necessities. Regulators and safety auditors require provable generalization bounds and rigorous model selection protocols rather than heuristic validation scores.

Conclusion #

Foundations of Machine Learning remains an indispensable anchor in a field frequently tempted by raw empiricism. By constructing an entire curriculum around PAC learning, Rademacher complexity, and VC-dimension, Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar remind researchers that algorithmic elegance cannot substitute for mathematical guarantees. The authors' candid omission of neural networks and graphical models due to the absence of closed-form guarantees is not a flaw - it is the book's defining strength, clearly demarcating what the discipline can rigorously prove from what it merely observes.

Questions ? Réponses.

Why did the authors omit neural networks and graphical models from the second edition?

The authors deliberately omitted neural networks and graphical models for the sake of brevity and because of the contemporary lack of solid theoretical guarantees for several of those methods. The book is organized strictly around algorithms that admit rigorous generalization bounds.

What distinguishes sample complexity from time and space complexity?

While time complexity evaluates execution speed and space complexity measures memory consumption, sample complexity quantifies the mathematical volume of training data an algorithm requires to learn a family of concepts within specified error and confidence tolerances.

What is the core distinction between empirical risk minimization and structural risk minimization?

Empirical risk minimization (ERM) selects the hypothesis that minimizes training error directly, risking overfitting when hypothesis complexity is high. Structural risk minimization (SRM) balances training error against hypothesis complexity (such as VC-dimension or Rademacher complexity), providing formal bounds on generalization risk.

References #

Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar, (2018). Foundations of Machine Learning, Second Edition ⧉. The MIT Press.
Leslie G. Valiant, (1984). A Theory of the Learnable ⧉. Communications of the ACM.
Vladimir N. Vapnik, (1998). Statistical Learning Theory ⧉. John Wiley & Sons.

Dernière révision 2026-10-10.

Dernière révision 2026-10-16.

Republier cet article

What a Machine Learning Textbook's Contents Page Says About the Field — Sebastien Rousseau

Foundations of Machine Learning (second edition, MIT Press, 2018) by Mehryar Mohri, Afshin Rostamizadeh and Ameet Talwalkar treats machine learning as the design of efficient and accurate...

Cet article est sous licence Creative Commons Attribution 4.0 International. La republication nécessite l'attribution à l'URL canonique.

What a Machine Learning Textbook's Contents Page Says About the Field — Sebastien Rousseau

Foundations of Machine Learning (second edition, MIT Press, 2018) by Mehryar Mohri, Afshin Rostamizadeh and Ameet Talwalkar treats machine learning as the design of efficient and accurate...

Originally published at https://sebastienrousseau.com/fr/2026-10-10-what-machine-learning-textbook-contents-page/ by Sebastien Rousseau.
Licensed under CC-BY-4.0.

SEBASTIEN ROUSSEAU FONDATEUR · INGÉNIEUR