Fetching the paper…
Reading the bibliography…
Practical and pervasive needs for robustness and privacy in algorithms have inspired the design of online adversarial and differentially private learning algorithms.
Convex set disjointness, distributed learning of halfspaces, and LP feasibility
Mark Braverman, Gillat Kol, Shay Moran, and Raghuvansh R. Saxena · 1909
Earlier work this paper cites.
Partitioning and geometric embedding of range spaces of finite Vapnik-Chervonenkis dimension
Noga Alon, David Haussler, and Emo Welzl · 1987
Earlier work this paper cites.
Sphere packing numbers for subsets of the Boolean n-cube with bounded Vapnik-Chervonenkis dimension
David Haussler · 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.
Limitations of learning via embeddings in Euclidean half spaces
Shai Ben-David, Nadav Eiron, and Hans Ulrich Simon · 2003
Earlier work this paper cites.
An equivalence between private classification and online prediction
Mark Bun, Roi Livni, and Shay Moran · 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.
Efficient algorithms for online decision problems
Adam Tauman Kalai and Santosh Vempala · 2005
Earlier work this paper cites.
A learning theory approach to non-interactive database privacy
Avrim Blum, Katrina Ligett, and Aaron Roth · 2008
Earlier work this paper cites.
Decision trees are PAC-learnable from most product distributions: a smoothed analysis
Adam Tauman Kalai and Shang-Hua Teng · 2008
Earlier work this paper cites.
The uniform hardcore lemma via approximate bregman projections
Boaz Barak, Moritz Hardt, and Satyen Kale · 2009
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.
Learning and smoothed analysis
Adam Tauman Kalai, Alex Samorodnitsky, and Shang-Hua Teng · 2009
Earlier work this paper cites.
Complexity lower bounds using linear algebra
Satyanarayana V. Lokam · 2009
Earlier work this paper cites.
Uniform convergence of Vapnik–Chervonenkis classes under ergodic sampling
Terrence M. Adams and Andrew B. Nobel · 2010
Earlier work this paper cites.
A multiplicative weights mechanism for privacy-preserving data analysis
Moritz Hardt and Guy N. Rothblum · 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.
Clustering stable instances of Euclidean k-means
Aravindan Vijayaraghavan, Abhratanu Dutta, and Alex Wang · 2011
Cited alongside, same era.
Uniform approximation of Vapnik–Chervonenkis classes
Terrence M. Adams and Andrew B. Nobel · 2012
Cited alongside, same era.
Learning topic models – going beyond SVD
Sanjeev Arora, Rong Ge, and Ankur Moitra · 2012
Cited alongside, same era.
Are stable instances easy?
Yonatan Bilu and Nathan Linial · 2012
Cited alongside, same era.
A simple and practical algorithm for differentially private data release
Moritz Hardt, Katrina Ligett, and Frank McSherry · 2012
Cited alongside, same era.
Learning and 1-bit compressed sensing under asymmetric noise
Pranjal Awasthi, Maria-Florina Balcan, Nika Haghtalab, and Hongyang Zhang · 2016
Later among the works it cites.
The computational power of optimization in online learning
Elad Hazan and Tomer Koren · 2016
Later among the works it cites.
Online Optimization of Smoothed Piecewise Constant Functions
Vincent Cohen-Addad and Varun Kanade · 2017
Later among the works it cites.
Online learning with a hint
Ofer Dekel, Arthur Flajolet, Nika Haghtalab, and Patrick Jaillet · 2017
Later among the works it cites.
Oracle-efficient online learning and auction design
Miroslav Dudík, Nika Haghtalab, Hiapeng Luo, Robert Schapire, Vassilis Syrgkanis, and Jennifer Wortman Vaughan · 2017
Later among the works it cites.
A PAC approach to application-specific algorithm selection
Rishi Gupta and Tim Roughgarden · 2017
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Clustering under approximation stability
Maria-Florina Balcan, Avrim Blum, and Anupam Gupta · 2013
Cited alongside, same era.
Beyond worst-case analysis in private singular vector computation
Moritz Hardt and Aaron Roth · 2013
Cited alongside, same era.
The effectiveness of Lloyd-type methods for the k-means problem
Rafail Ostrovsky, Yuval Rabani, Leonard J. Schulman, and Chaitanya Swamy · 2013
Cited alongside, same era.
Optimization, learning, and games with predictable sequences
Alexander Rakhlin and Karthik Sridharan · 2013
Cited alongside, same era.
The universal Glivenko-Cantelli property
Ramon van Handel · 2013
Cited alongside, same era.
The algorithmic foundations of differential privacy
Cynthia Dwork and Aaron Roth · 2014
Cited alongside, same era.
Dispersion for data-driven algorithm design, online learning, and private optimization
Maria-Florina Balcan, Travis Dick, and Ellen Vitercik · 2018
Later among the works it cites.
Foundation of Machine Learning, by the People, for the People
Nika Haghtalab · 2018
Later among the works it cites.
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.
Private PAC learning implies finite Littlestone dimension
Noga Alon, Roi Livni, Maryanthe Malliaris, and Shay Moran · 2019
Later among the works it cites.
Smoothed analysis in unsupervised learning via decoupling
Aditya Bhaskara, Aidao Chen, Aidan Perreault, and Aravindan Vijayaraghavan · 2019
Later among the works it cites.
Distribution-independent PAC learning of halfspaces with Massart noise
Ilias Diakonikolas, Themis Gouleakis, and Christos Tzamos · 2019
Later among the works it cites.
K-center clustering under perturbation resilience
Maria-Florina Balcan, Nika Haghtalab, and Colin White · 2020
Closest in time.
Beyond the Worst-Case Analysis of Algorithms
Tim Roughgarden · 2020
Closest in time.