Robust learning with anytime-guaranteed feedback
  Under data distributions which may be heavy-tailed, many stochastic
gradient-based learning algorithms are driven by feedback queried at points
with almost no performance guarantees on their own. Here we explore a modified
"anytime online-to-batch" mechanism which for smooth objectives admits
high-probability error bounds while requiring only lower-order moment bounds on
the stochastic gradients. Using this conversion, we can derive a wide variety
of "anytime robust" procedures, for which the task of performance analysis can
be effectively reduced to regret control, meaning that existing regret bounds
(for the bounded gradient case) can be robustified and leveraged in a
straightforward manner. As a direct takeaway, we obtain an easily implemented
stochastic gradient-based algorithm for which all queried points formally enjoy
sub-Gaussian error bounds, and in practice show noteworthy gains on real-world
data applications.
