Gradual Capacity Growth for Sparse Network Discovery

Technisches Resümee: Gradual Capacity Growth für die Entdeckung spärlicher Netzwerke

1. Problemstellung

Die zentrale Herausforderung beim Lernen in spärlichen (sparse) neuronalen Netzen besteht darin, dass die Beziehung zwischen Netzwerkdichte (Sparsity) und Aufgabenleistung im Allgemeinen unbekannt und aufgabenabhängig ist. Während die Leistung über einer gewissen „Betriebsdichte“ (der kleinsten Dichte, die eine nahezu dichte Genauigkeit liefert) typischerweise sättigt, erfordert die Identifizierung dieser Dichte normalerweise einen kostspieligen Trial-and-Error-Prozess oder ein dichtes Vortraining.

Bestehende Ansätze leiden unter spezifischen Einschränkungen:

• Iterative Magnitude Pruning (IMP): Erfordert dichtes Vortraining und mehrere Trainingszyklen, was 3- bis 4-mal mehr Fließkommaoperationen (FLOPs) als das dichte Training verursacht.
• Dynamic Sparse Training (DST) & Pruning-at-Initialization: Diese Methoden erfordern, dass die Ziel-Sparsity im Voraus festgelegt wird, was die Entdeckung der optimalen Betriebsdichte ohne erschöpfende Suche verhindert.
• Wachstumsbasierte Expansion: Frühere Methoden erweitern typischerweise die Breite, um zu dichten Modellen zu konvergieren, wobei Sparsity als temporäres statt als finales architektonisches Merkmal behandelt wird.

Das Paper postuliert, dass die Entdeckung der Betriebsdichte ein eigenständiges Problem von der Optimierung eines festen Sparsity-Budgets ist. Das Ziel ist es, ein spärliches Netzwerk konstruktiv wachsen zu lassen, um die kleinste Dichte $\rho^*$ zu finden, bei der die Leistung sättigt, ohne dichtes Vortraining oder eine vordefinierte Sparsity-Zielvorgabe zu nutzen, während gleichzeitig die kumulativen Trainingskosten minimiert werden.

2. Methodik: Gradual Capacity Growth (GCG)

Die Autoren schlagen Gradual Capacity Growth (GCG) vor, ein konstruktives Sparse-to-Dense-Trainingsframework. GCG beginnt mit einem spärlichen Seed und fügt progressiv Verbindungen hinzu, bis die Sättigung der Leistung geschätzt wird.

Kernkomponenten:

• Initialisierung: Das Netzwerk wird mittels PHEW [19] bei einer niedrigen Dichte ($\rho_{init}$) initialisiert, was einen leistungsfähigen Startpunkt bietet und gleichzeitig dislozierten Knoten vorbeugt.
• Wachstumsmechanismus (PathGrow):
  • Motivation: Basierend auf der Neural Tangent Kernel (NTK)-Analyse beschleunigen Verbindungen, die an Pfaden mit hohen Gewichtswerten teilnehmen, die Konvergenz. Ein reines Maximieren der Pfadgewichte kann jedoch Engpässe (schmale Hidden Layers) erzeugen, was die Generalisierung beeinträchtigt.
  • Path Weight Magnitude Product (PWMP): Um hocheffiziente Signalpfade zu identifizieren, berechnet GCG einen Score $S(i, j)$ für potenzielle Kanten. Dieser Score ist das Produkt der „Komplexität“ des Quellknotens (gesamter PWMP vom Input zum Knoten $i$) und der „Generalität“ des Zielknotens (gesamter PWMP vom Knoten $j zum Output). Dies wird über einen einzigen Vorwärts- und Rückwärtslauf auf einem Netzwerk mit Absolutwerten der Gewichte berechnet.
  • Probabilistisches Sampling: Anstatt deterministisch die am höchsten bewerteten Kanten hinzuzufügen (was Engpässe verursachen würde), sampelt PathGrow neue Verbindungen mit einer Wahrscheinlichkeit, die proportional zu ihren PWMP-Scores ist. Dies lenkt das Wachstum in Richtung hochsignifikanter Pfade, während die strukturelle Diversität erhalten bleibt.
• Trainingsplan:
  • Interleaved Growth: Das Wachstum findet früh im Trainingsprozess statt, eingebettet in kurze Phasen des „grob geschätzten Trainings“ (rough training). Dies ermöglicht es dem Netzwerk, nützliche Pfadgewicht-Signale offenzulegen, bevor die Gradienten verrauscht werden.
  • Exponentielles Wachstum: Die Dichte erhöht sich in jedem Schritt um einen Bruchteil der aktuellen Dichte ($\Delta \rho_k = \gamma \cdot \rho_k$), was eine effiziente Exploration der Dichte-Leistungs-Landschaft ermöglicht.
  • Gewichtsinitialisierung: Neue Verbindungen werden mit Gewichten von Null initialisiert, um Rauschen zu vermeiden und dem Gradientenabstieg zu ermöglichen, angemessene Werte zu lernen.
