An automatic system to detect equivalence between iterative algorithms

Understand

When are two algorithms the same? How can we be sure a recently proposed algorithm is novel, and not a minor twist 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.