Gradual Capacity Growth for Sparse Network Discovery

Technical Summary: Gradual Capacity Growth for Sparse Network Discovery

1. Problem Statement

The central challenge in sparse neural network learning is that the relationship between network density (sparsity) and task performance is generally unknown and task-dependent. While performance typically saturates beyond a certain "operating density" (the smallest density yielding near-dense accuracy), identifying this density usually requires expensive trial-and-error or dense pretraining.

Existing approaches suffer from specific limitations:

• Iterative Magnitude Pruning (IMP): Requires dense pretraining and multiple retraining cycles, incurring 3–4× the floating-point operations (FLOPs) of dense training.
• Dynamic Sparse Training (DST) & Pruning-at-Initialization: These methods require the target sparsity to be fixed in advance, preventing the discovery of the optimal operating density without exhaustive search.
• Growth-based Expansion: Previous methods typically expand width to converge to dense models, treating sparsity as temporary rather than a final architectural property.

The paper posits that discovering the operating density is a distinct problem from optimizing a fixed sparsity budget. The goal is to constructively grow a sparse network to find the smallest density $\rho^*$ where performance saturates, without dense pretraining or a preset sparsity target, while minimizing cumulative training cost.

2. Methodology: Gradual Capacity Growth (GCG)

The authors propose Gradual Capacity Growth (GCG), a constructive sparse-to-dense training framework. GCG starts from a sparse seed and progressively adds connections until performance saturation is estimated.

Core Components:

• Initialization: The network is initialized using PHEW [19] at a low density ($\rho_{init}$), providing a performant starting point while avoiding disconnected nodes.
• Growth Mechanism (PathGrow):
  • Motivation: Based on Neural Tangent Kernel (NTK) analysis, connections that participate in high-weight paths accelerate convergence. However, purely maximizing path weights can create bottlenecks (narrow hidden layers), harming generalization.
  • Path Weight Magnitude Product (PWMP): To identify high-signal pathways efficiently, GCG computes a score $S(i, j)$ for potential edges. This score is the product of the "complexity" of the source node (total PWMP from input to node $i$) and the "generality" of the destination node (total PWMP from node $j$ to output). This is computed via a single forward and backward pass on a network with absolute-valued weights.
  • Probabilistic Sampling: Instead of deterministically adding the highest-scoring edges (which causes bottlenecks), PathGrow samples new connections with probability proportional to their PWMP scores. This biases growth toward high-signal pathways while preserving structural diversity.
• Training Schedule:
  • Interleaved Growth: Growth occurs early in the training process, interleaved with short "rough training" phases. This allows the network to expose useful path-weight signals before gradients become noisy.
  • Exponential Growth: Density increases by a fraction of the current density ($\Delta \rho_k = \gamma \cdot \rho_k$) at each step, facilitating efficient exploration of the density-performance landscape.
  • Weight Initialization: New connections are initialized with zero weights to avoid noise and allow gradient descent to learn appropriate values.
• Stopping Criterion:
  • Since extensive training is not performed at every intermediate density, the method fits an exponential saturation curve ($P(G_k) = P_0 + A(1 - e^{-\beta \rho_k})$) to the observed performance-density trajectory.
  • The operating density $\hat{\rho}^*$ is estimated as the smallest density where the fitted curve reaches 95% of the maximum predicted improvement.

3. Key Contributions

1. Constructive Framework: GCG introduces a sparse-to-dense paradigm that discovers the operating density during training, eliminating the need for dense pretraining or a preset sparsity budget.
2. PathGrow Algorithm: A probabilistic growth rule that balances rapid convergence (via high-PWMP paths) with structural diversity (via randomized sampling) to avoid bottlenecks.
3. Efficiency: The method estimates the operating density with significantly lower cumulative training cost compared to iterative pruning.
4. Empirical Validation: Extensive experiments on CIFAR, TinyImageNet, and ImageNet demonstrate that GCG identifies sparse subnetworks achieving near-dense performance at moderate densities.

4. Results

• Performance vs. Density: On CIFAR and TinyImageNet, GCG finds subnetworks that match or exceed the performance of Iterative Magnitude Pruning (IMP-C) at densities of roughly 30–50%. While IMP-C achieves optimal accuracy at lower densities (~15–20%), GCG reaches comparable accuracy at moderate densities.
• Comparison with Baselines:
  • PathGrow vs. Alternatives: PathGrow outperforms or matches Random Growth (RG) and Gradient-based Growth (GG) on most benchmarks. It is more efficient than GG, which requires expensive gradient estimation for missing connections.
  • GCG vs. PHEW/RigL: GCG consistently outperforms one-shot pruning (PHEW) and dynamic sparse training (RigL) when training budgets are normalized, highlighting the benefit of iterative growth.
  • ImageNet: On large-scale ImageNet with ResNet-50, GCG lags behind dynamic methods (like RigL and GSE) by approximately 2 percentage points. The authors attribute this to the inability of growth-only methods to prune and reallocate connections that become less useful over time.
• Training Cost: GCG is substantially more efficient than IMP-C. On CIFAR benchmarks, GCG achieves comparable performance with roughly 1.5× the FLOPs of a dense training run, whereas IMP-C requires 3–4×.

5. Significance and Limitations

Significance:
The paper frames sparse learning not just as an optimization problem but as an exploration of how networks grow into high-performing subnetworks. GCG provides a practical mechanism for exploring the accuracy–density tradeoff under limited optimization budgets. It serves as a complementary approach to pruning, particularly effective for discovering sparse networks in the moderate-sparsity regime without the prohibitive cost of dense pretraining.

Limitations (as stated by the authors):

• Sparsity Ceiling: Growth-only methods cannot reach the extreme sparsity levels of pruning because low-importance connections are never explicitly removed.
• Architecture Specificity: The PWMP heuristic is tailored for feed-forward and convolutional structures and does not naturally extend to attention mechanisms (query-key matrices), where magnitudes decouple from functional importance.
• Efficiency Metrics: The cost analysis is based on algorithmic FLOPs rather than wall-clock time, ignoring hardware-specific overheads (e.g., sparse memory access, kernel launch overheads) that might offset gains on current accelerators.
• Domain Scope: Experiments are limited to vision benchmarks; validation in large-scale NLP or speech domains remains future work.

The authors conclude that GCG represents a step toward a broader growth-based research agenda, offering a constructive alternative to destructive pruning and fixed-budget dynamic training.