Dimension-Free Exponentiated Gradient
I present a new online learning algorithm that extends the exponentiated gradient framework to infinite dimensional spaces. My analysis shows that the algorithm is implicitly able to estimate the L 2 norm of the unknown competitor, U , achieving a regret bound of the order of O(U log(U T + 1))
, achievable without knowing U . For this analysis, I introduce novel tools for algorithms with time-varying regularizers, through the use of local smoothness. Through a lower bound, I also show that the algorithm is optimal up to log(U T ) term for linear and Lipschitz losses.
SUMMARY AND RELATED WORKS This paper is about 
      online linear regression with Lipschitz losses over L2-balls. In this 
      setting, the authors introduce and study a new online algorithm that 
      achieves a regret bound of the order of U*sqrt{T}*log(UT) after T rounds 
      over any L2-ball of radius U, without knowing U in advance. This algorithm 
      is close in spirit to that of Streeter and McMahan [21] (NIPS 2012), with 
      however an interesting important difference: the regret bound of Theorem 1 
      is dimension-free in the sense that it does not depend on the dimension d 
      of the input vectors x_t (note however that the algorithm of Streeter and 
      McMahan was primarily designed for the L1-norm rather than for the 
      L2-norm). This dimension-free bound suggests that the algorithm could be 
      used in infinite dimension, which is useful for kernel regression. Another 
      related algorithm is the standard gradient descent (see, e.g., Kivinen And 
      Warmuth 1997 and Cesa-Bianchi 1999). Gradient descent can also achieve a 
      dimension-free regret bound of the order of U*sqrt{T}, but at the price of 
      knowing U beforehand. In the more realistic case when U is unknown, the 
      regret bound of Gradient Descent has a worse dependency in U (U^2*sqrt{T} 
      instead of U*sqrt{T}). On the contrary, the algorithm introduced in the 
      present paper is adaptive to the unknown radius U (up to log factors). In 
      a second part of the paper, the authors prove that their regret bound is 
      optimal up to log factors, but this is in a rather weak sense (see below). 
      They finally carry out some simulations to compare their algorithm to 
      Gradient Descent with different values of the regularization parameter. 
      OVERALL ASSESSMENT My overall opinion about the paper 
      is positive for the following reasons: PROS 1) To the best 
      of my knwoledge, I think that Algorithm 1 is the first one that achieves 
      (up to log factors) a regret bound of order U sqrt{T} without knowing U 
      beforehand, via a sequential time-varying tuning of its parameters. Since 
      the rate U sqrt{T} is optimal for any fixed U and for linear losses (at 
      least for algorithms that don't have access to x_t, cf. [1]), and since 
      the ideas underlying Algorithm 1 are far from trivial, Theorem 1 should be 
      of interest to quite a few people in the machine learning community. 
      2) Comparisons to the literature are precise and honnest, which is a 
      nice quality. CONS Mathematical concerns and significance: 
      3) Proof of Theorem 1: the proof relies on Lemma 1, where it is 
      assumed that the functions f^*_t are twice differentiable. Since this is 
      not the case for the functions used in Theorem 1 (because of the null 
      vector), mathematical details are missing. In particular, what happens if 
      the null vector lies in the segment [\theta_t,\theta_{t+1}] at some round 
      t? Please provide careful details about how you carry out the Taylor 
      expansion of f^*_t around \theta_t. 4) Theorem 2: a) The lower 
      bound is not as strong as one could expect, since it only holds for a 
      fixed vector u (whose norm is roughly of order sqrt{T}). What happens for 
      other vectors u? It would be better to have some information, e.g., for 
      the case when \norm[u] -> 0 or when \norm[u] -> +\infty. b) In 
      the proof of Theorem 2, I think that to get E[\sum_t w_t^T z_t] = 0 on 
      line 594, the authors implicitely used the fact that w_t is independent 
      from z_t. This is not the case for all algorithms in the online protocol 
      described at the beginning of the paper (the learner can not only use the 
      past examples, but he has also access to x_t before making his decision). 
      Therefore, the lower bound of Theorem 2 holds on a smaller class of 
      algorithms: those that are only allowed to access to x_t through the norm 
      \norm[x_t] (since w_t and z_t are then indeed independent). Please write 
      this explicitely. Writing style: 5) As such, the proofs are 
      very technical and suffer from a lack of intuitions. Furthermore, the 
      proof style could really be improved: some explanations are missing (e.g., 
      simple arguments to carry out the calculations) and some details are not 
      at the right place (e.g., the particular shape of f_t^* should be made 
      precise right after Lemma 1, otherwise, we have to wait until Lemma 2 and 
      line 303 to understand the relationship between Algorithms 1 and 2). 
      OTHER COMMENTS 6) Absract: is Algorithm 1 really an extension 
      of the Exponentiated Gradient algorithm? I think that it is simply similar 
      in shape. The verb 'extends' is thus midleading. 7) Introduction: the 
      second paragraph is probably difficult to read for the unfamiliar reader. 
      Please state the online decision protocol and the definition of online 
      mirror descent (even in an informal way). 8) Line 44: a division by 
      sqrt{T} is missing in the Euclidean regularizer (or, better: the regret 
      bound is O(u^2/eta + eta*T), which is perhaps more standard). 9) Line 
      82: add the reference [8] to [3,17]. 10) The term 'sample' for x_t is 
      not appropriate: you could use 'input vector/data/covariates' instead. 
      11) Beginning of Section 2: the space Y is just the real line (so 
      write it explicitely), and X is a Euclidean vector space (maybe Hilbert 
      space?). Furthermore, the notation w_t^T x_t seems only appropriate when X 
      is finite-dimensional. 12) Section 3: since all references about 
      convex analysis are on finite-dimensional vector spaces, the extension to 
      infinite-dimensional spaces should be clarified (but I agree that it is 
      very natural). 13) Line 175: the optimality of the rate U*sqrt{T} was 
      only proved for algorithms that don't use the knowledge of x_t (cf. [1]). 
      14) Line 179: what about the upper bound on a? 15) Lemma 1: please 
      write that the norm of the Hessian is its spectral norm. 16) Line 221: 
      \norm[z_t]^2_{f_t} -> \norm[z_t]^2 17) Lines 239-241: please 
      explain briefly or point to the proof. 18) Lemma 2: it only holds for 
      \theta \neq 0 (see also Comment 3 above). 19) Line 269: w_r -> 
      \theta_r 20) Proof of Theorem 1: to help the reader, you could 
      explicitely structure the proof as follows: Case 1 = "\norm[\theta_t] > 
      ...", Case 2 = "\norm[\theta_t] \leq ...", and explain right from the 
      beginning which case corresponds to which term in the minimum of the bound 
      of Lemma 1. 21) Line 324: Lemma 3 is used with p=2 a^2 AND M=1/a. 
      22) Line 343: this is an equality. 23) Line 361: The sentence 'We 
      now use ...' should be postponed right after Equation (3). 24) Line 
      366: several typos: there are two L factors instead of one in the second 
      term of the right-hand side; \beta -> \beta_t; a factor of L is missing 
      after the equal sign. 25) The lower bound of Theorem 2 is for the 
      linear loss functions \ell_t(x) = - x. Please write this explicitely. 
      26) Several typos: 'vectorial space" -> 'vector space' (several 
      times in the paper), 'supplemental material' -> 'supplementary 
      material' (idem), 'derivative' -> 'derivatives' (line 270), 'the f(x)' 
      -> 'f(x)' (line 511). ---------------------------------------- 
      POST-REBUTTAL ADDENDUM I'd like to thank the authors for their 
      feedback. Since they addressed my two main questions very precisely and 
      ruled out concerns 3) and 4), I clearly recommend acceptance. When 
      polished (through the reviewers' suggestions), the paper will be a very 
      nice one. NB: I noted two other typos: a ||w|| is missing after 
      \alpha_t on line 303, and u_t should be replaced with z_t on line 
      496.