Learning Discrete Binary Representations with Gradient Descent

55 concepts56 papers1 proposal

To search through billions of images, documents, or graph nodes in milliseconds, modern retrieval systems rely on binary hashing. By compressing high-dimensional data vectors into compact strings of bits (such as $-1$ and $+1$), systems can compute similarities using lightning-fast bitwise XOR operations.

However, training a deep neural network to output these discrete binary codes presents a fundamental mathematical paradox. Deep learning relies on gradient descent, which requires a smooth, continuous landscape to calculate vectors of direction (gradients). Binary quantization requires a step function—like the $\text{sign}(x)$ operator—which is flat almost everywhere. Because the derivative of a flat line is zero, backpropagation grinds to a halt: the network receives no feedback on how to adjust its weights to improve the generated codes.

To bypass this non-differentiable bottleneck, researchers have developed three core strategies: decoupling the optimization, smoothing the discrete landscape stochastically, and enforcing structural consensus through generative modeling.

The Cost of Continuous Relaxation

The simplest workaround to the binary bottleneck is continuous relaxation. Instead of forcing the network to output hard bits during training, researchers often substitute the step function with a smooth approximation, such as the hyperbolic tangent ($\tanh$) function. As training progresses, the scaling factor of the function is increased to push the outputs closer to $-1$ and $+1$.

While mathematically convenient, this approach suffers from a severe flaw known as quantization error or metric mismatch. During training, the network optimizes its weights based on continuous values (e.g., $0.9$ and $-0.75$). But at inference time, these values are abruptly thresholded into hard bits ($+1$ and $-1$). As noted by Qi Li et al. in their work on Deep Supervised Discrete Hashing (neurips 2017), this sudden transformation alters the geometric relationships learned by the model, causing a catastrophic drop in retrieval accuracy. The network optimizes for a smooth space that it never actually uses at deployment.

Strategy 1: Decoupling via Discrete Optimization

Rather than forcing gradients through a non-differentiable function, one prominent strategy completely decouples the continuous feature learning from the discrete code generation.

In Supervised Discrete Hashing (cvpr 2015), Chunhua Shen et al. bypassed continuous relaxation by introducing a Discrete Cyclic Coordinate Descent (DCC) algorithm. Instead of updating all binary bits simultaneously via gradients, DCC optimizes the target binary codes bit-by-bit. By holding all bits constant except one, the problem reduces to a simple linear sub-problem that can be solved analytically in closed form. Once the optimal discrete codes are established, they serve as static targets to train the continuous layers of the network.

A parallel approach handles deep architectures by breaking the network into independent, layer-wise updates. Ziming Zhang et al. developed Very Deep Supervised Hashing (cvpr 2016), which replaces standard backpropagation with an optimization strategy inspired by the Alternating Direction Method of Multipliers (ADMM). By introducing auxiliary continuous variables that act as proxies for the binary constraints, the authors split the training objective into alternating steps: a standard continuous optimization step for the weights, and a discrete thresholding step for the outputs. This prevents zero-gradients from propagating backward through the network.

Decoupled Optimization (ADMM / DCC):
[Continuous Layers] ---> [Auxiliary Continuous Proxy] ---> [Hard Binary Code]
         |                             ^
         |-- (Continuous Gradient) ----|-- (Analytical Discrete Update)

Strategy 2: Stochastic Smoothing and Policy Gradients

Another way to restore gradient flow is to redefine the deterministic step function as a probabilistic process. If a network outputs a continuous value $x$, we can treat that value not as a direct coordinate, but as the parameter of a probability distribution over bits.

Vinith Misra applied this intuition to graph representations in Bernoulli Embeddings for Graphs (aaai 2018). By treating each bit in a node's embedding as a stochastic "coin flip" governed by a Bernoulli distribution, the author transformed an NP-hard discrete optimization problem into a smooth, differentiable expected value problem. Using a Central Limit Theorem approximation, the gradients can flow directly through the parameters of the distribution, allowing the model to learn optimal binary codes without ever calculating a derivative for a hard threshold.

Alternatively, the choice to flip a bit can be framed as an action in a reinforcement learning environment. In Relaxation-Free Deep Hashing via Policy Gradient (eccv 2018), Xin Yuan et al. introduced a framework (PGDH) that treats the neural network as a stochastic policy. The network outputs the probability of a bit being $+1$ or $-1$. Discrete binary codes are sampled from this policy, and their retrieval performance is evaluated against a ranking loss function. This evaluation returns a scalar reward, which is then used via Policy Gradients to update the network.

Because the gradient is calculated relative to the probability of taking an action rather than the discrete action itself, the non-differentiable bottleneck disappears entirely.

Stochastic Policy Gradient (PGDH):
[Continuous Output (x)] ---> [Probability P(bit=1)] ---> Sample ---> [Discrete Bit]
          ^                                                               |
          |------------------ Policy Gradient (Reward) -------------------|

To further refine direct gradient estimation, Fangyuan Luo et al. proposed the Approximation-Adjustable Gradient Estimator (AAGE). AAGE dynamically scales the gradient signal during backpropagation, correcting the coarse or misleading updates typical of standard straight-through estimators and ensuring that the continuous weights align tightly with the final discrete retrieval objective.

Strategy 3: Preserving Topology via Structural Consensus

A third paradigm focuses on ensuring that the geometric structure of the high-dimensional data is preserved when compressed into the discrete Hamming space. If two items are close neighbors in the continuous space, they must remain close neighbors in the binary space.

Maciej Zieba addressed this in BinGAN (neurips 2018) by incorporating a Generative Adversarial Network. BinGAN forces a decoder network to reconstruct original images directly from a compact, binarized bottleneck layer. By regularizing the network to maximize the mutual information between the continuous intermediate representations and the final discrete codes, the model "distills" complex semantic structures into a binary format, ensuring that no critical data is lost during thresholding.

BinGAN Architecture:
[Input Image] ---> [Continuous Features] ---> [Binary Bottleneck] ---> [Decoded Image]
                         |                                                 ^
                         |--------- Mutual Information Regularization -----|

Similarly, Fan Wang et al. leveraged Normalizing Flows in HCFRec (ijcai 2022) to enforce what they term structural consensus. Normalizing flows apply a sequence of invertible, differentiable mappings to transform a complex continuous latent distribution into a highly structured space designed for quantization. By optimizing this flow to maintain neighborhood topologies, the authors ensured that the subsequent non-differentiable mapping to binary hash codes preserves user-item relationships perfectly, achieving massive storage compression without sacrificing recommendation accuracy.

Key Foundational Work

Bit-Scalable Deep Hashing with Regularized Similarity Learning for Image Retrieval and Person Re-identification (2015) — contributed 1 concept elements to this direction.
Adaptive Hashing for Fast Similarity Search (2015) — contributed 1 concept elements to this direction.
Top Rank Supervised Binary Coding for Visual Search (2015) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_non_differentiable_binary_mapping_ff566727,
  title = {non-differentiable binary mapping},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/non-differentiable-binary-mapping/rdr_ff56672730a145cb8155b426890b2d7b},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_non_differentiable_binary_mapping_ff566727_v1,
  title = {non-differentiable binary mapping},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/non-differentiable-binary-mapping/rdr_ff56672730a145cb8155b426890b2d7b/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake