# Intuition behind the coordinate descent convergence

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!

• Clearly the information you have provided does not assure the final inequality, because $y$ and $x$ play identical roles in the derivation and switching them reverses the inequality. Evidently some implicit assumption has been made about $x$ and $y.$ The solution appears on slide 3: $x$ is a point that minimizes the objective function separately in each coordinate direction. Please include this assumption in your post. (At that point the answer ought to be obvious.)
– whuber
Feb 27, 2020 at 14:22
• Yes, sure. Thank you! Now it is clear! Without this hypothesis is impossible to conclude anything. Feb 27, 2020 at 14:52