Source-linked AI summary
A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Norm
Chi Jin, Praneeth Netrapalli, Rong Ge, Sham M. Kakade, Michael I. Jordan
TL;DR
The note addresses loose concentration bounds when random vectors have a large ordinary subGaussian parameter despite favorable norm concentration. It introduces norm-subGaussian vectors, derives concentration inequalities under a martingale condition, and reports logarithmic rather than linear dependence on dimension, while leaving tightness of that dependence open.
Problem
Ordinary subGaussian concentration bounds can be loose for vectors with favorable concentration properties but a large subGaussian parameter.
Method
The note defines norm-subGaussian vectors, develops equivalent characterizations, and proves concentration results for vector martingales under conditional norm-subGaussian assumptions.
Results
The resulting bounds have only logarithmic dependence on dimension, compared with at least linear dependence from applying subGaussian bounds.
Takeaways & Limitations
Norm-subGaussian vectors provide a framework covering subGaussian and bounded random vectors while yielding the note's sharper dimension dependence.
Takeaways & Limitations
The note does not establish whether the logarithmic dimension dependence is tight and identifies eliminating it as an open problem.
Abstract
from arXiv · showhide
In this note, we derive concentration inequalities for random vectors with subGaussian norm (a generalization of both subGaussian random vectors and norm bounded random vectors), which are tight up to logarithmic factors.
1 Introduction
The note motivates norm-subGaussian random vectors as a class with tighter concentration bounds when the usual subGaussian parameter is large. It generalizes subGaussian random vectors and norm-bounded vectors while targeting improved dimension dependence.
- Concentration inequalities are a central subject in probability theory, with sharp bounds developed for subGaussian distributions.
- Smaller subGaussian parameter σ yields better concentration bounds.
- When vectors have good concentration properties but a large σ, general subGaussian bounds can be loose.
- The note introduces norm-subGaussian random vectors and establishes tighter concentration bounds for them.
2 Norm SubGaussian Random Vector
Norm-subGaussian vectors are defined through norm concentration and include ordinary subGaussian and bounded-norm vectors as special cases. The note develops equivalent characterizations and relates vector norms, projections, and matrix moment-generating functions.
- Norm-subGaussian random vectors are introduced as a distribution class defined through concentration of the vector norm.
- SubGaussian random vectors and bounded-norm random vectors are special cases of norm-subGaussian vectors.
- Equivalent norm-subGaussian characterizations use moments and moment-generating functions, up to absolute-constant changes in σ.
- For zero-mean nSG(σ) vectors, ∥X∥^2 is c·σ^2-subExponential and every fixed unit-direction projection is c·σ-subGaussian.
- Because ∥X∥ is not zero mean, the analysis converts X into a matrix Y and characterizes Y's moment-generating function.
3 Vector Martingales with SubGaussian Norm
The section develops concentration bounds for vector martingales whose conditional increments are zero-mean norm-subGaussian with possibly random, history-dependent parameters. Using matrix moment-generating-function arguments and Lieb’s concavity theorem, it derives a general result and Hoeffding-type corollaries.
- Proof strategy: Lieb’s concavity theorem is the principal tool for proving the concentration result in the general martingale setting.The proof combines conditional matrix MGF bounds with matrix-ordering arguments.
- Setup: The main framework allows each conditional increment X_i to be zero-mean norm-subGaussian with parameter σ_i measurable from the preceding filtration.The parameters σ_i may themselves be random variables determined by the observed history.
- Main result: Lemma 6 gives a high-probability concentration bound for increments satisfying Condition 4, for fixed δ > 0 and θ > 0.The result is stated with probability at least 1 − δ.
- Corollaries: Corollary 7 specializes the general result to fixed parameters and provides a Hoeffding-type inequality for norm-subGaussian vectors.Because the σ_i are fixed, the proof can choose θ as a function of them.
- Corollaries: Corollary 8 extends the bounds to a range B > b > 0 by discretizing parameter scales and applying a union bound.The construction uses geometrically spaced scales and incurs a logarithmic number of scale levels.
4 Conclusion
The conclusion introduces norm-subGaussian random vectors as a class containing subGaussian and bounded random vectors. The resulting concentration bounds improve the dimension dependence from at least linear to logarithmic, although tightness of the logarithmic dependence remains open.
- Contribution: Norm-subGaussian random vectors include subGaussian random vectors and bounded random vectors as special cases.The class is presented as a unifying generalization of both settings.
- Conclusion: The developed bounds have logarithmic dependence on dimension, whereas applying subGaussian bounds would yield at least linear dependence on dimension.The comparison is stated for the bounds developed in Lemma 6 and Corollaries 7 and 8.
- Open question: It remains unclear whether the logarithmic dependence on dimension is tight, leaving complete elimination of that dependence as an open problem.The conclusion explicitly identifies this as an interesting open problem.