Pith. sign in

REVIEW 2 major objections 4 minor 1 cited by

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

T0 review · 2 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read For a two-layer binary network, the straight-through estimator provably finds the optimal weights once samples grow quadratically with dimension; last-iterate recurrence under label noise needs a quartic count.

desk verdict First finite-sample STE guarantee is worth engaging, but the ergodic proof has a floor/ceiling slip that needs fixing. read the letter →

arxiv 2505.18113 v2 pith:VAVBRZQB submitted 2025-05-23 cs.LG math.OC

Halyun Jeong , Jack Xin , Penghang Yin This is my paper
classification cs.LGmath.OC MSC 68T0768Q3294A12
keywords straight-throughestimatorquantization-awaretrainingbinaryneuralnetworkssamplecomplexity1-bitcompressedsensingergodicconvergencelast-iteratelabelnoise
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Quantization-aware training of binary neural networks relies on the straight-through estimator (STE), a heuristic that backpropagates fake gradients through discrete layers. This paper asks a question the heuristic literature has skipped: how many training samples does STE actually need? For a two-layer network with binary weights and binary activations, Gaussian input data, and squared loss, the answer is roughly $O(n^2)$ samples for the time-averaged iterate to converge to the optimal binary weights, and $O(n^4)$ for the last iterate to reach the optimum infinitely often. The finite-sample analysis matters because practitioners train with finite batches, while prior theory assumed infinite data; it also predicts a recurrence effect: under label noise the iterates escape from and return to the optimum repeatedly, which the authors argue prevents stagnation.

What carries the argument

The paper's engine is the exact Gaussian identity $\mathbb{E}[D(w;z)\,\mathbf{1}\{z^\top w>0\}\,z] = \frac{1}{2\sqrt{2\pi}}(w-w^*)$, where $D(w;z) := \mathbf{1}\{z^\top w>0\} - \mathbf{1}\{z^\top w^*>0\}$; it converts a single STE-gradient step into $x_t = x_{t-1} + \eta_t \frac{\|v\|^2}{\tau}(w^* - w_{t-1}) + \eta_t \varepsilon_t$ with $\tau = 2\sqrt{2\pi}$ and $\|\varepsilon_t\|_\infty \lesssim \sqrt{n/N}$. Around this recursion the proof builds three interlocking pieces: a decomposition of the STE-gradient into squared, cross, and noise terms; an $\ell^\infty$ concentration bound resembling the restricted approximate invertibility condition from 1-bit compressed sensing; and a cycle and occupation-time analysis of the sign dynamics of each coordinate showing correct signs are held about $1/\rho$ times longer than incorrect ones, with the drift-to-perturbation ratio $\rho = O(n/\sqrt{N})$.

What would settle it

Generate Gaussian input matrices with fixed $m$ and $n$, run Algorithm 1 with $N = C n^2$ for increasing constants $C$, and record whether $Q(\bar w_T) = w^*$ for large $T$; Theorem 1 predicts the recovery probability jumps to 1 once $C$ clears a universal constant. A more direct check measures the empirical concentration of the STE-gradient at a fixed non-optimal $w$: if $\|\tilde\nabla_w L(w) - (\|v\|^2/\tau)(w - w^*)\|_\infty$ does not decay like $\sqrt{n/N}$ as $N$ grows, the central bound fails. Repeating the recovery experiment with non-Gaussian inputs, for example uniform entries, should suppress recovery, isolating the Gaussian identity as the operative assumption.

Watch

Extended reading notes

Core claim

The central claim is that the STE-gradient method on a fully binarized two-layer network is governed by a drift-plus-perturbation recursion whose drift term is exactly proportional to $(w - w^*)$ in expectation on Gaussian data. The paper proves an $\ell^\infty$ concentration bound showing the perturbation has size $O(\sqrt{n/N})$ once $N \gtrsim n^2$, making the perturbation-to-drift ratio $\rho = O(n/\sqrt{N})$ small. From that, an occupation-time analysis shows each coordinate of the quantized iterate spends a $1/\rho$-factor longer in the correct sign region, so the ergodic average reaches the optimum at rate $O(\sqrt{n/N})$ and $Q(\bar w_T) = w^*$ for large $T$. Under label noise the surrogate gradient at the optimum is a nonvanishing symmetric random vector, so the last iterate visits $w^*$ infinitely often and, with probability at least $1/2$, departs infinitely often.

