Timezone: »
Poster
Stochastic and Adversarial Online Learning without Hyperparameters
Ashok Cutkosky · Kwabena A Boahen
Most online optimization algorithms focus on one of two things: performing well in adversarial settings by adapting to unknown data parameters (such as Lipschitz constants), typically achieving $O(\sqrt{T})$ regret, or performing well in stochastic settings where they can leverage some structure in the losses (such as strong convexity), typically achieving $O(\log(T))$ regret. Algorithms that focus on the former problem hitherto achieved $O(\sqrt{T})$ in the stochastic setting rather than $O(\log(T))$. Here we introduce an online optimization algorithm that achieves $O(\log^4(T))$ regret in a wide class of stochastic settings while gracefully degrading to the optimal $O(\sqrt{T})$ regret in adversarial settings (up to logarithmic factors). Our algorithm does not require any prior knowledge about the data or tuning of parameters to achieve superior performance.
Author Information
Ashok Cutkosky (Google)
Kwabena A Boahen (Stanford University)
More from the Same Authors
-
2021 Spotlight: Online Selective Classification with Limited Feedback »
Aditya Gangrade · Anil Kag · Ashok Cutkosky · Venkatesh Saligrama -
2021 Oral: High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails »
Ashok Cutkosky · Harsh Mehta -
2021 Poster: High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails »
Ashok Cutkosky · Harsh Mehta -
2021 Poster: Online Selective Classification with Limited Feedback »
Aditya Gangrade · Anil Kag · Ashok Cutkosky · Venkatesh Saligrama -
2021 Poster: Logarithmic Regret from Sublinear Hints »
Aditya Bhaskara · Ashok Cutkosky · Ravi Kumar · Manish Purohit -
2018 Poster: Distributed Stochastic Optimization via Adaptive SGD »
Ashok Cutkosky · RĂ³bert Busa-Fekete -
2016 Poster: Online Convex Optimization with Unconstrained Domains and Losses »
Ashok Cutkosky · Kwabena A Boahen -
2013 Demonstration: Controlling Robot Dynamics With Spiking Neurons »
Samir Menon · Sam Fok · Kwabena A Boahen -
2011 Poster: A Brain-Machine Interface Operating with a Real-Time Spiking Neural Network Control Algorithm »
Julie Dethier · Paul Nuyujukian · Chris Eliasmith · Terrence C Stewart · Shauki A Elasaad · Krishna V Shenoy · Kwabena A Boahen -
2007 Spotlight: An in-silico Neural Model of Dynamic Routing through Neuronal Coherence »
Devarajan Sridharan · Brian Percival · john arthur · Kwabena A Boahen -
2007 Poster: An in-silico Neural Model of Dynamic Routing through Neuronal Coherence »
Devarajan Sridharan · Brian Percival · john arthur · Kwabena A Boahen