Zur Stichprobenkomplexität der Mittelwertschätzung in -norm

Sei , sei eine Verteilung über und nehme an, dass seine Unterstützung in der Einheit -ball enthalten ist. Was ist die minimale Anzahl von iid-Stichproben , , die benötigt werden, um einen Schätzer des Mittelwerts mit der folgenden Garantie zu berechnen ? $1\leq p\leq \infty$ ${\cal D}$ $\mathbb{R}^d$ $p$ $n$ $W_i\sim {\cal D}$ $i=1,\ldots,n$ $\tilde W$

P {‖ \tilde{W} - E_{W \sim D} [W] ‖_{p} \leq ε} \geq 1 - δ .

$\mathbb{P}\{ \| \tilde W- \mathbb{E}_{W\sim {\cal D}}[W]\|_p \leq \varepsilon \} \geq 1-\delta.$

Mich interessiert besonders, wie $n$ von $p$ , $d$ und abhängt $\epsilon$ .

Ich vermute, dass dies in der Vergangenheit untersucht wurde, aber ich konnte keine Referenz finden. Andere Garantien (z. B. in Erwartung) könnten ebenfalls nützlich sein.

Schließlich kann diese Frage unter Berücksichtigung einer beliebigen Norm anstelle von allgemeiner gestellt werden $\|\cdot\|_p$ . Alle Ergebnisse in dieser Richtung wären sehr nützlich.

estimation mean Cristóbal Guzmán
quelle

Naiv erwarte ich keine allgemeine Antwort, die nur von p, d und abhängt . Die Antwort sollte vom Schwanzverhalten von D abhängen. Für ein einfaches Beispiel nehmen Sie eine Normalverteilung mit dem Mittelwert 0 und der Varianz 0,1 (abgeschnitten bei 1 und renormiert) und die Gleichverteilung auf [-1,1] mit d = 1

ϵ

$\epsilon$

Sid

Anscheinend geht es um den schlimmsten Fall, der an alle möglichen Verteilungen gebunden ist, die auf der Einheit -ball unterstützt werden.

ℓ_{p}

$\ell_p$

Vitaly

Welches ist der Rahmen dieser Frage? eine Hausaufgabe, eine Abschlussarbeit?

Brethlosze

Dies scheint das Gesetz der großen Zahlen in seiner schwachen Form zu sein. Die Frage bezieht sich auf das Grenzverhalten nach dem Theorem. Nach dem Chebychev-Lemma gibt es für mit einer -Konvergenz der Grenze, wobei ein Schätzer der Varianz ist, sicherlich andere Grenzen für die Verhalten ....

d = 1

$d=1$

δ (n) = s^{2} / (e^{2} n)

$\delta(n)=s^2/(e^2 n)$

s^{2}

$s^2$

n

$n$

Brethlosze

Danke an alle! Diese Frage tauchte in meiner Forschung auf: Ich möchte Schätzer aus iid-Stichproben mit einem alternativen Modell (statistische Abfragen) vergleichen. Jetzt habe ich einige Grenzen für Letzteres, aber ich weiß nicht, was für Ersteres bekannt ist. Wie Vitaly betonte, besteht die Idee darin, einen Worst-Case-Grenzwert für beliebige Verteilungen zu erhalten, und daher sind die Grenzen in Abhängigkeit von der Varianz eher schwach.

Cristóbal Guzmán

Antworten:

Ein eng verwandtes Thema ist das der Konzentrationsungleichheiten , die Ihnen eine Grenze (der Art, nach der Sie suchen) geben, die auch von der Anzahl der Proben (unter anderem) abhängt. Konkret ist das Konzept der Rademacher-Komplexität ein Standardwerkzeug, um diese Art von Problemen anzugehen. Die Rademacher-Komplexität kann als Permutationstest verstanden werden, bei dem Sie Ihre Beschriftungen zufällig ändern. Wenn Sie sich mit dem Problem der Schätzung des Mittelwerts befassen, gibt die Grenze an, wie wahrscheinlich es ist, dass Sie sich zufällig dem tatsächlichen Mittelwert nähern (wie konzentriert sind die Stichproben um den Mittelwert und wie stabil sind Ihre Schätzungen basierend auf verschiedenen Stichproben). .

Genauer gesagt, für eine Stichprobe der Größe , die aus einer Wahrscheinlichkeitsverteilung , und für eine reelle Funktionsklasse mit Domäne die empirische Rademacher-Komplexität ist die Zufallsvariable, definiert als wobei unabhängige Uniform sind bewertete Zufallsvariablen. Die Rademacher-Komplexität ist, $X=(x_{i})$ $l$ $D$ $F$ $X$

{\hat{R}}_{l} (F) = E_{σ} [s u p_{f \in F} | \frac{2}{l} \sum_{i = 1}^{l} σ_{i} f (x_{i}) | X]

$\hat{R}_{l}(F) = E_{\sigma}\left[sup_{f \in F}\left|\frac{2}{l}\sum_{i=1}^{l}\sigma_{i}f(x_{i})\right|X\right]$

σ = (σ_{1}, . . ., σ_{l})

$\sigma = (\sigma_{1},...,\sigma_{l})$

\pm 1

$\pm1$

R_{l} (F) = E_{S \sim D} [{\hat{R}}_{l} (F)] = E_{S σ} [s u p_{f \in F} | \frac{2}{l} \sum_{i = 1}^{l} σ_{i} f (x_{i}) | X]

$R_{l}(F) = E_{S \sim D}[\hat{R}_{l}(F)] = E_{S\sigma}\left[sup_{f \in F}\left|\frac{2}{l}\sum_{i=1}^{l}\sigma_{i}f(x_{i})\right|X\right]$

