Gradual Capacity Growth for Sparse Network Discovery

Sintesi Tecnica: Crescita Graduale della Capacità per la Scoperta di Reti Sparse

1. Definizione del Problema

La sfida centrale nell'apprendimento di reti neurali sparse è che la relazione tra densità della rete (sparsità) e performance del task è generalmente sconosciuta e dipendente dal task stesso. Sebbene le performance tendano a saturare oltre una certa "densità operativa" (la densità minima che produce un'accuratezza quasi pari a quella del modello denso), identificare questa densità richiede solitamente costosi tentativi ed errori o un pre-addestramento denso.

Gli approcci esistenti soffrono di specifiche limitazioni:

• Iterative Magnitude Pruning (IMP): Richiede il pre-addestramento denso e molteplici cicli di ri-addestramento, comportando un numero di operazioni in virgola mobile (FLOPs) da 3 a 4 volte superiore rispetto all'addestramento denso.
• Dynamic Sparse Training (DST) & Pruning-at-Initialization: Questi metodi richiedono che la densità target sia fissata in anticipo, impedendo la scoperta della densità operativa ottimale senza una ricerca esaustiva.
• Espansione basata sulla crescita (Growth-based Expansion): I metodi precedenti tipicamente espandono la larghezza per convergere verso modelli densi, trattando la sparsità come una proprietà temporanea piuttosto che come una proprietà architettonica finale.

Il paper sostiene che la scoperta della densità operativa sia un problema distinto dall'ottimizzazione di un budget di sparsità prestabilito. L'obiettivo è far crescere costruttivamente una rete sparsa per trovare la densità minima $\rho^*$ dove le performance saturano, senza pre-addestramento denso o un target di sparsità predefinito, minimizzando al contempo il costo cumulativo dell'addestramento.

2. Metodologia: Crescita Graduale della Capacità (GCG)

Gli autori propongono la Gradual Capacity Growth (GCG), un framework di addestramento costruttivo da sparse a dense. GCG parte da un seme sparso e aggiunge progressivamente connessioni finché non viene stimata la saturazione delle performance.

Componenti Core:

• Inizializzazione: La rete viene inizializzata utilizzando PHEW [19] a una bassa densità ($\rho_{init}$), fornendo un punto di partenza performante ed evitando nodi disconnessi.
• Meccanismo di Crescita (PathGrow):
  • Motivazione: In base all'analisi del Neural Tangent Kernel (NTK), le connessioni che partecipano a percorsi ad alto peso accelerano la converenza. Tuttavia, massimizzare puramente i pesi dei percorsi può creare colli di bottiglia (layer nascosti stretti), danneggiando la generalizzazione.
  • Path Weight Magnitude Product (PWMP): Per identificare efficientemente i percorsi ad alto segnale, GCG calcola un punteggio $S(i, j)$ per i potenziali archi. Questo punteggio è il prodotto della "complessità" del nodo sorgente (PWMP totale dall'input al nodo $i$) e della "generalità" del nodo di destinazione (PWMP totale dal nodo $j$ all'output). Ciò viene calcolato tramite un singolo passaggio forward e backward su una rete con pesi in valore assoluto.
  • Campionamento Probabilistico: Inveve di aggiungere deterministicamente gli archi con il punteggio più alto (il che causerebbe colli di bottiglia), PathGrow campiona nuove connessioni con una probabilità proporzionale ai loro punteggi PWMP. Questo orienta la crescita verso percorsi ad alto segnale preservando al contempo la diversità strutturale.
• Programma di Addestramento (Training Schedule):
  • Crescita Intervallata: La crescita avviene nelle fasi iniziali del processo di addestramento, intervallata da brevi fasi di "addestramento approssimativo" (rough training). Ciò consente alla rete di esporre segnali utili del peso del percorso prima che i gradienti diventino rumorosi.
  • Crescita Esponenziale: La densità aumenta di una frazione della densità corrente ($\Delta \rho_k = \gamma \cdot \rho_k$) ad ogni step, facilitando un'esplorazione efficiente del panorama densità-performance.
  • Inizializzazione dei Pesi: Le nuove connessioni vengono inizializzate con pesi nulli per evitare rumore e permettere al gradiente discendente di apprendere i valori appropriati.
