# Beyond Discreteness: Sample Complexity Analysis of Straight-Through Estimator for 1-bit Quantization

arXiv: https://arxiv.org/abs/2505.18113 · HTML: https://mlsanity.com/paper/2505.18113/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 37 of its 62 references that are in the map.
- First posted on arXiv 23 May 2025.

## Builds on (most cited first, 30 of 37)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift](https://mlsanity.com/paper/1502.03167/) (2015)
- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [Categorical Reparameterization with Gumbel-Softmax](https://mlsanity.com/paper/1611.01144/) (2016)
- [Estimating or Propagating Gradients Through Stochastic Neurons for Conditional Computation](https://mlsanity.com/paper/1308.3432/) (2013)
- [Obfuscated Gradients Give a False Sense of Security: Circumventing Defenses to Adversarial Examples](https://mlsanity.com/paper/1802.00420/) (2018)
- [XNOR-Net: ImageNet Classification Using Binary Convolutional Neural Networks](https://mlsanity.com/paper/1603.05279/) (2016)
- [PACT: Parameterized Clipping Activation for Quantized Neural Networks](https://mlsanity.com/paper/1805.06085/) (2018)
- [Quantized Neural Networks: Training Neural Networks with Low Precision Weights and Activations](https://mlsanity.com/paper/1609.07061/) (2016)
- [Understanding Straight-Through Estimator in Training Activation Quantized Neural Nets](https://mlsanity.com/paper/1903.05662/) (2019)
- [Training Deep Neural Networks with 8-bit Floating Point Numbers](https://mlsanity.com/paper/1812.08011/) (2018)
- [Overcoming Oscillations in Quantization-Aware Training](https://mlsanity.com/paper/2203.11086/) (2022)
- [Deep Learning with Low Precision by Half-wave Gaussian Quantization](https://mlsanity.com/paper/1702.00953/) (2017)
- [Training Quantized Nets: A Deeper Understanding](https://mlsanity.com/paper/1706.02379/) (2017)
- [Neural Network Approximation: Three Hidden Layers Are Enough](https://mlsanity.com/paper/2010.14075/) (2020)
- [Universal Approximation of Functions on Sets](https://mlsanity.com/paper/2107.01959/) (2021)
- [Rao-Blackwellizing the Straight-Through Gumbel-Softmax Gradient Estimator](https://mlsanity.com/paper/2010.04838/) (2020)
- [Learning strides in convolutional neural networks](https://mlsanity.com/paper/2202.01653/) (2022)
- [Relation Embedding with Dihedral Group in Knowledge Graph](https://mlsanity.com/paper/1906.00687/) (2019)
- [BinaryRelax: A Relaxation Approach For Training Deep Neural Networks With Quantized Weights](https://mlsanity.com/paper/1801.06313/) (2018)
- [BinaryDuo: Reducing Gradient Mismatch in Binary Activation Network by Coupling Binary Activations](https://mlsanity.com/paper/2002.06517/) (2020)
- [Enhance the Visual Representation via Discrete Adversarial Training](https://mlsanity.com/paper/2209.07735/) (2022)
- [Blended Coarse Gradient Descent for Full Quantization of Deep Neural Networks](https://mlsanity.com/paper/1808.05240/) (2018)
- [Mirror Descent View for Neural Network Quantization](https://mlsanity.com/paper/1910.08237/) (2019)
- [Injecting Logical Constraints into Neural Networks via Straight-Through Estimators](https://mlsanity.com/paper/2307.04347/) (2023)
- [Demystifying and Generalizing BinaryConnect](https://mlsanity.com/paper/2110.13220/) (2021)
- [Single-Path Mobile AutoML: Efficient ConvNet Design and NAS Hyperparameter Optimization](https://mlsanity.com/paper/1907.00959/) (2019)
- [Binary Iterative Hard Thresholding Converges with Optimal Number of Measurements for 1-Bit Compressed Sensing](https://mlsanity.com/paper/2207.03427/) (2022)
- [Learning Quantized Neural Nets by Coarse Gradient Method for Non-linear Classification](https://mlsanity.com/paper/2011.11256/) (2020)

## Built on by (most cited first, 2 of 2)

- [Training Non-Differentiable Networks via Optimal Transport](https://mlsanity.com/paper/2605.01928/) (2026)
- [Stability and Generalization of Straight-Through Estimators for Training Two-Layer Quantized Neural Networks](https://mlsanity.com/paper/2609.06430/) (2026)

## Abstract (arXiv)

Training quantized neural networks requires addressing the non-differentiable and discrete nature of the underlying optimization problem. To tackle this challenge, the straight-through estimator (STE) has become the most widely adopted heuristic, allowing backpropagation through discrete operations by introducing biased yet valid surrogate gradients. However, its theoretical properties remain largely unexplored, with few existing analyses focus on the generalization error by assuming an infinite amount of training data. In contrast, this work presents the first sample complexity analysis of STE in the context of neural network quantization. Our theoretical results highlight the critical role of sample size in the success of STE, a key insight absent from existing studies. Specifically, by analyzing the quantization-aware training of a two-layer neural network with binary weights and activations, we derive the sample complexity bounds in terms of the data dimensionality that guarantee the convergence of STE-based optimization to the global minimum for both ergodic and non-ergodic analyses. Moreover, in the presence of label noises, we prove an intriguing recurrence property of STE-gradient method, where the iterate repeatedly escape from and return to the optimal binary weights. Finally, we empirically demonstrate that STE fails for general non-Gaussian data but its effectiveness can be restored through normalization, underscoring its practical importance in effective quantization.