ÀÏ°ÄÃÅ¿ª½±Ö±²¥

Information, Concentration, and Learning
Maxim Raginsky

University of Illinois at Urbana-Champaign

Ìý

Abstract: During the last two decades, concentration of measure has been a subject ofÌývarious exciting developments in convex geometry, functional analysis,Ìýstatistical physics, high-dimensional statistics, probability theory,ÌýinformationÌýtheory, communications and coding theory, computer science, andÌýlearning theory. One common theme that emerges in these fields isÌýprobabilistic stability: complicated, nonlinear functions of a large number ofÌýindependent orÌýweakly dependent random variables often tend to concentrateÌýsharply around their expected values. Information theory plays a key role inÌýthe derivation of concentration inequalities. Indeed, both the entropy methodÌýand the approach based on transportation-cost inequalities are two majorÌýinformation-theoretic paths towardÌýproving concentration.

Ìý

Machine learning algorithms can be viewed as stochastic transformationsÌý(or channels, in information-theoretic parlance) that map training dataÌýto hypotheses. Following the classic paper of Bousquet and Elisseeff, weÌýsay thatÌýsuch an algorithm is stable if its output does not depend tooÌýmuch on any individual training example. Since stability is closelyÌýconnected to generalization capabilities of learning algorithms, it isÌýof theoretical and practical interestÌýto obtain sharp quantitativeÌýestimates on the generalization bias of machine learning algorithms inÌýterms of their stability properties. In this tutorial, I will survey a recent line of work aimed at deriving stability and/or generalization guarantees for learning algorithmsÌýbased on mutualÌýinformation, erasure mutual information, and related information-theoretic quantities.Ìý

Ìý

Bio: Maxim Raginsky received the B.S. and M.S. degrees in 2000 and theÌýPh.D. degree in 2002 from Northwestern University, all in ElectricalÌýEngineering. He has held research positions with Northwestern, theÌýUniversity of Illinois atÌýUrbana-Champaign (where he was a BeckmanÌýFoundation Fellow from 2004 to 2007), and Duke University. In 2012, heÌýhas returned to the UIUC, where he is currently an Associate Professor and William L. Everitt FellowÌýwith the Department of ElectricalÌýand Computer Engineering and theÌýCoordinated Science Laboratory. He also holds a courtesy appointmentÌýwith the Department of Computer Science. He has received the CAREER award from the National Science Foundation in 2013. Prof. Raginsky's interests cover probability and stochasticÌýprocesses, deterministic and stochastic control, machine learning,Ìýoptimization, and information theory. Much of his recent research isÌýmotivated by fundamentalÌýquestions in modeling, learning, and simulationÌýof nonlinear dynamical systems, with applications to advancedÌýelectronics, autonomy, and artificial intelligence.