Oracle Inequalities in Empirical Risk Minimization and Sparse Recovery Problems
École d'Été de Probabilités de Saint-Flour XXXVIII-2008
Published on 29. July 2011
IX, 254 pages
978-3-642-22147-7 (ISBN)
Description
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.
Reviews / Votes
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)
More details
Other editions
Additional editions
Vladimir Koltchinskii
Oracle Inequalities in Empirical Risk Minimization and Sparse Recovery Problems
École d'Été de Probabilités de Saint-Flour XXXVIII-2008
Book
07/2011
1st Edition
Springer
€80.24
Shipment within 7-9 days
Content
- Intro
- Oracle Inequalities in Empirical Risk Minimization and Sparse Recovery Problems
- Preface
- Contents
- Chapter 1: Introduction
- 1.1 Abstract Empirical Risk Minimization
- 1.2 Excess Risk: Distribution Dependent Bounds
- 1.3 Rademacher Processes and Data Dependent Bounds on Excess Risk
- 1.4 Penalized Empirical Risk Minimization and Oracle Inequalities
- 1.5 Concrete Empirical Risk Minimization Problems
- 1.6 Sparse Recovery Problems
- 1.7 Recovering Low Rank Matrices
- Chapter 2: Empirical and Rademacher Processes
- 2.1 Symmetrization Inequalities
- 2.2 Comparison Inequalities for Rademacher Sums
- 2.3 Concentration Inequalities
- 2.4 Exponential Bounds for Sums of Independent Random Matrices
- 2.5 Further Comments
- Chapter 3: Bounding Expected Sup-Norms of Empirical and Rademacher Processes
- 3.1 Gaussian and Subgaussian Processes, Metric Entropies and Generic Chaining Complexities
- 3.2 Finite Classes of Functions
- 3.3 Shattering Numbers and VC-classes of Sets
- 3.4 Upper Entropy Bounds
- 3.5 Lower Entropy Bounds
- 3.6 Generic Chaining Complexities and Bounding Empirical Processes Indexed by F2
- 3.7 Function Classes in Hilbert Spaces
- 3.8 Further Comments
- Chapter 4: Excess Risk Bounds
- 4.1 Distribution Dependent Bounds and Ratio Bounds for Excess Risk
- 4.2 Rademacher Complexities and Data Dependent Bounds on Excess Risk
- 4.3 Further Comments
- Chapter 5: Examples of Excess Risk Bounds in Prediction Problems
- 5.1 Regression with Quadratic Loss
- 5.2 Empirical Risk Minimization with Convex Loss
- 5.3 Binary Classification Problems
- 5.4 Further Comments
- Chapter 6: Penalized Empirical Risk Minimization and Model Selection Problems
- 6.1 Penalization in Monotone Families Fk
- 6.2 Penalization by Empirical Risk Minima
- 6.3 Linking Excess Risk and Variance in Penalization
- 6.4 Further Comments
- Chapter 7: Linear Programming in Sparse Recovery
- 7.1 Sparse Recovery and Neighborliness of Convex Polytopes
- 7.2 Geometric Properties of the Dictionary
- 7.2.1 Cones of Dominant Coordinates
- 7.2.2 Restricted Isometry Constants and Related Characteristics
- 7.2.3 Alignment Coefficients
- 7.3 Sparse Recovery in Noiseless Problems
- 7.4 The Dantzig Selector
- 7.5 Further Comments
- Chapter 8: Convex Penalization in Sparse Recovery
- 8.1 General Aspects of Convex Penalization
- 8.2 l1-Penalization and Oracle Inequalities
- 8.3 Entropy Penalization and Sparse Recovery in Convex Hulls: Random Error Bounds
- 8.4 Approximation Error Bounds, Alignment and Oracle Inequalities
- 8.5 Further Comments
- Chapter 9: Low Rank Matrix Recovery: Nuclear Norm Penalization
- 9.1 Geometric Parameters of Low Rank Recovery and Other Preliminaries
- 9.2 Matrix Regression with Fixed Design
- 9.3 Matrix Regression with Subgaussian Design
- 9.4 Other Types of Design in Matrix Regression
- 9.5 Further Comments
- Appendix A: Auxiliary Material
- A.1 Orlicz Norms
- A.2 Classical Exponential Inequalities
- A.3 Properties of #- and b-Transforms
- A.4 Some Notations and Facts in Linear Algebra
- References
- Index
- Programme of the school
- List of participants
