Question

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?

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