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

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.$n$$A$

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. ≤ $\tilde O(\sqrt{n/T})$$\tilde 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/n^3))$

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.$T$$T$

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.

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