Concentration for multiplier empirical processes with dependent weights

1.   Introduction

Over the last two decades, modern data collection techniques have enabled scientists and engineers to access and load vast numbers of variables as random data in their experiments. Probability theory provides the mathematical foundations for statistics and data-driven problems have led to various new advances in statistical research, which in turn contributes new and challenging problems in probability for further study. For instance, the rapid development of high-dimensional statistics has spurred the growth of the probability theory and even pure mathematics, including concentration inequalities, random matrix theory, geometric functional analysis and more ^[2,16].

The emergence of high-throughput data has led to a surge in statistical research on complex data, particularly on high-dimensional data and statistical learning ^[14,20]. This trend has gained traction in various scientific fields despite the high cost of measurements. Data sets are typically small, with only tens or hundreds of observations, and limited computing power often restricts the size of suitable finite samples. As a result, modern statisticians and data scientists have shifted their focus from asymptotic to non-asymptotic analysis, as it can handle small sample sizes and large model dimensions. Concentration inequalities play a crucial role in high-dimensional statistical inference, as they can derive various explicit non-asymptotic error bounds as a function of the sample size, sparsity level and dimension. When analyzing the various error bounds of the regularized estimator, concentration inequalities are indispensable tools for analysis ^[3,20].

When the random variables are unbound, the classcial Hoeffding's inequality ^[8] falls to do a non-asymptotic analysis. We need the concept of sub-Gaussian random variables ^[9] to obtain tight Hoeffding-type concentration inequalities for the sum of independent random variables. A centered random variable (r.v.) $X$ is called sub-Gaussian ($X \sim \operatorname{subG}({\sigma^2})$) if ${\rm{E}}{e^{s X}} \le {e^{{s^2}{{\sigma}^2}/2}}$ for $\forall\; s \in \mathbb{R}$, where ${\sigma} > 0$ is the sub-Gaussian parameter. From Chernoff's inequality, the exponential decay of the sub-Gaussian tail is obtained by $P \left(X \ge t \right)\le {\inf }_{s > 0} \exp\{-s t\} \mathrm{E} \exp\{s X\} \le{\inf }_{s > 0} \exp({-s t + \frac{\sigma^2s^2}{2}}) = \exp({- \frac{t^2}{2 \sigma^2}})$, minimizing the upper bound by putting $s = {t}/{\sigma^2}$. Moreover, for independent $\{ {X_i}\} _{i = 1}^n$ with $X_{i} \sim \operatorname{subG}(\sigma_{i})$, we have sub-Gaussian concentration inequality

for any variance proxies $\{\sigma_i^2\}_{i = 1}^n$ of $\{ {X_i}\} _{i = 1}^n$ (see Theorem 1.5 in ^[1]). Define the $L_p$-norm of r.v. $X$ as ${\left\| X \right\|_p}: = {({\rm{E}}|X{|^p})^{1/p}}$. An alternative form of the sub-Gaussian parameter is defined by the sub-Gaussian norm $\|\cdot\|_{\theta_{2}}$ for zero-mean r.v. $X$ is defined as $\|X\|_{\theta_{2}}: = \sup _{p \geq 1} [\frac{{\rm{E}}X^{2p}}{(2p-1)!!}]^{1/{(2p)}}$ (see page 23 in ^[1]).

Corollary 1.7 in ^[15] extended the sub-Gaussian concentration inequality (1.1) to the weighted sum of independent sub-Gaussian random variables with fixed weights.

Lemma 1. [Concentration for weighted sub-Gaussian sum] Let $Y_{1}, \ldots, Y_{n}$ be $n$ independent r.v.s with $Y_i \sim \operatorname{subG}(\sigma_i^{2})$. Define ${\sigma ^2} = \mathop {\max }\limits_{1 \le i \le n} \sigma _i^2 < \infty$. For any ${\mathit{\boldsymbol{ w }}} : = ({w_1}, \cdots, {w_n})^\top,$ we have

