Operations with concentration inequalities

We denote $\mathbb{R}_{+}$ (resp. $\mathbb{R}_{-}$) the set of positive (resp. negative) or null real numbers, $\mathbb{R}^{*}\equiv\mathbb{R}\setminus\{0\}$ and $\mathbb{R}_{+}^{*}=\mathbb{R}_{+}\setminus\{0\}$. Given $A\subset\mathbb{R}$, we note $\bar{A}$, the closure of $A$, $\mathring{A}$, the interior of $A$ and $\partial A$, the boundary of $A$ ($\partial A\equiv\bar{A}\setminus\mathring{A}$).

We extend the relation “$\leq$” to a relation between sets and introduce a new order “$\preceq$” defined followingly for any sets $A,B\subset\mathbb{R}$:

and we denote $A\geq B$ (resp. $A\succeq B$) when $-A\leq-B$ (resp. $-A\preceq-B$). The above definitions can easily extend to cases were $A$ or $B$ are scalars $a,b\in\mathbb{R}$ that are then identified with the singletons $\{a\}$ or $\{b\}$.

We consider below a set-valued mapping (also called “operator”) $f:\mathbb{R}\to 2^{\mathbb{R}}$. The graph of $f$ is the set $\operatorname{Gra}(f)=\{(x,y)\in\mathbb{R}^{2},y\in f(x)\}$. The inverse of $f$ is the set-valued mapping $f^{-1}$ satisfying:

Placing ourselves in the framework of monotone operator, we will say that $f$ is increasing if:

and $f$ is said to be a decreasing operator if $-f$ is increasing. Increasing and decreasing operators are both called monotone operators. The domain of $f$ is denoted $\operatorname{Dom}(f)=\{x\in\mathbb{R},f(x)\neq\emptyset\}$ and the range $\operatorname{Ran}(f)=\{y\in\mathbb{R},\exists x\in\mathbb{R}:y\in f(x)\}$. (Scalar-valued) functions are identified with operators whose image are all singletons. Given a set $A\subset\mathbb{R}$, we naturally define:

Then, given two operators $f,g$, the composition of $f$ and $g$ is the operator defined for any $x\in\mathbb{R}$ as $f\circ g(x)=f(g(x))$. The sum (resp. the product) between two operators $f,g:\mathbb{R}\to 2^{\mathbb{R}}$ is simply noted $f+g:x\mapsto f(x)+g(x)$ (resp. $f\cdot g:x\mapsto f(x)\cdot g(x)$) their domain is exactly $\operatorname{Dom}(f)\cap\operatorname{Dom}(g)$.

We denote $\operatorname{Id}:\mathbb{R}\to\mathbb{R}$ the function defined for all $x\in\mathbb{R}$ as $\operatorname{Id}(x)=x$. Given $u\in\mathbb{R}$, we denote the increment operator $\operatorname{inc}_{u}$ whose domain is $\operatorname{Dom}(\operatorname{inc}_{u})=(-\infty,u]$ and defined as:

Given two euclidean vector spaces $E$ and $F$ and an integer $d\in\mathbb{N}$, we denote $\mathcal{D}^{d}(E,F)$, the set of $d$ times differentiable mappings from $E$ to $F$ and $\mathcal{L}^{d}(E,F)$, the set of $d$-linear mappings from $E^{d}$ to $F$. Given a $d$ linear mapping $h\in\mathcal{L}^{d}(E,F)$, we further denote $\|h\|$ the operator norm of $h$ defined as:

Given $k\in[d]$, $f\in\mathcal{D}^{d}(E,F)$, and $x\in E$, we denote ${d^{k}f}\raisebox{-2.15277pt}{$|$}_{x}\in\mathcal{L}^{k}(E,F)$, the $k^{\text{th}}$ differential of $f$ at point $x$.

A fundamental result of the concentration of measure theory sets that for any Gaussian random vector $Z\sim\mathcal{N}(0,I_{n})$, for any $1$-Lipschitz for the euclidean norm on $\mathbb{R}^{n}$ mapping $f:\mathbb{R}^{n}\to\mathbb{R}$:

