Geschätzter Durchschnitt in Polynomialzeit

20

Sei eine Funktion. Wir wollen den Durchschnitt von f schätzen , das heißt: E [ f ( n ) ] = 2 - nx { 0 , 1 } n f ( x ) .f:{0,1}n(2n,1]fE[f(n)]=2nx{0,1}nf(x)

NOTE: In the OP, the range of f was [0,1]. I changed this a bit for technical reasons. (This should simplify the problem; if not, forget it!)

Sei der (randomisierte) Schätzalgorithmus. Angenommen, E hat Black-Box-Zugriff auf f . Wir bezeichnen dies mit E f .EEfEf

Es gibt zwei Bedingungen:

1) Laufzeit des Schätzers: Es existiert ein einzelnes Polynom so dass für alle n und alle f die Laufzeit von E f ( 1 n ) durch p ( n ) begrenzt ist.p()nfEf(1n) .p(n)E[f(n)]

2) Schätzerpräzision mit Sicherheit :δ Es existiert ein einzelnes Polynom , so dass wir für alle n und alle f 1 habenq()nfmit einer Wahrscheinlichkeit von mindestensδ.1q(n)<Ef(1n)E[f(n)]<q(n)δ

NOTE: The confidence δ was not in the OP. The parameter δ is in (0,1), and may depend on n. For instance, it may be 1-1/2^n.

Gibt es solche Schätzer?

Hintergrund und Motivation

Ich habe meine Motivation anfangs nicht erwähnt, da sie viel Hintergrundwissen erfordert. Jedenfalls beschreibe ich es für die Enthusiasten kurz: Die Notwendigkeit für solche Schätzer ergibt sich im Zusammenhang mit "Proofs of Ability", wie im folgenden Artikel definiert:

Mihir Bellare, Oded Goldreich. Proving Computational Ability , 1992. Unveröffentlichtes Manuskript.

Insbesondere haben die Autoren am Ende von Seite 5 implizit angenommen, dass solche Schätzer existieren (Präzision wird nicht erwähnt, und die Laufzeit ist nicht genau definiert; der Kontext definiert jedoch alles klar.)

Mein erster Versuch war, " Eine Stichprobe von Samplern - Eine rechnerische Perspektive auf das Sampling " zu lesen . Es handelt sich um ein sehr ähnliches Problem, jedoch ist die definierte Fehlerwahrscheinlichkeit additiv, während unsere multiplikativ ist. (Ich habe die Zeitung nicht vollständig gelesen, vielleicht wird erwähnt, was ich irgendwo brauche.)

EDIT (gemäß Tsuyoshis Anfrage): Tatsächlich setzt die Definition von "Proofs of Computational Ability" die Existenz eines "Knowledge Extractor" voraus, dessen (erwartete) Laufzeit . Da wirE[f(n)]nicht kennen, möchten wir es schätzen; Dies darf jedoch die Laufzeit nicht wesentlich verändern: Es sollte sie in einen Polynomfaktor ändern. Die Präzisionsbedingung versucht, eine solche Anforderung zu erfassen.p(n)E[f(n)]E[f(n)]

MS Dousti
quelle
Ich kann den Präzisionszustand nicht verstehen. Was hindert den Algorithmus E daran, immer 1 auszugeben? Meinten Sie 1 / q (n) <(Wahrer Wert) / (Geschätzter Wert) <q (n)?
Tsuyoshi Ito
Es scheint, dass p (n) = q (n) = O (1) und der triviale Algorithmus , der "1" ausgibt, funktionieren sollten. Die Laufzeit ist O (1), die durch p ( n ) begrenzt ist.Ef(1n) . Und die Genauigkeit ist <= 1, was weniger als q (n) ist. p(n)E[f(n)]
Robin Kothari
@ Tsuyoshi & Robin: Sorry Leute, ich habe eine Bedingung in der Präzision verpasst. Schau es dir jetzt an!
MS Dousti
Ich denke auch, dass der Schätzer zufällig ist (nur weil es sonst unmöglich aussieht). Ist das der Fall? Und wenn ja, was genau erfordern die Laufzeitbedingung und die Präzisionsbedingung?
Tsuyoshi Ito
1
Ich glaube, ich verstehe die Frage nicht klar. Warum ist ein naiver Sampler mit Chernoff-Bindung kein guter Schätzer?
Sylvain Peyronnet

Antworten:

15

EDIT: Dies löst die Version des Problems, bei der f nur 0 oder 1 ausgibt. Ich denke jedoch, dass die Lösung angepasst werden kann, damit sie für den allgemeineren Fall funktioniert.

Vielleicht habe ich die Frage falsch verstanden, aber das sieht nicht allzu schwer aus.

Anstatt den Durchschnitt zu schätzen, wollen wir die Anzahl der Einsen schätzen und diese Zahl k nennen. Es sei . Der Durchschnitt ist also k / N. Sie möchten dies innerhalb eines polynomialen multiplikativen Faktors in der Zeit O (N Polylog (N) / k) schätzen.N=2n

Ich denke, dass dies auch innerhalb eines konstanten multiplikativen Faktors getan werden kann. Nehmen wir zum Beispiel an, Sie möchten dies auf einen Faktor von 2 abschätzen. Die Ausgabe des Algorithmus liegt also zwischen k / 2 und 2k.k

