Open Problem: Better Bounds for Online Logistic Regression

H. Brendan McMahan and Matthew Streeter JMLR W&CP 23: 44.1 - 44.3, 2012

Abstract

Known algorithms applied to online logistic regression on a feasible set of L₂ diameter D achieve regret bounds like O(e^D log T) in one dimension, but we show a bound of O(√D + log T) is possible in a binary 1-dimensional problem. Thus, we pose the following question: Is it possible to achieve a regret bound for online logistic regression that is O(poly(D) log(T))? Even if this is not possible in general, it would be interesting to have a bound that reduces to our bound in the one-dimensional case.