the mapping $\alpha:t\mapsto 2e^{-t^{2}/2}$ is here called a concentration function of $Z$. Given a transformation $F:\mathbb{R}^{n}\to\mathbb{R}^{q}$, $\lambda$-Lipschitz for the euclidean norm on $\mathbb{R}^{n}$ and $\mathbb{R}^{q}$ we have for any $Z^{\prime}\in\mathbb{R}^{n}$, an independent copy of $Z$:

and it is easy to deduce, with a slight modification of $t$, that the concentration function of the random vector $F(Z)\in\mathbb{R}^{q}$ is $\alpha(\cdot/\lambda)$. The aim of our paper is to express the concentration of $F(Z)$ when $\lambda$ is not constant but a certain random variable $\Lambda(Z)$ for $\Lambda:\mathbb{R}^{n}\to\mathbb{R}$, measurable. The following result is given for the general concentration function of $Z$ and $\lambda$.

This theorem allows some extension of the famous Hanson-Wright concentration inequality to a wider range of concentration functions (Theorems 6.1 and 6.7).

A more general version of this theorem is given in Theorem 3.5 for $\alpha,\beta$ which are possibly constant in some parts of their domain, and for a random variable $\Lambda(Z)$ which writes like a product of $n$ random variables, each of which has its own concentration function. Theorem 3.10 gives a similar result for the random variable $Z$ that satisfies weaker so-called “convex concentration” hypotheses and $\Phi$ takes value in $\mathbb{R}$.

The mapping $(\alpha^{-1}\cdot\beta^{-1})^{-1}:\mathbb{R}^{+}\to\mathbb{R}^{+}$ rewrites $(\tilde{\alpha}^{-1}+\tilde{\beta}^{-1})^{-1}\circ\log$ with the introduction of $\tilde{\alpha}\equiv\alpha\circ\exp$ and $\tilde{\beta}\equiv\beta\circ\exp$. The expression $(\tilde{\alpha}^{-1}+\tilde{\beta}^{-1})^{-1}$ can be recognized as the so-called parallel sum, originally introduced in electrical engineering to model parallel resistor networks, which was then generalized to matrices in [5] and to nonlinear operators in convex analysis in [4] (see [7, Chapter 24] for a presentation in the context of set-valued functions). The parallel sum is traditionally denoted $\square$, but since we will also be presenting a parallel product, we found it more convenient to denote it as $\boxplus$ (and the parallel product as $\boxtimes$). The operation on graphs can easily be represented as shown in Figure 1.

The control of non Lipschitz functionals has been studied by different authors. To be brief, one can mention the famous works of Vu in [25] on binary variables, then the introduction of specific operator norms on tensors to get concentration of polynomial of Gaussian variables by Latała in [16] and later generalized for more general variables and functionals in [3], [11] and [12]. Their studies let appear the notion of “multilevel concentration inequalities” where the concentration rate usually takes the form:

for a finite set $A\subset\mathbb{R}_{+}$ and $(\sigma_{a})_{a\in A}\in\mathbb{R}_{+}^{A}$. This multi-level scheme appears naturally when one computes the parallel product of $k$ decreasing mappings

for a decreasing function (possibly heavy-tailed) $\alpha$ replacing $t\mapsto e^{-t^{2}}$. We present in Theorem 5.5 a first setting where this multi-level concentration can appear.

However, a more natural setting allows us to continue the long-running study of the concentration of chaos and other functionals with bounded $k^{\text{th}}$-differential, $k\in\mathbb{N}$. Two approaches have been developed for these objects.

The older one is based on Hermite polynomials and was introduced by Christer Borell [9]. This work is not available online but was cited in [17] that studies chaos of maximal order $d$ of Gaussian variables. Then concentration inequalities closer to the one we will set are proved for Gaussian random variables in [6] and for random vectors with independent log-concave entries in [19], both with the appearance of quantiles instead of medians.