Das sup bedeutet, dass es nach der höchstmöglichen Korrelation mit zufälligem Rauschen sucht. Dieses Konzept ist nun aufgrund des folgenden Satzes relevant:

Unter den obigen Bedingungen wird angenommen, dass die Klasse der Abbildungen von bis zum Intervall , und sei eine Stichprobe der Größe . Wenn Sie fixieren , dann erfüllt mit der Wahrscheinlichkeit über zufällige Ziehungen der Größe jedes , $F$ $X$ $[0,1]$ $(z_{i})$ $l$ $\delta \in (0,1)$ $1-\delta$ $l$ $f \in F$

E [f (z)] \leq \hat{E} [f (z)] + R_{l} (F) + \sqrt{\frac{l n (2 / δ)}{2 l}} \leq \hat{E} [f (z)] + {\hat{R}}_{l} (F) + 3 \sqrt{\frac{l n (2 / δ)}{2 l}}

$E[f(z)] \leq \hat{E}[f(z)] + R_{l}(F) + \sqrt{\frac{ln(2/\delta)}{2l}} \leq \hat{E}[f(z)] + \hat{R}_{l}(F) + 3\sqrt{\frac{ln(2/\delta)}{2l}}$

Beachten Sie, dass der Hut verwendet wird, um die empirische Erwartung anzuzeigen, die an einer bestimmten Probe gemessen wurde.

Die Idee ist, eine solche Familie von f zu finden und den Satz zu verwenden. Da eine kompakte Unterstützung hat, wissen Sie, dass in , wobei der Radius der Kugel ist. $D$ $(W-E[W])^{2}/R$ $[0,1]$ $R$

Mit den Eigenschaften der Rademacher Komplexität und einen zweiten Satz mit dem Sie die Rademacher Komplexität für lineare Vorhersage gibt (Details finden sich hier und im Detail hier ), erhalten Sie die folgende für Ihre Wahrscheinlichkeit gebunden

\sqrt{\frac{2 R^{2}}{l}} (\sqrt{2} + \sqrt{l n \frac{1}{δ}})

$\sqrt{\frac{2R^{2}}{l}}\left(\sqrt2 + \sqrt{ln\frac{1}{\delta}}\right)$

PS Ich habe gerade festgestellt, dass Sie sich auf die p-Norm bezogen haben. Trotzdem können Sie die Khintchine-Ungleichung verwenden, um diese Menge an die 2-Norm zu binden.

jpmuc
quelle

Dies ist eine großartige Antwort. Ich werde nur 3 Referenzen vorschlagen: Ein Einführungs-Tutorial: cs.cornell.edu/~sridharan/concentration.pdf --- Bezogen auf maschinelles Lernen, einschließlich einer Diskussion über die Komplexität von Rademacher, Vorlesungen 00-004 cs.nyu.edu / ~ mohri / ml14 --- Und wenn Sie es in die Hände bekommen können, Grundlagen des maschinellen Lernens von Mohri, Rostamizadeh und Talwalkar (2012).

Justanotherbrain

Ich entschuldige mich für die Verspätung. Die Komplexität von Rademacher ist in der Tat nützlich, um diese Frage zu beantworten: Zumindest konnten wir die Komplexität der Stichprobe für Bälle effektiv charakterisieren . Es gibt jedoch ein zusätzliches Tool, das in diesem Beitrag nicht erwähnt wird, daher werde ich eine Antwort darauf hinterlassen.

ℓ_{p}

$\ell_p$

Cristóbal Guzmán

Lassen Sie mich diese Frage und Antwort weiterverfolgen. In der Tat kann die Verbindung der linearen Funktionen des Doppelkörpers zur Rademacher-Komplexität verwendet werden, um Obergrenzen für das Problem bereitzustellen. Aber das ist nicht ganz das, worüber Cristobal und ich fragen. (Ganz zu schweigen davon, dass die Frage, die wir stellen, noch grundlegender ist).

Die Rademacher-Komplexität charakterisiert die Konvergenzrate des empirischen Mittelwerts zum wahren Mittelwert. So kann es eine Obergrenze geben. Diese Obergrenze ist in vielen Fällen eng, aber wir sind an Grenzen interessiert, die für jeden Mittelwertschätzer gelten.

Wir sind auch an Ergebnissen interessiert, die über das einfache (oder sogar für Fälle, die in der Antwort behandelt werden, aber allgemeine Normen, die durch einen konvexen, auf den Ursprung zentrierten Körper definiert sind. $L_2$ $L_p$ $p>2$

Vitaly
quelle

Vielen Dank an alle für die Antworten. Die Komplexität von Rademacher ist in der Tat ein nützliches Werkzeug, um Obergrenzen abzuleiten. Die Komplexität der Probe kann jedoch auch von der Geometrie des konvexen Körpers abhängen, an dem wir interessiert sind. In dieser Hinsicht kann man Ideen der gleichmäßigen Glätte und gleichmäßigen Konvexität aus der Banach-Raumtheorie verwenden, um die richtigen Raten zu erhalten. Dies ist in einigen Bereichen bekannt, aber ich habe keine präzise Referenz gefunden, daher haben wir die Analyse in unser Papier aufgenommen (siehe Anhang B unter http://arxiv.org/pdf/1512.09170v1.pdf ).

Zwei Fragen, die mir noch offen bleiben, sind zum einen: Wie lassen sich Untergrenzen für die Stichprobenkomplexität des empirischen Mittelwerts basierend auf der Rademacher-Komplexität ableiten? Dies ist vermutlich Standard, aber ich habe keine Referenz gefunden. Die zweite Frage lautet: Gibt es Beispiele, bei denen der empirische Mittelwert nicht die beste Stichprobenkomplexität für die Mittelwertschätzung bietet?

Cristóbal Guzmán
quelle