Yaos Minimax-Prinzip für Monte-Carlo-Algorithmen

22

Das berühmte Minimax-Prinzip von Yao beschreibt die Beziehung zwischen Verteilungskomplexität und randomisierter Komplexität. Sei ein Problem mit einer endlichen Menge von Eingaben und einer endlichen Menge von deterministischen Algorithmen, um zu lösen . Außerdem bezeichnen die Eingabeverteilung und die Wahrscheinlichkeitsverteilung für . Dann lautet das Prinzip P PX XAA P PD DR RA Amin A AE c O s t ( A , D ) max x XE c o s t ( R , x )für alle  D  und  R .

minAAEcost(A,D)maxxXEcost(R,x)for all D and R.
Dieser Beweis folgt direkt aus von Neumanns Minimaxsatz für Nullsummenspiele.

Meistens befasst sich Yaos Prinzip nur mit Las Vegas-Algorithmen , aber es kann wie folgt auf Monte-Carlo-Algorithmen verallgemeinert werden. wobei cost_ \ epsilon (\ cdot, \ cdot) die Kosten von Monte-Carlo-Algorithmen bezeichnet, bei denen die Wahrscheinlichkeit höchstens \ epsilon falsch ist .12 minA AE c O s t 2 ε ( A , D ) max x XE c o s t ϵ ( R , x )für alle  DR  und  ε [ 0 , 1 / 2 ]

12minAAEcost2ϵ(A,D)maxxXEcostϵ(R,x)for all DR and ϵ[0,1/2]
c O s t ε ( , ) costϵ(,)εϵ

In Yaos Originalarbeit ist die Beziehung für Monte-Carlo-Algorithmen in Satz 3 ohne Beweis angegeben. Irgendein Hinweis, um es zu beweisen?

Federico Magallanez
quelle

Antworten:

6

Dies ist nur ein ausführlicher Kommentar zu Marcos 'Antwort in seiner Notation. Ich bin nicht in der Lage, den Einzelheiten seines Arguments zu folgen, und das folgende ist ziemlich kurz und einfach.

Durch wird Σ A q(A) Σ x d ( x ) ε ( A , x ) = Σ x d(x) Σ A q ( A ) ε ( A , x )& lgr;.

Aq(A)xd(x)ϵ(A,x)=xd(x)Aq(A)ϵ(A,x)λ.

Die obige Tatsache und Markovs Ungleichung implizieren .Σ A & bgr; ( 2 λ ) q ( A )1 / 2Aβ(2λ)q(A)1/2

So bekommen wir:

max x A q ( A ) r ( A , x ) x d ( x ) A q ( A ) r ( A , x )= A q ( A ) x d ( x ) r ( A , x )A β ( 2 λ ) q ( A ) x d ( x ) r ( A , x )( A β ( 2 λ ) q ( A ) ) min A β ( 2 λ ) x d ( x ) r ( A , x )12 minAβ(2λ) xd(x)r(A,x)

maxxAq(A)r(A,x)xd(x)Aq(A)r(A,x)=Aq(A)xd(x)r(A,x)Aβ(2λ)q(A)xd(x)r(A,x)Aβ(2λ)q(A)minAβ(2λ)xd(x)r(A,x)12minAβ(2λ)xd(x)r(A,x)
Sasho Nikolov
quelle
8

Ich werde es versuchen. Ich werde die Originalnotation von Yao verwenden. Auf diese Weise wird es einfacher, einen Kontrast zu seinem Papier und seinen Definitionen herzustellen.

Sei eine endliche Menge von Eingaben, und sei eine endliche Menge von deterministischen Algorithmen, die auf einige Eingaben möglicherweise keine korrekte Antwort geben. Lassen Sie auch wenn die richtige Antwort für liefert , und wenn nicht. Bezeichnen Sie mit die Anzahl der Abfragen, die bei Eingabe von , oder äquivalent die Tiefe des Entscheidungsbaums vonI A 0( A , x ) = 0 A x ( A , x ) = 1 r ( A , x ) A x AIA0ϵ(A,x)=0Axϵ(A,x)=1r(A,x)AxA

Durchschnittskosten: Bei gegebener Wahrscheinlichkeitsverteilungdd auf I , die durchschnittlich Kosten einen Algorithmus ist .IAA0AA0C(A,d)=xId(x)r(A,x)C(A,d)=xId(x)r(A,x)

Verteilungskomplexität: Sei . Für jede Verteilung auf den Eingaben sei die Teilmenge von gegeben durch . Die Verteilungskomplexität mit Fehler für ein Rechenproblem ist definiert als .λ[0,1]λ[0,1]ddβ(λ)β(λ)A0A0β(λ)={A:AA0,xId(x)ϵ(A,x)λ}β(λ)={A:AA0,xId(x)ϵ(A,x)λ}λλPPF1,λ(P)=maxdminAβ(λ)C(A,d)F1,λ(P)=maxdminAβ(λ)C(A,d)

