Deep Learning as a Mixed Convex-Combinatorial Optimization Problem
This addresses the challenge of training quantized or non-differentiable deep networks for applications requiring reduced computational costs, though it appears incremental as it builds upon existing methods like the straight-through estimator.
The paper tackles the problem of learning deep neural networks with hard-threshold activations, which are non-differentiable and thus incompatible with gradient descent, by reformulating it as a mixed convex-combinatorial optimization problem and developing a recursive mini-batch algorithm. The result shows improved classification accuracy compared to the straight-through estimator, with empirical validation on models like AlexNet and ResNet-18 on ImageNet.
As neural networks grow deeper and wider, learning networks with hard-threshold activations is becoming increasingly important, both for network quantization, which can drastically reduce time and energy requirements, and for creating large integrated systems of deep networks, which may have non-differentiable components and must avoid vanishing and exploding gradients for effective learning. However, since gradient descent is not applicable to hard-threshold functions, it is not clear how to learn networks of them in a principled way. We address this problem by observing that setting targets for hard-threshold hidden units in order to minimize loss is a discrete optimization problem, and can be solved as such. The discrete optimization goal is to find a set of targets such that each unit, including the output, has a linearly separable problem to solve. Given these targets, the network decomposes into individual perceptrons, which can then be learned with standard convex approaches. Based on this, we develop a recursive mini-batch algorithm for learning deep hard-threshold networks that includes the popular but poorly justified straight-through estimator as a special case. Empirically, we show that our algorithm improves classification accuracy in a number of settings, including for AlexNet and ResNet-18 on ImageNet, when compared to the straight-through estimator.