• Stoppkriterium:
  • Da in jeder Zwischenstufe kein extensives Training durchgeführt wird, passt die Methode eine exponentielle Sättigungskurve ($P(G_k) = P_0 + A(1 - e^{-\beta \rho_k})$) an die beobachtete Performance-Dichte-Trajektorie an.
  • Die Betriebsdichte $\hat{\rho}^*$ wird als die kleinste Dichte geschätzt, bei der die angepasste Kurve 95 % der maximal vorhergesagten Verbesserung erreicht.

3. Wichtige Beiträge

1. Konstruktives Framework: GCG führt ein Sparse-to-Dense-Paradigma ein, das die Betriebsdichte während des Trainings entdeckt und somit die Notwendigkeit für dichtes Vortraining oder ein vordefiniertes Sparsity-Budget eliminiert.
2. PathGrow-Algorithmus: Eine probabilistische Wachstumsregel, die schnelle Konvergenz (durch hohe PWMP-Pfade) mit struktureller Diversität (durch randomisiertes Sampling) ausbalanciert, um Engpässe zu vermeiden.
3. Effizienz: Die Methode schätzt die Betriebsdichte mit signifikant geringeren kumulativen Trainingskosten im Vergleich zu iterativem Pruning.
4. Empirische Validierung: Umfangreiche Experimente auf CIFAR, TinyImageNet und ImageNet zeigen, dass GCG spärliche Subnetzwerke identifiziert, die bei moderaten Dichten eine nahezu dichte Genauigkeit erreichen.

4. Ergebnisse

• Leistung vs. Dichte: Auf CIFAR und TinyImageNet findet GCG Subnetzwerke, die die Leistung von Iterative Magnitude Pruning (IMP-C) bei Dichten von etwa 30–50 % erreichen oder übertreffen. Während IMP-C die optimale Genauigkeit bei niedrigeren Dichten (~15–20 %) erreicht, erzielt GCG vergleichbare Genauigkeiten bei moderaten Dichten.
• Vergleich mit Baselines:
  • PathGrow vs. Alternativen: PathGrow übertrifft oder gleicht Random Growth (RG) und Gradient-based Growth (GG) in den meisten Benchmarks. Es ist effizienter als GG, welches eine teure Gradientenschätzung für fehlende Verbindungen benötigt.
  • GCG vs. PHEW/RigL: GCG übertrifft konsistent One-Shot-Pruning (PHEW) und Dynamic Sparse Training (RigL), wenn die Trainingsbudgets normalisiert sind, was den Vorteil des iterativen Wachstums unterstreicht.
  • ImageNet: Bei groß angelegtem ImageNet mit ResNet-50 liegt GCG etwa 2 Prozentpunkte hinter dynamischen Methoden (wie RigL und GSE) zurück. Die Autoren führen dies darauf zurück, dass rein wachstumsbasierte Methoden nicht in der Lage sind, Verbindungen zu prunen und neu zu allokieren, die im Laufe der Zeit weniger nützlich werden.
• Trainingskosten: GCG ist wesentlich effizienter als IMP-C. Bei CIFAR-Benchmarks erreicht GCG eine vergleichbare Leistung mit etwa 1,5× den FLOPs eines dichten Trainingslaufs, während IMP-C etwa 3–4× benötigt.

5. Bedeutung und Limitationen

Bedeutung:
Das Paper rahmt das Lernen in spärlichen Netzen nicht nur als Optimierungsproblem, sondern als Exploration der Frage, wie Netzwerke zu leistungsstarken Subnetzwerken heranwachsen. GCG bietet einen praktischen Mechanismus, um den Tradeoff zwischen Genauigkeit und Dichte unter begrenzten Optimierungsbudgets zu untersuchen. Es dient als komplementärer Ansatz zum Pruning, der besonders effektiv bei der Entdeckung spärlicher Netzwerke im moderaten Sparsity-Regime ist, ohne die prohibitiven Kosten eines dichten Vortrainings.

Limitationen (wie von den Autoren angegeben):

• Sparsity-Deckelung: Nur-Wachstums-Methoden können nicht die extremen Sparsity-Level von Pruning-Methoden erreichen, da Verbindungen mit geringer Wichtigkeit nie explizit entfernt werden.
• Architekturspezifität: Die PWMP-Heuristik ist auf Feed-Forward- und Convolutional-Strukturen zugeschnitten und lässt sich nicht natürlich auf Attention-Mechanismen (Query-Key-Matrizen) übertragen, bei denen Beträge von der funktionalen Wichtigkeit entkoppelt sind.
• Effizienzmetriken: Die Kostenanalyse basiert auf algorithmischen FLOPs statt auf der Wandzeit (Wall-Clock Time), wodurch hardware-spezifische Overheads (z. B. spärlicher Speicherzugriff, Kernel-Launch-Overhead) ignoriert werden, die die Gewinne auf aktuellen Beschleunigern zunichtemachen könnten.
• Domänenumfang: Die Experimente beschränken sich auf Vision-Benchmarks; die Validierung in groß angelegten NLP- oder Sprachdomänen bleibt zukünftige Arbeit.

Die Autoren kommen zu dem Schluss, dass GCG einen Schritt in Richtung einer breiteren wachstumsbasierten Forschungsagenda darstellt und eine konstruktive Alternative zum destruktiven Pruning und zum fest budgetierten dynamischen Training bietet.