Multifold Confidence Intervals in Collaborative Mean Estimation (ColME) Using Sample Statistics

1. Problema e Contesto

Il lavoro si inserisce nel contesto dell'apprendimento decentralizzato e collaborativo (Federated Learning), reso necessario dalla crescita dei dispositivi IoT e la necessità di elaborare dati sensibili senza trasmissione centralizzata.
Il problema specifico affrontato è la stima della media online in ambienti eterogenei. In questi scenari, agenti distribuiti generano dati da distribuzioni diverse. L'obiettivo è che ogni agente stimi la propria media locale ($\mu_a$) il più rapidamente possibile collaborando solo con altri agenti che appartengono alla stessa "classe di similarità" (ovvero, agenti con la stessa distribuzione sottostante).

Le sfide principali identificate sono:

• Eterogeneità dei dati: Gli agenti possono avere distribuzioni con medie diverse, varianze diverse o forme di distribuzione diverse (es. Gaussiane vs Uniformi).
• Limitazioni delle stime esistenti: Gli approcci precedenti (come ColME, C-colME, B-colME) si basano principalmente sull'intersezione degli intervalli di confidenza delle medie. Questo fallisce o converge molto lentamente quando:
  1. Le medie sono molto simili ma le varianze sono diverse.
  2. Le medie e le varianze sono simili, ma le distribuzioni differiscono per caratteristiche di ordine superiore (es. curtosi).
• Dipendenza dalla varianza nota: Gli algoritmi esistenti spesso assumono che la varianza sia nota a priori, mentre in scenari reali deve essere stimata online e localmente.

2. Metodologia Proposta

L'autore propone un framework unificato che estende gli algoritmi collaborativi esistenti introducendo la stima online di statistiche campionarie aggiuntive e l'uso di intervalli di confidenza multipli (multifold).

A. Stima della Varianza e della Curtosi (Indipendente dalla Media)

Un contributo fondamentale è lo sviluppo di stimatori per la varianza e la curtosi che non richiedono la conoscenza della media locale ($\mu_a$), evitando così un circolo vizioso di dipendenza.

• Variabile di Differenza: Viene definita una nuova variabile casuale $d_a(t) = x_a(t) - x_a(t-1)$. Poiché la media attesa è costante nel tempo, $E[d_a(t)] = 0$.
• Stima della Varianza: Sfruttando la proprietà $E[d_a(t)^2] = 2\sigma^2$, la varianza viene stimata localmente e collaborativamente (tra vicini) utilizzando le differenze tra campioni consecutivi.
• Stima della Curtosi: Viene stimato il quarto momento centrale (e quindi la curtosi $\kappa$) utilizzando le differenze elevate alla quarta potenza, correggendo per il contributo della varianza stimata.
• Stima dell'Errore: Vengono derivati gli intervalli di confidenza (e l'errore standard) per gli stimatori della deviazione standard ($\hat{\sigma}$) e della curtosi ($\hat{\kappa}$), basandosi su distribuzioni sub-Gaussiane e approssimazioni di Fisher.

B. Intervalli di Confidenza Multipli (Multifold)

Invece di confrontare solo le medie, il sistema verifica l'intersezione degli intervalli di confidenza su tre dimensioni:

1. Media ($I_a$): Basata sulla media campionaria.
2. Deviazione Standard ($I_\sigma$): Basata sulla stima della deviazione standard.
3. Curtosi ($I_\kappa$): Basata sulla stima della curtosi.

Un collegamento (arco) tra due agenti nel grafo di comunicazione viene mantenuto solo se tutti gli intervalli di confidenza corrispondenti si intersecano. Se anche solo uno di essi non si interseca, l'arco viene "potato" (disconnesso). Questo permette di separare classi che sono indistinguibili su una singola dimensione statistica.

C. Grafi Ponderati

Per evitare la "potatura falsa" (disconnessione prematura di agenti simili a causa di fluttuazioni statistiche) e accelerare la convergenza, vengono introdotti grafi ponderati.

• I pesi degli archi sono calcolati usando un kernel Gaussiano basato sulla distanza normalizzata rispetto agli intervalli di confidenza.
• Il peso è determinato dal minimo tra i pesi calcolati per media, deviazione standard e curtosi, dando priorità alla misura meno certa (o più discriminante).

3. Contributi Chiave

1. Stimatori Online Indipendenti: Introduzione di stimatori per varianza e curtosi che non dipendono dalla media nota, rendendoli applicabili in scenari di apprendimento online puri.
2. Framework Multi-statistico: Estensione del ColME per utilizzare simultaneamente media, deviazione standard e curtosi per determinare le classi di similarità.
3. Gestione di Casi Complessi: Capacità di risolvere scenari precedentemente irrisolvibili:
   • Classi con medie simili ma varianze diverse.
   • Classi con medie e varianze simili ma distribuzioni diverse (diversa curtosi).
4. Analisi del Tempo di Separazione: Derivazione teorica del tempo atteso di separazione ($T_{sep}$) per ciascuna statistica, dimostrando come l'uso combinato riduca drasticamente il tempo necessario per identificare le classi corrette.

4. Risultati Sperimentali

I risultati sono stati validati tramite simulazioni numeriche con diversi scenari:

• Scenario 1 (Medie simili, Varianze diverse): L'uso degli intervalli di confidenza sulla deviazione standard ha permesso una separazione delle classi molto più rapida ($T_{sep} \approx 416$) rispetto all'uso della sola media ($T_{sep} \approx 4265$).
• Scenario 2 (Medie e Varianze simili, Curtosi diverse): In casi dove media e varianza non erano discriminanti, l'introduzione degli intervalli sulla curtosi ha permesso la separazione delle classi (es. distribuzione Bernoulli vs somma di uniformi).
• Scenario 3 (Multiclasse complessa): Un esempio con 4 classi diverse ha mostrato come l'algoritmo selezioni dinamicamente quale statistica utilizzare per separare le coppie di classi specifiche.
• Convergenza: Gli algoritmi proposti (B-colME e C-colME con intervalli multipli) convergono alla soluzione "Oracle" (la migliore possibile se le classi fossero note a priori) con un errore quadratico medio (MSE) significativamente inferiore rispetto alle stime locali o agli approcci non ponderati.
• Effetto dei Grafi Ponderati: L'uso dei pesi Gaussiani ha ulteriormente accelerato la convergenza, riducendo l'MSE e il numero di collegamenti errati ("wrong links") più velocemente rispetto ai grafi non ponderati.

5. Significato e Impatto

Questo lavoro rappresenta un avanzamento significativo nel campo dell'apprendimento decentralizzato e collaborativo:

• Robustezza all'Eterogeneità: Fornisce un meccanismo robusto per gestire la diversità dei dati senza richiedere assunzioni forti sulla conoscenza a priori delle distribuzioni.
• Efficienza in Scenari IoT: Permette di accelerare l'apprendimento in reti di dispositivi IoT dove i dati sono limitati e le distribuzioni possono variare sottilmente ma criticamente.
• Generalizzazione: Estende la teoria degli intervalli di confidenza oltre la semplice media, aprendo la strada a metodi di clustering e stima collaborativa basati su momenti statistici di ordine superiore.

In sintesi, il paper dimostra che integrare la stima di varianza e curtosi direttamente nel processo di selezione dei collaboratori permette di superare i limiti degli approcci basati solo sulla media, garantendo una convergenza più rapida e accurata in ambienti distribuiti complessi.