SoloGen

Arthur C. Clarke

On Cross-Validation

Rademacher Complexities and related stuff

A few sources that talk about Rademacher complexities (and other stuff):

•  O. Bousquet, S. Boucheron, and G. Lugosi, “Introduction to Statistical Learning Theory,” .
• P. Bartlett, O. Bousquet, and S. Mendelson, “Local Rademacher Complexities,” The Annals of Statistics,” 2005.
• V. Koltchinskii and D. Panchenko, “Rademacher Processes and Bounding the Risk of Function Learning,” ?.
• P. Bartlett and S. Mendelson, “Rademacher and Gaussian Complexities: Risk Bounds and Structural Results,” JMLR 2002 (I need to check this paper, especially because it defines Gaussian complexity. Is there any generalization for arbitrary “noise” term (instead of Gaussian or boolean)? )

Some References for Cross-Validation

• B. Efron and G. Gong, “A Leisurely Look at the Bootstrap, the Jackkife, and Cross-Validation,” 1983.
• M. Kearns, “A Bound on the Error of Cross Validation Using the Approximation and Estimation Rates, with the Consequences for the Training-Test Split,” 1997.
• P. Burman, E. Chow, and D. Nolan, “A Cross-Validatory Method for Dependent Data,” 1994
• B. Efron and R. Tibshirani, “Improvements on Cross-Validation: The 0.632+ Bootstrap Method,” 1997.
• G. Golub, M. Heath, and G. Wahba, “Generalized Cross-Validation as a Method for Choosing a Good Ridge Regression,” 1979. 
• J. Shao, “Linear Model Selection by Cross-Validation,” 1993.
Leave-one-out CV is not consistent! He suggests to use n_v/n —> 1 method while n —> \infty.