Concentration Inequalities

This concept is the mathematical backbone of why machine learning works at all. When you train a model on data, you are estimating something from a sample — and concentration inequalities tell you how much you can trust that estimate. They are the reason we can say 'with enough samples, the model's error on new data will be close to its error on the training data'. Without them, there would be no theoretical guarantee that a model generalizes beyond the data it saw. This unlocks: statistical learning theory, which is the branch of mathematics that analyzes why models generalize; and it deepens your understanding of any AI system that makes decisions under uncertainty — which is every AI system. For example, when an LLM is trained on billions of tokens, concentration inequalities are what justify the claim that its performance on the training data is a good proxy for its performance on unseen text. When you build a recommendation system, they tell you how many user ratings you need before you can trust the average rating. This is the foundation for the 'generalisation bounds' you will hear about in any serious discussion of model performance.

Concentration inequalities answer a simple question: when you average a bunch of random numbers, how close is that average to the true average you would get with infinitely many numbers? Suppose you flip a coin 100 times. You expect about 50 heads, but you might get 45 or 55. Concentration inequalities say: the probability that you are far from 50 (say, more than 10 away) is small, and they give you a specific number for that probability. The 'inequality' part means they give you an upper bound on the probability of being far from the expectation. They are called 'concentration' because they show that the average 'concentrates' around the true value as the sample size grows. The key insight is that the bound depends on two things: how many samples you have (more samples → tighter bound) and how spread out the random numbers are (if they are all between 1 and 2, the average is very predictable; if they range from 0 to 1000, the average is less predictable). These inequalities do not require you to know the exact distribution of the random numbers — they work for almost any distribution, which is why they are so powerful in machine learning, where you almost never know the true distribution.

Imagine you are trying to estimate the average height of all adults in India. You cannot measure everyone, so you take a random sample of 100 people and compute the average. You know that your sample average is probably close to the true average, but how close? The concentration inequality is like a guarantee from a mathematician: 'I cannot tell you exactly how close, but I can tell you that the probability of being off by more than X cm is less than Y.' The more people you measure (larger sample size), the smaller Y becomes. Also, if you know that heights in India have a small spread (most people are between 150 and 180 cm), then Y is smaller than if heights were wildly variable (say, from 50 to 250 cm). The analogy works well, but it has a limit: the guarantee is probabilistic, not absolute. It does not say 'you will definitely be within X cm', it says 'the probability of being off by more than X cm is at most Y'. For example, if Y = 5%, that means there is a 5% chance the estimate is bad. That 5% is not an excuse — it means you need to be aware that sometimes your sample might be unlucky, but the inequality tells you how often that happens.

A concentration inequality is a mathematical bound on the probability that a random quantity (such as the sample average) deviates from its expected value by more than a certain amount, stated as a function of the sample size and the variability of the underlying random variables.

This concept sits at the heart of probability theory, which you are learning about. It builds directly on the idea of expectation — the average you would get with infinite samples — and variance, which measures spread. You have notes on Sampling Distributions, which describe how a statistic like the sample mean varies across repeated samples; concentration inequalities give you quantitative bounds on how far that sample mean can stray from the true mean. This also connects to the Empirical CDF, which is a way to estimate a distribution from data: concentration inequalities underpin the proof that the empirical CDF converges uniformly to the true CDF as the sample size grows. In the broader AI landscape, concentration inequalities are the theoretical foundation for generalisation bounds in statistical learning theory, which tell you how well a model trained on finite data will perform on unseen data.