Statistische Abfrageuntergrenzen für das Lernen truncierter Gauss-Gemitteln

Wir untersuchen das Problem, den Mittelwert eines identitätskovarianzen Gauss in einem truncierten Setting zu schätzen, in dem Übertragungsbereich, wenn die Truncationsmenge aus einer Familie C von Mengen mit niedriger Komplexität stammt. Konkret haben wir für eine feste, aber unbekannte Truncationsmenge S Rᵈ Zugang zu Proben aus der Verteilung N (, I), die auf die Menge S trunciert ist. Das Ziel ist es, mit einer Genauigkeit >0 in ₂-Norm zu schätzen. Unser Hauptresultat ist eine untere Grenze für die statistische Abfrage (SQ), die eine überpolynomiale Informations-Berechnungslücke für diese Aufgabe nahelegt. Im Detail zeigen wir, dass die Komplexität jedes SQ-Algorithmus für dieses Problem d^poly (1/), selbst wenn die Klasse C einfach ist, sodass poly (d/) Proben informationstheoretisch ausreichen. Konkret gilt unsere SQ-Untergrenze, wenn C eine Vereinigung einer begrenzten Anzahl von Rechtecken ist, deren VC-Dimension und Gauss-Oberfläche klein sind. Als Folgerung unserer Konstruktion folgt auch, dass die Komplexität des zuvor bekannten Algorithmus für diese Aufgabe qualitativ bestmöglich ist.