Resumo Técnico: Spectral DPPs via NEPv

1. Enunciado do Problema

O artigo aborda a intratabilidade computacional da inferência de Máximas A Posteriori (MAP) de Processos de Ponto Determinantal (DPP) para seleção de dados em larga escala.

• Contexto: Selecionar um subconjunto diverso e de alta qualidade de tamanho $k$ de um conjunto fundamental massivo de $n$ candidatos (onde $n$ varia de milhões a bilhões) é crítico para curadoria de dados, seleção de coreset e aprendizado ativo.
• Objetivo: Maximizar $\log \det(L_S)$, onde $L_S$ é a submatriz principal de um kernel de similaridade semidefinido positivo $L$ indexado pelo subconjunto $S$.
• Desafio: Este problema de otimização é NP-difícil. Solvers discretos padrão (greedy, lazy-greedy) escalam superlinearmente ($O(kn^2)$ a $O(kn^3)$), tornando-os inviáveis para o regime "centrado em dados" onde a diversidade é mais necessária. Relaxações contínuas existentes (por exemplo, extensões softmax baseadas em simplex) frequentemente falham em impor restrições de diversidade de forma eficaz ou não escalam bem com kernels de baixo posto comuns em aprendizado de máquina.

2. Metodologia

Os autores propõem o NEPV-DPP, um framework que recastea o problema discreto de DPP-MAP como um problema de otimização contínua na variedade de Stiefel, levando a um novo Problema de Autovalor Não Linear com dependência de autovetor (NEPV).

2.1 Relaxação na Variedade de Stiefel

Em vez de relaxar o vetor de participação binário $x \in \{0,1\}^n$ para pesos fracionários em um simplex (como no trabalho anterior), o artigo relaxa a matriz de seleção de coordenadas discreta $V_S \in \{0,1\}^{n \times k}$ para um frame ortonormal arbitrário $V \in \mathbb{R}^{n \times k}$ tal que $V^\top V = I_k$.

• Objetivo: Maximizar $f(V) = \log \det(V^\top L V)$ sujeito a $V \in \text{St}(n, k)$.
• Vantagem Geométrica: A restrição de ortogonalidade ($V^\top V = I_k$) atua como uma restrição de diversidade "rígida". Ao contrário das relaxações de simplex, onde itens redundantes podem receber pesos fracionários, a relaxação de Stiefel força as direções selecionadas a serem mutuamente ortogonais, penalizando naturalmente a redundância antes mesmo da avaliação do objetivo.
• Compatibilidade de Baixo Posto: Se $L = \Phi \Phi^\top$ (um kernel de baixo posto comum em ML), o algoritmo nunca forma a matriz $n \times n$ $L$. Ele opera apenas na matriz $d \times k$ $\Phi^\top V$, permitindo um escalonamento quase linear em $n$.

2.2 A Formulação NEPV

Ao derivar as condições KKT para a relaxação de Stiefel, os autores mostram que as condições de otimalidade de primeira ordem formam uma nova classe de NEPV:
$$H(V) V = V \Lambda$$
onde o operador $H(V)$ depende de $V$ através do inverso da matriz Gram $(V^\top L V)^{-1}$:
$$H(V) = \frac{1}{2} \left( L P(V) + P(V)^\top L \right), \quad P(V) = V (V^\top L V)^{-1} V^\top L$$
Esta dependência do inverso da matriz Gram distingue-o de aplicações padrão de NEPV (por exemplo, em Teoria do Funcional de Densidade) onde o operador tipicamente depende de $VV^\top$.

2.3 Solver: Iteração SCF com Garantias

O artigo propõe uma iteração de Campo Autoconsistente (SCF) para resolver este NEPV, especificamente o Algoritmo 1 (NEPV-DPP):

1. Inicialização: Começar com os top-$k$ autovetores de $L$.
2. Iteração:
   • Calcular a matriz Gram $G_t = V_t^\top L V_t$.
   • Resolver para $A_t = L V_t G_t^{-1}$.
   • Construir o operador $H(V_t)$ implicitamente.
   • Aplicar deslocamento de nível ($\sigma$) e amortecimento ($\alpha$) para estabilizar a convergência.
   • Atualizar $V_{t+1}$ tomando os top-$k$ autovetores do operador deslocado e projetando de volta para a variedade de Stiefel via retração polar.
