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

概要

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} \})$.

参考リンク

• Paper ↗

リンク先のライセンス・再現性・データ条件をご確認ください。自動分類や実装の目安は保証ではありません。

実装を始めるプロンプト

参考リンクを確認したうえで、次の内容をコピーして利用できます。

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

# 概要
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…

# 原典
https://arxiv.org/abs/2610.37845

上記の手法を実装してください。実行前に依存関係とライセンスを確認してください。