Generalized Accelerated Optimization Framework for Big Data Processing
Loading...
URL
Journal Title
Journal ISSN
Volume Title
School of Electrical Engineering |
Doctoral thesis (article-based)
| Defence date: 2024-09-06
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Authors
Date
2024
Major/Subject
Mcode
Degree programme
Language
en
Pages
63 + app. 109
Series
Aalto University publication series DOCTORAL THESES, 166/2024
Abstract
Large-scale optimization problems arise in different fields of engineering and science. Due to the large number of parameters and different structures that these problems can have black-box first-order methods are widely used in solving them. Among the existing firstorder methods, the ones that are most widely used are different variants of Fast Gradient Methods (FGM). Such methods are devised in the context of the estimating sequences framework and exhibit desirable properties such as fast convergence rate and low per iteration complexity. In this Thesis, we devise new estimating sequences and show that they can be used to construct accelerated first-order methods. We start by considering the simplest case, i.e., minimizing smooth and convex objective functions. For this class of problems, we present a class of generalized estimating sequences, constructed by exploiting the history of the estimating functions that are obtained during the minimization process. Using these generalized estimating sequences, we devise a new accelerated gradient method and prove that it converges to a tolerated neighborhood of the optimal solution faster than FGM and other first-order methods. We then consider a more general class of optimization problems, namely composite objectives. For this class of problems, we introduce the class of composite estimating sequences, which are obtained by making use of the gradient mapping framework and a tight lower bound on the function that should be minimized. Using these composite estimating sequences, we devise a composite objective accelerated multi-step estimating sequence technique and prove its accelerated convergence rate. Last, embedding the memory term coming from the previous iterates into the composite estimating sequences, we obtain the generalized composite estimating sequences. Using these estimating sequences, we construct another accelerated gradient method and prove its accelerated convergence rate. The methods devised for solving composite objective functions that we introduce in this thesis are also equipped with efficient backtracking line-search strategies, which enable more accurate estimates of the step-size. Our results are validated by a large number of computational experiments on different types of loss functions, wherein both simulated and publicly available real-world datasets are considered. Our numerical experiments also highlight the robustness of our newly introduced methods to the usage of inexact values for of the Lipschitz constant and the strong convexity parameter.Description
Supervising professor
Vorobyov, Sergiy A., Prof., Aalto University, Department of Information and Communications Engineering, FinlandThesis advisor
Charalambous, Themistoklis, Prof., University of Cyprus, CyprusKeywords
big data, fast gradient methods, FGM
Other note
Parts
-
[Publication 1]: E. Dosti, S. A. Vorobyov, T. Charalambous. Generalizing Nesterov’s Acceleration Framework by Embedding Momentum Into Estimating Sequences: New Algorithm and Bounds. In IEEE International Symposium on Information Theory (ISIT), Helsinki, Finland, 1506-1511, June 2022.
DOI: 10.1109/ISIT50566.2022.9834684 View at publisher
- [Publication 2]: E. Dosti, S. A. Vorobyov, T. Charalambous. Embedding a Heavy-Ball type of Momentum into the Estimating Sequences. Journal Submission, March 2024.
-
[Publication 3]: E. Dosti, S. A. Vorobyov, T. Charalambous. A new accelerated gradient-based estimating sequence technique for solving large-scale optimization problems with composite structure. In IEEE 61st Conference on Decision and Control (CDC), Cancun, Mexico, 7516-7521, January 2023.
DOI: 10.1109/CDC51059.2022.9993313 View at publisher
-
[Publication 4]: E. Dosti, S. A. Vorobyov, T. Charalambous. A new class of composite objective multistep estimating sequence techniques. Signal Processing, 206, 108889, December 2022.
Full text in Acris/Aaltodoc: https://urn.fi/URN:NBN:fi:aalto-202301181218DOI: 10.1016/j.sigpro.2022.108889 View at publisher
- [Publication 5]: E. Dosti, S. A. Vorobyov, T. Charalambous. Generalizing the estimating sequences with memory terms for minimizing convex composite functions. Journal Submission, March 2024.