Beyond Discreteness: Finite-Sample Analysis of Straight-Through Estimator for Quantization

• URL: http://arxiv.org/abs/2505.18113v1
• Date: Fri, 23 May 2025 17:11:22 GMT
• Title: Beyond Discreteness: Finite-Sample Analysis of Straight-Through Estimator for Quantization
• Authors: Halyun Jeong, Jack Xin, Penghang Yin,
• Abstract summary: This work presents the first finite-sample analysis of the straight-through estimator (STE) in the context of neural network quantization.<n>Specifically, by analyzing the quantization-aware training of a two-layer neural network with binary weights and activations, we derive the sample complexity bound in terms of the data dimensionality.<n>In the presence of label noises, we uncover an intriguing recurrence property of STE-gradient method, where the iterate repeatedly escape from and return to the optimal binary weights.
• Score: 2.8948274245812327
• License: http://creativecommons.org/licenses/by/4.0/
• 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 surrogate gradients. However, its theoretical properties remain largely unexplored, with few existing works simplifying the analysis by assuming an infinite amount of training data. In contrast, this work presents the first finite-sample 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 bound in terms of the data dimensionality that guarantees the convergence of STE-based optimization to the global minimum. Moreover, in the presence of label noises, we uncover an intriguing recurrence property of STE-gradient method, where the iterate repeatedly escape from and return to the optimal binary weights. Our analysis leverages tools from compressed sensing and dynamical systems theory.

Related papers

• Statistically guided deep learning [10.619901778151336]
  We present a theoretically well-founded deep learning algorithm for nonparametric regression.<n>We show that a theoretical analysis of deep learning which takes into account simultaneously optimization, generalization and approximation can result in a new deep learning estimate.
  arXiv  Detail & Related papers  (2025-04-11T12:36:06Z)
• On the Dynamics Under the Unhinged Loss and Beyond [104.49565602940699]
  We introduce the unhinged loss, a concise loss function, that offers more mathematical opportunities to analyze closed-form dynamics. The unhinged loss allows for considering more practical techniques, such as time-vary learning rates and feature normalization.
  arXiv  Detail & Related papers  (2023-12-13T02:11:07Z)
• Understanding Multi-phase Optimization Dynamics and Rich Nonlinear Behaviors of ReLU Networks [8.180184504355571]
  We conduct a theoretical characterization of the training process of two-layer ReLU network trained by Gradient Flow on a linearlyparable data. We reveal four different phases from the whole training process showing a general simplifying-to-complicating learning trend. Specific nonlinear behaviors can also be precisely identified captured theoretically, such as initial, saddle-plateau dynamics, condensation escape, changes of activation patterns with increasing complexity.
  arXiv  Detail & Related papers  (2023-05-21T14:08:34Z)
• Joint Edge-Model Sparse Learning is Provably Efficient for Graph Neural Networks [89.28881869440433]
  This paper provides the first theoretical characterization of joint edge-model sparse learning for graph neural networks (GNNs) It proves analytically that both sampling important nodes and pruning neurons with the lowest-magnitude can reduce the sample complexity and improve convergence without compromising the test accuracy.
  arXiv  Detail & Related papers  (2023-02-06T16:54:20Z)
• Stability and Generalization Analysis of Gradient Methods for Shallow Neural Networks [59.142826407441106]
  We study the generalization behavior of shallow neural networks (SNNs) by leveraging the concept of algorithmic stability. We consider gradient descent (GD) and gradient descent (SGD) to train SNNs, for both of which we develop consistent excess bounds.
  arXiv  Detail & Related papers  (2022-09-19T18:48:00Z)
• How does unlabeled data improve generalization in self-training? A one-hidden-layer theoretical analysis [93.37576644429578]
  This work establishes the first theoretical analysis for the known iterative self-training paradigm. We prove the benefits of unlabeled data in both training convergence and generalization ability. Experiments from shallow neural networks to deep neural networks are also provided to justify the correctness of our established theoretical insights on self-training.
  arXiv  Detail & Related papers  (2022-01-21T02:16:52Z)
• Universal scaling laws in the gradient descent training of neural networks [10.508187462682308]
  We show that the learning trajectory can be characterized by an explicit bounds at large training times. Our results are based on spectral analysis of the evolution of a large network trained on the expected loss.
  arXiv  Detail & Related papers  (2021-05-02T16:46:38Z)
• Recurrence of Optimum for Training Weight and Activation Quantized Networks [4.103701929881022]
  Training deep learning models with low-precision weights and activations involves a demanding optimization task. We show how to overcome the nature of network quantization. We also show numerical evidence of the recurrence phenomenon of weight evolution in training quantized deep networks.
  arXiv  Detail & Related papers  (2020-12-10T09:14:43Z)
• Reintroducing Straight-Through Estimators as Principled Methods for Stochastic Binary Networks [85.94999581306827]
  Training neural networks with binary weights and activations is a challenging problem due to the lack of gradients and difficulty of optimization over discrete weights. Many successful experimental results have been achieved with empirical straight-through (ST) approaches. At the same time, ST methods can be truly derived as estimators in the binary network (SBN) model with Bernoulli weights.
  arXiv  Detail & Related papers  (2020-06-11T23:58:18Z)
• Multiplicative noise and heavy tails in stochastic optimization [62.993432503309485]
  empirical optimization is central to modern machine learning, but its role in its success is still unclear. We show that it commonly arises in parameters of discrete multiplicative noise due to variance. A detailed analysis is conducted in which we describe on key factors, including recent step size, and data, all exhibit similar results on state-of-the-art neural network models.
  arXiv  Detail & Related papers  (2020-06-11T09:58:01Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.