Problem: Better Bounds for Online Logistic Regression
Abstract: Known algorithms applied to online logistic regression on a
feasible set of L2 diameter D achieve regret bounds like O(eD log T) in one
dimension, but we show a bound of O(sqrt(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.