λλ -toleranz: Eine Verteilung auf die Familie ist -tolerant, wenn .qqA0A0λλmaxxIAA0q(A)ϵ(A,x)λmaxxIAA0q(A)ϵ(A,x)λ

Erwartete Kosten: Für einen randomisierten Algorithmus sei eine Wahrscheinlichkeitsverteilung, die tolerant für . Die erwarteten Kosten von für eine gegebene Eingabe sind .RRqqλλA0A0RRxxE(R,x)=AA0q(A)r(A,x)E(R,x)=AA0q(A)r(A,x)

Randomisierte Komplexität: Lassen Sie . Die randomisierte Komplexität mit dem Fehler ist .λ[0,1]λ[0,1]λλF2,λ=minRmaxxIE(R,x)F2,λ=minRmaxxIE(R,x)

Jetzt sind wir bereit, ins Geschäft einzusteigen. Was wir beweisen wollen, ist eine Verteilung auf die Eingaben und ein randomisierter Algorithmus (dh eine Verteilung auf ).ddRRqqA0A0

Yaos Minimax-Prinzip für Montecarlo-Algorithmen für .maxxIE(R,x)12minAβ(2λ)C(A,d)

maxxIE(R,x)12minAβ(2λ)C(A,d)
λ[0,1/2]λ[0,1/2]

Ich werde einem Ansatz von Fich, Meyer auf der Heide, Ragde und Wigderson folgen (siehe Lemma 4). Ihr Ansatz liefert keine Charakterisierung für Las Vegas-Algorithmen (nur die untere Schranke), ist aber für unsere Zwecke ausreichend. Aus ihrem Beweis ist es leicht zu ersehen, dass undA0A0II

1. .maxxIE(R,x)minAA0C(A,d)maxxIE(R,x)minAA0C(A,d)

Um dort die richtigen Zahlen zu erhalten, werden wir etwas Ähnliches tun. Da die Wahrscheinlichkeitsverteilung durch die randomisierten Algorithmus gegeben ist -toleranten auf wir haben , dass Wenn wir die Familie durch ersetzenqqRRλλA0A0λmaxxI{AA0q(A)ϵ(A,x)}xId(x)AA0q(a)ϵ(A,x)=AA0q(a)xId(x)ϵ(A,x)minAA0{xId(x)ϵ(A,x)}.

λmaxxI{AA0q(A)ϵ(A,x)}xId(x)AA0q(a)ϵ(A,x)=AA0q(a)xId(x)ϵ(A,x)minAA0{xId(x)ϵ(A,x)}.
A0A0β(2λ)β(2λ) wir sehen das

λmaxxI{AA0q(A)ϵ(A,x)}maxxI{Aβ(2λ)q(A)ϵ(A,x)}xId(x)Aβ(2λ)q(a)ϵ(A,x)=Aβ(2λ)q(a)xId(x)ϵ(A,x)minAβ(2λ){12xId(x)ϵ(A,x)},

λmaxxI{AA0q(A)ϵ(A,x)}maxxIAβ(2λ)q(A)ϵ(A,x)xId(x)Aβ(2λ)q(a)ϵ(A,x)=Aβ(2λ)q(a)xId(x)ϵ(A,x)minAβ(2λ){12xId(x)ϵ(A,x)},

wobei die zweite Ungleichung folgt, weil und die letzte Ungleichung durch die Definition von wobei die durch 2 geteilte Summe nicht größer sein kann als . Daher β(2λ)A0β(2λ)A0β(2λ)β(2λ)λλmaxxI{AA0q(A)ϵ(A,x)}12minAβ(2λ){xId(x)ϵ(A,x)}.

maxxI{AA0q(A)ϵ(A,x)}12minAβ(2λ){xId(x)ϵ(A,x)}.

Indem wir feststellen, dass auf und auf und Anspruch 1 oben abgebildet sind, können wir jetzt die Funktion in der obigen Ungleichung sicher durch ersetzen , um zu erhalten die gewünschte Ungleichung.ϵϵ{0,1}{0,1}rrNNϵϵr(A,x)r(A,x)

Marcos Villagra
quelle
Gibt es eine kurze Erklärung, woher der Faktor 2 kommt?
Robin Kothari
Kurz gesagt, es kommt aus der Definition von . Die Summe in der Definition geteilt durch 2 ist höchstens . β(2λ)λ
Marcos Villagra
Mir kommt etwas komisch vor. per definitionem also warum die min? maxAβ(2λ)){12xId(x),ϵ(A,x)}λ
Sasho Nikolov
und ich verstehe den letzten satz nicht. Wie haben Sie ein ganzes Argument über und es dann durch ? ϵr
Sasho Nikolov
Zu Ihrer ersten Frage habe ich weitere Details hinzugefügt.
Marcos Villagra