From Unlucky Strikers to Statistical Learning Theory

SVG Icon Editor

Author: Maximilian Fleissner

Figure: A footbal fan excited for his team. Image generated by an AI model.

Suppose a new striker joins your favorite Bundesliga team. Fans are excited, the club has paid an enormous transfer fee, and expectations are huge. The new season starts. And then, he only scores a single goal in his first ten games. As a football fan of the impatient kind, you may be quick to lose faith in your new signing. But isn't that a bit premature after just ten games? Did the new striker maybe just have a few unlucky matches? And should you really be shouting at the TV?

Let’s take a step back. Indeed, if the striker’s lack of success continues, the Law of Large Numbers 1 tells us that, eventually, your concerns will be justified (perhaps not the shouting though). The Law of Large Numbers states that as the number of trials in a random experiment increases, the average of the results will get closer to the expected value. The empirically observed average number of goals per game will approach the true expected number of goals per game, provided each of his performances is an independent sample from some underlying distribution. Formally, if we denote \( Z_1, \dots, Z_n \) for the number of goals scored in each of the first \( n \) games, then the average number of goals \( \hat{\mu} = \frac{1}{n} \sum_{i=1}^n Z_i \) will converge to the number of expected goals \( \mu = E[Z_1] \) as \( n \) goes to infinity (under some mild assumptions).

This convergence can be made quantitative using what is called Hoeffding’s inequality 2. Assuming for the moment that scoring more than ten goals will almost never happen, the probability of your estimate \( \hat{\mu} \) deviating from \( \mu \) by more than some small \( t > 0 \) can be bounded by

$$
P(| \hat \mu_n - \mu| > t) \le 2\exp(-nt^2/50)
$$

This result can be seen as a quantitative version of the Law of Large Numbers: Note that as the number of observations \( n \) grows, the probability of over- or underestimating the population mean \( \mu \) by more than a fixed budget of \( t \) decays to zero. Importantly, you do not need any assumptions on the parametric form of the distribution for this to be true.

From Estimation to Prediction

So far, so good. We now know how long we can stay calm before we angrily sell the new striker. But as machine learning enthusiasts, we are naturally not content with just estimating means. Wouldn't it be far more interesting to predict whether a player will score based on a bunch of features \( x \) you have collected before the game (strength of opponent, his recent form, home or away)?

Denoting \( x \) for these features and \( y \) for the binary label (whether or not the player scores), let us find a model \( h \) that predicts \( y \) from \( x \). For example, \( h \) could be a logistic regression, or a decision tree. Once fitted, you can assess the model's quality using a loss \( l(y, h(x)) \) that is zero if your prediction is correct, and one otherwise. Ideally, you want to find a good \( h \) such that this loss is low on average: You are aiming to minimize

$$
L(h) = E_{x,y}[l(y,h(x))]
$$

which is called the risk of the predictor \( h \).

Since you do not have knowledge of the true underlying distribution \( (x, y) \), the best you can do is fit a model \( \hat{h} \) on a training dataset of \( n \) observations \( (x_1, y_1), \dots, (x_n, y_n) \), with each pair denoting an instance of features and labels. On this training data, you observe an empirical risk

$$
\hat L(\hat h) = \frac{1}{n} \sum_{i=1}^n l(y_i, \hat h(x_i))
$$

that evaluates how good \( \hat{h} \) performs on the training data. But is \( \hat{L}(\hat{h}) \) a reliable estimate of \( L(\hat{h}) \)?

If we want to trust our model to perform similarly when confronted with new data, we need the difference between \( \hat{L}(\hat{h}) \) and \( L(\hat{h}) \) to be small. You may be tempted to appeal to the Law of Large Numbers again, or call upon its quantitative cousin Hoeffding’s inequality. After all, isn’t \( \hat{L}( \hat{h}) \) just an empirical average that will converge to its population version \( L(\hat{h}) \) as the number of samples grows?

Uniform Laws of Large Numbers

Unfortunately, this does not work. The function \( \hat{h} \) that you fit on your training data explicitly depends on the observations \( (x_i, y_i) \). After all, \( \hat{h} \) is chosen precisely because it performs well on these observations. Therefore, the ordinary Law of Large Numbers does not apply.

