학술논문
The Randomized Block Coordinate Descent Method in the H\'older Smooth Setting
Document Type
Working Paper
Source
Subject
Language
Abstract
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.