Oracle Inequalities in Empirical Risk Minimization and Sparse Recovery Problems: École D’Été de Probabilités de Saint-Flour XXXVIII-2008Springer Science & Business Media, 29 juil. 2011 - 254 pages The purpose of these lecture notes is to provide an introduction to the general theory of empirical risk minimization with an emphasis on excess risk bounds and oracle inequalities in penalized problems. In recent years, there have been new developments in this area motivated by the study of new classes of methods in machine learning such as large margin classification methods (boosting, kernel machines). The main probabilistic tools involved in the analysis of these problems are concentration and deviation inequalities by Talagrand along with other methods of empirical processes theory (symmetrization inequalities, contraction inequality for Rademacher sums, entropy and generic chaining bounds). Sparse recovery based on l_1-type penalization and low rank matrix recovery based on the nuclear norm penalization are other active areas of research, where the main problems can be stated in the framework of penalized empirical risk minimization, and concentration inequalities and empirical processes tools have proved to be very useful. |
Table des matières
Chapter 2 Empirical and Rademacher Processes | 17 |
Chapter 3 Bounding Expected SupNorms of Empirical and Rademacher Processes | 33 |
Chapter 4 Excess Risk Bounds | 58 |
Chapter 5 Examples of Excess Risk Bounds in Prediction Problems | 81 |
Chapter 6 Penalized Empirical Risk Minimization and Model Selection Problems | 98 |
Chapter 7 Linear Programming in Sparse Recovery | 121 |
Chapter 8 Convex Penalization in Sparse Recovery | 150 |
Chapter 9 Low Rank Matrix Recovery Nuclear Norm Penalization | 191 |
Appendix A Auxiliary Material | 235 |
References | 241 |
| 248 | |
Programme of the school | 251 |
List of participants | 253 |
Autres éditions - Tout afficher
Oracle Inequalities in Empirical Risk Minimization and Sparse Recovery Problems Vladimir Koltchinskii Aucun aperçu disponible - 2011 |
Expressions et termes fréquents
8-minimal set alignment coefficient Alog Annals of Statistics assumption Bernstein's inequality Candes chaining complexity class F concentration inequality condition convex function convex hull convex set Corollary Dantzig selector data dependent defined denote dictionary distribution empirical processes empirical risk minimization entropy estimation exists a constant F Univ following bound holds fぇ Giné Hermitian holds with probability implies inf Pf isometry Koltchinskii Lemma linear span loss function Massart measurable functions Mendelson model selection notations numerical constant oracle inequalities P(lg parameter penalized empirical risk penalties probability at least proof of Theorem Rademacher processes Rademacher sums random matrix random variables regression restricted isometry result risk minimization problem Sect sparse recovery problems sparsity subgaussian subspace Suppose upper bound vector δη λε Πε Πη Σλ