This is where statistical learning theory comes in to the rescue. Instead of bounding the difference for the random predictor \( \hat{h} \), we look at the worst case difference between empirical and true risk over all possible predictors. Formally,

$$
\left| L( \hat h) - \hat L( \hat h) \right| \le \sup_{h \in H} \left| L(h) - \hat L (h) \right|
$$

While this may seem overly pessimistic at first, this simplification is the key to obtain useful bounds on \( L(\hat{h}) \). For example, suppose \( H \) only contains \( M \) predictors to choose from. Then, it can be shown that

$$
P \left( \sup_{h \in H} \left| L(h) - \hat L (h) \right| > t \right) \le 2M \exp(-2n t^2)
$$

which ensures that our model \( \hat{h} \) will not perform much worse on new, unseen data provided the sample size \( n \) is large. You will notice the similarity to the inequality we obtained earlier. However, the size \( M \) of the predictor class now also shows up on the right side, increasing the probability of underestimating the true risk of your model. In particular, when \( M \) is exponential in \( n \), you do not get a useful bound on \( L(\hat{h}) \).

Controlling Complexity

To make matters worse, \( M \) is rarely finite in machine learning—we typically optimize over function spaces with infinitely many possible predictors in them. Fortunately, statistical learning theory sometimes allows us to replace \( M \) with finite quantities that essentially capture the complexity of the predictors in \( H \).

Two standard tools to measure this complexity are the VC dimension 3, which essentially tells us how many binary patterns models from \( H \) can fit, or Rademacher complexity, which measures the capacity of \( H \) to fit random noise. For both, the intuition is the same: The more wild the predictors from \( H \) potentially behave, the less you can trust the empirical risk to be an accurate estimate of the true risk. Then again, keep in mind that a certain level of complexity in \( H \) is unavoidable if you want a good model.

With these tools, it becomes possible to bound the risk for large classes of predictors, including linear models, decision trees, or support vector machines.

Outlook

Admittedly, this is a bit of a classic view on things. In today’s world, we train models with billions of parameters that can in fact fit any function you want, making standard bounds on \( |L(\hat{h}) - \hat{L}(\hat{h})| \) vacuous. It remains one of the mysteries of deep learning why it still produces models \( \hat{h} \) that generalize well. Broadly speaking, it is believed that the architectures and optimization schemes used in deep learning guide the model to "nice" solutions, but the question is far from resolved.

Then again, not every powerful function class is as much of a mystery as are deep neural networks: For kernel machines, it is a lot easier (though still challenging) to precisely characterize the risk of the learned predictors. Since some neural networks actually behave like kernel models 4, these insights can be used to say something about neural networks after all. But that's a story for another day—perhaps the next half time break.

References

1.Klenke, Achim. Probability theory: a comprehensive course (Chapter 5). Springer Science & Business Media, 2013.

2.Vapnik, Vladimir N. "An overview of statistical learning theory." IEEE transactions on neural networks 10.5 (1999): 988-999.

3.Jacot, Arthur, Franck Gabriel, and Clément Hongler. "Neural tangent kernel: Convergence and generalization in neural networks." Advances in neural information processing systems 31 (2018).

4.Jacot, Arthur, Franck Gabriel, and Clément Hongler. "Neural tangent kernel: Convergence and generalization in neural networks." Advances in neural information processing systems 31 (2018).

