2020

Reasoning About Generalization via Conditional Mutual Information

Steinke, Thomas, Zakynthinou, Lydia

Understand

We provide an information-theoretic framework for studying the generalization properties of machine learning algorithms.

Our framework ties together existing approaches, including uniform convergence bounds and recent methods for adaptive data analysis.
Specifically, we use Conditional Mutual Information (CMI) to quantify how well the input (i.e., the training data) can be recognized given the output (i.e., the trained model) of the learning algorithm.
We show that bounds on CMI can be obtained from VC dimension, compression schemes, differential privacy, and other methods.

Built on

“Elementary principles in statistical mechanics: developed with especial reference to the rational foundation of thermodynamics”
Josiah Gibbs · 1902
Earlier work this paper cites.
“Strengthened Information-theoretic Bounds on the Generalization Error”, 2019
Original
Ibrahim Issa, Amedeo Esposito and Michael Gastpar · 1903
Earlier work this paper cites.
“Beweis, daß jede Menge wohlgeordnet werden kann”
Original
Ernst Zermelo · 1904
Earlier work this paper cites.
“Bounds for the variance of the Mann-Whitney statistic”
Zygmund Birnbaum and Orval Klose · 1957
Earlier work this paper cites.
“Probability inequalities for sums of bounded random variables. j. amer. statist. assoc. 58”, 1963
W Hoeffding · 1963
Earlier work this paper cites.
“On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities”
V.. Vapnik and A.. Chervonenkis · 1971
Earlier work this paper cites.
“On the density of families of sets”
N. Sauer · 1972
Earlier work this paper cites.
“A combinatorial problem; stability and order for models and theories in infinitary languages”
Saharon Shelah · 1972
Earlier work this paper cites.
“Asymptotic evaluation of certain Markov process expectations for large time, I”
Monroe Donsker and SR Varadhan · 1975
Earlier work this paper cites.
“A finite sample distribution-free performance bound for local discrimination rules”
William Rogers and Terry Wagner · 1978
Earlier work this paper cites.
“Distribution-free inequalities for the deleted and holdout error estimates”
Luc Devroye and Terry Wagner · 1979
Earlier work this paper cites.
“Distribution-free performance bounds for potential function rules”
Luc Devroye and Terry Wagner · 1979
Earlier work this paper cites.
“A theory of the learnable”
Leslie Valiant · 1984
Earlier work this paper cites.
“Relating Data Compression and Learnability”, 1986
Nick Littlestone and Manfred. Warmuth · 1986
Earlier work this paper cites.
“An Efron-Stein Inequality for Nonsymmetric Statistics”
J. Steele · 1986
Earlier work this paper cites.
“On the method of bounded differences”
Colin McDiarmid · 1989
Earlier work this paper cites.
“Divergence measures based on the Shannon entropy”
Jianhua Lin · 1991
Earlier work this paper cites.
“Decision theoretic generalizations of the PAC model for neural net and other learning applications”
David Haussler · 1992
Earlier work this paper cites.
“Small-bias probability spaces: Efficient constructions and applications”
Joseph Naor and Moni Naor · 1993
Earlier work this paper cites.
“Efficient distribution-free learning of probabilistic concepts”
Michael Kearns and Robert Schapire · 1994
Earlier work this paper cites.
“An introduction to computational learning theory”
Michael Kearns, Umesh Vazirani and Umesh Vazirani · 1994
Earlier work this paper cites.
“Sharper bounds for Gaussian and empirical processes”
Michel Talagrand · 1994
Earlier work this paper cites.
“Fat-shattering and the learnability of real-valued functions”
Peter Bartlett, Philip Long and Robert Williamson · 1996
Earlier work this paper cites.
“Vapnik-Chervonenkis theory”
Luc Devroye, L\’aszl\’o Gy\"orfi and G\’abor Lugosi · 1996
Earlier work this paper cites.
“Scale-sensitive dimensions, uniform convergence, and learnability”
Noga Alon, Shai Ben-David, Nicolo Cesa-Bianchi and David Haussler · 1997
Earlier work this paper cites.
“Algorithmic stability and sanity-check bounds for leave-one-out cross-validation”
Michael Kearns and Dana Ron · 1999
Earlier work this paper cites.

Similar

“Some pac-bayesian theorems”
David McAllester · 1999
Cited alongside, same era.
“The information bottleneck method”
Naftali Tishby, Fernando Pereira and William Bialek · 2000
Cited alongside, same era.
“Stability and generalization”
Olivier Bousquet and Andr\’e Elisseeff · 2002
Cited alongside, same era.
“Sharpened Generalization Bounds based on Conditional Mutual Information and an Application to Noisy, Iterative Algorithms”, 2020
Original
Mahdi Haghifam, Jeffrey Negrea, Ashish Khisti, Daniel. Roy and Gintare Dziugaite · 2004
Cited alongside, same era.
“Clustering with Bregman divergences”
Arindam Banerjee, Srujana Merugu, Inderjit Dhillon and Joydeep Ghosh · 2005
Cited alongside, same era.
“Generalization Bounds via Information Density and Conditional Information Density”, 2020
Original
Fredrik Hellstr\"om and Giuseppe Durisi · 2005
Cited alongside, same era.
“Elements of Information Theory (Wiley Series in Telecommunications and Signal Processing)”
Thomas. Cover and Joy. Thomas · 2006
Cited alongside, same era.
“Our data, ourselves: Privacy via distributed noise generation”
Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov and Moni Naor · 2006
Cited alongside, same era.
“Calibrating Noise to Sensitivity in Private Data Analysis”
Cynthia Dwork, Frank McSherry, Kobbi Nissim and Adam Smith · 2006
Cited alongside, same era.
“Functional Bregman divergence and Bayesian estimation of distributions”
B\’ela Frigyik, Santosh Srivastava and Maya Gupta · 2008
Cited alongside, same era.
“Stochastic Convex Optimization.”
Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro and Karthik Sridharan · 2009
Cited alongside, same era.
“The limits of two-party differential privacy”
Andrew McGregor, Ilya Mironov, Toniann Pitassi, Omer Reingold, Kunal Talwar and Salil Vadhan · 2010
Cited alongside, same era.

