Online Robust and Adaptive Learning from Data Streams
  In online learning from non-stationary data streams, it is necessary to learn
robustly to outliers and to adapt quickly to changes in the underlying data
generating mechanism. In this paper, we refer to the former attribute of online
learning algorithms as robustness and to the latter as adaptivity. There is an
obvious tradeoff between the two attributes. It is a fundamental issue to
quantify and evaluate the tradeoff because it provides important information on
the data generating mechanism. However, no previous work has considered the
tradeoff quantitatively. We propose a novel algorithm called the stochastic
approximation-based robustness-adaptivity algorithm (SRA) to evaluate the
tradeoff. The key idea of SRA is to update parameters of distribution or
sufficient statistics with the biased stochastic approximation scheme, while
dropping data points with large values of the stochastic update. We address the
relation between the two parameters: one is the step size of the stochastic
approximation, and the other is the threshold parameter of the norm of the
stochastic update. The former controls the adaptivity and the latter does the
robustness. We give a theoretical analysis for the non-asymptotic convergence
of SRA in the presence of outliers, which depends on both the step size and
threshold parameter. Because SRA is formulated on the majorization-minimization
principle, it is a general algorithm that includes many algorithms, such as the
online EM algorithm and stochastic gradient descent. Empirical experiments for
both synthetic and real datasets demonstrated that SRA was superior to previous
methods.
