A phenomenon separating statistical performance achievable by proper and improper estimators, related to the one observed in our work for linear regression, has recently attracted considerable attention in the logistic regression literature. Consider the setting of online logistic regression over a bounded Euclidean ball \(\mathcal {W}_{b}\)  in \(\mathbb {R}^d\)  and denote the number of rounds by \(t\)  (for the background on the setup see [1]}). In this case, the cumulative regret of the online Newton step algorithm [2]} is of order \(e^{b}d\log t\) . The exponential dependence on \(b\)  lead to a question formulated in [3]} asking whether there exists an algorithm with logarithmic regret but polynomial dependence on the radius \(b\)  of the constraint set. The work [4]} shows that such an algorithm does not exist in the class of proper estimators; the work [1]} provides an improper algorithm that attains a cumulative regret guarantee of order \(d\log (bt)\)  with a doubly-exponential improvement in the dependence on \(b\) .
