An (T 3/4) lower bound for projection-free online learning with linear minimization oracles
stat.ML, cs.LG
Submitted: 2026-10-27
Updated: 2026-10-27
License: http://creativecommons.org/licenses/by/4.0/
The gist: This work considers projection-free online learning algorithms with linear minimization oracles for handling the decision set.
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(T 3/4 m-1/4, sqrt T).
Related papers
- Uniform-in-Time Weak Propagation-of-Chaos in Shallow Neural Networks
- Diffusion Models Observe Only Gradients: A Geometric Perspective on Score Matching Errors
- Quantifying Error Propagation and Model Collapse in Diffusion Models
- Behavior of prediction performance metrics with rare events
- Statistical Inference and Learning for Shapley Additive Explanations (SHAP)
- Control Variate Design for Score-Function Gradient Estimators in Importance-Weighted Variational Inference