What is the doubling dimension of convex functions?

Question

I am interested in the complexity of convex functions, specifically the "doubling dimension" of the class of convex functions defined on a compact subset of Euclidean space, when compared using the $L^\infty$ metric.

Formally, let $F$ be the class of convex functions mapping $[0,1]^n$ to $[0,1]$. For $f,g \in F$, define the distance between them as $d(f,g) = sup_{x \in [0,1]^n} |f(x) - g(x)|.$ My question is: Is $(F,d)$ a doubling metric space, and if so what is its doubling dimension as a function of $n$?

Recall that a metric space is doubling if there exists an integer $M$ such that every ball of finite radius $r$ can be covered by at most $M$ balls of radius $r/2$. For such a space, the doubling dimension is defined to be $\log_2 M$.

Observe that, had I replaced "convex" with "linear" in my statement of the question, the answer would have been "yes, and the doubling dimension is $O(n)$." I'm hoping for a similar answer for convex functions. Given that this seems like a fairly natural question, I would guess the answer is already known, or at least obvious to anyone working in functional analysis.

Answer 1

No the space is not doubling.

Take a strongly convex function, say $f(x)=x^2$. It is sufficient to show that there is $N(\varepsilon)$ which goes to $\infty$ as $\varepsilon\to0$, such that $\varepsilon$-neighborhood of $f$ contains $N(\varepsilon)$ points on distance $>\varepsilon$ from each other.

To see this take any finite collection of distinct points $\{x_i\}$ in $[0,1]$ and note that for all small $\varepsilon>0$ there is a function $f_i$ in the $\varepsilon$-neighborhood of $f$ such that $f_i(x_i)=f(x_i)+\varepsilon/2$ and $f_i(x_j)=f(x_j)-\varepsilon/2$ for all $i\ne j$.