Fetching the paper…
Reading the bibliography…
A recurring theme in statistical learning, online learning, and beyond is that faster convergence rates are possible for problems with low noise, often quantified by the performance of the best hypothesis; such results are known as first-order or small-loss guarantees.
On the uniform convergence of relative frequencies of events to their probabilities
Vladimir N. Vapnik and Alexey A. Chervonenkis · 1971
Earlier work this paper cites.
On the concept and measure of information contained in an observation
István Vincze · 1981
Earlier work this paper cites.
Adapting for heteroscedasticity in linear models
Raymond J Carroll · 1982
Earlier work this paper cites.
Advanced econometrics
Amemiya Takeshi · 1985
Earlier work this paper cites.
Asymptotic methods in statistical decision theory
Lucien Le Cam · 1986
Earlier work this paper cites.
Universal sequential coding of single messages
Yurii Mikhailovich Shtar’kov · 1987
Earlier work this paper cites.
Universal portfolios
Thomas M Cover · 1991
Earlier work this paper cites.
A game of prediction with expert advice
Vladimir Vovk · 1995
Earlier work this paper cites.
A decision-theoretic generalization of on-line learning and an application to boosting
Yoav Freund and Robert E Schapire · 1997
Earlier work this paper cites.
Associative reinforcement learning using linear probabilistic concepts
Naoki Abe and Philip M Long · 1999
Earlier work this paper cites.
Beating the hold-out: Bounds for K-fold and progressive cross-validation
Avrim Blum, Adam Kalai, and John Langford · 1999
Earlier work this paper cites.
Minimax regret under log loss for general classes of experts
Nicolò Cesa-Bianchi and Gábor Lugosi · 1999
Earlier work this paper cites.
Worst case prediction over sequences under log loss
Manfred Opper and David Haussler · 1999
Earlier work this paper cites.
Minimax nonparametric classification. I. Rates of convergence
Yuhong Yang · 1999
Earlier work this paper cites.
Some inequalities for information divergence and related measures of discrimination
Flemming Topsøe · 2000
Earlier work this paper cites.
Empirical Processes in M-Estimation
Sara A. van de Geer · 2000
Earlier work this paper cites.
Efficient algorithms for universal portfolios
Adam Kalai and Santosh Vempala · 2002
Earlier work this paper cites.
Some extensions of an inequality of Vapnik and Chervonenkis
Dmitriy Panchenko · 2002
Earlier work this paper cites.
Introduction to statistical learning theory
Olivier Bousquet, Stéphane Boucheron, and Gábor Lugosi · 2003
Earlier work this paper cites.
Hannan consistency in on-line learning in case of unbounded losses under partial monitoring
Chamy Allenberg, Peter Auer, László Györfi, and György Ottucsák · 2006
Earlier work this paper cites.
Prediction, Learning, and Games
Nicolò Cesa-Bianchi and Gabor Lugosi · 2006
Earlier work this paper cites.
Fast learning rates for plug-in classifiers
Jean-Yves Audibert and Alexandre B Tsybakov · 2007
Earlier work this paper cites.
Improved second-order bounds for prediction with expert advice
Nicolò Cesa-Bianchi, Yishay Mansour, and Gilles Stoltz · 2007
Earlier work this paper cites.
Logarithmic regret algorithms for online convex optimization
Elad Hazan, Amit Agarwal, and Satyen Kale · 2007
Cited alongside, same era.
Homomorphisms to
Anna Erschler and Anders Karlsson · 2010
Cited alongside, same era.
Smoothness, low noise and fast rates
Nathan Srebro, Karthik Sridharan, and Ambuj Tewari · 2010
Cited alongside, same era.
Contextual bandit algorithms with supervised learning guarantees
Alina Beygelzimer, John Langford, Lihong Li, Lev Reyzin, and Robert Schapire · 2011
Cited alongside, same era.
Contextual bandits with linear payoff functions
Wei Chu, Lihong Li, Lev Reyzin, and Robert E Schapire · 2011
Cited alongside, same era.
Adaptive subgradient methods for online learning and stochastic optimization
John Duchi, Elad Hazan, and Yoram Singer · 2011
Cited alongside, same era.
Open problem: First-order regret bounds for contextual bandits
Alekh Agarwal, Akshay Krishnamurthy, John Langford, Haipeng Luo, and Robert E Schapire · 2017
Later among the works it cites.
Active learning for cost-sensitive classification
Akshay Krishnamurthy, Alekh Agarwal, Tzu-Kuo Huang, Hal Daumé III, and John Langford · 2017
Later among the works it cites.
Soft-bayes: Prod for mixtures of experts with log-loss
Laurent Orseau, Tor Lattimore, and Shane Legg · 2017
Later among the works it cites.
From ads to interventions: Contextual bandits in mobile health
Ambuj Tewari and Susan A Murphy · 2017
Later among the works it cites.
Make the minority great again: First-order regret bound for contextual bandits
Zeyuan Allen-Zhu, Sébastien Bubeck, and Yuanzhi Li · 2018
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Online importance weight aware updates
Nikos Karampatziakis and John Langford · 2011
Cited alongside, same era.
Contextual bandit learning with predictable rewards
Alekh Agarwal, Miroslav Dudík, Satyen Kale, John Langford, and Robert E Schapire · 2012
Cited alongside, same era.
Concentration inequalities: A nonasymptotic theory of independence
Stéphane Boucheron, Gábor Lugosi, and Pascal Massart · 2013
Cited alongside, same era.
A probabilistic theory of pattern recognition
Luc Devroye, László Györfi, and Gábor Lugosi · 2013
Cited alongside, same era.
Normalized online learning
Stéphane Ross, Paul Mineiro, and John Langford · 2013
Cited alongside, same era.
Taming the monster: A fast and simple algorithm for contextual bandits
Alekh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert Schapire · 2014
Cited alongside, same era.
Alberto Bietti, Alekh Agarwal, and John Langford · 2018
Later among the works it cites.
Efficient online portfolio with logarithmic regret
Haipeng Luo, Chen-Yu Wei, and Kai Zheng · 2018
Later among the works it cites.
Small-loss bounds for online learning with partial information
Thodoris Lykouris, Karthik Sridharan, and Éva Tardos · 2018
Later among the works it cites.
A functional analysis proof of Gromov’s polynomial growth theorem
Narutaka Ozawa · 2018
Later among the works it cites.
Nearly minimax-optimal regret for linearly parameterized bandits
Yingkai Li, Yining Wang, and Yuan Zhou · 2019
Later among the works it cites.
Tight bounds on minimax regret under logarithmic loss via self-concordance
Blair Bilodeau, Dylan J Foster, and Daniel Roy · 2020
Later among the works it cites.
First-order bayesian regret analysis of thompson sampling
Sébastien Bubeck and Mark Sellke · 2020
Later among the works it cites.
Online and distribution-free robustness: Regression and contextual bandits with Huber contamination
Sitan Chen, Frederic Koehler, Ankur Moitra, and Morris Yau · 2020
Later among the works it cites.
Beyond UCB: Optimal and efficient contextual bandits with regression oracles
Dylan J Foster and Alexander Rakhlin · 2020
Later among the works it cites.
Adapting to misspecification in contextual bandits
Dylan J Foster, Claudio Gentile, Mehryar Mohri, and Julian Zimmert · 2020
Later among the works it cites.
Tight first-and second-order regret bounds for adversarial linear bandits
Shinji Ito, Shuichi Hirahara, Tasuku Soma, and Yuichi Yoshida · 2020
Later among the works it cites.
David Simchi-Levi and Yunzong Xu · 2020
Later among the works it cites.
Upper counterfactual confidence bounds: A new optimism principle for contextual bandits
Yunbei Xu and Assaf Zeevi · 2020
Later among the works it cites.
Pointer chasing via triangular discrimination
Amir Yehudayoff · 2020
Later among the works it cites.
Nearly minimax optimal reinforcement learning for linear mixture Markov decision processes
Dongruo Zhou, Quanquan Gu, and Csaba Szepesvari · 2020
Later among the works it cites.
Instance-dependent complexity of contextual bandits and reinforcement learning: A disagreement-based perspective
Dylan J Foster, Alexander Rakhlin, David Simchi-Levi, and Yunzong Xu · 2021
Closest in time.
Zihan Zhang, Jiaqi Yang, Xiangyang Ji, and Simon S Du · 2021
Closest in time.