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 \({\mathcal {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 \({\mathcal {O}}\left( k^{-\gamma }\right) \) . In the strongly convex setting, we show this rate for the expected suboptimality gap improves to \({\mathcal {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.
