Learning with Square Loss: Localization through Offset Rademacher Complexity

Abstract

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.

21 pages, 1 figure

References in corpus (1)

• Deviation optimal learning using greedy Q-aggregation

Cited by in corpus (9)

• Learning nonlinear dynamical systems from a single trajectory
• Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective
• Learning with Non-Convex Truncated Losses by SGD
• Adaptive Online Learning
• Optimal learning via local entropies and sample compression
• On Empirical Risk Minimization with Dependent and Heavy-Tailed Data
• Towards Optimal Problem Dependent Generalization Error Bounds in Statistical Learning Theory
• Sum-of-squares meets square loss: Fast rates for agnostic tensor completion
• Localization, Convexity, and Star Aggregation