A Boosting Framework on Grounds of Online Learning
By exploiting the duality between boosting and online learning, we present a boosting framework which proves to be extremely powerful thanks to employing the vast knowledge available in the online learning area. Using this framework, we develop various algorithms to address multiple practically and theoretically interesting questions including sparse boosting, smooth-distribution boosting, agnostic learning and, as a by-product, some generalization to double-projection online learning algorithms.
This work describes an approach for obtaining boosting algorithms from the mirror-descent algorithm for (online) convex minimization. The algorithms that are derived have provable guarantees in the PAC framework (that is given a weak learner with advantage \gamma it produces an \epsilon-accurate hypothesis). The framework is useful when boosting needs to be performed with additional (convex) constraints on the distribution since those can be obtained by changing the Bregman projection step. In particular, smoothness and sparsity are analyzed. The paper also claims to contribute new analysis of mirror-descent with lazy updates.This paper is a nice generalization of Kivinen-Warmuth 99 and Barak-Hardt-Kale 09 papers that only dealt with KL divergence to any Bregman divergence. The applications are nice but none of them seems both interesting and novel. Smoothness is certainly a useful property (e.g. for agnostic learning) but this case the approach to obtaining smoothness is identical to that in the BHK09 paper. In the case of sparsity the discussion of it is rather non-specific. No clear motivation and also no theoretical analysis of sparsity are given. The result only shows that it is possible to add an additional l_1 constraint into the boosting analysis. Without motivation and analysis it's impossible to tell for example how it would compare with subsampling.At the technical level the results seem nice but rely primarily on the well-known connection of boosting and online learning/optimization and known analysis of mirror-descent. The paper mentions a number of "second-order" improvements to aspects of the analysis but I'm not familiar enough with those to judge the importance and novelty. Overall I think that the paper has interesting technical content which should be published. At the same time I expect more novelty (either conceptually or technically) for a solid recommendation to NIPS.Some additional comments and typos:053 - The term smooth boosting was first defined by Servedio, COLT 01 not Gavinsky (but smoothness was used even earlier by Jackson, FOCS 94)095 - The bound on the number of steps lacks the \gamma_t term098 - Smoothness is also shown to be useful for agnostic boosting by Gavinsky, ALT 02 and by Feldman, ICS 10 for agnostic and PAC learning models.138 - It seems that later on you are using a different definition of entropy156 - is -> are169 - "norm of"170 - typos in the definition of entropy171 - what are x_i' here?279 - 3 typos415,419 conjunction->conjecture441 - M.Long is not an author of this article (P.Long is the editor)