A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
Information-theoretic lower bounds prove that no learning algorithm — regardless of computational power — can learn certain problems below a given sample complexity or error rate. These bounds are proved by constructing a family of "hard instances" that are indistinguishable from limited data and applying tools like Fano's inequality (which bounds the probability of correctly identifying a hypothesis when mutual information between the data and the hypothesis is small) or Le Cam's method (which reduces learning to a hypothesis test between two distributions). These bounds are unconditional — they hold against all algorithms, not just efficient ones — and establish the fundamental limits of statistical learning.
Upper bounds (like VC dimension-based sample complexity) tell you how many samples are sufficient for learning. Lower bounds tell you how many are necessary — they prove that no algorithm, no matter how clever, can learn with fewer samples. Information-theoretic lower bounds are the strongest form of this guarantee because they apply to all algorithms, including computationally unbounded ones.
The basic proof strategy is adversarial construction. You design a family of problems (distributions, target functions) within the stated class such that: (1) the problems are genuinely different (the target functions have large pairwise distance), but (2) the data distributions they generate are hard to distinguish from finite samples (the joint distributions of n samples are close in total variation or have low mutual information). If the learner cannot tell which problem it is facing, it cannot estimate the target accurately. The mathematical tools — Fano's inequality, Le Cam's method, Assouad's lemma — formalize different versions of this indistinguishability argument.
Le Cam's method is the simplest: construct two distributions P_0 and P_1 that are close in total variation distance but have parameters separated by some distance delta. The total variation between the n-fold products P_0n and P_1n is bounded by n times the chi-squared divergence or KL divergence between the base distributions. If this total variation is small (roughly below 1), no test can reliably distinguish the two, and the estimation error must be at least delta/2. This gives lower bounds that match upper bounds for many parametric estimation problems.
Fano's inequality handles the multi-hypothesis case, which is needed for most learning theory applications. Given M hypotheses with pairwise distance at least delta, and data such that the mutual information between the hypothesis index and the data is at most I bits, the error probability is at least 1 - (I + 1)/log(M). To prove a sample complexity lower bound, you construct M = 2d hypotheses (where d might be the dimension), show that n samples provide at most O(n) bits of mutual information about which hypothesis is true, and conclude that n must be at least Omega(d) for reliable identification. These lower bounds establish the fundamental limits of learning and serve as benchmarks for evaluating whether learning algorithms are optimal — an algorithm that matches the lower bound is minimax optimal and cannot be improved in the worst case.