Introduction to High-Dimensional Statistics

Cover
Half Title
Title Page
Copyright Page
Table of Contents
Preface, second edition
Preface
Acknowledgments
1 Introduction
	1.1 High-Dimensional Data
	1.2 Curse of Dimensionality
		1.2.1 Lost in the Immensity of High-Dimensional Spaces
		1.2.2 Fluctuations Cumulate
		1.2.3 Accumulation of Rare Events May Not Be Rare
		1.2.4 Computational Complexity
	1.3 High-Dimensional Statistics
		1.3.1 Circumventing the Curse of Dimensionality
		1.3.2 A Paradigm Shift
		1.3.3 Mathematics of High-Dimensional Statistics
	1.4 About This Book
		1.4.1 Statistics and Data Analysis
		1.4.2 Purpose of This Book
		1.4.3 Overview
	1.5 Discussion and References
		1.5.1 Take-Home Message
		1.5.2 References
	1.6 Exercises
		1.6.1 Strange Geometry of High-Dimensional Spaces
		1.6.2 Volume of a p-Dimensional Ball
		1.6.3 Tails of a Standard Gaussian Distribution
		1.6.4 Principal Component Analysis
		1.6.5 Basics of Linear Regression
		1.6.6 Concentration of Square Norm of Gaussian Random Variable
		1.6.7 A Simple Proof of Gaussian Concentration
2 Model Selection
	2.1 Statistical Setting
	2.2 Selecting among a Collection of Models
		2.2.1 Models and Oracle
		2.2.2 Model Selection Procedures
	2.3 Risk Bound for Model Selection
		2.3.1 Oracle Risk Bound
	2.4 Computational Issues
	2.5 Illustration
	2.6 Alternative Point of View on Model Selection
	2.7 Discussion and References
		2.7.1 Take-Home Message
		2.7.2 References
	2.8 Exercises
		2.8.1 Orthogonal Design
		2.8.2 Risk Bounds for the Different Sparsity Settings
		2.8.3 Collections of Nested Models
		2.8.4 Segmentation with Dynamic Programming
		2.8.5 Goldenshluger–Lepski Method
		2.8.6 Estimation under Convex Constraints
3 Minimax Lower Bounds
	3.1 Minimax Risk
	3.2 Recipe for Proving Lower Bounds
		3.2.1 Fano’s Lemma
		3.2.2 From Fano’s Lemma to a Lower Bound over a Finite Set
		3.2.3 Back to the Original Problem: Finding a Good Discretization
	3.3 Illustration
	3.4 Minimax Risk for Coordinate-Sparse Regression
		3.4.1 Lower Bound on the Minimax Risk
		3.4.2 Minimax Optimality of the Model Selection Estimator
		3.4.3 Frontier of Estimation in High Dimensions
	3.5 Discussion and References
		3.5.1 Take-Home Message
		3.5.2 References
	3.6 Exercises
		3.6.1 Kullback–Leibler Divergence between Gaussian Distribution
		3.6.2 Spreading Points in a Sparse Hypercube
		3.6.3 Some Other Minimax Lower Bounds
		3.6.4 Non-Parametric Lower Bounds
		3.6.5 Data Processing Inequality and Generalized Fano Inequality
4 Aggregation of Estimators
	4.1 Introduction
	4.2 Gibbs Mixing of Estimators
	4.3 Oracle Risk Bound
	4.4 Numerical Approximation by Metropolis–Hastings
	4.5 Numerical Illustration
	4.6 Discussion and References
		4.6.1 Take-Home Message
		4.6.2 References
	4.7 Exercises
		4.7.1 Gibbs Distribution
		4.7.2 Orthonormal Setting with Power Law Prior
		4.7.3 Group-Sparse Setting
		4.7.4 Gain of Combining
		4.7.5 Online Aggregation
		4.7.6 Aggregation with Laplace Prior
