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!

  • 1
    $\begingroup$ 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.) $\endgroup$
    – whuber
    Feb 27, 2020 at 14:22
  • 1
    $\begingroup$ Yes, sure. Thank you! Now it is clear! Without this hypothesis is impossible to conclude anything. $\endgroup$ Feb 27, 2020 at 14:52


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.