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$?

  • 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 Dec 23 '12 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 Dec 24 '12 at 23:25

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

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.