Online Learning with a Hint
We study a variant of online linear optimization where the player receives a hint about the loss function at the beginning of each round. The hint is given in the form of a vector that is weakly correlated with the loss vector on that round. We show that the player can benefit from such a hint if the set of feasible actions is sufficiently round. Specifically, if the set is strongly convex, the hint can be used to guarantee a regret of O(log(T )), and if the set is q-uniformly convex for q ∈ (2, 3), the hint can be used to guarantee a regret of o( √ T ). In contrast, we establish Ω( √ T ) lower bounds on regret when the set of feasible actions is a polyhedron.
The paper concerns online linear optimization where at each trial, the player, prior to prediction, receives a hint about the loss function. The hint has a form of a unit vector which is weakly correlated with the loss vector (its angle's cosine with loss vector is at least alpha). The paper shows that:
- When the set of feasible actions is strongly convex, there exists an algorithm which gets logarithmic regret (in T). The algorithm is obtained by a reduction to the online learning problem with exp-concave losses. The bound is unimprovable in general, as shown in the Lower Bounds section.
- When the set of actions is (C,q)-uniformly convex (the modulus of uniform convexity scales as C eps^q), and the hint is constant among trials, a simple follow-the-leader algorithm (FTL) achieves a regret bound which improves upon O(sqrt(T)) when q is between 2 and 3. This is further extended to the case when the hint comes from a finite set of vectors.
- When the set of actions is a polyhedron, the worst case regret has the same rate as without hints, i.e. Omega(sqrt(T)), even when the hint is constant among trials.
The first result is obtained by a clever substitution of the original loss function by a virtual loss which exploits the hint vector and is shown to be exp-concave. Then, an algorithm is proposed which as subroutine uses any algorithm A_exp for exp-concave online optimization, feeding A_exp with virtual losses, and playing an action for which the original loss is equal to the virtual loss (by exploiting the hint) of A_exp. Since the virtual loss of the adversary is no larger then its original loss, the algorithm's regret is no more than the regret of A_exp.
Interestingly, the second result uses FTL, which does not exploit the hint at all (and thus does not even need to know the hint). So I think this result is more about the constraint on the losses -- there is a direction v, along which the loss is positive in each round. This result resembles results from [15] on FTL with curved constraint sets. I think the results from [15] are incomparable to those here, contrary to what discussion in the appendix say. On the one hand, here the authors extended the analysis to uniformly convex sets (while [15] only work with strongly-convex sets). On the other hand, [15] assume that the cumulative loss vector at each trial is separated from the origin, and this is sufficient to get logarithmic regret; whereas here logarithmic regret is achieved under a different assumption that each individual loss is positive along v (with constant alpha). 
The extension of Theorem 4.2 to arbitrary hints (Appendix C) gives a bound which is exponential in dimension, while for q=2 Section 3 gives a much better algorithm which regret is only linear in the dimension. Do you think the exponential dependence on d for q > 2 is unimprovable? 
The paper is very well written, and the exposition of the main results is clear. For each result, the authors give an extended discussion, including illustrative examples and figures, which builds up intuition on why the result holds. I checked all the proofs in the main part of the paper and did not find any technical problems. I found the contribution to online learning theory strong and significant. What the paper lacks, however, is a motivating example(s) of practical learning problem(s) in which the considered version of hint would be available.
---------------
I have read the rebuttal. The authors clarified comparison to [15], which I asked about in my review.