Zinkevich's "online convex optimization" ( http://www.cs.cmu.edu/~maz/publications/ICML03.pdf ) generalizes "regret minimization" learning algorithms from a linear settings to a convex setting and gives good "external regret". Is there a similar generalization for internal regret? (I'm not totally sure even what exactly that would mean.)
-
$\begingroup$ Is it possible to add a short description of internal regret to the question? $\endgroup$– MoritzAug 20, 2010 at 15:48
-
$\begingroup$ In the usual "experts" setting internal regret would means that in retrospect you would not want switch one action with another, consistently over the whole history. The Blum-Mansour paper is probably the best reference for internal vs. external regret: jmlr.csail.mit.edu/papers/volume8/blum07a/blum07a.pdf $\endgroup$– NoamAug 20, 2010 at 16:01
2 Answers
Try "No-regret learning in convex games" by Gordon, Greenwald and Marks http://portal.acm.org/citation.cfm?id=1390202 . Its abstract sounds like it probably answers your question, or at least anyone answering that question would cite or be cited by that paper.
This Avrim Blum paper points a connection between external and internal regret. According to its abstract, externa regret is a measure of how bad an algorithm is compared to the best fixed action, while internal regret compares to the best variation of that method (best fixed permutation of outputs, like reporting class A whenever the original algorithm reported class B).
-
1$\begingroup$ The Blum-Mansour paper is not in the "online convex optimization" setting, but rather in the linear "experts" setting. My question is whether something similar, or some other direct internal regret algorithm can be applied in the convex setting. $\endgroup$– NoamAug 20, 2010 at 15:57