<p>Since you've tagged machine learning, I'll address this setting. Indeed, for the usual <span class="math-container">$\ell_p$</span> norms on <span class="math-container">$\mathbb{R}^n$</span>, we have <span class="math-container">$||x||_p\le ||x||_q$</span> for <span class="math-container">$p&gt;q$</span>. However, in machine learning applications, these are <em>normalized</em> norms (see, e.g., Mendelson, A few notes on Statistical Learning Theory
<a href="https://people.eecs.berkeley.edu/~jordan/courses/281B-spring04/readings/mendelson.ps" rel="nofollow noreferrer">https://people.eecs.berkeley.edu/~jordan/courses/281B-spring04/readings/mendelson.ps</a>
). 
Let <span class="math-container">$D$</span> be a distribution on <span class="math-container">$\{1,\ldots,n\}$</span>. Then the corresponding <span class="math-container">$\ell_p(D)$</span> norm is defined by
<span class="math-container">$$
||x||_{\ell_p(D)}^p = \sum_{i=1}^n D(i)|x_i|^p.
$$</span>
You can verify that for these norms, the inequality goes the other way:
<span class="math-container">$||x||_{\ell_p(D)}\ge ||x||_{\ell_q(D)}$</span> for <span class="math-container">$p&gt;q$</span>. This explains the covering number inequality as well.</p>

CC BY-SA 4.0
2019-02-28T07:18:39.057Z
2019-02-28T07:18:39.057Z
Aryeh
<h1>Problem</h1>

<p>I do not understand why larger <span class="math-container">$p$</span> will give a larger covering number. </p>

<p>Since when <span class="math-container">$p\geq q$</span>, the corresponding hypercube is also larger (by <span class="math-container">$\| x \| _ { q } \leq n ^ { ( 1 / q - 1 / p ) } \| x \| _ { p }$</span> when <span class="math-container">$p &gt; q&gt;0$</span>) and thus should give smaller covering set. Covering number is essentially the minimum cardinality of covering set, so it seems that larger <span class="math-container">$p$</span> should give smaller covering number?</p>

<p><a href="https://i.sstatic.net/XNo0i.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/XNo0i.png" alt="enter image description here"></a></p>

<machine-learning><lg.learning>
Confusion about covering number
Mr.Robot
# Confusion about covering number

(Asked by: username_0 on 2019-02-28)

# Problem

I do not understand why larger $p$ will give a larger covering number.

Since when $p\geq q$, the corresponding hypercube is also larger (by $\| x \| \_ { q } \leq n ^ { ( 1 / q - 1 / p ) } \| x \| \_ { p }$ when $p > q>0$) and thus should give smaller covering set. Covering number is essentially the minimum cardinality of covering set, so it seems that larger $p$ should give smaller covering number?

[![enter image description here](https://i.sstatic.net/XNo0i.png)](https://i.sstatic.net/XNo0i.png)

**Tags:** machine-learning, lg.learning

---

## 1 answers

### Answer by username_1 on 2019-02-28. Score: 1

Since you've tagged machine learning, I'll address this setting. Indeed, for the usual $\ell\_p$ norms on $\mathbb{R}^n$, we have $||x||\_p\le ||x||\_q$ for $p>q$. However, in machine learning applications, these are *normalized* norms (see, e.g., Mendelson, A few notes on Statistical Learning Theory
<https://people.eecs.berkeley.edu/~jordan/courses/281B-spring04/readings/mendelson.ps>
).
Let $D$ be a distribution on $\{1,\ldots,n\}$. Then the corresponding $\ell\_p(D)$ norm is defined by
$$
||x||\_{\ell\_p(D)}^p = \sum\_{i=1}^n D(i)|x\_i|^p.
$$
You can verify that for these norms, the inequality goes the other way:
$||x||\_{\ell\_p(D)}\ge ||x||\_{\ell\_q(D)}$ for $p>q$. This explains the covering number inequality as well.


---