However, if $w_{i}$'s are random in Lemma 1, the story is totally different. The goal of this paper is to obtain novel theoretical results on the concentration inequality for the sum of dependent variables with random weights, under high-dimensional data background. Our theory is motivated from the non-asymptotic oracle inequalities of the regularized estimator in high-dimensional negative binomial regressions ^[21], and the concentration of random Lipschitz coefficients associated with empirical loss functions ^[4]. Our setting is different from classical multiplier empirical processes serving the multiplier Bootstrap inference, where the multipliers are random variables independent of $\{Y_i\}_{i = 1}^{n}$ (see Chapter 2.9 of ^[17] and ^[6,7]). Mendelson ^[11] studied the concentration inequalities for the centered multiplier process indexed by a functional class, where the i.i.d. multipliers need not be independent of the original empirical processes. In the analyses of high-dimension continuous data regressions by empirical processes, researches often resort to concentration inequalities of the Lipschitz function of strongly log-concave distributions (see Theorems 2.26 and 3.16 in ^[18]). For high-dimension count data regressions, our section 3.3 discusses the discrete distributions with strongly log-concave structures, which it is considered hard to check the definition of discrete strongly log-concave distributions (see (3.12) below). However, this strong assumption is usually intractable and unverifiable from the data. The sub-Gaussian assumption for the i.i.d. data is testable (see ^[23]).

In section two, we present the main results of the theory and demonstrate their applications in a class of high-dimensional generalized linear models. Theoretical proofs of the main results and some lemmas and additional results are given in section three. Finally, the conclusions are presented in section four.

2.   Concentration for dependent summations

2.1.   Main results

When controlling the summation of a function of the random sample indexed by a common estimator $\hat{\theta}$, it is false to use any sort of classical law of large numbers and central limit theorems (or concentration inequality for independent summation).

Formally, let $X_{1}, \ldots, X_{n}$ be a random sample independently drawn from $P$ on a measurable space $(\mathcal{X}, \mathcal{A})$. Given an estimator $\hat{\theta},$ we want to study its asymptotic properties for summation of some function $f_{\hat{\theta}}(X_i)$,

A possible solution: Prove a uniform version (the suprema of empirical processes, see ^[17]) for all possible $\hat{\theta}$ on a set $K$, which is usually stronger than what is needed.

The summation in the $\rm{sup}$ enjoy independence.

In following theorem, we extend Lemma 1 with dependent and random weights.

