DeLTA seminar by Julian Zimmert, Google Research
Speaker
Julian Zimmert, Google Research
Title
Efficient Methods for Online Multiclass Logistic Regression
Abstract
Multiclass logistic regression is a fundamental task in machine learning with applications in classification and boosting. Previous work (Foster et al 2018) has highlighted the importance of improper predictors for achieving ``fast rates'' in the online multiclass logistic regression problem without suffering exponentially from secondary problem parameters, such as the
norm of the predictors in the comparison class. While Foster et al (2018) introduced a statistically optimal algorithm, it is in practice computationally intractable due to its run-time complexity being a large polynomial in the time horizon and dimension of input feature vectors.
In this work, we develop a new algorithm, FOLKLORE, for the problem which runs significantly faster than the algorithm of Foster et al (2018) -- the running time per iteration scales quadratically in the dimension -- at the cost of a linear dependence on the norm of the predictors in the regret bound. This yields the first practical algorithm for online multiclass logistic regression, resolving an open problem of Jezequel et al (2020).
_____________________________
You can subscribe to DeLTA Seminar mailing list by sending an empty email to delta-seminar-join@list.ku.dk.
Information about DeLTA Seminars is available at the DeLTA Lab page: https://sites.google.com/diku.edu/delta
DeLTA is a research group affiliated with the Department of Computer Science at the University of Copenhagen studying diverse aspects of Machine Learning Theory and its applications, including, but not limited to Reinforcement Learning, Online Learning and Bandits, PAC-Bayesian analysis