On the Performance of Empirical Risk Minimization with Smoothed Data
Adam Block Alexander Rakhlin Abhishek Shetty
In order to circumvent statistical and computational hardness results in
sequential decision-making, recent work has considered smoothed online
learning, where the distribution of data at each time is assumed to have
bounded likeliehood ratio with respect to a base measure when conditioned on
the history. While previous works have demonstrated the benefits of smoothness,
they have either assumed that the base measure is known to the learner or have
presented computationally inefficient algorithms applying only in special
cases. This work investigates the more general setting where the base measure
is \emph{unknown} to the learner, focusing in particular on the performance of
Empirical Risk Minimization (ERM) with square loss when the data are
well-specified and smooth. We show that in this setting, ERM is able to achieve
sublinear error whenever a class is learnable with iid data; in particular, ERM
achieves error scaling as $\tilde O( \sqrt{\mathrm{comp}(\mathcal F)\cdot T}
)$, where $\mathrm{comp}(\mathcal F)$ is the statistical complexity of learning
$\mathcal F$ with iid data. In so doing, we prove a novel norm comparison bound
for smoothed data that comprises the first sharp norm comparison for dependent
data applying to arbitrary, nonlinear function classes. We complement these
results with a lower bound indicating that our analysis of ERM is essentially
tight, establishing a separation in the performance of ERM between smoothed and
iid data.