TL;DR
This paper introduces Differentiable Approximation Bridges (DAB), a novel method for incorporating non-differentiable functions—like sorting, k-means, or binary thresholds—directly into neural network architectures. By training a small auxiliary "bridge" network to mimic these functions, the authors provide a smooth pathway for gradients during backpropagation, significantly outperforming existing techniques like the Straight-Through Estimator and Gumbel-Softmax.
What Problem Does This Paper Address?
Deep learning thrives on backpropagation, which requires every "layer" in a network to be differentiable (or at least sub-differentiable, like ReLU). This constraint excludes a massive library of useful, stable algorithms—think of traditional computer science tools like Merge-Sort, K-Means clustering, or simple discrete logic.
Existing workarounds have significant flaws. The Straight-Through Estimator (STE) simply "ignores" the non-differentiable part and copies gradients across it, but it fails if the function changes the data's dimensions. Relaxed Estimators (like Gumbel-Softmax) use continuous approximations that are slowly "hardened" over time, but these are often limited to specific probability distributions and can be tricky to tune. The authors wanted a general-purpose way to use any hard function as a layer without these constraints.
Methods
The core idea is the Differentiable Approximation Bridge (DAB). Instead of trying to find a mathematical derivative for a "hard" function ($l_{hard}$), the authors train a small, smooth neural network ($l_\phi$) to act as its twin.
- Forward Pass: The network uses the actual "hard" function (e.g., a real sorting algorithm) to compute the output. This ensures the model benefits from the exact discrete logic.
- Backward Pass: Gradients cannot flow through the hard function, so they are routed through the DAB network instead. Because the DAB is a standard neural network, it provides smooth, useful gradients to the layers below it.
- Joint Training: The DAB is trained alongside the main model. A regularizer (usually an L2 loss) forces the DAB's output to stay close to the hard function's output.
- Zero-Cost Inference: Once training is done, the DAB "bridge" is discarded. The final model uses the hard function directly, meaning there is no extra computational overhead during deployment.
Datasets
The authors conducted over 600 experiments across diverse domains:
- Neural Sequence Sorting: Synthetic sequences of varying lengths ($T=5, 10, 15$) to test combinatorial logic.
- Unsupervised Representation Learning: FashionMNIST, CIFAR10, and a high-resolution ImageNet (512x512) variant to test Variational Autoencoders (VAEs).
- Generative Modeling: Binarized MNIST and Binarized Omniglot for density estimation.
- Image Classification: CIFAR10 using a modified ResNet18.
Key Insights and Ideas
- Meaningful Signals > Exact Gradients: The "aha" moment is realizing that backpropagation doesn't need the perfect derivative; it just needs a "meaningful training signal" that points the weights in the right direction.
- Handling Dimension Changes: Unlike the Straight-Through Estimator, DAB can handle operations where the input and output sizes differ (e.g., a
top-koperation that reduces a vector's size). - Discrete Logic Simplifies Learning: Surprisingly, using "hard" discrete functions can make some tasks easier. In sorting, for example, using a
signumfunction to bin values into $\{-1, 0, 1\}$ allows the network to learn "swap" logic much more effectively than using continuous approximations liketanh. - Quantization as Regularization: Using discrete activations acts as a form of regularization, which the authors found improved the linear separability of latent spaces in VAEs.
Key Results
- Sorting Mastery: On sequence sorting, DAB achieved 99.3% accuracy on length-5 sequences. More impressively, on length-15 sequences where standard models collapsed to 4-10% accuracy, DAB maintained ~80% accuracy.
- Better VAEs: Compared to the popular Gumbel-Softmax, DAB improved image reconstruction quality and increased the linear separability of the latent space by 10%.
- State-of-the-Art Density Estimation: DAB outperformed the state-of-the-art RELAX and REBAR estimators on Binarized MNIST and Omniglot, achieving a better Variational Lower Bound (ELBO).
- Classification Boost: In image classification, DAB provided a 25% improvement over the Straight-Through Estimator when used in a dense model setting.
Limitations and Future Work
- Convergence Time: While DAB eventually reaches a better solution than competitors like REBAR, it currently takes significantly more epochs to converge.
- Hyperparameter Tuning: There is a new hyperparameter $\gamma$ that controls the strength of the DAB regularization. While the authors found it wasn't overly sensitive, it still adds one more knob to turn.
- Optimization: The authors suggest that adding a learning rate scheduler specifically for the DAB training could help bridge the convergence gap. Future work could also explore using DAB for even more complex non-differentiable modules like physics engines or discrete optimizers.
Summary updated