Was sind die bestmöglichen Zeit- / Fehler-Kompromisse für die ungefähre Lösung linearer Programme?

19

Betrachten Sie der Vollständigkeit halber die LP zum Lösen eines Zweispieler-Nullsummenspiels, bei dem jeder Spieler Aktionen hat. Angenommen, jeder Eintrag in der Auszahlungsmatrix hat einen absoluten Wert von höchstens 1. Nehmen wir der Einfachheit halber keine sparsamen Annahmen an.AnA

Angenommen, Laufzeit ist verfügbar, um den Wert dieses Spiels zu schätzen.T

Eine Technik zum Annähern dieses Werts ist die multiplikative Aktualisierungsmethode (in diesem Kontext als No-Regret-Lernen bekannt). Dies führt zu einem Fehler von , wobei Protokollfaktoren verbirgt.OO~(n/T)O~

Ich weiß nicht genau, wie die Fehlerlandschaft für die bekannteste Innenpunktmethode aussieht, aber ich vermute, der Fehler ist so etwas wie .O(exp(T/n3))

Die multiplikativen Aktualisierungsmethoden liefern einen Fehler, der ein inverses Polynom in . Innere Punktmethoden geben einen Fehler, der in exponentiell klein ist . Der Fehler des besten der beiden nimmt daher langsam ab, bis der innere Punkt aufholt, wonach der Fehler plötzlich von einer Klippe fällt. Mein Instinkt ist gegen die bestmöglichen Zeit- / Fehler-Kompromisse, wenn ich mich so verhalte.TTT

Meine frage :

Gibt es einen Algorithmus für die ungefähre lineare Programmierung, der die Ecke der Zeit- / Fehler-Kompromisskurve glättet? Das heißt, ein Algorithmus, der für jeden Wert des verfügbaren Zeitparameters mindestens so gut wie der beste der beiden ist und einen relativ reibungslosen Kompromiss zwischen Zeit und Fehler aufweist. Ein intelligenterer Weg, um interne und multiplikative Aktualisierungstechniken zu kombinieren, als den besseren der beiden zu verwenden, ist wahrscheinlich ein Weg, um einen solchen Algorithmus zu erhalten.

Referenzen :

Multiplikatives Update im Allgemeinen:

http://www.cs.princeton.edu/~arora/pubs/MWsurvey.pdf

Multiplikatives Update für Nullsummenspiele:

http://dx.doi.org/10.1016/0167-6377(95)00032-0

Multiplikatives Update zum Abdecken / Verpacken von LPs:

http://arxiv.org/PS_cache/arxiv/pdf/0801/0801.1987v1.pdf

Das originale Innenpapier:

http://math.stanford.edu/~lekheng/courses/302/classics/karmarkar.pdf

Innenpunkt aus der Perspektive der angewandten Mathematik:

Bertsekas 'nichtlineare Programmierung , Abschnitt 4.1.1.

Warren Schudy
quelle

Antworten:

2

Vielleicht ist dieser Verweis für Ihre Frage relevant.

Grigoriadis M., Khachiyan L. Ein sublinearer randomisierter Approximationsalgorithmus für Matrixspiele // Oper. Res. Lette. 1995. V. 18. Nr. 2. S. 53-58.

Der Algorithmus darin ist 1) randomisiert 2) der Fehler ist ADDITIV, aber 3) sublinear (Sie müssen nur einen winzigen Bruchteil der Eingabe überprüfen, um die Lösung mit hoher Wahrscheinlichkeit zu finden).

Sergey

Sergey
quelle
In der Tat ist dieses Papier ziemlich relevant. Dies ist der zweite Link, der im Abschnitt "Referenzen" meiner Frage angegeben ist.
Warren Schudy
Pardon. Ich habe übersehen, dass der Verweis bereits existiert. Daher sollte mein Kommentar entfernt oder als Rezension eines der Texte in Ihrer Liste angesehen werden. Einige zusätzliche Ergebnisse der gleichen Art, jedoch über einen allgemeineren Rahmen, können in Juditsky, A., Lan, G., Nemirovski, A., Shapiro, A. gefunden werden (2009), 1574 & ndash; 1609. Sergey
Sergey