Source-linked AI summary
Tail bounds via generic chaining
Sjoerd Dirksen
TL;DR
Expected-supremum bounds alone are often insufficient for applications requiring exceedance probabilities. The paper modifies generic chaining to control all p-th moments and converts these bounds into upper-tail estimates with sharp deviation parameters. It applies the method to unbounded or dependent empirical processes, chaos processes, and a simplified restricted-isometry proof for subsampled discrete Fourier transforms.
Problem
Applications often require probabilities that a process supremum exceeds its upper bound, not only an expected-supremum estimate.
Method
The paper alters generic chaining to bound all p-th moments of the supremum and uses Markov’s inequality to derive upper-tail bounds.
Results
The resulting deviation parameters are sharp up to numerical constants, with applications to unbounded or dependent empirical processes, chaos processes, and subsampled Fourier restricted-isometry proofs.
Takeaways & Limitations
The procedure can replace a separate expected-value estimate and concentration step, including in the restricted-isometry argument.
Takeaways & Limitations
The method does not yield optimal numerical constants because losses occur when converting between moment and tail bounds.
Abstract
from arXiv · showhide
We modify Talagrand's generic chaining method to obtain upper bounds for all p-th moments of the supremum of a stochastic process. These bounds lead to an estimate for the upper tail of the supremum with optimal deviation parameters. We apply our procedure to improve and extend some known deviation inequalities for suprema of unbounded empirical processes and chaos processes. As an application we give a significantly simplified proof of the restricted isometry property of the subsampled discrete Fourier transform.
1. Introduction
The paper modifies generic chaining to bound all p-th moments of a process supremum, yielding sharp upper-tail deviation parameters. It applies this approach to empirical and chaos processes and simplifies a restricted-isometry proof.
- Core contribution: Generic chaining is extended from estimating expected suprema to bounding all p-th moments of stochastic-process suprema.The resulting moment bounds are converted into upper-tail bounds through Markov’s inequality.
- Core contribution: The resulting upper-tail bound has deviation parameters sharp up to numerical constants and matches the Gaussian benchmark up to a possibly worse constant D.The comparison uses the optimal generic-chaining estimate for the expected supremum together with sharp Gaussian concentration.
- Gaussian case: For Gaussian processes under the canonical metric, the method produces sharp Lp-bounds up to universal constants.This follows from Talagrand’s majorizing measures theorem.
- Advantages: The method obtains upper-tail bounds essentially for free after estimating the expected supremum and requires only individual increment tail behavior.This permits processes with dependent increments and unbounded or dependent empirical-process summands.
- Applications: The paper establishes bounds for exponentially decaying increments, mixed subgaussian-subexponential tails, empirical-process suprema, and more involved chaos-type chaining arguments.The mixed-tail result positively answers an open question raised in Talagrand’s book.
- Applications: The approach simplifies the proof of the restricted isometry property for subsampled discrete Fourier transforms and extends to matrices sampled from bounded orthonormal systems.A related application sharpens the Johnson-Lindenstrauss embedding, discussed separately.
2. Preliminaries
The preliminaries establish probability, norm, tail, metric, admissibility, and covering-number notation used to formulate generic-chaining bounds. They also state finite-index assumptions and the process increment condition.
- Notation: The paper fixes a probability-space notation and uses E for expectation when describing random variables and process suprema.It also introduces notation for tail-behavior functions parameterized by α.
- Tail classes: ψα-random variables have finite ψα norm; ψ2 and ψ1 cases are called subgaussian and subexponential, respectively.For α ≥ 1, the associated space is an Orlicz space, while 0 < α < 1 yields a quasi-Banach space.
- Tail classes: Products of ψ2-random variables are ψ1, with a Hölder-type inequality derived from Young’s inequality.This relation supports handling products arising in later process bounds.
- Process framework: The analysis assumes finite index sets to avoid measurability complications for stochastic-process suprema.Infinite-index extensions are interpreted through lattice suprema in a later remark.
- Process framework: A process is ψα with respect to a semimetric when each increment’s tail is controlled at scale d(s,t) by 2 exp(−u^α).This increment condition supplies the metric-tail structure required by generic chaining.
- Generic-chaining notation: An admissible sequence starts with one point and has cardinality at most 2^2n at level n, while γα measures metric complexity through such sequences.Covering numbers separately record the smallest number of radius-u balls needed to cover the index set.
3. Suprema of ψα and mixed tail processes
The paper develops tail bounds for suprema of ψα and mixed-tail processes by combining truncated generic-chaining functionals with moment estimates and Markov optimization. The results include dependent-increment martingale bounds and improvements for mixed-tail processes, with applications to empirical-process suprema.
- ψα processes: Theorem 3.2 gives Lp-bounds and upper-tail bounds for ψα processes using truncated γ-functionals, with constants depending only on α.The construction uses l = ⌊log2(p)⌋ and generic-chaining decompositions to control the moments before deriving tails.
- ψα processes: For Gaussian processes with the canonical metric, Theorem 3.2 yields a sharp Lp-bound up to universal constants.This follows from comparison with Talagrand’s majorizing measures theorem.
- Scope and constants: The exposition does not optimize numerical constants, and the method incurs losses when converting between moment and tail bounds.The constants can be traded against one another and are not claimed to be optimal numerically.
- ψα processes: Theorem 3.2 requires no independence assumptions on increments, yielding a uniform Azuma-Hoeffding bound for families of martingales.The martingales are indexed by t and adapted to a common filtration.
- Mixed-tail processes: Theorem 3.5 treats mixed subgaussian-subexponential increments and improves a prior result while answering an open question in Talagrand’s book.Its proof combines two admissible partition sequences, reflecting the two tail metrics.
- Mixed-tail processes: The mixed-tail theorem is used to derive tail bounds for suprema of empirical processes.The paper identifies this application in Section 5.
4. Restricted isometry constants of subsampled unitary matrices
This section applies the generic-chaining method to restricted isometry constants for subsampled unitary matrices, simplifying the proof and extending it to bounded orthonormal systems.
- Setup: The s-th restricted isometry constant δs is defined as the smallest δ ensuring the relevant norm-preservation inequality for all s-sparse vectors.The section introduces δs for an m × N matrix and later characterizes sparsity through ∥x∥0.
- Setup: The random matrix is formed by independently selecting rows through Bernoulli selectors, restricting to selected indices, and rescaling the resulting unitary matrix.The expected number of selected rows is m, and the subsampled discrete Fourier transform is a special case.
- Proof strategy: The proof merges estimation of Eδs with deviation control, avoiding a separate concentration inequality while still using a chaining argument.This directly shortens the earlier two-part proof strategy.
- Results: The argument proves high-probability control of δs for subsampled discrete Fourier and, more generally, bounded orthonormal-system matrices.The generalization is stated as a consequence of a small modification of the proof.
- Results: P(δs(A) ≥ δ) ≤ η holds under the stated sampling condition, with universal constants d1 and d2.The supplied theorem passages state the probability guarantee and refer to the condition as equation (18), whose full expression is not reproduced here.
5. Supremum of an empirical process
This section derives tail bounds for suprema of empirical processes with subexponential or mixed-tail structure, then develops a sharper metric-based result for averages of squares.
- Empirical-process setup: Bernstein’s inequality supplies the mixed-tail control needed to apply the paper’s generic-chaining results to empirical processes.The process is modeled using independent subexponential variables and metrics reflecting its tail behavior.
- Averages of squares: Theorem 5.5 studies averages of squares of subgaussian variables using the metric dψ2(s,t) = max_i ∥Xsi − Xti∥ψ2.It seeks a natural bound in terms of the original variables rather than their squares.
- Proof strategy: The proof modifies generic chaining by splitting scales and controlling subgaussian and subexponential contributions separately.The construction uses an optimal admissible sequence, telescoping sums, Bernstein-type estimates, and quadratic inequalities.
- Averages of squares: Theorem 5.5 improves earlier work by requiring only independence, dropping the L2-sphere assumption, and providing a better deviation inequality.The comparison is made against Theorem 5.6 of Mendelson, Pajor, and Tomczak-Jaegermann.
6. Supremum of a second order chaos process
This section applies moment and tail bounds from generic chaining to suprema of second-order chaos processes, simplifying earlier arguments and improving the resulting metric dependence.
- Setup: A second-order chaos is defined from a random vector ξ by evaluating quadratic forms associated with matrices B.The section uses Schatten norms and matrix metrics to control collections of such forms.
- Existing bounds: Hanson–Wright gives mixed-tail behavior for individual quadratic forms, with metrics d∞ and d2 governing the process.Applying Theorem 3.5 yields a deviation bound involving both γ1 and γ2 functionals.
- Motivation: The appearance of γ1 can be suboptimal, motivating a bound for a special chaos-process form involving only γ2-functionals.This limitation is identified before introducing the improved result.
- Proof strategy: The proof avoids the majorizing-measures theorem while following the general structure of the earlier chaos-process argument.The paper presents this as a simplification of the proof of the prior result.
- Main result: Theorem 6.5 establishes Lp bounds and corresponding upper-tail bounds for suprema over matrix collections with independent mean-zero subgaussian coordinates.The result is built using decoupling, symmetrization, contraction, and generic chaining.
Appendix A.
The appendix collects elementary lemmas that convert moments to tails and relate exponential-moment, tail, and Orlicz-norm estimates used throughout the chaining arguments.
- Moment-to-tail conversion: Markov’s inequality provides the basic passage from moment bounds to tail bounds.The appendix states this as the role of its first observation.
- Norm and tail relations: Lemmas A.1 and A.2 relate probabilistic tail conditions to Orlicz-type norm bounds and include a converse observation.These equivalences are used repeatedly to translate increment assumptions into chaining estimates.
- Auxiliary lemmas: The appendix uses integration by parts, changes of variables, the gamma function, and Stirling’s formula to derive explicit moment estimates.These calculations complete the elementary auxiliary estimates used in the main proofs.
- Auxiliary lemmas: Lemma A.3 controls a finite collection of complex-valued random variables when the collection size is bounded relative to the moment parameter.Its hypothesis includes |T| ≤ 2^2l with l = ⌊log2(p)⌋.
- Auxiliary lemmas: Lemmas A.4 and A.5 provide tail and moment estimates for variables with exponential-type decay, supporting the scale-by-scale chaining analysis.Lemma A.5 applies to positive random variables and is used to control integrated tail behavior.