Resumo Técnico: Vizinhos Mais Próximos de Dois Lados para Completude de Matrizes

Declaração do Problema

O artigo aborda o problema da completude de matrizes no contexto de modelos de fatores latentes, focando especificamente em configurações onde a matriz de verdade subjacente $\Theta$ é gerada por uma função latente não linear $f$ que atua sobre fatores latentes de linhas e colunas desconhecidos. O modelo é definido como:
$$\theta_{i,j} = f(u_i, v_j)$$
onde $u_i \in \mathbb{R}^{d_1}$ e $v_j \in \mathbb{R}^{d_2}$ são fatores latentes, e $f$ pertence a uma classe de funções Hölder com parâmetro de suavidade $\lambda \in (0, 1]$. Esta configuração generaliza os modelos bilineares padrão (onde $f(u,v) = \langle u, v \rangle$) para funções não paramétricas, potencialmente não suaves (menos suaves que Lipschitz).

Um desafio crítico abordado é o regime MNAR (Missing Not At Random - Ausente Não Ao Acaso). Diferente do regime MCAR (Missing Completely At Random - Ausente Completamente Ao Acaso), onde a ausência é independente dos dados, o MNAR assume que a probabilidade de uma entrada ser observada depende dos fatores latentes não observados. Além disso, os autores consideram cenários onde as entradas podem estar deterministicamente ausentes (ou seja, ausentes com probabilidade 0 para configurações específicas), uma ocorrência comum em sistemas do mundo real, como mecanismos de recomendação, onde as preferências do usuário ditam a visibilidade.

O objetivo é estimar a verdade fundamental $\theta_{i,j}$ tanto para entradas observadas quanto para as ausentes, sem conhecimento prévio dos fatores latentes $U$ e $V$ ou da função $f$, alcançando taxas minimax ótimas.

Metodologia: Vizinhos Mais Próximos de Dois Lados (TS-NN)

Os autores propõem o algoritmo Two-Sided Nearest Neighbor (TS-NN). A intuição central é aproximar as distâncias latentes entre linhas e colunas usando dados observados, e então realizar a média dos resultados sobre os vizinhanças resultantes.

1. Estimativa de Distância: Como a função latente $f$ é desconhecida, o algoritmo constrói proxies baseados em dados para as distâncias quadráticas $L_2$ entre os fatores de linha e de coluna ($d^2_{row}$ e $d^2_{col}$).

   • O algoritmo estima a distância entre a linha $i$ e $i'$ através da média das diferenças quadráticas de suas entradas observadas através de colunas comuns, corrigida pela variância do ruído ($2\sigma^2$).
   • Da mesma forma, as distâncias de coluna são estimadas usando linhas comuns.
   • Formalmente, a distância de linha estimada é:
     $$\hat{d}^2_{row}(i, i') = \frac{\sum_{j} (X_{i,j} - X_{i',j})^2 A_{i,j}A_{i',j}}{\sum_{j} A_{i,j}A_{i',j}} - 2\sigma^2$$
     (Uma fórmula simétrica se aplica para as colunas).

2. Construção de Vizinhança: Usando parâmetros de ajuste $\eta_{row}$ e $\eta_{col}$, o algoritmo define vizinhanças:

   • $N_{row}(i) = \{i' : \hat{d}^2_{row}(i, i') \leq \eta^2_{row}\}$
   • $N_{col}(j) = \{j' : \hat{d}^2_{col}(j, j') \leq \eta^2_{col}\}$

3. Estimativa: A estimativa $\hat{\theta}_{i,j}$ é a média de todas as entradas observadas $X_{i',j'}$ onde $i' \in N_{row}(i)$ e $j' \in N_{col}(j)$.

Contribuições Principais e Resultados Teóricos

1. Adaptabilidade à Suavidade e Otimalidade Minimax

O principal achado teórico é que o TS-NN se adapta à suavidade $\lambda$ da função latente $f$.

• Regime MCAR: Sob as suposições padrão de MCAR, os autores provam que, com o ajuste apropriado ($\eta \propto (mn)^{-\frac{\lambda}{2\lambda + d_1 + d_2}}$), o Erro Quadrático Médio (MSE) atinge a taxa minimax não paramétrica ótima:
  $$\text{MSE} = O\left( (mn)^{-\frac{2\lambda}{2\lambda + d_1 + d_2}} \right)$$
  Esta taxa iguala-se à de um algoritmo "oráculo" que tem acesso aos verdadeiros fatores latentes $U$ e $V$.
