Covering Numbers for Convex Functions

I Introduction

Ever since the work of , covering numbers (and their logarithms, known as metric entropy numbers) have been studied extensively in a variety of disciplines. For a subset ${\cal F}$ of a metric space $({\mathcal{X}},\rho)$, the $\epsilon$-covering number $M({\cal F},\epsilon;\rho)$ is defined as the smallest number of balls of radius $\epsilon$ whose union contains ${\cal F}$. Covering numbers capture the size of the underlying metric space and play a central role in a number of areas in information theory and statistics, including nonparametric function estimation, density estimation, empirical processes and machine learning.

In recent years there has been an upsurge of interest in nonparametric function estimation under convexity based constraints, especially in multi-dimension. In general function estimation, it is well-known (see e.g., ) that the covering numbers of the underlying function space can be used to characterize optimal rates of convergence. They are also useful for studying the rates of convergence of empirical minimization procedures (see e.g., ). Our results have direct implications in this regard in the context of understanding the rates of convergence of the numerous convexity constrained function estimators, e.g., the nonparametric least squares estimator of a convex regression function studied in ; the maximum likelihood estimator of a log-concave density in multi-dimension studied in . Also, similar problems that crucially use convexity/concavity constraints to estimate sets have also received recent attention in the statistical and machine learning literature, see e.g., , and our results can be applied in such settings.

The paper is organized as follows. In Section II, we set up notation and provide motivation for our main results, which are proved in Section III. In Section IV, we draw some connections to previous results on covering numbers for convex functions and prove a related auxiliary result along with some inequalities of possible independent interest.

II Motivation

Bronshtein worked with the class ${\mathcal{C}}([a,b]^{d},B,\Gamma)$ where the functions are uniformly Lipschitz with constant $\Gamma$. However, in convexity-based function estimation problems, one usually does not have a known uniform Lipschitz bound on the unknown function class. This leads to difficulties in the analysis of empirical minimization procedures via Bronshtein’s result. To the best of our knowledge, there does not exist any other result on the covering numbers of convex functions that deals with all $d\geq 1$ and does not require the Lipschitz constraint.

In the absence of the uniformly Lipschitz constraint (i.e., if one works with the class ${\mathcal{C}}([a,b]^{d},B)$ instead of ${\mathcal{C}}([a,b]^{d},B,\Gamma)$), the covering numbers under the $L_{\infty}$ metric are infinite. In other words, the space ${\mathcal{C}}([a,b]^{d},B)$ is not totally bounded under the $L_{\infty}$ metric. This can be seen, for example, by noting that the functions

are in ${\mathcal{C}}(,1)$, for all $j\geq 1$, and satisfy

This motivated us to study the covering numbers of the class ${\mathcal{C}}([a,b]^{d},B)$ under a different metric, namely the $L_{p}$-metric for $1\leq p<\infty$. We recall that under the $L_{p}$-metric, $1\leq p<\infty$, the distance between two functions $f$ and $g$ on $[a,b]^{d}$ is defined as

Our main result in this paper shows that if one works with the $L_{p}$-metric as opposed to $L_{\infty}$, then the covering numbers of ${\mathcal{C}}([a,b]^{d},B)$ are finite. Moreover, they are bounded from above and below by constant multiples of $\epsilon^{-d/2}$ for sufficiently small $\epsilon$.

where $\epsilon^{\prime}:=(b-a)^{-d/p}\epsilon/B$.

Fix $1\leq p<\infty$. There exist positive constants $c$ and $\epsilon_{0}$, depending only on the dimension $d$ and $p$, such that, for every $B>0$ and $b>a$, we have

for every $\epsilon\leq\epsilon_{0}B(b-a)^{d/p}$.

