Distributed Sketching on Data Partitions for OLS Regression

Problematica
Questo articolo affronta le sfide computazionali della regressione dei Minimi Quadrati Ordinari (OLS) quando applicata a dataset massivi. Sebbene lo sketching distribuito sia un approccio consolidato per scalare l'OLS, i metodi tradizionali implicano tipicamente la creazione di piccoli sketch dell'intero dataset su ogni macchina. Gli autori identificano un limite in questo approccio standard: il processo di mappatura (sketching) dal dataset completo allo sketch ridotto rimane computazionalmente costoso, in particolare all'aumentare della dimensione del dataset. Il presente articolo propone una strategia alternativa: eseguire lo sketching su sottogruppi partizionati dei dati. In questo modello, un grande dataset viene diviso in $k$ sottogruppi, ciascuno assegnato a una macchina diversa. Ogni macchina costruisce uno sketch solo dal proprio sottogruppo locale, calcola un estimatore OLS locale e questi estimatori vengono successivamente mediati. Il problema centrale è caratterizzare esattamente l'eccesso di perdita (excess loss) di questo estimatore mediato e determinare in quali condizioni questo approccio partizionato sia statisticamente comparabile o migliore rispetto allo sketching dell'intero dataset.

Metodologia
Lo studio opera in un contesto di design fisso (fixed design setting), dove i punti di input $x_1, \dots, x_n$ sono fissi e le etichette sono generate tramite $y_i = x_i^T \alpha^* + \varepsilon_i$ con rumore Gaussiano i.i.d. Gli autori definiscono tre stimatori per il confronto:

1. $\hat{\alpha}^*$: L'esatto estimatore OLS sull'intero dataset.
2. $\bar{\beta}$: L'estimatore mediato derivato da sketch mappati dall'intero dataset (l'approccio standard di sketching distribuito).
3. $\bar{\theta}$: L'estimatore mediato derivato da sketch mappati da sottogruppi partizionati (l'approccio proposto).

L'analisi si concentra sull'eccesso di perdita esatto (la differenza tra la perdita quadratica attesa dell'estimatore e la perdita ottimale) per $\bar{\theta}$. Una quantità chiave introdotta per caratterizzare le prestazioni dell'approccio partizionato è $D$, definita come la media dei punteggi di leverage relativi attraverso i sottogruppi:
$$D = \frac{1}{k^2} \sum_{i=1}^k \sum_{j=1}^k \text{tr}[(X_i^T X_i)(X_j^T X_j)^{-1}]$$
Questa quantità funge da misura di divergenza per le covarianze dei sottogruppi di dati. Gli autori derivano i limiti teorici per l'eccesso di perdita atteso di $\bar{\theta}$ e li confrontano con i limiti noti per $\bar{\beta}$.

Contributi Chiave e Risultati

1. Caratterizzazione Esatta dell'Eccesso di Perdita: L'articolo fornisce un'espressione in forma chiusa per l'eccesso di perdita atteso dell'estimatore di sketching partizionato ($\bar{\theta}$). Il risultato mostra che la perdita dipende dalla varianza del rumore $\sigma^2$, dal numero di macchine $k$, dalla dimensione dello sketch $m$, dalla dimensione $d$ e dalla misura di divergenza $D$.
   $$\mathbb{E}[L(\bar{\theta})] - \mathbb{E}[L(\hat{\alpha}^*)] = \sigma^2 \frac{n - kd}{k(m - d - 1)} D + \sigma^2(D - d)$$
2. Confronto con lo Sketching dell'Intero Dataset: Gli autori dimostrano che la performance dell'approccio partizionato ($\bar{\theta}$) rispetto all'approccio dell'intero dataset ($\bar{\beta}$) è governata dal gap tra $D$ e $d$.
   • Se le covarianze dei sottogruppi hanno una piccola divergenza (ovvero, $D \approx d$, il che è comune quando i dati sono campionati i.i.d.), l'eccesso di perdita di $\bar{\theta}$ è comparabile o addirittura inferiore a quello di $\bar{\beta}$.
   • Se le covarianze dei sottogruppi hanno una grande divergenza (ad esempio, dati provenienti da fonti eterogenee), la perdita di $\bar{\theta}$ può superare quella di $\bar{\beta}$.
3. Numero Ottimale di Partizioni: Analizzando il valore atteso di $D$ sotto campionamento Gaussiano i.i.d., gli autori mostrano che il gap di performance tra i due metodi segue una forma a U invertita all'aumentare del numero di macchine $k$. Ciò implica che l'aumento di $k$ migliora inizialmente la performance relativa del metodo partizionato, ma oltre un certo punto, il gap diminuisce.
4. Efficienza Computazionale: L'articolo stabilisce che il costo computazionale dello sketching di un sottogruppo diminuisce linearmente con il numero di macchine ($O(mdn/k)$), mentre lo sketching dell'intero dataset rimane $O(mdn)$. I risultati empirici su dataset reali (Digit, California Housing, Covertype) confermano che il metodo partizionato riduce significativamente il tempo di addestramento all'aumentare di $k$, mantenendo al contempo un'accuratezza competitiva.
5. Limiti ad Alta Probabilità: Gli autori derivano i limiti ad alta probabilità per l'eccesso di perdita fuori campione (out-of-sample), mostrando che la perdita attesa è un proxy rappresentativo delle tipiche prestazioni dello sketching distribuito.

Significatività
L'articolo sostiene che lo sketching distribuito su partizioni di dati è un'alternativa valida ed efficiente allo sketching dell'intero dataset, in particolare per dataset massivi dove il costo di mappatura rappresenta un collo di bottiglia. La principale significatività risiede nella caratterizzazione teorica dell'eccesso di perdita esatto, che rivela che la partizione non degrada intrinsecamente la performance statistica, a condizione che i sottogruppi di dati siano relativamente omogenei (piccola divergenza di covarianza). Questa scoperta supporta l'adozione pratica dello sketching partizionato per ottenere sostanziali risparmi computazionali senza sacrificare l'accuratezza dell'estimatore OLS, purché la distribuzione dei dati tra le partizioni sia bilanciata. Il lavoro colma il divario tra efficienza computazionale e rigore statistico nella regressione lineare distribuita.