Interne Regret in Online Convex Optimization

19

Zinkevichs "Online-Konvexoptimierung" ( http://www.cs.cmu.edu/~maz/publications/ICML03.pdf ) verallgemeinert die Lernalgorithmen zur "Minimierung des Bedauerns" von einer linearen Einstellung auf eine konvexe Einstellung und gibt eine gute "externe Bedauern" . Gibt es eine ähnliche Verallgemeinerung für internes Bedauern? (Ich bin mir nicht ganz sicher, was genau das bedeuten würde.)

lg.learning online-learning Noam
quelle
Ist es möglich, der Frage eine kurze Beschreibung des internen Bedauerns hinzuzufügen?
Moritz
In den üblichen "Experten" würde internes Bedauern bedeuten, dass Sie im Nachhinein nicht möchten, dass eine Aktion durch eine andere ersetzt wird, und zwar konsistent über die gesamte Geschichte. Das Blum-Mansour-Papier ist wahrscheinlich die beste Referenz für internes und externes Bedauern: jmlr.csail.mit.edu/papers/volume8/blum07a/blum07a.pdf
Noam

Antworten:

9

Probieren Sie "No-Regre-Learning in konvexen Spielen" von Gordon, Greenwald und Marks http://portal.acm.org/citation.cfm?id=1390202 . Das Abstract klingt so, als würde es wahrscheinlich Ihre Frage beantworten, oder zumindest würde jemand, der diese Frage beantwortet, von diesem Artikel zitieren oder zitiert werden.

Warren Schudy
quelle
0

Dieses Avrim Blum-Papier weist auf einen Zusammenhang zwischen äußerem und innerem Bedauern hin. Laut seiner Zusammenfassung ist externa regret ein Maß dafür, wie schlecht ein Algorithmus mit der besten festen Aktion verglichen wird, während internes Bedauern mit der besten Variation dieser Methode verglichen wird (beste feste Permutation von Ausgaben wie Berichtsklasse A, wenn der ursprüngliche Algorithmus dies meldet Klasse b).

Alexandre Passos
quelle
1
Das Blum-Mansour-Papier befindet sich nicht in der Einstellung "Online-Konvexoptimierung", sondern in der linearen Einstellung "Experten". Meine Frage ist, ob etwas ähnliches oder ein anderer direkter interner Reue-Algorithmus in der konvexen Einstellung angewendet werden kann.
Noam