Combining Online Learning Guarantees
We show how to take any two parameter-free online learning algorithms with different regret guarantees and obtain a single algorithm whose regret is the minimum of the two base algorithms. Our method is embarrassingly simple: just add the iterates. This trick can generate efficient algorithms that adapt to many norms simultaneously, as well as providing diagonal-style algorithms that still maintain dimension-free guarantees. We then proceed to show how a variant on this idea yields a black-box procedure for generating optimistic online learning algorithms. This yields the first optimistic regret guarantees in the unconstrained setting and generically increases adaptivity. Further, our optimistic algorithms are guaranteed to do no worse than their non-optimistic counterparts regardless of the quality of the optimistic estimates provided to the algorithm.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Adaptive prediction theory combining offline and online learning
Real-world intelligence systems usually operate by combining offline learning and online adaptation with highly correlated and non-stationary system data or signals, which, however, has rarely been investigated theoretic…
Anytime Online-to-Batch Conversions, Optimism, and Acceleration
A standard way to obtain convergence guarantees in stochastic convex optimization is to run an online learning algorithm and then output the average of its iterates: the actual iterates of the online learning algorithm d…
Combining Adversarial Guarantees and Stochastic Fast Rates in Online Learning
We consider online learning algorithms that guarantee worst-case regret rates in adversarial environments (so they can be deployed safely and will perform robustly), yet adapt optimally to favorable stochastic environmen…
An Analysis of Model-Based Reinforcement Learning From Abstracted Observations
Many methods for Model-based Reinforcement learning (MBRL) in Markov decision processes (MDPs) provide guarantees for both the accuracy of the model they can deliver and the learning efficiency. At the same time, state a…
Model-based Reinforcement Learningreinforcement-learningReinforcement LearningReinforcement Learning (RL)Data-driven system analysis of nonlinear systems using polynomial approximation
In the context of data-driven control of nonlinear systems, many approaches lack of rigorous guarantees, call for nonconvex optimization, or require knowledge of a function basis containing the system dynamics. To tackle…