Riepilogo Tecnico: Condizioni di Validità Pratiche per l'Apprendimento Federato Tollerante ai Comportamenti Bizantini

1. Enunciato del Problema

Nell'Apprendimento Federato (FL), un server centrale aggrega aggiornamenti di modelli ad alta dimensionalità provenienti da $n$ client. Quando fino a $t$ client sono bizantini (malintenzionati o difettosi), possono inviare vettori arbitrari per interrompere il processo di apprendimento. La sfida fondamentale consiste nel definire condizioni di validità—garanzie geometriche che specificano dove deve risiedere l'output dell'aggregazione rispetto agli input onesti—senza fare affidamento su distribuzioni dei dati specifiche o modelli di attacco.

La classica condizione di validità convessa, che richiede che l'output risieda all'interno dell'involucro convesso dei vettori onesti, è teoricamente solida ma praticamente difettosa per il FL moderno. Soffre di una resilienza dipendente dalla dimensionalità, tollerando al massimo $t < n/(d+1)$ client bizantini in $d$ dimensioni. Questo limite è troppo restrittivo per modelli ad alta dimensionalità. Inoltre, le regole di aggregazione pratiche spesso producono output fuori dall'involucro convesso dei vettori onesti pur rimanendo vicini alla popolazione onesta, un comportamento che la validità convessa non riesce a catturare.

2. Metodologia e Quadro Teorico

Gli autori propongono un nuovo quadro di validità basato sulla Sfera Minima Circoscritta (MEB) piuttosto che sull'involucro convesso.

• Validità MEB: Richiede che il vettore di output risieda all'interno della sfera più piccola che racchiude tutti i vettori di input onesti. A differenza dell'involucro convesso, la MEB è un oggetto a dimensionalità piena che accoglie naturalmente gli output che escono dall'involucro convesso ma rimangono entro la scala geometrica degli aggiornamenti onesti.
• Validità c-MEB (Rilassata): Riconoscendo che la validità MEB esatta soffre ancora di limitazioni di resilienza nelle alte dimensioni, gli autori introducono un rilassamento moltiplicativo. Un algoritmo soddisfa la validità c-MEB se l'output risiede all'interno di una sfera centrata sul centro della MEB onesta, ma con un raggio espanso di un fattore $c$ (cioè raggio $c \cdot r^*$).
• Area Sicura: Gli autori definiscono un'"area sicura" per la validità MEB come l'intersezione delle MEB di tutti i possibili sottoinsiemi di $n-t$ vettori. Dimostrano che soddisfare la validità MEB richiede un accordo all'interno di questa intersezione.

3. Contributi e Risultati Chiave

A. Limiti della Validità MEB Esatta

Il documento stabilisce che la validità MEB esatta non è universalmente raggiungibile in contesti ad alta dimensionalità.

• Risultato di Impossibilità: Gli autori dimostrano che nessun algoritmo di accordo può soddisfare la validità MEB esatta se $n \le (d+1)t - d$. Questo riflette le limitazioni di resilienza della validità convessa, dimostrando che il contenimento geometrico rigoroso è insufficiente per la tolleranza ai comportamenti bizantini in alte dimensioni.

B. Algoritmo Ottimale per la Validità MEB Rilassata

Sotto l'assunzione di una maggioranza onesta ($n > 2t$), gli autori presentano MinMax-MEB, una regola di aggregazione ottimale per la validità c-MEB.

• Meccanismo: L'algoritmo calcola la MEB per ogni sottoinsieme di $n-t$ client. Successivamente, seleziona un vettore di output che minimizza la massima distanza normalizzata rispetto a queste MEB candidate.
• Limite di Rilassamento: Utilizzando il teorema di Soddy-Gosset (una generalizzazione del teorema di Descartes sulle sfere tangenti), gli autori dimostrano che per $n > 2t$, il fattore di rilassamento ottimale $c$ è limitato superiormente da:
  $$c < \sqrt{2}$$
  Nello specifico, $c \le 1 + \frac{k-1}{k+1+\sqrt{2(k+1)k}}$, dove $k = \min\{d, \frac{n}{n-t} - 1\}$. Questo limite è stretto per $d=2$.