The more recent approach was initiated by Latała in [16] and relies on moment bounds to express a two-sided concentration inequality for Gaussian chaos. The tensor-product matrix norms involved in this type of concentration can be numerous, but the expectation is taken inside the norms, which could be a good improvement. This approach was followed in [3] for general functionals with bounded derivative of higher order and for random vectors satisfying log-Sobolev inequalities, then [12] extended the results to so-called “$\alpha$-sub exponential random variables”.

The two approaches are known to be “relatively equivalent” in the case of $d=2$ (see the discussion initiated at the end of Section 3 in [2]), the question remains open for larger orders. Our present work is in line with the first approach, and in this respect, our main contribution is to extend previous results to $(i)$ functionals with bounded $d^{\text{th}}$-derivative and $(ii)$ to any random vector $Z\in E$ of a metric space $(E,d)$ admitting a concentration function $\alpha:\mathbb{R}_{+}\to\mathbb{R}_{+}$ that could be defined as:

(following the idea of Ledoux presented at the beginning of his book [18]).

Finally, let us mention here that an elementary result (Lemma 2.5) provides a sufficient condition to replace medians or independent copies with expectations in concentration inequalities similar to (2) when $\alpha$ is integrable. In “natural settings”, it morally consists in assuming the integrability of $\alpha$. This Lemma allows to generalize the Hanson-wright inequality to random vectors having a concentration function $\alpha$ satisfying $\int_{\mathbb{R}_{+}}t\alpha(t)dt\leq\infty$ (second moment bounded), see Theorem 6.7.

In order to be able to treat rigorously the case of non-invertible mappings $\alpha$ and $\beta$, we decided to work with maximal operators of $\mathbb{R}$, i.e. set-valued mappings that always admit an inverse. To our knowledge, this connection between probabilities and set-valued mappings was only explored by Rockafellar (see for instance [22]) to study financial tools like superquantiles.

Section I provides basic tools for dealing with operators and the expression of the sum (resp. the product) of two concentration inequalities with the parallel sum (resp. with the parallel product). Further presentation of operators is provided in the appendix with the definition of the minimum of operators and the connection with the parallel sum to provide a more intuitive understanding of this operation. It is an easy exercise to check that these results on operators become trivial in the case of singleton-valued invertible mappings.

Section II briefly explains how to deal with different concentration pivots such as median, independent copies or expectation. Section III introduces important results of concentration in high dimension and expresses the concentration of a transformation with concentrated variations. In Section V we present a general example of heavy-tailed concentration in high dimension. In Section V we introduce relevant notations and parallel operation tools to justify the appearance of multilevel concentration, we further prove Theorem 0.2. Finally, in Section VI, we apply our results to obtain a heavy-tailed version of the Hanson-Wright theorem.

To set first elementary properties on parallel sum and product, let us provide without proof basic lemmas on the inverse f operators.

One can easily circumvise the domain and range of the parallel sum and parallel product from their definition.

To ensure the monotonicity of $f\boxtimes g$ one has to impose the ranges of $f,g$ to be subsets of $\mathbb{R}_{+}$ (or $\mathbb{R}_{-}$) as it will be done later.

As a simple consequence of Lemma 1.19, note that the parallel sum and product are both associative, commutative and the parallel product distributes on the parallel sum as classical sums and products of function would do.

Unlike the classical sum or product of functions, the composition distributes towards the sum $\ \boxplus$ and the product $\ \boxtimes$ on the left.

It is a simple inference of the following lemma.

Be careful, increasing operators (resp. decreasing operators) $f:\mathbb{R}\mapsto 2^{\mathbb{R}}$ satisfy $x<y\implies f(x)\leq f(y)$, but of course $f(x)\not\leq f(x)$. In particular, if $\operatorname{Gra}(f)=\{0\}\times\mathbb{R}_{+}\cup\mathbb{R}_{+}\times\{0\}$, note that $\operatorname{Gra}(f\circ f)=\mathbb{R}_{+}^{2}$, one sees that $f$ is decreasing but $f\circ f$ is not monotone. The composition with invertible functions though preserves monotonicity.

