Guest post on Tom Cover by Yoav Freund

(Details on registration and student travel awards for the 2012 IEEE Conference on Computational Complexity in Porto available at here.

New York Area Theory Day information here.)



Tom Cover passed away recently. Today we have a guest post about him from Yoav Freund which was written with help from Gabor Lugosi, Nicolo Cesa-Bianchi, Avrim Blum, Rob Schapire, Sanjoy Dasgupta and Manfred Warmuth.

Tom Cover was a leading light, a mentor and an inspiration. I was shocked to hear of his passing away. It was only a few weeks ago that I saw him in the recent ITA conference in San Diego. As usual, engrossed in conversation with a young colleague, gesticulating with his long arms to punctuate his words.

I was first introduced to Cover's work when, as a graduate student in UCSC, I read the classical book of Cover and Thomas on Information theory. Lured by the psychedelic cover I was enchanted by the lucid examples (betting in the horse races) and the elegant math. Like me, many computer scientists were introduced to the deep connections between probability, information, coding and prediction. It is a standard reference for information theory in computer science.

Beyond the book, Cover wrote wrote many of the foundational papers in information theory and its applications. A very partial list of his contribution include his work with Peter Hart on the convergence of the nearest neighbor classifier, His work on the capacity of linear classifiers preceded Vapnik and Chevonenkis. His work on finite memory algorithm for deciding whether the bias of a coin is rational or irrational is a beautiful mind-bender. His papers on gambling and portfolio management started much of the work on online learning.

Speaking of online learning, Cover took part in the first workshop on online learning that was held in UC Santa Cruz at 1992. Cover, with his typical sense of humor, suggested we call the workshop something for nothing. Later we had a bon-fire by the beach, I will always remember Cover as he was that day, a brilliant scientist, a wonderful communicator, a pursuer of beauty and of fun.

Annotated Bibliography

There's also his work on "Nearest neighbor pattern classification" (mid-60s, with Hart).

Yes, that's a very important one. He had two other early influential papers on nearest neighbor classification:

Thomas M. Cover. Rates of Convergence for Nearest Neighbor Procedures. Proceedings of The Hawaii International Conference on System Sciences, Honolulu, Hawaii, January 1968. Thomas M. Cover. Estimation by the Nearest Neighbor Rule. IEEE Transactions on Information Theory, IT-14(1):50--55, January 1968.

Even before Vapnik-Chervonenkis, he calculated the VC shatter coefficient for half spaces:

Thomas M. Cover. Capacity Problems for Linear Machines. Chapter in the book Pattern Recognition, Thompson Book Co., 1968. ed. by L. Kanal.

Then, of course, he was among the pioneers of online learning:



Thomas M. Cover. Universal Gambling Schemes and the Complexity Measures of Kolmogorov and Chaitin. Stanford University Dept. of Statistics Technical Report No. 12, October 1974.

Robert M. Bell and Thomas M. Cover. Competitive Optimality of Logarithmic Investment. Mathematics of Operations Research, 5(2):161--166, May 1980.

Thomas M. Cover. Log Optimal Portfolios. Chapter in Gambling Research: Gambling and Risk Taking, Seventh International Conference, Vol 4: Quantitative Analysis and Gambling, ed. by W.E. Eadington, 1987, Reno, Nevada.

Paul H. Algoet and Thomas M. Cover. Asymptotic Optimality and Asymptotic Equipartition Properties of Log-Optimum Investment. The Annals of Probability,, 16(2): 876-898, 1988.

Robert Bell and Thomas M. Cover. Game-Theoretic Optimal Portfolios. Management Science, 34(6): 724-733, June 1988.

He was among the first to use Blackwell's approachability for online learning:

Thomas M. Cover and David H. Gluss. Empirical Bayes Stock Market Portfolios. Advances in Applied Mathematics, (7):170-181, 1986 This one was a big seminal paper for structural risk minimization: Andrew R. Barron and Thomas M. Cover. Minimum Complexity Density Estimation. IEEE Transactions on Information Theory, 37(4): 1034-1054, July 1991.

Avrim Blum says: I don't know if the following had a big influence on COLT but I remember Ron Rivest describing this result which totally blew my mind: COVER, THOMAS M (1973). On determining the irrationality of the mean of a random variable. Ann. Math. Statist. 1862-871. COVER & HIRSCHLER (1975). A finite memory test of the irrationality of the parameter of a coin. Annals of Statistics, 939-946

You are observing a sequence of flips of a coin of unknown bias p, and after each flip must predict if p is rational or irrational. Shows that with prob 1 you can do this making only a finite number of mistakes....