Because life is too short to tune learning rates. By Francesco Orabona
This time we consider an application of Online Mirror Descent (OMD) to the problem of prediction with multi-scale expert advice. In this setting, at each time step , an algorithm selects a probability distribution over a set of experts (or actions). After observing a loss vector , the algorithm incurs a loss of . The [ ]
This is the last post in this series to show that online learning is more than online learning. This time it is about using an online linear optimization algorithm to minimize non-convex, non-smooth functions with access to stochastic gradients. Unlike in the previous two posts, here we will actually use the online algorithm itself, not [ ]
This is the second post in my series of From Online Learning to X . Last time, we saw how to derive Rademacher complexity bounds using the existence of online learning algorithms. This time, we will see how to go from online learning to PAC-Bayes bounds, using the existence of parameter-free algorithms for the learning with [ ]
This is the first of three posts to show that online learning is more than just online learning! Each of these posts will show how we can go from online learning to X, where X will be something completely unrelated to online learning. These results are based on the fact that a linear regret proof [ ]
We now consider online learning with delayed feedback. We consider a constant delay of length , where at time the learner has only observed before producing . In other words, the learner observes at time . This means that the algorithm receives its first feedback at round and it receives no feedback before that round. [ ]
This time I will describe an online algorithm that is better than the Percetron algorithm. This is one of those results that I consider fundamental in online learning, yet not enough widely known. 1. The Gaptron Algorithm We introduce the Gaptron algorithm, a randomized first-order algorithm for online binary and multiclass classification. The key motivation [ ]
We continue our journey into algorithms that predicts distributions and this time we talk about the Aggregating Algorithm. 1. The Aggregating Algorithm and Mixable Losses Here, we show how to extend the Weighted Average Algorithm (WAA) we saw last time to a larger class of loss functions. We will assume to be a probability density [ ]
This time we will introduce the Weighted Average Algorithm (WAA). I will do it my way: I am allergic to present for each algorithm a different analysis! From my blog it should be clear that we only have two main algorithms in online learning: OMD and FTRL. So, 99% of the online algorithms are instantiations [ ]
In this post, we introduce yet another way to quantify the ability of online learning algorithms to compete with a different comparators, besides the dynamic regret that we saw last time. 1. Strongly Adaptive Regret We introduce the concept of strongly adaptive regret: This definition captures the fact that we want the performance of the [ ]
In this post, we will see how to extend the notion of regret to a sequence of comparators instead of a single one. We saw that the definition of regret makes sense as a direct generalization of both the stochastic setting and the offline optimization. However, in some cases, we know that the environment is [ ]