conftrace_

2010 NeurIPS NeurIPS 2010

Online Learning: Random Averages, Combinatorial Parameters, and Learnability

Abstract

We develop a theory of online learning by defining several complexity measures. Among them are analogues of Rademacher complexity, covering numbers and fat-shattering dimension from statistical learning theory. Relationship among these complexity measures, their connection to online learning, and tools for bounding them are provided. We apply these results to various learning problems. We provide a complete characterization of online learnability in the supervised setting.

🌉 Interdisciplinary Bridge - Artificial Intelligence and Mathematics & Optimization

🐣 Hot Topic Early Bird - supervised learning

Authors

Alexander Rakhlin, Karthik Sridharan, Ambuj Tewari

Topics

Machine Learning > Optimization & Theory > Learning Theory Machine Learning > Optimization & Theory > Statistical Learning Mathematics & Optimization > Optimization > Online Algorithms Machine Learning > Learning Types > Online Learning Machine Learning > Optimization & Theory > Online Algorithms

Keywords

online learning supervised learning sample complexity learnability rademacher complexity online learning theory learnability characterization fat-shattering dimension covering number learnability theory

More from NeurIPS 2010

All NeurIPS 2010 papers →

Word Features for Latent Dirichlet Allocation

A Primal-Dual Message-Passing Algorithm for Approximated Large Scale Structured Prediction

Efficient algorithms for learning kernels from multiple similarity matrices with general convex loss functions

Variable margin losses for classifier design

Nonparametric Density Estimation for Stochastic Optimization with an Observable State Variable

Mixture of time-warped trajectory models for movement decoding