2023/07/21 by Hazan, Elad, Megiddo, Nimrod · 1 citation
#FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Optimization and Control (math.OC)
paper · doi:10.48550/arxiv.2307.11668
A new algorithm for regret minimization in online convex optimization is described. The regret of the algorithm after T time periods is O(√(T log T)) - which is the minimum possible up to a logarithmic term. In addition, the new algorithm is adaptive, in the sense that the regret bounds hold not only for the time periods 1,…,T but also for every sub-interval s,s+1,…,t. The running time of the algorithm matches that of newly introduced interior point algorithms for regret minimization: in n-dimensional space, during each iteration the new algorithm essentially solves a system of linear equations of order n, rather than solving some constrained convex optimization problem in n dimensions and possibly many constraints.