Name
Title | ||
|---|---|---|
ON THE CONVERGENCE OF RANDOMIZED BREGMAN COORDINATE DESCENT FOR NON-LIPSCHITZ COMPOSITE PROBLEMS |
Abstract | ||
|---|---|---|
We propose a new 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 is an element of [1, 2] is determined by the 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. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1109/ICASSP39728.2021.9414191 | 2021 IEEE INTERNATIONAL CONFERENCE ON ACOUSTICS, SPEECH AND SIGNAL PROCESSING (ICASSP 2021) |
Keywords | DocType | Citations |
Bregman distance, Non-Lipschitz, Coordinate Descent, Convex and Nonconvex Optimization | Conference | 0 |
PageRank | References | Authors |
0.34 | 0 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tianxiang Gao | 1 | 0 | 1.01 |
| Songtao Lu | 2 | 84 | 19.52 |
| Jia Liu | 3 | 0 | 0.34 |
| Chris Chu | 4 | 647 | 40.98 |