A Theoretical View on Sparsely Activated Networks

Cenk Baykal, Nishanth Dikkala, Rina Panigrahy, Cyrus Rashtchian, Xin Wang

TL;DR

This paper provides a theoretical framework for understanding why sparsely activated neural networks, like Mixture-of-Experts (MoE) models, can achieve comparable performance to dense networks while being significantly more efficient during inference. They introduce a formal model and prove that these sparse networks can approximate Lipschitz functions as effectively as dense networks, but with exponentially fewer computations.

What Problem Does This Paper Address?

The success of deep neural networks, particularly large Transformer models, has led to massive parameter counts. While these dense models are powerful, their inference cost (computational operations) is becoming prohibitively expensive. Sparsely activated networks offer a solution by only engaging a subset of network parameters for each input, inspired by architectures like Mixture-of-Experts (MoE). However, existing work on these sparse models is largely empirical, lacking theoretical guarantees on their approximation capabilities. This paper aims to bridge this gap by providing a theoretical explanation for the power of sparse networks and establishing their efficiency.

Methods

The authors introduce a formal model for Data-Dependent Sparse Models (DSM). This model captures the essence of sparse networks where the activated subset of neurons and their weights depend on the input. A key contribution is the introduction of a Locality Sensitive Hashing (LSH) based routing function. LSH is a technique that maps similar inputs to the same "bucket," which the authors leverage to theoretically analyze how well sparse networks can approximate target functions. They demonstrate that their DSM model can simulate popular sparse architectures like Switch and Scaling Transformers. They also prove theoretical bounds showing that LSH-based sparse networks can approximate Lipschitz functions with the same accuracy as dense networks but with significantly fewer computational operations (FLOPs) during inference.

Datasets

The paper uses synthetic datasets generated from:

  • Random polynomial functions: These are constructed to be L-Lipschitz.
  • Random hypercube functions: These are also L-Lipschitz.
  • CIFAR-10: A real-world image classification dataset.

The synthetic datasets are designed to align with the theoretical analysis of Lipschitz functions and to evaluate the performance of different routing mechanisms.

Key Insights and Ideas

  • Theoretical grounding for sparsity: The paper moves beyond empirical observations to provide a formal theoretical explanation for the effectiveness of sparse networks.
  • LSH as a powerful routing mechanism: Locality Sensitive Hashing provides a principled way to route inputs to experts in a sparse network, enabling theoretical analysis of approximation capabilities.
  • Efficiency gains are exponential: The theoretical results show that for Lipschitz functions, sparse networks offer an exponential advantage in inference time compared to dense networks, while maintaining comparable approximation quality.
  • Data-dependent sparsity is key: The authors emphasize that the "data-dependent" nature of the routing function is crucial for achieving these theoretical guarantees, allowing the network to adapt its sparsity pattern to the input.

Key Results

  • Approximation Power: The paper proves that LSH-based sparse networks can approximate L-Lipschitz functions on k-dimensional manifolds with an error of $\epsilon$, matching the approximation power of dense networks.
  • Inference Efficiency: Theoretical bounds show that sparse networks achieve this approximation with inference times of $O(dk \log(1/\epsilon))$, while dense networks require $\Omega(d \cdot (\frac{\sqrt{d}}{\epsilon})^k)$ time. This is an exponential difference.
  • Experimental Validation: Experiments on synthetic Lipschitz functions and CIFAR-10 demonstrate that DSM and LSH models outperform dense models with the same number of activated units. They also show that data-dependent sparse mechanisms (DSM/LSH) are superior to random hash-based sparsity.
  • Table 1 Example: A dense model with 73k FLOPs achieved an MSE of 0.01046, while a DSM model with only 18k FLOPs achieved a lower MSE of 0.006115.

Limitations and Future Work

  • Focus on Lipschitz Functions: The theoretical guarantees are primarily for L-Lipschitz functions. Extending these results to broader classes of functions would be valuable.
  • Small-scale Experiments: The experiments were conducted on relatively small datasets and networks to align with theoretical analysis. Evaluating DSM and LSH models on larger, real-world tasks (like large-scale NLP and vision transformers) is a natural next step.
  • Interpolation within Buckets: The paper suggests exploring better ways to interpolate within each LSH bucket, potentially using higher-degree polynomials.
  • Dense vs. Sparse Power: A fundamental question remains whether dense models are inherently more powerful than sparse models with the same total number of parameters. The current work focuses on efficiency, not necessarily expressiveness equivalence for all function classes.
  • Hyperparameter Sensitivity: The authors note that their experiments used a limited set of hyperparameter settings, and a more exhaustive search might reveal different relative behaviors.

Summary updated

Abstract

Deep and wide neural networks successfully fit very complex functions today, but dense models are starting to be prohibitively expensive for inference. To mitigate this, one promising direction is networks that activate a sparse subgraph of the network. The subgraph is chosen by a data-dependent routing function, enforcing a fixed mapping of inputs to subnetworks (e.g., the Mixture of Experts (MoE) paradigm in Switch Transformers). However, prior work is largely empirical, and while existing routing functions work well in practice, they do not lead to theoretical guarantees on approximation ability. We aim to provide a theoretical explanation for the power of sparse networks. As our first contribution, we present a formal model of data-dependent sparse networks that captures salient aspects of popular architectures. We then introduce a routing function based on locality sensitive hashing (LSH) that enables us to reason about how well sparse networks approximate target functions. After representing LSH-based sparse networks with our model, we prove that sparse networks can match the approximation power of dense networks on Lipschitz functions. Applying LSH on the input vectors means that the experts interpolate the target function in different subregions of the input space. To support our theory, we define various datasets based on Lipschitz target functions, and we show that sparse networks give a favorable trade-off between number of active units and approximation quality.
BibTeX
@inproceedings{baykal2022theoretical,
  author = {Cenk Baykal and Nishanth Dikkala and Rina Panigrahy and Cyrus Rashtchian and Xin Wang},
  title = {{A Theoretical View on Sparsely Activated Networks}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=AODVskSug8},
}
Figure