SoloGen

On Fast Rates in Classification

I am wondering what types of regularities are natural to be used in classification problems. In regression setting, different notion of smoothness appears naturally in the bound. I was wondering if I could find similar results for classification.

The field’s landscape is not clear to me yet. People use margin noise conditions that may give them fast rates (faster than n^{-1/2}). If their approach is using a regressor to estimate eta(x) = P{Y=1|X=x}) and then apply a plug-in rule, then the smoothness properties of eta(x) comes to the picture. They may even show that they can get super-fast rates. This smoothness of eta is, however, different from decision surface regularities. Eta can be far from smooth, but the classification might still be easy.

I need to write more about these somewhere, but for now, I found the following Jean-Yves Audibert and Alexandre Tsybakov’s paper interesting:

Jean-Yves Audibert and Alexandre Tsybakov, “Fast Learning Rates for Plug-in Classifiers under the Margin Condition,” Annals of Statistics, 2007.

Also I guess it would be nice to read the following paper too:

Michael Kohler and Adam Kryzak, “On the Rate of Convergence of Local Averaging Plug-in Classification Rules under a Margin Condition,” 2006.

On Pattern Theory (David Mumford)

• David Mumford, “Empirical Statistics and Stochastic Models for Visual Signals”.
• David Mumford, “Pattern Theory: the Mathematics of Perception” (presentation slides)

Conditional Density Estimation

• Chen, Linton and Robinson, “The Estimation of Conditional Densities”. (some interesting results regarding the mixing properties for Markov models)
• Hansen, “Nonparametric Conditional Density Estimation,” 2004. (Two-stage method for conditional density estimation: estimate the mean, and then estimate the deviation from the mean)
• Yoon, “Bayesian Conditional Density Estimation,” 2007. (Bayesian treatment. Quantile regression-based. Univariate rates - but I guess with extra assumption)
• Holmes, Gray, and Isbell, “Fast Nonparametric Conditional Density Estimation,” 2007. (A computational framework for calculating the bandwidths)
• Efromovich, “Conditional Density Estimation in a Regression Setting,” 2007. (Need to take a look later.)

A few papers by Terrence J. Sejnowski

• L. Finelli and T. Sejnowski, “What is Consolidated During Sleep-Dependent Motor Skill Learning?,” 2005.
• T. Flash and T. Sejnowski, “Computational Approaches to Motor Control,” 2001.
• D. Garlick and T. Sejnowski, “There is more to Fluid Intelligence than Working Memory Capacity and Executive Function,” 2006.
• T. Sejnowski, “Sleep and Memory,” 1995.