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

Research output: ThesisDoctoral ThesisCollection of Articles

Abstract

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.
Translated title of the contributionConstructing Accelerated Algorithms for Large-scale Optimization - Framework, Algorithms, and Applications
Original languageEnglish
QualificationDoctor's degree
Awarding Institution
  • Aalto University
Supervisors/Advisors
  • Vorobyov, Sergiy, Supervising Professor
Publisher
Print ISBNs978-952-60-8226-4
Electronic ISBNs978-952-60-8227-1
Publication statusPublished - 2018
MoE publication typeG5 Doctoral dissertation (article)

Keywords

  • acceleration
  • composite objective
  • estimate sequence
  • fast gradient method
  • first-order method
  • FISTA
  • large-scale optimization
  • line-search

Fingerprint Dive into the research topics of 'Constructing Accelerated Algorithms for Large-scale Optimization - Framework, Algorithms, and Applications'. Together they form a unique fingerprint.

Cite this