Tail bounds via generic chaining

Abstract

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.

Added detailed proof of Theorem 3.5; Application to dimensionality reduction expanded and moved to separate note arXiv:1402.3973

References in corpus (1)

• Dimensionality reduction with subgaussian matrices: a unified theory

Cited by in corpus (6)

• Dimensionality reduction with subgaussian matrices: a unified theory
• Structured signal recovery from non-linear and heavy-tailed measurements
• End-to-end Learning of a Convolutional Neural Network via Deep Tensor Decomposition
• Recipes for stable linear embeddings from Hilbert spaces to R^m
• Compressed Subspace Matching on the Continuum
• $L_1$-Penalization in Functional Linear Regression with Subgaussian Design