The main ingredient in our proof of the above theorem is an extension of Bronshtein’s theorem to uniformly bounded convex functions having different Lipschitz constraints in different directions. Specifically, for $B\in(0,\infty)$, $\Gamma_{i}\in(0,\infty]$ and $a_{i}<b_{i}$ for $i=1,\dots,d$, let ${\mathcal{C}}\left(\prod_{i=1}^{d}[a_{i},b_{i}];B;\Gamma_{1},\dots,\Gamma_{d}\right)$ denote the set of all real-valued convex functions $f$ on the rectangle $[a_{1},b_{1}]\times\dots\times[a_{d},b_{d}]$ that are uniformly bounded by $B$ and satisfy:

for every $i=1,\dots,d$; $x_{i},y_{i}\in[a_{i},b_{i}]$ and $x_{j}\in[a_{j},b_{j}]$ for $j\neq i$. In other words, the function $x\mapsto f(x_{1},\dots,x_{i-1},x,x_{i+1},\dots,x_{d})$ is Lipschitz on $[a_{i},b_{i}]$ with constant $\Gamma_{i}$ for all $x_{j}\in[a_{j},b_{j}],j\neq i$.

Clearly, the class ${\mathcal{C}}([a,b]^{d},B,\Gamma)$ that Bronshtein studied is contained in ${\mathcal{C}}([a,b]^{d};B;\Gamma,\dots,\Gamma)$. Also, it is easy to check that every function $f$ in ${\mathcal{C}}\left(\prod_{i}[a_{i},b_{i}];B;\Gamma_{1},\dots,\Gamma_{d}\right)$ is Lipschitz with respect to the Euclidean norm on $\prod_{i}[a_{i},b_{i}]$ with Lipschitz constant $\sqrt{\Gamma_{1}^{2}+\dots+\Gamma_{d}^{2}}$.

Note that for $\Gamma_{i}=\infty$, the inequality (III-A) is satisfied by every function $f$. As a result, we have the equality ${\mathcal{C}}([a,b]^{d},B)={\mathcal{C}}([a,b]^{d};B;\infty,\dots,\infty)$. The following result gives an upper bound for the $\epsilon$-covering number of ${\mathcal{C}}(\prod_{i}[a_{i},b_{i}];B;\Gamma_{1},\dots,\Gamma_{d})$ and is the main ingredient in the proof of Theorem III.1. Its proof is similar to Bronshtein’s proof [3, Proof of Theorem 6] of his upper bound on ${\mathcal{C}}([a,b]^{d},B,\Gamma)$ and is included in Section IV.

There exist positive constants $c$ and $\epsilon_{0}$, depending only on the dimension $d$, such that for every positive $B,\Gamma_{1},\dots,\Gamma_{d}$ and rectangle $[a_{1},b_{1}]\times\dots\times[a_{d},b_{d}]$, we have

for all $0<\epsilon\leq\epsilon_{0}\{B+\sum_{i=1}^{d}\Gamma_{i}(b_{i}-a_{i})\}$.

Note that the right hand side of (III.2) equals $\infty$ unless $\Gamma_{i}<\infty$ for all $i=1,\dots,d$. Thus, Theorem III.2 is only meaningful when $\Gamma_{i}<\infty$ for all $i=1,\dots,d$.

Because ${\mathcal{C}}([a,b]^{d},B,\Gamma)$ is contained in ${\mathcal{C}}([a,b]^{d};B;\Gamma_{1},\dots,\Gamma_{d})$, Theorem III.2 includes Bronshtein’s upper bound on ${\mathcal{C}}([a,b]^{d},B,\Gamma)$ as a special case. Moreover, it gives explicit dependence of the upper bound on the constants $a,b,B$ and $\Gamma$. Bronshtein did not state the dependence on these constants.

