Minimax Optimal Algorithms for Unconstrained Linear Optimization
We design and analyze minimax-optimal algorithms for online linear optimization games where the player's choice is unconstrained. The player strives to minimize regret, the difference between his loss and the loss of a post-hoc benchmark strategy. While the standard benchmark is the loss of the best strategy chosen from a bounded comparator set, we consider a very broad range of benchmark functions. The problem is cast as a sequential multi-stage zero-sum game, and we give a thorough analysis of the minimax behavior of the game, providing characterizations for the value of the game, as well as both the player's and the adversary's optimal strategy. We show how these objects can be computed efficiently under certain circumstances, and by selecting an appropriate benchmark, we construct a novel hedging strategy for an unconstrained betting game.
SUMMARY AND RELATED WORKS This paper is about 
      online linear optimization with an unconstrained comparator set (e.g., the 
      whole R^n space). Instead of trying to be competitive with the best linear 
      predictor x \in R^n, the aim is typically to be competitive with the best 
      penalized comparison vector. In this setting, and assuming that the convex 
      hull of the set of moves of the adversary is a full-rank polytope in R^n, 
      the authors provide stochastic techniques to derive the value of the game, 
      as well as the optimal strategies for the player and the adversary. These 
      abstract results are then applied to the one-dimensional case (a 
      straightforward extension to arbitrary dimension with 
      coordinate-decomposable games is also provided, but no thorough 
      application was worked out). Three 1-dimensional examples are studied in 
      details: linear optimization with a quadratic regularizer, non-stochastic 
      betting, and the standard online linear optimization problem on [-1,1] 
      (where the authors recover known results from their new general 
      technique). This paper is a continuation of a series of papers 
      that addressed adversarial online learning problems from a stochastic 
      viewpoint (Abernethy et al. COLT 2008, Abernethy et al. COLT 2009, Rakhlin 
      et al. NIPS 2012). It extends those works to the case of unconstrained 
      comparator sets. Note however that unconstrained online convex 
      optimization is definitely not new: papers like Duchi et al. (Composite 
      Objective Mirror Descent, COLT 2010) already provided regret upper bounds 
      for unconstrained comparison vectors. The novelty here is that this 
      setting is studied from an exact minimax viewpoint. OVERALL 
      ASSESSMENT My overall opinion about the paper is quite positive 
      for the following reasons: PROS 1) The paper is well 
      written and pleasant to read (all necessary intuitions are provided when 
      needed). Mathematics seem correct. 2) Though not ground-breaking, this 
      paper makes a further step towards the understanding of unconstrained 
      linear optimization. 3) The application to non-stochastic betting is 
      really nice, with a tight analysis and a simple algorithm. CONS 
      4) There are not sufficiently many applications of the abstract 
      results: Theorems 7 and 9 are nice for a warm-up, Theorem 8 is 
      interesting, but I would have also expected a study of other forms of 
      penalized regret like the ones already encountered with online mirror 
      descent. In particular, can the techniques of the present paper be adapted 
      to multi-dimensional games that are not coordinate-decomposable? Most 
      Bregman-divergence-based regularizations are indeed of this form. 5) 
      Contrary to what is announced on line 326, it seems that the constraint 
      that the player cannot bet more than what he owns is not imposed to the 
      game. I understand that it is possible to make sure that he loses no more 
      than 1$ at the end of the game, but what can be said on the whole path 
      from t=1 to t=T? OTHER COMMENTS 6) Related Work (Page 2): 
      references about unconstrained regret upper bounds with Online Mirror 
      Descent are missing. 7) Lines 105-107: the proposed 'alternative' is 
      not new: actually, the comparison of the loss to the best penalized loss 
      is known in statistics as an 'oracle inequality' from quite a long time 
      (see, e.g., the references in "Concentration Inequalities and Model 
      Selection", Massart, 2007). Parallely, in the machine learning community, 
      some works like the one of Vovk ("Competitive on-line statistics", 2001) 
      already began to formalize such ideas in the previous decade. 8) Line 
      141: hull(G)=hull(G') 9) Line 206: is the Lipschitz assumption really 
      needed? Is boundedness sufficient? 10) Statement of Theorem 3: I 
      suggest to move the fact that [we can find a full-rank set of corners 
      {g_1,...,g_{n+1}} of the polytope hull(G)] before the statement of Theorem 
      3. This is indeed straightforward in all subsequent applications. 
      (Furthermore, the term 'distinct' points is too weak, full-rank would be 
      more precise). 11) Line 262: it is implicitely assumed that V_{t+1} is 
      Lipschitz (or bounded? -> see above). 12) Line 288: the random 
      variable B was not defined earlier. 13) Theorem 7: recall that g_t \in 
      [-1,1]. 14) Title of Section 3.2: what does "all feasible sets" stand 
      for? 15) Line 341: please explain "bet everything every round ... 2^T" 
      16) Theorem 7 and the equation on line 683 are actually 
      straightforward by writing that B is the sum of independent Rademacher 
      variables. 17) Theorem 8: I think that the first exponential contains 
      (G_t-\tau)/sqrt{T} (no "-1" term), and that the exponent of the last term 
      is \tau-1 instead of \tau (the reason is that the authors used V_t instead 
      of V_{t+1}). 18) Several typos : argmin -> min (line 117), that 
      that -> that (line 121), Theorems 1 and 2 -> Corollary 2 (line 244), 
      V_t -> V_{t+1} (line 286), g_{1:T} -> g_{1:t} (lines 288 and 289), 
      -\partial L -> \partial L (line 292), *2* B sqrt{T} (line 338 + cf 
      consequences in the following lines), |G| \leq sqrt{T} (line 355), loss 
      functions -> losses (line 411) ADDITIONAL COMMENT AFTER THE 
      AUTHORS' REBUTTAL I thank the authors for their detailed answer. 
      It seems that point 5) can be taken care of. However, I regret that the 
      pratical implications of the abstract results are too narrow in the 
      submitted version, and that the amount of work needed to address the 
      (interesting) applications mentioned in the rebuttal is too large. The 
      proposed modified paper should have clear chances of acceptation in a 
      later conference.