caa a22 4500 60547849X CHVBK 20210128100406.0 cr unu---uuuuu 210128e20150601xx s 000 0 eng 10.1007/s10994-014-5474-8 doi (NATIONALLICENCE)springer-10.1007/s10994-014-5474-8 A generalized online mirror descent with applications to classification and regression [Elektronische Daten] [Francesco Orabona, Koby Crammer, Nicolò Cesa-Bianchi] Online learning algorithms are fast, memory-efficient, easy to implement, and applicable to many prediction problems, including classification, regression, and ranking. Several online algorithms were proposed in the past few decades, some based on additive updates, like the Perceptron, and some on multiplicative updates, like Winnow. A unifying perspective on the design and the analysis of online algorithms is provided by online mirror descent, a general prediction strategy from which most first-order algorithms can be obtained as special cases. We generalize online mirror descent to time-varying regularizers with generic updates. Unlike standard mirror descent, our more general formulation also captures second order algorithms, algorithms for composite losses and algorithms for adaptive filtering. Moreover, we recover, and sometimes improve, known regret bounds as special cases of our analysis using specific regularizers. Finally, we show the power of our approach by deriving a new second order algorithm with a regret bound invariant with respect to arbitrary rescalings of individual features. The Author(s), 2014 Orabona Francesco Yahoo Labs, 10036, New York, NY, USA aut Crammer Koby Department of Electrical Engineering, The Technion, 32000, Haifa, Israel aut Cesa-Bianchi Nicolò Department of Computer Science, Università degli Studi di Milano, 20135, Milan, Italy aut Machine Learning Springer US; http://www.springer-ny.com 99/3(2015-06-01), 411-435 0885-6125 99:3<411 2015 99 10994 https://doi.org/10.1007/s10994-014-5474-8 text/html Onlinezugriff via DOI BK010053 XK010053 XK010000 Metadata rights reserved Springer special CC-BY-NC licence nationallicence 1 research-article jats NATIONALLICENCE NATIONALLICENCE NL-springer NATIONALLICENCE 856 40 https://doi.org/10.1007/s10994-014-5474-8 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Orabona Francesco Yahoo Labs, 10036, New York, NY, USA aut NATIONALLICENCE 700 1- Crammer Koby Department of Electrical Engineering, The Technion, 32000, Haifa, Israel aut NATIONALLICENCE 700 1- Cesa-Bianchi Nicolò Department of Computer Science, Università degli Studi di Milano, 20135, Milan, Italy aut NATIONALLICENCE 773 0- Machine Learning Springer US; http://www.springer-ny.com 99/3(2015-06-01), 411-435 0885-6125 99:3<411 2015 99 10994