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


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.


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.