The Randomized Block Coordinate Descent Method in the Hölder Smooth Setting

Abstract

This work provides the first convergence analysis for the Randomized Block Coordinate Descent method for minimizing a function that is both Hölder smooth and block Hölder smooth. Our analysis applies to objective functions that are non-convex, convex, and strongly convex. For non-convex functions, we show that the expected gradient norm reduces at an $O\left(k^{\frac{\gamma }{1+\gamma }}\right)$ rate, where $k$ is the iteration count and $\gamma$ is the Hölder exponent. For convex functions, we show that the expected suboptimality gap reduces at the rate $O\left(k^{-\gamma }\right)$. In the strongly convex setting, we show this rate for the expected suboptimality gap improves to $O\left(k^{-\frac{2\gamma }{1-\gamma }}\right)$ when $\gamma >1$ and to a linear rate when $\gamma =1$. Notably, these new convergence rates coincide with those furnished in the existing literature for the Lipschitz smooth setting.