Parameter-Free Online Learning via Model Selection
We introduce an efficient algorithmic framework for model selection in online learning, also known as parameter-free online learning. Departing from previous work, which has focused on highly structured function classes such as nested balls in Hilbert space, we propose a generic meta-algorithm framework that achieves online model selection oracle inequalities under minimal structural assumptions. We give the first computationally efficient parameter-free algorithms that work in arbitrary Banach spaces under mild smoothness assumptions; previous results applied only to Hilbert spaces. We further derive new oracle inequalities for matrix classes, non-nested convex sets, and R d with generic regularizers. Finally, we generalize these results by providing oracle inequalities for arbitrary non-linear classes in the online supervised learning model. These results are all derived through a unified meta-algorithm scheme using a novel "multi-scale" algorithm for prediction with expert advice based on random playout, which may be of independent interest.
The paper introduces a framework for deriving model selection oracle inequalities in the adversarial online learning setting. The framework is based on a new meta-algorithm, called MultiScaleFTPL, which is able to combine base algorithms ("experts"), incurring a regret to the i-th algorithm which is proportional to the range of its losses. This adaptation to the loss range leads to numerous applications of the algorithm in a wide range of settings, in many of which oracle bounds were previously unavailable. 
In particular, the authors consider adaptation to the comparator's norm in uniformly convex Banach spaces (which is a novel results, as previously only Hilbert space norms were considered), an algorithm with a bound which holds for any \ell_p norm of the comparator (quite surprising that such a generality in the bound is actually possible), adaptation to the rank for online PCA, adaptation to the norm of positive definite comparator matrix in the Matrix Multipcative Weight setup, combining algorithms in the online supervised learning setup, including online penalized risk minimization and online multiple kernel learning. Many of these results are impressive. The overall contribution is thus very solid.
The central result in the paper is the MultiScaleFTPL algorithm, essentially a "prediction with expert advice" algorithm. The main feature of the algorithm, the reason why it stands out from other previously considered methods, is its adaptation to the loss range: the algorithm guarantees a regret to the expert i (for all i), which scales proportionally to the range of the losses of expert i, rather than to the worst-case range among experts. The algorithms is an unusual version of Follow the Perturbed Leader algorithm, which samples the future and plays with a distribution which minimizes the worst-case (w.r.t. the current gradient) penalized regret. 
The technical quality of the paper is high. I verified some of the proofs (not all) in the appendix. I found one confusing aspect in the proof of the main theorem (Thm 1), which I was not able to understand: at the top of page 12 (appendix) what does "choosing p_t to match e_i" mean, given that i is the index over which the supremum is taken? (i.e., it sounds as if p_t matches all all e_i simultaneously...). I would be very to glad to get a feedback from the authors on this issue. 
In summary, I really like the new algorithms and numerous impressive novel results the algorithm leads to. I think the paper is definitely worth accepting to the conference.
Minor remarks:
- line 54-55: "all losses ... are all bounded" -> "losses ... are bounded"
- Eq. (3) -- what is w_t^i on the l.h.s.? (i index not explained)
- line 121: "with norm large as" -> "with norm as large as"
- Eq. below line 135: sigma's are denoted differently than in Algorithm 3
- line 187: 2-smooth norm -- this term is not explained (at least give a reference to the definition)
- appendix A.1, last line of page 11: < p_t,g_t >  ->  < p_t, g_t' >
- appendix A.1 (proof of Thm 1): would be good to say what \epsilon is.
- appendix A.1 (proof of Thm 10): domination is defined by saying that w_1 is at least w_2 plus sum of c_1 + c_2, but there is a factor of 2 in front of epsilon sigma_i c_i in the bound. Should I understand it that epsilon is distributed on {-1/2, 1/2}? But then it does not fit to the proof of Thm 1 (top of page 12) 
- appendix A.2 (proof of Thm 2): \cal{A} introduced without definition (class of base algorithms?)
-------
The rebuttal clarified my (minor) issues with the proofs. I keep my high score.