Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 4 down vote accepted

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

share|improve this answer
    
I see. That seems right. If I understand it correctly, this example also shows that lipschitz-continuous convex functions are not doubling, right? –  user33442 Apr 26 '13 at 4:05
    
@sd, that is right. –  Anton Petrunin Apr 27 '13 at 3:20

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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