Oracle Inequalities in Empirical Risk Minimization and Sparse Recovery Problems

1. Front Matter

   Pages i-ix

   PDF

2. Introduction

   • Vladimir Koltchinskii

   Pages 1-16

3. Empirical and Rademacher Processes

   • Vladimir Koltchinskii

   Pages 17-32

4. Bounding Expected Sup-Norms of Empirical and Rademacher Processes

   • Vladimir Koltchinskii

   Pages 33-57

5. Excess Risk Bounds

   • Vladimir Koltchinskii

   Pages 59-79

6. Examples of Excess Risk Bounds in Prediction Problems

   • Vladimir Koltchinskii

   Pages 81-97

7. Penalized Empirical Risk Minimization and Model Selection Problems

   • Vladimir Koltchinskii

   Pages 99-119

8. Linear Programming in Sparse Recovery

   • Vladimir Koltchinskii

   Pages 121-149

9. Convex Penalization in Sparse Recovery

   • Vladimir Koltchinskii

   Pages 151-189

10. Low Rank Matrix Recovery: Nuclear Norm Penalization

    • Vladimir Koltchinskii

    Pages 191-234

11. Back Matter

    Pages 235-254

    PDF

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.

• 62J99, 62H12, 60B20, 60G99
• concentration inequalities
• empirical processes
• low rank matrix recovery
• sparse recovery

From the reviews:

“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. … The book is interesting and useful for students as well as for professionals in the field of probability theory, statistics, and their applications.” (Pavel Stoynov, Zentralblatt MATH, Vol. 1223, 2011)

• School of Mathematics, Georgia Institute of Technology, Atlanta, USA

  Vladimir Koltchinskii

Policies and ethics