I am looking at the page 6 of the slides about Coordinate Descent of Geoff Gordon and Ryan Tibshirani at the Carnegie Mellon University.
They are dealing with the the Coordinate Descent algorithm convergence for the case of $f(x)=g(x) + \sum_{i=1}^{n} h(x_i)$, where both $g$ and $h$ are convex and $h$ is a non-smooth separable function.
Edit: The missing assumption (as pointed by @whuber): Given convex, differentiable $f:\mathbb{R}^n\rightarrow\mathbb{R}$, if we are at a point $x$ such that $f(x)$ is minimized along each coordinate axis, have we found a global minimizer?
What have I tried?
For all $y$: $$g(y)-g(x)\ge \nabla g(x)(y-x) \text{ [since $g$ is convex]}$$ $$h(y)-h(x)=\sum_{i=1}^{n} (h(y_i)-h(x_i))$$ Therefore, $$f(y)-f(x)=g(y)-g(x)+h(y)-h(x)\ge$$ $$\nabla g(x)(y-x)+\sum_{i=1}^{n} (h(y_i)-h(x_i))=$$ $$\sum_{i=1}^{n} (\nabla_i g(x)(y_i-x_i) +h(y_i)-h(x_i))\ge 0,$$
However, I do not understand the last inequality. I mean why $$\sum_{i=1}^{n} (\nabla_i g(x)(y_i-x_i) +h(y_i)-h(x_i))\ge 0?$$ I understand that $\nabla_i g(x)$ is positive due to the algorithm, but not the reason the entire expression is positive. It must be something obvious since there is no comment at the slide. What am I missing?
Just to be clear, I am not looking for the full proof of convergence (that I can find in the paper). I would like to discover what I am missing in these slides. Any help will be very wellcome!
