Depending on the assumptions on the feasible set and the losses, there are many OCO algorithms that achieve optimal regret.
The two main families of OCO algorithms are based on Online Mirror Descent (OMD) [1]}, [2]} and Follow-The-Regularized-Leader (FTRL) [3]}, [4]}, [5]}. For the particular case where \(V\equiv \mathbb {R}^d\) , parameter-free algorithms are minimax optimal [6]}, [7]}. The key feature of parameter-free algorithms is that the \(\operatorname{Regret}_T({u})\)  scales nearly linearly in \(\Vert {u}\Vert \) , and is constant for \({u}=0\) . This guarantee is only obtainable by popular strategies like Online Subgradient Descent [8]} if the learning rate is carefully tuned to the (unknown!) value of \(\Vert {u}\Vert \) . This lack of tuning learning rates motivates the name “parameter-free”. Yet, even this favorable minimax optimality might not be satisfactory.
