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

Tutkimustuotos: Doctoral ThesisCollection of Articles


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.
Julkaisun otsikon käännösConstructing Accelerated Algorithms for Large-scale Optimization - Framework, Algorithms, and Applications
Myöntävä instituutio
  • Aalto-yliopisto
  • Vorobyov, Sergiy, Valvoja
Painoksen ISBN978-952-60-8226-4
Sähköinen ISBN978-952-60-8227-1
TilaJulkaistu - 2018
OKM-julkaisutyyppiG5 Tohtorinväitöskirja (artikkeli)

Sormenjälki Sukella tutkimusaiheisiin 'Constructing Accelerated Algorithms for Large-scale Optimization - Framework, Algorithms, and Applications'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

  • Siteeraa tätä