Information-theoretic analysis of stability and bias of learning algorithms

Maxim Raginsky, Alexander Rakhlin, Tsao Matthew, Yihong Wu, Xu Aolin

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish (US)
Title of host publication2016 IEEE Information Theory Workshop, ITW 2016
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages5
ISBN (Electronic)9781509010905
StatePublished - Oct 21 2016
Event2016 IEEE Information Theory Workshop, ITW 2016 - Cambridge, United Kingdom
Duration: Sep 11 2016Sep 14 2016

Publication series

Name2016 IEEE Information Theory Workshop, ITW 2016


Other2016 IEEE Information Theory Workshop, ITW 2016
Country/TerritoryUnited Kingdom

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Information Systems
  • Software
  • Signal Processing


Dive into the research topics of 'Information-theoretic analysis of stability and bias of learning algorithms'. Together they form a unique fingerprint.

Cite this