CBP: backpropagation with constraint on weight precision using a pseudo-Lagrange multiplier method

Guhyun Kim, Doo Seok JeongNeurIPS 2021

Introduction

Constrained Backpropagation (CBP) introduces a principled way to train low-precision neural networks by incorporating weight constraints directly into the objective function. Using a "pseudo-Lagrange multiplier" method combined with a clever "vanishing window" technique to quantize weights gradually, CBP achieves state-of-the-art accuracy on ImageNet. Remarkably, it often comes within striking distance of full-precision models while relying entirely on binary or ternary weights.

The Problem with Standard Quantization

Modern Deep Neural Networks (DNNs) are notoriously memory-intensive. To deploy them on edge devices or specialized hardware, researchers often "quantize" weights—reducing them from 32-bit floating-point numbers to binary (-1, 1), ternary (-1, 0, 1), or power-of-two "shift" values.

The primary challenge is that standard backpropagation is designed for continuous spaces. Discrete constraints (e.g., "this weight must be exactly 1 or -1") are mathematically non-differentiable. Most existing methods rely on the Straight-Through Estimator (STE), which essentially ignores the quantization during the backward pass and hopes for the best. This disconnect often leads to significant accuracy drops because the optimization process isn't truly aware of the strict constraints it must ultimately satisfy.

The CBP Solution: Methods and Mechanics

The authors propose treating quantization not as an afterthought, but as a formal optimization problem with constraints.

  1. Pseudo-Lagrange Multiplier Method (LMM): They define a Lagrangian function $\mathcal{L} = \text{Loss} + \lambda \cdot \text{Constraint}$. While standard LMM requires differentiability, the authors introduce a "pseudo-LMM" to handle the non-differentiable points inherent in discrete weight sets.
  2. Sawtooth Constraint Functions: They design a specific "sawtooth" function that hits its minimum values exactly at the desired quantized points (e.g., -1, 0, 1). The further a weight strays from a valid quantized value, the higher the penalty added to the loss.
  3. The Vanishing Window ($ucs$): This is the algorithm's secret sauce. Instead of forcing all weights to quantize simultaneously, CBP uses an "unconstrained-weight window."
    • Weights inside the window are free to move and minimize the primary loss.
  4. Weights outside the window are pushed by the Lagrange multiplier toward the nearest quantized value.
  5. As training progresses, the window shrinks (parameterized by a variable $g$), gradually forcing all weights into their quantized slots. This allows the network to adapt to the loss of precision in some weights by adjusting others that are still free.
  6. Quasi-static Updates: To prevent the weights and the Lagrange multipliers ($\lambda$) from oscillating wildly, $\lambda$ is updated much less frequently than the weights.
Sawtooth constraint functions for binary and ternary weights, illustrating the shrinking Unconstrained-weight (UCS) window as parameter g increases from 2 to 10.

Key Insights

  • Optimization over Clipping: Unlike methods that simply clip or round weights at the end of a step, CBP treats the constraint as a continuous force acting on the weight throughout the entire training process.
  • Sequential Quantization: The vanishing window ($ucs$) acts as a brilliant heuristic. It effectively prioritizes quantizing the weights that "want" to be quantized (those already near a target value) while giving "undecided" weights more time to find an optimal position.
  • Mathematical Rigor: The authors provide a theoretical framework demonstrating that minimizing their Lagrangian is equivalent to solving the constrained optimization problem, offering a more solid foundation than traditional quantization hacks.
  • Framework Compatibility: Because it simply modifies the objective function, CBP is fully compatible with standard deep learning frameworks like PyTorch or TensorFlow.

Key Results

The algorithm was evaluated on the ImageNet (ILSVRC 2012) dataset across several classic architectures: AlexNet, ResNet-18, ResNet-50, and GoogLeNet. CBP consistently outperformed previous state-of-the-art (SOTA) methods like ADMM and BWN.

Top-1 and Top-5 accuracy comparison on ImageNet across various architectures and quantization levels.
  • ResNet-18 (Binary): Achieved 66.6% top-1 accuracy, significantly higher than the 64.8% achieved by the previous best (ADMM).
  • ResNet-50 (Binary): Reached 74.4% top-1 accuracy (vs. 68.7% for ADMM). For context, the full-precision version of this model is 76.0%, meaning CBP lost only 1.6% accuracy while drastically reducing the memory footprint.
  • Shift Weights: Using 2-bit shift weights (which are highly hardware-friendly as they replace multiplications with bit-shifts), ResNet-18 reached 69.6% accuracy—identical to the full-precision baseline.
  • GoogLeNet (Binary): Reached 64.0% top-1 accuracy, a nearly 4% jump over ADMM.

Limitations and Future Work

While highly effective, CBP does come with trade-offs:

  • Training Complexity: CBP introduces extra floating-point operations (FLOPs) during training to update the Lagrange multipliers. For AlexNet, this increased training complexity by about 25%, though for ResNets, the overhead was a negligible ~2%.
  • Hyperparameter Tuning: The method introduces new hyperparameters, such as the multiplier learning rate ($\eta_\lambda$) and the window growth schedule ($g$), which currently require manual searching.
  • Post-Training Focus: The paper primarily evaluates CBP as a "post-training" refinement method (starting from a pre-trained full-precision model). Its performance when training from scratch with random initialization is less explored.
  • Hardware Implementation: While the final weights are quantized, the training process itself still requires high-precision arithmetic. The true benefit of this method is realized only during the inference phase on specialized hardware.

Summary updated

BibTeX
@inproceedings{kim2021cbp,
  author = {Guhyun Kim and Doo Seok Jeong},
  title = {{CBP: backpropagation with constraint on weight precision using a pseudo-Lagrange multiplier method}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
}
Figure