4
$\begingroup$

Suppose $(X,d)$ is a metric space of unit diameer and let $F$ be the collection of all $1$-Lipschitz functions mapping $X$ to $[-1,1]$, equipped with the sup-norm $||\cdot||_\infty$.

I am interested in bounding the covering numbers $N(\epsilon,F,||\cdot||_\infty)$ in terms of covering numbers of the base space $N(\epsilon,X,d)$.

Kolmogorov and Tihomirov gave upper and lower estimates, see e.g., Theorem 17. For metric spaces with doubling dimension $D$, these estimates amount to $$ (c_1/\epsilon)^D \le \log N(\epsilon,F,||\cdot||_\infty) \le (c_2/\epsilon)^D \log(1/\epsilon)$$ for universal constants $c_1,c_2$ --- leaving a $\log(\epsilon)$ gap between the upper and lower bounds. Has the gap been closed?

Improve this question
$\endgroup$
2
  • $\begingroup$ Can this Kolmogorov-Tihomirov lowerbound on the metric entropy in the infinity-norm be used to get a lowerbound on the packing number of the same function space in some data-dependent pseuodo-metric? (On the function space I am assuming a a pseudo metric which is defined as follows : i.e for any $2$ functions $f$ and $g$ we have, the distance between them defined as, $d(f,g) = \frac{1}{n} \sum_{i=1}^n \vert f(x_i) - g(x_i) \vert$ for some choice of $n$ points $\{ x_1,..,x_n\}$ in the common domain of the functions) $\endgroup$
    – gradstudent
    Commented Jul 1, 2018 at 6:08
  • $\begingroup$ Yes, see my answer here mathoverflow.net/questions/303777/… $\endgroup$
    – Aryeh Kontorovich
    Commented Jul 1, 2018 at 13:09

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .