Embedding Dimension Lower Bounds for Universality of Deep Sets and Janossy Pooling

Resumo Técnico: Limites Inferiores da Dimensão de Embedding para a Universalidade de Deep Sets e Janossy Pooling

Enunciado do Problema
O artigo aborda a questão teórica da universalidade em arquiteturas de redes neurais invariantes a permutações, especificamente Deep Sets e sua generalização, Janossy pooling. Embora esteja estabelecido que essas arquiteturas podem aproximar qualquer função contínua invariante a permutações, um problema aberto crítico permanece: determinar a dimensão de embedding mínima $M$ (a dimensão latente) necessária para garantir essa universalidade.

Trabalhos anteriores forneceram limites superiores (por exemplo, $M \le 2nd + 1$ para Deep Sets com $d>1$) e limites inferiores triviais (por exemplo, $M \ge n$ para $d=1$). No entanto, para Deep Sets com $d > 1$ e para Janossy pooling $k$-ário com $k > 1$, não existiam limites inferiores não triviais que escalassem com a dimensão ambiente $d$. O artigo foca no caso de saída escalar ($p=1$) sobre o domínio $K = [0, 1]^d$, definindo $M_{univ}(d, n, k)$ como a dimensão de embedding mínima necessária para a universalidade.

Metodologia
Os autores introduzem uma técnica novel baseada no teorema de Borsuk-Ulam para estabelecer limites inferiores na dimensão de embedding. A metodologia procede através de várias etapas-chave:

1. Redução para Janossy Pooling Indexado: Os autores demonstram primeiro que, se a arquitetura padrão de Janossy $k$-ária for universal, isso implica a universalidade de uma classe maior e não invariante chamada "Janossy pooling indexado". Nesta variante indexada, as funções codificadoras $\phi_{i_1, \dots, i_k}$ são permitidas a depender dos índices específicos da tupla de entrada, em vez de serem compartilhadas entre todas as permutações. Essa redução permite aos autores provar limites inferiores para a classe indexada, que se aplicam automaticamente à classe simétrica original.
2. Rigidez de Diferenças Finitas: É estabelecido um lema crucial mostrando que os mapas latentes de Janossy indexados satisfazem uma específica "rigidez de diferenças finitas". Se o mapa concordar em um subconjunto de "eixo" de uma grade (onde pelo menos uma coordenada é zero), ele deve concordar em toda a grade. Essa propriedade vincula o comportamento do codificador em um conjunto esparsos de entradas ao seu comportamento em uma grade densa.
3. Construção de Borsuk-Ulam: Para provar o limite inferior, os autores constroem dois conjuntos compactos disjuntos, $E_+$ e $E_-$, dentro do espaço de entrada. Eles utilizam o teorema de Borsuk-Ulam para mostrar que, se a dimensão de embedding $M$ for muito pequena (especificamente, se $M$ for menor que um limiar derivado), qualquer codificador contínuo $\Phi$ mapeando para $\mathbb{R}^M$ deve mapear um par de pontos antipodais (um de $E_+$ e um de $E_-$) para o mesmo vetor latente.
4. Argumento de Colisão: Ao construir uma função alvo contínua $g$ que assume valores distintos (0 e 1) em $E_-$ e $E_+$, respectivamente, os autores mostram que, se o codificador mapear pontos desses conjuntos para o mesmo vetor latente, nenhum decodificador $\rho$ pode aproximar $g$ com um erro menor que $1/2$. Essa contradição prova que a dimensão assumida $M$ é insuficiente para a universalidade.

Principais Contribuições e Resultados

• Novo Limite Inferior para Deep Sets ($k=1$): O artigo prova que, para Deep Sets atuando em conjuntos de $n$ pontos em $\mathbb{R}^d$, a dimensão de embedding mínima satisfaz:
  $$M_{univ}(d, n, 1) \ge d(n - 1)$$
  Este é o primeiro limite inferior para $d > 1$ que cresce com a dimensão ambiente $d$. Quando combinado com o limite superior existente de $2nd + 1$ (de Dym–Gortler), isso estabelece que a dimensão necessária escala como $\Theta(nd)$, até fatores constantes. Para $d=1$, o limite produz $n-1$, recuperando a dependência linear conhecida em $n$ até uma constante aditiva.

• Primeiro Limite Inferior Não Trivial para Janossy Pooling $k$-ário ($k > 1$): Para Janossy pooling $k$-ário geral, os autores derivam o primeiro limite inferior não trivial que depende de $d$. O resultado é:
  $$M_{univ}(d, n, k) \gtrsim_k (d(n - k))^{1/k}$$
  Este resultado demonstra que, mesmo com interações de ordem finita ($k > 1$), a dimensão latente necessária deve crescer tanto com a dimensão ambiente $d$ quanto com o tamanho do conjunto $n$.

• Estrutura Técnica: O artigo fornece uma estrutura rigorosa para analisar a universalidade, reduzindo arquiteturas simétricas para as indexadas e aplicando obstruções topológicas (Borsuk-Ulam) aos mapeamentos do espaço latente.

Significância e Limitações
O artigo afirma que esses resultados resolvem um problema aberto significativo destacado na literatura anterior sobre os requisitos de dimensionalidade para redes invariantes a permutações. Especificamente, confirma que, para Deep Sets, a dimensão de embedding deve escalar linearmente tanto com $n$ quanto com $d$, corrigindo lacunas anteriores onde apenas limites dependentes de $n$ eram conhecidos para $d>1$. Para pooling $k$-ário, estabelece que as interações não eliminam a necessidade de crescimento da dimensão com $d$.

Os autores observam limitações específicas em sua construção atual:

• Para Deep Sets ($k=1$), o limite é $d(n-1)$ em vez de $dn$. Essa "perda" de um ponto surge porque a estratégia de prova requer um bloco de variáveis para separar os dois conjuntos compactos disjuntos usados no argumento de Borsuk-Ulam.
• Para $k > 1$, o expoente $1/k$ no limite inferior é uma limitação da construção atual, que usa $k$ variáveis base para rotular regiões em uma esfera. Isso deixa uma lacuna substancial entre o limite inferior derivado e o limite superior herdado de $O(nd)$ de Deep Sets.

O artigo conclui que determinar a dependência exata em $d$, $n$ e $k$, e provar limites superiores e inferiores correspondentes para Janossy pooling de ordem finita, permanece um problema aberto.