Parameter-free OCO Algorithms
Parameter-free OCO algorithms are motivated by a desire to avoid choosing a step size and can achieve optimal theoretical regret bounds [1]}, [2]}, [3]}, [4]}, [5]}, [6]}, [7]}, [8]}, [9]}, [10]}, [11]}, [12]}, [13]}, [14]}. Some of them are based on the FTRL framework [15]}, [16]}, [17]} (sometimes indirectly through methods such as coin-betting). The closest work to our algorithms is the CODE algorithm [18]} which is the first attempt to combine parameter-free methods with truncated losses. Inspired by the Importance Weight Awareness updates in [19]}, CODE models the optimization algorithm with an ODE, and solves the ODE in a closed form to make infinitely many infinitesimal parameter-free updates on truncated losses. While CODE solves the ODE in closed form, it does not have any theoretical guarantee. In our work, in each step \(t\) , we consider the loss in two points only: on the current prediction and the updated one. This gives rise to an implicit equation that we can solve for truncated losses and to an optimal regret guarantee.
