Randomized Bregman Coordinate Descent Methods for Non-Lipschitz Optimization
This work addresses optimization challenges in non-Lipschitz settings for researchers in machine learning and optimization, offering incremental improvements by extending coordinate descent methods under relative smoothness assumptions.
The authors tackled the problem of minimizing composite objective functions without requiring global Lipschitz-continuous gradients, proposing a randomized Bregman coordinate descent method. They proved convergence to stationary points and derived iteration complexities of O(nε^{-2}) for nonconvex cases and O(nε^{-1}) for convex cases, with accelerated versions achieving O(nε^{-1/γ}).
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 $ε$-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 convergence rate is recovered. We also present the accelerated version of the RBCD method, which attains an $O(n\varepsilon^{-1/γ} )$ iteration complexity for the convex case, where the scalar $γ\in [1,2]$ is determined by the \textit{generalized translation variant} of the Bregman distance. Convergence analysis without assuming the global Lipschitz-continuous (partial) gradient sets our results apart from the existing works in the composite problems.