Timezone: »
In this paper, we use differential privacy as a lens to examine online learning in both full and partial information settings. The differential privacy framework is, at heart, less about privacy and more about algorithmic stability, and thus has found application in domains well beyond those where information security is central. Here we develop an algorithmic property called one-step differential stability which facilitates a more refined regret analysis for online learning methods. We show that tools from the differential privacy literature can yield regret bounds for many interesting online learning problems including online convex optimization and online linear optimization. Our stability notion is particularly well-suited for deriving first-order regret bounds for follow-the-perturbed-leader algorithms, something that all previous analyses have struggled to achieve. We also generalize the standard max-divergence to obtain a broader class called Tsallis max-divergences. These define stronger notions of stability that are useful in deriving bounds in partial information settings such as multi-armed bandits and bandits with experts.
Author Information
Jacob Abernethy (Georgia Institute of Technology)
Young H Jung (University of Michigan)
Chansoo Lee (Google)
Audra McMillan (Northeastern/Boston University)
Ambuj Tewari (University of Michigan)
Related Events (a corresponding poster, oral, or spotlight)
-
2019 Poster: Online Learning via the Differential Privacy Lens »
Thu Dec 12th 01:00 -- 03:00 AM Room East Exhibition Hall B + C
More from the Same Authors
-
2020 Poster: TorsionNet: A Reinforcement Learning Approach to Sequential Conformer Search »
Tarun Gogineni · Ziping Xu · Exequiel Punzalan · Runxuan Jiang · Joshua Kammeraad · Ambuj Tewari · Paul Zimmerman -
2020 Poster: Private Identity Testing for High-Dimensional Distributions »
Clément L Canonne · Gautam Kamath · Audra McMillan · Jonathan Ullman · Lydia Zakynthinou -
2020 Poster: Reinforcement Learning in Factored MDPs: Oracle-Efficient Algorithms and Tighter Regret Bounds for the Non-Episodic Setting »
Ziping Xu · Ambuj Tewari -
2020 Spotlight: Private Identity Testing for High-Dimensional Distributions »
Clément L Canonne · Gautam Kamath · Audra McMillan · Jonathan Ullman · Lydia Zakynthinou -
2020 Poster: On the Equivalence between Online and Private Learnability beyond Binary Classification »
Young H Jung · Baekjin Kim · Ambuj Tewari -
2020 Spotlight: On the Equivalence between Online and Private Learnability beyond Binary Classification »
Young H Jung · Baekjin Kim · Ambuj Tewari -
2019 Poster: Generalization Bounds in the Predict-then-Optimize Framework »
Othman El Balghiti · Adam N. Elmachtoub · Paul Grigas · Ambuj Tewari -
2019 Poster: Learning Auctions with Robust Incentive Guarantees »
Jacob Abernethy · Rachel Cummings · Bhuvesh Kumar · Sam Taggart · Jamie Morgenstern -
2019 Poster: Regret Bounds for Thompson Sampling in Episodic Restless Bandit Problems »
Young H Jung · Ambuj Tewari -
2019 Poster: On the Optimality of Perturbations in Stochastic and Adversarial Multi-armed Bandit Problems »
Baekjin Kim · Ambuj Tewari -
2018 Workshop: CiML 2018 - Machine Learning competitions "in the wild": Playing in the real world or in real time »
Isabelle Guyon · Evelyne Viegas · Sergio Escalera · Jacob D Abernethy -
2018 Poster: Active Learning for Non-Parametric Regression Using Purely Random Trees »
Jack Goetz · Ambuj Tewari · Paul Zimmerman -
2018 Poster: But How Does It Work in Theory? Linear SVM with Random Features »
Yitong Sun · Anna Gilbert · Ambuj Tewari -
2018 Poster: Acceleration through Optimistic No-Regret Dynamics »
Jun-Kun Wang · Jacob Abernethy -
2018 Spotlight: Acceleration through Optimistic No-Regret Dynamics »
Jun-Kun Wang · Jacob Abernethy -
2017 Workshop: Machine Learning Challenges as a Research Tool »
Isabelle Guyon · Evelyne Viegas · Sergio Escalera · Jacob D Abernethy -
2017 Poster: Action Centered Contextual Bandits »
Kristjan Greenewald · Ambuj Tewari · Susan Murphy · Predag Klasnja -
2017 Poster: Online multiclass boosting »
Young H Jung · Jack Goetz · Ambuj Tewari -
2017 Poster: On Frank-Wolfe and Equilibrium Computation »
Jacob D Abernethy · Jun-Kun Wang -
2017 Spotlight: On Frank-Wolfe and Equilibrium Computation »
Jacob D Abernethy · Jun-Kun Wang -
2016 Poster: Hardness of Online Sleeping Combinatorial Optimization Problems »
Satyen Kale · Chansoo Lee · David Pal -
2016 Poster: Phased Exploration with Greedy Exploitation in Stochastic Combinatorial Partial Monitoring Games »
Sougata Chaudhuri · Ambuj Tewari -
2016 Poster: Threshold Bandits, With and Without Censored Feedback »
Jacob D Abernethy · Kareem Amin · Ruihao Zhu -
2015 Poster: Predtron: A Family of Online Algorithms for General Prediction Problems »
Prateek Jain · Nagarajan Natarajan · Ambuj Tewari -
2015 Poster: Fighting Bandits with a New Kind of Smoothness »
Jacob D Abernethy · Chansoo Lee · Ambuj Tewari -
2015 Poster: A Market Framework for Eliciting Private Data »
Bo Waggoner · Rafael Frongillo · Jacob D Abernethy -
2015 Poster: Alternating Minimization for Regression Problems with Vector-valued Outputs »
Prateek Jain · Ambuj Tewari -
2014 Workshop: Large-scale reinforcement learning and Markov decision problems »
Benjamin Van Roy · Mohammad Ghavamzadeh · Peter Bartlett · Yasin Abbasi Yadkori · Ambuj Tewari -
2014 Workshop: NIPS Workshop on Transactional Machine Learning and E-Commerce »
David Parkes · David H Wolpert · Jennifer Wortman Vaughan · Jacob D Abernethy · Amos Storkey · Mark Reid · Ping Jin · Nihar Bhadresh Shah · Mehryar Mohri · Luis E Ortiz · Robin Hanson · Aaron Roth · Satyen Kale · Sebastien Lahaie -
2014 Poster: On Iterative Hard Thresholding Methods for High-dimensional M-Estimation »
Prateek Jain · Ambuj Tewari · Purushottam Kar -
2013 Poster: Minimax Optimal Algorithms for Unconstrained Linear Optimization »
Brendan McMahan · Jacob D Abernethy -
2013 Poster: Convex Calibrated Surrogates for Low-Rank Loss Matrices with Applications to Subset Ranking Losses »
Harish G Ramaswamy · Shivani Agarwal · Ambuj Tewari -
2013 Poster: Adaptive Market Making via Online Learning »
Jacob D Abernethy · Satyen Kale -
2013 Poster: How to Hedge an Option Against an Adversary: Black-Scholes Pricing is Minimax Optimal »
Jacob D Abernethy · Peter Bartlett · Rafael Frongillo · Andre Wibisono -
2013 Spotlight: How to Hedge an Option Against an Adversary: Black-Scholes Pricing is Minimax Optimal »
Jacob D Abernethy · Peter Bartlett · Rafael Frongillo · Andre Wibisono -
2013 Oral: Adaptive Market Making via Online Learning »
Jacob D Abernethy · Satyen Kale -
2013 Spotlight: Convex Calibrated Surrogates for Low-Rank Loss Matrices with Applications to Subset Ranking Losses »
Harish G Ramaswamy · Shivani Agarwal · Ambuj Tewari -
2013 Poster: Learning with Noisy Labels »
Nagarajan Natarajan · Inderjit Dhillon · Pradeep Ravikumar · Ambuj Tewari -
2012 Poster: Feature Clustering for Accelerating Parallel Coordinate Descent »
Chad Scherrer · Ambuj Tewari · Mahantesh Halappanavar · David Haglin -
2011 Poster: A Collaborative Mechanism for Crowdsourcing Prediction Problems »
Jacob D Abernethy · Rafael Frongillo -
2011 Oral: A Collaborative Mechanism for Crowdsourcing Prediction Problems »
Jacob D Abernethy · Rafael Frongillo -
2011 Poster: Greedy Algorithms for Structurally Constrained High Dimensional Problems »
Ambuj Tewari · Pradeep Ravikumar · Inderjit Dhillon -
2011 Poster: On the Universality of Online Mirror Descent »
Nati Srebro · Karthik Sridharan · Ambuj Tewari -
2011 Poster: Nearest Neighbor based Greedy Coordinate Descent »
Inderjit Dhillon · Pradeep Ravikumar · Ambuj Tewari -
2011 Poster: Online Learning: Stochastic, Constrained, and Smoothed Adversaries »
Sasha Rakhlin · Karthik Sridharan · Ambuj Tewari -
2011 Poster: Orthogonal Matching Pursuit with Replacement »
Prateek Jain · Ambuj Tewari · Inderjit Dhillon -
2010 Oral: Online Learning: Random Averages, Combinatorial Parameters, and Learnability »
Sasha Rakhlin · Karthik Sridharan · Ambuj Tewari -
2010 Poster: Online Learning: Random Averages, Combinatorial Parameters, and Learnability »
Sasha Rakhlin · Karthik Sridharan · Ambuj Tewari -
2010 Poster: Smoothness, Low Noise and Fast Rates »
Nati Srebro · Karthik Sridharan · Ambuj Tewari -
2010 Poster: Repeated Games against Budgeted Adversaries »
Jacob D Abernethy · Manfred K. Warmuth -
2008 Poster: On the Generalization Ability of Online Strongly Convex Programming Algorithms »
Sham M Kakade · Ambuj Tewari -
2008 Spotlight: On the Generalization Ability of Online Strongly Convex Programming Algorithms »
Sham M Kakade · Ambuj Tewari -
2008 Poster: On the Complexity of Linear Prediction: Risk Bounds, Margin Bounds, and Regularization »
Sham M Kakade · Karthik Sridharan · Ambuj Tewari -
2007 Poster: Optimistic Linear Programming gives Logarithmic Regret for Irreducible MDPs »
Ambuj Tewari · Peter Bartlett -
2006 Poster: Sample Complexity of Policy Search with Known Dynamics »
Peter Bartlett · Ambuj Tewari