Randomized Bregman Coordinate Descent Methods for Non-Lipschitz Optimization

Tianxiang Gao, Songtao Lu, Jia Liu, Chris Chu

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:

  1. 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.
  2. 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.

Table 1: Comparison of iteration complexities for coordinate descent and gradient descent methods across different smoothness assumptions.

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.

Figure 2: Convergence performance of BPG, ABPG, RBCD, and ARBCD on a Poisson linear inverse problem, showing the clear advantage of acceleration.

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

Abstract

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} )$. 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/\gamma} )$ iteration complexity for the convex case, where the scalar $\gamma\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.
BibTeX
@inproceedings{gao2021randomized,
  author = {Tianxiang Gao and Songtao Lu and Jia Liu and Chris Chu},
  title = {{Randomized Bregman Coordinate Descent Methods for Non-Lipschitz Optimization}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2021},
  url = {https://openreview.net/forum?id=rm2uc6SuEhC},
}
Figure