On The Convergence Of Randomized Bregman Coordinate Descent For Non-Lipschitz Composite Problems

We propose a new randomized Bregman (block) coordinate de- scent (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 gen- erated sequence is a stationary point. Further, we show that the it- eration complexity of the proposed method is O(nε−2) to achieve ε-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ε−1). If, in addition, the objective is strongly convex (relative to the reference function), the global linear conver- gence rate is recovered. We also present the accelerated version of the RBCD method, which attains an O(nε−1/γ ) iteration complex- ity for the convex case, where the scalar γ ∈ [1, 2] is determined by the generalized translation variant of the Bregman distance. Con- vergence analysis without assuming the global Lipschitz-continuous (partial) gradient sets our results apart from the existing works in the composite problems.