Analysis of Optimization Algorithms via Sum-of-Squares

Sandra S. Y. Tan (), Antonios Varvitsiotis () and Vincent Y. F. Tan ()
Additional contact information
Sandra S. Y. Tan: National University of Singapore
Antonios Varvitsiotis: National University of Singapore
Vincent Y. F. Tan: National University of Singapore

Journal of Optimization Theory and Applications, 2021, vol. 190, issue 1, No 3, 56-81

Abstract: Abstract We introduce a new framework for unifying and systematizing the performance analysis of first-order black-box optimization algorithms for unconstrained convex minimization. The low-cost iteration complexity enjoyed by first-order algorithms renders them particularly relevant for applications in machine learning and large-scale data analysis. Relying on sum-of-squares (SOS) optimization, we introduce a hierarchy of semidefinite programs that give increasingly better convergence bounds for higher levels of the hierarchy. Alluding to the power of the SOS hierarchy, we show that the (dual of the) first level corresponds to the performance estimation problem (PEP) introduced by Drori and Teboulle (Math Program 145(1):451–482, 2014), a powerful framework for determining convergence rates of first-order optimization algorithms. Consequently, many results obtained within the PEP framework can be reinterpreted as degree-1 SOS proofs, and thus, the SOS framework provides a promising new approach for certifying improved rates of convergence by means of higher-order SOS certificates. To determine analytical rate bounds, in this work, we use the first level of the SOS hierarchy and derive new results for noisy gradient descent with inexact line search methods (Armijo, Wolfe, and Goldstein).

Keywords: Sum-of-squares; Semidefinite programming; Performance estimation problem (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10957-021-01869-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joptap:v:190:y:2021:i:1:d:10.1007_s10957-021-01869-0

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-021-01869-0

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().