Étant donné

11

Voici un problème avec une saveur similaire à l'apprentissage des juntes:

Entrée: Une fonction f:{0,1}n{1,1} , représentée par un oracle d'appartenance, c'est-à-dire un oracle qui a donné X , renvoie F(X) .

Objectif: trouver un sous-cube S de {0,1}n avec le volume |S|=2n-k tels que |EXSF(X)|0,1 . Nous supposons qu'un tel sous-cube existe.

Il est facile d'obtenir un algorithme qui s'exécute dans le temps nO(k) et renvoie une réponse correcte avec une probabilité 0,99 en essayant toutes les (2n)k façons de choisir un sous-cube et en échantillonnant la moyenne de chacun.

Je suis intéressant de trouver un algorithme qui s'exécute dans le temps poly(n,2k) . Alternativement, une borne inférieure serait formidable. Le problème a une saveur similaire à l'apprentissage des juntes, mais je ne vois pas de lien réel entre leur difficulté de calcul.

Mise à jour: @Thomas ci-dessous prouve que la complexité de l'échantillon de ce problème est poly(2k,Journaln) . La question intéressante est, encore, la complexité de calcul du problème.

Edit: vous pouvez supposer pour simplifier qu'il existe un sous-cube avec |EXSF(X)|0,2 (notez l'écart: nous recherchons un sous-cube avec une moyenne 0,1 .) Je suis sûr que toute solution au problème avec l'écart résoudra également le problème sans l'écart.

boulette de Mobius
la source

Réponses:

7

Voici une meilleure limite sur la complexité de l'échantillon. (Bien que la complexité de calcul soit toujours .)nk

Théorème. Supposons qu'il existe un sous-cube de taille 2 n - k tel que | E x S [ f ( x ) ] | 0,12 . Avec O ( 2 kk log n ) échantillons, nous pouvons, avec une forte probabilité, identifier un sous-cube S de taille 2 n - k tel que | E x S [ fS2n-k|EXS[F(X)]|0,12O(2kkJournaln)S2n-k .|EXS[F(X)]|0,1

Notez la petite perte de paramètres ( est optimale contre garantie de 0,1 ).0,120,1

Preuve. Pick - points de P { 0 , 1 } n uniformément au hasard et requête f à chaque x P .mP{0,1}nFXP

Fixez un sous-cube de taille 2 n - k . Nous avons E [ | S P | ] = m 2 - k . Par une borne Chernoff, P [ | S P | < m 2 - k - 1 ] 2 - Ω ( m 2 - k ) . Aussi P [ | E x S S2n-kE[|SP|]=m2-k

P[|SP|<m2-k-1]2-Ω(m2-k).
P[|EXSP[F(X)]-EXS[F(X)]|>ε]2-Ω(|SP|ε2).

Par une union liée à tous choix deS, on aP[S| ExSP[f(x)]-ExS[f(x)]| ε]1- ( n(nk)2kSAinsi, en choisissantm=O(2k/ε2klogn), nous pouvons nous assurer qu'avec une probabilité d'au moins0,99, nous pouvons estimerExS[f(x)]àεprès pour tous les sous-cubesSde taille2n-k

P[S  |EXSP[F(X)]-EXS[F(X)]|ε]1-(nk)2k2-Ω(m2-kε2).
m=O(2k/ε2kJournaln)0,99EXS[F(X)]εS2n-k.

En posant , nous prouvons le théorème: choisir le sous-cube avec le plus grand | E x S P [ f ( x ) ] | satisfera, avec une probabilité élevée, aux exigences. QEDε=0,01|EXSP[F(X)]|

Thomas
la source
1
C2kCCnk
3
Une autre façon de voir cela est que l'espace de plage que vous décrivez a une dimension de rupture limitée et donc une dimension VC limitée, puis vous lui lancez le théorème d'approximation eps.
Suresh Venkat