Take the 2-minute tour ×

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
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
add comment

1 Answer

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
@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
add comment

Your Answer


