1 Introduction↩︎

1.1 The Marcinkiewicz discretization↩︎

Let \((\Omega, \mathcal{F}, \mu)\) be a probability space, where \(\mathcal{F}\) is a \(\sigma\)-algebra of subsets of \(\Omega\) and \(\mu\) is a probability measure on \(\mathcal{F}\). For \(1\leqslant p< \infty\), denote by \(L_p(\mu) \equiv L_p(\Omega,\mu)\) the usual Lebesgue space of measurable functions \(f\colon\Omega \to \mathbb{C}\) equipped with the norm \[\|f\|_{L_p(\mu)} = \left( \int_{\Omega} |f|^p\, d\mu \right)^{1/p}.\] Let \(B(\Omega)\) denote the space of all bounded functions \(f\colon\Omega \to \mathbb{C}\) equipped with the uniform norm \[\|f\|_{\infty}:=\sup_{x\in\Omega} |f(x)|.\] Let \(X_N \subset B(\Omega)\) be an \(N\)-dimensional linear space of bounded functions. We assume that any function \(f \in X_N\) that vanishes \(\mu\)-a.e. on \(\Omega\) is identically zero (equivalently, \(\|\cdot\|_{L_p(\mu)}\) defines a norm on \(X_N\)).

Our goal is to discretize the \(L_p\) norm on \(X_N\) by Marcinkiewicz-type inequalities. Specifically, given \(1\leqslant p<\infty\) and \(\varepsilon\in(0,1)\), we seek sampling points \(\xi^1,\dots,\xi^m\in\Omega\) (with \(m\geqslant N\)) such that \[\label{mz} (1-\varepsilon)\|f\|_{L_p(\mu)}^p \leqslant \frac{1}{m}\sum_{j=1}^m |f(\xi^j)|^p \leqslant (1+\varepsilon)\|f\|_{L_p(\mu)}^p, \quad \forall\, f\in X_N.\tag{1}\] The main problem is to determine the asymptotically optimal sample size \(m\) for which 1 holds on an arbitrary \(N\)-dimensional subspace \(X_N\) under natural structural assumptions.

1.2 Background and motivation↩︎

In the classical setting, \(X_N\) typically consists of trigonometric or algebraic polynomials of bounded degree on a compact domain \(\Omega \subset \mathbb{R}^d\), equipped with a normalized (possibly weighted) Lebesgue measure. In this case, inequalities of the form 1 are known as Marcinkiewicz–Zygmund inequalities. For these polynomial spaces, such inequalities with an asymptotically optimal sample size \(m \asymp N\) have been established on various regular compact domains, such as tori, intervals, spheres, cubes, and \(C^2\)-smooth domains in \(\mathbb{R}^d\); see, for instance, [1]–[8]. These inequalities play a fundamental role in the convergence of Fourier series, Lagrange interpolation, and polynomial approximation. However, classical techniques rely heavily on geometric properties of \(\Omega\) and often suffer from the curse of dimensionality as the ambient dimension \(d\) increases. These limitations motivate a more general high-dimensional theory in which \(X_N\) is an arbitrary \(N\)-dimensional subspace of \(B(\Omega)\). In this general setting, Marcinkiewicz discretization inequalities 1 are governed by the norms of the embeddings \((X_N,\|\cdot\|_{L_p}) \hookrightarrow B(\Omega)\), which are conveniently expressed via Nikolskii-type inequalities.

1.3 Nikolskii-type inequality↩︎

Given \(p \in [1,\infty)\), an \(N\)-dimensional subspace \(X_N \subset B(\Omega)\) is said to satisfy the \((p,\infty)\)–Nikolskii-type inequality with constant \(H\geqslant 1\) if \[\|f\|_{\infty} \leqslant H^{1/p}\,\|f\|_{L_p(\mu)}, \quad \forall\, f \in X_N.\] In this case, we write \(X_N \in \textrm{NI}_{p,\infty}(H)\).

It is readily seen that for any \(p \geqslant 2\), \[X_N \in \textrm{NI}_{p,\infty}(H) \implies X_N \in \textrm{NI}_{2,\infty}(H).\] In particular, for \(p \geqslant 2\), the condition \(X_N \in \textrm{NI}_{p,\infty}(H)\) implies that \(H \geqslant N\). Therefore, in this case we may write \(H = KN\) for some constant \(K \geqslant 1\).

1.4 Prior work↩︎

In recent years, the Marcinkiewicz discretization problem 1 has been extensively studied under the \((2,\infty)\)–Nikolskii-type inequality, namely, in the case when \[\label{1-1} X_N \in \textrm{NI}_{2,\infty}(K N),\tag{2}\] where \(K \geqslant 1\) is fixed (see, for instance, [9]–[17]). The techniques employed in these works are largely drawn from the theory of embeddings of finite-dimensional subspaces (see [18]–[24]). Although a constant \(K\) in 2 always exists by finite-dimensional norm equivalence, its size is crucial.

We now recall the main known results under the assumption \(X_N\in \textrm{NI}_{2,\infty}(KN)\).

(i) The case \(p=2\). By [11], [13], building on the groundbreaking work [25], the bound \[m \geqslant C\varepsilon^{-2}KN\] ensures an \(L_2\)-discretization inequality of the form 1 , up to an additional factor \(K\) on the right-hand side (see also [20]).

(ii) The case \(1\leqslant p<2\). It was shown in [10], using a refined form of Talagrand’s estimate [22]*Theorem 16.8.2, that 1 holds whenever \[m \geqslant C(p,\varepsilon) \begin{cases} (KN)\log(KN), & p=1,\\[1mm] (KN)\log(KN)(\log\log(KN))^2, & 1<p<2. \end{cases}\]

(iii) The case \(p>2\). This regime is different. If the \(L_p\) and \(L_2\) norms are equivalent on a subspace \(X_N\), that is, \[\|f\|_{L_p(\mu)} \leqslant M \|f\|_{L_2(\mu)}, \quad \forall\, f \in X_N,\] then the Marcinkiewicz discretization inequality necessarily requires at least \[\label{eq-lower} m \geqslant c(p) M^{-p} N^{p/2}\tag{3}\] sampling points (see [26] and [5]*D.20). Under 2 , it was shown in [12] that \[\label{p-under-2-nik} m \geqslant C(p,\varepsilon)(KN)^{p/2}\log(KN)\tag{4}\] suffices for 1 . To obtain nearly linear bounds in \(N\) for \(p>2\), [12] replaced 2 by the stronger condition \[X_N \in \textrm{NI}_{p,\infty}(KN),\] under which it was shown that 1 holds whenever \[\label{eq-p-1} m \geqslant C(p,\varepsilon)KN(\log(KN))^p.\tag{5}\] This was later improved in [27] to \[\label{eq-p-2} m \geqslant C(p,\varepsilon)KN(\log(KN))^{\min\{3,p\}}.\tag{6}\]

It is known (see Example 1 below) that for certain subspaces \(X_N \in \textrm{NI}_{p,\infty}(N)\) one cannot achieve 1 with fewer than \(N\log N\) random samples. Thus, for \(p>2\), the main unresolved issue in the random-sampling setting was whether one could bridge the gap between the lower bound of order \(N\log N\) and the previously known upper bounds of order \(N(\log N)^{\min\{p,3\}}\).

1.5 The main result on Marcinkiewicz discretization↩︎

In this paper, we establish the following probabilistic version of the \(L_p\) Marcinkiewicz discretization inequality for \(p>2\).

Given a probability space \((\Omega,\mathcal{F},\mu)\), we consider independent random points \(\xi^1,\ldots,\xi^m\) in \(\Omega\), not necessarily identically distributed, such that the average of their distributions is \(\mu\), that is, \[\label{probab-cond} \mu(E)=\frac{1}{m}\sum_{j=1}^m \mathbb{P}\{\xi^j\in E\}, \quad E\in\mathcal{F}.\tag{7}\] In particular, this condition is satisfied whenever the points \(\xi^1,\dots,\xi^m\) are i.i.d. with distribution \(\mu\).

In particular, for \(X_N\in \mathrm{NI}_{p,\infty}(KN)\), this improves the previously known bounds 5 and 6 , which involved polynomial losses in \(\log(KN)\), to \[m \asymp KN\log(KN)(\log\log(KN))^{p-1},\] which is optimal up to the factor \((\log\log(KN))^{p-1}\) in the random-sampling setting.

We also note that, up to the factor \((\log\log(KN))^{p-1}\), Theorem 1 recovers the bound 4 for spaces \(X_N \in \textrm{NI}_{2,\infty}(K N)\). Indeed, in this case \[\|f\|_\infty \leqslant(K N)^{1/2}\|f\|_{L_2(\mu)} \leqslant\bigl((K N)^{p/2}\bigr)^{1/p}\|f\|_{L_p(\mu)},\] so that \(X_N \in \textrm{NI}_{p,\infty}\bigl((K N)^{p/2}\bigr)\).

1.6 Restricted isometry property↩︎

Another sampling discretization problem considered in this paper is related to the construction of matrices with the restricted isometry property (RIP), a central notion in compressed sensing introduced by Candès and Tao [28] (see also [29]). Recall that an \(m\times N\) matrix \(A\) is said to satisfy the RIP of order \(s\) with constant \(\varepsilon\in(0,1)\) if \[\label{RIP} (1-\varepsilon)\|{\boldsymbol{a}}\|_{\ell_2^N}^2 \leqslant\|A{\boldsymbol{a}}\|_{\ell_2^m}^2 \leqslant(1+\varepsilon)\|{\boldsymbol{a}}\|_{\ell_2^N}^2, \quad \forall\, {\boldsymbol{a}}\in\mathbb{C}^N \text{ with } \|{\boldsymbol{a}}\|_0\leqslant s,\tag{8}\] where \(\|{\boldsymbol{a}}\|_0:=|\operatorname{supp}{\boldsymbol{a}}|\) denotes the number of nonzero coordinates of the vector \({\boldsymbol{a}}\).

A common approach (see [30]*Chapter 12) to construct such matrices is to sample from a bounded orthonormal system \(\mathcal{D}_N=\{\varphi_1,\dots,\varphi_N\}\subset B(\Omega)\) in \(L_2(\mu)\) satisfying \[\label{cond-bound} \|\varphi_j\|_\infty \leqslant K_0, \quad j=1,\dots,N.\tag{9}\] More precisely, the central problem is to determine how many random samples \(\xi^1,\ldots,\xi^m\) are required so that the sampled matrix \[\label{matrix} A=\frac{1}{\sqrt m} \begin{pmatrix} \varphi_1(\xi^1) & \cdots & \varphi_N(\xi^1)\\ \varphi_1(\xi^2) & \cdots & \varphi_N(\xi^2)\\ \vdots & \ddots & \vdots\\ \varphi_1(\xi^m) & \cdots & \varphi_N(\xi^m) \end{pmatrix}\tag{10}\] satisfies 8 with high probability.

Rudelson and Vershynin [31] proved that this holds whenever \[m \geqslant C(K_0,\varepsilon)\, s \log N \, (\log s)^2 \, \log(s \log N),\] and Haviv and Regev [32] (see also [33]) later improved this to \[\label{eq-HR} m \geqslant C(K_0,\varepsilon)\, s\log N\,(\log s)^2.\tag{11}\] Some intermediate results can be found in [34], [35].