We are now ready to prove Theorem III.1 using Theorem III.2. Here is the intuition behind the proof. The class ${\mathcal{C}}([a,b]^{d},B)$ can be thought of as an expansion of the class ${\mathcal{C}}([a,b]^{d};B;\Gamma_{1},\dots,\Gamma_{d})$ formed by the removal of the $d$ Lipschitz constraints $\Gamma_{1},\dots,\Gamma_{d}$ (or equivalently, by setting $\Gamma_{1}=\dots=\Gamma_{d}=\infty$). Instead of removing all these $d$ Lipschitz constraints at the same time, we remove them sequentially one at a time. This is formally accomplished by induction on the number of indices $i$ for which $\Gamma_{i}=\infty$. Each step of the induction argument focuses on the removal of one finite $\Gamma_{i}$ and is thus like solving the one-dimensional problem. We consequently use Dryanov’s ideas from [2, Theorem 3.1] to solve this quasi one-dimensional problem which allows us to complete the induction step.

The scaling identity (1) lets us take $a=0,b=1$ and $B=1$.

We shall prove that there exist positive constants $c$ and $\epsilon_{0}$, depending only on $d$ and $p$, such that for every $\Gamma_{i}\in(0,\infty]$, we have

for $0<\epsilon\leq\epsilon_{0}$. Note that this proves the theorem because we can set $\Gamma_{i}=\infty$ for all $i=1,\dots,d$. Our proof will involve induction on $l$: the number of indices $i$ for which $\Gamma_{i}=\infty$.

For $l=0$, i.e., when $\Gamma_{i}<\infty$ for all $i=1,\dots,d$, (III-A) is a direct consequence of Theorem III.2. In fact, in this case, (III-A) also holds for $p=\infty$. Suppose now that (III-A) holds for all $l<k$ for some $k\in\{1,\dots,d\}$. We shall then verify it for $l=k$. Fix $\Gamma_{i}\in(0,\infty]$ such that exactly $k$ of them equal infinity. Without loss of generality, we assume that $\Gamma_{1}=\dots=\Gamma_{k}=\infty$ and $\Gamma_{i}<\infty$ for $i>k$. For every sufficiently small $\epsilon>0$, we shall exhibit an $\epsilon$-cover of ${\mathcal{C}}(^{d};1;\infty,\dots,\infty,\Gamma_{k+1},\dots,\Gamma_{d})$ in the $L_{p}$-metric whose cardinality has logarithm bounded from above by a constant multiple of $(\sum_{i>k}\Gamma_{i}+2)^{d/2}\epsilon^{-d/2}$. Note that for $k=d$, the term $\sum_{i>k}\Gamma_{i}$ equals zero. For convenience, let us denote the class ${\mathcal{C}}(^{d};1;\infty,\dots,\infty,\Gamma_{k+1},\dots,\Gamma_{d})$ by ${\mathcal{G}}$ in the rest of this proof.

Fix $\eta>0$ and choose an integer $A$ and $\delta_{1},\dots,\delta_{A+1}$ such that

For every two functions $f$ and $g$ on $^{d}$, we can obviously decompose the integral $\int|f-g|^{p}$ as

For a fixed $m=1,\dots,A$, consider the problem of covering the functions in ${\mathcal{G}}$ on the rectangular strip $[\delta_{m},\delta_{m+1}]\times^{d-1}$. Clearly,

where, for $x=(x_{1},\dots,x_{d})\in^{d}$,

By convexity, the restriction of every function $f$ in ${\mathcal{G}}$ to $[\delta_{m},\delta_{m+1}]\times^{d-1}$ belongs to the class:

Because $2(\delta_{m+1}-\delta_{m})/\delta_{m}<\infty$, we can use the induction hypothesis to assert the existence of positive constants $\epsilon_{0}$ and $c$, depending only on $d$ and $p$, such that for every positive real number $\alpha_{m}\leq\epsilon_{0}$, there exists an $\alpha_{m}$-cover of ${\mathcal{C}}(^{d};1;2(\delta_{m+1}-\delta_{m})/\delta_{m},\infty,\dots,\infty,\Gamma_{k+1},\ldots,\Gamma_{d}))$ in the $L_{p}$-metric on $^{d}$ of size smaller than

