Introduction
A significant bottleneck in first-order optimization is the traditional reliance on global Lipschitz continuity of the gradient. This assumption, while mathematically convenient, is frequently violated in modern applications such as matrix factorization, tensor decomposition, and Poisson likelihood models. In these scenarios, gradients can change abruptly, leading to instability in standard methods.
This paper introduces a robust framework that merges the efficiency of Coordinate Descent (CD) with the flexibility of Bregman distances. By leveraging the notion of "relative smoothness," the authors propose Randomized Bregman Coordinate Descent (RBCD) and its accelerated counterpart (ARBCD), establishing the first iteration complexity bounds for coordinate descent in non-Lipschitz settings.
The Challenge: Beyond Global Lipschitz Continuity
Standard optimization algorithms like Gradient Descent or Coordinate Descent typically assume the slope of the function does not change too rapidly. When this "Lipschitz-continuous gradient" assumption fails, standard methods often require computationally expensive line searches or become unstable.
While Bregman Proximal Gradient (BPG) methods were developed to handle such "geometry" issues by adapting the step to the function's curvature, convergence rates for Coordinate Descent variants—which are preferred for large-scale problems due to low per-iteration costs—remained unestablished until now.
Proposed Methodology
The authors introduce two primary algorithms designed for composite functions that lack global Lipschitz-continuous gradients:
- RBCD (Randomized Bregman Coordinate Descent): At each iteration, the algorithm randomly selects a block of variables and updates it using a Bregman proximal mapping. This mapping uses a Bregman distance $D_h$ derived from a reference function $h$ that matches the objective's curvature, rather than standard Euclidean distance.
- ARBCD (Accelerated RBCD): This variant incorporates Nesterov-style momentum adapted for the non-Euclidean Bregman setting.
To enable acceleration, the authors introduce the Generalized Translation Invariant (GTI) property for Bregman distances. This ensures that momentum terms function correctly even when the underlying geometry is non-standard. Furthermore, an efficient implementation scheme ensures that coordinate updates maintain $O(1)$ complexity, avoiding full-dimensional vector processing at every step.
Theoretical Complexity and Empirical Results
The paper provides rigorous complexity bounds for reaching an $\epsilon$-accurate solution across various problem types. These results are summarized in the table below, comparing the proposed methods against existing literature.
Key theoretical insights include:
- Nonconvex Problems: $O(n\epsilon^{-2})$ to reach a stationary point.
- Convex Problems: $O(n\epsilon^{-1})$.
- Accelerated Convex: $O(n\epsilon^{-1/\gamma})$, where $\gamma \in [1, 2]$ is a scaling factor.
In numerical evaluations, such as the Poisson Linear Inverse Problem, the ARBCD method demonstrated significant performance gains. Unlike many accelerated methods that exhibit oscillatory "ripples," ARBCD showed a more consistent, monotonic descent in objective values.
Discussion and Limitations
While the proposed methods offer substantial improvements, they introduce new considerations:
- Hyperparameter Sensitivity: The acceleration parameter $\gamma$ is critical. Experiments indicated that while an optimal $\gamma$ yields rapid convergence, an incorrect choice can lead to divergence in certain problems, such as relative-entropy regression.
- Reference Function Selection: The method's efficacy depends on identifying an appropriate reference function $h$. While functions like $h(x) = -\sum \log x_i$ are effective for Poisson models, other domains may require more specialized engineering.
Future research directions include extending these results to asynchronous parallel settings and developing automated methods for selecting optimal reference functions.
Summary updated