# Combinatorial optimization for low bit-width neural networks

arXiv: https://arxiv.org/abs/2206.02006 · HTML: https://mlsanity.com/paper/2206.02006/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 23 references that are in the map.
- First posted on arXiv 4 Jun 2022.

## Builds on (most cited first, 11 of 11)

- [Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classification](https://mlsanity.com/paper/1502.01852/) (2015)
- [XNOR-Net: ImageNet Classification Using Binary Convolutional Neural Networks](https://mlsanity.com/paper/1603.05279/) (2016)
- [BinaryConnect: Training Deep Neural Networks with binary weights during propagations](https://mlsanity.com/paper/1511.00363/) (2015)
- [Ternary Weight Networks](https://mlsanity.com/paper/1605.04711/) (2016)
- [Binary Neural Networks: A Survey](https://mlsanity.com/paper/2004.03333/) (2020)
- [Deep Learning with Low Precision by Half-wave Gaussian Quantization](https://mlsanity.com/paper/1702.00953/) (2017)
- [Greedy Layerwise Learning Can Scale to ImageNet](https://mlsanity.com/paper/1812.11446/) (2018)
- [R-GAP: Recursive Gradient Attack on Privacy](https://mlsanity.com/paper/2010.07733/) (2020)
- [Regularizing Activation Distribution for Training Binarized Deep Networks](https://mlsanity.com/paper/1904.02823/) (2019)
- [Neural Networks with Few Multiplications](https://mlsanity.com/paper/1510.03009/) (2015)
- [Submodularity in Action: From Machine Learning to Signal Processing Applications](https://mlsanity.com/paper/2006.09905/) (2020)

## Abstract (arXiv)

Low-bit width neural networks have been extensively explored for deployment on edge devices to reduce computational resources. Existing approaches have focused on gradient-based optimization in a two-stage train-and-compress setting or as a combined optimization where gradients are quantized during training. Such schemes require high-performance hardware during the training phase and usually store an equivalent number of full-precision weights apart from the quantized weights. In this paper, we explore methods of direct combinatorial optimization in the problem of risk minimization with binary weights, which can be made equivalent to a non-monotone submodular maximization under certain conditions. We employ an approximation algorithm for the cases with single and multilayer neural networks. For linear models, it has O(nd) time complexity where n is the sample size and d is the data dimension. We show that a combination of greedy coordinate descent and this novel approach can attain competitive accuracy on binary classification tasks.