• Regime MNAR: O artigo estabelece que esta otimalidade se mantém mesmo sob condições MNAR, desde que uma condição de regularidade (Suposição 6) seja atendida. Esta condição exige essencialmente que o número de entradas observadas na interseção das vizinhanças de linha e coluna seja suficientemente grande em relação ao produto dos tamanhos das vizinhanças, mesmo que algumas entradas estejam deterministicamente ausentes.

2. Robustez à Ausência Determinística

Uma contribuição significativa é a demonstração de que o TS-NN produz taxas de erro não triviais mesmo quando uma parte significativa da matriz está deterministicamente ausente (ex: 50% das entradas ausentes para pares específicos de usuário-item). Os limites teóricos mostram que, desde que a probabilidade de ausência "efetiva" dentro das vizinhanças permaneça limitada longe de zero, a taxa minimax é preservada.

3. Garantias Pontuais e Normalidade Assintótica

• Limites Pontuais: O artigo fornece limites de erro pontuais não assintóticos para entradas individuais $\hat{\theta}_{i,j}$. Estes limites exibem uma "maldição da dimensionalidade" em relação aos parâmetros de ajuste e dimensões da matriz, que desaparece quando calculada a média para o nível populacional (MSE).
• Normalidade Assintótica: Sob condições específicas sobre o tamanho da vizinhança, os autores provam que o estimador pontual é assintoticamente normal:
  $$\sqrt{|N_{row,col}(i,j)|} (\hat{\theta}_{i,j} - \theta_{i,j}) \xrightarrow{d} \mathcal{N}(0, \sigma^2)$$
  Este resultado permite a construção de intervalos de confiança válidos para estimativas contrafatuais.

Resultados Empíricos

Os autores validam seus achados teóricos através de:

1. Simulações Sintéticas:

   • Experimentos comparam o TS-NN contra baselines incluindo Row-NN, Column-NN, Doubly-Robust NN (DR-NN), Universal Singular Value Thresholding (USVT) e SoftImpute.
   • Resultados: O TS-NN consistentemente alcança as melhores taxas de decaimento de MSE, igualando-se ao Oracle-TS-NN (que conhece os fatores latentes) em configurações MCAR. Crucialmente, o TS-NN mantém um desempenho robusto em configurações MNAR onde outros métodos (como o DR-NN) degradam significativamente.
   • Adaptabilidade de Suavidade: As taxas de decaimento empíricas do TS-NN alinham-se com as previsões teóricas conforme o parâmetro de suavidade $\lambda$ varia.
   • Intervalos de Confiança: Os intervalos de confiança construídos atingem uma cobertura próxima da nominal (95%) para amostras moderadas, validando o resultado de normalidade assintótica.

2. Estudo de Caso Real (HeartSteps):

   • O método é aplicado ao conjunto de dados de saúde móvel HeartSteps, um ensaio micro-randomizado envolvendo 37 usuários e pontos de decisão ao longo de 6 semanas.
   • O conjunto de dados exibe características MNAR (usuários estão indisponíveis ~20% do tempo, e as notificações só são enviadas se estiverem disponíveis).
   • Resultos: Em um cenário de validação cruzada de 5 dobras, o TS-NN supera variantes de NN de um lado (Row-NN, Col-NN) e o baseline "All-Row-NN" na estimativa de contagens de passos contrafatuais, demonstrando a utilidade prática da abordagem de dois lados para lidar com a ausência determinística.

Significância e Alegações

O artigo afirma unir dois domínios de pesquisa distintos: completude de matrizes não paramétrica e análise de dados ausentes MNAR.

• Primeira Análise do Gênero: Os autores afirmam que esta é a primeira análise teórica de um método que lida simultaneamente com fatores latentes de linha e coluna desconhecidos, uma função Hölder-contínua não linear (com $\lambda < 1$) e ausência MNAR.
• Equivalência de Oráculo: O trabalho demonstra que a falta de conhecimento sobre os fatores latentes não penaliza a taxa de convergência; o TS-NN performa tão bem quanto um oráculo com conhecimento total de $U$ e $V$ no regime intermediário.
• Robustez: A metodologia mostra-se robusta a padrões de ausência determinística, uma característica frequentemente ignorada na literatura padrão de completude de matrizes, mas crítica para aplicações do mundo real como sistemas de recomendação.

Os autores concluem que o TS-NN fornece uma solução teoricamente fundamentada, adaptável e robusta para a completude de matrizes em ambientes complexos, não suaves e com ausência não aleatória.