Machine Learning. The Science of Selection under Uncertainty

Yevgeny SeldinarXiv 2025 · DOI · arXiv

Introduction

The fundamental challenge of machine learning is the transition from training performance to real-world reliability. When a model performs well on a specific dataset, how can we guarantee it will generalize to unseen data? In "Machine Learning: The Science of Selection under Uncertainty," Yevgeny Seldin frames learning not merely as optimization, but as a rigorous process of selection. By viewing the learner as an agent choosing from a set of candidate hypotheses based on noisy, finite observations, the text establishes a statistical foundation for quantifying the risk of a model "getting lucky" during training.

The Science of Selection

Seldin illustrates the core problem of machine learning through the "Archer Analogy." Imagine selecting an archer for a competition based on a single trial shot. If you observe thousands of mediocre archers, one will eventually hit the bullseye by pure chance. In machine learning, the "archers" are prediction rules (hypotheses). If the hypothesis space is large enough, some models will inevitably fit the training data perfectly without capturing the underlying patterns. ML theory, therefore, is the science of ensuring that the selected model is truly skilled rather than merely fortunate.

Theoretical Foundations: Concentration of Measure

To provide formal guarantees, the book builds upon concentration of measure inequalities. While standard tools like Markov’s and Hoeffding’s inequalities provide a baseline, the text emphasizes more sophisticated tools that allow for tighter bounds:

  • kl-divergence based bounds: These offer more nuanced guarantees by providing a tighter relationship between observed and true error than simple linear bounds.
  • Bernstein Inequalities: Unlike range-based bounds that can be overly pessimistic, Bernstein inequalities exploit the variance of the data. If a model’s errors are consistent (low variance), these tools allow for "fast convergence rates," where the error bound shrinks rapidly as more data is acquired.

PAC-Bayesian Analysis and Soft Selection

A significant portion of the work is dedicated to PAC-Bayesian analysis. Traditional Vapnik-Chervonenkis (VC) theory often evaluates the "richness" or complexity of an entire class of models. In contrast, PAC-Bayes allows for "soft selection." By assigning a distribution (a prior and a posterior) over the hypothesis space, PAC-Bayes rewards models that align with prior knowledge and penalizes over-commitment to a single, potentially overfitted hypothesis.

One of the text's novel contributions is the Recursive PAC-Bayes-split-kl Inequality. In many learning scenarios, models are updated sequentially. Traditional bounds often suffer from "information leakage," where the confidence accumulated from previous data is lost during an update. Recursive PAC-Bayes uses a clever decomposition to preserve this confidence across multiple updates, making it a vital tool for life-long learning systems.

Online Learning and the "Bandit Magic"

The principles of selection extend beyond batch learning into online environments where data arrives in a stream. The book analyzes the "regret" of algorithms—the difference between the algorithm's cumulative performance and the best possible strategy in hindsight.

  • EXP3 and UCB1: The text explores these classic algorithms within the multi-armed bandit framework, focusing on how to balance exploration and exploitation.
  • Importance Weighting: Seldin describes the "magic" of importance weighting in bandit settings. Since we only observe the outcome of the action taken, we lack full information. Importance weighting allows for the creation of unbiased estimates of what would have happened if different choices had been made, effectively emulating a full-information environment from partial feedback.

Empirical Context and Results

Although theoretical in nature, the book grounds its concepts in practical benchmarks to illustrate how these bounds behave in real-world scenarios:

  • MNIST (5-6 Subset): Used to explore how validation error fluctuates based on the size of the validation set and data corruption in K-Nearest Neighbors.
  • Yahoo! Front Page Today Module: A large-scale dataset (over 700,000 rows) used for the offline evaluation of bandit algorithms (UCB1 and EXP3) using importance sampling.
  • UCI Ionosphere: Employed to test the efficacy of PAC-Bayesian aggregation techniques.

Key results include the demonstration that the Hedge algorithm is minimax optimal for prediction with expert advice and that Support Vector Machines (SVMs) can be given rigorous generalization guarantees even in infinite-dimensional spaces by using margin-based analysis and fat-shattering dimensions.

Limitations and Future Directions

The text concludes by acknowledging the boundaries of current theory. Most existing guarantees rely on the assumption that data is Independent and Identically Distributed (i.i.d.). However, in real-world systems where models influence their environment (e.g., recommendation engines or traffic routing), these feedback loops break the i.i.d. assumption. Furthermore, while some bounds are theoretically tight, they can be computationally expensive to optimize directly, necessitating the development of more "optimization-friendly" relaxations. Finally, the book notes the gap between correlation-based machine learning and true causal inference, identifying the intersection of online learning and causality as a key frontier for future research.

Conclusion

"Machine Learning: The Science of Selection under Uncertainty" provides a comprehensive roadmap for moving from heuristic-based modeling to theoretically grounded selection. By treating variance as a resource and selection as a statistical risk, it offers the tools necessary to build machine learning systems that are not just accurate, but provably reliable.

Summary updated

Abstract

Learning, whether natural or artificial, is a process of selection. It starts with a set of candidate options and selects the more successful ones. In the case of machine learning the selection is done based on empirical estimates of prediction accuracy of candidate prediction rules on some data. Due to randomness of data sampling the empirical estimates are inherently noisy, leading to selection under uncertainty. The book provides statistical tools to obtain theoretical guarantees on the outcome of selection under uncertainty. We start with concentration of measure inequalities, which are the main statistical instrument for controlling how much an empirical estimate of expectation of a function deviates from the true expectation. The book covers a broad range of inequalities, including Markov's, Chebyshev's, Hoeffding's, Bernstein's, Empirical Bernstein's, Unexpected Bernstein's, kl, and split-kl. We then study the classical (offline) supervised learning and provide a range of tools for deriving generalization bounds, including Occam's razor, Vapnik-Chervonenkis analysis, and PAC-Bayesian analysis. The latter is further applied to derive generalization guarantees for weighted majority votes. After covering the offline setting, we turn our attention to online learning. We present the space of online learning problems characterized by environmental feedback, environmental resistance, and structural complexity. A common performance measure in online learning is regret, which compares performance of an algorithm to performance of the best prediction rule in hindsight, out of a restricted set of prediction rules. We present tools for deriving regret bounds in stochastic and adversarial environments, and under full information and bandit feedback.
BibTeX
@misc{seldin2025machine,
  author = {Yevgeny Seldin},
  title = {{Machine Learning. The Science of Selection under Uncertainty}},
  year = {2025},
  eprint = {2509.21547},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2509.21547},
}
Figure