Randomized Bregman Coordinate Descent Methods for Non-Lipschitz Optimization

Understand

We propose a new \textit{randomized Bregman (block) coordinate descent} (RBCD) method for minimizing a composite problem, where the objective function could be either convex or nonconvex, and the smooth part are freed from the global Lipschitz-continuous (partial) gradient assumption.

• Under the notion of relative smoothness based on the Bregman distance, we prove that every limit point of the generated sequence is a stationary point.
• Further, we show that the iteration complexity of the proposed method is $O(n\varepsilon^{-2})$ to achieve $\epsilon$-stationary point, where $n$ is the number of blocks of coordinates.
• If the objective is assumed to be convex, the iteration complexity is improved to $O(n\epsilon^{-1} )$.