Provable Quantization with Randomized Hadamard Transform

Resumen Técnico: Cuantización Demostrable con Transformada Hadamard Aleatorizada

Enunciado del Problema
La cuantización de vectores es un primitivo fundamental para comprimir vectores de valores reales en $\mathbb{R}^d$ en representaciones binarias compactas, con aplicaciones que van desde la búsqueda de similitud y el aprendizaje federado hasta transformadores eficientes y compresión de modelos. Un enfoque estándar consiste en aplicar una matriz de rotación aleatoria $R$ al vector de entrada $x$, seguido de una cuantización escalar. Si bien las rotaciones aleatorias densas ofrecen garantías teóricas sólidas (por ejemplo, las coordenadas de $Rx$ son aproximadamente gaussianas), requieren un tiempo de aplicación de $\Theta(d^2)$, lo cual es prohibitivo para vectores de alta dimensión.

Para abordar esto, la transformada Hadamard aleatorizada ($H_D$), que se aplica en un tiempo $O(d \log d)$, se utiliza a menudo como una alternativa estructurada. Sin embargo, $H_D$ no es una rotación uniformemente aleatoria; posee una estructura discreta que complica el análisis teórico. Los resultados existentes para la cuantización utilizando una única $H_D$ son o bien puramente empíricos o bien proporcionan garantías demostrables más débiles (que requieren dimensiones más altas o más bits) que las alcanzables con rotaciones verdaderamente aleatorias. El desafío consiste en lograr la velocidad de la transformada Hadamard ($O(d \log d)$) manteniendo al mismo tiempo los límites teóricos fuertes de distorsión de las rotaciones aleatorias.

Metodología
Los autores proponen una variante de la cuantización de vectores que combina una única transformada Hadamard aleatorizada con dithering (la inyección de desplazamientos aleatorios). La metodología central implica:

1. Transformación: El vector de entrada $x$ se transforma mediante $y = H_D x$, donde $H$ es una matriz Hadamard normalizada y $D$ es una matriz diagonal con entradas Rademacher ($\pm 1$) independientes.
2. Cuantización Escalar con Dithering: En lugar de cuantizar directamente las coordenadas de $y$, el método aplica un cuantizador escalar a cada coordenada después de desplazarla mediante un desplazamiento aleatorio.
   • El cuantizador escalar se basa en una versión con dithering de la cuantización de Lloyd.
   • Utiliza una función de mapeo específica $F(t)$, definida como la función de distribución acumulada (CDF) de una variable aleatoria gaussiana con media 0 y varianza 3 (derivada de la densidad $\phi(t)^{1/3}$).
   • Se aplica un parámetro de desplazamiento aleatorio $U \sim \text{Unif}[0, 1)$ a la rejilla de cuantización en el espacio de cuantiles.
3. Insesgadez: El artículo presenta dos algoritmos. El Algoritmo 1 proporciona el límite del error cuadrático medio (MSE) pero es ligeramente sesgado. El Algoritmo 5 modifica la regla de reconstrucción (utilizando una función específica $G$ en lugar de $F^{-1}$) para asegurar que el estimador sea insesgado ($E[\hat{x}] = x$) mientras se preservan los límites asintóticos del MSE.
4. Cuantización de Producto Interno: Para apoyar la estimación de productos internos, los autores proponen un cuantizador de dos etapas (Algoritmo 4). Después de la cuantización base, se cuantiza el vector residual $r = x - \hat{x}$. Esto implica:
   • Cuantizar la escala del residual.
   • Aplicar una nueva transformada Hadamard aleatorizada al residual.
   • Cuantizar las coordenadas del residual transformado utilizando un esquema basado en niveles y bits de signo aleatorios para descorrelacionar el error del vector de consulta.

Contribuciones y Resultados Clave

• Optimalidad Asintótica: La contribución teórica principal es demostrar que la cuantización con dithering utilizando una única transformada Hadamard aleatorizada alcanza límites de error cuadrático medio que coinciden asintóticamente con los de las matrices de rotación verdaderamente aleatorias.
  • Teorema 1.1: Para cualquier vector unitario $x$, el estimador insesgado $\hat{x}$ satisface:
    $$E[\|\hat{x} - x\|_2^2] \le \left(\frac{\pi\sqrt{3}}{2} + o(1)\right) \cdot 4^{-b}$$
    donde $b$ es el ancho de bits por coordenada. El término $o(1)$ se desvanece uniformemente a medida que $b \to \infty$ sobre todas las dimensiones $d$ y vectores unitarios $x$. Esta constante coincide con el límite alcanzado por TurboQuant (que asume rotaciones completamente aleatorias).
• Insesgadez: El cuantizador propuesto es insesgado, una propiedad crítica para aplicaciones como el aprendizaje federado donde la acumulación de sesgo puede degradar la convergencia del modelo.
• Garantías de Producto Interno: El artículo proporciona un límite para el error en la estimación de productos internos (Teorema 1.2). Muestra que el error cuadrático escala como $O(1/(d \cdot 4^b))$, utilizando una propiedad mixta del momento cuarto de las variables Rademacher para manejar la correlación entre el residual y el vector de consulta.
• Complejidad de Bits: El cuantizador de producto interno de dos etapas puede almacenarse utilizando $db + (3 + \frac{1}{2\ln 2})d + O(\log(b + \log d))$ bits, manteniendo una complejidad de almacenamiento lineal en $d$.

Significado y Afirmaciones
El artículo afirma que su enfoque resuelve la compensación entre la eficiencia computacional y las garantías teóricas en la cuantización de vectores. Mediante la introducción de dithering, los autores superan las dificultades analíticas planteadas por la estructura discreta de la transformada Hadamard.

• Justificación Teórica: El trabajo justifica el uso de una única matriz Hadamard aleatorizada en métodos como TurboQuant y EDEN, los cuales anteriormente dependían de rotaciones completamente aleatorias para sus garantías teóricas.
• Simplicidad vs. Complejidad: A diferencia de enfoques anteriores que requieren componer múltiples transformadas Hadamard (por ejemplo, $H_{D_1}H_{D_2}$) para aproximar rotaciones aleatorias, este método logra garantías comparables con una única transformada y dithering simple, manteniendo baja la complejidad de implementación.
• Limitaciones: Los autores declaran explícitamente que el trabajo es principalmente teórico. Caracteriza el error cuadrático medio y el error de producto interno en el peor de los casos, pero no optimiza constantes de bits finitos ni proporciona evaluaciones empíricas en sistemas posteriores. El análisis es específico para cuantizadores ajenos a los datos basados en una única transformada Hadamard aleatorizada y dithering aleatorizado.