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.


1 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$.

  • $\begingroup$ I see. That seems right. If I understand it correctly, this example also shows that lipschitz-continuous convex functions are not doubling, right? $\endgroup$
    – sd234
    Apr 26, 2013 at 4:05
  • $\begingroup$ @sd, that is right. $\endgroup$ Apr 27, 2013 at 3:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.