  This work provides test error bounds for iterative fixed point methods on
linear predictors -- specifically, stochastic and batch mirror descent (MD),
and stochastic temporal difference learning (TD) -- with two core
contributions: (a) a single proof technique which gives high probability
guarantees despite the absence of projections, regularization, or any
equivalents, even when optima have large or infinite norm, for
quadratically-bounded losses (e.g., providing unified treatment of squared and
logistic losses); (b) locally-adapted rates which depend not on global problem
structure (such as condition numbers and maximum margins), but rather on
properties of low norm predictors which may suffer some small excess test
error. The proof technique is an elementary and versatile coupling argument,
and is demonstrated here in the following settings: stochastic MD under
realizability; stochastic MD for general Markov data; batch MD for general IID
data; stochastic MD on heavy-tailed data (still without projections);
stochastic TD on Markov chains (all prior stochastic TD bounds are in
expectation).
