Hamed Karimi wins award for influential machine learning theory paper

A decade-old paper earns recognition

Karimi received the award in Naples at the European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, known as ECML PKDD. The award recognizes research published a decade earlier that has had a lasting impact.

The winning paper, Linear convergence of gradient and proximal-gradient methods under the Polyak, Łojasiewicz condition, was written by Karimi with Julie Nutini and Mark Schmidt while Karimi was a postdoctoral researcher at the University of British Columbia. According to Amazon Science, the paper has been cited over 2,000 times and has appeared in graduate textbooks.

“When we wrote the paper in 2016, we genuinely didn’t expect it to make a splash,” Karimi said. “We did not know that the result would become part of the way researchers analyze optimization in machine learning.”

Explaining why optimization works

Machine learning models are trained by adjusting parameters to reduce a loss function, which measures the difference between model outputs and labeled training data. Gradient descent and related methods repeatedly update those parameters in the direction that reduces the loss.

Mathematical theory traditionally guaranteed a fast, linear rate of convergence for strongly convex functions. Amazon Science describes this geometry as a steep bowl with one lowest point. Modern machine learning problems can instead have flat valley floors, particularly when training data are redundant and models have disproportionately more parameters than training data.

Those problems can still be successfully trained with gradient descent, but earlier theory could not explain why or specify how quickly. Karimi and his coauthors showed that the Polyak, Łojasiewicz condition, an inequality published independently in 1963 by Boris Polyak and Stanisław Łojasiewicz, can provide that guarantee without strongly convex geometry. The proof is only three lines long.

A framework for multiple training methods

The paper organized previously separate approaches for optimization problems with weaker conditions, showing how their assumptions relate. It identified the Polyak, Łojasiewicz condition as the weakest known condition that still guarantees a linear rate for the functions studied.

The researchers also introduced a version of the condition for problems combining smooth and nonsmooth functions. They then applied the analysis to coordinate descent, sign gradient descent, and stochastic gradient descent. In each case, they recovered the convergence rate previously known only for strongly convex functions.

According to Amazon Science, variants of the approach now support convergence results in reinforcement learning, optimization over curved parameter spaces, and the sampling methods behind diffusion models. The result gives researchers a short template for analyzing new training methods, helping connect the performance of algorithms used in practice with what mathematical theory can prove.