NeurIPS 2020

Better Full-Matrix Regret via Parameter-Free Online Learning

Meta Review

The reviewers were convinced that the reduction from Cutkosky and Orabona, 2018 does not solve the problem already, and agreed on the theoretical contribution of this work. We believe that the paper will benefit from a revision with the following two improvements: 1) include detailed discussions related to Cutkosky and Orabona, 2018 as mentioned in the rebuttal; 2) conduct experiments to showcase the practical advantages of the proposed algorithms compared to existing ones such as AdaGrad, MetaGrad [1], and those from [2,3]. Indeed, one of the key motivations of the paper is to explain the practical success of AdaGrad and to develop an even better parameter-free version, and the results would have been much more convincing if some experimental evidence was included as well. [1] Tim van Erven and Wouter M. Koolen. Metagrad: Multiple learning rates in online learning. 2016. [2] Haipeng Luo, Alekh Agarwal, Nicolò Cesa-Bianchi and John Langford. Efficient Second Order Online Learning via Sketching. 2016. [3] Zakaria Mhammedi and Wouter M. Koolen. Lipschitz and Comparator-Norm Adaptivity in Online Learning. 2020.