TITLE: Convex functions: bounding the difference
QUESTION [0 upvotes]: 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$?

REPLY [2 votes]: $$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.
{"set_name": "stack_exchange", "score": 0, "question_id": 117062}