Acceleration and Universality: Designing Fast, Parameter-free Algorithms for Convex Minimization

Abstract: Parameter-free optimization studies algorithms that adapt to the problem structure at hand. Specifically, such algorithms are capable of converging (preferably at an optimal rate) without requiring the knowledge of problem-dependent quantities. A central effort in the field is designing parameter-free algorithms that can solve different problems without any modifications. We refer to those algorithms as universal. In this presentation, I will talk about developing universal algorithms for constrained, convex minimization problems by introducing appropriate modifications to the extragradient method. 

First, I will introduce a first-order algorithm which achieves, for the first time, optimal convergence rates for compactly-constrained smooth/non-smooth objectives, in the presence of deterministic/stochastic first-order information, simultaneously. In other words, the method implicitly adapts to the noise levels in the gradient feedback and the smoothness/regularity of the objective function. 

Building upon similar techniques, I will present a second-order algorithm, which combines regularized Newton’s method with the extragradient template and an adaptive step-size. The latter algorithm adapts to the noise levels in both the first and second-order information, while achieving faster global rates than standard Newton-type algorithms.

Speaker Bio: Ali Kavis is a postdoctoral fellow at IFML, working jointly with Sujay Sanghavi and Aryan Mokhtari. He is currently interested in studying convex/non-convex minimization and min-max optimization problems while developing robust stochastic algorithms which have provably-optimal convergence guarantees. His research is partially funded by the Swiss National Science Foundation (SNSF). He received his Ph.D. degree from EPFL, Switzerland in 2023 and completed his B.Sc. degree in Computer Engineering at Bilkent University, Turkey in 2017.