Ich werde einen Algorithmus skizzieren, der die entsprechende Laufzeit haben sollte. Überprüfen Sie zuerst, ob k zwischen N / 2 und N liegt. Dies ist einfach, probieren Sie einfach ein paar zufällige Werte aus und wenn Sie mehr als eine halbe 1 erhalten, dann liegt es in diesem Intervall. Sie haben also eine 2-Approximation. Wenn nicht, prüfen Sie, ob es zwischen N / 4 und N / 2 liegt. Und so weiter. Jedes Mal, wenn Sie das Intervall verkleinern, ist es kostspieliger abzuschätzen, ob k in diesem Bereich liegt. Die Kosten sind jedoch umgekehrt proportional zu der Größe des Intervalls.

Wenn Sie beispielsweise prüfen, ob k zwischen und 2 N / 2 q liegt , müssen Sie ungefähr O ( 2 q ) -Anfragen stellen. Auf jeden Fall sollten Sie nach mehrmaligem Wiederholen dieses Vorgangs das Intervall erhalten, in dem k liegt. Sagen wir k liegt zwischen N / 2 q und 2 N / 2 q . Dann ist k ungefähr N / 2 q . Also 2 qN/2q2N/2qO(2q)N/2q2N/2qN/2q2qist über k / N. In diesem Schritt würden wir also O (k / N) Abfragen ausgeben. Für diesen Schritt sind jedoch q andere Schritte erforderlich, dies ist jedoch nur ein zusätzlicher Polylog-Faktor (N). Die Gesamtlaufzeit ist also O (N Polylog (N) / k) für eine 2-Approximation.

(Man müsste tatsächlich eine Fehlerverstärkung durchführen, um in jedem Schritt eine angemessene Präzision zu erzielen. Dies ist jedoch nur ein zusätzlicher Polylog-Faktor.)


Der Grund, warum ich in diesem mehrstufigen Prozess gerne daran denke, ist, dass er den Prozess als eine Voraussage- und Überprüfungsmaßnahme hervorhebt. Wenn dir jemand sagt, dass zwischen N / 2 q und 2 n / 2 q liegt , dann könntest du es in der versprochenen Zeit noch genauer abschätzen, wenn du diese Tatsache kennst. Wir müssen also den Schritt eliminieren, für k eine Vermutung zu erhalten . Dies erfolgt durch binäre Suche über alle möglichen Intervalle dieses Typs.kN/2q2n/2qk

Damit dies bei nicht-booleschen Ausgaben funktioniert, müssen Sie nur die angezeigten Werte summieren, anstatt die Anzahl der Einsen zu zählen. Ich werde versuchen, eine Referenz zu finden, um zu zeigen, dass dies konsequent funktioniert.

Robin Kothari
quelle
(1) Da die Funktion f nicht ganzzahlige Werte annehmen kann, möchten Sie wahrscheinlich die Summe der Werte anstelle der Anzahl der Einsen verwenden. (2) Müssen wir stufenweise abschätzen? Ich vermute, dass wir dies in einer einzigen Stufe tun können, indem wir nur wiederholen, bis die Summe ein festes Polynom überschreitet. Siehe auch meinen Kommentar zur Frage.
Tsuyoshi Ito
Oh, ich habe nicht bemerkt, dass der Bereich [0,1] ist. Ich dachte, es wäre {0,1}. Aber ich denke, das gleiche Verfahren funktioniert. Vielleicht können wir ein Problem auf das andere reduzieren, da wir die Anzahl der Einsen an einer bestimmten Position der binären Darstellung der Ausgabe mit ausreichender Genauigkeit "zählen" können. Über (2) denke ich, dass Ihr Verfahren gleichwertig ist. Ich betrachte es so, weil es sich wie ein Rat- und Überprüfungsprozess anfühlt, dh wenn man eine miese Schätzung von k annimmt, bekommt man eine bessere. Ich werde dies in meine Antwort einfügen.
Robin Kothari
Ich stimme zu, dass die beiden Algorithmen im Wesentlichen gleich sind. Auch bei [0,1] und {0,1} funktioniert Ihr Algorithmus wahrscheinlich so, wie es angegeben ist, nachdem jede Auswertung eines nichtintegralen Werts f (x) durch einen Münzwurf (1 Wp f (x) und 0 Wp) ersetzt wurde 1 - f (x)).
Tsuyoshi Ito
@ Robin: Danke für die Antwort. Mir ist auch etwas unklar: Sie sagten: "Probieren Sie einfach ein paar zufällige Werte aus, und wenn Sie mehr als eine halbe Sekunde erhalten, dann ist es in diesem Intervall." Ich glaube, das muss quantifiziert werden: Wie viele Proben ergeben welche Präzision? (Ich habe OP geändert, um ein solches Vertrauen zu berücksichtigen. Andernfalls wäre es unmöglich, den erforderlichen Sampler zu entwerfen!)
MS Dousti
@ Sadeq: Das ist ein Chernoff-Satz. Wenn Sie erwarten, dass k n / 2 ist (z. B. eine faire Münze), können Sie schnell einen Endwert aufschreiben, wenn Sie mehr als n (1 + eps) / 2 sehen, und in ähnlicher Weise für den unteren Endwert.
Suresh Venkat
3

f1,f2,f{0,1}nki=1kfiMMM=polylog(n)M/k

kμE(f)klowkhighμ1δi=1klowfi<Mi=1khighfi>Mfiklow<k<khigh1δM/k

Warren Schudy
quelle