For an orthonormal dictionary \(\mathcal{D}_N\), the RIP for a matrix of the form 10 is equivalent to sampling discretization of the \(L_2\) norm on the class of \(s\)-sparse functions. Indeed, if \({\boldsymbol{a}}\in\mathbb{C}^N\) and \[f=\sum_{j=1}^N a_j\varphi_j,\] then \(A{\boldsymbol{a}}\) is the vector of sampled values \((f(\xi^1),\dots,f(\xi^m))\) up to the factor \(m^{-1/2}\), and 8 becomes \[(1-\varepsilon)\|f\|_{L_2(\mu)}^2 \leqslant\frac{1}{m}\sum_{j=1}^m |f(\xi^j)|^2 \leqslant(1+\varepsilon)\|f\|_{L_2(\mu)}^2, \quad \forall\, f\in \Sigma_s(\mathcal{D}_N),\] where \[\Sigma_s(\mathcal{D}_N) := \bigcup_{\substack{J\subset \{1,2,\ldots, N\} \\ |J|=s}} \mathrm{span}\{\varphi_j\colon j\in J\}.\] This identifies RIP as a special case of universal sampling discretization.

1.7 Universal sampling discretization↩︎

The RIP formulation above suggests a natural extension in which the \(L_2\) norm is replaced by the \(L_p\) norm. This leads to a universal version of the Marcinkiewicz discretization problem: instead of discretizing the norm on a fixed finite-dimensional space, one seeks a single random sample that simultaneously discretizes the \(L_p\) norm over a family of finite-dimensional spaces generated by sparse subsets of a fixed finite dictionary. Problems of this type have recently been studied in [36]–[38].

To move beyond the orthogonal setting, we replace orthogonality by a one-sided \(s\)-sparse Riesz-type condition. Namely, we say that a dictionary \(\mathcal{D}_N=\{\varphi_1,\dots,\varphi_N\}\subset B(\Omega)\) is a uniformly bounded one-sided \(s\)-sparse Riesz system with constant \(K\geqslant 1\) if \[\|\varphi_j\|_\infty \leqslant 1, \quad j=1,\dots,N,\] and \[\label{riesz} \sum_{j=1}^N |a_j|^2 \leqslant K\Bigl\|\sum_{j=1}^N a_j\varphi_j\Bigr\|_{L_2(\mu)}^2, \quad \forall\, {\boldsymbol{a}}=(a_1,\dots,a_N)\in\mathbb{C}^N \;\text{with }\|{\boldsymbol{a}}\|_0\leqslant s.\tag{12}\] In particular, if \(\{\varphi_1, \ldots, \varphi_N\}\) is an orthonormal system satisfying 9 , then the rescaled system \(\mathcal{D}_N:=\{\tfrac{1}{K_0}\varphi_1, \ldots, \tfrac{1}{K_0}\varphi_N\}\) forms a uniformly bounded \(s\)-sparse Riesz system with constant \(K=K_0^2\). We note that this condition can be viewed as a variant of the Nikolskii-type inequality \(\textrm{NI}_{2,\infty}(\sqrt{Ks})\), since it implies that \[\|f\|_\infty\leqslant\sqrt{Ks}\|f\|_{L_2(\mu)} \quad \forall\, f\in \Sigma_s(\mathcal{D}_N).\]

The universal sampling discretization problem asks for conditions on \(m\) under which, for i.i.d. random points \(\xi^1,\dots,\xi^m\in\Omega\), one has \[\label{2-3-1} (1-\varepsilon)\|f\|_{L_p(\mu)}^p \leqslant\frac{1}{m}\sum_{j=1}^m |f(\xi^j)|^p \leqslant(1+\varepsilon)\|f\|_{L_p(\mu)}^p, \quad \forall\, f\in \Sigma_s(\mathcal{D}_N),\tag{13}\] with high probability. The non-Euclidean \(L_p\) case with \(p\ne 2\) is, as usual, significantly more challenging than the \(L_2\) case. The best previously known result in this direction was obtained in [37], where the Rudelson–Vershynin theorem was extended from \(p=2\) to the full range \(p\in[1,2]\). More precisely, it was shown there that when \[\label{eq-univ-m} m \geqslant C(p) K s \log N\, (\log (Ks))^2 \, \log(Ks \log N),\tag{14}\] then \(m\) random samples suffice to guarantee 13 for a uniformly bounded \(s\)-sparse Riesz system with constant \(K\geqslant 1\). Our next result improves this bound.

Compared with 14 , Theorem 2 reduces the logarithmic loss from \((\log(Ks))^2\,\log(Ks\log N)\) to \(\log s\,\log(Ks)\,\log\log(Ks),\) thus improving the overall dependence both on \(s\) and \(N\). Moreover, our bound differs from the best known \(L_2\) sample complexity 11 only by an additional factor of \(\log\log s\).

1.8 Notation↩︎

Throughout the paper we set \(\mathbb{N}_0=\mathbb{N}\cup\{0\}\). For \(p\in(1,\infty)\), we denote by \(p'=\frac{p}{p-1}\) the conjugate exponent of \(p\), and as usual we set \(p'=\infty\) for \(p=1\). We also adopt the convention that whenever an expression of the form \(\frac{pp_0}{p-p_0}\) appears with \(p=p_0\), it is understood to be equal to \(\infty\).

For a set of functions \(F\subset B(\Omega)\) and \(r\in(0,\infty)\), we define \[T_r(F):=\{|f|^r\colon f\in F\}.\] We identify a vector \(x\in\mathbb{C}^m\) with the function on \(\{1,\dots,m\}\) given by \(j\mapsto x(j)\). Accordingly, for \(0<r<\infty\) and \(G\subset\mathbb{C}^m\), we write \[|x|^r := \bigl(|x(1)|^r,\ldots,|x(m)|^r\bigr) \qquad\text{and}\qquad T_r(G):=\{|x|^r\colon x\in G\}.\] For \(1\leqslant q\leqslant\infty\), we denote by \(\|\cdot\|_q\) the standard \(\ell_q^m\) norm on \(\mathbb{C}^m\). For a sample \(\pmb\xi=(\xi^1,\dots,\xi^m)\), we define the associated normalized discrete \(\ell_q\) norm by \[\label{1-9-2025} \|f\|_{L_q(\pmb\xi)} := \begin{cases} \Bigl(\frac{1}{m}\sum\limits_{j=1}^m |f(\xi^j)|^q\Bigr)^{1/q}, & 1\leqslant q<\infty,\\[1em] \max\limits_{1\leqslant j\leqslant m}|f(\xi^j)|, & q=\infty. \end{cases}\tag{15}\] For a set \(F\subset B(\Omega)\), we define \[\label{1-16} F(\pmb\xi) := \bigl\{(f(\xi^1),\ldots,f(\xi^m))\colon f\in F\bigr\}\subset\mathbb{C}^m.\tag{16}\]

Throughout the paper, \(C,c>0\) denote positive absolute constants whose values may change from line to line. When several such constants appear in the same argument, we distinguish them by subscripts, writing \(C_1,C_2\), etc. These subscripts are only labels and do not indicate dependence on parameters. Such dependence is indicated explicitly, for instance by writing \(C(p)\) when dependence on the parameter \(p\) is involved.

1.9 Organization of the paper↩︎

The remainder of the paper is organized as follows. In Section 2, we introduce the probabilistic framework, discuss the connection with empirical moments of random vectors, and explain the limitations of the sole Nikolskii assumption. In Section 3, we formulate our main abstract discretization theorem, Theorem 3, the key chaining estimate, Theorem 4, and its application to \(\theta\)-convex indexing sets, Theorem 7.

Section 4 collects preliminary material on entropy numbers and Talagrand’s generic chaining theory. In Section 5, we present the main steps in the proof of Theorem 3, reducing it to the technical chaining estimate of Theorem 4. Section 6 is devoted to the derivation of Theorems 7 and 1, while Section 7 contains the proof of Theorem 2.

In Section 8, we review the aspects of van Handel’s approach to chaining needed in the sequel and prove a finite-dimensional version of the contraction principle. Finally, Section 9 contains the proof of Theorem 4, which is the main technical part of the paper.

2 Probabilistic setting and connection with empirical moments↩︎

2.1 Probabilistic framework↩︎

Let \(\pmb\xi:=(\xi^1,\ldots,\xi^m)\) be a sequence of independent random points in \(\Omega\) satisfying condition 7 , that is, \[\mu(E)=\frac{1}{m}\sum_{j=1}^m {\mathbb{P}}[\xi^j\in E], \quad E\in\mathcal{F}.\] Given a subclass \(F\subset B(\Omega)\), we define the discretization error by \[\mathop{\mathrm{Er}}_p(F,\pmb\xi) := \sup_{f\in F} \biggl| \frac{1}{m}\sum_{j=1}^m |f(\xi^j)|^p - \|f\|_{L_p(\mu)}^p \biggr|.\] Thus, for \[X_N^p:=\{f\in X_N\colon\|f\|_{L_p(\mu)}\leqslant 1\},\] the Marcinkiewicz discretization inequality 1 holds if and only if \[\mathop{\mathrm{Er}}_p(X_N^p,\pmb\xi)\leqslant\varepsilon.\] Our goal is to estimate the minimal sample size \(m\) for which \(\mathop{\mathrm{Er}}_p(X_N^p,\pmb\xi)\) is small, either in expectation or with high probability. More precisely, given \(\varepsilon,\delta\in(0,1)\), one seeks conditions ensuring that \[\mathbb{E}\,\mathop{\mathrm{Er}}_p(X_N^p,\pmb\xi)\leqslant\varepsilon \quad\text{or}\quad {\mathbb{P}}\bigl[\mathop{\mathrm{Er}}_p(X_N^p,\pmb\xi)>\varepsilon\bigr]\leqslant\delta.\]

2.2 Random sampling and empirical moments↩︎

The probabilistic Marcinkiewicz discretization problem is closely related to the problem of approximating moments of a random vector by empirical moments. Let \(\pmb\varphi\in\mathbb{R}^N\) be an \(N\)-dimensional random vector, and let \(\pmb\varphi^1,\dots,\pmb\varphi^m\) be independent copies of \(\pmb\varphi\). For a set \(B\subset\mathbb{R}^N\), consider \[V_p(B):= \sup_{y\in B} \biggl| \frac{1}{m}\sum_{j=1}^m |\langle \pmb\varphi^j,y\rangle|^p - \mathbb{E}|\langle \pmb\varphi,y\rangle|^p \biggr|.\] The problem of controlling \(V_p(B)\) with high probability has been extensively studied in high-dimensional probability. The most classical case corresponds to \(p=2\) and \(B\) being the Euclidean unit ball, which is equivalent to approximating the covariance matrix by the empirical covariance matrix in operator norm (see, for instance, [39]–[43]). More general values of \(p\) and more general index sets \(B\) have been studied to a much lesser extent, with only a few works addressing this level of generality, typically under some additional assumptions (see, for instance, [44]–[48]).

The connection with probabilistic Marcinkiewicz discretization becomes immediate after choosing a basis of \(X_N\). For simplicity, we assume that \(X_N\) consists solely of real-valued functions. Let \(\varphi_1,\dots,\varphi_N\) be a basis of \(X_N\), and define the random vector \[\pmb\varphi := (\varphi_1,\dots,\varphi_N)\colon (\Omega,\mathcal{F},\mu)\to\mathbb{R}^N.\] If \(\xi^1,\dots,\xi^m\) are i.i.d.random points in \(\Omega\) with distribution \(\mu\), then \[\pmb\varphi^j:=\bigl(\varphi_1(\xi^j),\dots,\varphi_N(\xi^j)\bigr), \quad j=1,\dots,m,\] are independent copies of \(\pmb\varphi\). Moreover, \[\mathop{\mathrm{Er}}_p(F,\pmb\xi)=V_p(B),\] where \[B:=\Bigl\{y=(y_1,\dots,y_N)\in\mathbb{R}^N\colon \sum_{k=1}^N y_k\varphi_k\in F\Bigr\}.\] Thus, probabilistic Marcinkiewicz discretization is equivalent to the empirical moment problem for random vectors associated with \(X_N\), and results obtained in either language can be readily translated into the other.

