Gradual Capacity Growth for Sparse Network Discovery

Technische Samenvatting: Graduele Capaciteitsgroei voor Sparse Netwerkontdekking

1. Probleemstelling

De centrale uitdaging in het leren van sparse neurale netwerken is dat de relatie tussen netwerkdichtheid (sparsity) en taakprestaties over het algemeen onbekend en taakafhankelijk is. Hoewel prestaties doorgaans verzadigen voorbij een bepaalde "operationele dichtheid" (de kleinste dichtheid die een prestatie nabij die van een dense model oplevert), vereist het identificeren van deze dichtheid meestal kostbare trial-and-error of dense pretraining.

Bestaande benaderingen lijden aan specifieke beperkingen:

• Iterative Magnitude Pruning (IMP): Vereist dense pretraining en meerdere hertrainingscycli, wat resulteert in 3–4× de floating-point operaties (FLOPs) van dense training.
• Dynamic Sparse Training (DST) & Pruning-at-Initialization: Deze methoden vereisen dat de doel-sparsity vooraf wordt vastgesteld, wat het ontdekken van de optimale operationele dichtheid verhindert zonder een uitputtende zoektocht.
• Groei-gebaseerde Expansie: Eerdere methoden breiden doorgaans de breedte uit om te convergeren naar dense modellen, waarbij sparsity wordt behandeld als een tijdelijk kenmerk in plaats van een definitieve architecturale eigenschap.

Het artikel stelt dat het ontdekken van de operationele dichtheid een ander probleem is dan het optimaliseren van een vaste sparsity-budget. Het doel is om een sparse netwerk constructief te laten groeien om de kleinste dichtheid $\rho^*$ te vinden waar de prestaties verzadigen, zonder dense pretraining of een vooraf ingestelde sparsity-target, terwijl de cumulatieve trainingskosten worden geminimaliseerd.

2. Methodologie: Gradual Capacity Growth (GCG)

De auteurs stellen Gradual Capacity Growth (GCG) voor, een constructief sparse-naar-dense trainingsframework. GCG start vanuit een sparse zaadje (seed) en voegt progressief verbindingen toe totdat de prestatieverzadiging wordt geschat.

Kerncomponenten:

• Initialisatie: Het netwerk wordt geïnitialiseerd met behulp van PHEW [19] op een lage dichtheid ($\rho_{init}$), wat een presterend startpunt biedt terwijl gedisconnecteerde nodes worden vermeden.
• Groeimechanisme (PathGrow):
  • Motivatie: Gebaseerd op Neural Tangent Kernel (NTK) analyse, versnellen verbindingen die deelnemen aan hoog-gewicht paden de convergentie. Echter, het puur maximaliseren van padgewichten kan bottlenecks creëren (smalle verborgen lagen), wat de generalisatie schaadt.
  • Path Weight Magnitude Product (PWMP): Om hoog-signaal paden efficiënt te identificeren, berekent GCG een score $S(i, j)$ voor potentiële randen (edges). Deze score is het product van de "complexiteit" van de bronnode (totale PWMP van input naar node $i$) en de "generaliteit" van de bestemmingsnode (totale PWMP van node $j$ naar output). Dit wordt berekend via een enkele forward en backward pass op een netwerk met absolute-gewichtswaarden.
  • Probabilistische Sampling: In plaats van deterministisch de hoogst scorende randen toe te voegen (wat bottlenecks veroorzaakt), samplet PathGrow nieuwe verbindingen met een waarschijnlijkheid proportioneel aan hun PWMP-scores. Dit stuurt de groei naar hoog-signaal paden terwijl de structurele diversiteit behouden blijft.
• Trainingsschema:
  • Interleaved Growth: Groei vindt vroeg in het trainingsproces plaats, afgewisseld met korte "ruwe trainingsfasen" (rough training). Dit stelt het netwerk in staat om nuttige pad-gewicht signalen bloot te leggen voordat gradiënten ruisachtig worden.
  • Exponentiële Groei: De dichtheid neemt bij elke stap toe met een fractie van de huidige dichtheid ($\Delta \rho_k = \gamma \cdot \rho_k$), wat een efficiënte exploratie van het dichtheid-prestatie landschap faciliteert.
  • Gewichtsinitialisatie: Nieuwe verbindingen worden geïnitialiseerd met nul-gewichten om ruis te voorkomen en gradiëntafdaling (gradient descent) de ruimte te geven om passende waarden te leren.
