7
$\begingroup$

I am looking for a straightforward way to upper bound the covering number of a $d$-dimensional euclidean ball by $\ell_\infty$-balls of radius $\varepsilon$, which I will call cubes of sidelength $2\varepsilon$ for clarity. Let us denote this number by $\mathcal N(\varepsilon)$.

An elementary upper bound is to say $\mathcal N(\varepsilon) \leqslant 1 / \varepsilon^d$, as we can cover the whole cube of sidelength 2 with this many small cubes. However, I know that the precise asymptotic behavior, up to multiplicative and additive constants, is the following $$ \log \mathcal N(\varepsilon) \approx \left\{\begin{split} \frac{1}{\varepsilon^2} \log d \varepsilon^2\quad \text{if} \quad \varepsilon \geqslant 1/\sqrt{d}\\ d \log \frac{1}{d\varepsilon^2} \quad \text{if} \quad \varepsilon \leqslant 1/\sqrt{d} \, . \end{split}\right. \ $$ Therefore the easy upper bound of $d \log 1/ \varepsilon$ is loose when $\varepsilon$ is large. The change of regime happens when the diagonal of the smaller cubes become comparable to the radius of the larger ball.

The only proof I found, in online teaching notes [1], is convoluted. It consists in first bounding the covering number of $\ell_1$ balls by $\ell_2$ balls, thanks to Maurey's empirical method, and then to appeal to a duality result of [2].

While the proof is elegant and sophisticated, the inconvenient is that it yields non-explicit constants. Also, it does not seem to take advantage of the ``easiness'' of the problem: covering with hypercubes should not be too hard as the cubes fit well together. I tried counting the number of cubes needed to cover the ball in the natural covering (cutting the cube of sidelength $2$ into small cubes of length $2\varepsilon$ ) but I have no idea how one would do so. For all I know, it might even be that the optimal covering has some overlap between the cubes.

EDIT: A nice improvement on the trivial bound by Rémi Peyre. Considering the natural covering, it suffices to count the cubes that lie inside the ball of radius $1 + 2 \varepsilon \sqrt{d}$. Therefore \begin{equation} \mathcal N(\varepsilon) \leq \frac{1}{2 \epsilon^d} \mathrm{Vol}\big(B(1 + 2\varepsilon\sqrt{d}) \big) \leq \frac{1}{\sqrt{d\pi}} (2 \pi e)^{d/2} \Big( 1 + \frac{1}{2\varepsilon \sqrt{d}} \Big)^d \, . \end{equation} using a non-asymptotic version of Stirling. Taking logs we obtain something of order $d ( c + \log(1 + 1/(\varepsilon \sqrt{d}) )$. This is an improvement but is still far from the refined bounds above, when $\varepsilon \sqrt{d}$ is large.

[1] http://www.stat.yale.edu/~yw562/teaching/598/lec15.pdf

[2] Duality of metric entropy, S. Artstein, V. Milman, and S. J. Szarek https://annals.math.princeton.edu/wp-content/uploads/annals-v159-n3-p07.pdf

$\endgroup$
6
  • 3
    $\begingroup$ Using the natural covering, the total area covered by your cubes will be contained inside the ball of radius $1 + 2 \epsilon \sqrt{d}$, whose volume you can compute explicitly; and since the cubes in this covering are disjoint, dividing by the volume of a cube you would get an upper bound on $\mathcal{N}(\epsilon)$. Is the bound obtained this way powerful enough for your purpose…? $\endgroup$ Dec 22, 2020 at 2:50
  • $\begingroup$ @Rémi Peyre then, what fraction of the area of the annulus between the balls of radius $1+2\epsilon\sqrt d$ and $1$ is covered by the cubes? A lower bound on it may be used to improve the bound on $\mathcal{N}(\epsilon)$. I guess it's around $1/d$. $\endgroup$ Dec 22, 2020 at 7:33
  • $\begingroup$ Thanks a lot @RémiPeyre . I added an edit with this idea. It's still not enough to recover the $1/\epsilon^2 \log d\epsilon^2$ behavior. Perhaps using Pietro Majer's idea. Actually, if you consider the case $\epsilon = 1/2$, the natural covering has $2^d$ elements, and the bound says I could do with $d$ cubes only (times a constant and plus a constant). So it would seem the natural covering is not the answer? $\endgroup$
    – hHhh
    Dec 22, 2020 at 21:26
  • $\begingroup$ My intuition completely fails me in high-dimension and I find this fascinating. $\endgroup$
    – hHhh
    Dec 22, 2020 at 21:28
  • $\begingroup$ Following the comment of @PietroMajer, an refinement of my above idea would consist in considering that the origin of the grid in the natural covering is chosen randomly (in $(\mathbf{R}/2\epsilon\mathbf{Z})^d$, I mean). Then, for $x$ outside the ball, you can ask what is the probability that $x$ will be included in the natural covering of the ball: this is tantamount to asking what the probability is that the $(2\epsilon)$-edge cube centred at a point chosen randomly in the $(2\epsilon)$-edge cube centred on $x$ will intersect the ball. (to be continued) $\endgroup$ Dec 23, 2020 at 16:21

1 Answer 1

3
$\begingroup$

Once you know the answer, the proof is a trivial induction on $d$. We will show that for some positive constants $A,B,K$ (to be chosen in the end) one can cover the ball of radius $r$ by $$ F(d,R^2)=\left(1+\frac{d}{R^2}\right)^{BR^2}+\left(\frac{AR^2}{d}\right)^{d/2}=F_1(d,R^2)+F_2(d,R^2). $$ cubes with sidelength $2K$ where $R^2=r^2+K^2$. If you are not too picky about constants, this is equivalent to what you have requested.

We will notice first of all that $F(d,R^2)=0$ for $R<K$ ($r$ is killed for $R=K$ already, so we do not need to take any special care of too small values of $R$ in any dimension. We shall also notice that everything is fine in dimensions $1,2$, so we'll take $d\ge 2$ for the induction step.

Now take the $d+1$-dimensional ball of radius $r$, cover the central slice of width $2K$ by $F(d,R^2)$ cubes and then go up and down by $K$ looking at how the radii of the cross-sections change and using the optimal cover each time. We'll get $$ F(d,R^2)+2\sum_{m\ge 1} F(d,R^2-m^2K^2) $$
All we need to do is to compare it to $F(d+1,R^2)$. We want the domination to be overwhelming (in a sense), so let us look at each term separately first.

Term 1: We have $$ F_1(d+1,R^2)-F_1(d,R^2)\ge B\left(1+\frac{d}{R^2}\right)^{BR^2-1} $$ (mean value theorem). On the other hand, the derivative of the function $f(x)=Bx\log(1+\frac dx)$ is $B[\log(1+\frac dx)-\frac{d}{d+x}]\ge B[\log(1+\frac d{R^2})-\frac d{d+R^2}]=B\lambda$ on $[0,R^2]$, so the sum in $m$ for $F_1$ is dominated by $$ \left(1+\frac{d}{R^2}\right)^{BR^2}\int_{K^2/2}^\infty e^{-B\lambda t}dt=\left(1+\frac{d}{R^2}\right)^{BR^2}e^{-BK^2\lambda/2}\frac 1{B\lambda} \\ \le \left(1+\frac{d}{R^2}\right)^{BR^2-1}e^B e^{-(BK^2/2-1)\lambda}\frac 1{B\lambda}\le \left(1+\frac{d}{R^2}\right)^{BR^2-1}e^B e^{-BK^2\lambda/4}\frac 1{B\lambda} $$ If $\lambda\ge\frac 1K$, we have the factor $$ e^{-(K/4-1)B}\frac KB\ll B $$ provided that $K$ is large enough (even in terms of $B$, if you want; we'll choose $K$ last).

So, we are in danger here only if $\lambda<\frac 1K$, in which case, since $\log(1+u)-\frac u{u+1}\approx u^2/2$ near $u=0$, we have $\frac{d}{R^2}\le\sqrt{\frac 6K}$, say, and we shall use the trivial estimate $R^2e^{Bd}$ for the sum (each term is at most $e^d$ and there are not more than $R^2$ terms).

Term 2: $$ F_2(d+1,R^2)=\left(\frac{AR^2}{d+1}\right)^{(d+1)/2}\ge \sqrt{\frac{AR^2}{d+1}}\left(\frac d{d+1}\right)^{d/2}\left(\frac{AR^2}{d}\right)^{d/2} \\ \ge \sqrt{\frac{AR^2}{2de}}F(d,R^2) $$ If $\frac{d}{R^2}<\sqrt{\frac 6K}$, this is at least $$ \sqrt{\frac{AR^2}{2de}}\left(\frac{AR^2}{d}\right)^{d/2}\ge \frac{AR^2}{2de}\left(\frac{AR^2}{d}\right)^{(d-1)/2} \ge \frac{AR^2}{2de}(A\sqrt K/3)^{d/4}\gg R^2e^{Bd} $$ if $A$ is not too small and $A\sqrt K/(3e^4)\gg e^{4B}$, which can be achieved by increasing $K$ for any fixed $A,B$.

Now it is time to estimate the sum in $m$. Again, comparing to the exponent, we see that we get $$ \le F_2(d,R^2)\sum_{m\ge 1} e^{-\frac{m^2K^2d}{2R^2}}\le \sqrt{\frac{R^2}d} $$ so we need to compare $ \sqrt{\frac{AR^2}{2de}} $ and $1+2\sqrt{\frac{R^2}d}$. If $d\le R^2$, the first expression wins big time. If not, we have at most $3\left(\frac{AR^2}{d}\right)^{d/2}$. We can play it against $B\left(1+\frac{d}{R^2}\right)^{BR^2-1}$ now. $B$ certainly beats $3$. If $d>AR^2$, the comparison is trivial. Finally, if $R^2\le d\le AR^2$, we have at most $A^{AR^2/2}$ on the left and at least $2^{BR^2/2}$ on the right, so if $A^A\le 2^B$, we are fine. This tells the relation between $A$ and $B$ (both large) and $K$ is chosen last.

The end.

P.S. If you think a bit, you see that such induction is doomed to work: no fancy cover is possible because for the cubes of twice smaller size the covers of our slices are disjoint (the cube just cannot stretch enough in the vertical direction), so the stupid algorithm (cover slice by slice reducing the dimension by 1, then do the same for each slice of slice, etc.) is actually the best.

$\endgroup$
5
  • $\begingroup$ this looks great thanks! I'll have to work through it a bit before I accept (do you sincerely consider this to be trivial?) about the PS: there is still some degrees of freedom in what we call the stupid algorithm, in that we can choose where we center the covers. E.g. take $\epsilon\geq \sqrt{2}/2$. There is a bad way to do the covering, using $2^d$ cubes, and a smarter way, centering a first cube around $0$ and stacking one on each face, taking $2d+1$ cubes. $\endgroup$
    – hHhh
    Dec 23, 2020 at 13:13
  • $\begingroup$ @hHhh Of course, check all the details and ask all the questions that come to your head! If they are all correct, I sincerely do consider it trivial: you have an explicit formula for the answer, so why not to do some elementary algebra to check if the simple recursion works. But of course, I can make mistakes (in the first version I differentiated $\log$ incorrectly, so I had to delete the answer, to edit it, and then to undelete. As to "bad way", it is, indeed, wasteful to cover the central section twice every time. You certainly want the maximal reduction in the radius of the slice, I agree. $\endgroup$
    – fedja
    Dec 23, 2020 at 13:22
  • $\begingroup$ @fedja Which bound is the induction proving -- the "large" $\epsilon$ or the "small" $\epsilon$ regime? $\endgroup$ Jul 6, 2021 at 10:25
  • $\begingroup$ @AryehKontorovich I think it is proving all of them. Am I missing anything? $\endgroup$
    – fedja
    Jul 9, 2021 at 3:00
  • $\begingroup$ I see. Will just have to stare at it longer:) $\endgroup$ Jul 9, 2021 at 4:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.