Skip to content
conftrace_
2015 JMLR JMLR 2015

The Sample Complexity of Learning Linear Predictors with the Squared Loss

Abstract

We provide a tight sample complexity bound for learning bounded- norm linear predictors with respect to the squared loss. Our focus is on an agnostic PAC-style setting, where no assumptions are made on the data distribution beyond boundedness. This contrasts with existing results in the literature, which rely on other distributional assumptions, refer to specific parameter settings, or use other performance measures. [abs] [ pdf ][ bib ] © JMLR 2015. (edit, beta)

🐣 Hot Topic Early Bird - pac learning

Authors

Ohad Shamir

Topics

Machine Learning > Core Methods > Regression Machine Learning > Optimization & Theory > Learning Theory Machine Learning > Optimization & Theory > Statistical Learning

Keywords

statistical learning sample complexity pac learning agnostic learning squared loss linear predictor
Download PDF

More from JMLR 2015

All JMLR 2015 papers →
On the Inductive Bias of Dropout
Agnostic Learning of Disjunctions on Symmetric Distributions
SnFFT: A Julia Toolkit for Fourier Analysis of Functions over Permutations
Minimax Analysis of Active Learning
Convergence Rates for Persistence Diagram Estimation in Topological Data Analysis
Supervised Learning via Euler's Elastica Models