EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Algebraic characterization of equivalence between oracle-based iterative algorithms

Laurent Lessard, Madeleine Udell

Mathematical Programming · 17.08.2026

DOI: 10.1007/s10107-026-02402-9 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Mathematical Programming, online erschienen am 17.08.2026. Verfasst von Laurent Lessard und 1 weiteren Autor:innen. Die Arbeit nennt 60 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Northeastern University USA.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

When are two algorithms the same? How can we be sure a recently proposed algorithm is novel, and not a minor variation on an existing method? In this paper, we present a framework for reasoning about equivalence between a broad class of iterative algorithms, with a focus on algorithms designed for convex optimization. We propose several notions of what it means for two algorithms to be equivalent, and provide computationally tractable means to detect equivalence. Our main definition, oracle equivalence, states that two algorithms are equivalent if they result in the same sequence of calls to the function oracles (for suitable initialization). Borrowing from control theory, we use state-space realizations to represent algorithms and characterize algorithm equivalence via transfer functions. Our framework can also identify and characterize equivalence between algorithms that use different oracles that are related via a linear fractional transformation. Prominent examples include linear transformations and function conjugation. To support the paper, we have developed a software package named Linnaeus that implements the framework to identify other iterative algorithms that are equivalent to an input algorithm.

Förderung

  • Northeastern University USA

Zitieren

APA

Lessard, L., & Udell, M. (2026). Algebraic characterization of equivalence between oracle-based iterative algorithms. Mathematical Programming. https://doi.org/10.1007/s10107-026-02402-9

Vancouver

Lessard L, Udell M. Algebraic characterization of equivalence between oracle-based iterative algorithms. Mathematical Programming. 2026. doi:10.1007/s10107-026-02402-9

BibTeX
@article{Lessard2026,
  author = {Lessard, Laurent and Udell, Madeleine},
  title = {Algebraic characterization of equivalence between oracle-based iterative algorithms},
  journal = {Mathematical Programming},
  year = {2026},
  doi = {10.1007/s10107-026-02402-9}
}
Kostenlos starten →