Taming Binarized Neural Networks and Mixed-Integer Programs

Abstract

There has been a great deal of recent interest in binarized neural networks, especially because of their explainability. At the same time, automatic differentiation algorithms such as backpropagation fail for binarized neural networks, which limits their applicability. By reformulating the problem of training binarized neural networks as a subadditive dual of a mixed-integer program, we show that binarized neural networks admit a tame representation. This, in turn, makes it possible to use the framework of Bolte et al. for implicit differentiation, which offers the possibility for practical implementation of backpropagation in the context of binarized neural networks. This approach could also be used for a broader class of mixed-integer programs, beyond the training of binarized neural networks, as encountered in symbolic approaches to AI and beyond.

arXiv comment9 pages, 4 figures

References in corpus (18)

• Binarized Neural Networks: Training Deep Neural Networks with Weights and Activations Constrained to +1 or -1
• Estimating or Propagating Gradients Through Stochastic Neurons for Conditional Computation
• BinaryConnect: Training Deep Neural Networks with binary weights during propagations
• DoReFa-Net: Training Low Bitwidth Convolutional Neural Networks with Low Bitwidth Gradients
• Towards Accurate Binary Convolutional Neural Network
• A comprehensive review of Binary Neural Network
• Understanding Straight-Through Estimator in Training Activation Quantized Neural Nets
• Locally o-minimal structures with tame topological properties
• Nonsmooth Implicit Differentiation for Machine Learning and Optimization
• An Integer Programming Approach to Deep Neural Networks with Binary Activation Functions
• A study of rank-one sets with linear side constraints and application to the pooling problem
• On Subadditive Duality for Conic Mixed-Integer Programs
• Integer Programming for Causal Structure Learning in the Presence of Latent Variables
• Symbolic Regression using Mixed-Integer Nonlinear Optimization
• Global convergence of the gradient method for functions definable in o-minimal structures
• Polynomial Matrix Inequalities within Tame Geometry
• Improving the Validity of Decision Trees as Explanations
• Piecewise Polynomial Regression of Tame Functions via Integer Programming