Load-bearing premise

The proof requires the input rows to be exactly Gaussian, because only then does the expected surrogate gradient align with $w - w^*$; without this identity the drift term disappears and the concentration argument collapses.

Editorial extensions

If this is right

  • Quantization-aware training of a two-layer binarized network succeeds with $O(n^2)$ samples in the ergodic sense and $O(n^4)$ in the last-iterate sense, making the finite sample size itself the decisive resource.
  • With continuous label noise the STE-gradient iterates provably visit the global optimum infinitely often and also escape it infinitely often with probability at least $1/2$, so the surrogate gradient never gets trapped at the optimum.
  • The sample requirement grows with $(\|v\|_1^2 + K_\xi \|v\|_1)n / \|v\|_2$, so denser second-layer weights and heavier noise both raise the cost in a quantified way.
  • Exact recovery is achieved by quantizing the ergodic average, $Q(\bar w_T) = w^*$, for sufficiently large $T$, giving a concrete stopping criterion.
  • The empirical phase transition for ergodic recovery is linear in $N/n$, matching the theoretical $O(n^2)$ bound; the quartic last-iterate bound is conservative relative to the observed quadratic transition.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the drift-plus-perturbation decomposition is the active mechanism, then whitening or other normalizations of non-Gaussian inputs should restore STE's effectiveness in the same two-layer setting, which is directly testable with a small-scale experiment; the paper asserts this restoration but does not show the supporting experiment in the body.
  • For deeper networks the same per-layer concentration argument would plausibly accumulate, suggesting a sample complexity that grows with the sum of per-layer quadratic terms; this extension is not proven here.
  • The nonvanishing surrogate gradient at $w^*$ is an anti-stagnation feature: unlike projected gradient descent with a discrete projection, STE cannot rest at a fixed point, which may be the real reason STE-based quantization training avoids premature convergence.
  • The proven $1/2$ escape probability is only a lower bound; measuring the empirical departure frequency as a function of noise variance should show it approaching $1$, a strengthening the authors hint at but leave open.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. The paper studies the straight-through estimator (STE) for quantization-aware training of a two-layer network with binary weights and activations, under i.i.d. Gaussian inputs and squared loss. The main contribution is a finite-sample analysis: Theorem 4 gives an l_infinity concentration bound for the STE gradient around a drift term proportional to w-w*, and Theorems 6/8 and 7/9 use this to claim that O(n^2) samples suffice for the ergodic average to converge to the optimal binary weight w*, while O(n^4) samples suffice for the last iterate to visit w* infinitely often. With continuous label noise, the iterates are also claimed to escape from w* infinitely often. The proofs combine techniques from 1-bit compressed sensing with an occupation-time/cycle analysis of the one-dimensional coordinate dynamics, and the theoretical phase transition is compared with numerical experiments.

Significance. If the result holds, this is a genuinely useful first finite-sample treatment of STE for full weight-and-activation quantization, going beyond the population-loss analyses in prior work. The explicit dependence on dimension n, sample size N, noise level, and the second-layer weights v yields a concrete and falsifiable prediction, and the recurrence phenomenon under label noise is an interesting observation. The concentration argument is largely self-contained and does not fit parameters to data. However, the main ergodic claim currently rests on a floor/ceiling error in the cycle-length estimate, and the uniform bound over the whole binary cube has a gap at the antipodal point; both are localized and appear repairable, but as written they affect load-bearing parts of the proof.

major comments (2)
  1. [Appendix B, Step 2 (proof of Theorem 6)] The minimum positive-phase length is defined as L := floor((1-2rho)/rho), and the proof then asserts L >= (1-2rho)/rho. This is false whenever (1-2rho)/rho is not an integer; for rho=0.19, floor((1-2rho)/rho)=3 while (1-2rho)/rho is about 3.26, so the subsequent inequality 1+L >= (1-rho)/rho fails (4 < 4.26). The bound gamma <= T'/(1+L)+1 <= T' rho/(1-rho)+1, which is what produces the O(rho) average-sign error and hence the ergodic convergence rate, is therefore not established as written. Replacing the floor by a ceiling repairs the argument with only constant adjustments, but the manuscript as written does not prove the claimed sample complexity.
  2. [Appendix A, proof of Theorem 5 (w = -w* case)] Theorem 5 and Theorem 4 must hold uniformly for all w in Q1, including the antipodal point w = -w*. In the w = -w* part of the proof, the manuscript invokes Lemmas 1 and 3, but Lemma 3 is explicitly stated only for w != +-w* and its proof uses u2 = (w+w*)/||w+w*||, which is undefined at w = -w*. A separate argument for the orthogonal component, or an extension of Lemma 3 to this case, is needed; the ingredients (zero expectation and sub-Gaussianity) appear available, but the proof as written contains a gap at a point that is quantified in the main theorem.
