<p><a href="http://jmlr.csail.mit.edu/papers/volume8/blum07a/blum07a.pdf" rel="nofollow">This Avrim Blum paper</a> 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).</p>

CC BY-SA 2.5
2010-08-20T15:57:44.707Z
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.
Noam
CC BY-SA 2.5
2010-08-20T12:29:18.313Z
2010-08-20T12:29:18.313Z
Alexandre Passos
<p>Try "No-regret learning in convex games" by Gordon, Greenwald and Marks <a href="http://portal.acm.org/citation.cfm?id=1390202">http://portal.acm.org/citation.cfm?id=1390202</a> . Its abstract sounds like it probably answers your question, or at least anyone answering that question would cite or be cited by that paper.</p>

CC BY-SA 2.5
2010-10-06T14:40:34.527Z
2010-10-06T14:45:48.080Z
2010-10-06T14:45:48.080Z
Warren Schudy
<p>Zinkevich's "online convex optimization" ( <a href="http://www.cs.cmu.edu/~maz/publications/ICML03.pdf">http://www.cs.cmu.edu/~maz/publications/ICML03.pdf</a> ) 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.)</p>

CC BY-SA 2.5
2010-08-20T15:48:09.207Z
Is it possible to add a short description of internal regret to the question?
Moritz
CC BY-SA 2.5
2010-08-20T16:01:02.643Z
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: http://jmlr.csail.mit.edu/papers/volume8/blum07a/blum07a.pdf
Noam
<lg.learning><online-learning>
Internal Regret in Online Convex Optimization
Noam
# Internal Regret in Online Convex Optimization

(Asked by: username_0 on 2010-08-19)

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

**Tags:** lg.learning, online-learning

> **Comments:**
> **username_1**: Is it possible to add a short description of internal regret to the question?  
> **username_0**: 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: http://jmlr.csail.mit.edu/papers/volume8/blum07a/blum07a.pdf  

---

## 2 answers

### Answer by username_3 on 2010-10-06. Score: 9 | Accepted answer

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.


---

### Answer by username_2 on 2010-08-20. Score: 0

[This Avrim Blum paper](http://jmlr.csail.mit.edu/papers/volume8/blum07a/blum07a.pdf) 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).

> **Comments:**
> **username_0**: 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.  

---

