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?

Improve this question
$\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
    Commented 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
    Commented Sep 28, 2012 at 17:18
  • 2
    $\begingroup$ Certainly the bound must include the Lipschitz constant. Lets say that it is 1. $\endgroup$
    – Flavio Burton
    Commented 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
    Commented Sep 28, 2012 at 17:58

2 Answers 2

Reset to default
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$.)

Improve this answer
$\endgroup$
4
  • $\begingroup$ Could you elaborate on how you would prove a lower bound for $f(x) = ||x||^2$ ? $\endgroup$
    – Flavio Burton
    Commented 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$
    – ε-δ
    Commented 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$
    – Simo_the_Wolf
    Commented 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.
    Commented 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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .