| Paper ID | SPTM-21.5 |
| Paper Title |
ON THE CONVERGENCE OF RANDOMIZED BREGMAN COORDINATE DESCENT FOR NON-LIPSCHITZ COMPOSITE PROBLEMS |
| Authors |
Tianxiang Gao, Iowa State University, United States; Songtao Lu, IBM, United States; Jia Liu, Ohio Stat University, United States; Chris Chu, Iowa Stat University, United States |
| Session | SPTM-21: Optimization Methods for Signal Processing |
| Location | Gather.Town |
| Session Time: | Friday, 11 June, 13:00 - 13:45 |
| Presentation Time: | Friday, 11 June, 13:00 - 13:45 |
| Presentation |
Poster
|
| Topic |
Signal Processing Theory and Methods: [OPT] Optimization Methods for Signal Processing |
| IEEE Xplore Open Preview |
Click here to view in IEEE Xplore |
| Virtual Presentation |
Click here to watch in the Virtual Conference |
| Abstract |
We propose a new randomized Bregman (block) coordinate de- scent (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 gen- erated sequence is a stationary point. Further, we show that the it- eration complexity of the proposed method is O(nε−2) to achieve ε-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ε−1). If, in addition, the objective is strongly convex (relative to the reference function), the global linear conver- gence rate is recovered. We also present the accelerated version of the RBCD method, which attains an O(nε−1/γ ) iteration complex- ity for the convex case, where the scalar γ ∈ [1, 2] is determined by the generalized translation variant of the Bregman distance. Con- vergence analysis without assuming the global Lipschitz-continuous (partial) gradient sets our results apart from the existing works in the composite problems. |
