DeLTA seminar by Julian Zimmert, Google Research


portrait of Julian Zimmert

Julian Zimmert, Google Research


Efficient Methods for Online Multiclass Logistic Regression


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
Information about DeLTA Seminars is available at the DeLTA Lab page: