Projection-free online learning methods face inherent speed limits

An $Ω(T^{3/4})$ lower bound for projection-free online learning with linear minimization oracles

Machine Learning

Summary

This paper studies how fast certain computer algorithms can learn decisions over time without relying on traditional projection steps, focusing on a tool called a linear minimization oracle. The authors prove that all such methods have a fundamental limitation on how quickly they can improve, measured by a quantity called regret, which must grow at least as fast as the time raised to the 3/4 power. They also show a way to improve performance by allowing multiple oracle calls per decision, and provide matching upper bounds for this case. This gives new insights into the trade-offs involved in these learning algorithms and clarifies what is possible with current techniques.

What this means in practice

  • For machine learning engineers: Design and analyze online decision algorithms that avoid costly projections while understanding their inherent speed limits due to oracle call constraints.
  • For operations research teams: Develop projection-free optimization methods for large-scale problems where multiple oracle calls per step can reduce long-term error growth.

A theory result. No direct application yet.

Authors

Julien Weibel, Pierre Gaillard, Wouter Koolen, Adrien Taylor

Abstract

This work considers projection-free online learning algorithms with linear minimization oracles for handling the decision set. For Online Frank--Wolfe (OFW), regret upper bounds were already known for specific OFW tunings [Hazan and Kale, 2012, Hazan, 2016] which scaled as $T^{3/4}$ (where $T$ is the horizon length). However, it remained an open question whether the regret of all OFW tunings scaled as $T^{3/4}$. We answer that question, proving a universal worst-case regret lower bound $Ω(T^{3/4} m^{-1/4})$ for any projection-free algorithm that makes at most $m$ linear minimization oracle calls per round. The analysis suggests an extended OFW to resort to multiple linear optimizations per round, for which we prove a regret upper bound $O(\max \{ T^{3/4} m^{-1/4}, \sqrt{T} \})$.
View PDFOpen arXiv