This paper, published in early 2020, addresses a significant bottleneck in first-order optimization: the reliance on global Lipschitz continuity. By merging the efficiency of Coordinate Descent (CD) with the flexibility of Bregman distances, the authors provide a robust framework for solving "relatively smooth" problems that were previously difficult to handle theoretically and practically.
TL;DR
The authors propose Randomized Bregman Coordinate Descent (RBCD) and its accelerated version to minimize composite functions that lack global Lipschitz-continuous gradients. By leveraging the notion of "relative smoothness," they establish the first iteration complexity bounds for coordinate descent in this setting, achieving significant speedups on problems like Poisson inverse modeling.
What Problem Does This Paper Address?
Most standard optimization algorithms (like Gradient Descent or Coordinate Descent) rely on a "Lipschitz-continuous gradient" assumption. Essentially, this assumes the slope of the function doesn't change too abruptly, allowing us to take steps without overshooting.
However, many modern applications—such as matrix factorization, tensor decomposition, and Poisson likelihood models—violate this. In these cases, the gradient can change extremely rapidly, making standard methods unstable or requiring computationally expensive line searches. While "Bregman Proximal Gradient" (BPG) methods were recently developed to handle this by adapting the "geometry" of the step to the function, there were no established convergence rates for Coordinate Descent versions, which are often preferred for large-scale problems due to their low per-iteration memory and computational costs.
Methods
The authors introduce two primary algorithms:
- RBCD (Randomized Bregman Coordinate Descent): At each step, the algorithm randomly selects one block of variables and updates it using a Bregman proximal mapping. Instead of measuring distance with standard Euclidean "straight lines," it uses a Bregman distance $D_h$ derived from a reference function $h$ that "matches" the curvature of the objective function.
- ARBCD (Accelerated RBCD): An accelerated variant that uses Nesterov-style momentum adapted for the Bregman setting.
Key Theoretical Innovations: * Relative Smoothness: They analyze the algorithms under the framework of relative smoothness, where the objective function is bounded by the Bregman distance of a reference function rather than a quadratic term. * Generalized Translation Invariant (GTI): To enable acceleration, they introduce the GTI property for Bregman distances, which allows the momentum terms to work correctly even when the underlying geometry is non-Euclidean. * Efficient Implementation: They provide a scheme (Algorithm 3) to ensure that the coordinate updates remain $O(1)$ in complexity, avoiding the need to process the full-dimensional vector at every step.
Datasets
The paper evaluates the algorithms using synthetic benchmarks designed to mimic real-world non-Lipschitz problems:
- Poisson Linear Inverse Problem: Common in medical imaging and astronomy, where data follows a Poisson distribution.
- Relative-Entropy Nonnegative Regression: A problem involving Kullback-Leibler (KL) divergence.
- Synthetic Setup: Datasets with dimensions $M=500$ and $N=500$, where entries are generated from uniform distributions.
Key Insights and Ideas
- Custom Geometry: The "aha moment" is that you don't need a function to be globally smooth if you can find a reference function $h$ that "grows" as fast as your objective. By measuring steps relative to $h$, the objective becomes "relatively smooth."
- Coordinate Descent is "Cheaper": Because RBCD only updates one block at a time, its per-iteration cost is $n$ times cheaper than full gradient methods (where $n$ is the number of blocks).
- No More Ripples: Interestingly, while accelerated gradient methods often show "ripples" or oscillations in their convergence plots, the ARBCD method demonstrated a more consistent, monotonic descent in the objective value during experiments.
Key Results
The authors provide rigorous complexity bounds for the number of iterations needed to reach an $\epsilon$-accurate solution:
- Nonconvex Problems: $O(n\epsilon^{-2})$ to reach a stationary point.
- Convex Problems: $O(n\epsilon^{-1})$.
- Strongly Convex (Relative): Linear convergence rate.
- Accelerated Convex: $O(n\epsilon^{-1/\gamma})$, where $\gamma$ is a scaling factor (typically $\gamma \in [1, 2]$).
In numerical tests, ARBCD significantly outperformed both the standard Bregman Proximal Gradient (BPG) and the non-accelerated RBCD, reaching lower error levels much faster in terms of iteration count.
Limitations and Future Work
- Hyperparameter Sensitivity: The acceleration parameter $\gamma$ is critical. The experiments showed that while a smaller $\gamma$ can lead to faster convergence, choosing it incorrectly can lead to divergence (as seen in the relative-entropy regression tests).
- Reference Function Selection: The method's success depends entirely on finding an appropriate reference function $h$ for a given problem. While $h(x) = -\sum \log x_i$ works well for Poisson models, other problems may require more complex engineering to find a suitable $h$.
- Future Directions: The authors suggest that extending these results to asynchronous parallel settings or exploring more automated ways to choose the reference function would be valuable next steps.
Summary updated