Oracle inequalities in empirical risk minimization and sparse recovery problems. École d'Été de Probabilités de Saint-Flour XXXVIII-2008. (Q549116)

The book is 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 of Rademacher sums, entropy and generic chaining bounds). Sparse recovery based on \(l_1\)-type penalization and low rank matrix recovery based on 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 proved to be very useful. The book is organized in nine chapters. Chapter 1, Introduction, is a brief overview of empirical risk minimizaton problems and of the role of empirical and Rademacher processes in constructing distribution dependent and data dependent excess risk bounds. Penalized empirical risk minimization, oracle inequalities, sparse recovery and low rank matrix recovery problems are also discussed. Chapter 2 presents empirical and Rademacher processes more deeply. In Chapter 3, a number of bounds on expectation of suprema of empirical and Rademacher processes are used. In Chapter 4, distribution dependent and data dependent upper bounds on the excess risk of an empirical risk minimizer are developed. In Chapter 5, some examples of excess risk bounds in prediction problems are presented. In Chapter 6, penalized empirical risk minimization and model selection problems are considered. In Chapter 7, some interesting algorithms for sparse recovery are formulated and studied as linear programs. In Chapter 8, the role of penalized empirical risk minimization with convex penalties in sparse recovery problems is discussed. In Chapter 9, the problem of estimation of a large target matrix based on a finite number of noisy measurements of linear functionals of this matrix is investigated. The underlying assumption is that the target matrix is of small rank and the goal is to determine how the estimation error depends on the rank and on other important parameters of the problem such as the number of measurements and the variance of the noise. The book is interesting and useful for students as well as for professionals in the field of probability theory, statistics, and their applications.