book

Introduction to High-Dimensional Statistics, 2nd Edition

by Christophe Giraud

August 2021

Intermediate to advanced

364 pages

10h 41m

English

Chapman and Hall/CRC

Read now

Unlock full access

1.1 High-Dimensional Data1.2 Curse of Dimensionality1.2.1 Lost in the Immensity of High-Dimensional Spaces1.2.2 Fluctuations Cumulate1.2.3 Accumulation of Rare Events May Not Be Rare1.2.4 Computational Complexity1.3 High-Dimensional Statistics1.3.1 Circumventing the Curse of Dimensionality1.3.2 A Paradigm Shift1.3.3 Mathematics of High-Dimensional Statistics1.4 About This Book1.4.1 Statistics and Data Analysis1.4.2 Purpose of This Book1.4.3 Overview1.5 Discussion and References1.5.1 Take-Home Message1.5.2 References1.6 Exercises1.6.1 Strange Geometry of High-Dimensional Spaces1.6.2 Volume of a p-Dimensional Ball1.6.3 Tails of a Standard Gaussian Distribution1.6.4 Principal Component Analysis1.6.5 Basics of Linear Regression1.6.6 Concentration of Square Norm of Gaussian Random Variable1.6.7 A Simple Proof of Gaussian Concentration
2.1 Statistical Setting2.2 Selecting among a Collection of Models2.2.1 Models and Oracle2.2.2 Model Selection Procedures2.3 Risk Bound for Model Selection2.3.1 Oracle Risk Bound2.4 Computational Issues2.5 Illustration2.6 Alternative Point of View on Model Selection2.7 Discussion and References2.7.1 Take-Home Message2.7.2 References2.8 Exercises2.8.1 Orthogonal Design2.8.2 Risk Bounds for the Different Sparsity Settings2.8.3 Collections of Nested Models2.8.4 Segmentation with Dynamic Programming2.8.5 Goldenshluger–Lepski Method2.8.6 Estimation under Convex Constraints

