The Pareto Regret Frontier
Performance guarantees for online learning algorithms typically take the form of regret bounds, which express that the cumulative loss overhead compared to the best expert in hindsight is small. In the common case of large but structured expert sets we typically wish to keep the regret especially small compared to simple experts, at the cost of modest additional overhead compared to more complex others. We study which such regret trade-offs can be achieved, and how. We analyse regret w.r.t. each individual expert as a multi-objective criterion in the simple but fundamental case of absolute loss. We characterise the achievable and Pareto optimal trade-offs, and the corresponding optimal strategies for each sample size both exactly for each finite horizon and asymptotically.
This paper concerns regret against individual actions 
      in the full-information online prediction setting. Instead of trying to 
      bound the regret uniformly for all experts (actions), the work gives 
      characterization of what "regret profiles" are achievable for the most 
      basic case of binary prediction with absolute loss. The author(s) call a 
      profile < r0,r1 > T-realizable if there exists an algorithm that 
      guarantees regret r0 and r1 against constant predictions 0 and 1, 
      respectively, given any (non-oblivious) adversary. An example for a 
      trivial T-realizable profile is < 0,T >. The paper exactly 
      (even constants) characterizes the Pareto-front of all T-realizable 
      profiles for any T in the basic case of two actions and absolute loss. 
      Then they use the result to prove an asymptotic bound. The paper also 
      provides algorithms that achieve the realizable profiles. The 
      paper is well written, the problem is well motivated, the proofs seem 
      sound. The problem of satisfying non-uniform regret bounds is an 
      interesting new line of research. This paper takes the first steps in this 
      new direction. Some comments: In Definition 1, the 
      paper reveals that the adversary model considered is the non-oblivious 
      (adaptive) one. I would prefer if it was mentioned more explicitly and at 
      an earlier point in the paper. Especially because Lemma 3 does not go 
      through for oblivious adversaries. I found the second part of 
      Theorem 6 confusing. First I thought it was a full description of the 
      algorithm that achieves the vertices of the Pareto-front. Only later I 
      realized that it is just some fact about what the algorithm does at three 
      particular time steps. Maybe say this explicitly or just leave out this 
      part. How do the new bounds relate to the old uniform regret bound 
      of \sqrt{T/2 \ln K}? I would have liked to see some discussion about this, 
      especially since the above bound is asymptotically optimal. The 
      algorithms that prove the upper bounds seem to be highly inefficient 
      computationally. It would be nice to have algorithms that are more 
      efficient and have regret bounds close to the optimal 
      ones.