Source-linked AI summary
A tail inequality for quadratic forms of subgaussian random vectors
Daniel Hsu, Sham M. Kakade, Tong Zhang
TL;DR
The paper addresses concentration of positive semidefinite quadratic forms when the entries form a subgaussian random vector, extending a Gaussian-style question beyond the Gaussian setting. It provides a sharp upper-tail inequality with a simple proof and explicit constants, matching the Gaussian analogue, and applies it to fixed-design linear regression with subgaussian noise.
Problem
The paper asks how closely ∥Ax∥2 concentrates around its expectation for subgaussian random vectors, where bounded-variable bounds can be suboptimal.
Method
The paper proves a sharp subgaussian quadratic-form tail inequality using a simple argument with Gaussian comparison and martingale tools.
Results
The resulting bound has explicit constants matching the analogous bound for independent standard Gaussian variables.
Takeaways & Limitations
The inequality applies to positive semidefinite quadratic forms and to fixed-design linear regression with subgaussian noise.
Takeaways & Limitations
The result assumes a subgaussian random vector characterized by a parameter σ, while bounded-variable martingale arguments can be suboptimal for subgaussian inputs.
Abstract
from arXiv · showhide
We prove an exponential probability tail inequality for positive semidefinite quadratic forms in a subgaussian random vector. The bound is analogous to one that holds when the vector has independent Gaussian entries.
1 Introduction
The paper studies concentration of quadratic forms in subgaussian random vectors and develops a sharp upper-tail bound analogous to the Gaussian result. It also connects the bound to squared norms of random sums and explains why bounded-variable approaches can be suboptimal.
- Motivation: The central quantity is the deviation of ∥Ax∥2 = x⊤(A⊤A)x from its expectation for a random vector x.Here A is fixed, while ∥·∥ and ∥·∥ denote Euclidean and spectral norms, respectively.
- Main contribution: The paper extends Gaussian quadratic-form concentration to subgaussian random vectors with a sharp upper-tail bound.The stated result is analogous to the Gaussian bound and coincides with Proposition 1 when σ = 1.
- Motivation: The squared norm of a random sum can be expressed through a matrix whose columns are the summand vectors, motivating the quadratic-form analysis.For vectors a1, . . . , an and A = [a1| · · · |an], the paper considers the squared norm of the associated random sum.
- Earlier approach: A martingale-difference argument yields exponentially decaying upper tails under mild boundedness assumptions on the summands.Applying the stated lemma with ui = aixi produces a bound with probability at least 1 − e−t when the xi are almost surely bounded by 1 or another constant.
- Limitation of earlier approach: The bounded-variable bound can be suboptimal for subgaussian variables, including Rademacher variables.The paper motivates its main result partly by improving deviation terms that can be significantly smaller, especially for large t.
- Proof strategy: The paper gives a simple proof with explicit constants matching the analogous bound for independent standard Gaussian variables.The Gaussian proposition relies on rotational invariance and a tail bound for linear combinations of χ2 random variables.
2 Positive semidefinite quadratic forms
Theorem 1 generalizes the Gaussian quadratic-form tail bound to subgaussian random vectors, with explicit constants matching the independent-Gaussian case. The section also applies the theorem to fixed-design least squares regression with subgaussian noise.
- 2 Positive semidefinite quadratic forms: Theorem 1 gives an exponential tail bound for positive semidefinite quadratic forms generated by a subgaussian random vector.It generalizes the preceding bound while allowing a mean vector μ and subgaussian parameter σ.
- 2 Positive semidefinite quadratic forms: When μ = 0 and σ = 1, the theorem recovers the Gaussian proposition exactly.The paper states that the resulting expression is the same as Proposition 1.
- 2 Positive semidefinite quadratic forms: The proof also establishes an upper bound on the moment generating function of ∥Ax∥2 for 0 ≤ η < 1/(2σ^2∥Σ∥).This auxiliary MGF statement underlies the tail inequality.
- 2 Positive semidefinite quadratic forms: The proof introduces an independent standard Gaussian vector and uses a singular value decomposition of A to reduce the quadratic form to weighted squared Gaussian coordinates.Rotational invariance then expresses the relevant linear and quadratic terms in transformed coordinates.
- 2 Positive semidefinite quadratic forms: The resulting bound combines the Frobenius-scale term sqrt(tr(Σ^2)t) with the operator-norm term ∥Σ∥t.The displayed expression includes the corresponding factors 2 and 2.
- 2 Positive semidefinite quadratic forms: The Gaussian auxiliary lemma controls the logarithmic moment generating function of a weighted sum of squared standard Gaussian variables.The proof restricts the moment parameter using the largest weight and applies elementary bounds before optimizing.
- Example: fixed-design regression with subgaussian noise: The theorem is applied to fixed-design linear regression with the ordinary least squares estimator under subgaussian response assumptions.The design vectors are fixed, the empirical covariance matrix is assumed invertible, and the estimator targets minimum expected squared error.
- Example: fixed-design regression with subgaussian noise: For regression, the excess loss is defined as the difference between the estimator's expected squared error and the minimum expected squared error.In the equal-variance case, the resulting tail inequality is essentially tight for independent Gaussian responses.
A.1 Martingale tail inequalities
The section develops martingale tail tools and applies them to sums of random vectors through a Doob-martingale argument. Bernstein’s inequality controls bounded martingale differences, while auxiliary lemmas establish the needed bounds.
- Bernstein’s inequality applies to martingale differences with conditional mean zero, an almost-sure bound |d_i| ≤ b, and a conditional variance-sum bound ≤ v.
- The proof of Proposition 2 combines the two lemmas with Jensen’s inequality, and the martingale-vector lemma is completed by induction.
- For random-vector sums, the Doob martingale differences are conditional increments of E[∥s_n∥], and they sum to ∥s_n∥ − E[∥s_n∥].
- The triangle inequality bounds each increment through the current vector norm and its conditional expectation, yielding |d_i| ≤ 2b almost surely.
A.2 Gaussian quadratic forms and χ2 tail inequalities
The section recalls the Gaussian-to-χ2 reduction for quadratic forms and invokes the Laurent–Massart inequality to control weighted sums of independent one-degree-of-freedom χ2 variables.
- A standard Gaussian square z^2 has a χ2 distribution with one degree of freedom, enabling χ2 tail bounds for linear combinations.
- Laurent–Massart’s lemma bounds weighted sums of independent χ2 variables with one degree of freedom for non-negative weights and t > 0.
- An eigen-decomposition and rotational invariance transform ∥Ax∥2 into a weighted sum of squared independent Gaussian coordinates, so the χ2 tail lemma yields the proposition.