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

Suppose I have a Lipschitz-continuous convex function $f:\mathbb{R}^n\rightarrow \mathbb{R}$. I wish to approximate it on the unit ball by a piecewise-linear function $g:\mathbb{R}^n\rightarrow \mathbb{R}$ such that pointwise: $$\forall x : ||x||_2 \leq 1, |f(x) - g(x)| \leq \epsilon$$

Are there known bounds on the complexity of the piecewise linear function (i.e. the number of linear pieces needed) to achieve such an approximation, in terms of $\epsilon$ and $n$? I'm particularly interested in the dependence on the dimension $n$. Might the dependence be polynomial (or even linear?), or are there Lipschitz convex functions that require exponentially many linear pieces (in $n$) to approximate?

share|improve this question
    
The bound cannot be in terms of just $\epsilon$ and $n$, because multiplying $\epsilon$ by $\lambda$ is the same as multiply $f$ by $\lambda^{-1}$. Thus you must also write the bound in terms of some norm of $f$, such as its Lipschitz constant. –  Will Sawin Sep 28 '12 at 17:16
    
I think a bound on merely the size of $f$ is not sufficient: setting $f(x)=||x||_2^k$ for $n\geq 2$ and letting $k$ grow to infinity, I think the complexity of the piecewise linear function required for a fixed $\epsilon$ goes to $\infty$ as well, but I don't have a clean proof of this. This is why I suggest the Lipschitz constant. –  Will Sawin Sep 28 '12 at 17:18
2  
Certainly the bound must include the Lipschitz constant. Lets say that it is 1. –  Flavio Burton Sep 28 '12 at 17:19
    
Maybe if you seek for a $g$ that $\epsilon$-approximates $f$ with high-probability, then it might be slightly easier to construct such a $g$. Do you have a particular convex function in mind, or are you really interested in the entire class of Lipschitz-continuous convex functions? –  Suvrit Sep 28 '12 at 17:58

1 Answer 1

For $f(x)=|x|^2$, you get $\varepsilon\sim\tfrac C {k^{2/n}}$, where $k$ is the number of pieces for your PL-function. In particular, you will not get linear bound for $n\ge 3$.

I think for any convex 1-Lipschitz function you should get $\varepsilon=O(k^{-2/n})$.

An easy construction gives $\varepsilon=O(k^{-1/n})$, simply take the maximum of supporting linear functions with gradients $\{v_1,v_2,\dots,v_k\}$ which form a $C k^{-1/n}$ dense set in the unit ball.

(Note that the worse case for this approximation is a linear function with gradient sufficiently far from $v_i$.)

share|improve this answer
    
Could you elaborate on how you would prove a lower bound for $f(x) = ||x||^2$ ? –  Flavio Burton Sep 28 '12 at 17:58
1  
@Flavio, the diameter on one of pieces has to be $δ_k=Ck^{−1/n}$. On this piece the maximum of difference has to be at least $C'δ^2_k$. –  ε-δ Sep 28 '12 at 18:39
    
It seems to me that with the method of $\varepsilon - \delta$ with subdifferentials the bound should depend on the second derivative of $f$ instead of the first derivative, in pariticular getting $\varepsilon \leq C \| D^2f \| k^{ -2/n}$. Of course with this estimate one cannot include the example $f(x)=|x|$ –  Simo_the_Wolf Sep 28 '12 at 19:16

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.