Stochastic and Adversarial Online Learning without Hyperparameters
Most online optimization algorithms focus on one of two things: performing well in adversarial settings by adapting to unknown data parameters (such as Lipschitz constants), typically achieving O( √ T ) regret, or performing well in stochastic settings where they can leverage some structure in the losses (such as strong convexity), typically achieving O(log(T )) regret. Algorithms that focus on the former problem hitherto achieved O( √ T ) in the stochastic setting rather than O(log(T )). Here we introduce an online optimization algorithm that achieves O(log 4 (T )) regret in a wide class of stochastic settings while gracefully degrading to the optimal O( √ T ) regret in adversarial settings (up to logarithmic factors). Our algorithm does not require any prior knowledge about the data or tuning of parameters to achieve superior performance.
This paper introduces a parameter-free algorithm for online learning that attains non-trivial guarantees in both the stochastic and adversarial settings simultaneously. Previous work in this area includes the MetaGrad algorithm, which was not parameter-free and required knowledge of L_max, but simultaneously attained O(B L_max \sqrt{T}) regret in the adversarial setting and O(dBL_max log(T)) in the stochastic or strongly setting. The key insight by the authors is to interpret an upper bound on the regret as an expectation over the learner's output vectors (scaled by the norm of the gradient at each round), to rewrite this expression in terms of a bias and variance term, and then to shift the regularization component of an existing parameter-free algorithm by a running estimate of the previously mentioned expectation. This results in an algorithm with O(\sqrt{T} \log(T)^2 L_max B) regret. When the loss functions satisfy a certain curvature property called \alpha-acute convexity, the algorithm is able to attain a regret in O(\log(T)^4 L_max B/\alpha). 
This paper introduces a clever method for an interesting area of online learning, that of parameter-free algorithms that work well in multiple environments. The manuscript is well-written and the authors provide the reader with an abundance of both insight into the problem and intuition for their solution. The main concern I have for the paper is the practical utility of their algorithm. The algorithm's adversarial guarantee includes an extra log(T)^2 factor in addition to the usual terms, and, as the authors admit, the stochastic guarantee in the stochastic setting may only be compelling for extraordinarily large values of T. Still, this paper is at the very least an interesting theoretical contribution. 
Some technical questions:
1) Line 107: Can the authors explain how they arrived at the 2nd inequality?
2) Line 184: Should the last expression be \frac{\mu}{2} \|w - w^*\|^2? 
3) Line 187: Can the authors explain how they arrived at the 2nd inequality (i.e. .... \geq \frac{\mur}{2}\|w\|)?
4) As the authors mention, for strongly convex functions, \alpha = \mu/(2 L_max). Thus, the stochastic bound will become O(\log(T)^4B/\mu). However, the standard online convex optimization guarantee for strongly convex loss functions is O(log(T)L^2/\mu). Apart from the additional log(T) terms, can the authors discuss the difference in dependence on B vs L^2?
Post author response: I've read the author response and choose to maintain my score.