1
$\begingroup$

I have read some literature about the convergence rate of block coordinate descent. They all assume that the object function $f$ is Lipschitz continuous, is there any results for the convergence rate if $f$ is continuous and convex but not have Lipschitz gradient?

Update: Assume the function $f$ is smooth and block coordinate descent can find the minimum of $f$ successfully without getting stuck at some points.

$\endgroup$
1
$\begingroup$

The Wikipedia page has a counterexample: A continuous convex function for which coordinate descent fails to converge but getting stuck in a non-optimal point.

Here are the level lines of this function:

Nonsmooth coordinate descent.svg
By Nicoguaro - Own work, CC BY 4.0, Link

$\endgroup$
  • $\begingroup$ I have updated the question. Assume that BCD can find the minimum of $f$, is there any known convergence rate for the problem? $\endgroup$ – Yi Yang Aug 18 '17 at 10:46
  • $\begingroup$ For some reason I have the feeling that this question is going to change as soon as there appears a new answer... $\endgroup$ – Dirk Aug 18 '17 at 15:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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