19
$\begingroup$

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.)

$\endgroup$
  • $\begingroup$ Is it possible to add a short description of internal regret to the question? $\endgroup$ – Moritz Aug 20 '10 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$ – Noam Aug 20 '10 at 16:01
9
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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).

$\endgroup$
  • 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$ – Noam Aug 20 '10 at 15:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.