16
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Will Sawin
    Sep 28, 2012 at 17:16
  • $\begingroup$ 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. $\endgroup$
    – Will Sawin
    Sep 28, 2012 at 17:18
  • 2
    $\begingroup$ Certainly the bound must include the Lipschitz constant. Lets say that it is 1. $\endgroup$ Sep 28, 2012 at 17:19
  • $\begingroup$ 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? $\endgroup$
    – Suvrit
    Sep 28, 2012 at 17:58

2 Answers 2

3
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Could you elaborate on how you would prove a lower bound for $f(x) = ||x||^2$ ? $\endgroup$ Sep 28, 2012 at 17:58
  • 1
    $\begingroup$ @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$. $\endgroup$
    – ε-δ
    Sep 28, 2012 at 18:39
  • $\begingroup$ 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|$ $\endgroup$ Sep 28, 2012 at 19:16
  • $\begingroup$ @Simo_the_Wolf (and ε-δ) I'm tackling a similar problem, but the math here is really new to me. I was wondering if you could suggest some introductory reading (that would allow me to understand the easy construction)? $\endgroup$
    – Berk U.
    Mar 16, 2015 at 18:24
1
$\begingroup$

See Lemma 4.1 in

Balazs, Gyorgy, Szepesvari, Near-optimal max-affine estimators for convex regression, AISTATS, 2015, http://jmlr.org/proceedings/papers/v38/balazs15.pdf

Although they use $||x||_\infty \le 1$, the modification to the Euclidean norm is straightforward.

$\endgroup$
1
  • 1
    $\begingroup$ Considering that this question was asked several years ago you may want to add more to your answer. $\endgroup$ Oct 31, 2015 at 15:38

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.