|
I've seen the concept of regret apply mostly to online learning problems, but while going through the definition it does seem that is not bounded to this setting. I'm trying to come with a simple example to explain this concept in terms of simple linear models. The Wikipedia page does try to do it, but is incomplete at best, does anyone has a reference where there is a worked example of regret being applied in a linear regressions setting. Thanks |
|
I really like Shai Shalev-Shwartz's foundations and trends in machine learning tutorial on online learning. It explains the notion of regret and how it generalizes notions such as optimization and sequential prediction. The online learning scenario is as follows. There is a learner, who at each round plays an action. Then nature, adversarially, selects a reward function (if the action is a vector and the reward function is convex all sorts of nice things can be proven). The idea behind regret is that while it is not always be possible for a learner to do arbitrarily well (indeed, the adversary can always pick a convex function that will strongly hurt the learner, as the adversary plays his action after observing the output of the learner), a good learning algorithm should eventually select a hypothesis which is as good as the best answer in hindsight. Regret is the difference between the loss of the algorithm and the loss of the best answer in hindsight. If the algorithm's regret is sublinear on the number of rounds, then it vanishes on average, and it is said that learning is possible. It is easy, then, to talk about regret in a linear regression setting. In each round the world reveals an x, the learner predicts a y = w^T x, the adversary selects y*, and the learner suffers the loss (y - y*)^2. A common regret guarantee then is that learning algorithms compete well with all w* with bounded norm. |