By covering the functions in ${\mathcal{G}}$ by the constant function 0 on $[0,\delta_{1}]\times^{d-1}$ and up to $\alpha_{m}$ in the $L_{p}$-metric on $[\delta_{m},\delta_{m+1}]\times^{d-1}$ for $m=1,\dots,A$, we obtain a cover of the restriction of the functions in ${\mathcal{G}}$ to the set $[0,u]\times^{d-1}$ in $L_{p}$-metric having coverage $S_{1}^{1/p}$ and cardinality bounded from above by $\exp(S_{2})$ where

for $m=1,\dots,A+1$, where $A$ is the largest integer such that

Note that if $\eta\leq 1$, then $\log\eta\leq 0$ which implies $\zeta_{m}\leq 1$. Also, for $m=2,\dots,A$, we have

where we have used $\delta_{A}<u$ and the fact that $u$ has the expression (5). Therefore $\zeta_{m}\geq 2\zeta_{m-1}$ which can be rewritten as

Using this for $r=2$ and $r=d$, we deduce that

An exactly similar analysis can be done now to cover the restrictions of the functions in ${\mathcal{G}}$ to the set $[v,1]\times^{d-1}$ having the same coverage $S_{1}^{1/p}$ and same cardinality bounded by $\exp(S_{2})$. For $[u,v]\times^{d-1}$, we note, by convexity, that the restrictions of functions in ${\mathcal{G}}$ to the set $[u,v]\times^{d-1}$ belong to ${\mathcal{C}}([u,v]\times^{d-1};1;2/u,\infty,\dots,\infty,\Gamma_{k+1},\dots,\Gamma_{d})$. By the induction hypothesis, there exist constants $c$ and $\epsilon_{0}$, depending only on $d$ and $p$, such that for all $\eta\leq\epsilon_{0}$, one can get a $\epsilon$-cover of ${\mathcal{C}}([u,v]\times^{d-1};1;2/u,\infty,\dots,\infty,\Gamma_{k+1},\dots,\Gamma_{d})$ in the $L_{p}$-metric having cardinality smaller than

Observe that $u$ only depends on $p$. By combining the covers of the restrictions of functions in ${\mathcal{G}}$ to these three strips $[0,u]\times^{d-1}$, $[u,v]\times^{d-1}$ and $[v,1]\times^{d-1}$, we obtain, for $\eta\leq\epsilon_{0}$, a cover of ${\mathcal{G}}$ in the $L_{p}$-metric having coverage at most

By relabelling $(17/3)^{1/p}\eta$ as $\epsilon$, we have proved that for $\epsilon\leq(3/17)^{1/p}\epsilon_{0}$,

This proves (III-A) for all $\Gamma_{1},\dots,\Gamma_{d}$ such that exactly $k$ of them equal $\infty$. The proof is complete by induction. ∎

The argument used in the induction step above involved splitting the interval $$into the three intervals$[0,u],[u,v]$and$[v,1]$, and then subsequently splitting the interval$[0,u]$into smaller subintervals. We have borrowed this idea from Dryanov [2, Proof of Theorem 3.1]. We must mention however that Dryanov uses a more elaborate argument to bound sums of the form$S_{1}$and$S_{2}$. Our way of controlling$S_{1}$and$S_{2}$ is much simpler which shortens the argument considerably.

There exist positive constants $c$ and $\epsilon_{0}$, depending only on the dimension $d$, such that for every $p\geq 1$, $B>0$ and $b>a$, we have

for $\epsilon\leq\epsilon_{0}B(b-a)^{d/p}$.

