pipette
ENEnglish

An lower bound for projection-free online learning with linear minimization oracles

Julien Weibel, Pierre Gaillard, Wouter Koolen, Adrien Taylor

Preprint

En palabras de los autores

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 (where is the horizon length). However, it remained an open question whether the regret of all OFW tunings scaled as . We answer that question, proving a universal worst-case regret lower bound for any projection-free algorithm that makes at most 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 .

Resultado principalEl resumen no menciona limitaciones.

Apareció: viernes, 30 de octubre. arXiv. Preprint, todavía sin revisión por pares.