Timezone: »
Poster
No-Regret Algorithms for Unconstrained Online Convex Optimization
Matthew Streeter · Brendan McMahan
Wed Dec 05 07:00 PM -- 12:00 AM (PST) @ Harrah’s Special Events Center 2nd Floor
Some of the most compelling applications of online convex optimization, including online prediction and classification, are unconstrained: the natural feasible set is R^n. Existing algorithms fail to achieve sub-linear regret in this setting unless constraints on the comparator point x* are known in advance. We present an algorithm that, without such prior knowledge, offers near-optimal regret bounds with respect to any choice of x. In particular, regret with respect to x = 0 is constant. We then prove lower bounds showing that our algorithm's guarantees are optimal in this setting up to constant factors.
Author Information
Matthew Streeter (Duolingo)
Brendan McMahan (Google Research)
More from the Same Authors
-
2021 Poster: Differentially Private Learning with Adaptive Clipping »
Galen Andrew · Om Thakkar · Brendan McMahan · Swaroop Ramaswamy -
2020 Tutorial: (Track1) Federated Learning and Analytics: Industry Meets Academia Q&A »
Peter Kairouz · Brendan McMahan · Virginia Smith -
2020 Poster: Privacy Amplification via Random Check-Ins »
Borja Balle · Peter Kairouz · Brendan McMahan · Om Thakkar · Abhradeep Guha Thakurta -
2020 Tutorial: (Track1) Federated Learning and Analytics: Industry Meets Academia »
Brendan McMahan · Virginia Smith · Peter Kairouz -
2019 : Privacy for Federated Learning, and Federated Learning for Privacy »
Brendan McMahan -
2019 Workshop: Workshop on Federated Learning for Data Privacy and Confidentiality »
Lixin Fan · Jakub Konečný · Yang Liu · Brendan McMahan · Virginia Smith · Han Yu -
2018 : Brendan McMahan »
Brendan McMahan -
2018 Poster: Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimization »
Blake Woodworth · Jialei Wang · Adam Smith · Brendan McMahan · Nati Srebro -
2018 Spotlight: Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimization »
Blake Woodworth · Jialei Wang · Adam Smith · Brendan McMahan · Nati Srebro -
2018 Poster: cpSGD: Communication-efficient and differentially-private distributed SGD »
Naman Agarwal · Ananda Theertha Suresh · Felix Xinnan Yu · Sanjiv Kumar · Brendan McMahan -
2018 Spotlight: cpSGD: Communication-efficient and differentially-private distributed SGD »
Naman Agarwal · Ananda Theertha Suresh · Felix Xinnan Yu · Sanjiv Kumar · Brendan McMahan -
2014 Poster: Delay-Tolerant Algorithms for Asynchronous Distributed Online Learning »
Brendan McMahan · Matthew Streeter -
2013 Poster: Minimax Optimal Algorithms for Unconstrained Linear Optimization »
Brendan McMahan · Jacob D Abernethy -
2013 Poster: Estimation, Optimization, and Parallelism when Data is Sparse »
John Duchi · Michael Jordan · Brendan McMahan -
2009 Poster: Online Learning of Assignments »
Matthew Streeter · Daniel Golovin · Andreas Krause -
2009 Spotlight: Online Learning of Assignments »
Matthew Streeter · Daniel Golovin · Andreas Krause -
2008 Poster: An Online Algorithm for Maximizing Submodular Functions »
Matthew Streeter · Daniel Golovin -
2008 Spotlight: An Online Algorithm for Maximizing Submodular Functions »
Matthew Streeter · Daniel Golovin