As before, by the scaling identity (1), we take $a=0$, $b=1$ and $B=1$. For functions defined on $^{d}$, the $L_{p}$-metric, $p>1$, is larger than $L_{1}$. We will thus take $p=1$ in the rest of this proof. We prove that for $\epsilon$ sufficiently small, there exists an $\epsilon$-packing subset of ${\mathcal{C}}(^{d},1)$, under the $L_{1}$-metric, of cardinality larger than a constant multiple of $\epsilon^{-d/2}$. By a packing subset of ${\mathcal{C}}(^{d},1)$, we mean a subset $F$ satisfying $||f-g||_{1}\geq\epsilon$ whenever $f,g\in F$ with $f\neq g$.

Fix $0<\eta\leq 4(2+\sqrt{d-1})^{-2}$ and let $k:=k(\eta)$ be the positive integer satisfying

Consider the intervals $I(i)=[u(i),v(i)]$ for $i=1,\dots,k$, such that

$0\leq u(1)<v(1)\leq u(2)<v(2)\leq\dots\leq u(k)<v(k)\leq 1$,

$v(i)-u(i)=\sqrt{\eta}$, for $i=1,\dots,k$,

$u(i+1)-v(i)=\frac{1}{2}\sqrt{\eta(d-1)}$ for $i=1,\dots,k-1$.

Let ${\mathcal{S}}$ denote the set of all $d$-dimensional cubes of the form $I(i_{1})\times\dots\times I(i_{d})$ where $i_{1},\dots,i_{d}\in\{1,\dots,k\}$. The cardinality of ${\mathcal{S}}$, denoted by $|{\mathcal{S}}|$, is clearly $k^{d}$.

where $f_{0}(x):=\frac{1}{d}\left(x_{1}^{2}+\dots+x_{d}^{2}\right)$, for $x\in^{d}$. The functions $h_{S},S\in{\mathcal{S}}$ have the following four key properties:

For every $x\in^{d}$, we have $h_{S}(x)\leq h_{S}(1,\dots,1)\leq 1$.

For every $x\in S$, we have $h_{S}(x)\geq f_{0}(x)$. This is because whenever $x\in S$, we have $u(i_{j})\leq x_{j}\leq v(i_{j})$ for each $j$, which implies $\{x_{j}-u(i_{j})\}\{v(i_{j})-x_{j}\}\geq 0$.

Let $S,S^{\prime}\in{\mathcal{S}}$ with $S\neq S^{\prime}$. For every $x\in S^{\prime}$, we have $h_{S}(x)\leq f_{0}(x)$. To see this, let $S^{\prime}=I(i^{\prime}_{1})\times\dots\times I(i^{\prime}_{d})$ with $I(i^{\prime}_{j})=[u(i^{\prime}_{j}),v(i^{\prime}_{j})]$. Let $x\in S^{\prime}$ and fix $1\leq j\leq d$. If $I(i_{j})=I(i_{j}^{\prime})$, then $x_{j}\in I(i_{j})=[u(i_{j}),v(i_{j})]$ and hence

If $I(i_{j})\neq I(i_{j}^{\prime})$ and $u(i^{\prime}_{j})<v(i^{\prime}_{j})<u(i_{j})<v(i_{j})$, then

The same above bound holds if $u(i_{j})<v(i_{j})<u(i^{\prime}_{j})<v(i^{\prime}_{j})$. Because $S\neq S^{\prime}$, at least one of $i_{j}$ and $i^{\prime}_{j}$ will be different. Consequently,

Let $\{0,1\}^{{\mathcal{S}}}$ denote the collection of all $\{0,1\}$-valued functions on ${\mathcal{S}}$. The cardinality of $\{0,1\}^{{\mathcal{S}}}$ clearly equals $2^{|{\mathcal{S}}|}$ (recall that $|{\mathcal{S}}|=k^{d}$).

For each $\theta\in\{0,1\}^{{\mathcal{S}}}$, let

The first two properties of $h_{S},S\in{\mathcal{S}}$ ensure that $g_{\theta}\in{\mathcal{C}}(^{d},1)$. The last two properties imply that