• Criterio di Arresto:
  • Poiché non viene eseguito un addestramento esteso ad ogni densità intermedia, il metodo adatta una curva di saturazione esponenziale ($P(G_k) = P_0 + A(1 - e^{-\beta \rho_k})$) alla traiettoria osservata tra performance e densità.
  • La densità operativa $\hat{\rho}^*$ viene stimata come la densità minima in cui la curva adattata raggiunge il 95% del massimo miglioramento previsto.

3. Contributi Chiave

1. Framework Costruttivo: GCG introduce un paradigma da sparse a dense che scopre la densità operativa durante l'addestramento, eliminando la necessità di pre-addestramento denso o di un budget di sparsità predefinito.
2. Algoritmo PathGrow: Una regola di crescita probabilistica che bilancia una rapida convergenza (tramite percorsi ad alto PWMP) con la diversità strutturale (tramite campionamento randomizzato) per evitare colli di bottiglia.
3. Efficienza: Il metodo stima la densità operativa con un costo di addestramento cumulativo significativamente inferiore rispetto al pruning iterativo.
4. Validazione Empirica: Esperimenti estesi su CIFAR, TinyImageNet e ImageNet dimostrano che GCG identifica sottoreti sparse che raggiungono prestazioni simili a quelle dense.

4. Risultati

• Performance vs. Densità: Su CIFAR e TinyImageNet, GCG trova sottoreti che eguagliano o superano le performance di Iterative Magnitude Pruning (IMP-C) a densità di circa il 30–50%. Mentre IMP-C raggiunge l'accuratezza ottimale a densità inferiori (~15–20%), GCG raggiunge un'accuratezza comparabile a densità moderate.
• Confronto con i Baseline:
  • PathGrow vs. Alternative: PathGrow supera o eguaglia Random Growth (RG) e Gradient-based Growth (GG) nella maggior parte dei benchmark. È più efficiente di GG, che richiede una costosa stima del gradiente per le connessioni mancanti.
  • GCG vs. PHEW/RigL: GCG supera costantemente il pruning one-shot (PHEW) e il dynamic sparse training (RigL) quando i budget di addestramento sono normalizzati, evidenziando il vantaggio della crescita iterativa.
  • ImageNet: Su ImageNet su larga scala con ResNet-50, GCG resta indietro rispetto ai metodi dinamici (come RigL e GSE) di circa 2 punti percentuali. Gli autori attribuiscono ciò all'incapacità dei metodi basati solo sulla crescita di eliminare (pruning) e riallocare le connessioni che diventano meno utili nel tempo.
• Costo di Addestramento: GCG è sostanzialmente più efficiente di IMP-C. Sui benchmark CIFAR, GCG ottiene prestazioni comparabili con circa 1,5× i FLOPs di un addestramento denso, mentre IMP-C richiede 3–4×.

5. Significato e Limitazioni

Significato:
Il paper inquadra l'apprendimento sparso non solo come un problema di ottimizzazione, ma come un'esplorazione di come le reti crescono verso sottoreti ad alte prestazioni. GCG fornisce un meccanismo pratico per esplorare il compromesso accuratezza-densità sotto budget di ottimizzazione limitati. Funge da approccio complementare al pruning, particolarmente efficace per scoprire reti sparse nel regime di moderata sparsità senza il costo proibitivo del pre-addestramento denso.

Limitazioni (come dichiarato dagli autori):

• Soffitto di Sparsità: I metodi basati solo sulla crescita non possono raggiungere i livelli di estrema sparsità del pruning perché le connessioni a bassa importanza non vengono mai esplicitamente rimosse.
• Specificità dell'Architettura: L'euristica PWMP è adattata per strutture feed-forward e convoluzionali e non si estende naturalmente ai meccanismi di attenzione (matrici query-key), dove i pesi si disaccoppiano dall'importanza funzionale.
• Metriche di Efficienza: L'analisi dei costi si basa sui FLOPs algoritmici piuttosto che sul tempo di esecuzione reale (wall-clock time), ignorando gli overhead hardware-specifici (es. accesso alla memoria sparsa, overhead del kernel launch) che potrebbero annullare i guadagni sugli acceleratori attuali.
• Ambito del Dominio: Gli esperimenti sono limitati ai benchmark di visione; la validazione in domini NLP o speech su larga scala rimane un lavoro futuro.

Gli autori concludono che GCG rappresenta un passo verso un'agenda di ricerca più ampia basata sulla crescita, offrendo un'alternativa costruttiva al pruning distruttivo e al training dinamico a budget fisso.