# Convex functions: bounding the difference

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

• 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. Dec 23, 2012 at 3:21
• Sorry about this. I realized after posting to math.SE that mathoverflow might be a better place. Thanks for pointing it out. Dec 24, 2012 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.