3.1 Minimax Risk3.2 Recipe for Proving Lower Bounds3.2.1 Fano’s Lemma3.2.2 From Fano’s Lemma to a Lower Bound over a Finite Set3.2.3 Back to the Original Problem: Finding a Good Discretization3.3 Illustration3.4 Minimax Risk for Coordinate-Sparse Regression3.4.1 Lower Bound on the Minimax Risk3.4.2 Minimax Optimality of the Model Selection Estimator3.4.3 Frontier of Estimation in High Dimensions3.5 Discussion and References3.5.1 Take-Home Message3.5.2 References3.6 Exercises3.6.1 Kullback–Leibler Divergence between Gaussian Distribution3.6.2 Spreading Points in a Sparse Hypercube3.6.3 Some Other Minimax Lower Bounds3.6.4 Non-Parametric Lower Bounds3.6.5 Data Processing Inequality and Generalized Fano Inequality
4.1 Introduction4.2 Gibbs Mixing of Estimators4.3 Oracle Risk Bound4.4 Numerical Approximation by Metropolis–Hastings4.5 Numerical Illustration4.6 Discussion and References4.6.1 Take-Home Message4.6.2 References4.7 Exercises4.7.1 Gibbs Distribution4.7.2 Orthonormal Setting with Power Law Prior4.7.3 Group-Sparse Setting4.7.4 Gain of Combining4.7.5 Online Aggregation4.7.6 Aggregation with Laplace Prior
5.1 Reminder on Convex Multivariate Functions5.1.1 Subdifferentials5.1.2 Two Useful Properties5.2 Lasso Estimator5.2.1 Geometric Insights5.2.2 Analytic Insights5.2.3 Oracle Risk Bound5.2.4 Computing the Lasso Estimator5.2.5 Removing the Bias of the Lasso Estimator5.3 Convex Criteria for Various Sparsity Patterns5.3.1 Group-Lasso for Group Sparsity5.3.2 Sparse-Group Lasso for Sparse-Group Sparsity5.3.3 Fused-Lasso for Variation Sparsity5.4 Discussion and References5.4.1 Take-Home Message5.4.2 References5.5 Exercises5.5.1 When Is the Lasso Solution Unique?5.5.2 Support Recovery via the Witness Approach5.5.3 Lower Bound on the Compatibility Constant5.5.4 On the Group-Lasso5.5.5 Dantzig Selector5.5.6 Projection on the ℓ1-Ball5.5.7 Ridge and Elastic-Net5.5.8 Approximately Sparse Linear Regression5.5.9 Slope Estimator5.5.10 Compress Sensing
6.1 Iterative Hard Thresholding6.1.1 Reminder on the Proximal Method6.1.2 Iterative Hard-Thresholding Algorithm6.1.3 Reconstruction Error6.2 Iterative Group Thresholding6.3 Discussion and References6.3.1 Take-Home Message6.3.2 References6.4 Exercices6.4.1 Linear versus Non-Linear Iterations6.4.2 Group Thresholding6.4.3 Risk Bound for Iterative Group Thresholding
7.1 Estimator Selection7.2 Cross-Validation Techniques7.3 Complexity Selection Techniques7.3.1 Coordinate-Sparse Regression7.3.2 Group-Sparse Regression7.3.3 Multiple Structures7.4 Scale-Invariant Criteria7.5 Discussion and References7.5.1 Take-Home Message7.5.2 References7.6 Exercises7.6.1 Expected V-Fold CV ℓ2-Risk7.6.2 Proof of Corollary 7.57.6.3 Some Properties of Penalty (7.4)7.6.4 Selecting the Number of Steps for the Forward Algorithm
8.1 Statistical Setting8.2 Reminder on Singular Values8.3 Low-Rank Estimation8.3.1 When the Rank of A* is Known8.3.2 When the Rank of A* Is Unknown8.4 Low Rank and Sparsity8.4.1 Row-Sparse Matrices8.4.2 Criterion for Row-Sparse and Low-Rank Matrices8.4.3 Convex Criterion for Low-Rank Matrices8.4.4 Computationally Efficient Algorithm for Row-Sparse and Low-Rank Matrices8.5 Discussion and References8.5.1 Take-Home Message8.5.2 References8.6 Exercises8.6.1 Hard Thresholding of the Singular Values8.6.2 Exact Rank Recovery8.6.3 Rank Selection with Unknown Variance
9.1 Reminder on Conditional Independence9.2 Graphical Models9.2.1 Directed Acyclic Graphical Models9.2.2 Non-Directed Models9.3 Gaussian Graphical Models9.3.1 Connection with the Precision Matrix and the Linear Regression9.3.2 Estimating g by Multiple Testing9.3.3 Sparse Estimation of the Precision Matrix9.3.4 Estimation by Regression9.4 Practical Issues9.5 Discussion and References9.5.1 Take-Home Message9.5.2 References9.6 Exercises9.6.1 Factorization in Directed Models9.6.2 Moralization of a Directed Graph9.6.3 Convexity of –log(det(K))9.6.4 Block Gradient Descent with the ℓ1/ℓ2 Penalty9.6.5 Gaussian Graphical Models with Hidden Variables9.6.6 Dantzig Estimation of Sparse Gaussian Graphical Models9.6.7 Gaussian Copula Graphical Models9.6.8 Restricted Isometry Constant for Gaussian Matrices
10.1 Introductory Example10.1.1 Differential Expression of a Single Gene10.1.2 Differential Expression of Multiple Genes10.2 Statistical Setting10.2.1 p-Values10.2.2 Multiple-Testing Setting10.2.3 Bonferroni Correction10.3 Controlling the False Discovery Rate10.3.1 Heuristics10.3.2 Step-Up Procedures10.3.3 FDR Control under the WPRD Property10.4 Illustration10.5 Discussion and References10.5.1 Take-Home Message10.5.2 References10.6 Exercises10.6.1 FDR versus FWER10.6.2 WPRD Property10.6.3 Positively Correlated Normal Test Statistics
11.1 Statistical Modeling11.1.1 Bayes Classifier11.1.2 Parametric Modeling11.1.3 Semi-Parametric Modeling11.1.4 Non-Parametric Modeling11.2 Empirical Risk Minimization11.2.1 Misclassification Probability of the Empirical Risk Minimizer11.2.2 Vapnik–Chervonenkis Dimension11.2.3 Dictionary Selection11.3 From Theoretical to Practical Classifiers11.3.1 Empirical Risk Convexification11.3.2 Statistical Properties11.3.3 Support Vector Machines11.3.4 AdaBoost11.3.5 Classifier Selection11.4 Discussion and References11.4.1 Take-Home Message11.4.2 References11.5 Exercises11.5.1 Linear Discriminant Analysis11.5.2 VC Dimension of Linear Classifiers in ℝd11.5.3 Linear Classifiers with Margin Constraints11.5.4 Spectral Kernel11.5.5 Computation of the SVM Classifier11.5.6 Kernel Principal Component Analysis
12.1 Proximity-Separation-Based Clustering12.1.1 Clustering According to Proximity and Separation12.1.2 Kmeans Paradigm12.1.3 Hierarchical Clustering Algorithms12.2 Model-Based Clustering12.2.1 Gaussian Sub-Population Model12.2.2 MLE Estimator12.3 Kmeans12.3.1 Kmeans Algorithm12.3.2 Bias of Kmeans12.3.3 Debiasing Kmeans12.4 Semi-Definite Programming Relaxation12.5 Lloyd Algorithm12.5.1 Bias of Lloyd Algorithm12.6 Spectral Algorithm12.7 Recovery Bounds12.7.1 Benchmark: Supervised Case12.7.2 Analysis of Spectral Clustering12.7.3 Analysis of Lloyd Algorithm12.8 Discussion and References12.8.1 Take-Home Message12.8.2 References12.9 Exercises12.9.1 Exact Recovery with Hierarchical Clustering12.9.2 Bias of Kmeans12.9.3 Debiasing Kmeans12.9.4 Bayes Classifier for the Supervised Case12.9.5 Cardinality of an ε-Net12.9.6 Operator Norm of a Random Matrix12.9.7 Large Deviation for the Binomial Distribution12.9.8 Sterling Numbers of the Second Kind12.9.9 Gaussian Mixture Model and EM Algorithm
A.1 Gaussian Random VectorsA.2 Chi-Square DistributionA.3 Gaussian Conditioning
B.1 Basic InequalitiesB.2 Concentration InequalitiesB.2.1 McDiarmid InequalityB.2.2 Gaussian Concentration InequalityB.2.3 Concentration of Quadratic Forms of Gaussian VectorsB.3 Symmetrization and Contraction LemmasB.3.1 Symmetrization LemmaB.3.2 Contraction PrincipleB.4 Birgé’s Inequality
C.1 Singular Value DecompositionC.2 Moore–Penrose Pseudo-InverseC.3 Matrix NormsC.4 Matrix AnalysisC.4.1 Characterization of the Singular ValuesC.4.2 Best Low-Rank ApproximationC.5 Perturbation BoundsC.5.1 Weyl InequalityC.5.2 Eigenspaces Localization
D.1 Subdifferentials and SubgradientsD.2 Examples of Subdifferentials

Content preview from Introduction to High-Dimensional Statistics, 2nd Edition

Chapter 3 Minimax Lower Bounds

DOI:10.1201/9781003158745-3

The goal of the statistician is to infer information as accurately as possible from data. From a theoretical perspective, when investigating a given statistical model, her goal is to propose an estimator with the smallest possible risk, ideally with a low computational complexity. In particular, when analyzing a given estimator, not only we must derive an upper bound on the risk as in the previous chapter, but also, we must derive a lower bound on the risk achievable by the best possible estimator. Then, we can compare if the upper and lower bounds match. If so, we have the guarantee that the proposed estimator is optimal (in terms of the chosen risk).

Deriving lower bounds is then ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.

Start your free trial

Introduction to High-Dimensional Statistics

Publisher Resources

ISBN: 9781000408355

Introduction to High-Dimensional Statistics, 2nd Edition

by Christophe Giraud

Chapter 3

Minimax Lower Bounds

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.

You might also like