Then

“Max-information, differential privacy, and post-selection hypothesis testing”
Ryan Rogers, Aaron Roth, Adam Smith and Om Thakkar · 2016
Later among the works it cites.
“Information-theoretic analysis of stability and bias of learning algorithms”
Maxim Raginsky, Alexander Rakhlin, Matthew Tsao, Yihong Wu and Aolin Xu · 2016
Later among the works it cites.
“Controlling Bias in Adaptive Data Analysis Using Information Theory”
Daniel Russo and James Zou · 2016
Later among the works it cites.
“On-average kl-privacy and its equivalence to generalization for max-entropy mechanisms”
Yu-Xiang Wang, Jing Lei and Stephen Fienberg · 2016
Later among the works it cites.
“Information, privacy and stability in adaptive data analysis”
Original
Adam Smith · 2017
Later among the works it cites.
“Information-theoretic analysis of generalization capability of learning algorithms”
Aolin Xu and Maxim Raginsky · 2017
Later among the works it cites.
“Chaining mutual information and tightening generalization bounds”
Amir Asadi, Emmanuel Abbe and Sergio Verd\’u · 2018
Later among the works it cites.
“Composable and versatile privacy via truncated CDP”
Mark Bun, Cynthia Dwork, Guy Rothblum and Thomas Steinke · 2018
Later among the works it cites.
“Learners that Use Little Information”
Raef Bassily, Shay Moran, Ido Nachum, Jonathan Shafer and Amir Yehudayoff · 2018
Later among the works it cites.
“Calibrating Noise to Variance in Adaptive Data Analysis”
Vitaly Feldman and Thomas Steinke · 2018
Later among the works it cites.
“Generalization bounds for uniformly stable algorithms”
Vitaly Feldman and Jan Vondrak · 2018
Later among the works it cites.
“The limits of post-selection generalization”
Kobbi Nissim, Adam Smith, Thomas Steinke, Uri Stemmer and Jonathan Ullman · 2018
Later among the works it cites.
“A direct sum result for the information complexity of learning”
Original
Ido Nachum, Jonathan Shafer and Amir Yehudayoff · 2018
Later among the works it cites.
“Average-Case Information Complexity of Learning”
Original
Ido Nachum and Amir Yehudayoff · 2018
Later among the works it cites.
“Limits of Private Learning with Access to Public Data”
Noga Alon, Raef Bassily and Shay Moran · 2019
Later among the works it cites.
“Sharper bounds for uniformly stable algorithms”
Original
Olivier Bousquet, Yegor Klochkov and Nikita Zhivotovskiy · 2019
Later among the works it cites.
“Tightening mutual information based bounds on generalization error”
Yuheng Bu, Shaofeng Zou and Venugopal Veeravalli · 2019
Later among the works it cites.
“PAC learning with stable and private predictions”
Original
Yuval Dagan and Vitaly Feldman · 2019
Later among the works it cites.
“A new approach to adaptive data analysis and learning via maximal leakage”
Original
Amedeo Esposito, Michael Gastpar and Ibrahim Issa · 2019
Later among the works it cites.
“High probability generalization bounds for uniformly stable algorithms with nearly optimal rate”
Original
Vitaly Feldman and Jan Vondr\’ak · 2019
Later among the works it cites.
“A New Analysis of Differential Privacy’s Generalization Guarantees”
Original
Christopher Jung, Katrina Ligett, Seth Neel, Aaron Roth, Saeed Sharifi-Malvajerdi and Moshe Shenfeld · 2019
Later among the works it cites.
“A necessary and sufficient stability notion for adaptive generalization”
Katrina Ligett and Moshe Shenfeld · 2019
Later among the works it cites.
“In Defense of Uniform Convergence: Generalization via derandomization with an application to interpolating predictors”
Original
Jeffrey Negrea, Gintare Dziugaite and Daniel Roy · 2019
Later among the works it cites.
“Information-Theoretic Generalization Bounds for SGLD via Data-Dependent Estimates”
Jeffrey Negrea, Mahdi Haghifam, Gintare Dziugaite, Ashish Khisti and Daniel Roy · 2019
Later among the works it cites.
“Robust Generalization via α \alpha -Mutual Information”
Original
Amedeo Esposito, Michael Gastpar and Ibrahim Issa · 2020
Closest in time.
Gabor Lugosi https://twitter.com/lugosi_gabor/status/1230106553711198209 , 2020
2020
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…