We now bound from below the $L_{1}$ distance between $g_{\theta}$ and $g_{\theta^{\prime}}$ for $\theta,\theta\in\{0,1\}^{{\mathcal{S}}}$. Because the interiors of the cubes in ${\mathcal{S}}$ are all disjoint, we can write

Note that from (9) and by symmetry, the value of integral

is the same for all $S\in{\mathcal{S}}$. We have thus shown that

where ${\Upsilon}(\theta,\theta^{\prime}):=\sum_{S\in{\mathcal{S}}}\left\{\theta(S)\neq\theta^{\prime}(S)\right\}$ denotes the Hamming distance.

The quantity $\zeta$ can be computed in the following way. Let $S=I(i_{1})\times\dots\times I(i_{d})$ where $I(i_{j})=[u(i_{j}),v(i_{j})]$. We write

By the change of variable $y_{j}=\{x_{j}-u(i_{j})\}/\{v(i_{j})-u(i_{j})\}$ for $j=1,\dots,d$, we get

Recalling that $v(i)-u(i)=\sqrt{\eta}$ for all $i=1,\dots,k$, we get $\zeta=\eta^{d/2}\eta\gamma_{d}$ where

Note that $\gamma_{d}$ is a constant that depends on the dimension $d$ alone. Thus, from (10), we deduce

for all $\theta,\theta^{\prime}\in\{0,1\}^{{\mathcal{S}}}$. We now use the Varshamov-Gilbert lemma (see e.g., [18, Lemma 4.7]) which asserts the existence of a subset $W$ of $\{0,1\}^{{\mathcal{S}}}$ with cardinality, $|W|\geq\exp(|{\mathcal{S}}|/8)$ such that ${\Upsilon}(\tau,\tau^{\prime})\geq|{\mathcal{S}}|/4$ for all $\tau,\tau^{\prime}\in W$ with $\tau\neq\tau^{\prime}$. Thus, from (11) and (8), we get that for every $\tau,\tau^{\prime}\in W$ with $\tau\neq\tau^{\prime}$,

where $c_{1}:=\frac{\gamma_{d}}{4}(2+\sqrt{d-1})^{-d}$. Taking $\epsilon:=c_{1}\eta$, we have obtained for $\epsilon\leq\epsilon_{0}:=4c_{1}(2+\sqrt{d-1})^{-2}$, an $\epsilon$-packing subset of ${\mathcal{C}}(^{d},1)$ of size $M:=|W|$ where

where $c$ depends only on the dimension $d$. This completes the proof. ∎

The explicit packing subset constructed in the above proof consists of functions that can be viewed as perturbations of the quadratic function $f_{0}$. Previous lower bounds on the covering numbers of convex functions in [3, Proof of Theorem 6] and [2, Section 2] (for $d=1$) are based on perturbations of a function whose graph is a subset of a sphere; a more complicated convex function than $f_{0}$. The perturbations of $f_{0}$ in the above proof can also be used to simplify the lower bound arguments in those papers.

IV Distances between convex functions, and their epigraphs

One of the aims of this section is to provide the proof of Theorem III.2. Our strategy for the proof of Theorem III.2 is similar to Bronshtein’s proof of the upper bound on $M({\mathcal{C}}([a,b]^{d},B,\Gamma),\epsilon;L_{\infty})$. The proof involves the following ingredients:

An inequality between the $L_{\infty}$ distance between two convex functions and the Hausdorff distance between their epigraphs.

The result of Bronshtein for the covering numbers of convex sets in the Hausdorff metric.

For a convex function $f$ on $^{d}$ and $B>0$, let us define the epigraph $V_{f}(B)$ of $f$ by

If $f\in{\mathcal{C}}(^{d},B)$, then clearly