However, the standard assumptions used in the empirical moment literature are not well suited to the regime \(p>2\) considered in this paper. Typically, one assumes an almost sure bound \[\label{diam} \|\pmb\varphi\|_{\ell_2^N}\leqslant\sqrt{KN}\tag{17}\] together with a moment-comparison estimate of the form \[\label{moments} \bigl(\mathbb{E}|\langle \pmb\varphi,y\rangle|^q\bigr)^{1/q} \leqslant M\bigl(\mathbb{E}|\langle \pmb\varphi,y\rangle|^2\bigr)^{1/2}, \qquad \forall\, y\in\mathbb{R}^N,\tag{18}\] for some \(q\geqslant p\). When the basis \(\{\varphi_k\}_{k=1}^N\) is orthonormal in \(L_2(\mu)\), condition 17 corresponds to the usual \((2,\infty)\)-Nikolskii inequality \(X_N\in \mathrm{NI}_{2,\infty}(KN)\). By contrast, condition 18 translates into the norm-equivalence assumption \[\|f\|_{L_p(\mu)}\leqslant\|f\|_{L_{q}(\mu)}\leqslant M\|f\|_{L_2(\mu)},\quad \forall\, f\in X_N,\] which is too restrictive for the discretization problem when \(p>2\): it fails in many classical spaces, such as spaces of trigonometric or algebraic polynomials, and, more importantly, it is precisely this condition that forces the required number of sampling points to grow polynomially in the dimension (see 3 ).

For this reason, we do not impose any moment-comparison assumptions. Instead, we work under the more flexible \((p,\infty)\)-Nikolskii condition \(X_N\in\mathrm{NI}_{p,\infty}(H)\) and seek high-probability discretization bounds in terms of the Nikolskii constant \(H\). It is worth mentioning that this framework still contains the classical \((2,\infty)\) setting, since \[\mathrm{NI}_{2,\infty}(KN)\implies \mathrm{NI}_{p,\infty}\bigl((KN)^{p/2}\bigr).\]

2.3 Limitations of the \((p,\infty)\)-Nikolskii assumption↩︎

The generality of the \((p,\infty)\)-Nikolskii assumption comes with an intrinsic limitation: in this setting, one cannot in general obtain probabilistic Marcinkiewicz discretization with fewer than \(\mathcal{O}(N \log N)\) random samples. This already appears in the model case of the uniform measure on an \(N\)-point set.

3 The main abstract results↩︎

3.1 A general estimate in terms of the chaining functional↩︎

Our main abstract discretization theorem bounds the expected uniform discretization error \(\mathop{\mathrm{Er}}_p(F,\pmb{\xi})\) of the \(L_p\) norm over an arbitrary function set \(F\) containing \(0\), in terms of Talagrand’s chaining functional (see Definition 3) \[\gamma_{p,p_0}\Bigl(F,\|\cdot\|_{L_{p_1}(\pmb{\xi})}\Bigr) := m^{\frac{1}{p}-\frac{1}{p_0}} \gamma_{p,p_0}\Bigl(F(\pmb{\xi}),\|\cdot\|_{p_1}\Bigr),\] where \(p\geqslant 2\), \(p_0\in(1, p]\), \(p_1:=\frac{pp_0}{p-p_0}\), and \(F(\pmb{\xi})\) is defined in 16 .

To formulate the theorem, let \((\Omega,\mathcal{F},\mu)\) be a probability space, and let \(\pmb{\xi}:=(\xi^1,\ldots,\xi^m)\) be a collection of \(m\) independent random elements taking values in \(\Omega\) and satisfying condition 7 .

The results announced in Section 1 will be derived from this theorem.

Our approach relies on Talagrand’s generic chaining [22], combining ideas from [24] with van Handel’s more recent approach  [49], [50], which utilizes interpolation functionals and the contraction principle. This framework is particularly convenient in our setting, since it allows one to compare a given chaining functional with more tractable auxiliary ones.

