Provable Quantization with Randomized Hadamard Transform

Riepilogo Tecnico: Quantizzazione Provabile con Trasformata di Hadamard Randomizzata

Enunciato del Problema
La quantizzazione vettoriale è un primitivo fondamentale per comprimere vettori a valori reali in $\mathbb{R}^d$ in rappresentazioni binarie compatte, con applicazioni che spaziano dalla ricerca di similarità e dall'apprendimento federato ai transformer efficienti e alla compressione dei modelli. Un approccio standard prevede l'applicazione di una matrice di rotazione casuale $R$ al vettore di input $x$, seguita da una quantizzazione scalare. Sebbene le rotazioni casuali dense offrano garanzie teoriche solide (ad esempio, le coordinate di $Rx$ sono approssimativamente gaussiane), richiedono un tempo $\Theta(d^2)$ per essere applicate, il che è proibitivo per vettori ad alta dimensionalità.

Per ovviare a ciò, la trasformata di Hadamard randomizzata ($H_D$), che si applica in tempo $O(d \log d)$, è spesso utilizzata come alternativa strutturata. Tuttavia, $H_D$ non è una rotazione uniformemente casuale; possiede una struttura discreta che complica l'analisi teorica. I risultati esistenti per la quantizzazione mediante una singola $H_D$ sono o puramente empirici o forniscono garanzie provabili più deboli (richiedendo dimensioni superiori o più bit) rispetto a quelle ottenibili con rotazioni realmente casuali. La sfida consiste nel raggiungere la velocità della trasformata di Hadamard ($O(d \log d)$) mantenendo al contempo i forti limiti teorici sulla distorsione delle rotazioni casuali.

Metodologia
Gli autori propongono una variante della quantizzazione vettoriale che combina una singola trasformata di Hadamard randomizzata con il dithering (l'iniezione di offset casuali). La metodologia di base comprende:

1. Trasformazione: Il vettore di input $x$ viene trasformato tramite $y = H_D x$, dove $H$ è una matrice di Hadamard normalizzata e $D$ è una matrice diagonale con voci indipendenti di Rademacher ($\pm 1$).
2. Quantizzazione Scalare con Dithering: Invece di quantizzare direttamente le coordinate di $y$, il metodo applica un quantizzatore scalare a ciascuna coordinata dopo averla spostata di un offset casuale.
   • Il quantizzatore scalare si basa su una versione con dithering della quantizzazione di Lloyd.
   • Utilizza una specifica funzione di mappatura $F(t)$, definita come la funzione di distribuzione cumulativa (CDF) di una variabile casuale gaussiana con media 0 e varianza 3 (derivata dalla densità $\phi(t)^{1/3}$).
   • Un parametro di spostamento casuale $U \sim \text{Unif}[0, 1)$ viene applicato alla griglia di quantizzazione nello spazio delle quantili.
3. Imparzialità: Il documento presenta due algoritmi. L'Algoritmo 1 fornisce il limite sull'errore quadratico medio (MSE) ma è leggermente distorto. L'Algoritmo 5 modifica la regola di ricostruzione (utilizzando una specifica funzione $G$ invece di $F^{-1}$) per garantire che lo stimatore sia imparziale ($E[\hat{x}] = x$), preservando al contempo i limiti MSE asintotici.
4. Quantizzazione del Prodotto Scalare: Per supportare la stima del prodotto scalare, gli autori propongono un quantizzatore a due stadi (Algoritmo 4). Dopo la quantizzazione di base, il vettore residuo $r = x - \hat{x}$ viene quantizzato. Ciò comporta:
   • La quantizzazione della scala del residuo.
   • L'applicazione di una nuova trasformata di Hadamard randomizzata al residuo.
   • La quantizzazione delle coordinate del residuo trasformato utilizzando uno schema basato sui livelli e bit di segno casuali per decorrelare l'errore dal vettore di query.

Contributi e Risultati Chiave

• Ottimalità Asintotica: Il contributo teorico principale è la dimostrazione che la quantizzazione con dithering mediante una singola trasformata di Hadamard randomizzata raggiunge limiti sull'errore quadratico medio che asintoticamente corrispondono a quelli delle matrici di rotazione realmente casuali.
  • Teorema 1.1: Per ogni vettore unitario $x$, lo stimatore imparziale $\hat{x}$ soddisfa:
    $$E[\|\hat{x} - x\|_2^2] \le \left(\frac{\pi\sqrt{3}}{2} + o(1)\right) \cdot 4^{-b}$$
    dove $b$ è la larghezza in bit per coordinata. Il termine $o(1)$ si annulla uniformemente al tendere di $b \to \infty$ su tutte le dimensioni $d$ e tutti i vettori unitari $x$. Questa costante corrisponde al limite raggiunto da TurboQuant (che assume rotazioni completamente casuali).
• Imparzialità: Il quantizzatore proposto è imparziale, una proprietà critica per applicazioni come l'apprendimento federato, dove l'accumulo di distorsione può degradare la convergenza del modello.
• Garanzie sul Prodotto Scalare: Il documento fornisce un limite per l'errore nella stima dei prodotti scalari (Teorema 1.2). Dimostra che l'errore quadratico scala come $O(1/(d \cdot 4^b))$, sfruttando una proprietà mista del momento di quarto ordine delle variabili di Rademacher per gestire la correlazione tra il residuo e il vettore di query.
• Complessità in Bit: Il quantizzatore del prodotto scalare a due stadi può essere memorizzato utilizzando $db + (3 + \frac{1}{2\ln 2})d + O(\log(b + \log d))$ bit, mantenendo una complessità di archiviazione lineare in $d$.

Significato e Affermazioni
Il documento afferma che il suo approccio risolve il compromesso tra efficienza computazionale e garanzie teoriche nella quantizzazione vettoriale. Introducendo il dithering, gli autori superano le difficoltà analitiche poste dalla struttura discreta della trasformata di Hadamard.

• Giustificazione Teorica: Il lavoro giustifica l'uso di una singola matrice di Hadamard randomizzata in metodi come TurboQuant e EDEN, che in precedenza si affidavano a rotazioni completamente casuali per le loro garanzie teoriche.
• Semplicità vs. Complessità: A differenza di approcci precedenti che richiedono la composizione di multiple trasformate di Hadamard (ad esempio $H_{D_1}H_{D_2}$) per approssimare rotazioni casuali, questo metodo raggiunge garanzie comparabili con una singola trasformata e un semplice dithering, mantenendo bassa la complessità di implementazione.
• Limitazioni: Gli autori dichiarano esplicitamente che il lavoro è principalmente teorico. Caratterizza l'errore quadratico medio e l'errore del prodotto scalare nel caso peggiore, ma non ottimizza le costanti per bit finiti né fornisce valutazioni empiriche su sistemi downstream. L'analisi è specifica per quantizzatori ignari dei dati basati su una singola trasformata di Hadamard randomizzata e dithering randomizzato.