STAT 241B / EECS 281B
Advanced Topics in Statistical Learning Theory

Back to top

Scribe notes

Homework and solutions

References and readings

Books:

Papers:

Course projects

Implementing and experimenting with some algorithms (e.g., SVMs, boosting, kernel PCA, kernel regression, kernel CCA, spectral clustering).

Running experiments for a particular application of interest.

Trying to extend an existing method or theoretical result.

Picking a topic that interests you, and learning about in more depth. For instance, if you were interested in dimensionality reduction techniques, then you might read and prepare a survey overview of a related set of papers (e.g., on PCA, spectral methods, Laplacian eigenmap etc.) Similarly, if you were interested in concentration inequalities and risk bounds.....See below for some suggested readings.

JSTOR

IEEEXPLORE

MathSciNet

Kernel methods, SVMs and related topics

`An introduction to kernel-based learning algorithms.' K.-R. Mueller, S. Mika, G. Raetsch, K. Tsuda, and B. Schoelkopf.

`A Tutorial on Support Vector Machines for Pattern Recognition.' C. J. C. Burges. A Tutorial on Support Vector Regression.' A. J. Smola and B. Schoelkopf.

See also the text books:

`An Introduction to Support Vector Machines.' Nello Cristianini and John Shawe-Taylor. Cambridge University Press, Cambridge, UK, 2000. (see the web page)

`Kernel Methods for Pattern Analysis.' John Shawe-Taylor and Nello Cristianini. Cambridge University Press, Cambridge, UK, 2004. (see the web page)

`Learning with Kernels.' Bernhard Schoelkopf and Alex Smola. MIT Press, Cambridge, MA, 2002. (see the web page)

The following papers describe a geometric view of SVM optimization problems.

`A fast iterative nearest point algorithm for support vector machine classifier design.' S.S. Keerthi, S.K. Shevade, C. Bhattacharyya and K.R.K. Murthy.

`Duality and Geometry in SVM Classifiers.' Kristin P. Bennett and Erin J. Bredensteiner.

`A Geometric Interpretation of nu-SVM Classifiers.' D.J. Crisp and C.J.C. Burges

Reproducing kernel Hilbert spaces and related topics

`Consistency and convergence rates of one-class SVM and related algorithms.' (See Section 3.) R. Vert and J.-P. Vert.

`An Explicit Description of the Reproducing Kernel Hilbert Spaces of Gaussian RBF Kernels .' I. Steinwart, D. Hush, and C. Scovel.

`Convolution Kernels on discrete structures' D. Haussler

`Dynamic alignment kernels' C. Watkins

`Convolution kernels for natural language' Michael Collins and Nigel Duffy.

`Text classification using string kernels' H. Lodhi, C. Saunders, J. Shawe-Taylor, N. Cristianini, and C. Watkins

Surrogate loss functions and their properties

Kernel PCA and related topics

Kernel PCA B. Schoelkopf et al.

Convergence of eigenspaces in kernel PCA , L. Zwald and G. Blanchard (2005).

Kernel ICA, by F. Bach and M. Jordan, Journal of Machine Learning Research (2003)

Kernel Methods for Measuring Independence, by A. Gretton et al. Journal of Machine Learning Research (2005).

Statistical properties of kernel principal components analysis. , G. Blanchard et al. (2007).

Eigenspectra of random kernel matrices , by Noureddine El Karoui, UC Berkeley Stat. technical report (2008)

Random matrix theory

Local operator theory, random matrices, and Banach spaces, by K. R. Davidson and S. J. Szarek, In "Handbook of Banach Spaces", pages 317--336.

The following papers discuss aspects of principal component analysis in high-dimensions, as well as PCA with sparsity assumptions:

On the distribution of the largest eigenvalue in principal components analysis, by I. M. Johnstone, Annals of Statistics, Vol. 29, No. 2. (2001), pp. 295-327.

Sparse principal components analysis, by I. M. Johnstone and A. Lu. (2003, also 2009). Paper on arxiv

A direct formulation of sparse PCA using semidefinite programming, by d'Aspremont et al.

