Home
Hello! Our names are Jiri and Wessel. On this blog, we will post our or others’ solutions to the exercises from High-Dimensional Statistics: A Non-Asymptotic Viewpoint by Martin J. Wainwright. Find out more about us here.
Due to legal reasons, we are unfortunately unable to restate the text of the questions. You can purchase the book here, or gain access here if you are a student at the University of Cambridge.
Tags
General
Chapter 2
-
22 July 2020 Exercise 2.1: Tightness of Inequalities -
25 July 2020 Exercise 2.2: Mills Ratio -
25 July 2020 Exercise 2.3: Polynomial Markov Versus Chernoff -
25 July 2020 Exercise 2.4: Sharp Sub-Gaussian Parameter for Bounded Random Variable -
21 August 2020 Exercise 2.5: Sub-gaussian Bounds and Means and Variances -
25 July 2020 Exercise 2.6: Lower Bounds on Squared Sub-Gaussians -
27 August 2020 Exercise 2.7: Bennett's Inequality -
27 August 2020 Exercise 2.8: Bernstein and Expectations -
27 August 2020 Exercise 2.9: Sharp Upper Bounds on Binomial Tails -
24 August 2020 Exercise 2.10: Lower Bounds on Binomial Tails -
27 August 2020 Exercise 2.11: Upper and Lower Bounds for Gaussian Maxima -
25 August 2020 Exercise 2.12: Upper Bounds for Sub-Gaussian Maxima -
27 August 2020 Exercise 2.13: Operations on Sub-Gaussian Variables -
25 August 2020 Exercise 2.14: Concentration Around Medians and Means -
27 August 2020 Exercise 2.15: Concentration and Kernel Density Estimation -
26 August 2020 Exercise 2.16: Deviation Inequalities in Hilbert Space -
27 August 2020 Exercise 2.17: Hanson–Wright Inequality -
27 August 2020 Exercise 2.18: Orlicz Norms -
27 August 2020 Exercise 2.19: Maxima of Orlicz Variables -
27 August 2020 Exercise 2.20: Tail Bounds Under Moment Conditions -
9 October 2020 Exercise 2.21: Concentration and Data Compression -
28 August 2020 Exercise 2.22: Concentration for Spin Glasses
Chapter 3
-
10 October 2020 Exercise 3.1: Shannon Entropy and Kullback–Leibler Divergence -
5 September 2020 Exercise 3.2: Chain Rule for Kullback-Leibler Divergence -
10 October 2020 Exercise 3.3: Variational Representation of Entropy -
19 October 2020 Exercise 3.4: Entropy and Constant Shifts -
10 October 2020 Exercise 3.5: Equivalent Forms of Entropy -
19 October 2020 Exercise 3.6: Entropy Rescaling -
10 October 2020 Exercise 3.7: Entropy for Bounded Variables -
20 October 2020 Exercise 3.8: Exponential Families and Entropy -
10 October 2020 Exercise 3.9: Another Variational Representation -
21 October 2020 Exercise 3.10: Brunn–Minkowski and Classical Isoperimetric Inequality -
10 October 2020 Exercise 3.11: Concentration on the Euclidean Ball -
21 October 2020 Exercise 3.12: Rademacher Chaos Variables -
10 October 2020 Exercise 3.13: Total Variation and Wasserstein -
22 October 2020 Exercise 3.14: Transportation Cost Inequality -
10 October 2020 Exercise 3.15: Bounds for Suprema of Non-Negative Functions -
22 October 2020 Exercise 3.16: Different Forms of Functional Bernstein Inequality
Chapter 4
-
2 March 2021 Exercise 4.1: Continuity of Functionals -
30 October 2020 Exercise 4.2: Failure of Glivenko–Cantelli -
2 March 2021 Exercise 4.3: Maximum Likelihood and Uniform Laws -
30 October 2020 Exercise 4.4: Details of Symmetrisation Argument -
2 March 2021 Exercise 4.5: Necessity of Vanishing Rademacher Complexity -
30 October 2020 Exercise 4.6: Too Many Linear Classifiers -
2 March 2021 Exercise 4.7: Basic Properties of Rademacher Complexity -
30 October 2020 Exercise 4.8: Operations on VC Classes -
2 March 2021 Exercise 4.9: Proof of Lemma 4.14 -
30 October 2020 Exercise 4.10: Pascal's Rule -
2 March 2021 Exercise 4.11: Completion of Proof of Proposition 4.18 -
30 October 2020 Exercise 4.12: VC Dimension of Left-Sided Intervals -
2 March 2021 Exercise 4.13: VC Dimension of Spheres -
30 October 2020 Exercise 4.14: VC Dimension of Monotone Boolean Conjunctions -
2 March 2021 Exercise 4.15: VC Dimension of Closed and Convex Sets -
30 October 2020 Exercise 4.16: VC Dimension of Polygons -
2 March 2021 Exercise 4.17: Infinite VC Dimension
Chapter 5
-
8 April 2021 Exercise 5.1: Failure of Total Boundedness -
19 February 2021 Exercise 5.2: Packing and Covering Sandwich Inequality -
8 April 2021 Exercise 5.3: Packing of the Boolean Hypercube -
19 February 2021 Exercise 5.4: From VC Dimension to Metric Entropy -
8 April 2021 Exercise 5.5: Gaussian and Rademacher Complexity -
19 February 2021 Exercise 5.6: Gaussian Complexity for $\ell_q$-Balls -
8 April 2021 Exercise 5.7: Upper Bound for $\ell_0$-"Balls" -
19 February 2021 Exercise 5.8: Lower Bounds for $\ell_0$-"Balls" -
8 April 2021 Exercise 5.9: Gaussian Complexity of Ellipsoids -
1 March 2021 Exercise 5.10: Concentration of Gaussian Suprema -
8 April 2021 Exercise 5.11: Details of Example 5.19 -
1 March 2021 Exercise 5.12: Gaussian Contraction Inequality -
8 April 2021 Exercise 5.13: Details of Example 5.33 -
1 March 2021 Exercise 5.14: Maximum Singular Value of Gaussian Random Matrices
Chapter 6
-
9 April 2021 Exercise 6.1: Bounds on Eigenvalues -
5 March 2021 Exercise 6.2: Relations Between Matrix Operator Norms -
9 April 2021 Exercise 6.3: Nonnegative Matrices and Operator Norms -
5 March 2021 Exercise 6.4: Inequality for Matrix Exponential -
9 April 2021 Exercise 6.5: Matrix Monotone Functions -
5 March 2021 Exercise 6.6: Variance and Positive Semidefiniteness -
9 April 2021 Exercise 6.7: Sub-Gaussian Random Matrices -
17 March 2021 Exercise 6.8: Sub-Gaussian matrices and Mean Bounds -
9 April 2021 Exercise 6.9: Bounded Matrices and Bernstein Condition -
17 March 2021 Exercise 6.10: Tail Bounds for Non-Symmetric Matrices -
9 April 2021 Exercise 6.11: Unbounded Matrices and Bernstein Bounds -
17 March 2021 Exercise 6.12: Sharpened Matrix Bernstein Inequality -
9 April 2021 Exercise 6.13: Bernstein's Inequality for Vectors -
17 March 2021 Exercise 6.14: Random Sphere Packings -
9 April 2021 Exercise 6.15: Bernstein's Inequality for Vectors -
17 March 2021 Exercise 6.16: Graphs and Adjacency Matrices
Chapter 12
-
9 April 2021 Exercise 12.1: Closedness of Nullspace -
19 June 2021 Exercise 12.2: Projections in a Hilbert space -
9 April 2021 Exercise 12.3: Direct Sum Decomposition of Hilbert Space -
19 June 2021 Exercise 12.4: Uniqueness of Kernel -
9 April 2021 Exercise 12.5: Kernels and Cauchy–Schwarz -
19 June 2021 Exercise 12.6: Eigenfunctions for Linear Kernels -
9 April 2021 Exercise 12.7: Different Kernels for Polynomial Functions -
19 June 2021 Exercise 12.8: PSD Kernels -
9 April 2021 Exercise 12.9: Left–Right Multiplication and Kernels -
19 June 2021 Exercise 12.10: Kernels and Power Sets -
9 April 2021 Exercise 12.11: Feature Map for Polynomial Kernel -
19 June 2021 Exercise 12.12: Probability Spaces and Kernels -
9 April 2021 Exercise 12.13: From Sets to Power Sets -
19 June 2021 Exercise 12.14: Kernel and Function Boundedness -
9 April 2021 Exercise 12.15: Sobolev Kernels and Norms -
19 June 2021 Exercise 12.16: Kernel and Function Boundedness -
9 April 2021 Exercise 12.17: Total Variation Norm -
19 June 2021 Exercise 12.18: RKHS-induced Semi-metrics -
9 April 2021 Exercise 12.19: Positive Semidefiniteness of Gaussian Kernel -
19 June 2021 Exercise 12.20: Support Vector Machines and Kernel Methods
Chapter 13
-
9 April 2021 Exercise 13.1: Characterisation of the Bayes Least-Squares Estimate -
26 August 2021 Exercise 13.2: Prediction Error in Linear Regression -
9 April 2021 Exercise 13.3: Cubic Smoothing Splines -
26 August 2021 Exercise 13.4: Star-Shaped Sets and Convexity -
9 April 2021 Exercise 13.5: Lower Bounds on the Critical Inequality -
3 May 2021 Exercise 13.6: Local Gaussian Complexity and Adaptivity -
9 April 2021 Exercise 13.7: Rates for Polynomial Regression -
26 August 2021 Exercise 13.8: Rates for Twice-Differentiable Functions -
9 April 2021 Exercise 13.9: Rates for Additive Nonparametric Models -
26 August 2021 Exercise 13.10: Orthogonal Series Expansions -
9 April 2021 Exercise 13.11: Differentiable Functions and Fourier Coefficients
Chapter 14
-
9 April 2021 Exercise 14.1: Bounding the Lipschitz Constant -
12 September 2021 Exercise 14.2: Properties of Local Rademacher Complexity -
9 April 2021 Exercise 14.3: Sharper Rates via Entropy Integrals -
12 September 2021 Exercise 14.4: Uniform Laws for Kernel Classes -
9 April 2021 Exercise 14.5: Empirical Approximations of Kernel Integral Operators -
12 September 2021 Exercise 14.6: Linear Functions and Four-Way Independence -
9 September 2021 Exercise 14.7: Uniform Laws and Sparse Eigenvalues -
12 September 2021 Exercise 14.8: Estimation of Nonparametric Additive Models -
9 September 2021 Exercise 14.9: Nonparametric Maximum Likelihood -
12 September 2021 Exercise 14.10: Hellinger Distance and Kullback–Leibler Divergence -
9 September 2021 Exercise 14.11: Bounds on Histogram Density Estimation
Chapter 15
-
9 September 2021 Exercise 15.1: Alternative Representation of Total Variation Norm -
29 January 2022 Exercise 15.2: Basics of Discrete Entropy -
9 September 2021 Exercise 15.3: Properties of the Kullback–Leibler Divergence -
29 January 2022 Exercise 15.4: More Properties of Shannon Entropy -
9 September 2021 Exercise 15.5: Le Cam's Inequality -
29 January 2022 Exercise 15.6: Pinsker–Csiszar–Kullback Inequality -
9 September 2021 Exercise 15.7: Decoupling for Hellinger Distance -
29 January 2022 Exercise 15.8: Sharper Bounds for Gaussian Location Families -
29 January 2022 Exercise 15.9: Achievable Rates for Uniform Shift Family -
29 January 2022 Exercise 15.10: Bounds on TV Distance -
9 September 2021 Exercise 15.11: Mixture Distribution and KL Divergence -
29 January 2022 Exercise 15.12: $f$-Divergences -
9 September 2021 Exercise 15.13: KL Divergence for Multivariate Gaussian -
29 January 2022 Exercise 15.14: Gaussian Distributions And Maximum Entropy -
9 September 2021 Exercise 15.15: Sharper Bound for Variable Selection in Sparse PCA -
29 January 2022 Exercise 15.16: Lower Bounds for Sparse PCA in $\ell^2$-Error -
9 September 2021 Exercise 15.17: Lower Bounds for Generalised Linear Models -
2 February 2022 Exercise 15.18: Lower Bounds for Additive Nonparametric Regression
Bounded Differences Inequality
-
27 August 2020 Exercise 2.15: Concentration and Kernel Density Estimation -
26 August 2020 Exercise 2.16: Deviation Inequalities in Hilbert Space -
2 March 2021 Exercise 4.5: Necessity of Vanishing Rademacher Complexity
Chernoff Bound
-
25 July 2020 Exercise 2.3: Polynomial Markov Versus Chernoff -
27 August 2020 Exercise 2.7: Bennett's Inequality -
27 August 2020 Exercise 2.9: Sharp Upper Bounds on Binomial Tails -
25 August 2020 Exercise 2.14: Concentration Around Medians and Means -
27 August 2020 Exercise 2.18: Orlicz Norms -
21 October 2020 Exercise 3.12: Rademacher Chaos Variables -
19 February 2021 Exercise 5.8: Lower Bounds for $\ell_0$-"Balls"
Entropy Integral
Gaussian Mgf
-
27 August 2020 Exercise 2.13: Operations on Sub-Gaussian Variables -
28 August 2020 Exercise 2.22: Concentration for Spin Glasses
Incomplete
-
25 July 2020 Exercise 2.6: Lower Bounds on Squared Sub-Gaussians -
27 August 2020 Exercise 2.11: Upper and Lower Bounds for Gaussian Maxima -
25 August 2020 Exercise 2.14: Concentration Around Medians and Means -
26 August 2020 Exercise 2.16: Deviation Inequalities in Hilbert Space -
28 August 2020 Exercise 2.22: Concentration for Spin Glasses -
10 October 2020 Exercise 3.7: Entropy for Bounded Variables -
2 March 2021 Exercise 4.3: Maximum Likelihood and Uniform Laws -
8 April 2021 Exercise 5.11: Details of Example 5.19
Layer Cake
-
25 July 2020 Exercise 2.6: Lower Bounds on Squared Sub-Gaussians -
27 August 2020 Exercise 2.8: Bernstein and Expectations -
27 August 2020 Exercise 2.11: Upper and Lower Bounds for Gaussian Maxima -
25 August 2020 Exercise 2.14: Concentration Around Medians and Means -
27 August 2020 Exercise 2.18: Orlicz Norms
Lipschitz Gaussian
-
28 August 2020 Exercise 2.22: Concentration for Spin Glasses -
8 April 2021 Exercise 5.7: Upper Bound for $\ell_0$-"Balls" -
1 March 2021 Exercise 5.10: Concentration of Gaussian Suprema -
1 March 2021 Exercise 5.14: Maximum Singular Value of Gaussian Random Matrices -
9 April 2021 Exercise 13.9: Rates for Additive Nonparametric Models