everything.study
18.465

Topics in Statistics: Statistical Learning Theory

Graduate · Historical course

Spring 2007

Topics

  • Introduction
  • Voting classifiers, training error of boosting
  • Support vector machines (SVM)
  • Generalization error of SVM
  • One dimensional concentration inequalities. Bennett’s inequality
  • Bernstein’s inequality
  • Hoeffding, Hoeffding-Chernoff, and Khinchine inequality
  • Vapnik-Chervonenkis classes of sets
  • Properties of VC classes of sets
  • Symmetrization. Pessimistic VC inequality
  • Optimistic VC inequality
  • VC subgraph classes of functions. Packing and covering numbers
  • Covering numbers of the VC subgraph classes
  • Kolmogorov’s chaining method. Dudley’s entropy integral
  • More symmetrization. Generalized VC inequality
  • Consequences of the generalized VC inequality
  • Covering numbers of the convex hull
  • Uniform entropy condition of VC-hull classes
  • Generalization error bound for VC-hull classes
  • Bounds on the generalization error of voting classifiers
  • Bounds on the generalization error of voting classifiers (cont.)
  • Bounds in terms of sparsity
  • Bounds in terms of sparsity (cont.) (example)
  • Martingale-difference inequalities
  • Comparison inequality for Rademacher processes
  • Application of martingale inequalities. Generalized martingale inequalities
  • Generalization bounds for neural networks
  • Generalization bounds for neural networks (cont.)
  • Generalization bounds for kernel methods
  • Optimistic VC inequality for random classes of sets
  • Applications of random VC inequality to voting algorithms and SVM
  • Talagrand’s convex-hull distance inequality
  • Consequences of Talagrand’s convex-hull distance inequality
  • Talagrand’s concentration inequality for empirical processes
  • Talagrand’s two-point inequality
  • Applications of Talagrand’s concentration inequality
  • Applications of talagrand’s convex-hull distance inequality. Bin packing
  • Entropy tensorization inequality. Tensorization of Laplace transform
  • Application of the entropy tensorization technique
  • Stein’s method for concentration inequalities

Readings

  • Vapnik, Vladimir Naumovich. The Nature of Statistical Learning Theory . New York, NY: Springer, 1998. ISBN: 9780387945590.
    Recommended
  • ———. Statistical Learning Theory . New York, NY: Wiley, 1998. ISBN: 9780471030034. (Acid-free paper.)
    Recommended
  • Ledoux, Michel, and Michel Talagrand. Probability in Banach Spaces: Isoperimetry and Processes . New York, NY: Springer-Verlag, 1991. ISBN: 9780387520131.
    Recommended
  • van der Vaart, Aad W., and Jon A. Wellner. Weak Convergence and Empirical Processes: With Applications to Statistics . New York, NY: Springer, 2000. ISBN: 9780387946405.
    Recommended
  • Anthony, Martin, and Peter L. Bartlett. Neural Network Learning: Theoretical Foundations . New York, NY: Cambridge University Press, 1999. ISBN: 9780521573535.
    Recommended
  • Devroye, Luc, László Györfi, and Gábor Lugosi. A Probabilistic Theory of Pattern Recognition . New York, NY: Springer, 1997. ISBN: 9780387946184.
    Recommended
  • Talagrand, M. “Concentration of Measure and Isoperimetric Inequalities in Product Spaces.” Publ Math IHES 81 (1995): 73-203.
    Listed reading
Spring 2005 · Topics in Statistics: Nonparametrics and Robustness

Topics

  • Chapters 1 and 2, Rank Tests
  • Chapter 3, Handout(s)
  • Section 11.5, Handout(s)
  • Robustness
  • Review for Midterm
  • Robustness (cont.)
  • M-estimation
  • Multivariate Robustness
  • VC Combinatorics
  • Nonparametric Classification
  • Nonparametric Classification (cont.)

Readings

  • Randles, R. H., and D. A. Wolfe. Introduction to the Theory of Nonparametric Statistics . Malabar, FL: Krieger, 1991. ISBN: 0894645439. (This book is currently out of print, but used copies may be available.)
    Listed reading
  • For one or two lectures, we will use Section 2 of Chapter V, “Uniform and exponential spacings,” of the following book:
    Listed reading
  • Devroye, L. Non-Uniform Random Variate Generation. New York, NY: Springer-Verlag, 1986. ISBN: 3540406522. (This book is also out of print, but the author made it available on the web.)
    Listed reading
  • Burges, C.J.C. “A tutorial on support vector machines for pattern recognition.” Data Mining and Knowledge Discovery 2 . Boston, MA: Kluwer Academic Publishers, 1998. pp. 121-167.
    Listed reading
Sources