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

Halyun Jeong Jack Xin Penghang Yin · 2025

Read Beyond Discreteness: Sample Complexity Analysis of Straight-Through Estimator for 1-bit Quantization by Halyun Jeong Jack Xin Penghang Yin (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-18113.txt.

Introduction

Halyun Jeong, Jack Xin, and Penghang Yin study a training trick in this 2025 paper on small neural networks. The trick, called the straight-through estimator, lets a network learn even though its weights are cut down to just one bit, a step that saves size and power.

Earlier work on the trick assumed endless training data. The authors instead ask how much data is enough, and they derive bounds tied to the size of the data itself. With noisy labels, they show the method can drift away from the best weights and then return to them. Tests also show the trick can fail on some data unless the data is first put on a common scale.

Catalog record

CREATORHalyun Jeong Jack Xin Penghang Yin
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE133 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-18113

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Beyond Discreteness: Sample Complexity Analysis of Straight-Through Estimator for 1-bit Quantization Halyun Jeong Jack Xin Penghang Yin Abstract 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. Keywords. quantization, straight-through estimator, 1-bit compressed sensing MSC codes. 68T07, 68Q32, 90C26, 94A12 1 Introduction Deep neural networks (DNNs) have revolutionized machine learning, achieving remarkable success across various domains, including computer vision [ 17 , 26 ] , reinforcement learning [ 35 , 50 ] , and natural language processing [ 51 ] . However, state-of-the-art DNNs often contain billions of parameters, requiring substantial computational power and memory. The high resource consumption at inference time poses significant challenges for deploying these models on resource-constrained devices, such as smartphones, embedded systems, and Internet-of-Things (IoT) devices. To address this challenge, network quantization has emerged as a well-adopted and robust solution, aiming to reduce the precision of weights and activations while preserving model performance. Quantized DNNs operate using low-precision arithmetic rather than standard full-precision floating-point representations, significantly reducing memory footprint and computational cost. This compression technique enables real-time inference on energy-efficient specialized accelerators [ 43 , 55 ] . Training quantized neural networks, also known as quantization-aware training (QAT) [ 2 , 7 , 10 , 20 , 43 , 61 ] , poses significant mathematical challenges due to the discrete nature of low-precision weights and activations, which prohibits the direct use of standard backpropagation. A widely adopted approach to address this challenge is the straight-through estimator (STE) [ 5 ] , which enables gradient-like optimization by using fake gradients for piecewise constant objectives. In essence, STE is an informative heuristic that replaces the almost-everywhere zero derivative of discrete components (e.g., quantized activation function) exclusively during the backward pass , yielding an unconventional yet practical "gradient" by modifying the chain rule. STE has played a pivotal role in quantization methods, making it possible to train low-bitwidth neural networks efficiently. Additionally, STE has been extensively used to handle the minimization of discrete-valued objectives that arise in machine learning such as neural architecture search [ 44 , 49 ] , discrete latent variables [ 23 , 27 , 38 ] , adversarial attack [ 3 ] , and sparse recovery [ 36 ] , among others [ 33 , 54 , 57 , 58 ] . However, despite its empirical success, STE remains an informal heuristic with limited theoretical justification, leading to potential optimization instability and performance degradation. The main challenge in analyzing STE arises from the absence of a valid gradient of the discrete-valued sample loss l(\boldsymbol{w};\boldsymbol{z}) , where \boldsymbol{w} represents the model parameters and \boldsymbol{z} is a sample. The theoretical foundations of STE have primarily been studied in the context of neural network quantization [ 29 , 61 , 60 ] . In particular, [ 60 ] was among the first to provide a rigorous analysis of STE for activation quantization. While subsequent studies have explored alternative quantization settings, these analyses focus on minimizing the population loss: \min_{\boldsymbol{w}}\,\mathbb{E}_{\boldsymbol{z}}[l(\boldsymbol{w};\boldsymbol{z})] , over the data distribution—an assumption that unrealistically presumes access to infinitely many samples [ 31 , 32 , 56 ] . Under such an assumption, \mathbb{E}_{\boldsymbol{z}}[l(\boldsymbol{w};\boldsymbol{z})] is differentiable with a valid gradient almost everywhere (a.e.), which enables the analysis of the correlation between the gradient of the population loss \nabla_{\boldsymbol{w}}\mathbb{E}_{\boldsymbol{z}}[l(\boldsymbol{w};\boldsymbol{z})] and the STE gradient \tilde{\nabla}_{\boldsymbol{w}}l(\boldsymbol{w};\boldsymbol{z}) (also referred to as the coarse gradient [ 60 , 62 ] ). Here \tilde{\nabla}_{\boldsymbol{w}} denotes the unconventional STE gradient operator, intended to be distinguished from the standard gradient \nabla_{\boldsymbol{w}} . Notably, [ 60 ] provides convergence insights and demonstrates that, when STE is properly chosen, the expectation of STE gradient \mathbb{E}_{\boldsymbol{z}}[\tilde{\nabla}_{\boldsymbol{w}}l(\boldsymbol{w};\boldsymbol{z})] , despite being biased , maintains a positive correlation with the population gradient \nabla_{\boldsymbol{w}}\mathbb{E}_{\boldsymbol{z}}[l(\boldsymbol{w};\boldsymbol{z})] , thereby ensuring a descent property of the STE gradient method for activation-only quantization. With finitely many samples, however, analyzing the empirical risk minimization: \min_{\boldsymbol{w}}\frac{1}{N}\sum_{i=1}^{N}l(\boldsymbol{w};\boldsymbol{z}_{i}) , becomes dramatically more challenging, as the empirical loss gradient is a.e. zero. In this setting, a rigorous sample complexity analysis is essential to establish the effectiveness of STE-based optimization. Moreover, existing works typically consider either weight-only [ 1 , 12 , 24 , 30 ] or activation-only quantization [ 31 , 60 ] . The analysis appears to be even more intricate when both weights and activations are quantized, as it involves the use of dual STEs. 1.1 Contributions In this paper, we present the theoretical analysis of the straight-through estimator (STE) for quantization-aware training, addressing an optimization problem that is discrete in both its objective and constraint. Specifically, our main contributions are summarized as follows: • We provide the first analysis of the sample complexity that guarantees the effectiveness of STE. For training a two-layer binarized neural net with random Gaussian inputs, we show that O(n^{2}) samples suffice for convergence of the ergodic (averaged) iterates to the optimal solution, while O(n^{4}) samples are sufficient for the non-ergodic (last iterate) convergence, where n is the dimension of data. Moreover, we empirically validate that our O(n^{2}) bound for the ergodic convergence case is tight. • For the non-ergodic convergence analysis, we discover a surprising recurrence behavior of the STE gradient algorithm in the presence of label noise: the iterates repeatedly hit exactly and escape from the optimal binary weights. This stands in contrast to classical problems like linear regression and compressed sensing, where exact recovery of the underlying parameters is typically impossible under observation noise. • We empirically show that convergence guarantees fail to hold for general sub-Gaussian distributions. Nevertheless, we demonstrate that applying a normalization procedure can improve the performance of STE when the data deviate from normality, underscoring the practical importance of normalization in the effective use of STE. • To support the analysis, we leverage techniques from the context of 1-bit compressed sensing [ 15 ] , revealing important connections between these two domains. Additionally, we introduce a novel application of occupation time analysis, a tool traditionally used in dynamical systems, to rigorously analyze the drift dynamics of the iterates. Notations. We clarify the mathematical notations that will be

Read the complete text