Thomas Cover

Life and career

Ask a room of machine learning students where the book *Elements of Information Theory* came from and most will name the book before the author. Thomas M. Cover, with Joy Thomas, wrote the text that taught entropy, mutual information, channel capacity, and rate–distortion to essentially everyone who learned them after 1991. But the textbook is the least original thing he did. Cover proved a theorem about the nearest neighbor rule that is arguably the founding result of statistical learning theory, another about the capacity of high-dimensional space to shatter points that anticipates VC theory, and a third about betting on stocks that connects portfolio growth to Shannon's channel coding. He had a taste, sustained across four decades, for the moment where information theory turns out to be secretly about learning.

Cover was born in San Bernardino, California, in 1938. He took his bachelor's degree in physics at MIT in 1960 and his PhD in electrical engineering at Stanford in 1964, under Norman Abramson — later known for the ALOHA packet radio network. He joined the Stanford faculty essentially immediately and never left, holding a joint appointment in electrical engineering and statistics for nearly five decades. That joint appointment is not incidental; it describes exactly where his work lived. He supervised a long line of doctoral students who went on to shape both information theory and machine learning, and he served as president of the IEEE Information Theory Society.

Colleagues describe him as an elegant thinker with an aversion to computational brute force — someone who wanted a clean theorem with a short proof and a surprising conclusion, and who was less interested when the answer required grinding. He was a serious athlete, a runner and a gymnast in his youth, and reportedly juggled; the image of Cover with a coin, a die, and a stock chart in the air is not far off.

Among his honors were the Claude E. Shannon Award, the highest recognition in information theory, and election to the National Academy of Engineering and the American Academy of Arts and Sciences. He continued working at Stanford until his death in 2012, at seventy-three.

Key contributions

**The nearest neighbor bound (1967, with Peter Hart).** "Nearest Neighbor Pattern Classification" answers a question that sounds too simple to have an interesting answer: how badly can you do if you just classify a new point by the label of its closest training example? Cover and Hart proved that as the sample size goes to infinity, the asymptotic error rate *R* of the 1-NN rule satisfies

*R** ≤ *R* ≤ *R**(2 − *R***M*/(*M*−1))

where *R** is the Bayes error and *M* is the number of classes — so in the two-class case, *R* ≤ 2*R**. In words: the dumbest possible nonparametric classifier, which fits no model and estimates no parameters, is asymptotically within a factor of two of the theoretical optimum. The proof is short and geometric, resting on the observation that in the infinite-sample limit the nearest neighbor's label is drawn from the class posterior at the query point.

The result matters for two reasons beyond the bound itself. It established that *half the available information about the classification problem is contained in the nearest neighbor alone*, which is a striking statement about the geometry of labeled data. And it is one of the first genuine performance guarantees in pattern recognition — an asymptotic theorem rather than an empirical claim, at a moment when the field was mostly running experiments and reporting accuracies.

**Cover's theorem on separability (1965).** "Geometrical and Statistical Properties of Systems of Linear Inequalities with Applications in Pattern Recognition" computes the probability that *N* points in general position in *d* dimensions can be separated by a hyperplane. The answer: separability is essentially certain when *N* < 2*d* and essentially impossible when *N* > 2*d*, with a sharp phase transition at *N* = 2*d*. The counting function *C*(*N*, *d*) = 2 Σ (*N*−1 choose *k*) is a direct ancestor of the VC growth function, and the capacity result 2*d* prefigures VC dimension by several years. It is also the standard justification for the kernel trick: project into a high enough dimension and your data become linearly separable, which Cover quantified precisely.

**Universal portfolios (1991).** Cover asked whether one can invest without knowing anything about the market's statistics and still do as well, asymptotically, as the best constant-rebalanced portfolio chosen in hindsight. His universal portfolio — a performance-weighted mixture over all constant-rebalanced portfolios — achieves exactly that, with the shortfall in exponential growth rate going to zero. This is a **regret bound** in the modern online learning sense, stated in the language of investment and derived by information-theoretic means, and it predates or parallels the online convex optimization literature that made regret central. His related work with Ordentlich on universal prediction, and the earlier Kelly-gambling connection (the growth rate of optimal betting equals the mutual information between the side information and the outcome), all express the same theme: what a model-free rule can be *proved* to guarantee against an adversarial or unknown environment.

**Elements of Information Theory (1991, with Joy Thomas).** The book made the field teachable. Its treatment of the asymptotic equipartition property, typical sets, the method of types, rate–distortion theory, Kolmogorov complexity, and the information-theoretic view of statistics is the standard reference. Cover also did substantial work on multi-user information theory — broadcast channels in particular, where he introduced superposition coding — and on universal source coding.

In battle

Cover is one of the best-rounded figures in the entire roster, and the numbers say so: mean 43.3 against a field where 25 to 30 is typical for a midcentury specialist, median 35, thirteen dominant scores, and only sixteen problems at or below 20. Where the AI figures have a peak and a wasteland, Cover has a broad plateau — because information theory is a general-purpose lens and he pointed it at everything.

His peak is **Just look at the neighbors** (P145) at 99. This is the 1967 paper verbatim: the problem asks someone to prove that the nearest-neighbor rule's asymptotic error is at most twice Bayes, and he is the theorem's author. **All your neighbors are equidistant** (P278) at 96 is the other side of the same coin — the curse of dimensionality's effect on distance concentration, which his separability work bears on directly. **Bet with information theory** (P039) at 97 is Kelly betting and the growth-optimal portfolio, a subject he owned from the gambling side and the investment side both. **The noisy channel's limit** (P035) at 92 is Shannon capacity, where Cover is the field's principal expositor and a contributor to multi-user extensions. **The candidate you cannot recall** (P222) at 92 is the secretary problem and optimal stopping, a natural fit for someone who thought about sequential decisions under uncertainty with provable guarantees. **Twenty questions with a liar** (P050) at 88 is coding with errors — noisy search, exactly his register. **Compress without knowing the source** (P166) at 85 is universal source coding, and **Keep only the bits that matter** (P172) at 85 is rate–distortion.

His category means are unusually strong across the board: `high-dim` 78.0, `information` 73.9 across sixteen problems, `testing` 72.0, `classification` 65.5, `rl` 63.0, `small-sample` 63.0. The reinforcement learning number is notable and is the universal portfolio result showing through — regret against the best fixed strategy in hindsight is an RL concept, and he had it early.

His losses are consistently *high* — his floor is 13, not 3, which is unusual — and they cluster on two things. First, computational complexity and computability: **The problem all others reduce to** (P158, NP-completeness) at 15, **Three machines, one class** (P155) at 13, **Every interesting property is undecidable** (P156) at 13. Cover's mathematics is probability and geometry; nothing in it touches reductions, program semantics, or the halting problem, and his `computability` mean of 29.6 is buoyed by information-theoretic complexity (Kolmogorov) rather than the classical theory. Second, empirical and applied grind: **Attention replaces recurrence** (P088) at 14, **Climb the yield surface** (P112) at 14, and **The same patients, measured again and again** (P137, longitudinal mixed models) at 14. Architecture engineering, agricultural field optimization, and repeated-measures modeling all require sustained empirical work of a kind he never did.

The strategic read is that Cover is a safe card almost everywhere and a devastating one at the boundary between information and learning. He rarely embarrasses himself, which makes him valuable in a game where most specialists are liabilities two-thirds of the time. But he can be beaten by a complexity theorist on anything with a reduction in it, and by a practicing statistician on anything requiring a fitted model rather than a proved bound. He is, in the game as in life, a man who wants the elegant theorem and declines the brawl.