Dado , encontre um subcubo com grande volume e grande valor médio

11

Aqui está um problema com um sabor semelhante ao aprendizado de juntas:

Entrada: Uma função , representada por um oracle de associação, ou seja, um oracle que forneceu , retorna .f:{0,1}n{1,1}xf(x)

Objetivo: Encontre um subcubo de com volume modo que . Assumimos que esse subcubo exista.S{0,1}n|S|=2nk|ExSf(x)|0.1

É fácil obter um algoritmo que seja executado no tempo e retorne uma resposta correta com probabilidade , tentando todas as maneiras de escolher um subcubo e amostrar a média em cada um.0,99 ( 2 n ) knO(k)0.99(2n)k

Eu sou interessante em encontrar um algoritmo que é executado no tempo . Como alternativa, um limite inferior seria ótimo. O problema tem um sabor semelhante ao aprendizado de juntas, mas não vejo uma conexão real entre as dificuldades computacionais.poly(n,2k)

Atualização: @Thomas abaixo prova que a complexidade da amostra deste problema é . A questão interessante é, ainda, a complexidade computacional do problema.poly(2k,logn)

Edit: você pode assumir por simplicidade que existe um subcubo com (observe a lacuna: estamos procurando um subcubo com média .) Tenho certeza de que qualquer solução para o problema da lacuna também resolverá o problema sem a lacuna.0,1|ExSf(x)|0.20.1

bolinho de massa mobius
fonte

Respostas:

7

Aqui está uma ligação melhor à complexidade da amostra. (Embora a complexidade computacional ainda seja .)nk

Teorema. Suponha que exista um subcubo de tamanho tal que . Com amostras , podemos, com alta probabilidade, identificar um subcubo do tamanho modo que .2 n - k | E x S [ f ( x ) ] | 0,12 S ( 2 kk log n ) S ' 2 n - k | E x S [ f ( x ) ] | 0,1S2nk|ExS[f(x)]|0.12O(2kklogn)S2nk|ExS[f(x)]|0.1

Observe a pequena perda nos parâmetros ( é ideal versus garantia de ).0,10.120.1

Prova. Escolha pontos uniformemente aleatoriamente e consulta em cada .P { 0 , 1 } n f x PmP{0,1}nfxP

Corrija um subcubo de tamanho . Temos . Por um limite de Chernoff,Também2 n - k E [ | S P | ] = m 2 - k P [ | S P | < m 2 - k - 1 ] 2 - Ω ( m 2 - k ) . P [ | E x S P [ f ( x ) ] - ES2nkE[|SP|]=m2k

P[|SP|<m2k1]2Ω(m2k).
P[|ExSP[f(x)]ExS[f(x)]|>ε]2Ω(|SP|ε2).

Por uma união vinculada a todas as opções de , temosPortanto, escolhendo , podemos garantir que, com probabilidade de pelo menos , possamos estimar dentro de para todos os subcubos de tamanho .SP[S| ExSP[f(x)]-ExS[f(x)]| ε]1- ( n(nk)2kSm=O(2k/ε2klogN)0,99ExS[f(x)]εS2n-k

P[S  |ExSP[f(x)]ExS[f(x)]|ε]1(nk)2k2Ω(m2kε2).
m=O(2k/ε2klogn)0.99ExS[f(x)]εS2nk

Definindo , provamos o teorema: escolhendo o subcubo com o maiorcom alta probabilidade, satisfará os requisitos. QED| E x S P [ f ( x ) ] |ε=0.01|ExSP[f(x)]|

Thomas apoia Monica
fonte
1
Oh, uau, que bobagem da minha parte: sim, a idéia básica é que, se você provar pontos, um esperado deles estará em cada subcubo, portanto, com um valor modesto de que dá uma grande tamanho de amostra suficiente para resolver o problema, mesmo após a união de todos os limites Chernoff. Além disso, tenho certeza de que qualquer solução pode ser adaptada para eliminar a diferença entre 0,1 e 0,12, portanto, adicionarei isso como um comentário à pergunta. Obrigado!! C C n kC2kCCnk
mobius bolinho de massa
3
Outra maneira de ver isso é que o espaço do intervalo que você descreve limita a dimensão de quebra e, portanto, a dimensão VC, e então você lança o teorema da aproximação eps nele.
precisa saber é o seguinte