Why upper bounds are only half the story
Everything so far has been an upper bound: a promise that some algorithm achieves error at most something. But how do you know you have not simply failed to be clever? Maybe a better algorithm needs far fewer samples. A lower bound answers this: it proves that no algorithm, however ingenious, can beat a certain error using a given amount of data. Matching upper and lower bounds is the gold standard — it certifies that a problem's difficulty is fully understood and that your method is, up to constants, optimal.
Lower bounds also tame hype. When someone claims a method needs exponentially few samples, a matching lower bound is the discipline that says whether that is possible in principle or marketing. The same sample-complexity question we asked for upper bounds now runs in reverse: what is the largest error that every algorithm must suffer?
The minimax frame
The clean way to ask 'how hard is this problem?' is the minimax framework: minimize over all algorithms the maximum risk over all distributions in the problem class. The inner max is an adversary choosing the worst distribution for your method; the outer min is you choosing the best method against that adversary. The resulting minimax rate is the intrinsic difficulty of the problem — independent of any particular algorithm, a property of the learning task itself.
The minimax risk: the best worst-case error any algorithm can guarantee over the whole problem class.
The strategy for proving a minimax lower bound is a beautiful reduction: pick a finite family of distributions that are statistically close — hard to tell apart from m samples — yet have very different best answers. If even distinguishing them is hard, then estimating the answer must be at least as hard, and that converts a testing impossibility into an estimation lower bound. Le Cam's two-point method is the smallest instance; Fano's method is the many-point generalization.
Fano's method: information limits estimation
Fano's inequality is the information-theoretic engine of lower bounds. Plant a large packing of well-separated candidate truths and treat learning as decoding which one generated the data — a communication problem. Fano says you cannot recover the right index with low error unless the mutual information between the truth and the sample exceeds the log of the packing size. Bound that mutual information with KL divergences between the candidates, and out drops a minimax lower bound: estimation is impossible faster than information arrives.
Fano's inequality lower-bounds the probability of decoding the wrong truth once the mutual-information budget is too small.
This single template — a separated packing, a mutual-information budget, KL bounds between hypotheses — yields the classic minimax rates across statistics: the n^(−β/(2β+d)) rate for β-smooth nonparametric regression, the sqrt(d/n) rate for d-dimensional parametric estimation, and matching lower bounds for sparse recovery. The same entropy of the problem that the covering numbers in guide 2 measured for upper bounds reappears here, now lower-bounding what is achievable. Capacity and difficulty are two faces of one quantity.
No free lunch: the universal limit
The most sweeping lower bound is the no free lunch theorem: averaged over all possible target functions, every learning algorithm has identical expected error — no learner is universally better than random guessing. This is not nihilism; it is a precise statement that generalization requires assumptions. The only reason learning works in practice is that real targets are not uniformly random — they are smooth, structured, compressible — and an algorithm succeeds exactly insofar as its inductive bias matches that structure.
Regret: learning when there is no distribution
Everything above assumed i.i.d. data from a fixed distribution. Online learning throws that away: examples arrive one at a time, possibly chosen by an adversary, and you predict, then suffer a loss, then update — forever. With no distribution there is no 'true risk', so the benchmark changes to regret: your cumulative loss minus that of the best single fixed decision in hindsight. Sublinear regret — regret growing slower than the number of rounds — means your average loss approaches the best fixed strategy's, so you are learning even against an adversary.
Regret measures total loss against the best fixed action in hindsight; the best online algorithms keep it sublinear, of order sqrt(T).
Remarkably, sublinear regret is achievable even against a fully adversarial sequence: online gradient descent and the multiplicative-weights / Hedge algorithm both attain regret of order sqrt(T) over T rounds. The multi-armed bandit is the partial-information cousin, where you see only the loss of the action you took. Online-to-batch conversion then closes the loop: an algorithm with low regret, fed i.i.d. data and averaged, yields a hypothesis with a generalization guarantee — so the adversarial theory hands you back the statistical one, and the two halves of learning theory meet.