Provable Quantization with Randomized Hadamard Transform

Resumo Técnico: Quantização Provável com Transformada de Hadamard Aleatorizada

Enunciado do Problema
A quantização vetorial é um primitivo fundamental para comprimir vetores de valor real em $\mathbb{R}^d$ em representações binárias compactas, com aplicações que vão desde busca por similaridade e aprendizado federado até transformers eficientes e compressão de modelos. Uma abordagem padrão envolve aplicar uma matriz de rotação aleatória $R$ ao vetor de entrada $x$, seguida de quantização escalar. Embora rotações aleatórias densas forneçam garantias teóricas limpas (por exemplo, as coordenadas de $Rx$ são aproximadamente Gaussianas), elas exigem tempo $\Theta(d^2)$ para aplicação, o que é proibitivo para vetores de alta dimensão.

Para abordar isso, a transformada de Hadamard aleatorizada ($H_D$), que aplica em tempo $O(d \log d)$, é frequentemente usada como uma alternativa estruturada. No entanto, $H_D$ não é uma rotação uniformemente aleatória; ela possui uma estrutura discreta que complica a análise teórica. Resultados existentes para quantização usando uma única $H_D$ são ou puramente empíricos ou fornecem garantias prováveis que são mais fracas (exigindo dimensões mais altas ou mais bits) do que aquelas alcançáveis com rotações verdadeiramente aleatórias. O desafio é alcançar a velocidade da transformada de Hadamard ($O(d \log d)$) mantendo os limites teóricos fortes de distorção das rotações aleatórias.

Metodologia
Os autores propõem uma variante da quantização vetorial que combina uma única transformada de Hadamard aleatorizada com dithering (a injeção de deslocamentos aleatórios). A metodologia central envolve:

1. Transformação: O vetor de entrada $x$ é transformado via $y = H_D x$, onde $H$ é uma matriz de Hadamard normalizada e $D$ é uma matriz diagonal com entradas independentes de Rademacher ($\pm 1$).
2. Quantização Escalar com Dithering: Em vez de quantizar diretamente as coordenadas de $y$, o método aplica um quantizador escalar a cada coordenada após deslocá-la por um deslocamento aleatório.
   • O quantizador escalar é baseado em uma versão com dithering da quantização de Lloyd.
   • Ele utiliza uma função de mapeamento específica $F(t)$, definida como a função de distribuição acumulada (CDF) de uma variável aleatória Gaussiana com média 0 e variância 3 (derivada da densidade $\phi(t)^{1/3}$).
   • Um parâmetro de deslocamento aleatório $U \sim \text{Unif}[0, 1)$ é aplicado à grade de quantização no espaço de quantis.
3. Inviés: O artigo apresenta dois algoritmos. O Algoritmo 1 fornece o limite do erro quadrático médio (MSE), mas é ligeiramente enviesado. O Algoritmo 5 modifica a regra de reconstrução (usando uma função específica $G$ em vez de $F^{-1}$) para garantir que o estimador seja inviés ($E[\hat{x}] = x$), preservando os limites assintóticos de MSE.
4. Quantização de Produto Interno: Para suportar a estimação de produto interno, os autores propõem um quantizador de dois estágios (Algoritmo 4). Após a quantização base, o vetor residual $r = x - \hat{x}$ é quantizado. Isso envolve:
   • Quantizar a escala do residual.
   • Aplicar uma nova transformada de Hadamard aleatorizada ao residual.
   • Quantizar as coordenadas do residual transformado usando um esquema baseado em níveis e bits de sinal aleatórios para descorrelacionar o erro do vetor de consulta.

Principais Contribuições e Resultados

• Optimalidade Assintótica: A principal contribuição teórica é provar que a quantização com dithering usando uma única transformada de Hadamard aleatorizada alcança limites de erro quadrático médio que assintoticamente correspondem aos das matrizes de rotação verdadeiramente aleatórias.
  • Teorema 1.1: Para qualquer vetor unitário $x$, o estimador inviés $\hat{x}$ satisfaz:
    $$E[\|\hat{x} - x\|_2^2] \le \left(\frac{\pi\sqrt{3}}{2} + o(1)\right) \cdot 4^{-b}$$
    onde $b$ é a largura de bits por coordenada. O termo $o(1)$ desaparece uniformemente à medida que $b \to \infty$ sobre todas as dimensões $d$ e vetores unitários $x$. Esta constante corresponde ao limite alcançado pelo TurboQuant (que assume rotações totalmente aleatórias).
• Inviés: O quantizador proposto é inviés, uma propriedade crítica para aplicações como aprendizado federado, onde o acúmulo de viés pode degradar a convergência do modelo.
• Garantias de Produto Interno: O artigo fornece um limite para o erro na estimação de produtos internos (Teorema 1.2). Ele mostra que o erro quadrático escala como $O(1/(d \cdot 4^b))$, utilizando uma propriedade de momento de quarta ordem mista das variáveis de Rademacher para lidar com a correlação entre o residual e o vetor de consulta.
• Complexidade de Bits: O quantizador de produto interno de dois estágios pode ser armazenado usando $db + (3 + \frac{1}{2\ln 2})d + O(\log(b + \log d))$ bits, mantendo complexidade de armazenamento linear em $d$.

Significado e Alegações
O artigo alega que sua abordagem resolve o compromisso entre eficiência computacional e garantias teóricas na quantização vetorial. Ao introduzir dithering, os autores superam as dificuldades analíticas impostas pela estrutura discreta da transformada de Hadamard.

• Justificativa Teórica: O trabalho justifica o uso de uma única matriz de Hadamard aleatorizada em métodos como TurboQuant e EDEN, que anteriormente dependiam de rotações totalmente aleatórias para suas garantias teóricas.
• Simplicidade vs. Complexidade: Diferentemente de abordagens anteriores que exigem a composição de múltiplas transformadas de Hadamard (por exemplo, $H_{D_1}H_{D_2}$) para aproximar rotações aleatórias, este método alcança garantias comparáveis com uma única transformada e dithering simples, mantendo a complexidade de implementação baixa.
• Limitações: Os autores afirmam explicitamente que o trabalho é primariamente teórico. Ele caracteriza o erro quadrático médio e o erro de produto interno no pior caso, mas não otimiza constantes de bits finitos ou fornece avaliações empíricas em sistemas downstream. A análise é específica para quantizadores cegos aos dados baseados em uma única transformada de Hadamard aleatorizada e dithering aleatório.