TY - GEN
T1 - Information-theoretic analysis of stability and bias of learning algorithms
AU - Raginsky, Maxim
AU - Rakhlin, Alexander
AU - Matthew, Tsao
AU - Wu, Yihong
AU - Aolin, Xu
N1 - Funding Information:
Research supported in part by NSF grants CDS&E-MSS 1521529, CCF-1017564, CAREER award CCF-1254041, and by the Center for Science of Information (CSoI), an NSF Science and Technology Center, under grant agreement CCF-0939370
Publisher Copyright:
© 2016 IEEE.
PY - 2016/10/21
Y1 - 2016/10/21
N2 - Machine learning algorithms can be viewed as stochastic transformations that map training data to hypotheses. Following 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. We propose several information-theoretic measures of algorithmic stability and use them to upper-bound the generalization bias of learning algorithms. Our framework is complementary to the information-theoretic methodology developed recently by Russo and Zou.
AB - Machine learning algorithms can be viewed as stochastic transformations that map training data to hypotheses. Following 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. We propose several information-theoretic measures of algorithmic stability and use them to upper-bound the generalization bias of learning algorithms. Our framework is complementary to the information-theoretic methodology developed recently by Russo and Zou.
UR - http://www.scopus.com/inward/record.url?scp=84999025283&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84999025283&partnerID=8YFLogxK
U2 - 10.1109/ITW.2016.7606789
DO - 10.1109/ITW.2016.7606789
M3 - Conference contribution
AN - SCOPUS:84999025283
T3 - 2016 IEEE Information Theory Workshop, ITW 2016
SP - 26
EP - 30
BT - 2016 IEEE Information Theory Workshop, ITW 2016
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2016 IEEE Information Theory Workshop, ITW 2016
Y2 - 11 September 2016 through 14 September 2016
ER -