Madeleine Udell

New Results on the Polyak Stepsize: Tight Convergence Analysis and Universal Function Classes

Abstract. In this paper, we revisit a classical adaptive stepsize strategy for gradient descent: the Polyak stepsize (PolyakGD), originally proposed in Polyak [ USSR Comput. Math. Math. Phys., 9 (1969), pp. 14–29]. We study the convergence behavior of PolyakGD from two perspectiv...

Algebraic characterization of equivalence between oracle-based iterative algorithms

Abstract 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...