  We provide algorithms for regression with adversarial responses under large
classes of non-i.i.d. instance sequences, on general separable metric spaces,
with provably minimal assumptions. We also give characterizations of
learnability in this regression context. We consider universal consistency
which asks for strong consistency of a learner without restrictions on the
value responses. Our analysis shows that such an objective is achievable for a
significantly larger class of instance sequences than stationary processes, and
unveils a fundamental dichotomy between value spaces: whether finite-horizon
mean estimation is achievable or not. We further provide optimistically
universal learning rules, i.e., such that if they fail to achieve universal
consistency, any other algorithms will fail as well. For unbounded losses, we
propose a mild integrability condition under which there exist algorithms for
adversarial regression under large classes of non-i.i.d. instance sequences. In
addition, our analysis also provides a learning rule for mean estimation in
general metric spaces that is consistent under adversarial responses without
any moment conditions on the sequence, a result of independent interest.
