An Accelerated Composite Gradient Method for Large-scale Composite Objective Problems
Loading...
Access rights
openAccess
URL
Journal Title
Journal ISSN
Volume Title
A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
Authors
Date
2019-01-15
Major/Subject
Mcode
Degree programme
Language
en
Pages
444 - 459
Series
IEEE Transactions on Signal Processing, Volume 67, issue 2
Abstract
Various signal processing applications can be expressed as large-scale optimization problems with a composite objective structure, where the Lipschitz constant of the smooth part gradient is either not known, or its local values may only be a fraction of the global value. The smooth part may be strongly convex as well. The algorithms capable of addressing this problem class in its entirety are black-box accelerated first-order methods, related to either Nesterov's Fast Gradient Method or the Accelerated Multistep Gradient Scheme, which were developed and analyzed using the estimate sequence mathematical framework. In this paper, we develop the augmented estimate sequence framework, a relaxation of the estimate sequence. When the lower bounds incorporated in the augmented estimate functions are hyperplanes or parabolae, this framework generates a conceptually simple gap sequence. We use this gap sequence to construct the Accelerated Composite Gradient Method (ACGM), a versatile first-order scheme applicable to any composite problem. Moreover, ACGM is endowed with an efficient dynamic Lipschitz constant estimation (line-search) procedure. We also introduce the wall-clock time unit (WTU), a complexity measure applicable to all first-order methods that accounts for variations in per-iteration complexity and more consistently reflects the running time in practical applications. When analyzed using WTU, ACGM has the best provable convergence rate on the composite problem class, both in the strongly and non-strongly convex cases. Our simulation results confirm the theoretical findings and show the superior performance of our new method.Description
Keywords
acceleration, composite objective, estimate sequence, first-order method, large-scale optimization, line-search, optimization algorithm
Other note
Citation
Florea, M I & Vorobyov, S A 2019, ' An Accelerated Composite Gradient Method for Large-scale Composite Objective Problems ', IEEE Transactions on Signal Processing, vol. 67, no. 2, 8443140, pp. 444 - 459 . https://doi.org/10.1109/TSP.2018.2866409