  This work provides the first convergence analysis for the Randomized Block
Coordinate Descent method for minimizing a function that is both H\"older
smooth and block H\"older 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\"older 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.
