Learning Hurdles for Sleeping Experts

DOI10.1145/2505983zbMath1347.68192OpenAlexW2217850561MaRDI QIDQ2828218

Varun Kanade, Thomas Steinke

Publication date: 24 October 2016

Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2505983

zbMATH Keywords

online learninglower boundssleeping experts

Mathematics Subject Classification ID

Computational learning theory (68Q32) Learning and adaptive systems in artificial intelligence (68T05) Probabilistic games; gambling (91A60) Online algorithms; streaming algorithms (68W27)

Uses Software

• AdaBoost.MH

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimization, approximation, and complexity classes
• Decision theoretic generalizations of the PAC model for neural net and other learning applications
• Toward efficient agnostic learning
• Regret bounds for sleeping experts and bandits
• Proof verification and the hardness of approximation problems
• Learning Kernel-Based Halfspaces with the 0-1 Loss
• On the Generalization Ability of On-Line Learning Algorithms
• A theory of the learnable
• Learning DNF in time
• A Lower Bound for Agnostically Learning Disjunctions
• Some optimal inapproximability results
• Prediction, Learning, and Games
• Near-Optimal Algorithms for Online Matrix Prediction
• Concentration of Measure for the Analysis of Randomized Algorithms

This page was built for publication: Learning Hurdles for Sleeping Experts