Training Deep Neural Networks with Constrained Learning Parameters

Prasanna Date, Christopher D. Carothers, John E. Mitchell, James A. Hendler, Malik Magdon-Ismail

TL;DR

This paper introduces CoNNTrA, a novel algorithm for training deep neural networks (DNNs) with parameters restricted to finite discrete values (like ternary). CoNNTrA achieves comparable accuracy to traditional backpropagation while drastically reducing memory usage by up to 32x, making it highly suitable for resource-constrained edge computing environments.

What Problem Does This Paper Address?

The paper tackles the growing challenge of deploying deep learning models on edge computing devices. While current DNNs achieve impressive accuracy, they are notoriously power-hungry and memory-intensive due to their use of double-precision floating-point parameters. This is unsustainable for the post-Moore's Law era, where edge devices will form a significant part of the computational fabric. The authors aim to create DNNs that are not only accurate but also have low memory and power footprints, essential for applications like IoT and autonomous vehicles.

Methods

The core contribution is the Combinatorial Neural Network Training Algorithm (CoNNTrA). CoNNTrA is a coordinate gradient descent-based approach designed to train DNNs with parameters constrained to a finite set of discrete values (e.g., binary {-1, +1} or ternary {-1, 0, +1}).

Key aspects of CoNNTrA include:

  • Discretization: A subroutine (Algorithm 1) that takes pretrained weights and maps them to the nearest discrete value.
  • Coordinate Gradient Descent: Instead of updating all weights simultaneously, CoNNTrA iteratively searches for the best discrete value for each weight individually, aiming to minimize the error function. This is a "global search" over the discrete values for each weight.
  • Polynomial Time Complexity: The algorithm is designed to have a polynomial time complexity, making it more feasible for practical deployment compared to computationally expensive evolutionary optimization methods.

The paper also proves that training binary neural networks with a Euclidean error function is NP-Hard, providing theoretical justification for the need for efficient algorithms like CoNNTrA.

Datasets

The authors evaluated CoNNTrA on several standard machine learning benchmark datasets:

  • MNIST: Used for both logistic regression and convolutional neural network (CNN) tasks.
  • Iris: Used for a deep neural network (DNN) task.
  • ImageNet: Used for a convolutional neural network (CNN) task.

Key Insights and Ideas

  • Discrete Parameters for Efficiency: Constraining learning parameters to finite discrete values (like ternary) is a direct and effective way to reduce memory requirements. A ternary parameter can be stored using just 2 bits, compared to 64 bits for a double-precision floating-point number.
  • CoNNTrA's Practicality: The proposed CoNNTrA algorithm offers a computationally efficient (polynomial time) method to train these memory-constrained models, making them viable for edge devices.
  • Trade-off Between Expressibility and Efficiency: While CoNNTrA achieves significant memory savings, the reduced expressibility of discrete parameters can lead to slightly higher training and validation errors compared to models using full-precision floating-point weights. However, the paper demonstrates these errors are often "at par" or very close.
  • NP-Hardness of Binary Training: The theoretical proof that binary neural network training is NP-Hard highlights the importance of developing specialized, efficient algorithms rather than relying on general-purpose optimization methods.

Key Results

The experimental evaluation across MNIST, Iris, and ImageNet datasets yielded compelling results:

  • Memory Reduction: CoNNTrA consistently achieved significant memory savings, with an average reduction of 32x compared to traditional Backpropagation models. For instance, on ImageNet, memory usage dropped from ~499 MB to ~15 MB.
  • Comparable Accuracy: The training and validation errors for CoNNTrA models were generally "at par" with or very close to those achieved by Backpropagation. For example, on MNIST CNN, training error was 2.60% vs. 1.40% for Backprop, and validation error was 2.39% vs. 1.56%.
  • Training Time: CoNNTrA generally took longer to train than Backpropagation. The authors attribute this to their "serialized implementation" and state that parallel implementations are expected to significantly reduce training times. For example, ImageNet training took ~647k seconds for CoNNTrA versus ~388k seconds for Backpropagation.

Limitations and Future Work

  • Training Time: The current serialized implementation of CoNNTrA leads to longer training times compared to Backpropagation.
  • Slightly Higher Errors: The reduced expressibility of discrete parameters can result in slightly higher errors compared to full-precision models, although the paper emphasizes these are often comparable.

The authors propose several avenues for future work:

  • Parallel Implementation: Developing an efficient parallelized version of CoNNTrA to drastically improve training times.
  • Broader Applicability: Investigating CoNNTrA's use for other NP-complete problems beyond neural network training, such as the traveling salesman problem, protein folding, and genetic imputation.
  • Neuromorphic Systems: Further exploring the combination of CoNNTrA with neuromorphic computing systems to achieve even greater energy efficiency and robustness.

Summary updated

Abstract

Today's deep learning models are primarily trained on CPUs and GPUs. Although these models tend to have low error, they consume high power and utilize large amount of memory owing to double precision floating point learning parameters. Beyond the Moore's law, a significant portion of deep learning tasks would run on edge computing systems, which will form an indispensable part of the entire computation fabric. Subsequently, training deep learning models for such systems will have to be tailored and adopted to generate models that have the following desirable characteristics: low error, low memory, and low power. We believe that deep neural networks (DNNs), where learning parameters are constrained to have a set of finite discrete values, running on neuromorphic computing systems would be instrumental for intelligent edge computing systems having these desirable characteristics. To this extent, we propose the Combinatorial Neural Network Training Algorithm (CoNNTrA), that leverages a coordinate gradient descent-based approach for training deep learning models with finite discrete learning parameters. Next, we elaborate on the theoretical underpinnings and evaluate the computational complexity of CoNNTrA. As a proof of concept, we use CoNNTrA to train deep learning models with ternary learning parameters on the MNIST, Iris and ImageNet data sets and compare their performance to the same models trained using Backpropagation. We use following performance metrics for the comparison: (i) Training error; (ii) Validation error; (iii) Memory usage; and (iv) Training time. Our results indicate that CoNNTrA models use 32x less memory and have errors at par with the Backpropagation models.
BibTeX
@inproceedings{date2020training,
  author = {Prasanna Date and Christopher D. Carothers and John E. Mitchell and James A. Hendler and Malik Magdon-Ismail},
  title = {{Training Deep Neural Networks with Constrained Learning Parameters}},
  booktitle = {Icrc},
  year = {2020},
  doi = {10.1109/icrc2020.2020.00018},
}
Figure