C. Garanzie di Validità per Aggregatori Pratici

Il documento analizza le esistenti regole di aggregazione robuste per determinare le loro costanti di validità c-MEB:

1. Media a Diametro Minimo (MDA): Soddisfa la validità $\left(1 + \frac{2t}{n-t}\right)$-MEB.
2. Medoide: Soddisfa la validità $\frac{3n-2t}{n-2t}$-MEB. Gli autori dimostrano inoltre che il medoide non può soddisfare la validità c-MEB per $c \le 2$.
3. Mediana Geometrica: Soddisfa la validità $\frac{2(n-t)}{n-2t}$-MEB. Il documento fornisce controesempi che mostrano come la mediana geometrica non soddisfi la validità 1.08-MEB e non soddisfi la validità convessa.

Questi risultati dimostrano che gli algoritmi pratici standard, pur violando la stretta validità convessa, soddisfano intrinsecamente la validità MEB rilassata con fattori costanti dipendenti dal rapporto tra nodi bizantini e onesti.

D. Confronto Sistematico delle Condizioni di Validità

Gli autori mappano le relazioni tra la validità MEB e le condizioni esistenti:

• Validità Convessa $\implies$ Validità MEB: Poiché l'involucro convesso è contenuto all'interno della MEB, qualsiasi output che soddisfa la validità convessa soddisfa automaticamente la validità MEB.
• Validità MEB $\nRightarrow$ Validità Convessa: La validità MEB permette output fuori dall'involucro convesso (ad esempio, in un sottospazio a dimensionalità inferiore collassato dall'involucro convesso).
• Relazione con la Validità Convessa Rilassata: La validità c-MEB implica la validità convessa rilassata $(\delta, 2)$ con $\delta = (c+1)r^*$. Viceversa, la validità convessa rilassata implica una validità MEB rilassata.
• Relazione con la Validità a Scatola: La validità a scatola (limiti per coordinata) implica la validità $\sqrt{d}$-MEB, ma la validità MEB non implica la validità a scatola, poiché la MEB è a dimensionalità piena mentre la scatola può collassare in certe dimensioni.

4. Significato e Affermazioni

Il documento afferma che la validità c-MEB offre un'alternativa pratica alla validità convessa per l'Apprendimento Federato tollerante ai comportamenti bizantini.

• Collegamento tra Teoria e Pratica: Collega le condizioni di validità geometriche utilizzate nel calcolo distribuito con il comportamento delle regole di aggregazione pratiche utilizzate nel FL.
• Indipendenza dalla Dimensionalità: A differenza della validità convessa, la condizione MEB rilassata non soffre di limiti di resilienza dipendenti dalla dimensionalità (purché $n > 2t$), rendendola adatta per modelli ad alta dimensionalità.
• Limite di Bias: Gli autori notano che la validità c-MEB fornisce un limite indipendente dalla distribuzione sul bias dell'aggregato rispetto all'aggiornamento medio onesto, collegando le garanzie geometriche alle analisi standard dell'ottimizzazione robusta ai comportamenti bizantini.

5. Limitazioni

Gli autori riconoscono diverse limitazioni:

• Complessità Computazionale: La regola ottimale MinMax-MEB richiede il calcolo delle MEB per tutti i sottoinsiemi di dimensione $n-t$, il che è computazionalmente costoso per grandi $t$. Le regole pratiche (Medoide, Mediana Geometrica) sono più efficienti ma offrono fattori di rilassamento più deboli.
• Assunzioni sul Modello: Il quadro teorico assume un server fidato, comunicazioni affidabili, geometria euclidea e un limite superiore noto $t$ sui client bizantini.
• Strettezza dei Limiti: Sebbene il limite $c < \sqrt{2}$ sia stretto per $d=2$, i fattori ottimali per dimensioni superiori e per algoritmi specifici come MDA e Medoide potrebbero essere più stretti di quanto attualmente dimostrato.
• Additivo vs Moltiplicativo: Il documento nota che la relazione tra rilassamenti moltiplicativi e additivi della validità MEB rimane una questione aperta.