On the Performance of Empirical Risk Minimization with Smoothed Data
This work addresses a gap in smoothed online learning by extending results to unknown base measures, though it is incremental as it builds on prior assumptions of known measures.
The paper tackles the problem of online learning with smoothed data where the base measure is unknown, showing that Empirical Risk Minimization (ERM) with square loss achieves sublinear error scaling as $ ilde O( \sqrt{\mathrm{comp}(\mathcal F)\cdot T} )$ when the data are well-specified and smooth, and proves a lower bound indicating this analysis is tight.
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.