Measures of Complexity: Festschrift for Alexey Chervonenkis

by Vladimir Vovk (editor)

Chervonenkis's Recollections.- A Paper That Created Three New Fields.- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities.- Sketched 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 Basic Notions and Results.- Predictive Complexity for Games with Finite Outcome Spaces.- Making Vapnik-Chervonenkis Bounds Accurate.- Transductive PAC-Bayes Bounds Seen as a Generalization of Vapnik-Chervonenkis Bounds.- The Two Styles of VC Bounds.- 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.- Tragic Death of Alexey Chervonenkis.- Credits.- Index.

432 pages, Paperback

First published October 5, 2015