Randomized Bregman Coordinate Descent Methods for Non-Lipschitz Optimization

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{\epsilon }^{-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{\epsilon }^{-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.

First draft

References in corpus (10)

• An Alternating Direction Algorithm for Matrix Completion with Nonnegative Factors
• Inexact Block Coordinate Descent Methods For Symmetric Nonnegative Matrix Factorization
• Accelerated Bregman Proximal Gradient Methods for Relatively Smooth Convex Optimization
• Improved Iteration Complexity Bounds of Cyclic Block Coordinate Descent for Convex Problems
• A cyclic block coordinate descent method with generalized gradient projections
• Accelerating Greedy Coordinate Descent Methods
• Fast and Simple Optimization for Poisson Likelihood Models
• Multi-block Bregman proximal alternating linearized minimization and its application to orthogonal nonnegative matrix factorization
• Leveraging Two Reference Functions in Block Bregman Proximal Gradient Descent for Non-convex and Non-Lipschitz Problems
• Accelerated Stochastic Greedy Coordinate Descent by Soft Thresholding Projection onto Simplex

Cited by in corpus (2)

• Bregman Finito/MISO for nonconvex regularized finite sum minimization without Lipschitz gradient continuity
• Regret Bounds without Lipschitz Continuity: Online Learning with Relative-Lipschitz Losses