RELATED

  • / Valentyn Melnychuk

    Can We Trust the Uncertainty of Causal Foundation Models?

    Causal foundation models promise fast, flexible treatment-effect estimation from observational data, but can their uncertainty be trusted? This post examines prior-data fitted networks (PFNs) for causal inference, revealing a hidden prior-induced confounding bias, and introduces a one-step posterior correction that restores reliable, frequentist-consistent uncertainty for average treatment effect estimation. Full post
  • / Molly Kennedy

    Exploring XAI Methods for Interpretability of Large Language Models

    Large Language Models can summarise text, answer questions, and classify sentiment with impressive accuracy, but their reasoning often feels like a black box. Why did the model land on that prediction? This post walks through four complementary approaches from Explainable AI (XAI) that help open up the box. Together, these methods make LLMs less opaque and more trustworthy. Full post
  • / Tzu-Yuan Huang

    Robotic Decision Making via Diffusion Models

    Robots are increasingly expected to operate in complex, real-world environments, but the machine learning methods that drive their decision-making, like reinforcement and imitation learning, often struggle with training stability and capturing the multimodal nature of behavior. This post introduces diffusion models as a powerful alternative for robotic decision making, explaining their core denoising mechanism and surveying their applications in several contexts. Full post
  • / Lukas Gosch

    A Beginner’s Guide to Certifiable Robustness

    Machine learning models, such as ChatGPT and those used in autonomous driving, are becoming essential tools in our daily lives. However, the existence of "adversarial examples" demonstrates that these systems are not free from vulnerabilities. The post, introduces the concept of adversarial examples and discusses Certifiable Robustness, a methodology designed to combat them. Full post
  • / Balian He

    Responsible Textual Generative Models (Part I): Generating Truthful Content

    This post introduces hallucination in large language models—why fluent outputs can still be wrong, what distinguishes intrinsic from extrinsic errors, and how training data, model design, inference, and alignment contribute. It surveys detection and mitigation approaches and sets up later posts on toxicity, bias, and inclusivity in responsible textual generative AI. Full post
  • / Aswathi

    Random Convolutions: A Simple Way to Boost Generalization

    Random Convolutions (RC) are a simple and effective data augmentation technique designed to improve the robustness of deep learning models, particularly in medical imaging. Instead of relying on fixed or learned filters, RC applies a small stack of randomly generated convolutional filters to input images during training. This introduces strong but controlled variations in image texture while preserving the underlying anatomical structure. By exposing models to a wide range of plausible appearance changes, Random Convolutions reduce overfitting to dataset-specific characteristics such as scanner type or acquisition protocol. In practice, RC acts as an implicit form of domain randomization, encouraging models to focus on stable, shape-based and contextual features rather than fragile texture cues. Despite its simplicity and low computational cost, RC has been shown to substantially improve generalization across institutions and imaging conditions in challenging tasks such as multiple sclerosis lesion segmentation. Full post
  • / Ahmed Abdelrahman

    Neuromorphic Computing: A Brain-inspired Approach to Robot Intelligence

    This post offers a high-level walkthrough of neuromorphic computing, why it matters for energy-efficient robot intelligence, and how SNNs, event cameras, and neuromorphic chips fit together Full post
  • / Shengqiang Zhang

    Introduction to Embodied Instruction Following

    This work explores how AI systems bridge the gap between understanding human instructions and performing real actions by learning through direct interaction with their environment. Full post
  • / Unai Fischer Abaigar

    Performative Prediction

    Machine learning systems are increasingly used to support decision-making processes. Yet, these systems do not merely reflect the world—they also reshape it. Once deployed, predictions can influence behaviors, alter policies, and redirect resources, creating feedback loops that change the very data-generating processes they aim to model. Full post
  • / Moritz Knolle

    What even is differential privacy?

    A concise introduction to differential privacy which offers provably privacy guarantees for training machine learning models. Full post
  • / Sameer Ambekar

    Mitigating Domain shifts

    Adapting a deep neural network to unseen data and tasks is imperative these days, however access to target data is often available. Common target adaptation techniques including domain adaptation and generalization train for meaningful representations during source training. Recent paradigms such as Test-time training/adaptation focus on optimizing the source model on unseen data. To do so, they finetune the model on the streaming unsupervised data which is useful for practical scenarios. Moreover, these techniques can be applied to variety of tasks such as regression, classification and segmentation. Full post
  • / Lisa Wimmer

    A gentle introduction to uncertainty quantification

    Uncertainty Quantification (UQ) is considered indispensable for predictive models in safety-critical applications. Modern models, though high-performing, struggle with providing meaningful uncertainty estimates due to a number of reasons. Full post
  • / Blog Editorial Team

    Welcome to the relAI Blog

    Welcome to the relAI blog of the Konrad Zuse School of Excellence in Reliable AI (relAI). This blog will serve as a platform to share cutting-edge research and developments from our school, highlighting the significant strides we are making towards making AI systems safer, more trustworthy, and privacy-preserving. Full post
LOAD MORE