Interference-Robust Non-Coherent Over-the-Air Computation for Decentralized Optimization

1. Il Problema

Il lavoro si concentra sull'ottimizzazione decentralizzata in reti wireless, un contesto fondamentale per applicazioni come il rilevamento remoto, la coordinazione di sciami di droni (UAV) e l'apprendimento automatico distribuito (Federated Learning) in ambienti privi di infrastruttura centrale (es. zone disastrate).

• Obiettivo: Risolvere il problema di ottimizzazione globale $F(w) = \frac{1}{N}\sum f_i(w)$, dove ogni nodo $i$ possiede solo la sua funzione locale $f_i(w)$ e non ha accesso ai dati degli altri.
• Algoritmo di riferimento: Viene utilizzato il Decentralized Gradient Descent (DGD), che richiede a ogni nodo di aggiornare i propri parametri combinando una discesa del gradiente locale con un passo di consenso basato sulla discrepanza rispetto ai vicini.
• La sfida: L'implementazione del DGD su canali wireless è complessa a causa di rumore, fading e interferenze. La soluzione precedente, nota come NCOTA (Non-Coherent Over-the-Air Computation), permette di calcolare la media dei parametri sfruttando la sovrapposizione naturale delle energie dei segnali wireless, senza richiedere informazioni sullo stato del canale (CSI) o schedulazione delle trasmissioni.
• Il limite critico: Sebbene la NCOTA sia efficiente, è intrinsecamente vulnerabile alle interferenze esterne. A differenza del rumore termico (che può essere compensato statisticamente), l'energia delle interferenze si accumula ai ricevitori, introducendo un bias (distorsione) non nullo nelle stime del segnale di discrepanza. Questo bias si accumula nel tempo, impedendo la convergenza dell'algoritmo di ottimizzazione verso la soluzione globale ottima.

2. Metodologia Proposta: IR-NCOTA

L'autore propone un nuovo schema chiamato IR-NCOTA (Interference-Robust NCOTA) per preservare l'efficienza della NCOTA anche in presenza di interferenze esterne non controllate. L'idea centrale è trasformare l'interferenza in una distribuzione circolare simmetrica a media zero rispetto al sistema di riferimento rotante.

Lo schema si basa su due meccanismi chiave:

A. Rotazione Casuale Coordinata del Riferimento

• Concetto: Invece di utilizzare un sistema di riferimento fisso per codificare i vettori dei parametri locali, tutti i nodi applicano una trasformazione unitaria casuale coordinata ($U$) ai propri vettori locali prima della trasmissione.
• Implementazione: La matrice $U$ è generata da una sequenza pseudo-casuale condivisa (es. un semplice cambio di segno $U = sI$ con $s \in \{+1, -1\}$) e cambia ad ogni iterazione.
• Effetto: Poiché l'interferenza è statisticamente indipendente dalla rotazione $U$, quando si calcola la media delle stime su più iterazioni, il contributo dell'interferenza si annulla statisticamente (media zero), mentre il segnale utile viene recuperato ruotando indietro il risultato con $U^\top$.

B. Sequenza Pilota Pseudo-Rasuale

• Concetto: Per stimare correttamente i pesi del Laplaciano (che dipendono dai guadagni medi del canale) senza essere distorti dall'interferenza, i nodi trasmettono una sequenza pilota con fasi casuali pseudo-randomizzate.
• Funzionamento: I nodi trasmettono piloti con fasi $\phi_m$ distribuite uniformemente. Questo permette di stimare la somma dei guadagni del canale ($\bar{\Lambda}_i$) sfruttando le correlazioni incrociate tra i piloti, assicurandosi che il termine di interferenza rimanga a media zero grazie all'indipendenza tra le fasi dei piloti e il segnale di interferenza.

Stima del Segnale di Discrepanza

Il segnale di discrepanza $\hat{d}_i$ viene ricostruito combinando le due stime:

1. Stima della somma pesata dei parametri vicini ($\hat{s}_i$), ottenuta dopo la rotazione inversa.
2. Stima della somma dei guadagni di canale ($\hat{\Lambda}_i$) moltiplicata per il parametro locale noto $w_i$.
   La formula finale è: $\hat{d}_i = \hat{s}_i - \hat{\Lambda}_i w_i$.
   Grazie a questi accorgimenti, l'aspettativa matematica della stima rimane invariata: $E[\hat{d}_i] = d_i$, ripristinando la condizione di invarianza (unbiasedness) necessaria per la convergenza del DGD.

3. Risultati Numerici

Gli autori hanno valutato le prestazioni su un compito di classificazione utilizzando il dataset Fashion-MNIST con una rete di 200 nodi distribuiti su un'area circolare.

• Scenario senza interferenza: IR-NCOTA mostra prestazioni comparabili alla NCOTA classica, confermando che l'introduzione dei meccanismi di robustezza non degrada le prestazioni in condizioni ideali.
• Scenario con interferenza attiva:
  • NCOTA Classica: Fallisce completamente. Le metriche di errore (norma dell'errore, gap di sub-ottimalità, errore di test) raggiungono un "pavimento" (floor) stabile, indicando che l'algoritmo non converge a causa della distorsione accumulata.
  • IR-NCOTA: Riesce a mitigare l'effetto dell'interferenza. Le metriche di errore continuano a diminuire nel tempo, garantendo la convergenza verso la soluzione ottima globale. Sebbene il tasso di convergenza sia leggermente più lento rispetto al caso senza interferenza (a causa dell'aumento della varianza nelle stime), l'algoritmo rimane stabile e funzionale.

4. Contributi Chiave

1. Identificazione del limite: Dimostrazione teorica che la NCOTA perde la proprietà di stime non distorte in presenza di interferenze esterne, portando al fallimento della convergenza.
2. Nuovo Schema (IR-NCOTA): Proposta di un protocollo che utilizza rotazioni di riferimento coordinate e piloti casuali per "spazzare via" statisticamente l'interferenza.
3. Garanzia di Convergenza: Dimostrazione che lo schema proposto mantiene la condizione di non distorsione ($E[\hat{d}_i] = d_i$), preservando così i teoremi di convergenza del DGD anche in ambienti ostili.
4. Efficienza: La soluzione richiede un overhead minimo (circa l'1% di tempo aggiuntivo per i piloti) e non necessita di informazioni sullo stato del canale o di coordinamento complesso oltre alla sequenza pseudo-casuale condivisa.

5. Significato e Impatto

Questo lavoro è significativo perché estende l'applicabilità della computazione over-the-air (OTA) non coerente a scenari reali e dinamici, dove le interferenze (intenzionali o accidentali) sono comuni.

• Robustezza: Permette di utilizzare algoritmi di ottimizzazione decentralizzata in ambienti "hostili" (es. operazioni di soccorso, aree militari, zone rurali con scarsa copertura) dove l'infrastruttura è assente e le interferenze sono inevitabili.
• Scalabilità: Mantiene i vantaggi della NCOTA (nessuna schedulazione, scalabilità a reti dense, assenza di CSI) risolvendone il principale punto debole.
• Implicazioni per il ML Distribuito: Offre una soluzione pratica per il Federated Learning su reti wireless ad hoc, garantendo che i modelli globali convergano correttamente anche in presenza di disturbi esterni.

In sintesi, il paper trasforma la NCOTA da una tecnica promettente ma fragile in una soluzione robusta e pronta per il deployment in scenari di ottimizzazione decentralizzata reali.