0
$\begingroup$

Suppose you are given a convex function $f: R^d \rightarrow R$. Let us say you are given $x,x' \in R^d$ and $x_1, x_2, \ldots, x_n \in R^d$ such that

$$\sum_{i=1}^n (x_i - x') = x - x'.$$

Is it possible to bound $f(x) - f(x')$ in terms of $f(x_i) - f(x')$?

That is, a bound of the form

$$f(x) - f(x') \leq \sum_{i}^n \left( f(x_i) - f(x') \right) + \sum_i^n \epsilon(x_i,x),$$

where $\epsilon_i$ are some small "error" functions based on some property of $f$? Is there a class of functions $f$ for which this will be valid with $\epsilon = 0$?

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ Crossposted to math.SE: math.stackexchange.com/q/263923/264 In the future, please wait some time before posting your question in multiple fora, and when you do, provide links to the other posts - as you can imagine, it would be frustrating for someone to put time into answering your question here, only to see hear from you that you'd already gotten the solution elsewhere. $\endgroup$
    – Zev Chonoles
    Commented Dec 23, 2012 at 3:21
  • $\begingroup$ Sorry about this. I realized after posting to math.SE that mathoverflow might be a better place. Thanks for pointing it out. $\endgroup$
    – Rajhans
    Commented Dec 24, 2012 at 23:25

1 Answer 1

Reset to default
2
$\begingroup$

$$f(x) - f(x') \le \sum_i \left(f(x_i) - f(x')\right)$$ iff the function $g(x) = f(x + x') - f(x')$ is subadditive.

Improve this answer
$\endgroup$

You must log in to answer this question.

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