Let \(F \subset B(\Omega)\) be a bounded set. A standard symmetrization argument, combined with Talagrand’s majorizing measure theorem, implies (see 35 ) that \[\mathbb{E}\mathop{\mathrm{Er}}_p(F,\pmb{\xi}) \leqslant\frac{C(p)}{m}\, \mathbb{E}\,\Bigl[ \gamma_{p,1}\bigl(T_p(F(\pmb\xi)),\|\cdot\|_{p'}\bigr)\Bigr],\] thereby reducing the problem to the estimation of \(\gamma_{p,1}\bigl(T_p(G),\|\cdot\|_{p'}\bigr)\) for the vector set \[G:=F(\pmb\xi)\subset \mathbb{C}^m.\] The main difficulty is that the geometry of \(T_p(G)\) is usually much more complicated than that of the original set \(G\), making it hard to obtain direct, sharp estimates of \(\gamma_{p,1}\bigl(T_p(G),\|\cdot\|_{p'}\bigr)\) in concrete situations. The key step in our argument is therefore to bound this functional in terms of more tractable auxiliary chaining quantities on \(G\). This is formalized in the following abstract comparison theorem.

3.2 Uniformly convex classes↩︎

Theorem 3 is especially useful when the indexing sets \(F\) are \(\theta\)-convex for some \(\theta\geqslant 2\) (see Definition 6). It is well-known that Euclidean balls are \(2\)-convex. More generally, for any \(1<p<\infty\), and any finite-dimensional subspace \(X_N\) of \(L_p(\mu)\), the unit ball \[X_N^p:=\{f\in X_N\colon \|f\|_{L_p(\mu)}\leqslant 1\}\] is \(\max\{p, 2\}\)-convex with a constant \(\eta=\eta(p)\) depending only on \(p\).

Guédon and Rudelson [47] established the following estimate for every \(p\geqslant\theta\) and every \(\theta\)-convex subset \(F\) of a Euclidean ball \(D\), with \(\theta\)-convexity constant \(\eta\): \[\label{GR-est} \mathbb{E}\mathop{\mathrm{Er}}_p(F,\pmb{\xi}) \leqslant C(p,\eta)\Bigl(A + A^{1/2} \sup_{f \in F} \|f\|_{L_p(\mu)}^{p/2}\Bigr),\tag{24}\] where \[A = \frac{(\log m)^{2(1-\frac{1}{\theta})}}{m} \mathbb{E}\Bigl( \sup_{f \in D}\|f\|_{L_\infty(\pmb{\xi})}^2 \sup_{g \in F}\|g\|_{L_\infty(\pmb{\xi})}^{p-2} \Bigr).\] The specific case where \(F=D\) is the Euclidean ball and \(p=2\) was treated earlier by Rudelson [51]. The estimate 24 was further improved in [12]*Corollary 4.4, where it was shown to hold with \[A = \frac{1}{m} \mathbb{E}\Bigl( \sup_{f \in D}\|f\|_{L_\infty(\pmb{\xi})}^2 \sup_{g \in F}\|g\|_{L_\infty(\pmb{\xi})}^{p-2} \Bigr) + \frac{\log m}{m} \mathbb{E}\Bigl( \sup_{g \in F}\|g\|_{L_\infty(\pmb{\xi})}^{p}\Bigr).\] Taking \(\theta=p\geqslant 2\), \(F = X_N^p\), and \(D = X_N^2\), one obtains the Marcinkiewicz discretization inequality 1 with \(m = C(p, \varepsilon) H^{p/2} \log H\) sampling points for each subspace \(X_N \in \textrm{NI}_{2,\infty}(H)\).

To cover the case \(X_N \in \textrm{NI}_{p,\infty}(H)\) with \(p>2\), the following counterpart of the estimate 24 was proved in [12]*Corollary 4.7 for any \(\theta\)-convex subset \(F\) of \(B(\Omega)\): \[\mathbb{E}\mathop{\mathrm{Er}}_p(F,\pmb{\xi}) \leqslant C(p, \eta)\Bigl(A + A^{\frac{1}{\theta}} \sup_{f \in F} \|f\|_{L_p(\mu)}^{p(1-\frac{1}{\theta})}\Bigr),\] where \[A = \frac{(\log m)^\theta}{m} \mathbb{E} \sup_{g \in F}\|g\|_{L_\infty(\pmb{\xi})}^p.\] Taking here \(F = X_N^p\) and \(\theta=p\), one obtains the Marcinkiewicz discretization inequality 1 with \(m = C(p, \varepsilon)\, H (\log H)^p\) sampling points for every subspace \(X_N \in \textrm{NI}_{p,\infty}(H)\) (see [27]*Theorem 2.2 for further refinements).

In this paper, we deduce from Theorem 3 the following general result on the discretization error over \(\theta\)-convex sets \(F \subset B(\Omega;\mathbb{R})\), where \((\Omega,\mathcal{F}, \mu)\) denotes an arbitrary probability space, and \(B(\Omega;\mathbb{R})\) denotes the space of all bounded real-valued functions on \(\Omega\).

Taking \(F = X_N^p\), one deduces Theorem 1 for a subspace \(X_N \in \textrm{NI}_{p,\infty}(H)\) in the real case.

4 Preliminaries: entropy, entropy numbers and chaining functionals↩︎

In this section, we recall several basic facts concerning entropy numbers and Talagrand’s generic chaining theory [22]. We begin by fixing some notation.

Let \((\mathbf{T},\varrho)\) be a metric space. For \(x\in \mathbf{T}\) and \(r>0\), we write \[B_\varrho(x,r):=\{y\in \mathbf{T}\colon \varrho(x,y)\leqslant r\}\] for the closed ball of radius \(r\) centered at \(x\). For a set \(A\subset \mathbf{T}\), we define \[\mathop{\mathrm{diam}}(A,\varrho):=\sup_{s,t\in A}\varrho(s,t)\; \;\text{and}\; \;\varrho(s, A):=\inf_{t\in A}\varrho(s,t)\; \;\text{for s\in \mathbf{T}}.\] If the metric \(\varrho\) is induced by a norm \(\|\cdot\|\), we write \(\mathop{\mathrm{diam}}(A,\|\cdot\|)\) instead of \(\mathop{\mathrm{diam}}(A,\varrho)\).

For a finite set \(\Lambda\), we denote its cardinality by \(|\Lambda|\). For \(x\geqslant 0\), we write \(\lceil x\rceil\) for the smallest integer greater than or equal to \(x\). Finally, we set \[N_0:=1, \quad N_n:=2^{2^n}, \quad n\in\mathbb{N}.\]

4.1 Entropy and entropy numbers↩︎

Clearly, \[e_n(A,\varrho) = \inf\bigl\{\varepsilon>0\colon\mathcal{H}_\varepsilon(A,\varrho)\leqslant 2^n\bigr\}.\] One may also define entropy numbers without requiring the centers of the covering balls to belong to \(A\), namely \[\tilde{e}_n(A,\varrho):= \inf\Bigl\{\varepsilon>0\colon A\subset \bigcup_{j=1}^{N_n} B_\varrho(x_j,\varepsilon) \text{ for some } x_1,\dots,x_{N_n}\in \mathbf{T} \Bigr\}.\] Then \[\label{3-1-0} \tilde{e}_n(A,\varrho)\leqslant e_n(A,\varrho)\leqslant 2\,\tilde{e}_n(A,\varrho).\tag{26}\] If the metric \(\varrho\) is induced by a norm \(\|\cdot\|\), we also write \(e_n(A,\|\cdot\|)\) instead of \(e_n(A,\varrho)\).

We shall use the following standard properties of entropy numbers in finite-dimensional spaces, which follow from [52]*Corollary 7.2.2 and [52]*Estimate (7.1.6).

For further properties of entropy numbers, we refer to [52]*Chapter 7.

4.2 The Talagrand chaining functional↩︎

By definition, \[\mathop{\mathrm{diam}}(\mathbf{T},\varrho) = \sup_{x\in\mathbf{T}}\mathop{\mathrm{diam}}(\mathcal{A}_0(x),\varrho) \leqslant \gamma_{\alpha,\beta}(\mathbf{T},\varrho).\] Thus, without loss of generality, we may always assume that \(\mathop{\mathrm{diam}}(\mathbf{T},\varrho)<\infty\).

There is an equivalent description of the chaining functional in terms of approximating sets.

It is known (see [22]*Theorem 2.3.1 and [49]*Lemma 4.2) that: \[\label{eq-gamma-equiv} \gamma_{\alpha,\beta}^*(\mathbf{T},\varrho) \leqslant \gamma_{\alpha,\beta}(\mathbf{T},\varrho) \leqslant C(\alpha)\,\gamma_{\alpha,\beta}^*(\mathbf{T},\varrho).\tag{28}\]

The chaining functional is also linked to entropy numbers through the estimate \[\label{1-2-2025} \gamma_{\alpha,\beta}(\mathbf{T},\varrho) \leqslant C(\alpha) \biggl( \sum_{n=0}^\infty \bigl[2^{n/\alpha}e_n(\mathbf{T},\varrho)\bigr]^\beta \biggr)^{1/\beta}.\tag{29}\]

The following theorem of Talagrand, which connects the supremum of a random process with the associated chaining functional, is a basic tool in what follows.

4.3 Entropy and chaining functionals of \(\theta\)-convex sets↩︎

Uniform convexity, and in particular \(\theta\)-convexity, plays an important role in the study of entropy numbers and Talagrand’s chaining functionals in normed spaces. In this section, we collect several known estimates for \(\theta\)-convex sets that will be used later to derive a convenient upper bound for the chaining functional appearing in our main arguments.

We begin by recalling the definition of a \(\theta\)-convex set.

Classical examples of \(\theta\)-convex Banach spaces are the spaces \(L_p\), \(1<p<\infty\), and their closed linear subspaces, with \(\theta=\max\{p,2\}\).

The entropy bound 29 provides a general estimate for chaining functionals in terms of entropy numbers. While this estimate is sufficiently strong for many purposes, it is often not optimal and may lose logarithmic factors. A substantial improvement is possible when the underlying set is uniformly convex (see, for instance, [22], [49], [50]). In particular, for \(\theta\)-convex sets one has the following refinement of 29 .

For \(\theta\)-convex sets one also has the following estimate for entropy numbers in the sampled \(\ell_\infty\) norm (see [22]*Lemma 16.5.4, [12]*Corollary 4.2, [54]).

5 Proof of Theorem 3↩︎

As explained in Subsection 3.1, the proof of Theorem 3 relies on the estimate provided by Theorem 4. Since the proof of Theorem 4 is rather involved, we postpone it to Section 9. Assuming Theorem 4, we now proceed to prove Theorem 3.

Recall that \(\pmb\xi=(\xi^1,\dots,\xi^m)\in\Omega^m\), where \(\xi^1,\dots,\xi^m\) are independent random points satisfying \[\label{5-1b} \mu(E)=\frac{1}{m}\sum_{j=1}^m {\mathbb{P}}[\xi^j\in E], \quad \text{for every measurable } E\subset\Omega.\tag{31}\] For \(1\leqslant q\leqslant\infty\), the seminorm \(\|\cdot\|_{L_q(\pmb\xi)}\) is defined in 15 . For \(1\leqslant p<\infty\) and \(F\subset B(\Omega)\), we write \[\label{4-1a} \mathop{\mathrm{Er}}_p(F,\pmb\xi):= \sup_{f\in F} \Biggl| \frac{1}{m}\sum_{j=1}^m |f(\xi^j)|^p - \|f\|_{L_p(\mu)}^p \Biggr|.\tag{32}\]

The proof of Theorem 3 is divided into four steps, which are carried out in the next four subsections. In Step 1, we combine a standard symmetrization argument with Talagrand’s majorizing measure theorem to obtain \[\label{4-7-eq} \mathbb{E}\mathop{\mathrm{Er}}_p(F,\pmb\xi) \leqslant \frac{C(p)}{m}\, \mathbb{E}_{\pmb\xi}\, \Bigl[\gamma_{p,1}\bigl(T_p(F(\pmb\xi)),\|\cdot\|_{p'}\bigr)\Bigr].\tag{33}\] In Step 2, we establish Theorem 3 for the case \(q=1\) by applying  33 and optimizing the parameters in Theorem 4. In Step 3, we extend this result to \(q>1\) via Talagrand’s concentration inequality (Lemma 7), which bounds the \(L_q(\mu)\)-norm of Banach space-valued random elements by their \(L_1(\mu)\)-norm. Finally, in Step 4, we deduce the probability estimate 22 .

5.1 Step 1: Symmetrization↩︎

Let \(\pmb\varepsilon=(\varepsilon_1,\dots,\varepsilon_m)\) be a sequence of i.i.d. random variables, each taking the values \(\pm1\) with probability \(1/2\), and assume that \(\pmb\varepsilon\) is independent of the random points \(\xi^1,\dots,\xi^m\).

In this step, we use a standard Giné–Zinn symmetrization argument (see, for instance, [22]*Lemma 9.1.11, [47], and [12]*Lemma 3.1) to obtain the following estimate.

For completeness, we provide the proof below.

By Lemma 4, \[\label{5-2b} \mathbb{E}\mathop{\mathrm{Er}}_p(F,\pmb\xi) \leqslant \frac{2}{m}\,\mathbb{E}_{\pmb\xi}\mathbb{E}_{\pmb\varepsilon} \Bigl[\sup_{x\in T_p(F(\pmb\xi))}|W_x|\Bigr] = \frac{2}{m}\,\mathbb{E}_{\pmb\xi}\mathbb{E}_{\pmb\varepsilon} \Bigl[\sup_{x\in T_p(F(\pmb\xi))}|W_x-W_0|\Bigr],\tag{34}\] where \[W_x:=\sum_{j=1}^m \varepsilon_j x(j), \quad x\in T_p(F(\pmb\xi))\subset\mathbb{R}^m.\] Now we fix the points \(\xi^1,\dots,\xi^m\in\Omega\) and apply Theorem 9 to the process \[\{W_x\colon x\in T_p(F(\pmb\xi))\}.\] To do so, we need to verify the increment condition 30 . This follows from the following tail estimate for Bernoulli processes.

Therefore, by Theorem 9 and Lemma 5, there exists a constant \(C(p)>0\) such that \[\mathbb{E}_{\pmb\varepsilon}\Bigl[\sup_{x\in T_p(F(\pmb\xi))}|W_x-W_0|\Bigr] \leqslant C(p)\,\gamma_{p,1}\bigl(T_p(F(\pmb\xi)),\|\cdot\|_{p'}\bigr).\] Combining this with 34 , we obtain \[\label{5-8b} \mathbb{E}\mathop{\mathrm{Er}}_p(F,\pmb\xi) \leqslant \frac{C(p)}{m}\, \mathbb{E}_{\pmb\xi}\Bigl[\gamma_{p,1}\bigl(T_p(F(\pmb\xi)),\|\cdot\|_{p'}\bigr)\Bigr].\tag{35}\]

5.2 Step 2: Deriving Theorem 3 for \(q=1\) from Theorem 4↩︎

Let \(q=1\). For simplicity, we define \(m_1:=\frac{m}{m_0}\), and \[\label{4-5d} \delta:=\frac{H}{m_1\log m_1},\tag{36}\] where \(H\) is the constant from the estimates 20 and 19 for \(q=1\). Since \(m_1\geqslant 16\), by 21 , we obtain \[\label{4-5c} 0<\delta\leqslant\frac{1}{(\log m_1)\cdot e\,(e\log\log m_1)^{p/p_0'}} < e^{-1-p/p_0'}.\tag{37}\]

We now apply Theorem 4 with the set \(G = F(\pmb{\xi})\) for a fixed \(\pmb{\xi}=(\xi^1,\dots,\xi^m)\). Let \(0<b<1\), \(\alpha_0 \in (0,1)\), and \(n_0 \in \mathbb{N} \cap [2,\infty)\) be parameters to be specified later. Since \(b\,\alpha_0^{1/p}\leqslant n_0\), Theorem 4 yields \[\begin{align} &{\gamma}_{p,1}\bigl(T_p( F(\pmb{\xi}) ), \|\cdot\|_{p'}\bigr) \leqslant C(p)\Biggl[ A_{m_1}(n_0, b, {\alpha}_0)\, m\, \sup_{f \in F} \|f\|_{L_p( \pmb{\xi})}^p \\ &+ \frac{m}{m_1^{p_0/p}}\cdot \sup_{f\in F}\|f\|_{L_\infty(\pmb\xi)}^{p-p_0}\cdot \frac{\Bigl[{\rm diam}\bigl(F, \|\cdot\|_{L_{p_1}( \pmb{\xi})}\,\bigr)\Bigr]^{p_0} + \Bigl[m_0^{-1/p}{\gamma}_{p,p_0}\,\bigl(F, \|\cdot\|_{L_{p_1}(\pmb{\xi})}\,\bigr)\Bigr]^{p_0}}{b^{p_0-1}}\Biggr], \end{align}\] where \[A_{m_1}(n_0, b, {\alpha}_0) := bn_0 + (2^{n_0}\, {\alpha}_0)^{-1/p} \log m_1.\] Since \(0\in F\), we have \[{\rm diam}\bigl(F,\|\cdot\|_{L_{p_1}(\pmb{\xi})}\bigr) \leqslant 2 \sup_{g\in F}\|g\|_{L_{p_1}(\pmb{\xi})}.\] Thus, substituting into 35 , and using 20 and 19 with \(q=1\), we deduce \[\begin{align} &\mathbb{E}\mathop{\mathrm{Er}}_p(F, \pmb{\xi}) \leqslant{C_1(p)}\Bigg[ A_{m_1}(n_0, b, {\alpha}_0)\,\mathbb{E}\bigl[\sup_{f \in F} \|f\|_{L_p( \pmb{\xi})}^p\bigr] + \Bigl(\frac{H}{m_1}\Bigr)^{p_0/p}\cdot b^{1-p_0}\Bigg]. \end{align}\] Moreover, by 32 , \[\sup_{f \in F} \|f\|_{L_p( \pmb{\xi})}^p=\sup_{f\in F} \frac{1}{m}\sum_{j=1}^m |f(\xi^j)|^p \leqslant\mathop{\mathrm{Er}}_p(F, \pmb{\xi}) + \sup_{f \in F} \|f\|_{L_p(\mu)}^p.\] Thus, setting \(L := \sup\limits_{f \in F} \|f\|_{L_p(\mu)}^p + 1\) and using 36 , we obtain \[\begin{align} \label{5-6c} \mathbb{E}\mathop{\mathrm{Er}}_p(F, \pmb{\xi}) &\leqslant C_1(p) \Bigg[ A_{m_1}(n_0, b, {\alpha}_0) \Bigl(\mathbb{E}\mathop{\mathrm{Er}}_p(F, \pmb{\xi})+ \sup_{f \in F} \|f\|_{L_p(\mu)}^p\Bigr) +\frac{{\delta}^{p_0/p} \cdot (\log m_1)^{p_0/p}}{ b^{p_0-1}}\Bigg]\\ &\leqslant C_1(p) A_{m_1}(n_0, b, {\alpha}_0) \mathbb{E}\mathop{\mathrm{Er}}_p(F, \pmb{\xi})+ C_1(p) L\, B_{m_1}(n_0, b, {\alpha}_0),\notag \end{align}\tag{38}\] where \[B_{m_1}(n_0, b, {\alpha}_0) := b n_0 + (2^{n_0}\, {\alpha}_0)^{-1/p} \log m_1 + \frac{ {\delta}^{p_0/p} \cdot (\log m_1)^{p_0/p}}{b^{p_0-1}}.\label{5-15c}\tag{39}\]

We will choose the parameters \(n_0, b, {\alpha}_0\) so that \[\label{5-6b} A_{m_1}(n_0, b, {\alpha}_0) = bn_0 + (2^{n_0}\, {\alpha}_0)^{-1/p} \log m_1 \leqslant\frac{1}{2C_1(p)},\tag{40}\] which, combined with 38 , will yield \[\mathbb{E}\mathop{\mathrm{Er}}_p(F, \pmb{\xi}) \leqslant 2 C_1(p) L\, B_{m_1}(n_0, b, {\alpha}_0).\]

We now specify the parameters \(b, {\alpha}_0, n_0\) by minimizing the function \(B_{m_1}(n_0, b, {\alpha}_0)\) in 39 , subject to the constraint 40 . Let \(c=c(p)\in (0, 1/2)\) be a small constant (depending only on \(p\)) to be specified later. First, choose \[b := c\cdot \frac{{\delta}^{1/p} (\log m_1)^{1/p}}{n_0^{1/p_0}} \label{4-12a}\tag{41}\] so that \(b n_0 =\frac{c^{p_0} \, {\delta}^{p_0/p}\, (\log m_1)^{p_0/p}}{b^{p_0-1}}\), and hence \[\begin{align} B_{m_1}(n_0, b, {\alpha}_0) &=(c+ c^{1-p_0})({\delta}\log m_1)^{1/p} n_0^{1/p_0'} + (2^{n_0}\, {\alpha}_0)^{-1/p} \log m_1\\ &\leqslant 2 c^{-(p_0-1)} ({\delta}\log m_1)^{1/p} n_0^{1/p_0'} + (2^{n_0}\, {\alpha}_0)^{-1/p} \log m_1. \end{align}\] Now, setting \({\alpha}_0 := ( \log m_1)^{-1}\), we obtain \[B_{m_1}(n_0, b, {\alpha}_0) \leqslant(\log m_1)^{1/p} \left[ 2^{-n_0/p} \log m_1 + 2c^{1-p_0}{\delta}^{1/p} n_0^{1/p_0'} \right].\] Second, to balance these last two terms in the brackets, we require that \(2^{-n_0/p} \log m_1 \sim {\delta}^{1/p}\), that is, \(2^{n_0} \sim {\delta}^{-1} (\log m_1)^p\). More precisely, choose \(n_0 \in \mathbb{N}\) such that \[2^{n_0-1} \leqslant c^{-p} {\delta}^{-1} (\log m_1)^p \leqslant 2^{n_0 }.\] Using 37 , we have \[\label{5-21-c} n_0 \leqslant C_2(p) \Bigl[ \log {\delta}^{-1} + \log \log m_1+\log c^{-1}\Bigr]\leqslant C_3(p) |\log c| \cdot|\log {\delta}|,\tag{42}\] and, since \(p_0\leqslant p\) and \(\frac{1}{p_0'}\leqslant\frac{1}{p'}\), \[\begin{align} B_{m_1}(n_0, b, {\alpha}_0) &\leqslant 3 c^{1-p_0} (\log m_1)^{1/p} {\delta}^{1/p} n_0^{1/p_0'}\leqslant C_4(p, c)\, |\log{\delta}|^{ 1/p_0'}\, ({\delta}\cdot \log m_1)^{1/p}. \end{align}\] Thus, assuming the chosen parameters satisfy 40 , we obtain \[\mathbb{E}\mathop{\mathrm{Er}}_p(F, \pmb{\xi}) \leqslant C_5(p, c)L\cdot \bigl( {\delta}\cdot \log m_1\bigr)^{1/p}\cdot | \log {\delta}|^{1/p_0'},\] which combined with 36 , gives us the desired result: \[\mathbb{E}\mathop{\mathrm{Er}}_p(F, \pmb{\xi}) \leqslant C_5(p, c) \Bigl(\frac{Hm_0}{m}\Bigr)^{\frac{1}{p}} \Bigl(\log\log \frac{m}{m_0} + \log \frac{m}{Hm_0}\Bigr)^{1-\frac{1}{p_0}}\Bigl(1+\sup\limits_{f \in F} \|f\|_{L_p(\mu)}^p\Bigr).\]

Thus, it remains to show that 40 holds for a sufficiently small constant \(c \in (0, 1/2)\). Indeed, from 41 and 42 , we get \[\begin{align} A_{m_1}(n_0, b,{\alpha}_0)&:=b n_0 + 2^{-n_0/p}\, (\log m_1)^{1+\frac{1}{p}}\leqslant c n_0^{1/p_0'}{\delta}^{1/p}( \log m_1)^{1/p} + c {\delta}^{1/p} (\log m_1)^{1/p} \\ &\leqslant 2c {\delta}^{1/p} (\log m_1)^{1/p}\, n_0^{1/p_0'}\leqslant C_6(p) c |\log c|^{1/p_0'} \cdot \Bigl( {\delta}\cdot |\log {\delta}|^{p/p_0'}\, \log m_1\Bigr)^{1/p}. \end{align}\] Since the function \(x|\log x|^{p/p_0'}\) is increasing on \((0, e^{-p/p_0'})\), it follows by 37 that \[{\delta}\cdot |\log {\delta}|^{p/p_0'} \leqslant\frac{ (\log\log m_1 {+1+p} +p\log\log \log m_1)^{p/p_0'}}{ (\log m_1) \cdot (\log\log m_1)^{p/p_0'}}\leqslant\frac{C_7(p)}{\log m_1}.\] Hence, we have \[A_{m_1}(n_0, b,{\alpha}_0) \leqslant C_8(p) c |\log c|^{1/p_0'}\leqslant C_8(p) c |\log c|^{1/p'}.\] Finally, we choose \(c = c(p) \in (0,1)\) sufficiently small so that 40 holds. This completes the proof of Theorem 3 for \(q = 1\).

5.3 Step 3: Deriving Theorem 3 for \(q>1\)↩︎

Having established Theorem 3 for \(q = 1\), we now use this result to prove the case \(q > 1\). For this purpose, we require the following lemma.

The proof of Lemma 6 relies on the following concentration inequality of Talagrand.

We are now in a position to prove the claim of Theorem 3 for all \(q > 1\). First, note that \[\max_{1 \leqslant j \leqslant m} \sup_{f \in F} |f(\xi^j)|^p \leqslant m^{1- {\frac{p_0}{p}}} \sup_{f \in F}\|f\|_{L_\infty(\pmb\xi)}^{p-p_0}\cdot \sup_{g \in F}\|g\|_{L_{p_1}( \pmb\xi)}^{p_0}.\] Thus, 19 implies 43 with \[H_0 = H^{p_0/p}m^{1-\frac{p_0}{p}},\] and hence, by Lemma 6, we obtain \[\label{9-2b} \left( \mathbb{E}|\mathop{\mathrm{Er}}_p(F, \pmb{\xi})|^q \right)^{1/q} \leqslant\frac{Cq}{1+\log q} \max\Bigl\{ \mathbb{E}\mathop{\mathrm{Er}}_p(F, \pmb{\xi}),\;\Bigl(\frac{H}{m}\Bigr)^{p_0/p} \Bigr\}.\tag{44}\] Next, by Hölder’s inequality, \[\mathbb{E}\, \Bigl(\sup_{f\in F}\|f\|_{L_\infty(\pmb\xi)}^{p-p_0} \sup_{g\in F}\|g\|_{L_{p_1}(\pmb{\xi})}^{p_0}\Bigr) \leqslant H^{p_0/p},\] so we may apply the results from Step 2 (Subsection 5.2). For all \(m\) satisfying 21 , we then obtain \[\label{9-2a} \mathbb{E}\mathop{\mathrm{Er}}_p(F, \pmb{\xi}) \leqslant C_9(p) \Bigl(\frac{Hm_0}{m}\Bigr)^{\frac{1}{p}} \Bigl(\log\log \frac{m}{m_0} + \log \frac{m}{Hm_0}\Bigr)^{1-\frac{1}{p_0}}\Bigl(1+\sup\limits_{f \in F} \|f\|_{L_p(\mu)}^p\Bigr).\tag{45}\] On the other hand, 21 clearly implies that \[\Bigl(\frac{H}{m}\Bigr)^{p_0/p}\leqslant\Bigl(\frac{Hm_0}{m}\Bigr)^{1/p}\leqslant\text{RHS of \eqref{9-2a}}.\] This combined with 44 and 45 then yields \[\left( \mathbb{E}|\mathop{\mathrm{Er}}_p(F, \pmb{\xi})|^q \right)^{1/q}\leqslant\frac{C_{10}(p)q}{1+\log q}\Bigl(\frac{Hm_0}{m}\Bigr)^{\frac{1}{p}} \Bigl(\log\log \frac{m}{m_0} + \log \frac{m}{Hm_0}\Bigr)^{1-\frac{1}{p_0}}\Bigl(1+\sup\limits_{f \in F} \|f\|_{L_p(\mu)}^p\Bigr),\] which proves Theorem 3 for any \(q>1\).

5.4 Step 4: Deriving the probability estimate (22 )↩︎

We will apply the following simple lemma.

Now, if 19 holds for every \(q>1\), then, by the results of Subsection 5.3, we have \[\left( \mathbb{E}|\mathop{\mathrm{Er}}_p(F, \pmb{\xi})|^q \right)^{1/q} \leqslant\frac{C(p) q}{1+\log q}\,\Theta, \quad \forall\, q \geqslant 1,\] where \[\Theta := \Bigl({\frac{Hm_0}{m}}\Bigr)^{\frac{1}{p}} \Bigl(\log\log \frac{m}{m_0} + \log \frac{m}{Hm_0}\Bigr)^{1-\frac{1}{p_0}} \Bigl(1+\sup\limits_{f \in F} \|f\|_{L_p(\mu)}^p\Bigr).\] Applying Lemma 8 to the random variable \[Z = \frac{\mathop{\mathrm{Er}}_p(F,\pmb\xi)}{C(p)\Theta},\] we obtain the estimate \[\mathbb{P}\bigl[\mathop{\mathrm{Er}}_p(F,\pmb{\xi}) > C(p)\Theta\, t\bigr] \leqslant\exp\Bigl(-\frac{t \log t}{e}\Bigr), \quad \forall\, t \geqslant e.\]

6 Proofs of Theorems 7 and 1↩︎

Let \((\Omega,\mathcal{F}, \mu)\) be a probability space, and \(\pmb{\xi}:=(\xi^1,\ldots,\xi^m)\in\Omega^m\) be a collection of \(m\) independent random elements satisfying condition 7 . Let \(p \geqslant 2\), \(p_0\in(1, p]\), and \(p_1:=\frac{pp_0}{p-p_0}\). We begin with the following intermediate lemma, which allows us to pass from Theorem 3 to the statement of Theorem 7, and which will also be useful in the next section for obtaining results on universal discretization.

For the convenience of later applications, we record the following consequence of Lemma 9.

7 Proof of Theorem 2↩︎

In this section, we deduce Theorem 2 from Lemma 9. Before delving into the technical details, we outline the primary strategy of the proof. We define \[F:=\Sigma_s^p(\mathcal{D}_N):=\bigl\{f\in \Sigma_s(\mathcal{D}_N)\colon \|f\|_{L_p(\mu)}\leqslant 1\bigr\}.\] Then, observing that \(\mathop{\mathrm{Er}}_p(F,\pmb{\xi})= \mathop{\mathrm{Er}}_2(T_{p/2}(F),\pmb{\xi})\) for any \(\pmb\xi=(\xi^1,\cdots, \xi^m)\in \Omega^m\), we apply Lemma 9 with the parameter \(p=2\) to the modified function class \(T_{p/2}(F)\) rather than directly to \(F\). The proof of Theorem 2 proceeds in two stages.

First, in Subsection 7.1, we establish two technical lemmas. Lemma 10 will imply that for any \(1\leqslant p_0<2\), we have \[\begin{align} & \; {\gamma}_{2, p_0} (T_{p/2}(F), \|\cdot\|_{L_{p_1}(\pmb\xi)}) \leqslant C(p) \Bigl[ {\gamma}_{p, \frac{pp_0}{2}} (F, \|\cdot\|_{L_{q}(\pmb\xi)})\Bigr]^{\frac{p}{2} }, \end{align}\] where \(p_1:=\frac{2p_0}{2-p_0}\) and \(q:=\frac{pp_0}{2-p_0}\). Lemma 11 then provides bounds for the chaining functionals \({\gamma}_{p, \frac{pp_0}{2}} (F, \|\cdot\|_{L_{q}(\pmb\xi)})\) for any \(\pmb\xi=(\xi^1,\cdots, \xi^m)\in\Omega^m\). This bound constitutes the core technical component of the proof of Theorem 2.

Second, in Subsection 7.2, we use the estimates from Lemmas 10 and 11 to verify the conditions of Lemma 9 for the function class \(T_{p/2}(F)\) and the parameter \(p=2\). Applying Lemma 9 then allows us to estimate the probability \({\mathbb{P}}[ \mathop{\mathrm{Er}}_2(T_{p/2}(F),\pmb{\xi})>\varepsilon]\) for any \(\varepsilon\in (0, \frac{1}{2}]\), which concludes the proof of Theorem 2.

Throughout the remainder of this section, \((\Omega, \mathcal{F}, \mu)\) denotes our base probability space. Any supplementary probability measure \(\nu\) on \(\Omega\) is assumed to be defined on an extended \(\sigma\)-algebra \(\mathcal{F}_1\) containing \(\mathcal{F}\). Recall that we define \[\|f\|_\infty := \sup_{x\in\Omega} |f(x)| \quad \text{for all } f\in B(\Omega).\] In our applications, \(\nu\) will be a uniform probability measure supported on a finite sequence of points in \(\Omega\).

7.1 Technical lemmas↩︎

We start with the following simple observation for the \(\gamma\)-functionals.

The main technical component of the proof of Theorem 2 is contained in the following lemma.

7.2 Proof of Theorem 2↩︎

For simplicity, we again set \(F:=\Sigma_s^p(\mathcal{D}_N)\). Fix the random points \(\xi^1, \cdots, \xi^m\), and let \(\nu\) be the uniform distribution on the finite set \(\{\xi^1,\cdots, \xi^m\}\subset \Omega\). Applying Lemma 11 with \(\nu\), we find a number \(p_0=p_0(s, K) \in [\frac{3}{2}, 2)\) such that the following two inequalities hold for \(q:=\frac{pp_0}{2-p_0} \geqslant 3\): \[\label{7-18} \sup_{f\in F} \|f\|_\infty^{p-\frac{pp_0}{2}} \; \cdot\; \Bigl[ {\gamma}_{p, \frac{pp_0}{2}}(F, \|\cdot\|_{L_q(\pmb\xi)})\Bigr]^{\frac{pp_0}{2}} \leqslant C(p) \bigl( Ks \;\log s \;\log (Ks) \; \log N\bigr)^{\frac{p_0}{2}},\tag{81}\] \[\label{7-19} \sup_{f\in F} \|f\|_\infty^{p-\frac{pp_0}{2}} \; \cdot \;\sup_{g\in F} \|g\|_{L_q(\pmb\xi)}^{\frac{pp_0}{2}}\leqslant C(p) (Ks)^{\frac{p_0}{2}}.\tag{82}\]

We will apply Lemma 9 to the function class \(T_{p/2}(F)\) rather than to \(F\). To this end, we first note that \[\sup_{g\in T_{p/2}(F)}\|g\|_{L_2(\mu)}=\sup_{f\in F}\|f\|_{L_p(\mu)}^{\frac{p}{2}}\leqslant 1,\] and \[\mathop{\mathrm{Er}}_p(F,\pmb{\xi})= \mathop{\mathrm{Er}}_2(T_{p/2}(F),\pmb{\xi}).\] Second, invoking Lemma 10 with \(\lambda=\frac{p}{2}\), we obtain that for \(p_1:=\frac{2p_0}{2-p_0}\) and \(q:=\frac{pp_0}{2-p_0}\), \[\begin{align} &\sup_{g\in T_{p/2}(F)} \|g\|_\infty^{2-p_0}\cdot\Bigl[ {\gamma}_{2, p_0} (T_{p/2}(F), \|\cdot\|_{L_{p_1}(\pmb\xi)})\Bigr]^{p_0} \leqslant C_1(p) \sup_{f\in F} \|f\|_\infty^{p-\frac{pp_0}{2} }\cdot\Bigl[ {\gamma}_{p, \frac{pp_0}{2}} (F, \|\cdot\|_{L_{q}(\pmb\xi)})\Bigr]^{\frac{pp_0}{2} }, \end{align}\] which, using 81 , is estimated above by \[\leqslant C_2(p) \bigl( Ks \;\log s \;\log (Ks) \; \log N\bigr)^{\frac{p_0}{2}}.\] Finally, using 82 , we obtain \[\begin{align} \sup_{g\in T_{p/2}(F)} \|g\|_\infty^{2-p_0}\; \cdot \sup_{g\in T_{p/2}(F)} \|g\|_{L_{p_1}(\pmb\xi)}^{p_0}&= \sup_{f\in F} \|f\|_\infty^{p-\frac{pp_0}{2}} \; \cdot \;\sup_{g\in F} \|g\|_{L_q(\pmb\xi)}^{\frac{pp_0}{2}}\leqslant C(p) (Ks)^{\frac{p_0}{2}}. \end{align}\]

The above estimates show that Lemma 9 is applicable to the function class \(T_{p/2}(F)\) with the parameters \(p=2\), \(H=Ks\), \({\alpha}=0\) and \(m_0\sim \log s\, \log (Ks)\, \log N\). Recalling \(1<p_0<2\), we observe that \[H m_0 (\log\log H)^{2/p_0'} \leqslant C Ks \log s\, \log (Ks)\, \log N\, \log\log (Ks).\] Taking Remark 12 into account, we then obtain that for any \(\lambda \geqslant e\) and \(\varepsilon \in (0,\tfrac12]\), \[\begin{align} \mathbb{P}\bigl[\mathop{\mathrm{Er}}_p(F,\pmb{\xi})>\varepsilon\bigr]= \mathbb{P}\Bigl[\mathop{\mathrm{Er}}_2(T_{p/2}(F),\pmb{\xi})>\varepsilon\Bigr] \leqslant 2 \exp\bigl(-c(p)\lambda(\log\lambda)^{1/p_0}\bigr)\leqslant 2 \exp\bigl(-c(p)\lambda\sqrt{\log\lambda}\bigr) \end{align}\] provided that \[m \geqslant(\lambda\,\varepsilon^{-1})^2(\log \varepsilon^{-1})\, Ks\, \log N\, \log s \, \log(Ks)\, \log\log(Ks).\] This proves Theorem 2. 0◻

8 van Handel’s approach: the contraction principle and \(K\)-functionals↩︎

Talagrand’s generic chaining provides sharp estimates for the expected supremum of random processes in terms of chaining functionals (see, for instance, Theorem 9). In concrete applications, however, these functionals are often difficult to estimate directly. Van Handel [49], [50] developed a powerful approach to bounding them by combining a contraction principle with interpolation techniques based on \(K\)-functionals. In this section, we recall the main ingredients of this method and derive a finite-dimensional version of the contraction principle that is particularly convenient for our later applications.

We begin with van Handel’s contraction principle, which bounds chaining functionals in terms of suitable local entropy estimates. Throughout this section, unless stated otherwise, \(\mathbf{T}=(\mathbf{T},\varrho)\) denotes a metric space.

We will mostly work in a finite-dimensional setting, where \(\mathbf{T}\) is a subset of a finite-dimensional normed space \((X,\|\cdot\|)\) and \(\varrho\) is the metric induced by \(\|\cdot\|\). Combining Lemma 14 with Lemma 1, we obtain the following finite-dimensional version of Lemma 14, involving only finitely many functionals \(s_n\colon \mathbf{T}\to[0,\infty)\).

In applications of Lemma 14, the main difficulty is to construct, for a sufficiently small constant \(a>0\), a sequence of functionals \(s_n\colon\mathbf{T}\to[0,\infty)\) such that the entropy estimate 83 holds for every subset \(A\subset\mathbf{T}\), while the quantity \[\sup_{x\in\mathbf{T}}\sum_{n\geqslant 0}\bigl(2^{n/\alpha}s_n(x)\bigr)^\beta\] remains under control. Van Handel [49] proposed an elegant way to do this by means of interpolation \(K\)-functionals. We briefly recall this approach below, in a slightly generalized form. Since only the case \(\beta=1\) will be used later, we restrict ourselves to this case throughout the rest of the section.

By definition, it is clear that \[\label{3-3b} 0\leqslant K_n(x,t)\leqslant K_{n+1}(x, t)\leqslant u_{n+1}(x, 0)\leqslant u^\ast,\; \;\forall\, x\in \mathbf{T},\; \;\forall\, n\in \mathbb{N}_0.\tag{86}\] We will adhere to the notation and assumptions introduced in Definition 7 throughout the remainder of this section.

The next two lemmas record the basic properties of the quantities introduced in Definition 7. Since we will use them repeatedly, we include their proofs for completeness.

We now combine Lemma 15 with Lemmas 16 and 17 to derive an estimate for the chaining functional \(\gamma_{\alpha,1}\) in terms of the growth of the associated \(K\)-functionals in a finite-dimensional setting. This estimate will be the main tool in the next section.

In applications of Theorem 14, the parameters \(b_1,b_2,n_0\), and \(n_1\) must typically be optimized. By contrast, the parameter \(\ell\) is inessential, and the implicit constants are allowed to depend on it.

9 Proof of Theorem 4↩︎

In this section, we prove Theorem 4, which is restated below for convenience. Throughout the paper, \(\|\cdot\|_q\) denotes the norm \(\|\cdot\|_{\ell_q^m}\) for any \(1\leqslant q\leqslant\infty\).
Let \(2 \leqslant p < \infty\), \(p_0\in(1, p]\), and \(p_1:=\frac{pp_0}{p-p_0}\). Then there exists a constant \(C = C(p)>0\) such that for every nonempty set \(G \subset \mathbb{C}^m\) and any choice of parameters \(b > 0\), \(\alpha_0 \in (0,1)\), \(n_0 \in \mathbb{N}\) and \(m_0\in \mathbb{N}\cap [1, m)\), one has \[\begin{align} {\gamma}_{p,1}(T_p(G),\|\cdot\|_{p'}) &\leqslant C \Biggl[ \Bigl( b n_0 + b^2\cdot (\alpha_0)^{1/p} +\frac{\log \frac{m}{m_0}}{(2^{n_0}\alpha_0)^{1/p}} \Bigr) \sup_{x \in G} \|x\|_{p}^p} \\ &+ \sup_{x\in G}\|x\|_\infty^{p-p_0}\cdot \frac{m_0^{p_0/p}\bigl[\mathop{\mathrm{diam}}(G, \|\cdot\|_{p_1}) \bigr]^{p_0}+ \bigl[{\gamma}_{p,p_0}(G, \|\cdot\|_{p_1})\bigr]^{p_0}}{b^{p_0-1}} \Biggr].\nonumber \end{align}\]
By Remark 6, we only need to prove Theorem 4 for the real case \(G\subset\mathbb{R}^m\). The proof is based on Theorem 14, applied to the set \[\mathbf{T}:=T_p(G)=\{|g|^p\colon g\in G\},\] together with a suitable sequence of functionals \(\widetilde{s}_k:\mathbf{T}\to[0,\infty)\) constructed from an admissible sequence of partitions of \(G\). A central step is to verify a local entropy estimate of the form 92 for an appropriate increasing sequence of functionals \[u_n\colon\mathbf{T}\times[0,\infty)\to[0,\infty), \quad n\in\mathbb{N}_0.\] This requires two technical lemmas, Lemmas 19 and 20, presented in Subsection 9.1. We prove Lemma 19 in that subsection, but the proof of the more involved Lemma 20 is deferred to Subsection 9.3. Finally, the proof of Theorem 4 is completed in Subsection 9.2 using Lemma 20.

Throughout this section, we fix \(2\leqslant p<\infty\) and assume \(G\subset\mathbb{R}^m\) is a nonempty set satisfying \[\label{4-5-25} \sup_{g\in G}\|g\|_p^p=:u^\ast<\infty.\tag{97}\] Let \(\mathbf{T}:=T_p(G)\). For brevity, we also write \(q\) in place of \(p_0\).

For any index set \(I\subset\{1,2,\dots,m\}\), let \[\mathbb{R}^I:=\operatorname{span}\{e_j\colon j\in I\}\subset\mathbb{R}^m,\] and denote by \(R_I\colon \mathbb{R}^m\to\mathbb{R}^m\) the orthogonal projection onto \(\mathbb{R}^I\), given by \[R_Ix=\sum_{j\in I}x_je_j, \quad x=(x_1,\dots,x_m)\in\mathbb{R}^m.\] Denoting the complement of \(I\) by \(I^c:=\{1,2,\dots,m\}\setminus I,\) we define the threshold set for any \(\tau\geqslant 0\) and \(x\in \mathbb{R}^m\) as \[I^c(x;\tau):=\{j\in I^c\colon x(j)\geqslant\tau\}.\]

9.1 Key lemmas↩︎

We start with the following elementary inequality.

We now apply Lemma 18 to establish a key local entropy estimate, which provides control of the form 84 .

To prove Theorem 4, we will apply Theorem 14 with the parameter \({\alpha}=p\). The crucial part is to establish a local entropy number estimate of the form 92 . Lemma 19 provides the entropy estimate 101 , which can be rewritten as \[\begin{align} e_{n+\ell+1}(A, \|\cdot\|_{p'}) \leqslant 16 \cdot 2^{-2^{\ell}} \mathop{\mathrm{diam}}(A, \|\cdot\|_{p'}) + \sup_{x\in A} \widetilde{s}_{n}(x) + 8p \beta \cdot \min_{|I| \leqslant 2^n} S_{I^c}(A; \tau),\label{4-12-25} \end{align}\tag{107}\] where \(\widetilde{s}_n(x)=\widetilde{s}_{n,1}(x)+\widetilde{s}_{n,2}(x)\), \(\widetilde{s}_{n,1}(x):= 8\tau^{1/p} (u^\ast)^{1/p'}\) and \[\begin{align} \label{4-13b} \widetilde{s}_{n,2}(x):=8p \beta^{-(q-1)} \cdot \sup_{f\in G}\|f\|_\infty^{p-q} \cdot \left[ \mathop{\mathrm{diam}}\, (\mathcal{A}_{n+\ell}(g_x), \|\cdot\|_{\frac{pq}{p-q}})\right]^{q}. \end{align}\tag{108}\] For the term \(\widetilde{s}_{n,1}\), choosing \(\tau:=({\alpha}_0 2^{n+n_0-1}) ^{-1} u^\ast\) for some parameters \({\alpha}_0\in (0, 1)\) and \(n_0\in\mathbb{N}\), we obtain \[\sup_{x\in A}\sum_{n=n_1}^{\lceil\log_2 m\rceil} 2^{\frac{n}{p}} \widetilde{s}_{n,1}(x)=\frac{ 8u^\ast }{{\alpha}_0^{1/p} }\sum_{n= n_1}^{\lceil\log_2 m\rceil} 2^{-\frac{n_0-1}{p}}\leqslant\frac{C\cdot (\log_2 m - n_1) \cdot u^\ast}{ ( 2^{n_0}{\alpha}_0)^{1/p} },\label{4-13-25}\tag{109}\] for any \(n_1\in [1,\lceil \log_2 m\rceil]\cap \mathbb{N}\). For the term \(\widetilde{s}_{n,2}\), we may choose \(\beta=b 2^{-\frac{n}{p}}\) for some parameter \(b>0\), and optimize the admissible sequence so that \[\begin{align} \label{4-14-25} \sup_{x\in A}\sum_{n=0}^\infty 2^{\frac{n}{p}} \widetilde{s}_{n,2}(x) &= 8p b^{-(q-1)} \cdot \sup_{f\in G}\|f\|_\infty^{p-q} \sup_{x\in A}\sum_{n=0}^\infty \Bigl[ 2^{\frac{n}{p}}\mathop{\mathrm{diam}}\, (\mathcal{A}_{n+\ell}(g_x), \|\cdot\|_{\frac{pq}{p-q}})\Bigr]^{q}\\ &\leqslant 16 pb^{-(q-1)} \sup_{f\in G}\|f\|_\infty^{p-q} \Bigl[{\gamma}_{p, q} (G, \|\cdot\|_{\frac{pq}{p-q}})\Bigr]^{q}.\notag \end{align}\tag{110}\] The main difficulty comes from the term involving \(\min\limits_{|I| \leqslant 2^n} S_{I^c}(A; \tau)\). To establish a local entropy number bound of the form 92 , it is necessary to construct an increasing sequence of bounded nonnegative functions \(u_n\colon {\boldsymbol{T}}\times [0,\infty)\to [0,\infty)\), \(n\in \mathbb{N}_0\) satisfying the estimate 111 below. The existence of such a sequence is ensured by the following lemma.

The proof of Lemma 20 will be deferred to Subsection 9.3. For now, we accept it as given and proceed to the proof of Theorem 4 in the next subsection.

9.2 Proof of Theorem 4 (under the assumption of Lemma 20)↩︎

Let \(q:=p_0\in(1, p]\), \(b>0\), \({\alpha}_0\in (0, 1)\) and \(n_0, m_0\in\mathbb{N}\) be the parameters given in Theorem 4. Let \(\ell\in\mathbb{N}\) be a positive integer depending only on \(p\), to be specified later.

First, as we discussed above, we may apply Lemma 19 with the choices of parameters \[\alpha = p,\; \beta = 2^{-n/p} b, \; \;\text{and}\; \tau = (\alpha_0 2^{n+n_0-1})^{-1} u^\ast.\] This yields the entropy estimate 107 for every subset \(A \subset {\boldsymbol{T}}\).

Next, we invoke Lemma 20 to estimate the term \(\min\limits_{|I|\leqslant 2^n} S_{I^c} (A, \tau)\) in 107 . Specifically, substituting the bound from 111 into 107 , we obtain, for any \(a>0\), \[\begin{align} &e_{n+\ell+1} (A, \|\cdot\|_{p'})\leqslant 16\cdot 2^{-2^{\ell}} \cdot \mathop{\mathrm{diam}}(A, \|\cdot\|_{p'}) + \sup_{x\in A} \widetilde{s}_{n}(x)+\\ &+8p b\cdot (2^{n_0} {\alpha}_0)^{1/p} \cdot \sup_{x\in A}r_{n+n_0}^a(x)+\frac{8pb}{ 2^{n/p} }\cdot \sup_{x\in A} \Bigl[ u_{n+n_0} (x, r_{n+n_0}^a(x)) -u_n(x, r_A)\Bigr], \end{align}\] where \(\widetilde{s}_n=\widetilde{s}_{n,1}+\widetilde{s}_{n,2}\), as defined in 108 , and \[r_A= 2^{n_0/p}\sup_{x\in A} r_{n+n_0}^a (x) +\mathop{\mathrm{diam}}(A, \|\cdot\|_{p'}).\] We now specify the constants \(\ell\) and \(a\). Let \(C(p)>1\) denote the constant \(C({\alpha})\) from Theorem 14, evaluated at \({\alpha}=p\). Define \(a:=\frac{1}{ 32 p C(p) b}\), and choose \(\ell=\ell(p)\) to be the smallest positive integer such that \[16\cdot 2^{-2^{\ell}}\leqslant\frac{1}{4C(p)}.\] Invoking Theorem 14 with the parameters \[{\alpha}=p,\; \;b_1=8p b\cdot ({\alpha}_0)^{1/p}, \; \; b_2=8p b,\;\;\text{and}\; \; n_1=\lceil \log_2 m_0\rceil,\] we obtain \[{\gamma}_{p,1}(\mathbf{T}, \|\cdot\|_{p'}) \leqslant C_1(p) \Bigg[ \big(bn_0+b^2 ({\alpha}_0)^{1/p}\big)u^\ast+2^{n_1/p}\mathop{\mathrm{diam}}({\boldsymbol{T}},\|\cdot\|_{p'})+\sup_{x\in {\boldsymbol{T}}}\sum_{n=n_1}^{\lceil \log_2 m \rceil} 2^{n/p} \widetilde{s}_n(x)\Bigg].\]

To estimate the last term, we take the infimum over all admissible sequences \((\mathcal{A}_n)_{n\geqslant 0}\) of partitions of \(G\). Using the estimates 109 and 110 , and taking \(n_1= \lceil \log_2 m_0 \rceil\) we then obtain \[\begin{align} \sup_{x\in T}\sum_{n=n_1}^{\lceil \log_2 m \rceil} 2^{n/p} \widetilde{s}_n(x)\leqslant C_2(p)\Bigg[ \frac{ (\log_2 \frac{m}{m_0}) \cdot u^\ast}{ (2^{n_0}{\alpha}_0)^{1/p} } + \sup\limits_{f\in G}\|f\|_\infty^{p-q}\cdot \frac{ \Bigl[{\gamma}_{p, q} (G, \|\cdot\|_{\frac{pq}{p-q}})\Bigr]^q}{b^{q-1}}\Bigg]. \end{align}\]

We now estimate the diameter \(\mathop{\mathrm{diam}}({\boldsymbol{T}}, \|\cdot\|_{p'})\) of \({\boldsymbol{T}}=T_p(G)\) in the norm \(\|\cdot\|_{p'}\). For any \(f, g\in G\), we have \[\begin{align} \Bigl\||f|^p-|g|^{p}\Bigr\|_{p'}&\leqslant p \Bigl\| (|f|^{p-1}+|g|^{p-1})|f-g|\Bigr\|_{p'}\\ &\leqslant 2 p \|f-g\|_{\frac{pq}{p-q}}\cdot \sup_{h\in G}\|h\|_\infty^{\frac{p-q}{q}}\cdot (u^\ast)^{1/q'}. \end{align}\] Applying Young’s inequality, we then obtain, for all \(f, g\in G\), \[\Bigl\||f|^p-|g|^{p}\Bigr\|_{p'}\leqslant 2p bm_0^{-1/p}u^\ast +2p (bm_0^{-1/p})^{-(q-1)}\cdot \sup_{h\in G}\|h\|_\infty^{p-q}\cdot \|f-g\|_{\frac{pq}{p-q}}^q.\] Taking the supremum over all \(f, g\in G\), we conclude \[m_0^{1/p}\mathop{\mathrm{diam}}({\boldsymbol{T}},\|\cdot\|_{p'}) \leqslant 2p b u^\ast + 2pb^{-(q-1)}m_0^{q/p}\, \sup_{f\in G}\|f\|_\infty^{p-q} \cdot \bigl[\mathop{\mathrm{diam}}(G, \|\cdot\|_{\frac{pq}{p-q}}) \bigr]^q.\] Finally, combining all of the above estimates, we obtain the desired bound: \[\begin{align} {\gamma}_{p,1}(\mathbf{T}, \|\cdot\|_{p'})\leqslant& C_3(p) \Biggl[ \left( bn_0+b^2 \cdot ({\alpha}_0)^{1/p} +\frac{ \log_2 \frac{m}{m_0}}{ (2^{n_0}{\alpha}_0)^{1/p}} \right)u^\ast \\ &+ \sup_{f\in G}\|f\|_\infty^{p-q}\cdot \frac{m_0^{q/p}\bigl[\mathop{\mathrm{diam}}(G, \|\cdot\|_{\frac{pq}{p-q}}) \bigr]^q+ \bigl[{\gamma}_{p,q}(G, \|\cdot\|_{\frac{pq}{p-q}})\bigr]^q}{b^{q-1}}\Biggr]. \end{align}\] Theorem 4 is now proved up to Lemma 20. 0◻

9.3 Proof of Lemma 20↩︎

We consider the metric space \({\boldsymbol{T}}=(\mathbf{T}, \|\cdot\|_{p'})\), where \[{\boldsymbol{T}}=T_p(G)=\{|f|^p\colon f\in G\}.\] Recall that \[u^\ast=\sup_{g\in G}\|g\|_p^p=\sup_{x\in {\boldsymbol{T}}}\|x\|_1<\infty.\] For \(x\in {\boldsymbol{T}}\) and \(r\geqslant 0\), let \(B_{\boldsymbol{T}}(x,r):=\{y\in {\boldsymbol{T}}\colon \|x-y\|_{p'}\leqslant r\}\). We need to estimate the quantity \[{\min_{|I|\leqslant{\alpha}_n} S_{I^c} (A, \tau),}\] where \[S_{I^c} (A, \tau) = \sup_{x\in A} \sum_{j\in I^c(x;\tau)} \; x(j).\] Throughout the proof, the letters \(I, J\) always denote subsets of \(\{1,2,\dots, m\}\).

We temporarily fix an index set \(I\subset \{1,2,\cdots, m\}\) with \(|I|\leqslant{\alpha}_n\). For any \(x\in \mathbf{T}\), we have \[|I^c(x;\tau)|\leqslant\frac{\|x\|_1}{\tau}\leqslant{\alpha}_{n+n_0-1}.\] Consequently, \[\begin{align} S_{I^c} (A, \tau) &= \sup_{x\in A} \|R_{I^c(x;\tau)} x\|_1 \leqslant\sup_{x\in A} \max_{\substack{J:\;I\cap J=\emptyset\\ |J|\leqslant{\alpha}_{n+n_0-1}}} \|R_J x\|_1. \end{align}\]

Let \(s\colon {\boldsymbol{T}}\to [0,\infty)\) be any nonnegative function. If \(x\in {\boldsymbol{T}}\), \(y\in B_{\boldsymbol{T}}(x, s(x))\) and \(|J|\leqslant{\alpha}_{n+n_0-1}\), then \[\begin{align} \Bigl| \|R_J x\|_1-\|R_J y\|_1\Bigr|\leqslant\bigl\|R_J (x-y)\bigr\|_1 \leqslant|J|^{\frac{1}{p}} \|x-y\|_{p'}\leqslant s(x) \cdot ({\alpha}_{n+n_0-1})^{\frac{1}{p}}, \end{align}\] which implies \[\|R_J x\|_1 \leqslant({\alpha}_{n+n_0-1})^{\frac{1}{p}}\cdot s(x)+\inf_{y\in B_{\boldsymbol{T}}(x, s(x))} \|R_J y\|_1.\] Hence, \[S_{I^c} (A, \tau) \leqslant S_1(I; A, \tau)+ ({\alpha}_{n+n_0-1})^{1/p} \sup_{x\in A} s(x),\label{4-17-25}\tag{112}\] where \[S_1(I; A, \tau):= \sup_{x\in A} \max_{\substack{J:\;I\cap J=\emptyset\\ |J|\leqslant{\alpha}_{n+n_0-1}}} \inf_{y\in B_{\boldsymbol{T}}(x, s(x))}\|R_J y\|_1.\] Observe that \[\begin{align} &\sup_{x\in A} \max_{\substack{J:\; I\cap J=\emptyset\\ |J|\leqslant{\alpha}_{n+n_0-1}}}\Bigg[ \inf_{y\in B_{\boldsymbol{T}}(x, s(x))}\|R_J y\|_1+ \inf_{y\in B_{\boldsymbol{T}}(x, s(x))}\|R_I y\|_1\Bigg]\\ &\leqslant\sup_{x\in A} \max_{\substack{J: \;I\cap J=\emptyset\\ |J|\leqslant{\alpha}_{n+n_0-1}}} \inf_{y\in B_{\boldsymbol{T}}(x, s(x))}\|R_{I\cup J} y\|_1\leqslant \sup_{x\in A} \max_{|J|\leqslant{\alpha}_{n+n_0}} \inf_{y\in B_{\boldsymbol{T}}(x, s(x))}\|R_{J} y\|_1, \end{align}\] where the last step uses the inequality \({\alpha}_{n+n_0-1}+{\alpha}_n\leqslant{\alpha}_{n+n_0}\). For any \(x, z\in A\), we have \[B_{\boldsymbol{T}} (x, s(x))\subset B_{\boldsymbol{T}} (z, s_A),\; \;\text{where}\; \;s_A:= \sup_{z\in A} s(z) + \mathop{\mathrm{diam}}(A, \|\cdot\|_{p'}),\] implying \[\begin{align} \inf_{y\in B_{\boldsymbol{T}}(x, s(x))}\|R_I y\|_1\geqslant\sup_{z\in A} \inf_{y\in B_{\boldsymbol{T}}(z, s_A)}\|R_I y\|_1,\; \;\forall\, x\in A. \end{align}\] It follows that \[\begin{align} &S_1(I; A, \tau)+ { \sup_{z\in A} \inf_{y\in B_{\boldsymbol{T}}(z, s_A)} }\|R_I y\|_1\leqslant \sup_{x\in A} \max_{|J|\leqslant{\alpha}_{n+n_0}} \inf_{y\in B_{\boldsymbol{T}}(x, s(x))}\|R_{J} y\|_1. \end{align}\] This combined with 112 yields \[\begin{align} & S_{I^c} (A, \tau)+ \sup_{x\in A} \inf_{y\in B_{\boldsymbol{T}}(x, s_A)}\|R_I y\|_1\\ &\leqslant\sup_{x\in A} \max_{|J|\leqslant{\alpha}_{n+n_0}} \inf_{y\in B_{\boldsymbol{T}}(x, s(x))}\|R_{J} y\|_1+ ({\alpha}_{n+n_0-1})^{1/p} \sup_{x\in A} s(x). \end{align}\] Taking the maximum over all \(I\subset \{1,2,\cdots, m\}\) with \(|I|\leqslant{\alpha}_n\), we obtain \[\begin{align} &\min_{|I|\leqslant{\alpha}_n} S_{I^c} (A, \tau)+ \sup_{x\in A} \max_{|I|\leqslant{\alpha}_n} \inf_{y\in B_{\boldsymbol{T}}(x, s_A)}\|R_I y\|_1\notag\\ &\leqslant\max_{|I|\leqslant{\alpha}_n}\Bigg[S_{I^c} (A, \tau)+ \sup_{x\in A} \inf_{y\in B_{\boldsymbol{T}}(x, s_A)}\|R_I y\|_1\Bigg]\notag\\ &\leqslant\sup_{x\in A} \max_{|I|\leqslant{\alpha}_{n+n_0}} \inf_{y\in B_{\boldsymbol{T}}(x, s(x))}\|R_{I} y\|_1+ ({\alpha}_{n+n_0-1})^{1/p} \sup_{x\in A} s(x). \end{align}\] Thus, it follows that \[\begin{align} \label{9-18} &\min_{|I|\leqslant{\alpha}_n} S_{I^c} (A, \tau)- ({\alpha}_{n+n_0-1})^{1/p} \sup_{x\in A} s(x) \\ &\leqslant\Bigg[\sup_{x\in A} \max_{|I|\leqslant{\alpha}_{n+n_0}} \inf_{y\in B_{\boldsymbol{T}}(x, s(x))}\|R_{I} y\|_1- \sup_{x\in A} \max_{|I|\leqslant{\alpha}_n} \inf_{y\in B_{\boldsymbol{T}}(x, s_A)}\|R_I y\|_1\Bigg]\notag\\ &\leqslant\sup_{x\in A}\Bigg[ \max_{|I|\leqslant{\alpha}_{n+n_0}} \inf_{y\in B_{\boldsymbol{T}}(x, s(x))}\|R_{I} y\|_1- \max_{|I|\leqslant{\alpha}_n} \inf_{y\in B_{\boldsymbol{T}}(x, s_A)}\|R_I y\|_1\Bigg]. \notag \end{align}\tag{113}\]

Now we define a sequence of functionals \(u_n\colon {\boldsymbol{T}}\times [0,\infty)\to [0,\infty)\), \(n\in \mathbb{N}_0\) as follows: \[u_n(x,r)=\max_{|I|\leqslant{\alpha}_n} \inf_{y\in B_{\boldsymbol{T}}(x,r)} \|R_I y\|_1,\quad x\in \mathbf{T},\;\;r\geqslant 0.\] By definition, the sequence \((u_n(x, r))_{n\geqslant 0}\) is decreasing in \(r\) and satisfies \[0\leqslant u_n(x,r)\leqslant u_{n+1}(x,r)\leqslant u^\ast \; \;\text{for allx\in \mathbf{T} and r\geqslant 0.}\] Furthermore, we can rewrite 113 equivalently in the form: \[\min_{|I|\leqslant{\alpha}_n} S_{I^c} (A, \tau)\leqslant\sup_{x\in A} \Bigl[ u_{n+n_0} (x, s(x))-u_n(x, s_A)\Bigr]+({\alpha}_{n+n_0-1})^{1/p} \sup_{x\in A} s(x).\] To complete the proof, we set \(s(x):=r_{n+n_0}^a(x)\), and observe that \[s_A:= \sup_{z\in A} s(z) + \mathop{\mathrm{diam}}(A, \|\cdot\|_{p'})\leqslant r_A:= 2^{n_0/p}\sup_{x\in A} r_{n+n_0}^a (x) +\mathop{\mathrm{diam}}(A, \|\cdot\|_{p'}).\] Since the function \(u_n(x, \cdot)\) is decreasing, we prove the growth condition 111 for all \(a>0\). 0◻

References↩︎