It will be more convenient below to work with so-called “maximally monotone operators” principally because of Proposition 1.10 and Theorems 1.18 and 1.12 given below. Although it is not completely trivial, maximality for operators on $\mathbb{R}$ is quite elementary, principally because the class of convex sets is equal to the class of connected sets (it is the class of intervals of $\mathbb{R}$).

The Minty Theorem provides straightforwardly simple examples of maximally monotone operators.

Since we are here working in $\mathbb{R}$, it is possible to improve the hypotheses sufficient for the sum (or parallel sum) of two operators to be maximally monotone that were given in Example 1.9, Item 5.

Note that the operator $f:\mathbb{R}\mapsto 2^{\mathbb{R}}$ such that $\operatorname{Dom}(f)=\emptyset$ is rigorously monotone but not maximally monotone (its graph is contained in the graph of any monotone operator).

One could be tempted to transfer the maximality of the parallel sum to the parallel product thanks to the following identity, true for any $f,g:\mathbb{R}\mapsto 2^{\mathbb{R}}$ such that²²2The identity $f=f\circ\exp\circ\log$ is only true for operators $f:\mathbb{R}\mapsto 2^{\mathbb{R}}$ such that $\operatorname{Dom}(f)\subset\mathbb{R}_{+}^{*}$ $\operatorname{Dom}(f),\operatorname{Dom}(g)\subset\mathbb{R}_{+}^{*}$:

However the maximality properties raise some difficulties because there are some examples where $f$ is maximally monotone but $f\circ\log$ is not (for instance for any $f\equiv\operatorname{inc}_{u}$ for $u>0$). Besides the condition $\operatorname{Dom}(f),\operatorname{Dom}(g)\subset\mathbb{R}_{+}^{*}$ is arguably too restrictive for our application where one would more naturally merely assume $\operatorname{Dom}(f),\operatorname{Dom}(g)\subset\mathbb{R}_{+}$.

Still it is possible to show the maximality of the product and the parallel product from scratch if one restricts the ranges to stay in $\mathbb{R}_{+}$, mainly to preserve monotonicity.

All those result on maximally monotone operators being set, we reached the central objective of this section: to relate the cumulative distribution function of the sum (resp. of the product) of random variables with the parallel sum (resp. the parallel product). Although rather trivial (at least when working with invertible functions and not operators), it is at the basis of the main theorems of next sections. Since we are trying to bound probabilities, we decide to slightly restrict the class of operator considered in this kind of results. That will simplify the settings and the proofs.

When $n=2$ and $\alpha=\beta$, note that $\alpha\boxplus\beta=\alpha(\frac{\cdot}{2})$. In particular, the example depicted on Figure 2 shows that the inequality $\mathbb{P}\left(X+Y>t\right)\leq 2\alpha(\frac{t}{2})$ can be reached for some random variables $X$ and $Y$ and some values of $t$.

The proof of this proposition requires two additional results that will mainly allow us to deal with the multiplicity of image of operators. Maximally monotone operators are actually almost always singleton value as seen in next theorem.

When $f(x)$ contains more than one element, it is still possible to deal with the fact that $f^{-1}\circ f\neq\operatorname{Id}$ thanks to the following elementary lemma.

In the setting of Proposition 1.17, note that if $\alpha_{1},\ldots,\alpha_{n}$ are all invertible mappings (singleton-valued operators) defined on $\mathbb{R}$, one can deduce that $\forall t\in\operatorname{Dom}(\alpha_{1}\boxplus\cdots\boxplus\alpha_{n})$:

This inference is fully justified for general operators in the appendix.

Proposition 1.17 could be called a “tail concentration result”, one might be more naturally interested in the concentration around a deterministic value as depicted in next results.