UBC Computer Science researchers win Test of Time Award for influential paper at leading machine learning conference
Paper by Dr. Schmidt and former trainees Hamed Karimi and Julie Nutini recognized at ECML PKDD 2026 for lasting impact in past decade
UBC Computer Science Professor Mark Schmidt and his former trainees Hamed Karimi and Julie Nutini have been awarded the Test of Time Award at the 2026 European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD), which took place Sept 7-11 in Naples, Italy. The paper established a framework for proving the fast convergence of gradient methods. In the past 10 years, the paper has been cited over 2000 times by researchers who have used it to re-derive guarantees for nearly every standard optimization method and in new areas such as reinforcement learning and sampling from diffusion models.
“When we wrote the paper in 2016, we genuinely didn’t expect it to make a splash,” says Dr. Karimi, a former postdoctoral fellow in Dr. Schmidt’s group and current senior applied scientist at Amazon. “The paper being recognized a decade later means a lot, especially shared with Julie and Mark and rooted in my time at UBC.”
A little more than a decade ago, Dr. Schmidt was preparing to teach in his CPSC 340 (Machine Learning and Data Mining) class, thinking about how students will learn about gradient descent — an algorithm to train machine learning models. While the textbook results show that gradient descent will be faster for strongly convex functions, Dr. Schmidt was frustrated that there were no machine learning models that were actually strongly convex.
“We’ve got this beautiful theory, but it didn't apply to anything,” says Dr. Schmidt. “I didn’t want to teach this assumption that never satisfied anything — I wanted something more realistic.”
So he asked his then postdoctoral fellow Hamed Karimi and PhD student Julie Nutini to help him find an assumption that gave a simpler proof showing that gradient descent has a linear convergence rate, so that it could be taught in class. After a few weeks of working on a whiteboard, they came back with an elegant condition that gives a three-line proof. They later discovered that the condition had not only already existed, but had been published in Russian, by mathematician Boris Polyak, and separately in French, by Polish mathematician Stanisław Łojasiewicz — but was forgotten for 50 years.
Dr. Schmidt and his team wrote up the paper, coining their condition the “Polyak-Lojasiewicz condition.” (The team later discovered that the condition had also been published in German in 1963 by Tadeusz Leżański). While the paper was initially rejected because it centered around a condition that was not new, it eventually found a home at ECML after further revisions.
“The paper was difficult to write because the contribution was unconventional,” says Dr. Karimi. “A paper whose contribution was clarity is genuinely hard to score.”
The Polyak-Lojasiewicz condition gave a simple proof of fast convergence and was the weakest condition in the non-convex setting — something that other researchers spent the last 25 years proposing conditions to fix. Their paper also included a proximal condition to simplify proofs for many standard algorithms used in machine learning.
Over the last decade, they saw that their condition was being used in different areas, from studying algorithms to explaining why deep learning models like ChatGPT learn so fast. The Polyak-Lojasiewicz condition ultimately provided new insights and rates on some very well-studied problems such as least squares and logistic regression.
“It’s amazing to see how many directions this has gone,” says Dr. Schmidt. “It really shows that people appreciate the simple things, which is not always easy to publish."