Measures of Complexity

Chervonenkis’s Recollections.- A Paper That Created Three New Fields.- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities.- Sketched History: VC Combinatorics, 1826 up to 1975.- Institute of Control Sciences through the Lens of VC Dimension.- VC Dimension, Fat-Shattering Dimension, Rademacher Averages, and Their Applications.- Around Kolmogorov Complexity: Basic Notions and Results.- Predictive Complexity for Games with Finite Outcome Spaces.- Making Vapnik–Chervonenkis Bounds Accurate.- Comment: Transductive PAC-Bayes Bounds Seen as a Generalization of Vapnik–Chervonenkis Bounds.- Comment: The Two Styles of VC Bounds.- Rejoinder: Making VC Bounds Accurate.- Measures of Complexity in the Theory of Machine Learning.- Classes of Functions Related to VC Properties.- On Martingale Extensions of Vapnik–Chervonenkis.- Theory with Applications to Online Learning.- Measuring the Capacity of Sets of Functions in the Analysis of ERM.- Algorithmic Statistics Revisited.- Justifying Information-Geometric Causal Inference.- Interpretation of Black-Box Predictive Models.- PAC-Bayes Bounds for Supervised Classification.- Bounding Embeddings of VC Classes into Maximum Classes.- Algorithmic Statistics Revisited.- Justifying Information-Geometric Causal Inference.- Interpretation of Black-Box Predictive Models.- PAC-Bayes Bounds for Supervised Classification.- Bounding Embeddings of VC Classes into Maximum Classes.- Strongly Consistent Detection for Nonparametric Hypotheses.- On the Version Space Compression Set Size and Its Applications.- Lower Bounds for Sparse Coding.- Robust Algorithms via PAC-Bayes and Laplace Distributions.- Postscript: Tragic Death of Alexey Chervonenkis.- Credits.- Index.