Chebyshev polynomials meet Nevanlinna-Pick interpolation: An automated procedure for algorithm synthesis

Ibrahim Kurban Ozaslan, Tryphon Georgiou, Mihailo Jovanovic
Proceedings of The 8th Annual Learning for Dynamics and Control Conference, PMLR 331:1542-1557, 2026.

Abstract

The synthesis of optimization algorithms typically follows a design-first-analyze-later paradigm, a practice that often obscures fundamental performance limits and hampers the systematic design of algorithms operating near these limits. In this paper, we build on a recently proposed frequency-domain control framework that enables a principled approach to algorithm design, integrating the analysis and synthesis stages and thereby elucidating the fundamental performance boundaries. Specifically, we remove restrictive assumptions from recent prior work and extend the framework to encompass a broad class of strongly convex problems with equality constraints. This leads to a new family of algorithms that achieves a sharp trade-off between the number of matrix–vector multiplications per iteration and the convergence rate. Notably, one of the resulting algorithms attains the optimal lower bound on the total number of matrix-vector multiplications required to reach a prescribed accuracy.

Cite this Paper

BibTeX
@InProceedings{pmlr-v331-ozaslan26a, title = {Chebyshev polynomials meet Nevanlinna-Pick interpolation: An automated procedure for algorithm synthesis}, author = {Ozaslan, Ibrahim Kurban and Georgiou, Tryphon and Jovanovic, Mihailo}, booktitle = {Proceedings of The 8th Annual Learning for Dynamics and Control Conference}, pages = {1542--1557}, year = {2026}, editor = {Sukhatme, Gaurav and Lindemann, Lars and Tu, Stephen and Wierman, Adam and Atanasov, Nikolay}, volume = {331}, series = {Proceedings of Machine Learning Research}, month = {17--19 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v331/main/assets/ozaslan26a/ozaslan26a.pdf}, url = {https://proceedings.mlr.press/v331/ozaslan26a.html}, abstract = {The synthesis of optimization algorithms typically follows a design-first-analyze-later paradigm, a practice that often obscures fundamental performance limits and hampers the systematic design of algorithms operating near these limits. In this paper, we build on a recently proposed frequency-domain control framework that enables a principled approach to algorithm design, integrating the analysis and synthesis stages and thereby elucidating the fundamental performance boundaries. Specifically, we remove restrictive assumptions from recent prior work and extend the framework to encompass a broad class of strongly convex problems with equality constraints. This leads to a new family of algorithms that achieves a sharp trade-off between the number of matrix–vector multiplications per iteration and the convergence rate. Notably, one of the resulting algorithms attains the optimal lower bound on the total number of matrix-vector multiplications required to reach a prescribed accuracy.} }
Endnote
%0 Conference Paper %T Chebyshev polynomials meet Nevanlinna-Pick interpolation: An automated procedure for algorithm synthesis %A Ibrahim Kurban Ozaslan %A Tryphon Georgiou %A Mihailo Jovanovic %B Proceedings of The 8th Annual Learning for Dynamics and Control Conference %C Proceedings of Machine Learning Research %D 2026 %E Gaurav Sukhatme %E Lars Lindemann %E Stephen Tu %E Adam Wierman %E Nikolay Atanasov %F pmlr-v331-ozaslan26a %I PMLR %P 1542--1557 %U https://proceedings.mlr.press/v331/ozaslan26a.html %V 331 %X The synthesis of optimization algorithms typically follows a design-first-analyze-later paradigm, a practice that often obscures fundamental performance limits and hampers the systematic design of algorithms operating near these limits. In this paper, we build on a recently proposed frequency-domain control framework that enables a principled approach to algorithm design, integrating the analysis and synthesis stages and thereby elucidating the fundamental performance boundaries. Specifically, we remove restrictive assumptions from recent prior work and extend the framework to encompass a broad class of strongly convex problems with equality constraints. This leads to a new family of algorithms that achieves a sharp trade-off between the number of matrix–vector multiplications per iteration and the convergence rate. Notably, one of the resulting algorithms attains the optimal lower bound on the total number of matrix-vector multiplications required to reach a prescribed accuracy.
APA
Ozaslan, I.K., Georgiou, T. & Jovanovic, M.. (2026). Chebyshev polynomials meet Nevanlinna-Pick interpolation: An automated procedure for algorithm synthesis. Proceedings of The 8th Annual Learning for Dynamics and Control Conference, in Proceedings of Machine Learning Research 331:1542-1557 Available from https://proceedings.mlr.press/v331/ozaslan26a.html.

Related Material