Theorem 1. [Concentration for weighted dependent sum] Let $Y_{i}$'s be independent centered sub-Gaussian random variables with $\mathop {\max }\nolimits_{1 \le i \le n}{\|Y_k\|_{\theta _2}} < \infty$. Let $w_{i}(\hat{\theta})$'s be a series of bounded function of a bounded random variable $\hat{\theta}$ as the weights (can be dependent on all $Y_{i}$'s), where ${\| \hat{\theta}\|_1} \leq r < \infty$ and $\mathop {\max }\nolimits_{1 \le i \le n}w_{i}(\cdot) \le 1$. Then, with probability of at least $1-\delta$,

for all ${\| \hat{\theta}\|_1} < \infty$, where $Y_i^{\prime}$ is an independent copy of $Y_i$.

The first term in (2.1) is due to sub-Gaussian concentration, and the second term in (2.1) is from the upper bound of the expected version of the superma of empirical process $f({\mathit{\boldsymbol{ Y }}}): = \frac{1}{n} \sup \nolimits_{{{\left\| {\theta} \right\|}_1} \le r} | {\sum\nolimits_{i = 1}^n {w_{i}({\theta}) } {Y_i}} |$ (see the proof in section three).

2.2.   Applications: Local stochastic Lipschitz conditions in GLMs

The concentration of random Lipschitz coefficients associated with empirical loss functions is crucial for deriving error bounds of Lasso or Elastic-net penalized high-dimensional generalized linear models (GLMs) in high-dimensional regressions. For more information, please refer to ^[3,4,10].

Definition 1. [Elastic-net or Lasso penalized loss problems] Let $\{(Y_i, \mathit{\boldsymbol{X}}_i)\}_{i = 1}^{n}$ be independent identically random variables with values in $\mathbb{R}\times \mathbb{R}^p$, where $\{Y_i\}_{i = 1}^{n}\sim Y$ are response variables and $\{\mathit{\boldsymbol{X}}_i\}_{i = 1}^{n}\sim \mathit{\boldsymbol{X}}$ are covariates. Let $l(y, \mathit{\boldsymbol{x}}, \boldsymbol{\beta})$ be a loss function of parameter $\boldsymbol{\beta}$ and data $(y, \mathit{\boldsymbol{x}})$. The empirical loss function is defined as

Elastic-net (or Lasso) estimators are given by

where ${\lambda _1} > 0$ and ${\lambda _2}\ge 0$ are tuning parameters.

Define the minimizer

as the vector of true coefficients, where $l(Y, \mathit{\boldsymbol{X}}, \boldsymbol{\beta})$ is the loss function. The $\ell_1$ ball is denoted as ${{\cal S}_R}(\boldsymbol{\beta} ^*): = \left\{ { \boldsymbol{\beta} \in {\mathbb{R}^p}:{\|{ \boldsymbol{\beta} } - \boldsymbol{\beta} ^*\|_1} \le R} \right\}$. Theorem 1 can be used to establish exponential-type concentration inequalities for the local stochastic Lipschitz (LSL) constant:

When study error bounds ${\|{{\hat{ \boldsymbol{\beta}} }} - \boldsymbol{\beta} ^*\|_1}$ of Lasso or Elastic-net penalized high-dimensional GLMs, one must bound the dependent empirical processes $\frac{\left(\mathbb{P}_{n}-\mathbb{P}\right) [l(Y, \boldsymbol{X}, \boldsymbol{\hat \beta})-l(Y, \boldsymbol{X}, \boldsymbol{\beta}^{*})]}{\|\boldsymbol{\hat \beta} - \boldsymbol{\beta}^*\|_1}$ with the LSL constant as the upper bound.

Next, we provide an example of negative binomial loss in negative binomial regressions ^[21]. The negative binomial loss function is $l(y, \mathit{\boldsymbol{x}}, \boldsymbol{\beta}) = y\mathit{\boldsymbol{x}}^\top \boldsymbol{\beta} - (\theta + y)\log (\theta + {e^{\mathit{\boldsymbol{x}}^\top\boldsymbol{\beta} }})$, where $\theta$ is called the dispersion parameter. Denote the expected risk function as $\mathbb{P}l(Y, \boldsymbol{X}, \boldsymbol{\beta}) : = {\rm E}l(Y, \boldsymbol{X}, \boldsymbol{\beta})$. Let ${l_1}(y, \mathit{\boldsymbol{x}}, \boldsymbol{\beta}) : = - y[\mathit{\boldsymbol{x}}^\top \boldsymbol{\beta} - {\rm{log}}(\theta + {\rm{ exp}}\{ {\rm{ }}{\boldsymbol{x}^\top} \boldsymbol{\beta} \})]$, and ${l_2}(\mathit{\boldsymbol{x}}, \boldsymbol{\beta}) : = \theta {\rm{log}}(\theta {\rm{ + exp}}\{{\boldsymbol{x}^\top} \boldsymbol{\beta} \})$, then

The upper bounds for the first and second parts of the empirical process: $(\mathbb{P}_{n}-\mathbb{P})(l_{m}(\boldsymbol{\beta}^{*})-l_{m}(\hat{ \boldsymbol{\beta}}))$ for $m = 1, 2$ is paramount to study the error bound of ${\|{{\hat{ \boldsymbol{\beta}} }} - \boldsymbol{\beta} ^*\|_1}$.

Let $\lambda$ be a positive constant that needs to be determined. We have

Here, we assume that both $\boldsymbol{x}$ and $\boldsymbol{\beta}$ are bound, and $\theta$ is a known dispersion parameter. The high probability for the second term in (2.4) is easy to deal with if we apply McDiarmid's inequality (see Lemma 4 of ^[21]). However, the high probability for the first term in (2.4) is hard to control since it contains unbounded negative binomial variables $\{Y_i\}_{i = 1}^{n}$. Zhang and Jia ^[21] used the concentration inequality for strongly log-concave discrete distributions to solve this problem, but the strongly log-concave property is difficult to check for discrete distribution (see (H.4) in ^[21]). The sub-Gaussian distribution assumption is easy to verify for negative binomial variables, and this is from the fact that the negative binomial distribution belongs to the exponential family if the dispersion parameter is given. When $\Theta$ is compact in (2.7) below, Proposition 3.2 in ^[20] shows that $\{ {Y_i}\} _{i = 1}^n$ is sub-Gaussian.

From Taylor's expansion of continuous functions, one has $\log \left({\theta + {e^x}} \right) - \log \left({\theta + {e^a}} \right) = \frac{{{e^{\tilde a}}}}{{\theta + {e^{\tilde a}}}}(x - a)$, where ${\tilde a}$ is some real number between $a$ and $x$. Let $\boldsymbol{X}_i^\top\tilde {\boldsymbol{\beta}}$ be some point between $\boldsymbol{X}_i^\top\hat{ \boldsymbol{\beta}}$ and $\boldsymbol{X}_i^\top \boldsymbol{\beta} ^*$, i.e., $\tilde {\boldsymbol{\beta}} = \left({\begin{array}{*{20}{c}} {{t_1}{{\hat \beta }_1}}\\ \vdots \\ {{t_p}{{\hat \beta }_p}} \end{array}} \right) + \left({\begin{array}{*{20}{c}} {(1 - {t_1})\beta _1^*}\\ \vdots \\ {(1 - {t_p})\beta _p^*} \end{array}} \right)$ for $\{ {t_j}{\rm{\} }}_{j = 1}^p \subset [0, 1]$. Observe that

For a finite $M_0$, if we have $\hat{ \boldsymbol{\beta}} \in {{\cal S}_{M_0}}(\boldsymbol{\beta} ^*)$, then $\tilde {\boldsymbol{\beta}} \in {{\cal S}_{M_0}}(\boldsymbol{\beta} ^*)$. This is from the fact $\| {\tilde {\boldsymbol{\beta}} - { \boldsymbol{\beta} ^*}} \| \le \sum\nolimits_{j = 1}^p {{t_j}|{{\hat \beta }_j} - \beta _1^*|} \le \| {{{\hat{ \boldsymbol{\beta}} }} - {\boldsymbol{\beta}^*}} \| \le {M_0}.$ Suppose $|\boldsymbol{X}_i|_{\infty}$ is uniformly bounded by $1/M_0$. We have $|(2.5)|: = \frac{1}{n}{\sum\limits_{i = 1}^n {w_{i}({\hat{ \boldsymbol{\beta}} })} {({Y_i}} - {\rm{E}}{Y_i})}$ with dependent weights

Thus, the high probability upper bound in Theorem 1 is applicable to determine $\frac{\lambda}{2}$, i.e.,

2.3.   Berstein-type concentration inequalities

In this section, let $\{ {Y_i}\} _{i = 1}^n$ be exponential family random variables with density

Here, ${\rm{E}}(Y_i) = \dot{b}(\eta_i)$ and ${\rm{Var}}(Y_i) = \ddot{b}(\eta_i)$. It should be noted that Proposition 3.2 in ^[20] shows that $\{ {Y_i}\} _{i = 1}^n$ is sub-Gaussian if $\Theta$ is compact.

Under distributional assumption (2.7), we will study the Berstein-type concentration inequalities for the randomly weighted sum of centered exponential family random variables (with different parameters $\theta_i$'s):

where the $\{w_{i}(\hat{\theta})\}_{i = 1}^n$ are called the multipliers (or random weights), and $\hat{\theta}$ is independent of $\{ {Y_i}\}_{i = 1}^n$.

Theorem 2. [Concentration inequalities for randomly weighted sum of exponential family r.v.s] If $\{ {Y_i}\} _{i = 1}^n$ has density (2.7) with moment conditions: ${\rm{E}}|Y_i|^k \le k!C_Y^k$, where $C_Y > 0$ is a constant. We assume that

(i) Bounded weights: ${\mathit{\boldsymbol{ W }}}_{\hat\theta} : = ({w_{1}}({\hat\theta}), \cdots, {w_{n}}({\hat\theta}))^\top$ is a random vector s.t. $\mathop {\max }\nolimits_{1 \le i \le n} |{w_{i}}({\hat\theta})| \le {w} < \infty$;

(ii) Let ${\rm{E}}[|{Y_i}{|^k}|{\mathit{\boldsymbol{ W }}}_{\hat\theta}] = {\rho _{i, k}}{\rm{E}}[|{Y_i}{|^k}]$ with ${\rm{E}}{\rho _{i, k}} = 1$;

(iii) There exists a non-decreasing sequence ${\{ {u_n}\} }$ and constant ${C_\rho}$ s.t. $P(\mathop {\max}\limits_{k\ge 1, 1 \le i \le n} {\rho _{i, k}} > {u_n}) \le {C_\rho}/{{{u_n}}}.$ Then,

where $\{{w_{i}}({\hat\theta}){Y_i}\}$ is dependent since each ${w_{i}}({\hat\theta}){Y_i}$ depends on a common estimator ${\hat\theta}$ from the data $\{ {Y_i}\} _{i = 1}^n$.

It should be noted that our work here is related to Proposition 3.2 in ^[20] and it is about the concentration inequalities for the non-random weighted sum of exponential family random variables. For condition (ii), suppose that the estimator ${\hat\theta}$ converges to a true parameter $\theta^*$ almost surely, and one has ${\rm{E}}[|{Y_i}{|^k}|{\mathit{\boldsymbol{ W }}}_{\theta^*}] = {\rm{E}}[|{Y_i}{|^k}]$ since $W_{\theta^*}$ is non-random. The difference between conditional expectation and unconditional expectation is:

if $|{\rm{E}}[|{Y_i}{|^k}|{\mathit{\boldsymbol{ W }}}_{{\boldsymbol{\beta}}}]$ is a $\ell_1$-Lipschitz function of ${ \boldsymbol{\beta}}$. We call $P(\mathop {\max}\limits_{k\ge 1, 1 \le i \le n} {\rho _{i, k}} \ge {u_n}) \le {C_\rho}/{{{u_n}}}$ in assumption (iii) a high level condition. Intuitionally, due to the dependence summation, the random weighted summation will lose the rate of convergence in the exponential inequalities (addition term $4w{C_T}t$ is added), compared to the case of non-random weighted summation. The assumption of compact parameter space for the exponential family is key to obtaining the sub-Gaussian type concentration inequalities.

Our multiplier concentration inequality here is different from ^[11], which studies the concentration upper bounds for centered multiplier empirical processes $\frac{1}{{\sqrt n }}\sum\limits_{i = 1}^n {[{W_i}{Y_i}}- {\rm{E}}({W_i}{Y_i})]$ (the random weights $\{W_i\}$ and random variables $\{Y_i\}$ need not be independent); however, they assume that $\{W_i\}$ is i.i.d. To the best of our knowledge, Theorem 2 is a new concentration inequality that is suitable for the weighted sum of dependent random variables.

3.   Theoretical proofs

3.1.   Proofs of main results

Proof of Theorem 1: Let ${\mathit{\boldsymbol{ Y }}} = (Y_1, \cdots, Y_n)^\top$ be a vector of independent r.v.s in a space $\mathcal{Y},$ and define $(Y_1^{\prime}, \cdots, Y_n^{\prime})^\top$ as an independent copy of $(Y_1, \cdots, Y_n)^\top$. For any function $f: \mathcal{Y}^{n} \rightarrow \mathbb{R}$, it is of interest to study the concentration for $f({\mathit{\boldsymbol{ Y }}})$ about its expectation. In case of Theorem 1,

For $z \in \mathcal{Y}$ and $k \in\{1, \ldots, n\}$, define the substitution operator

and the centered conditional version of $f$

Next, we use a constant-sharper sub-Gaussian concentration for $f(Z)$ in Corollary 4 in ^[22], which requires the $\| \cdot \|_{{\theta_2}}$-norm condition of r.v. $\{D_{f, Z_i}(z)\}_{i = 1}^n$.

Lemma 2. If $\{D_{f, Z_i}(z)\}_{i = 1}^n$ has finite $\| \cdot \|_{{\theta_2}}$-norm for ${z \in \mathcal{Z}}$, then $f(Z)- {\rm{E}}f(Z) \sim \operatorname{subG}({\rm{8}}\sup_{z \in \mathcal{Z}} \sum_{i = 1}^n {\left\| {{D_{ f, {Z_i}}}(z)} \right\|_{{\theta _2}}^2})$ and

From the identity in (3.1), we have

The conditional Jensen's inequality gives

The definition ${\left\| X \right\|_{\theta_{2}}} = \sup\nolimits_{k \ge 1} {[{\frac{{{2^k}k!}}{{(2k)!}}{\rm{E}}{X^{2k}}}]^{1/(2k)}}$ shows $\| D_{f, Y_k}(y) \|_{\theta _2} \le \frac{1}{n} \||Y_k- Y_k^{\prime}|\|_{\theta _2}$ by (3.2) and (3.3). Hence, we have $\sup_{z \in \mathcal{Z}} \sum_{i = 1}^n {\| {{D_{f, {Z_i}}}(z)} \|_{{\theta _2}}^2} = \frac{1}{n^2}\sum_{k = 1}^n\||Y_k- Y_k^{\prime}|\|_{\theta _2}^2$ in Lemma 2, which leads to

Let $\delta = e^{{{{ - {(nt)^2}}}/16\sum_{k = 1}^n\||Y_k- Y_k^{\prime}|\|_{\theta _2}^2}}$, and $t = 4\sqrt{\frac{1}{n}\sum_{k = 1}^n\||Y_k- Y_k^{\prime}|\|_{\theta _2}^2}\sqrt {\frac{{\log \delta^{-1}}}{n}}$. We have

with probability at least $1-\delta$.

It remains to obtain a bounds on ${\rm{E}}f({\mathit{\boldsymbol{ Y }}})$, which is upper bounded by the symmetrization theorem from Lemma 3 with different functions. To see this, let $X_i = Y_i$ in Lemma 3 and $g_i(Y_i) = w_{i}({\theta}) Y_i$ for $i = 1, \cdots, n$.

Since $w_{i}({\theta})$'s are series of bounded functions of a common bounded variable ${\theta}$ where ${\| {\theta}\|_1} \leq r$ and $\mathop {\max }\nolimits_{1 \le i \le n}w_{i}(\cdot) \le 1$, for any vector ${\theta}$ with ${{\left\| {\theta} \right\|}_1} \le r$, there exists a sequence of vectors $\{a_{w_{i}}\}_{i = 1}^{n}\in \mathbb{R}^p$ with ${\left\| a_{w_{i}} \right\|_{\infty}}\le1/r$ such that

Equation (3.5) and Lemma 3 imply

Next, we apply the maximal inequality. By Corollary 7.5 in ^[20], with ${\rm{E}}[{{\epsilon_i}}{Y_i}{{a_{{w_{i}}j}}}|{\mathit{\boldsymbol{ Y }}}] = 0$ and ${{\epsilon_i}}{Y_i}{{a_{{w_{i}}j}}} \le \mathop {\max }\nolimits_{1 \le i \le n}{\left\| a_{w_{i}} \right\|_{\infty}}{Y_i} = r^{-1}{Y_i}$, one has

Thus, ${\rm{E}}f({\mathit{\boldsymbol{ Y }}})\le 2\sqrt {\frac{1}{{n}}\sum_{i = 1}^{n} {\rm{E}}Y_i^2}\sqrt {\frac{{2\log (2p)}}{n}}$. Using (3.4),

with the probability of at least $1-\delta$.

Proof of Theorem 2: We will adopt the following result, which gives the moments inequality for the exponential family. It is deduced by the analytic properties of the absolute moments of exponential family random variables:

see Proposition 5.2 in ^[20]. For notation simplicity, let ${{\mathit{\boldsymbol{ W }}}}: = {\mathit{\boldsymbol{ W }}}_{\hat\theta}$ and $W_{i} = {w_{i}}({\hat\theta})$. By using Taylor's expansion and the binomial coefficient formula, we have the following upper bound for the conditional moment generating function of ${W_i}{Y_i} - {\rm{E}}({W_i}{Y_i})$, conditioning on the event $\{ \mathop {\max }\nolimits_{k \ge 1, 1 \le i \le n} {\rho _{i, k}} \le {u_n}\}$:

for $s \in (0, \delta)$ with some $\delta > 0$.

Therefore, we can assume that $\left| {2sw{C_T}} \right| < 1$, so

Define the randomly weighted sum $S_n^{W } = :\sum\nolimits_{i = 1}^n {{W_i}{Y_i}}$. By the conditional independence of $\{{W_i}{Y_i}|{\mathit{\boldsymbol{ W }}}\}_{i = 1}^n$, it follows that by (3.8),

By conditional Markov's inequality and on $\{ \mathop {\max }\nolimits_{k \ge 1, 1 \le i \le n} {\rho _{i, k}} < {u_n}\}$, we have for $a > 0$

where the last equality is obtained by setting $a = \frac{t}{{8nu_n{{(w{C_T})}^2} + 2w{C_T}t}}$.

Taking expectation w.r.t. ${\mathit{\boldsymbol{ W }}}$ on (3.10), it implies

3.2.   Some lemmas

Lemma 3. [Symmetrization theorem with different functions] Let $\varepsilon_{1}, ..., \varepsilon_{n}$ be a Rademacher sequence with uniform distribution on $\{ - 1, 1\}$, independent of $X_{1}, ..., X_{n}$ and $g_i\in \mathcal{G}_i$. Then,

where ${\rm{E}}_{\epsilon}\left\{\cdot\right\}$ refers to the expectation w.r.t. $\epsilon_{1}, ..., \epsilon_{n}$.

Proof: Let $\{X_{i}^{\prime}\}_{i = 1}^{n}$ be an independent copy of $\{X_{i}\}_{i = 1}^{n}$. The ${\rm{E}}^{\prime}$ denotes the expectation w.r.t. $\{X_{i}^{\prime}\}_{i = 1}^{n}$, and let ${\cal F}_{n}^{\prime} = \sigma\left(X^{\prime}_{1}, \cdots, X^{\prime}_{n}\right)$. So,

where we use the conditional expectation version of Jensen's inequalities.

Since $\varepsilon_{i} [g_{i}\left(X_{i}\right)-g_{i}(X_{i}^{\prime})]$ and $g_{i}\left(X_{i}\right)-g_{i}(X_{i}^{\prime})$ have the same distribution, then,

If $g_i = f, \; \mathcal{G}_i = \mathcal{F}$ for $i = 1, 2, \cdots, n$, then we have the classical symmetrization theorem.

Lemma 4. [Symmetrization Theorem, Lemma 2.3.1 in ^[17]] Let $\varepsilon_{1}, ..., \varepsilon_{n}$ be a Rademacher sequence with uniform distribution on $\{ - 1, 1\}$, independent of $X_{1}, ..., X_{n}$ and $f\in \mathcal{F}$. Then, we have

where ${\rm{E}}[\cdot]$ refers to the expectation w.r.t. $X_{1}, ..., X_{n}$ and ${\rm{E}}_{\epsilon}\left\{\cdot\right\}$ w.r.t. $\epsilon_{1}, ..., \epsilon_{n}$.

3.3.   Concentration for strongly log-concave discrete distributions

In this section, we restate the applications of the concentration inequality for a function of the data under the so-called strongly log-concave discrete distribution assumption, which was used in the Supplementary Material of ^[21]. We utilized the convex geometry approach to establish the tail bounds. In convex geometry, the following discrete version of the Prékopa-Leindler inequality can be found in Theorem 1.2 of ^[5]. The discrete version of the Prékopa-Leindler inequality is an essential inequality when deriving concentration inequalities of strongly log-concave counting measures. This shares the same idea when we consider the continuous version of Prékopa-Leindler inequality (see Theorem 3.15 of ^[18]).

Let $\lfloor r\rfloor = \max \{m \in \mathbb{Z}; m \leq r\}$ be the lower integer part of $r \in \mathbb{R}$, and $\lceil r\rceil = -\lfloor- r\rfloor$ be the upper integer part. Denote $\lfloor {\mathit{\boldsymbol{ x }}}\rfloor = \left(\left\lfloor x_{1}\right\rfloor, \ldots\left\lfloor x_{n}\right\rfloor\right)$ and $\lceil {\mathit{\boldsymbol{ x }}}\rceil = \left(\left\lceil x_{1}\right\rceil, \ldots, \left\lceil x_{n}\right\rceil\right)$.

Lemma 5. [Discrete Prékopa-Leindler inequality] Let $f, g, h, k: \mathbb{Z}^{n} \rightarrow [0, \infty)$ be functions that satisfy the following inequality:

Then, we have

From a geometric perspective, the Prékopa-Leindler inequality is a valuable method to prove concentration inequalities under Lipschitz functions of strongly log-concave distributions. From the idea in ^[12], a distribution ${P}$ with a density $p({\mathit{\boldsymbol{ x }}})$ (w.r.t. the counting measure) is said to be strongly discrete log-concave, if $\psi({\mathit{\boldsymbol{ x }}}) = :-\log p({\mathit{\boldsymbol{ x }}}) : \mathbb{Z}^{n} \rightarrow \mathbb{R}$ is strongly midpoint log-convex for some $\gamma > 0$:

The inequality (3.12) is an extension of strongly convexity for continuous functions on $\mathbb{R}^{n}$:

with modulus of convexity $\gamma$ ^[13].

Strongly log-convex property for a discrete density function requires that continuous functions are restricted on a lattice space. If $\gamma = 0$, (3.12) turns to the discrete midpoint convexity property for $\psi({\mathit{\boldsymbol{ x }}})$

see ^[12]. However, directly restricting a continuous function to some lattice space may not necessarily obtain discrete convex functions. For the corresponding counterexample, see ^[19].

For one-dimensional ${P}$, the probability mass function $p(x)$ is said to be log-concave if the sequence $\{p(x)\}_{x \in \mathbb{Z}}$ is log-concave; that is, for any $\lambda n+(1-\lambda) m \in \mathbb{Z}$ with $m, n \in \mathbb{Z}$ and $\lambda \in(0, 1)$, one has

Proposition 1. [The concentration inequality of strongly log-concave discrete distributions] Consider a strongly log-concave discrete distribution ${P}_\gamma$ with index $\gamma > 0$ on $\mathbb{Z}^{n}$. For $f: \mathbb{R}^{n} \rightarrow \mathbb{R}$ that is $L$-Lipschitz w.r.t. Euclidean norm, then,

Proof: Let $h$ be a zero-mean function with Lipschitz constant $L$ (w.r.t. the Euclidean norm). It remains to prove the upper bound of a moment generating function $\mathrm{E}e^{h({\mathit{\boldsymbol{ X }}})} \leq e^{\frac{L^{2}}{\tau}}$. Then, for $f$ with Lipschitz constant $K$ and $\lambda \in \mathbb{R},$ we apply the upper bound to the zero-mean function $h({\mathit{\boldsymbol{ X }}}): = \lambda(f({\mathit{\boldsymbol{ X }}})-\mathrm{E}f({\mathit{\boldsymbol{ X }}}))$, which has Lipschitz constant $L = \lambda K$. Given $\lambda \in(0, 1)$ and ${\mathit{\boldsymbol{ x }}}, {\mathit{\boldsymbol{ y }}} \in \mathbb{Z}^{n},$ define the proximity operator of $h$ as

With this proximity operator, the proof is proceeding by using the discrete Prekopa-Leindler inequality (Lemma 5) with $\lambda = 1 / 2$, $h({\mathit{\boldsymbol{ t }}}) = k({\mathit{\boldsymbol{ t }}}) = :p({\mathit{\boldsymbol{ t }}}) = e^{-\psi({\mathit{\boldsymbol{ t }}})}$, $f({\mathit{\boldsymbol{ x }}}): = e^ {-h({\mathit{\boldsymbol{ x }}})-\psi({\mathit{\boldsymbol{ x }}})}\; \text { and }\; g({\mathit{\boldsymbol{ y }}}): = e^{l({\mathit{\boldsymbol{ y }}})-\psi({\mathit{\boldsymbol{ y }}})}.$ We check that

Then, (3.11) satisfies Lemma 5 with $\lambda = 1 / 2$.

By discrete strong convexity of the function $\psi$

and the proximity operator of $h$, we have

which verifies (3.14).

By $\sum_{{\mathit{\boldsymbol{ x }}} \in \mathbb{Z}^{n}} h({\mathit{\boldsymbol{ x }}}) = \sum_{{\mathit{\boldsymbol{ x }}} \in \mathbb{Z}^{n}} k({\mathit{\boldsymbol{ x }}}) = 1$, we know that Lemma 5 gives

Then, Jensen's inequality implies

where in the last equality we use $\mathrm{E}[-h({\mathit{\boldsymbol{ X }}})] = \mathrm{E}[\lambda(f({\mathit{\boldsymbol{ X }}})-\mathrm{E}f({\mathit{\boldsymbol{ X }}}))] = 0$. The definition of the proximity operator shows

where the second last inequality due to $L$-Lipschitz of $h$, i.e., $|h({\mathit{\boldsymbol{ x }}})-h({\mathit{\boldsymbol{ Y }}})| \leq L\|{\mathit{\boldsymbol{ x }}}-{\mathit{\boldsymbol{ Y }}}\|_{2}.$

Then, we have $\mathrm{E}e^{\lambda(f({\mathit{\boldsymbol{ X }}})-\mathrm{E}f({\mathit{\boldsymbol{ X }}})]} \leq e^{\frac{1}{2}\cdot\lambda^{2}\cdot\frac{2L^{2}}{\gamma}}\; \text { for all } \lambda \in \mathbb{R}.$ This means that ${f({\mathit{\boldsymbol{ X }}})}-\mathrm{E}f({\mathit{\boldsymbol{ X }}})\sim\operatorname{subG}(\frac{2L^{2}}{\gamma})$, hence the tail bound is (3.13).

4.   Conclusions

Non-asymptotic statistical inference on high-dimensional data is important for many fields, such as data mining and machine learning. In this paper, we derived a novel concentration inequality for the sum of independent sub-Gaussian variables with random dependent weights in high-dimensional regression settings. We applied the proposed concentration inequality to obtain a high probability bound for the stochastic Lipschitz constant for negative binomial loss functions involved in Lasso-penalized negative binomial regressions, and used this bound to study oracle inequalities for the Lasso estimators. The usefulness of the proposed concentration inequality in applications was justified by solid theoretical proofs.

Use of AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

The authors would like to thank the reviewers and Dr. Pengfei Wang for their valuable suggestions that have significantly improved the quality of this paper. This work was supported in part by the National Natural Science Foundation of China under grant numbers 12101630 and 12261011, and the "double first-class" construction projects of Chinese universities under grant number ZG216S2348.

Conflict of interest

The authors declare no conflict of interest.