for every $(x_{1},\dots,x_{d+1})\in V_{f}(B)$. Therefore, for every $f\in{\mathcal{C}}(^{d},B)$, its epigraph $V_{f}(B)$ is contained in the $(d+1)$-dimensional ball of radius $\sqrt{d+B^{2}}$ centered at the origin. The following inequality relates the $L_{\infty}$ distance between two functions in ${\mathcal{C}}(^{d};B;\Gamma_{1},\dots,\Gamma_{d})$ to the Hausdorff distance between their epigraphs. The Hausdorff distance between two compact, convex sets $C$ and $D$ in Euclidean space is defined by

where $|\cdot|$ denotes Euclidean distance.

For every pair of functions $f$ and $g$ in ${\mathcal{C}}(^{d};B;\Gamma_{1},\dots,\Gamma_{d})$, we have

where the second last inequality follows from the Cauchy-Scwarz (C-S) inequality. Lemma IV.1 now follows because $x\in^{d}$ is arbitrary in the above argument. ∎

A more detailed account of Bronshtein’s proof of (12) can be found in Section 8.4 of .

The conclusion of the theorem is clearly only meaningful in the case when $\Gamma_{i}<\infty$ for all $i=1,\dots,d$. We therefore assume this in the rest of this proof.

For every $f\in{\mathcal{C}}\left(\prod_{i=1}^{d}[a_{i},b_{i}];B;\Gamma_{1},\dots,\Gamma_{d}\right)$, let us define the function $\hat{f}$ on $^{d}$ by

for $t_{1},t_{2},\ldots,t_{d}\in$. Clearly the function $\hat{f}$ belongs to the class ${\mathcal{C}}\left(^{d};B;\Gamma_{1}(b_{1}-a_{1}),\dots,\Gamma_{d}(b_{d}-a_{d})\right)$ and covering $\hat{f}$ to within $\epsilon$ in the $L_{\infty}$-metric is equivalent to covering $f$. Thus

We thus take, without loss of generality, $a_{i}=0$ and $b_{i}=1$ for all $i=1,\dots,d$.

From Lemma IV.1 and the observation that $V_{f}(B)\in{\mathcal{K}}^{d+1}(\sqrt{d+B^{2}})$ for all $f\in{\mathcal{C}}(^{d},B)$, it follows that

Thus from (12), we deduce the existence of two positive constants $c$ and $\epsilon_{0}$, depending only on $d$, such that

if $\epsilon\leq\epsilon_{0}\sqrt{(d+B^{2})(1+\Gamma_{1}^{2}+\dots+\Gamma_{d}^{2})}$. By the scaling inequality (IV), we obtain

if $\epsilon\leq\epsilon_{0}\sqrt{(d+B^{2})(1+\sum_{i}\Gamma_{i}^{2}(b_{i}-a_{i})^{2})}$. By another scaling argument, it follows that

for every $\Upsilon>0$ and, as a consequence, we get, for every $\Upsilon>0$,

if $\epsilon\leq\epsilon_{0}\sqrt{(d\Upsilon^{2}+B^{2})(1+\sum_{i}\Gamma_{i}^{2}(b_{i}-a_{i})^{2}/\Upsilon^{2})}$. Choosing (by differentiation)

if $\epsilon\leq\epsilon_{0}\left(B+\sqrt{d\sum_{i}\Gamma_{i}^{2}(b_{i}-a_{i})^{2}}\right)$. The proof of the theorem will now be complete by noting that

The terms involving $d$ can be absorbed in the constants $c$ and $\epsilon_{0}$. ∎

One might wonder if a version of Lemma IV.2 can be proved for the $L_{p}$-metric instead of the $L_{\infty}$-metric, and without any Lipschitz constraints. Such an inequality would, in particular, yield an alternative simpler proof of Theorem III.1. It turns out that one can prove such a bound for the $L_{1}$-metric but not for $L_{p}$ for any $p>1$. The inequality for $L_{1}$ is presented next. This inequality could possibly be of independent interest. The reason why such an inequality can not be proved for $L_{p},p>1$, is explained in Remark IV.1.

For every pair of functions $f$ and $g$ in ${\mathcal{C}}(^{d},1)$, we have