5 Convex Criteria
	5.1 Reminder on Convex Multivariate Functions
		5.1.1 Subdifferentials
		5.1.2 Two Useful Properties
	5.2 Lasso Estimator
		5.2.1 Geometric Insights
		5.2.2 Analytic Insights
		5.2.3 Oracle Risk Bound
		5.2.4 Computing the Lasso Estimator
		5.2.5 Removing the Bias of the Lasso Estimator
	5.3 Convex Criteria for Various Sparsity Patterns
		5.3.1 Group-Lasso for Group Sparsity
		5.3.2 Sparse-Group Lasso for Sparse-Group Sparsity
		5.3.3 Fused-Lasso for Variation Sparsity
	5.4 Discussion and References
		5.4.1 Take-Home Message
		5.4.2 References
	5.5 Exercises
		5.5.1 When Is the Lasso Solution Unique?
		5.5.2 Support Recovery via the Witness Approach
		5.5.3 Lower Bound on the Compatibility Constant
		5.5.4 On the Group-Lasso
		5.5.5 Dantzig Selector
		5.5.6 Projection on the l1-Ball
		5.5.7 Ridge and Elastic-Net
		5.5.8 Approximately Sparse Linear Regression
		5.5.9 Slope Estimator
		5.5.10 Compress Sensing
6 Iterative Algorithms
	6.1 Iterative Hard Thresholding
		6.1.1 Reminder on the Proximal Method
		6.1.2 Iterative Hard-Thresholding Algorithm
		6.1.3 Reconstruction Error
	6.2 Iterative Group Thresholding
	6.3 Discussion and References
		6.3.1 Take-Home Message
		6.3.2 References
	6.4 Exercices
		6.4.1 Linear versus Non-Linear Iterations
		6.4.2 Group Thresholding
		6.4.3 Risk Bound for Iterative Group Thresholding
7 Estimator Selection
	7.1 Estimator Selection
	7.2 Cross-Validation Techniques
	7.3 Complexity Selection Techniques
		7.3.1 Coordinate-Sparse Regression
		7.3.2 Group-Sparse Regression
		7.3.3 Multiple Structures
	7.4 Scale-Invariant Criteria
	7.5 Discussion and References
		7.5.1 Take-Home Message
		7.5.2 References
	7.6 Exercises
		7.6.1 Expected V-Fold CV l2-Risk
		7.6.2 Proof of Corollary 7.5
		7.6.3 Some Properties of Penalty (7.4)
		7.6.4 Selecting the Number of Steps for the Forward Algorithm
8 Multivariate Regression
	8.1 Statistical Setting
	8.2 Reminder on Singular Values
	8.3 Low-Rank Estimation
		8.3.1 When the Rank of A* is Known
		8.3.2 When the Rank of A* Is Unknown
	8.4 Low Rank and Sparsity
		8.4.1 Row-Sparse Matrices
		8.4.2 Criterion for Row-Sparse and Low-Rank Matrices
		8.4.3 Convex Criterion for Low-Rank Matrices
		8.4.4 Computationally Efficient Algorithm for Row-Sparse and Low-Rank Matrices
	8.5 Discussion and References
		8.5.1 Take-Home Message
		8.5.2 References
	8.6 Exercises
		8.6.1 Hard Thresholding of the Singular Values
		8.6.2 Exact Rank Recovery
		8.6.3 Rank Selection with Unknown Variance
9 Graphical Models
	9.1 Reminder on Conditional Independence
	9.2 Graphical Models
		9.2.1 Directed Acyclic Graphical Models
		9.2.2 Non-Directed Models
	9.3 Gaussian Graphical Models
		9.3.1 Connection with the Precision Matrix and the Linear Regression
		9.3.2 Estimating g by Multiple Testing
		9.3.3 Sparse Estimation of the Precision Matrix
		9.3.4 Estimation by Regression
	9.4 Practical Issues
	9.5 Discussion and References
		9.5.1 Take-Home Message
		9.5.2 References
	9.6 Exercises
		9.6.1 Factorization in Directed Models
		9.6.2 Moralization of a Directed Graph
		9.6.3 Convexity of —log(det(K))
		9.6.4 Block Gradient Descent with the l1=l2 Penalty
		9.6.5 Gaussian Graphical Models with Hidden Variables
		9.6.6 Dantzig Estimation of Sparse Gaussian Graphical Models
		9.6.7 Gaussian Copula Graphical Models
		9.6.8 Restricted Isometry Constant for Gaussian Matrices