High-dimensional analysis of semidefinite programming relaxations for sparse principal component analysis, by A. A. Amini and M. J. Wainwright, To appear in the Annals of Statistics. Paper

Eigenspectra of random kernel matrices , by Noureddine El Karoui, UC Berkeley Stat. technical report (2008)

High-dimensional linear regression and $\ell_1$ relaxation

The following papers discuss aspects of linear regression in high-dimensions, including some under sparsity constraints.

Lasso for Gaussian graph selection and high-dimensional analysis:

High-dimensional graphs and variable selection with the Lasso, by N. Meinshausen and P. Buhlmann, Annals of Statistics, 34, pp 1436--1462, 2006.

On model selection consistency of the Lasso, by P. Zhao and B. Yu, Journal of Machine Learning Research, pp. 2541--2567, 2006.

Sharp thresholds for noisy and high-dimensional recovery of sparsity using $\ell_1$-constrained quadratic programming, by M. J. Wainwright, IEEE Transactions on Information Theory, May 2009. Full Text  (PDF)

The Dantzig Selector: Statistical estimation when $p$ is much larger than $n$, by E. Candes and T. Tao. Annals of Statistics 35:6, pp. 2313--2351, 2007.

Simultaneous Analysis of Lasso and Dantzig Selector, by P. Bickel, Y. Ritov and A. Tsybakov, Annals of Statistics, To appear.

Boosting, ensemble methods and related topics

Bagging predictors, by L, Breiman.

The boosting approach to machine learning: An overview by R. E. Schapire

Experiments with a new boosting algorithm, by Y. Freund and R. E. Schapire.

`Boosting the margin: A new explanation for the effectiveness of voting methods.' Robert E. Schapire, Yoav Freund, Peter Bartlett and Wee Sun Lee.

`Arcing classifiers.' Leo Breiman.

`Additive logistic regression: a statistical view of boosting.' Jerome Friedman, Trevor Hastie and Robert Tibshirani.

Concentration inequalities and risk bounds

`Concentration-of-measure inequalities.' Gabor Lugosi.

` A few notes on Statistical Learning Theory.' Shahar Mendelson

Review paper on Rademacher averages and local Rademacher averages:
`New Approaches to Statistical Learning Theory.' Olivier Bousquet.

The following paper collects some useful properties of Rademacher averages.
`Rademacher and Gaussian complexities: risk bounds and structural results' P. L. Bartlett and S. Mendelson.

Rademacher averages for large margin classifiers:
`Empirical margin distributions and bounding the generalization error of combined classifiers.' Vladimir Koltchinskii and Dmitriy Panchenko.

The `finite lemma' (Rademacher averages of finite sets) is Lemma 5.2 in this paper, which also introduces local Rademacher averages.
`Some applications of concentration inequalities to statistics.' Pascal Massart.

Model selection and related topics

`An experimental and theoretical comparison of model selection methods.' M. Kearns, Y. Mansour, A. Ng, and D. Ron

`Risk bounds for model selection via penalisation.'. Andrew Barron, Lucien Birge and Pascal Massart.

`Model selection and error estimation.' P. L. Bartlett, S. Boucheron, and G. Lugosi.

`Some applications of concentration inequalities to statistics.' Pascal Massart.

`A consistent strategy for boosting algorithms.' Gabor Lugosi and Nicolas Vayatis.

`Consistency of support vector machines and other regularized kernel classifiers.' I. Steinwart.

`The consistency of greedy algorithms for classification.' Shie Mannor, Ron Meir, Tong Zhang.

`Concentration inequalities and model selection.' Pascal Massart.



For Bernstein's inequality, and generalizations, see:
`Concentration-of-measure inequalities.' Gabor Lugosi.

`A Bennett concentration inequality and its application to suprema of empirical processes', Olivier Bousquet.

`Concentration inequalities using the entropy method.' S. Boucheron, G. Lugosi and P. Massart.
`A sharp concentration inequality with applications.' Stephane Boucheron, Gabor Lugosi and Pascal Masssart.


Bounding the variance for excess loss classes:
`Improving the sample complexity using global data.' S. Mendelson.

Back to top