Note that the Cauchy-Schwarz inequality has been used twice in the above chain of inequalities. We have thus shown that $g(x)-f(x)\leq\rho(1+|m_{g}(x)|)$ in the case when $f(x)<g(x)$. One would have a similar inequality in the case when $f(x)>g(x)$. Combining these two, we obtain (15).

where we have used the inequality $(1-2\rho)^{d}\geq 1-2d\rho$.

for $t>0$ sufficiently small, where $e_{i}$ is the unit vector in the $i$th coordinate direction i.e., $e_{i}(j):=1$ if $i=j$ and otherwise. Dividing both sides by $t$ and letting $t\downarrow 0$, we would get $m_{f}(x)(i)\leq f^{\prime}(x;e_{i})$ (we use $f^{\prime}(x;v)$ to denote the directional derivative of $f$ in the direction $v$; directional derivatives exist as $f$ is convex). Using (16) for $t<0$, we get $m_{f}(x)(i)\geq-f^{\prime}(x;-e_{i})$. Combining these two inequalities, we get

We now show that for each $i$, both the integrals $\int_{[\rho,1-\rho]^{d}}|f^{\prime}(x;e_{i})|$ and $\int_{[\rho,1-\rho]^{d}}|f^{\prime}(x;-e_{i})|$ are bounded from above by 4. Assume, without loss of generality, that $i=1$ and notice

We fix $u=(x_{2},\dots,x_{d})\in[\rho,1-\rho]^{d-1}$ and focus on the inner integral. Let $v(z):=f(z,x_{2},\dots,x_{d})$ for $z\in$. Clearly $v$ is a convex function on $$and its right derivative,$v_{r}^{\prime}(x_{1})$at the point$z=x_{1}\in(0,1)$equals$f^{\prime}(x;e_{1})$where$x=(x_{1},\dots,x_{d})$. The inner integral thus equals$\int_{\rho}^{1-\rho}|v_{r}^{\prime}(z)|dz$. Because of the convexity of$v$, its right derivative$v_{r}^{\prime}(z)$ is non-decreasing and satisfies

The function $v(\cdot)$ clearly satisfies $|v(z)|\leq 1$ because $f\in{\mathcal{C}}(^{d},1)$. This implies that $\int_{\rho}^{1-\rho}|v_{r}^{\prime}(z)|dz\leq 4$. The identity (IV) therefore gives

Similarly, by working with left derivatives of $v$ as opposed to right, we can prove that

Therefore, the integral $\int_{[\rho,1-\rho]^{d}}|m_{f}|$ is at most $8d$ because it is less than or equal to

This completes the proof of Lemma IV.2. ∎

Lemma IV.2 is not true if $L_{1}$ is replaced by $L_{p}$, for $p>1$. Indeed, if $d=1$ and $f_{\alpha}(x):=\max(0,1-(x/\alpha))$ for $0<\alpha\leq 1$ and $g(x):=0$ for all $x\in$, then it can be easily checked that for $1\leq p<\infty$,

As $\alpha$ can be arbitrarily close to zero, this clearly rules out any inequality of the form (14) with the $L_{1}$-metric replaced by $L_{p}$, for $1<p\leq\infty$.

Lemma IV.2 and Bronshtein’s result (12) can be used to give an alternative proof of Theorem III.1 for the special case $p=1$. Indeed, the scaling identity (1) lets us take $a=0$, $b=1$ and $B=1$. Inequality (14) implies that the covering number $M\left({\mathcal{C}}(^{d},1),\epsilon;L_{1}\right)$ is less than or equal to

Thus from (12), we deduce the existence of two positive constants $c$ and $\epsilon_{0}$, depending only on $d$, such that

whenever $\epsilon\leq\epsilon_{0}$. Note that, by Remark IV.1, this method of proof does not work in the case of $L_{p}$, for $1<p<\infty$.

References