MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
Crossposted to math.SE: 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. – Zev Chonoles Dec 23 '12 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. – Rajhans Dec 24 '12 at 23:25
up vote 2 down vote accepted

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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