Gradual Capacity Growth for Sparse Network Discovery

Résumé Technique : Croissance Graduelle de la Capacité pour la Découverte de Réseaux Sparses

1. Énoncé du Problème

Le défi central de l'apprentissage des réseaux neuronaux épars (sparse) est que la relation entre la densité du réseau (sparsité) et la performance de la tâche est généralement inconnue et dépendante de la tâche. Bien que la performance sature typiquement au-delà d'une certaine « densité de fonctionnement » (la plus petite densité produisant une précision proche de celle d'un modèle dense), identifier cette densité nécessite habituellement des essais et erreurs coûteux ou un pré-entraînement dense.

Les approches existantes souffrent de limitations spécifiques :

• Élagage par Magnitude Itératif (IMP) : Nécessite un pré-entraînement dense et plusieurs cycles de ré-entraînement, ce qui engendre 3 à 4 fois plus d'opérations en virgule flottante (FLOPs) qu'un entraînement dense.
• Entraînement Sparse Dynamique (DST) & Élagage à l'Initialisation : Ces méthodes exigent que la densité cible soit fixée à l'avance, empêchant la découverte de la densité de fonctionnement optimale sans une recherche exhaustive.
• Expansion basée sur la Croissance : Les méthodes précédentes visent généralement à augmenter la largeur pour converger vers des modèles denses, traitant la sparsité comme un état temporaire plutôt que comme une propriété architecturale finale.

L'article postule que la découverte de la densité de fonctionnement est un problème distinct de l'optimisation d'un budget de sparsité fixé. L'objectif est de faire croître de manière constructive un réseau épars pour trouver la plus petite densité $\rho^*$ où la performance sature, sans pré-entraînement dense ni cible de sparsité prédéfinie, tout en minimisant le coût cumulé de l'entraînement.

2. Méthodologie : Croissance Graduelle de la Capacité (GCG)

Les auteurs proposent la Croissance Graduelle de la Capacité (GCG), un cadre d'entraînement constructif de "sparse-to-dense". Le GCG part d'une graine (seed) éparse et ajoute progressivement des connexions jusqu'à ce que la saturation de la performance soit estimée.

Composants Clés :

• Initialisation : Le réseau est initialisé en utilisant PHEW [19] à une faible densité ($\rho_{init}$), fournissant un point de départ performant tout en évitant les nœuds déconnectés.
• Mécanisme de Croissance (PathGrow) :
  • Motivation : Basé sur l'analyse du Noyau Tangent Neural (NTK), les connexions qui participent à des chemins de poids élevés accélèrent la convergence. Cependant, maximiser purement les poids des chemins peut créer des goulots d'étranglement (couches cachées étroites), nuisant à la généralisation.
  • Produit de la Magnitude des Poids des Chemins (PWMP) : Pour identifier efficacement les voies à haut signal, le GCG calcule un score $S(i, j)$ pour les arêtes potentielles. Ce score est le produit de la « complexité » du nœud source (PWMP total de l'entrée au nœud $i$) et de la « généralité » du nœud de destination (PWMP total du nœud $j$ vers la sortie). Ceci est calculé via une seule passe avant et arrière sur un réseau avec des poids en valeur absolue.
  • Échantillonnage Probabiliste : Au lieu d'ajouter de manière déterministe les arêtes ayant les scores les plus élevés (ce qui cause des goulots d'étranglement), PathGrow échantillonne de nouvelles connexions avec une probabilité proportionnelle à leurs scores PWMP. Cela biaise la croissance vers les voies à haut signal tout en préservant la diversité structurelle.
• Calendrier d'Entraînement :
  • Croissance Entrelacée : La croissance se produit tôt dans le processus d'entraînement, entrelacée avec de courtes phases d'« entraînement grossier ». Cela permet au réseau d'exposer des signaux de poids de chemin utiles avant que les gradients ne deviennent bruités.
  • Croissance Exponentielle : La densité augmente d'une fraction de la densité actuelle ($\Delta \rho_k = \gamma \cdot \rho_k$) à chaque étape, facilitant l'exploration efficace du paysage densité-performance.
  • Initialisation des Poids : Les nouvelles connexions sont initialisées avec des poids nuls pour éviter le bruit et permettre la descente de gradient d'apprendre les valeurs appropriées.
• Critère d'Arrêt :
  • Puisque l'entraînement intensif n'est pas effectué à chaque densité intermédiaire, la méthode ajuste une courbe de saturation exponentielle ($P(G_k) = P_0 + A(1 - e^{-\beta \rho_k})$) à la trajectoire performance-densité observée.
  • La densité de fonctionnement $\hat{\rho}^*$ est estimée comme la plus petite densité où la courbe ajustée atteint 95 % de l'amélioration maximale prédite.

3. Contributions Clés

1. Cadre Constructif : Le GCG introduit un paradigme de "sparse-to-dense" qui découvre la densité de fonctionnement pendant l'entraînement, éliminant le besoin de pré-entraînement dense ou d'un budget de sparsité prédéfini.
2. Algorithme PathGrow : Une règle de croissance probabiliste qui équilibre une convergence rapide (via les chemins à haut PWMP) avec une diversité structurelle (via l'échantillonnage aléatoire) pour éviter les goulots d'étranglement.
3. Efficacité : La méthode estime la densité de fonctionnement avec un coût d'entraînement cumulé nettement inférieur à celui de l'élagage itératif.
4. Validation Empirique : Des expériences approfondies sur CIFAR, TinyImageNet et ImageNet démontrent que le GCG identifie des sous-réseaux épars atteignant une performance proche du modèle dense à des densités modérées.

4. Résultats

• Performance vs Densité : Sur CIFAR et TinyImageNet, le GCG trouve des sous-réseaux qui égalent ou dépassent la performance de l'Élagage par Magnitude Itératif (IMP-C) à des densités d'environ 30–50 %. Bien que l'IMP-C atteigne une précision optimale à des densités plus faibles (~15–20 %), le GCG atteint une précision comparable à des densités modérées.
• Comparaison avec les Baselines :
  • PathGrow vs Alternatives : PathGrow surpasse ou égale la Croissance Aléatoire (RG) et la Croissance basée sur le Gradient (GG) sur la plupart des benchmarks. Il est plus efficace que GG, qui nécessite une estimation de gradient coûteuse pour les connexions manquantes.
  • GCG vs PHEW/RigL : Le GCG surpasse systématiquement l'élagage en une seule étape (PHEW) et l'entraînement sparse dynamique (RigL) lorsque les budgets d'entraînement sont normalisés, soulignant le bénéfice de la croissance itérative.
  • ImageNet : Sur l'échelle large d'ImageNet avec ResNet-50, le GCG accuse un retard d'environ 2 points de pourcentage par rapport aux méthodes dynamiques (comme RigL et GSE). Les auteurs attribuent cela à l'incapacité des méthodes de croissance pure à élaguer et réallouer les connexions qui deviennent moins utiles au fil du temps.
• Coût d'Entraînement : Le GCG est substantiellement plus efficace que l'IMP-C. Sur les benchmarks CIFAR, le GCG atteint une performance comparable avec environ 1,5× les FLOPs d'un entraînement dense, alors que l'IMP-C nécessite 3–4×.

5. Signification et Limites

Signification :
L'article présente l'apprentissage sparse non pas seulement comme un problème d'optimisation, mais comme une exploration de la manière dont les réseaux croissent pour devenir des sous-réseaux performants. Le GCG fournit un mécanisme pratique pour explorer le compromis précision-densité sous des budgets d'optimisation limités. Il sert d'approche complémentaire à l'élagage, particulièrement efficace pour découvrir des réseaux épars dans le régime de sparsité modérée sans le coût prohibitif du pré-entraînement dense.

Limites (telles qu'énoncées par les auteurs) :

• Plafond de Sparsité : Les méthodes de croissance pure ne peuvent pas atteindre les niveaux de sparsité extrême de l'élagage car les connexions de faible importance ne sont jamais explicitement supprimées.
• Spécificité de l'Architecture : L'heuristique PWMP est adaptée aux structures de type feed-forward et convolutionnelles et ne s'étend pas naturellement aux mécanismes d'attention (matrices requête-clé), où les magnitudes se découplent de l'importance fonctionnelle.
• Métriques d'Efficacité : L'analyse du coût est basée sur les FLOPs algorithmiques plutôt que sur le temps réel (wall-clock time), ignorant les surcoûts liés au matériel (ex: accès mémoire sparse, surcharge de lancement de noyau) qui pourraient compenser les gains sur les accélérateurs actuels.
• Domaine d'Application : Les expériences sont limitées aux benchmarks de vision ; la validation dans les domaines de l'NLP ou de la parole à grande échelle reste un travail futur.

Les auteurs concluent que le GCG représente une étape vers un agenda de recherche plus large basé sur la croissance, offrant une alternative constructive à l'élagage destructif et à l'entraînement dynamique à budget fixe.