Show the following inequality holds (with Taylor Approximation)

Question

Consider a sequence of vector $x_1, x_2, ..., x_N$. Show that for $$ \bar{x} = \frac{1}{N} \sum_{i=1}^N x_i $$ the following inequality holds $$ f(\bar{x}) - f(x^*) \leq \frac{1}{N}\sum_{i=1}^N <x_i - x^*, \nabla f(x_i)> $$ where $x^*$ minimizes $f$ which is a convex function mapping from $R^n$ to $R^m$.

Answer 1

By convexity, $$f(x_i) + \langle x^* - x_i, \nabla f(x_i) \rangle \le f(x^*)$$ for each $i$. Summing over all $i$ and dividing by $N$ yields $$\frac{1}{N} \sum_{i=1}^N f(x_i) - f(x^*) \le \frac{1}{N} \sum_{i=1}^N \langle x_i - x^*, \nabla f(x_i)\rangle.$$ Finally, note that $\frac{1}{N} \sum_{i=1}^N f(x_i) \ge f(\bar{x})$.