Constructing Accelerated Algorithms for Large-scale Optimization - Framework, Algorithms, and Applications

Thumbnail Image
Journal Title
Journal ISSN
Volume Title
School of Electrical Engineering | Doctoral thesis (article-based) | Defence date: 2018-10-23
Degree programme
147 + app. 61
Aalto University publication series DOCTORAL DISSERTATIONS, 197/2018
A wide range of inverse problems and various machine learning tasks can be expressed as large-scale optimization problems with a composite objective structure, where the gradient of the smooth part has a global Lipschitz constant that is either impractical to compute, or considerably larger than the local values. The smooth part may be strongly convex as well, especially in certain medical imaging applications. The only fast methods that are able to address this entire class of problems are similar to or based on the black-box algorithms developed and analyzed by Nesterov using the estimate sequence mathematical framework. In this work, we introduce 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 the entire composite problem class. ACGM is endowed with an efficient dynamic Lipschitz constant estimation (line-search) procedure and features monotonicity. Motivated by the absence of an accurate complexity measure applicable to all first-order methods, we also introduce the wall-clock time unit (WTU). The WTU accounts for variations in algorithmic per-iteration complexity and more consistently reflects the performance of first-order methods in practice. 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. We confirm the superiority of ACGM within its class using an extensive simulation benchmark. ACGM also excels in terms of robustness and usability. In particular, ACGM is guaranteed to converge without requiring any quantitative prior information. Additional information, if available, leads to an improvement in performance at least on par with competing methods. Moreover, ACGM actually encompasses several popular algorithms for large-scale optimization, including Nesterov's Fast Gradient Method (FGM) and the Fast Iterative Shrinkage Thresholding Algorithm (FISTA), along with their most common variants. The efficiency and generality of ACGM enables new applications, particularly in ultrasound image reconstruction. In contrast with the unrealistic models of existing approaches, we propose two ultrasound image formation models based on spatially varying kernel convolution that account for arbitrary boundary conditions. We provide these models and their adjoints with resource efficient matrix-free implementations. Using either of our models, a variant of ACGM optimized for this task is able to efficiently reconstruct large ultrasound images with accuracy vastly superior to the state-of-the-art.
Supervising professor
Vorobyov, Sergiy A., Prof., Aalto University, Department of Signal Processing and Acoustics, Finland
acceleration, composite objective, estimate sequence, fast gradient method, first-order method, FISTA, large-scale optimization, line-search
Other note
  • [Publication 1]: Mihai I. Florea, Sergiy A. Vorobyov. A Robust FISTA-like Algorithm. In IEEE International Conference on Acoustics, Speech and Signal Processing, New Orleans, USA, pp. 4521–4525, Mar. 2017.
    DOI: 10.1109/ICASSP.2017.7953012 View at publisher
  • [Publication 2]: Mihai I. Florea, Sergiy A. Vorobyov. An Accelerated Composite Gradient Method for Large-scale Composite Objective Problems. Accepted for publication in IEEE Transactions on Signal Processing, May 2018.
  • [Publication 3]: Mihai I. Florea, Sergiy A. Vorobyov. A Generalized Accelerated Composite Gradient Method: Uniting Nesterov’s Fast Gradient Method and FISTA. Submitted to IEEE Transactions on Signal Processing, Oct. 2018.
  • [Publication 4]: Mihai I. Florea, Adrian Basarab, Denis Kouamé, Sergiy A. Vorobyov. Restoration of Ultrasound Images using Spatially-variant Kernel Deconvolution. In IEEE International Conference on Acoustics, Speech and Signal Processing, Calgary, Canada, pp. 796–800, Apr. 2018.
  • [Publication 5]: Mihai I. Florea, Adrian Basarab, Denis Kouamé, Sergiy A. Vorobyov. An Axially Variant Kernel Imaging Model Applied to Ultrasound Image Reconstruction. IEEE Signal Processing Letters, vol. 25, no.7, pp. 961–965, Jul. 2018.
    DOI: 10.1109/LSP.2018.2824764 View at publisher