Learning with Square Loss: Localization through Offset Rademacher Complexity

By Tengyuan Liang, Alexander Rakhlin, Karthik Sridharan. 2015

85 citations recorded by the source corpus.

We consider regression with square loss and general classes of functions without the boundedness assumption. We introduce a notion of offset Rademacher complexity that provides a transparent way to study localization both in expectation and in high probability. For any (possibly non-convex) class, the excess loss of a two-step estimator is shown to be upper bounded by this offset complexity through a novel geometric inequality. In the convex case, the estimator reduces to an empirical risk minimizer. The method recovers the results of \citep{RakSriTsy15} for the bounded case while also providing guarantees without the boundedness assumption.

Subfields: Artificial Intelligence, Computational Mechanics, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Statistics and Probability

Citations in the corpus

Deep Neural Networks for Estimation and Inference: Application to Causal Effects and Other Semiparametric Estimands (2018, methodology): “…our proof is to use a scale sensitive localization theory (Koltchinskii and Panchenko (2000), Bartlett, Bousquet, and Mendelson (2005), Koltchinskii (2006, 2011), Liang, Rakhlin, and Sridharan (2015)) with such scale insensitive measures for deep neural networks for general smooth loss functions.”
Fast Rates with Unbounded Losses (2016, methodology): “Empirical process vs Information-theoretic There also are approaches based on empirical process theory (EPT) like (Bartlett et al., 2005; Bartlett and Mendelson, 2006; Koltchinskii, 2006; Mendelson, 2014a; Liang et al., 2015), and information-theoretic approaches based on prior measures, change-of-m”