Fetching the paper…
Reading the bibliography…
We prove novel algorithmic guarantees for several online problems in the smoothed analysis model.
How good is the simplex algorithm
Victor Klee and George J Minty · 1972
Earlier work this paper cites.
Simple local search problems that are hard to solve
Alejandro A Schäffer · 1991
Earlier work this paper cites.
Ten Lectures on the Probabilistic Method
Joel Spencer · 1994
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.
The Discrepancy Method: Randomness and Complexity
Bernard Chazelle · 2000
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.
Smoothed analysis: Why the simplex algorithm usually takes polynomial time
Daniel A Spielman and Shang-Hua Teng · 2004
Earlier work this paper cites.
How slow is the k-means method?
David Arthur and Sergei Vassilvitskii · 2006
Earlier work this paper cites.
Prediction, learning, and games
Nicolò Cesa-Bianchi and Gábor Lugosi · 2006
Earlier work this paper cites.
Learning, Regret Minimization, and Equilibria
Avrim Blum and Yishay Mansour · 2007
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.
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.
Constructive algorithms for discrepancy minimization
Nikhil Bansal · 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
Earlier work this paper cites.
Learning topic models – going beyond SVD
Sanjeev Arora, Rong Ge, and Ankur Moitra · 2012
Earlier work this paper cites.
The multiplicative weights update method: a meta-algorithm and applications
Sanjeev Arora, Elad Hazan, and Satyen Kale · 2012
Earlier work this paper cites.
Are stable instances easy?
Yonatan Bilu and Nathan Linial · 2012
Earlier work this paper cites.
A simple and practical algorithm for differentially private data release
Moritz Hardt, Katrina Ligett, and Frank McSherry · 2012
Earlier work this paper cites.
Clustering under approximation stability
Maria-Florina Balcan, Avrim Blum, and Anupam Gupta · 2013
Cited alongside, same era.
Concentration Inequalities: A Nonasymptotic Theory of Independence
S. Boucheron, G. Lugosi, and P. Massart · 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.
Bilu–Linial stable instances of max cut and minimum multiway cut
Konstantin Makarychev, Yury Makarychev, and Aravindan Vijayaraghavan · 2014
Cited alongside, same era.
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.
Smoothed analysis in unsupervised learning via decoupling
Aditya Bhaskara, Aidao Chen, Aidan Perreault, and Aravindan Vijayaraghavan · 2019
Later among the works it cites.
On-line balancing of random inputs
Nikhil Bansal and Joel H. Spencer · 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.
Balancing covariates in randomized experiments using the gram-schmidt walk
Christopher Harshaw, Fredrik Sävje, Daniel A. Spielman, and Peng Zhang · 2019
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Spectral sparsification and regret minimization beyond matrix multiplicative updates
Zeyuan Allen-Zhu, Zhenyu Liao, and Lorenzo Orecchia · 2015
Cited alongside, same era.
Constructive discrepancy minimization by walking on the edges
Shachar Lovett and Raghu Meka · 2015
Cited alongside, same era.
Learning and 1-bit compressed sensing under asymmetric noise
Pranjal Awasthi, Maria-Florina Balcan, Nika Haghtalab, and Hongyang Zhang · 2016
Cited alongside, same era.
Algorithmic discrepancy beyond partial coloring
Nikhil Bansal and Shashwat Garg · 2017
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, Arthur Flajolet, Nika Haghtalab, and Patrick Jaillet · 2017
Cited alongside, same era.
Online geometric discrepancy for stochastic arrivals with applications to envy minimization
Haotian Jiang, Janardhan Kulkarni, and Sahil Singla · 2019
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.
Boosting for control of dynamical systems
Naman Agarwal, Nataly Brukhim, Elad Hazan, and Zhou Lu · 2020
Later among the works it cites.
Discrepancy minimization via a self-balancing walk, 2020
Ryan Alweiss, Yang P. Liu, and Mehtaab Sawhney · 2020
Later among the works it cites.
K-center clustering under perturbation resilience
Maria-Florina Balcan, Nika Haghtalab, and Colin White · 2020
Later among the works it cites.
Online discrepancy minimization for stochastic arrivals
Nikhil Bansal, Haotian Jiang, Raghu Meka, Sahil Singla, and Makrand Sinha · 2020
Later among the works it cites.
Online vector balancing and geometric discrepancy
Nikhil Bansal, Haotian Jiang, Sahil Singla, and Makrand Sinha · 2020
Later among the works it cites.
An equivalence between private classification and online prediction
Mark Bun, Roi Livni, and Shay Moran · 2020
Later among the works it cites.
Robust and heavy-tailed mean estimation made simple, via regret minimization
Samuel B. Hopkins, Jerry Li, and Fred Zhang · 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.
Beyond the Worst-Case Analysis of Algorithms
Tim Roughgarden · 2020
Later among the works it cites.
Adversarial laws of large numbers and optimal regret in online classification
Noga Alon, Omri Ben-Eliezer, Yuval Dagan, Shay Moran, Moni Naor, and Eylon Yogev · 2021
Closest in time.
A regret minimization approach to iterative learning control
Naman Agarwal, Elad Hazan, Anirudha Majumdar, and Karan Singh · 2021
Closest in time.
Smoothed Analysis of Local Search
Bodo Manthey · 2021
Closest in time.