An Accelerated Coordinate Gradient Descent Algorithm for Non-separable Composite Optimization

Aviad Aberdam () and Amir Beck ()
Additional contact information
Aviad Aberdam: Technion - Israel Institute of Technology
Amir Beck: Tel Aviv University

Journal of Optimization Theory and Applications, 2022, vol. 193, issue 1, No 12, 219-246

Abstract: Abstract Coordinate descent algorithms are popular in machine learning and large-scale data analysis problems due to their low computational cost iterative schemes and their improved performances. In this work, we define a monotone accelerated coordinate gradient descent-type method for problems consisting of minimizing $$f+g$$ f + g , where f is quadratic and g is nonsmooth and non-separable and has a low-complexity proximal mapping. The algorithm is enabled by employing the forward–backward envelope, a composite envelope that possess an exact smooth reformulation of $$f+g$$ f + g . We prove the algorithm achieves a convergence rate of $$O(1/k^{1.5})$$ O ( 1 / k 1.5 ) in terms of the original objective function, improving current coordinate descent-type algorithms. In addition, we describe an adaptive variant of the algorithm that backtracks the spectral information and coordinate Lipschitz constants of the problem. We numerically examine our algorithms on various settings, including two-dimensional total-variation-based image inpainting problems, showing a clear advantage in performance over current coordinate descent-type methods.

Keywords: Coordinate gradient descent; Composite functions; Forward–backward envelope; Convex optimization; 90C25; 65K05 (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10957-021-01957-1 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joptap:v:193:y:2022:i:1:d:10.1007_s10957-021-01957-1

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-021-01957-1

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().