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 Answer 1

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$
2
  • $\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$
    – JYY
    Aug 18, 2017 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, 2017 at 15:35

Your Answer

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

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