Online Convex Optimization with Unconstrained Domains and Losses
We propose an online convex optimization algorithm (RESCALEDEXP) that achieves optimal regret in the unconstrained setting without prior knowledge of any bounds on the loss functions. We prove a lower bound showing an exponential separation between the regret of existing algorithms that require a known bound on the loss functions and any algorithm that does not require such knowledge. RESCALEDEXP matches this lower bound asymptotically in the number of iterations. RESCALEDEXP is naturally hyperparameter-free and we demonstrate empirically that it matches prior optimization algorithms that require hyperparameter optimization.
The paper studies online convex optimization over a Hilbert space and without any assumption on the loss functions (besides convexity). 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. (Previous papers either had suboptimal regret or assumed bounds on either the domain or the norm of the gradients.)  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.  The main result of the paper is an algorithm that roughly matches the lower bound. The algorithm is FTRL with regularizer (x+1)*log(x+1)-x and a clever learning rate schedule. Similar regularizers were considered before, however, the learning rate schedule is novel and very technical.  The paper resolves a COLT 2016 open problem (Francesco Orabona and David Pal "Open Problem: Parameter-Free and Scale-Free Online Algorithms") by proving a lower bound. At the same it opens a host of new open questions, as it is clear that the proposed algorithm is not the final answer to the unconstrained online convex optimization problem -- but that's great news and most welcome! (E.g. doubling method in algorithm can be hopefully removed. Or one could imagine algorithms and regret bounds that are better under certain assumptions on the growth of the norms of the gradients.)  As far as I can judge, the results are correct. I checked the lower bound in great detail. I checked the proof of the main theorem.  However, I didn't check the lemmas in the appendix.  -----  Suggestions for improvement:  1) Please add reference to COLT 2016 open problem by Francesco Orabona and David Pal, "Open Problem: Parameter-Free and Scale-Free Online Algorithms". It directly addresses the problem in the paper. You might get $100 award :)  2) The ratio |g_t|/L(t) is not defined for t=1. This is happens since L(1) is not defined. L(1) can be defined either as zero or minus infinity, but in the either case the ratio |g_t|/L(t) is not defined. More generally, the ratio will not be defined if first few g_t's are zero. Please explain what is meant. The largest confusion is in Theorem 2.1 where if the reader understands the ratio |g_1|/L(1) as plus infinity,  the theorem does not hold. (Algorithm 1 is fine.)  3) In proof of Theorem 2.1. Please use gradients g_t instead of losses l_t(w) so that it matches statement of the Theorem (which uses only g_t's). I.e. please replace l_t(w)= -w with g_t = -1 and l_t(w)=2Tw with g_t=2T.  4) Also, in the proof of Theorem 2.1, between lines 83 and 84. The third inequality is really an equality.  5) Line 107: In the inequality (M_t + |g|_{1:t}^2 >= ...), M_t should be replaced by M_{t+1}. (Or shift indices on g_t's by one.)  6) Algorithm 1: A very minor issue arises when first few g_t's are zero. There are some divisions by zero in the algorithm.   7) Theorem 3.2. Please don't write g_T <= L_{max} >= L. I understand what was meant, but other readers might not. In particular, it is not clear if g_T < L < L_{max} is allowed. Simply, write g_T <= L_{max} and L_{max} >= L.   8) Please number the theorems simply as 1,2,3. Also, I would call Theorem 3.2 a lemma, since it's just technical result.  9)  Though, experiments on neural networks are fashionable these days, the algorithm would shine on regression with absolute loss much better. 
This is a good and honest paper on an important practical problem (stated as an COLT 2016 open problem).  Research in this paper is a very big step towards a clean practical and optimal algorithm that will remove the need to "tune" learning rates for online convex unconstrained optimization problems.