RECORD
Analysis of Optimization Algorithms via Sum-of-Squares
Optimization and Control · Submitted 11 Jun 2019
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim 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.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
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 result{s} for noisy gradient descent with inexact line search methods (Armijo, Wolfe, and Goldstein).
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | We introduce a new framework for unifying and systematizing the performance analysis of first-order black-box optimization algorithms for unconstrained convex minimization. | contribution 1.00 | 0.95 | 0.15 | asserted 1.00 |
| s1 | The low-cost iteration complexity enjoyed by first-order algorithms renders them particularly relevant for applications in machine learning and large-scale data analysis. | background 1.00 | 0.06 | 0.03 | asserted 0.98 |
| s2 | 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. | method 0.56 | 0.93 | 0.18 | asserted 1.00 |
| s3 | 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. | result 0.54 | 0.76 | 0.09 | asserted 0.98 |
| s4 | Program., 145(1):451--482, 2014], a powerful framework for determining convergence rates of first-order optimization algorithms. | background 0.44 | 0.18 | 0.08 | asserted 0.92 |
| s5 | 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. | interpretation 0.98 | 0.42 | 0.45 | hedged possibility 0.64 |
| s6 | To determine analytical rate bounds, in this work we use the first level of the SOS hierarchy and derive new result{s} for noisy gradient descent with inexact line search methods (Armijo, Wolfe, and Goldstein). | contribution 0.56 | 0.96 | 0.22 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v4
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original 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 result{s} for noisy gradient descent with inexact line search methods (Armijo, Wolfe, and Goldstein).
Human review
How the literature uses it
1 arXiv paper cite this in 1 sentence
What it cites · 1 sentence without a confident label
Cites as background 5 papers
-
The value of the PEP framework has been illustrated in a series of recent works that can broadly categorized into the study of worst-case guarantees for first-order optimization algorithms [ref] , the design of optimal methods [ref] , and more recently, worst-case guarantees for solving various monotone inclusion problems [ref] .
Worst-case convergence analysis of inexact gradient and Newton methods through semidefinite programming performance estimation · Related work · 0.94
-
The value of the PEP framework has been illustrated in a series of recent works that can broadly categorized into the study of worst-case guarantees for first-order optimization algorithms [ref] , the design of optimal methods [ref] , and more recently, worst-case guarantees for solving various monotone inclusion problems [ref] .
Optimizing the Efficiency of First-Order Methods for Decreasing the Gradient of Smooth Convex Functions · Related work · 0.94
-
The value of the PEP framework has been illustrated in a series of recent works that can broadly categorized into the study of worst-case guarantees for first-order optimization algorithms [ref] , the design of optimal methods [ref] , and more recently, worst-case guarantees for solving various monotone inclusion problems [ref] .
Operator Splitting Performance Estimation: Tight contraction factors and optimal parameter selection · Related work · 0.94
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.