10 Multiple Testing
	10.1 Introductory Example
		10.1.1 Differential Expression of a Single Gene
		10.1.2 Differential Expression of Multiple Genes
	10.2 Statistical Setting
		10.2.1 p-Values
		10.2.2 Multiple-Testing Setting
		10.2.3 Bonferroni Correction
	10.3 Controlling the False Discovery Rate
		10.3.1 Heuristics
		10.3.2 Step-Up Procedures
		10.3.3 FDR Control under the WPRD Property
	10.4 Illustration
	10.5 Discussion and References
		10.5.1 Take-Home Message
		10.5.2 References
	10.6 Exercises
		10.6.1 FDR versus FWER
		10.6.2 WPRD Property
		10.6.3 Positively Correlated Normal Test Statistics
11 Supervised Classification
	11.1 Statistical Modeling
		11.1.1 Bayes Classifier
		11.1.2 Parametric Modeling
		11.1.3 Semi-Parametric Modeling
		11.1.4 Non-Parametric Modeling
	11.2 Empirical Risk Minimization
		11.2.1 Misclassification Probability of the Empirical Risk Minimizer
		11.2.2 Vapnik–Chervonenkis Dimension
		11.2.3 Dictionary Selection
	11.3 From Theoretical to Practical Classifiers
		11.3.1 Empirical Risk Convexification
		11.3.2 Statistical Properties
		11.3.3 Support Vector Machines
		11.3.4 AdaBoost
		11.3.5 Classifier Selection
	11.4 Discussion and References
		11.4.1 Take-Home Message
		11.4.2 References
	11.5 Exercises
		11.5.1 Linear Discriminant Analysis
		11.5.2 VC Dimension of Linear Classifiers in Rd
		11.5.3 Linear Classifiers with Margin Constraints
		11.5.4 Spectral Kernel
		11.5.5 Computation of the SVM Classifier
		11.5.6 Kernel Principal Component Analysis
12 Clustering
	12.1 Proximity-Separation-Based Clustering
		12.1.1 Clustering According to Proximity and Separation
		12.1.2 Kmeans Paradigm
		12.1.3 Hierarchical Clustering Algorithms
	12.2 Model-Based Clustering
		12.2.1 Gaussian Sub-Population Model
		12.2.2 MLE Estimator
	12.3 Kmeans
		12.3.1 Kmeans Algorithm
		12.3.2 Bias of Kmeans
		12.3.3 Debiasing Kmeans
	12.4 Semi-Definite Programming Relaxation
	12.5 Lloyd Algorithm
		12.5.1 Bias of Lloyd Algorithm
	12.6 Spectral Algorithm
	12.7 Recovery Bounds
		12.7.1 Benchmark: Supervised Case
		12.7.2 Analysis of Spectral Clustering
		12.7.3 Analysis of Lloyd Algorithm
	12.8 Discussion and References
		12.8.1 Take-Home Message
		12.8.2 References
	12.9 Exercises
		12.9.1 Exact Recovery with Hierarchical Clustering
		12.9.2 Bias of Kmeans
		12.9.3 Debiasing Kmeans
		12.9.4 Bayes Classifier for the Supervised Case
		12.9.5 Cardinality of an ε-Net
		12.9.6 Operator Norm of a Random Matrix
		12.9.7 Large Deviation for the Binomial Distribution
		12.9.8 Sterling Numbers of the Second Kind
		12.9.9 Gaussian Mixture Model and EM Algorithm
Appendix A Gaussian Distribution
	A.1 Gaussian Random Vectors
	A.2 Chi-Square Distribution
	A.3 Gaussian Conditioning
Appendix B Probabilistic Inequalities
	B.1 Basic Inequalities
	B.2 Concentration Inequalities
		B.2.1 McDiarmid Inequality
		B.2.2 Gaussian Concentration Inequality
		B.2.3 Concentration of Quadratic Forms of Gaussian Vectors
	B.3 Symmetrization and Contraction Lemmas
		B.3.1 Symmetrization Lemma
		B.3.2 Contraction Principle
	B.4 Birgé’s Inequality
Appendix C Linear Algebra
	C.1 Singular Value Decomposition
	C.2 Moore–Penrose Pseudo-Inverse
	C.3 Matrix Norms
	C.4 Matrix Analysis
		C.4.1 Characterization of the Singular Values
		C.4.2 Best Low-Rank Approximation
	C.5 Perturbation Bounds
		C.5.1 Weyl Inequality
		C.5.2 Eigenspaces Localization
Appendix D Subdifferentials of Convex Functions
	D.1 Subdifferentials and Subgradients
	D.2 Examples of Subdifferentials
Appendix E Reproducing Kernel Hilbert Spaces
Notations
Bibliography
Index