Skip to main content
added 52 characters in body
Source Link
dohmatob
  • 6.9k
  • 1
  • 18
  • 76

The $\epsilon$-covering number of the euclidean unit ball in $\mathbb R^d$ scales like $(1/\epsilon)^d$. More formally,

Lemma. If $\epsilon < 1$, then $(1/\epsilon)^d \le N(\epsilon, B_2) \le (3/\epsilon)^d$. Else $N(\epsilon,B_2) = 1$.

Proof. See Theorem 4.2 and Example 14.1 of this manuscript http://www.stat.yale.edu/~yw562/teaching/598/lec14.pdf. $\quad\quad\Box$

Now, use this to get (an estimate of) the covering number of $rB_2$, for any $r \ge 0$.

The $\epsilon$-covering number of the euclidean unit ball in $\mathbb R^d$ scales like $(1/\epsilon)^d$. More formally,

Lemma. $(1/\epsilon)^d \le N(\epsilon, B_2) \le (3/\epsilon)^d$.

Proof. See Theorem 4.2 and Example 14.1 of this manuscript http://www.stat.yale.edu/~yw562/teaching/598/lec14.pdf. $\quad\quad\Box$

Now, use this to get (an estimate of) the covering number of $rB_2$, for any $r \ge 0$.

The $\epsilon$-covering number of the euclidean unit ball in $\mathbb R^d$ scales like $(1/\epsilon)^d$. More formally,

Lemma. If $\epsilon < 1$, then $(1/\epsilon)^d \le N(\epsilon, B_2) \le (3/\epsilon)^d$. Else $N(\epsilon,B_2) = 1$.

Proof. See Theorem 4.2 and Example 14.1 of this manuscript http://www.stat.yale.edu/~yw562/teaching/598/lec14.pdf. $\quad\quad\Box$

Now, use this to get (an estimate of) the covering number of $rB_2$, for any $r \ge 0$.

Source Link
dohmatob
  • 6.9k
  • 1
  • 18
  • 76

The $\epsilon$-covering number of the euclidean unit ball in $\mathbb R^d$ scales like $(1/\epsilon)^d$. More formally,

Lemma. $(1/\epsilon)^d \le N(\epsilon, B_2) \le (3/\epsilon)^d$.

Proof. See Theorem 4.2 and Example 14.1 of this manuscript http://www.stat.yale.edu/~yw562/teaching/598/lec14.pdf. $\quad\quad\Box$

Now, use this to get (an estimate of) the covering number of $rB_2$, for any $r \ge 0$.