Reviews: Online Convex Optimization with Unconstrained Domains and Losses

This is a practically important optimization problem, as many machine learning problems can be reduced to it (via online to batch conversion). The paper does a nice job explaining the history of this problem. This paper is the first that lifts the assumption to know an a priori bound on the norms of the gradients of the loss functions and achieves an almost linear dependency on the norm of the competitor. The authors prove a lower bound on regret of any algorithm (Theorem 2.1). The lower bound shows that regret can be exponential in the worst case if the norms of the gradients grow too rapidly.