3. Arredondamento: Converter a solução contínua $V^\star$ de volta para um subconjunto discreto $S$ usando amostragem de leverage-score seguida de refinamento greedy local.

2.4 Teoria de Convergência

Os autores provam um teorema de contração local para a iteração SCF.

• Lema Chave: Eles estabelecem um limite de perturbação para a matriz Gram inversa $(V^\top L V)^{-1}$ na variedade de Stiefel, mostrando que pequenas mudanças no subespaço (medidas pela distância cordal $\|\sin \Theta\|_F$) resultam em mudanças limitadas na matriz Gram inversa.
• Resultado: Sob uma suposição de gap espectral ($\lambda_k(L) > \lambda_{k+1}(L)$) e com deslocamento de nível suficiente, a iteração converge linearmente (geometricamente) para um ponto crítico local. A taxa de convergência depende do eigengap e do parâmetro de deslocamento de nível.

3. Principais Contribuições

1. Novidade Matemática: O artigo identifica que a relaxação contínua de DPP-MAP na variedade de Stiefel gera um NEPV anteriormente não estudado, onde o operador depende do inverso do kernel projetado. Isso requer uma nova análise de perturbação para matrizes Gram inversas.
2. Escalabilidade Algorítmica: O algoritmo resultante NEPV-DPP requer apenas produtos matriz-vetor com o kernel (ou fatores de baixo posto), escalando como $O((ndk + nk^2)t)$ para $t$ iterações. Isso o torna viável para $n$ na casa dos milhões, ao contrário dos métodos discretos $O(kn^3)$.
3. Restrições de Diversidade Superiores: A relaxação de Stiefel impõe diversidade via ortogonalidade $L_2$, o que se mostra mais robusto contra redundância do que as relaxações baseadas em simplex.
4. Validação Empírica (Sintética): O artigo fornece benchmarks sintéticos demonstrando que o NEPV-DPP supera as extensões softmax e as relaxações de simplex D-ótimas em regimes de alta redundância (quase-duplicatas) e estruturas de baixo posto, alcançando melhor cobertura de clusters distintos e valores de log-determinante mais altos.

4. Resultados e Alegações

• Desempenho Sintético: Em experimentos com $n=1000$ a $n=450$ e estruturas de cluster variadas:
  • Regime de Redundância: O NEPV-DPP selecionou com sucesso um representante de cada um dos 5 clusters de quase-duplicatas (cobertura de 5/5), enquanto a extensão softmax selecionou duplicatas (cobertura de 3/5) e a relaxação de simplex D-ótima falhou totalmente (cobertura de 0/5).
  • Regime Uniforme: O NEPV-DPP alcançou a maior distância pairwise mínima e o maior valor de log-determinante em comparação com os baselines, evitando o comportamento de "agrupamento nos cantos" (corner-clumping) dos métodos de simplex.
• Escalabilidade: O método integra-se diretamente com kernels de baixo posto e mapas de características, evitando a formação da matriz de kernel $n \times n$ completa.
• Escopo Modesto: O artigo afirma explicitamente que benchmarks de dados reais completos, medições de qualidade downstream e comparações de tempo de execução em escala de produção foram deixados para um estudo empírico planejado. O presente trabalho foca na relaxação, no solver e na análise de escalonamento.

5. Significância

O artigo afirma remover a barreira algorítmica que impede o uso de seleção baseada em DPP principiada em curadoria de dados em larga escala. Ao transformar um problema discreto NP-difícil em um NEPV contínuo tratável com um solver provadamente convergente, ele permite a seleção de subconjuntos diversos e de alta qualidade de pools de candidatos massivos (milhões a bilhões) onde métodos anteriores eram computacionalmente proibitivos. O trabalho faz a ponte entre o apelo teórico dos DPPs e as restrições práticas dos pipelines modernos de aprendizado de máquina.