minor comments (4)
  1. [Appendix B, Step 3 (proof of Theorem 6)] The identity sum_{t=1}^{T0} sign(x_t^j) = T0 - 2 assumes that x_{T0}^j < 0, but this is false in the case where x_t^j never becomes negative and T0 = T; there the sum is T, not T - 2. Since the argument only needs a lower bound, writing '>=' instead of '=' would suffice, but the displayed equality is not true in general.
  2. [Abstract and Section 6] The abstract in the paper metadata states that the authors 'empirically demonstrate that STE fails for general non-Gaussian data but its effectiveness can be restored through normalization,' but Section 6 contains no such experiment. This claim should either be added to the experiments or removed from the abstract.
  3. [Appendix A.1.1, Lemma 1 union bound] The failure-probability computation undercounts a factor of two: 2^n times 2 exp(-c'''n) equals 2 exp((n+1)ln 2 - c'''n), not 2 exp(n ln 2 - c'''n). This does not affect the conclusion, since the constants can absorb the extra factor, but the displayed algebra is incorrect.
  4. [Appendix D, Theorem 8] The sentence 'Since M0 >= 1 can be chosen arbitrarily close to 1, by choosing M0 = 1.1' is confusing, because M0 was introduced earlier as a fixed universal constant arising from the step-size ratio. The dependence of the burn-in time T'_init on M0 should be stated explicitly so that the choice M0 = 1.1 is clearly legitimate.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the sample-complexity theorems follow from a Gaussian-population identity and self-contained concentration and counting arguments; the only self-citation is an independently checkable integral.

full rationale

The derivation chain is self-contained in the sense required by the circularity rubric. The central concentration bound (Theorem 4 / Theorem 3) is obtained from three sub-Gaussian/Bernstein concentration estimates (Lemmas 1-5) whose means are computed from the exact Gaussian identity E[D(w;z)1{z^T w>0}z] = (w-w*)/(2*sqrt(2*pi)), cited from the authors' prior work [30]. This identity is parameter-free, does not involve the sample size N, and does not already encode the convergence conclusion; it is an exact Gaussian integral that could be verified externally, so the self-citation is not load-bearing in a circular way. The ergodic and last-iterate theorems are then derived by explicit cycle-length and occupation-time counting arguments (Appendix B/C/D) that use only this drift-alignment bound plus Assumptions 1-3; no parameter is fitted to data and no 'prediction' is defined in terms of the quantity it claims to predict. The empirical recovery-rate experiments are external checks rather than inputs to the proof. The floor-versus-ceiling issue in Appendix B is a possible internal proof error, and the abstract's non-Gaussian claim lacks an included experiment, but neither constitutes the derivation reducing to its own inputs. Overall, no step was found that is self-definitional, fitted-input-as-prediction, or smuggled via self-citation.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The central claim rests on four axioms: the Gaussian input model, the sub-Gaussian symmetric noise model, the step-size scheduling assumption, and a parameter-free Gaussian expectation identity imported from prior work [30,59]. No numbers are fitted to data; the step size is an algorithmic hyperparameter, not a fitted parameter. The only external mathematical input is the Gaussian identity, which is not circular because it is derived, not chosen to fit the target result.

assumptions (5)
  • domain assumption Assumption 1: Rows of Z are i.i.d. N(0,I_n) and m ≲ O(2^n)
    Used throughout the proof; the Gaussian law is required for the population expectation identity E[D(w;z)1{z^T w>0}z] ∝ (w-w*) and for the sub-Gaussian concentration arguments. The bound m ≲ 2^n keeps the union bounds over cross terms exponential in n but controlled.
  • domain assumption Assumption 2: Label noise ξ is symmetric and sub-Gaussian with norm Kξ
    Symmetry gives E[ξ]=0 and is used in Lemma 6 for the symmetric gradient at w*; sub-Gaussianity is used in the Bernstein bound for the noise term.
  • domain assumption Assumption 3: Step sizes η_t are positive, non-increasing, non-summable, with η_{t+1}/η_t → 1
    These conditions are standard in stochastic approximation and are used in the drift analysis (one-step reset and cycle length) for general step sizes.
  • standard math Gaussian expectation identity from [30,59]: E[D(w;z)1{z^T w>0}z] = (1/(2√(2π)))(w-w*)
    This identity is cited, not proved, and is the source of the explicit constant τ = 2√(2π). It is a parameter-free Gaussian integral and is used in Lemmas 1-3.
  • standard math Concentration inequalities: Hoeffding for sub-Gaussians and Bernstein for sub-exponentials, plus union bound
    Used to prove the uniform ℓ∞ concentration bound over the discrete set Q1 of size 2^n.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Beyond Discreteness: Sample Complexity Analysis of Straight-Through Estimator for 1-bit Quantization." pith.science (2026). https://pith.science/paper/VAVBRZQB

@misc{pith2026250518113,
  author       = {Pith},
  title        = {Pith review of: Beyond Discreteness: Sample Complexity Analysis of Straight-Through Estimator for 1-bit Quantization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VAVBRZQB}},
  note         = {Machine review of arXiv:2505.18113}
}
read the original 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.

Figures

Figures reproduced from arXiv: 2505.18113 by the authors.

Figure 1
Figure 1. Left: Recovery rate for the ergodic averaged iterate Q(wT ) in the noiseless case. Middle: Recovery rate for the last-iterate wT in the noiseless case. Right: Curves for ∥wt − w∗∥ vs. t and L(wt ) vs. t in the noisy case with m = 128, n = 25, N = 140. The left and middle panels of [PITH_FULL_IMAGE:figures/full_fig_p012_1.png] view at source ↗

Discussion (0). Sign in to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Understanding Quantization-Aware Training: Gradients at Quantized Weights Bias to the Low-Loss Basin

    cs.LG 2026-06 unverdicted novelty 7.0 of 10

    A geometric local landscape model explains PTQ basin-crossing failure at aggressive bitwidths and proves finite-time QAT recovery via straight-through estimator gradient bias under quantizer-compatibility assumptions.

Reference graph

Works this paper leans on

62 extracted references · 42 canonical work pages · cited by 1 Pith paper

  1. [1]

    Mirror descent view for neural network quantization

    Thalaiyasingam Ajanthan, Kartik Gupta, Philip Torr, Richad Hartley, and Puneet Dokania. Mirror descent view for neural network quantization. InInternational conference on artificial intelligence and statistics, pages 2809–2817. PMLR, 2021

    work page 2021

  2. [2]

    Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples

    Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples. arXiv preprint arXiv:1802.00420, 2018

    arXiv 2018

  3. [3]

    A simple proof of the restricted isometry property for random matrices.Constructive approximation, 28:253–263, 2008

    Richard Baraniuk, Mark Davenport, Ronald DeVore, and Michael Wakin. A simple proof of the restricted isometry property for random matrices.Constructive approximation, 28:253–263, 2008

    work page 2008

  4. [4]

    Estimating or propagating gradients through stochastic neurons for conditional computation

    Yoshua Bengio, Nicholas Léonard, and Aaron Courville. Estimating or propagating gradients through stochastic neurons for conditional computation. arXiv preprint arXiv:1308.3432, 2013

    arXiv 2013

  5. [5]

    1-bit compressive sensing

    Petros T Boufounos and Richard G Baraniuk. 1-bit compressive sensing. In2008 42nd Annual Conference on Information Sciences and Systems, pages 16–21. IEEE, 2008

    2008

  6. [6]

    Deep learning with low precision by half-wave gaussian quantization

    Zhaowei Cai, Xiaodong He, Jian Sun, and Nuno Vasconcelos. Deep learning with low precision by half-wave gaussian quantization. InIEEE Conference on Computer Vision and Pattern Recognition, 2017. 13

    work page 2017

  7. [7]

    Robust uncertainty princi- ples: Exact signal reconstruction from highly incomplete frequency information.IEEE Transactions on information theory, 52(2):489–509, 2006

    Emmanuel J Candès, Justin Romberg, and Terence Tao. Robust uncertainty princi- ples: Exact signal reconstruction from highly incomplete frequency information.IEEE Transactions on information theory, 52(2):489–509, 2006

    work page 2006

  8. [8]

    Optimal quantized compressed sensing via projected gradient descent.arXiv preprint arXiv:2407.04951, 2024

    Junren Chen and Ming Yuan. Optimal quantized compressed sensing via projected gradient descent.arXiv preprint arXiv:2407.04951, 2024

    arXiv 2024

Show all 62 references
  1. [9]

    Pact: Parameterized clipping activation for quantized neural networks.arXiv preprint arXiv:1805.06085, 2018

    Jungwook Choi, Zhuo Wang, Swagath Venkataramani, Pierce I-Jen Chuang, Vijayalak- shmi Srinivasan, and Kailash Gopalakrishnan. Pact: Parameterized clipping activation for quantized neural networks.arXiv preprint arXiv:1805.06085, 2018

    2018 arXiv

  2. [10]

    Ergodic theory: with a view towards number theory

    SG Dani. Ergodic theory: with a view towards number theory. by manfred einsiedler thomas ward. springer verlag, london, 2011.Ergodic Theory and Dynamical Systems, 32(3):1157–1160, 2012

    2011

  3. [11]

    Demystifying and generalizing binaryconnect.Advances in Neural Information Processing Systems, 34:13202–13216, 2021

    Tim Dockhorn, Yaoliang Yu, Eyyüb Sari, Mahdi Zolnouri, and Vahid Partovi Nia. Demystifying and generalizing binaryconnect.Advances in Neural Information Processing Systems, 34:13202–13216, 2021

    2021

  4. [12]

    Compressed sensing: theory and applications

    Yonina C Eldar and Gitta Kutyniok. Compressed sensing: theory and applications. Cambridge university press, 2012

    2012

  5. [13]

    Springer, 2013

    Simon Foucart and Holger Rauhut.An invitation to compressive sensing. Springer, 2013

    2013

  6. [14]

    Nbiht: An efficient algorithm for 1-bit compressed sensing with optimal error decay rate.IEEE Transactions on Information Theory, 68(2):1157–1177, 2021

    Michael P Friedlander, Halyun Jeong, Yaniv Plan, and Özgür Yılmaz. Nbiht: An efficient algorithm for 1-bit compressed sensing with optimal error decay rate.IEEE Transactions on Information Theory, 68(2):1157–1177, 2021

    2021

  7. [15]

    Approximation of functions with one-bit neural networks

    Sinan Güntürk and Weilin Li. Approximation of functions with one-bit neural networks. arXiv preprint arXiv:2112.09181, 2021

    2021 arXiv

  8. [16]

    Deep residual learning for image recognition

    Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. InIEEE conference on computer vision and pattern recognition, pages 770–778, 2016

    2016

  9. [17]

    Neural networks for machine learning, coursera.Coursera, video lectures, 2012

    Geoffrey Hinton. Neural networks for machine learning, coursera.Coursera, video lectures, 2012

    2012

  10. [18]

    Binarized neural networks: Training neural networks with weights and activations constrained to +1 or -1.arXiv preprint arXiv:1602.02830, 2016

    Itay Hubara, Matthieu Courbariaux, Daniel Soudry, Ran El-Yaniv, and Yoshua Bengio. Binarized neural networks: Training neural networks with weights and activations constrained to +1 or -1.arXiv preprint arXiv:1602.02830, 2016

    2016 arXiv

  11. [19]

    Quantized neural networks: Training neural networks with low precision weights and activations

    Itay Hubara, Matthieu Courbariaux, Daniel Soudry, Ran El-Yaniv, and Yoshua Bengio. Quantized neural networks: Training neural networks with low precision weights and activations. Journal of Machine Learning Research, 18:1–30, 2018. 14

    2018

  12. [20]

    Robust 1- bit compressive sensing via binary stable embeddings of sparse vectors.IEEE transactions on information theory, 59(4):2082–2102, 2013

    Laurent Jacques, Jason N Laska, Petros T Boufounos, and Richard G Baraniuk. Robust 1- bit compressive sensing via binary stable embeddings of sparse vectors.IEEE transactions on information theory, 59(4):2082–2102, 2013

    2013

  13. [21]

    Categorical reparameterization with gumbel- softmax

    Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameterization with gumbel- softmax. In International Conference on Learning Representations (ICLR), 2017

    2017

  14. [22]

    Parq: Piecewise-affine regularized quantization.arXiv preprint arXiv:2503.15748, 2025

    Lisa Jin, Jianhao Ma, Zechun Liu, Andrey Gromov, Aaron Defazio, and Lin Xiao. Parq: Piecewise-affine regularized quantization.arXiv preprint arXiv:2503.15748, 2025

    2025 arXiv

  15. [23]

    Binaryduo: Reducing gradient mismatch in binary activation network by coupling binary activations.arXiv preprint arXiv:2002.06517, 2020

    Hyungjun Kim, Kyungsu Kim, Jinseok Kim, and Jae-Joon Kim. Binaryduo: Reducing gradient mismatch in binary activation network by coupling binary activations.arXiv preprint arXiv:2002.06517, 2020

    2002 arXiv

  16. [24]

    Imagenet classification with deep convolutional neural networks.Communications of the ACM, 60(6):84–90, 2017

    Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolutional neural networks.Communications of the ACM, 60(6):84–90, 2017

    2017

  17. [25]

    Gradient estimation for binary latent variables via gradient variance clipping

    Russell Z Kunes, Mingzhang Yin, Max Land, Doron Haviv, Dana Pe’er, and Simon Tavaré. Gradient estimation for binary latent variables via gradient variance clipping. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 8405–8412, 2023

    2023

  18. [26]

    Gradient-based learning applied to document recognition.Proceedings of the IEEE, 86(11):2278–2324, 1998

    Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition.Proceedings of the IEEE, 86(11):2278–2324, 1998

    1998

  19. [27]

    Training quantized nets: A deeper understanding

    Hao Li, Soham De, Zheng Xu, Christoph Studer, Hanan Samet, and Tom Goldstein. Training quantized nets: A deeper understanding. InAdvances in Neural Information Processing Systems, pages 5811–5821, 2017

    2017

  20. [28]

    Binary quantized network training with sharpness-aware minimization.Journal of Scientific Computing, 94(1):16, 2023

    Ren Liu, Fengmiao Bian, and Xiaoqun Zhang. Binary quantized network training with sharpness-aware minimization.Journal of Scientific Computing, 94(1):16, 2023

    2023

  21. [29]

    Learning quantized neural nets by coarse gradient method for nonlinear classification.Research in the Mathematical Sciences, 8:1–19, 2021

    Ziang Long, Penghang Yin, and Jack Xin. Learning quantized neural nets by coarse gradient method for nonlinear classification.Research in the Mathematical Sciences, 8:1–19, 2021

    2021

  22. [30]

    Recurrence of optimum for training weight and activation quantized networks.Applied and Computational Harmonic Analysis, 62:41–65, 2023

    Ziang Long, Penghang Yin, and Jack Xin. Recurrence of optimum for training weight and activation quantized networks.Applied and Computational Harmonic Analysis, 62:41–65, 2023

    2023

  23. [31]

    Enhance the visual representation via discrete adversarial training

    Xiaofeng Mao, Yuefeng Chen, Ranjie Duan, Yao Zhu, Gege Qi, Xiaodan Li, Rong Zhang, Hui Xue, et al. Enhance the visual representation via discrete adversarial training. Advances in Neural Information Processing Systems, 35:7520–7533, 2022

    2022

  24. [32]

    Binary iterative hard thresholding converges with optimal number of measurements for 1-bit compressed sensing.Journal of the ACM, 71(5):1–64, 2024

    Namiko Matsumoto and Arya Mazumdar. Binary iterative hard thresholding converges with optimal number of measurements for 1-bit compressed sensing.Journal of the ACM, 71(5):1–64, 2024. 15

    2024

  25. [33]

    Playing atari with deep reinforcement learning

    Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint arXiv:1312.5602, 2013

    2013 arXiv

  26. [34]

    Straight- through meets sparse recovery: the support exploration algorithm

    Mimoun Mohamed, François Malgouyres, Valentin Emiya, and Caroline Chaux. Straight- through meets sparse recovery: the support exploration algorithm. arXiv preprint arXiv:2301.13584, 2023

    2023 arXiv

  27. [35]

    Rao-blackwellizing the straight- through gumbel-softmax gradient estimator.arXiv preprint arXiv:2010.04838, 2020

    Max B Paulus, Chris J Maddison, and Andreas Krause. Rao-blackwellizing the straight- through gumbel-softmax gradient estimator.arXiv preprint arXiv:2010.04838, 2020

    2010 arXiv

  28. [36]

    Cambridge university press, 1989

    Karl E Petersen and Karl Petersen.Ergodic theory. Cambridge university press, 1989

    1989

  29. [37]

    Robust 1-bit compressed sensing and sparse logistic regression: A convex programming approach.IEEE Transactions on Information Theory, 59(1):482–494, 2012

    Yaniv Plan and Roman Vershynin. Robust 1-bit compressed sensing and sparse logistic regression: A convex programming approach.IEEE Transactions on Information Theory, 59(1):482–494, 2012

    2012

  30. [38]

    One-bit compressed sensing by linear programming

    Yaniv Plan and Roman Vershynin. One-bit compressed sensing by linear programming. Communications on pure and Applied Mathematics, 66(8):1275–1297, 2013

    2013

  31. [39]

    The generalized lasso with non-linear observations

    Yaniv Plan and Roman Vershynin. The generalized lasso with non-linear observations. IEEE Transactions on information theory, 62(3):1528–1537, 2016

    2016

  32. [40]

    Xnor- net: Imagenet classification using binary convolutional neural networks

    Mohammad Rastegari, Vicente Ordonez, Joseph Redmon, and Ali Farhadi. Xnor- net: Imagenet classification using binary convolutional neural networks. InEuropean Conference on Computer Vision, pages 525–542. Springer, 2016

    2016

  33. [41]

    Learning strides in convolutional neural networks.arXiv preprint arXiv:2202.01653, 2022

    Rachid Riad, Olivier Teboul, David Grangier, and Neil Zeghidour. Learning strides in convolutional neural networks.arXiv preprint arXiv:2202.01653, 2022

    2022 arXiv

  34. [42]

    Cornell Aeronautical Laboratory, 1957

    Frank Rosenblatt.The perceptron, a perceiving and recognizing automaton Project Para. Cornell Aeronautical Laboratory, 1957

    1957

  35. [43]

    Spartan Book, 1962

    Frank Rosenblatt.Principles of neurodynamics. Spartan Book, 1962

    1962

  36. [44]

    Neural network approximation: Three hidden layers are enough.Neural Networks, 141:160–173, 2021

    Zuowei Shen, Haizhao Yang, and Shijun Zhang. Neural network approximation: Three hidden layers are enough.Neural Networks, 141:160–173, 2021

    2021

  37. [45]

    High-order approximation rates for shallow neural networks with cosine and reluk activation functions.Applied and Computational Harmonic Analysis, 58:1–26, 2022

    Jonathan W Siegel and Jinchao Xu. High-order approximation rates for shallow neural networks with cosine and reluk activation functions.Applied and Computational Harmonic Analysis, 58:1–26, 2022

    2022

  38. [46]

    Single-path mobile automl: Efficient convnet design and nas hyperparameter optimization.IEEE Journal of Selected Topics in Signal Processing, 14(4):609–622, 2020

    Dimitrios Stamoulis, Ruizhou Ding, Di Wang, Dimitrios Lymberopoulos, Bodhi Priyantha, Jie Liu, and Diana Marculescu. Single-path mobile automl: Efficient convnet design and nas hyperparameter optimization.IEEE Journal of Selected Topics in Signal Processing, 14(4):609–622, 2020. 16

    2020

  39. [47]

    Policy gradient methods for reinforcement learning with function approximation.Advances in neural information processing systems, 12, 1999

    Richard S Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy gradient methods for reinforcement learning with function approximation.Advances in neural information processing systems, 12, 1999

    1999

  40. [48]

    Attention is all you need.Advances in neural information processing systems, 30, 2017

    Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. Attention is all you need.Advances in neural information processing systems, 30, 2017

    2017

  41. [49]

    Cambridge university press, 2018

    Roman Vershynin.High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018

    2018

  42. [50]

    Memory capacity of neural networks with threshold and rectified linear unit activations.SIAM Journal on Mathematics of Data Science, 2(4):1004–1033, 2020

    Roman Vershynin. Memory capacity of neural networks with threshold and rectified linear unit activations.SIAM Journal on Mathematics of Data Science, 2(4):1004–1033, 2020

    2020

  43. [51]

    Universal approximation of functions on sets.Journal of Machine Learning Research, 23(151):1–56, 2022

    Edward Wagstaff, Fabian B Fuchs, Martin Engelcke, Michael A Osborne, and Ingmar Posner. Universal approximation of functions on sets.Journal of Machine Learning Research, 23(151):1–56, 2022

    2022

  44. [52]

    Training deep neural networks with 8-bit floating point numbers.Advances in neural information processing systems, 31, 2018

    Naigang Wang, Jungwook Choi, Daniel Brand, Chia-Yu Chen, and Kailash Gopalakr- ishnan. Training deep neural networks with 8-bit floating point numbers.Advances in neural information processing systems, 31, 2018

    2018

  45. [53]

    Roste: An efficient quantization-aware supervised fine-tuning approach for large language models

    Quan Wei, Chung-Yiu Yau, Hoi-To Wai, Dongyeop Kang, Youngsuk Park, and Mingyi Hong. Roste: An efficient quantization-aware supervised fine-tuning approach for large language models. arXiv preprint arXiv:2502.09003, 2025

    2025 arXiv

  46. [54]

    Relation embedding with dihedral group in knowledge graph

    Canran Xu and Ruijiang Li. Relation embedding with dihedral group in knowledge graph. Annual Conference of the Association for Computational Linguistics, 2019

    2019

  47. [55]

    Injecting logical constraints into neural networks via straight-through estimators

    Zhun Yang, Joohyung Lee, and Chiyoun Park. Injecting logical constraints into neural networks via straight-through estimators. In International Conference on Machine Learning, pages 25096–25122. PMLR, 2022

    2022

  48. [56]

    Ratio and difference ofl1 and l2 norms and sparse representation with coherent dictionaries.Commun

    Penghang Yin, Ernie Esser, and Jack Xin. Ratio and difference ofl1 and l2 norms and sparse representation with coherent dictionaries.Commun. Inf. Syst., 14(2):87–109, 2014

    2014

  49. [57]

    Understanding straight-through estimator in training activation quantized neural nets

    Penghang Yin, Jiancheng Lyu, Shuai Zhang, Stanley Osher, Yingyong Qi, and Jack Xin. Understanding straight-through estimator in training activation quantized neural nets. In International Conference on Learning Representations, 2019

    2019

  50. [58]

    Binaryrelax: A relaxation approach for training deep neural networks with quantized weights

    Penghang Yin, Shuai Zhang, Jiancheng Lyu, Stanley Osher, Yingyong Qi, and Jack Xin. Binaryrelax: A relaxation approach for training deep neural networks with quantized weights. SIAM Journal on Imaging Sciences, 11(4):2205–2223, 2018

    2018

  51. [59]

    Blended coarse gradient descent for full quantization of deep neural networks.Research in the Mathematical Sciences, 6(1), 2019

    Penghang Yin, Shuai Zhang, Jiancheng Lyu, Stanley Osher, Yingyong Qi, and Jack Xin. Blended coarse gradient descent for full quantization of deep neural networks.Research in the Mathematical Sciences, 6(1), 2019. 17 Appendix First, we restate the assumption for the sample size...

    2019

  52. [60]

    correct" sign region within one time step of entering the “incorrect

    Suppose each component of|ϵt| is bounded by e∆ := 1 τ (C ′∥v∥2 1 + C ′′Kξ∥v∥1) r n N = O((∥v∥2 1 + Kξ∥v∥1)) r n N . This bound holds with probability at least1 − 5m exp(−cn) for some positive universal constant c >0, as established by theℓ∞ concentration bound in Theorem 4. Th...

  53. [61]

    Each componentGp is symmetric about zero (Gp d = −Gp)

  54. [62]

    This also impiles thatP (G ̸= 0) = 1

    Since ξ(i) is a continuous random variable (makingGp continuous) and v ̸= 0, so for each p, Gp is not almost surely zero, andP (Gp > 0) = P (Gp < 0) = 1 /2, thus P (Gp ̸= 0) = 1. This also impiles thatP (G ̸= 0) = 1. Proof of the Lemma 6. 37 Symmetry of Gp. Let Gp = 1 N PN i=1...

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.