Online learning algorithms are fast, memory-efficient, easy to implement, and applicable to many prediction problems, including classification, regression, and ranking. Several online algorithms were proposed in the past few decades, some based on additive updates, like the Perceptron, and some on multiplicative updates, like Winnow. Online mirror descent is a general prediction strategy offering a unified viewpoint on the design and the analysis of online algorithms: most first-order algorithms can indeed be obtained as special cases of mirror descent. We generalize online mirror descent to sequences of time-varying regularizers with generic updates. Unlike standard mirror descent, our more general formulation also captures second order algorithms, algorithms for composite losses, and algorithms for adaptive filtering. Moreover, we recover, and sometimes improve, known regret bounds by instantiating our analysis on specific regularizers. Finally, we show the power of our approach by deriving a new second order algorithm with a regret bound invariant with respect to arbitrary rescalings of individual features.

本文提供了一种新的方法，将在线预测算法在线镜像下降推广到具有通用更新的时间变化正则化器，并演示了该方法的强大功能。

一种广义的在线镜像下降算法及其在分类和回归中的应用