• Stopcriterium:
  • Omdat er niet uitgebreid wordt getraind bij elke tussenliggende dichtheid, past de methode een exponentiële verzadigingscurve ($P(G_k) = P_0 + A(1 - e^{-\beta \rho_k})$) toe op de geobserveerde prestatie-dichtheid traject.
  • De operationele dichtheid $\hat{\rho}^*$ wordt geschat als de kleinste dichtheid waar de passende curve 95% van de maximaal voorspelde verbetering bereikt.

3. Belangrijkste Bijdragen

1. Constructief Framework: GCG introduceert een sparse-naar-dense paradigma dat de operationele dichtheid tijdens de training ontdekt, waardoor de noodzaak voor dense pretraining of een vooraf ingesteld sparsity-budget vervalt.
2. PathGrow Algoritme: Een probabilistische groeiregel die snelle convergentie (via hoog-PWMP paden) balanceert met structurele diversiteit (via gerandomiseerde sampling) om bottlenecks te vermijden.
3. Efficiëntie: De methode schat de operationele dichtheid met aanzienlijk lagere cumulatieve trainingskosten vergeleken met iteratieve pruning.
4. Empirische Validatie: Uitgebreide experimenten op CIFAR, TinyImageNet en ImageNet demonstreren dat GCG sparse subnetwerken identificeert die een prestatie nabij die van dense modellen bereiken bij gematigde dichtheden.

4. Resultaten

• Prestaties vs. Dichtheid: Op CIFAR en TinyImageNet vindt GCG subnetwerken die de prestaties van Iterative Magnitude Pruning (IMP-C) evenaren of overtreffen bij dichtheden van ongeveer 30–50%. Hoewel IMP-C optimale nauwkeurigheid bereikt bij lagere dichtheden (~15–20%), bereikt GCG vergelijkbare nauwkeurigheid bij gematigde dichtheden.
• Vergelijking met Baselines:
  • PathGrow vs. Alternatieven: PathGrow presteert beter dan of even goed als Random Growth (RG) en Gradient-based Growth (GG) op de meeste benchmarks. Het is efficiënter dan GG, dat dure gradiëntschatting vereist voor ontbrekende verbindingen.
  • GCG vs. PHEW/RigL: GCG presteert consequent beter dan one-shot pruning (PHEW) en dynamic sparse training (RigL) wanneer de trainingsbudgetten genormaliseerd zijn, wat het voordeel van iteratieve groei onderstreept.
  • ImageNet: Op grootschalige ImageNet met ResNet-50 blijft GCG ongeveer 2 procentpunten achter bij dynamische methoden (zoals RigL en GSE). De auteurs schrijven dit toe aan het onvermogen van groei-alleen methoden om verbindingen die minder nuttig worden in de loop van de tijd te prunen en te heralloceren.
• Trainingskosten: GCG is aanzienlijk efficiënter dan IMP-C. Op CIFAR benchmarks bereikt GCG vergelijkbare prestaties met ongeveer 1.5× de FLOPs van een dense training run, terwijl IMP-C ongeveer 3–4× vereist.

5. Betekenis en Beperkingen

Betekenis:
Het artikel frameert sparse learning niet alleen als een optimalisatieprobleem, maar als een exploratie van hoe netwerken groeien naar hoog-presterende subnetwerken. GCG biedt een praktisch mechanisme om de nauwkeurigheid–dichtheid trade-off te verkennen onder beperkte optimalisatiebudgetten. Het dient als een complementaire benadering van pruning, die bijzonder effectief is voor het ontdekken van sparse netwerken in het gematigde sparsity-regime zonder de prohibitieve kosten van dense pretraining.

Beperkingen (zoals vermeld door de auteurs):

• Sparsity Ceiling: Groei-alleen methoden kunnen niet de extreme sparsity-niveaus van pruning bereiken omdat verbindingen met een lage belangrijkheid nooit expliciet worden verwijderd.
• Architectuur-specifiek: De PWMP-heuristiek is afgestemd op feed-forward en convolutionele structuren en breidt zich niet natuurlijk uit naar attention-mechanismen (query-key matrices), waar magnitudes ontkoppeld zijn van functionele belangrijkheid.
• Efficiëntiemetingen: De kostenanalyse is gebaseerd op algoritmische FLOPs in plaats van wandkloktijd, waarbij hardware-specifieke overheads (bijv. sparse geheugentoegang, kernel launch overheads) worden genegeerd die de winst op huidige versnellers kunnen compenseren.
• Domeinomvang: Experimenten zijn beperkt tot visuele benchmarks; validatie in grootschalige NLP of spraakdomeinen blijft toekomstig werk.

De auteurs concluderen dat GCG een stap vormt naar een bredere groei-gebaseerde onderzoeksagenda, en een constructief alternatief biedt voor destructieve pruning en fixed-budget dynamische training.