Fetching the paper…
Reading the bibliography…
In this paper, we study oracle-efficient algorithms for beyond worst-case analysis of online learning.
Covering numbers for real-valued function classes
Peter L Bartlett, Sanjeev R Kulkarni, and S Eli Posner · 1997
Earlier work this paper cites.
Neural network learning: Theoretical foundations
Martin Anthony and Peter L Bartlett · 1999
Earlier work this paper cites.
Nonparametric goodness-of-fit testing under Gaussian models
Yuri I. Ingster and Irina A. Suslina · 2003
Earlier work this paper cites.
Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time
Daniel A. Spielman and Shang-Hua Teng · 2004
Earlier work this paper cites.
From batch to transductive online learning
Sham Kakade and Adam T Kalai · 2005
Earlier work this paper cites.
Efficient algorithms for online decision problems
Adam Tauman Kalai and Santosh Vempala · 2005
Earlier work this paper cites.
Lecture notes in statistical learning theory, Spring 2006
Peter Bartlett · 2006
Earlier work this paper cites.
Concentration inequalities and asymptotic results for ratio type empirical processes
Evarist Giné and Vladimir Koltchinskii · 2006
Earlier work this paper cites.
Online learning with prior knowledge
Elad Hazan and Nimrod Megiddo · 2007
Earlier work this paper cites.
Playing games with approximation algorithms
Sham M. Kakade, Adam Tauman Kalai, and Katrina Ligett · 2007
Earlier work this paper cites.
Agnostic online learning
Shai Ben-David, Dávid Pál, and Shai Shalev-Shwartz · 2009
Earlier work this paper cites.
Introduction to Nonparametric Estimation
A. Tsybakov · 2009
Earlier work this paper cites.
Extracting certainty from uncertainty: Regret bounded by variation in costs
Elad Hazan and Satyen Kale · 2010
Earlier work this paper cites.
Online learning: Stochastic, constrained, and smoothed adversaries
Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari · 2011
Cited alongside, same era.
Relax and randomize: From value to algorithms
Alexander Rakhlin, Ohad Shamir, and Karthik Sridharan · 2012
Cited alongside, same era.
Online learning with predictable sequences
Alexander Rakhlin and Karthik Sridharan · 2013
Cited alongside, same era.
Optimization, learning, and games with predictable sequences
Sasha Rakhlin and Karthik Sridharan · 2013
Cited alongside, same era.
Adaptivity and optimism: An improved exponentiated gradient algorithm
Jacob Steinhardt and Percy Liang · 2014
Cited alongside, same era.
Learning in auctions: Regret is hard, envy is easy
Constantinos Daskalakis and Vasilis Syrgkanis · 2016
Cited alongside, same era.
A smoothed analysis of the greedy algorithm for the linear contextual bandit problem
Sampath Kannan, Jamie H Morgenstern, Aaron Roth, Bo Waggoner, and Zhiwei Steven Wu · 2018
Later among the works it cites.
The externalities of exploration and how data diversity helps exploitation
Manish Raghavan, Aleksandrs Slivkins, Jennifer Vaughan Wortman, and Zhiwei Steven Wu · 2018
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 · 2019
Later among the works it cites.
Online learning with imperfect hints
Aditya Bhaskara, Ashok Cutkosky, Ravi Kumar, and Manish Purohit · 2020
Later among the works it cites.
Oracle-efficient online learning and auction design
Miroslav Dudík, Nika Haghtalab, Haipeng Luo, Robert E Schapire, Vasilis Syrgkanis, and Jennifer Wortman Vaughan · 2020
Later among the works it cites.
Beyond ucb: Optimal and efficient contextual bandits with regression oracles
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
The computational power of optimization in online learning
Elad Hazan and Tomer Koren · 2016
Cited alongside, same era.
Accelerating online convex optimization via adaptive prediction
Mehryar Mohri and Scott Yang · 2016
Cited alongside, same era.
Efficient algorithms for adversarial contextual learning
Vasilis Syrgkanis, Akshay Krishnamurthy, and Robert Schapire · 2016
Cited alongside, same era.
Online Optimization of Smoothed Piecewise Constant Functions
Vincent Cohen-Addad and Varun Kanade · 2017
Cited alongside, same era.
Online learning with a hint
Ofer Dekel, Nika Haghtalab, Patrick Jaillet, et al · 2017
Cited alongside, same era.
A PAC approach to application-specific algorithm selection
Rishi Gupta and Tim Roughgarden · 2017
Cited alongside, same era.
Dylan Foster and Alexander Rakhlin · 2020
Later among the works it cites.
Smoothed analysis of online and differentially private learning
Nika Haghtalab, Tim Roughgarden, and Abhishek Shetty · 2020
Later among the works it cites.
The statistical complexity of interactive decision making
Dylan J Foster, Sham M Kakade, Jian Qian, and Alexander Rakhlin · 2021
Later among the works it cites.
Bypassing the monster: A faster and simpler optimal algorithm for contextual bandits under realizability
David Simchi-Levi and Yunzong Xu · 2021
Later among the works it cites.
Smoothed online learning is as easy as statistical learning
Adam Block, Yuval Dagan, Noah Golowich, and Alexander Rakhlin · 2022
Closest in time.
Oracle-efficient online learning for smoothed adversaries
Nika Haghtalab, Yanjun Han, Abhishek Shetty, and Kunhe Yang · 2022
Closest in time.
Smoothed analysis with adaptive adversaries
Nika Haghtalab, Tim Roughgarden, and Abhishek Shetty · 2022
Closest in time.