NeurIPS 2020

Regret Bounds without Lipschitz Continuity: Online Learning with Relative-Lipschitz Losses


Meta Review

This paper treats the problem of online convex optimization without Lipschitz continuity of the loss functions. The authors consider a variant of Lipschitz continuity called "relative Lipschitz continuity": this notion is originally due to Lu (2019) and involves a Bregman divergence instead of the standard norm in comparing nearby points. In this context, the authors prove the following results: - Under only relative Lipschitz continuity: an $O(sqrt{T})$ regret bound for follow-the-regularized-leader (FTRL) and a "stabilized" variant of the online mirror descent (OMD) algorithm. - Under relative continuity and relative strong convexity: an $O(logT)$ bound for the above algorithms. These results are similar to standard bounds in the literature for Lipschitz continuous / strongly convex functions. The extension to *relative* Lipschitz continuous / strongly convex functions was welcomed by the reviewers, but two major issues were identified: 1. An earlier ICLR paper by Antonakopoulos et al. (2020) already provides $O(\sqrt{T})$ bounds for FTRL and OMD under a closely related "Riemannian Lipschitz continuity" condition. The authors do not explain the relation between these two variants of Lipschitz continuity, and this can cause significant confusion. 2. Even though the reviewers acknowledged the significance of the authors' logarithmic regret bounds, the authors did not provide in the paper an example of a function that is simultaneously relatively Lipschitz continuous and relatively strongly convex in a non-standard way. This paper generated significant discussion during the review phase and I also reached out to an external referee for an additional opinion. The authors' rebuttal addressed point (1) but point (2) was left more open; however, the authors did provide a concrete example when I contacted them about this issue. This paper represents a "risk" in the following sense: the reviewers believe that there is sufficient merit in the authors' results (I agree with this). On the other hand, addressing the points identified above requires a rewrite of certain parts of the paper without the possibility of getting a second look at it. Given that the paper is overall well written and the required changes are "additive" instead of "restructuring" (which would be more difficult), there is consensus for an "accept" recommendation subject to the following changes: 1. The authors should include a precise definition of Riemannian Lipschitz continuity, how it relates to relative Lipschitz continuity, and a statement of the results of Antonakopoulos et al. for FTRL and OMD in order to facilitate the comparison with the paper's new results. 2. The authors should give a detailed description of how non-quadratic polynomials satisfy the relative strong convexity and Lipschitz continuity assumptions (over bounded domains) in a non-standard way. The extra page available for the camera ready should be more than enough to implement the above required additions. Subject to these changes, the paper would make a fine addition to the technical program of NeurIPS 2020.