Fundamental Bias in Inverting Random Sampling Matrices with Application to Sub-sampled Newton

Resumo Técnico: Viés Fundamental na Inversão de Matrizes de Amostragem Aleatória com Aplicação em Newton Sub-amostrado

1. O Problema

O artigo aborda um problema fundamental na Álgebra Linear Numérica Randomizada (RandNLA) e no Aprendizado de Máquina (ML): o viés de inversão (inversion bias).

• Contexto: Em muitas aplicações de ML de grande escala (como regressão, otimização estocástica e métodos de Newton), utiliza-se sketching (esboço) aleatório para reduzir a dimensionalidade de uma matriz $A \in \mathbb{R}^{n \times d}$ (onde $n \gg d$) para uma matriz menor $\tilde{A} \in \mathbb{R}^{m \times d}$.
• O Desafio: Embora a matriz esboçada $\tilde{A}^\top \tilde{A}$ seja frequentemente um estimador não tendencioso (ou quase não tendencioso) de $A^\top A$, a sua inversa $(\tilde{A}^\top \tilde{A} + C)^{-1}$ não é um estimador não tendencioso de $(A^\top A + C)^{-1}$. Isso ocorre porque a inversão de matrizes é um operador não linear.
• Impacto: Esse viés prejudica a precisão e a taxa de convergência de pipelines de ML que dependem da inversão da matriz de covariância esboçada, como o método de Newton Sub-amostrado (SSN).
• Limitação do Estado da Arte: Trabalhos anteriores mostraram como corrigir esse viés para projeções Gaussianas densas (que são computacionalmente caras) e projeções esparsas sub-Gaussianas (LESS). No entanto, não havia uma caracterização precisa ou correção eficaz para métodos de amostragem aleatória (uniforme e baseada em leverage scores) e projeções estruturadas como a Transformada de Hadamard Aleatória Sub-amostrada (SRHT).

2. Metodologia e Abordagem

Os autores utilizam uma combinação avançada de Teoria de Matrizes Aleatórias (RMT) não assintótica e técnicas de RandNLA para analisar e corrigir o viés.

• Análise de "Leave-One-Out": A metodologia central envolve uma análise refinada do comportamento espectral da matriz inversa esboçada. Em vez de tratar a amostragem como uma projeção genérica, os autores analisam a estrutura específica das matrizes de amostragem.
• Equação Auto-Consistente: Eles derivam uma equação auto-consistente para o valor esperado da matriz inversa. Diferente das projeções Gaussianas, onde o viés é corrigido por um fator escalar simples, a amostragem aleatória exige uma correção mais complexa que depende das pontuações de leverage (alavancagem) das linhas da matriz original.
• Técnicas de De-biasing (Correção de Viés):
  1. Correção Matricial (Fina): Propõem uma matriz de re-ponderação $\check{S}$ que ajusta cada linha amostrada individualmente com base no seu leverage score exato ($\ell_i^C$). A fórmula proposta é:
     $$\check{S} = \text{diag}\left\{ \sqrt{\frac{m}{m - \ell_{is}^C / \pi_{is}}} \right\}_{s=1}^m \cdot S$$
     Isso transforma a matriz de amostragem padrão $S$ em uma matriz corrigida $\check{S}$ que elimina o viés de inversão.
  2. Correção Escalar (Aproximada): Mostram que, para esquemas de amostragem que são aproximações próximas dos leverage scores exatos (como amostragem de leverage aproximada ou SRHT), a correção matricial complexa pode ser aproximada por um simples fator escalar de re-escalação: $\frac{m}{m - d_{eff}}$, onde $d_{eff}$ é a dimensão efetiva.

3. Principais Contribuições

1. Caracterização Precisa do Viés de Inversão:

   • O artigo fornece a primeira caracterização teórica precisa do viés de inversão para amostragem aleatória geral (uniforme e baseada em leverage) e para projeções estruturadas (SRHT).
   • Demonstra que o viés na amostragem aleatória é fundamentalmente diferente e mais complexo do que em projeções Gaussianas ou LESS, exigindo uma correção que depende dos leverage scores.

2. Métodos de Correção (De-biasing):

   • Propõe um método de correção matricial exato (Teorema 3.2) que torna o estimador da inversa não tendencioso.
   • Estabelece que, para amostragem baseada em leverage scores aproximados e SRHT, a correção pode ser realizada eficientemente apenas com um fator escalar, mantendo a eficiência computacional.

3. Convergência Independente do Problema para SSN:

   • Aplicando essas correções ao método de Newton Sub-amostrado (SSN), os autores estabelecem as primeiras taxas de convergência local independentes do problema para SSN.
   • O método corrigido atinge taxas de convergência comparáveis ao Newton Sketch com projeções Gaussianas densas, mas com custos computacionais muito menores (devido à esparsidade da amostragem).

4. Resultados e Evidências Numéricas

• Teoria: Os teoremas provam que, com o número adequado de amostras ($m$), a matriz inversa corrigida $(A^\top \check{S}^\top \check{S} A + C)^{-1}$ é um estimador não tendencioso $(\epsilon, \delta)$ de $(A^\top A + C)^{-1}$.
• Experimentos:
  • Os autores testaram o método em problemas de regressão logística utilizando os conjuntos de dados MNIST e CIFAR-10.
  • Comparação: O SSN corrigido com amostragem de leverage aproximada (SSN-ARLev) superou consistentemente o método Newton-LESS (baseado em projeção esparsa) em termos de trade-off entre tempo de execução e erro relativo.
  • Eficiência: Enquanto o tempo de execução do Newton-LESS aumentava significativamente com o tamanho do esboço ($m$), o tempo do SSN corrigido permaneceu aproximadamente constante, demonstrando uma vantagem computacional superior.
  • Viés: Gráficos experimentais confirmaram que a correção escalar reduz drasticamente o viés de inversão em comparação com a amostragem não corrigida.

5. Significado e Impacto

• Ponte entre Teoria e Prática: O trabalho preenche uma lacuna crítica entre a teoria de matrizes aleatórias e a prática de otimização de segunda ordem em grande escala. Ele mostra que métodos de amostragem simples e baratos (como leverage score sampling) podem ser tão eficazes quanto projeções Gaussianas densas, desde que o viés de inversão seja corretamente tratado.
• Otimização Escalável: Ao permitir que o SSN atinja taxas de convergência locais superiores sem o custo computacional proibitivo de matrizes densas, o método proposto torna a otimização de segunda ordem viável para conjuntos de dados massivos que não cabem na memória de uma única máquina.
• Generalidade: A abordagem não se limita a um tipo específico de amostragem, oferecendo um framework unificado para corrigir viés em amostragem uniforme, baseada em leverage e transformadas de Hadamard, ampliando o arsenal de ferramentas para RandNLA.

Em resumo, o artigo demonstra que o "viés de inversão" não é um impedimento intransponível para métodos de amostragem aleatória, mas sim um efeito corrigível que, quando tratado, permite algoritmos de otimização de segunda ordem mais rápidos, precisos e escaláveis.