Convergence for Discrete Parameter Update Schemes

Paul Wilson, Fabio Zanasi, George Constantinides · 2025

Read Convergence for Discrete Parameter Update Schemes by Paul Wilson, Fabio Zanasi, George Constantinides (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-2512-04051.txt.

Introduction

Training large models in low precision saves enormous computing, but the usual recipe computes updates in full precision and rounds them afterwards. Paul Wilson, Fabio Zanasi, and George Constantinides propose cutting out the rounding step in a 2025 machine learning preprint. In their schemes, the update rule itself is discrete, producing integer steps by design rather than by discretising a continuous update.

The authors prove that a general class of such schemes converges. As a concrete member, they present a multinomial update rule, backed by empirical evaluation. The framing matters most for models whose structure is inherently discrete, where pretending updates are continuous wastes effort. The work connects to a wider push for efficient training under hardware constraints. Giving discrete rules a rigorous footing may open design space that quantisation cannot reach.

Catalog record

CREATORPaul Wilson, Fabio Zanasi, George Constantinides
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE20 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2512-04051

Browse the full library · About the Tower of Babel

Full text

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

Convergence for Discrete Parameter Update Schemes I thank Diptarko Roy for helpful discussions. The first two authors acknowledge support from ARIA’s Safeguarded AI programme Paul Wilson, Fabio Zanasi, George Constantinides Abstract Modern deep learning models require immense computational resources, motivating research into low-precision training. Quantised training addresses this by representing training components in low-bit integers, but typically relies on discretising real-valued updates. We introduce an alternative approach where the update rule itself is discrete, avoiding the quantisation of continuous updates by design. We establish convergence guarantees for a general class of such discrete schemes, and present a multinomial update rule as a concrete example, supported by empirical evaluation. This perspective opens new avenues for efficient training, particularly for models with inherently discrete structure. \optauthor 2 2 footnotemark: 2 1 Introduction State-of-the-art deep learning models comprise hundreds of billions of parameters and require sizeable computational and memory resources. As models continue to scale, hardware constraints become a central challenge, motivating research into low-precision computation and memory-efficient designs. Among such approaches, quantised training 7 ; 6 ; 2 seeks to train models using low-precision numerical representations (e.g. 8-bit, 4-bit, or even 2-bit integers) for various components of training. Recent work has demonstrated that quantised training is feasible at scale 11 ; 5 ; 3 , with stability issues addressed through a variety of techniques. A common trait of these approaches is that updates are first computed in real values and then discretised via a quantisation function, usually based on rounding (e.g. round-to-nearest or stochastic rounding). In this paper, we propose an alternative route: instead of discretising continuous updates, we assume from the outset that the update function itself is discrete (integer-valued). Our broader motivation is to identify models where directly discrete updates offer greater efficiency than quantisation. We expect such cases to arise in particular when training non-real-valued systems such as arithmetic or Boolean circuits, as developed in 14 ; 13 , and in binarised neural networks 12 . A more systematic exploration of such schemes is left for future work; in this paper, we focus on laying the mathematical foundations of our approach. Perhaps the work closest in spirit to ours is BOLD 10 : it introduces a fully-discrete update scheme that completely eliminates the need for floating point latent values, yielding a significant savings in memory requirements during both training and inference. BOLD relies on a bespoke backpropagation framework tailored to boolean architectures, with convergence analysis specific to that setting. By contrast, our aim is to provide a general framework for discrete updates under relatively weak assumptions; these encompass boolean-specific methods such as BOLD, while opening up a broader space of discrete training schemes. We return to the comparison in Section 3 . Our contribution is structured as follows. Section 2 introduces the assumptions underlying discrete update schemes and presents our main mathematical result: a convergence theorem. Section 3 provides a concrete example of such a scheme, which we then evaluate empirically in Section 4 . 2 Discrete Gradient Updates and their Convergence The standard stochastic gradient update may be written with learning rate sequence \alpha_{k} , update function g and random variable \xi_{k} , as w_{k+1}\leftarrow w_{k}-\alpha_{k}\cdot g(w_{k},\xi_{k}). In contrast, we seek an update that can be computed with simple, performant fixed-precision operations. We propose the following scheme. Definition 1 (Discrete Stochastic Gradient Update) . w_{k+1}\leftarrow w_{k}-\bar{g}(w_{k},\xi_{k}) where \bar{g}:\mathbb{R}^{d}\to S^{d}\subseteq\mathbb{Z}^{d} is a ‘discrete’ (i.e., integer-valued) function. We now focus on showing convergence of such scheme. It is convenient to follow the framework of the work 1 , which focuses on convergence of (standard) stochastic gradient update. In a nutshell, we ‘discretise’ the assumptions used in 1 , and follow a similar proof strategy to demonstrate convergence of discrete gradient update. The first requirement is Lipschitz continuity of gradients of the objective function F ( cf. Assumption 4.1, 1 ), as follows. Assumption 2 (Lipschitz-Continuous objective gradients) . The objective function F:\mathbb{R}^{d}\to\mathbb{R} is continuously differentiable and the gradient function of F , namely \nabla F:\mathbb{R}^{d}\to\mathbb{R}^{d} , is Lipschitz continuous with Lipschitz constant L>0 , i.e. \left\lVert\nabla F(w)-\nabla F(\bar{w})\right\rVert_{2}\leq L\left\lVert w-\bar{w}\right\rVert_{2} for all w,\bar{w}\in\mathbb{R}^{d} This implies the following inequality, shown in ( 1 , (4.3), Appendix B) ). F(w)\leq F(\bar{w})+\nabla F(\bar{w})^{T}(w-\bar{w})+\frac{1}{2}L\left\lVert w-\bar{w}\right\rVert^{2}_{2} (2.1) The second assumption poses requirements on the update. Assumption 3 (Update bound) . Let \bar{g} be a discrete gradient update as defined in Definition 1 , \alpha_{k} a sequence of learning rates, and F an objective function satisfying Assumption 2 . (a) The sequences of iterates w_{k} is contained in an open set over which F is bounded below by a scalar F_{\mathsf{inf}} ( 1 , Assumption 4.3 (a)) (b) There exist scalars \mu>0 , M\geq 0 , and M_{G}>0 such that: \nabla F(w_{k})^{T}\mathbb{E}_{\xi_{k}}\!\left[\bar{g}(w_{k},\xi_{k})\right]\geq\alpha_{k}\mu\left\lVert\nabla F(w_{k})\right\rVert_{2}^{2} (2.2) \mathbb{E}_{\xi_{k}}\!\left[\left\lVert\bar{g}(w_{k},\xi_{k})\right\rVert_{2}^{2}\right]\leq\alpha_{k}M+\alpha_{k}^{2}M_{G}\left\lVert\nabla F(w_{k})\right\rVert_{2}^{2} (2.3) Conditions (a) and (b) are similar to ( 1 , Assumption 4.3) , except in (b) we directly assume a bound on the second moment instead of deriving it from bounds on the 2-norm and variance. This will allow our proof of convergence to closely mirror the approach in ( 1 , Theorem 4.8) . We are now ready to state our convergence result under these assumptions. Proposition 4 . Let F be a (possibly non-convex) function, and fix \alpha_{k}=\bar{\alpha} for all k\in\mathbb{N} where 0<\bar{\alpha}\leq\frac{\mu}{LM_{G}} Then we have \displaystyle\mathbb{E}\left[\frac{1}{K}\sum_{k=1}^{K}\left\lVert\nabla F(w_{k})\right\rVert_{2}^{2}\right]\quad\leq \displaystyle\quad\frac{2(F(w_{1})-F_{\mathsf{inf}})}{K\mu\bar{\alpha}}+\frac{LM}{\mu} \displaystyle\xrightarrow{K\to\infty} \displaystyle\quad\frac{LM}{\mu} Proof. From Proposition 9 (Appendix A ) and by assumption on \bar{\alpha} we have \displaystyle\mathbb{E}_{\xi_{k}}\!\left[F(w_{k+1})\right]-F(w_{k}) \displaystyle\leq-(\mu-\frac{1}{2}\bar{\alpha}LM_{G})\bar{\alpha}\left\lVert\nabla F(w_{k})\right\rVert^{2}_{2}+\frac{1}{2}\bar{\alpha}LM (Proposition 9 ) \displaystyle\leq-\frac{1}{2}\mu\bar{\alpha}\left\lVert\nabla F(w_{k})\right\rVert^{2}_{2}+\frac{1}{2}\bar{\alpha}LM (Assumption on \bar{\alpha} ) Taking the total expectation, we obtain \displaystyle\mathbb{E}\left[F(w_{k+1})\right]-\mathbb{E}\left[F(w_{k})\right] \displaystyle\leq-\frac{1}{2}\mu\bar{\alpha}\mathbb{E}\left[\left\lVert\nabla F(w_{k})\right\rVert^{2}_{2}\right]+\frac{1}{2}\bar{\alpha}LM Now telescoping the sum for k\in\{1\ldots K\} , \displaystyle F_{\mathsf{inf}}-F(w_{1}) \displaystyle\leq\mathbb{E}\left[F(w_{K+1})\right]-F(w_{1}) \displaystyle\leq-\sum_{k=1}^{K}\left(\frac{1}{2}\mu\bar{\alpha}\mathbb{E}\left[\left\lVert\nabla F(w_{k})\right\rVert_{2}^{2}\right]+\frac{1}{2}\bar{\alpha}LM\right) \displaystyle=-\frac{1}{2}\mu\bar{\alpha}\sum_{k=1}^{K}\mathbb{E}\left[\left\lVert\nabla F(w_{k})\right\rVert_{2}^{2}\right]+\frac{1}{2}\bar{\alpha}KLM Now rearranging, \displaystyle\frac{1}{2}\mu\bar{\alpha}\sum_{k=1}^{K}\mathbb{E}\left[\left\lVert\nabla F(w_{k})\right\rVert_{2}^{2}\right]\leq \displaystyle\>F(w_{1})-F_{\mathsf{inf}}+\frac{1}{2}\bar{\alpha}KLM \displaystyle\sum_{k=1}^{K}\mathbb{E}\left[\left\lVert\nabla F(w_{k})\right\rVert_{2}^{2}\right]\leq \displaystyle\>\frac{2(F(w_{1})-F_{\mathsf{inf}})}{\mu\bar{\alpha}}+\frac{KLM}{\mu} (Divide by \frac{1}{2}\mu\alpha ) \displaystyle\mathbb{E}\left[\frac{1}{K}\sum_{k=1}^{K}\left\lVert\nabla F(w_{k})\right\rVert_{2}^{2}\right]\leq \displaystyle\>\frac{2(F(w_{1})-F_{\mathsf{inf}})}{K\mu\bar{\alpha}}+\frac{LM}{\mu} (Divide by K , \mathbb{E} Linearity) \displaystyle\xrightarrow{K\to\infty} \displaystyle\>\frac{LM}{\mu} ∎ Note the term \frac{LM}{\mu} does not involve the learning rate \bar{\alpha} , in contrast to ( 1 , Theorem 4.8) . This is the error bound resulting from the use of discrete weights, as common in other work on quantized learning 10 ; 8 ; 9 . 3 Example: Multinomial We now study a specific discrete gradient update \bar{g} satisfying Assumption 3 . Briefly, the idea is that \bar{g}(w_{k},\xi_{k}) samples from a ‘zero-inflated’ multinomial distribution whose probabilities are proportional to the gradient vector, while the ‘zero inflation’ incorporates a learning rate. Definition 5 (Zero-inflated multinomial) . Let n\in\mathbb{N} represent a number of trials, 0\leq r\leq 1 a probability, and q\in\mathbb{R}^{d} be a discrete probability distribution. Write y\sim\mathsf{ZIMultinomial}(n,r,q) to mean the random variable equal to x_{1:d} , where x\sim\mathsf{Multinomial}(n,p) , and \displaystyle p_{0} \displaystyle=1-r \displaystyle p_{i} \displaystyle=rq_{i}\>\mathrm{for}\>i\in\{1..d\} Note that \sum_{i=0}^{d}p_{i}=p_{0}+\sum_{i=1}^{d}p_{i}=(1-r)+r\sum_{i=1}^{d}q_{i}=1 and so p indeed defines a discrete probability distribution. The first and second moments of the zero-inflated multinomial are given in Proposition 10 . We can now define a discrete update \bar{g} using the \mathsf{ZIMultinomial} . Definition 6 (ZIM update) . Fix constants 0\leq r\leq 1 and c>0 . Define \bar{g}(w_{k},\xi_{k}):=x\odot\operatorname{sign}(\nabla F(w_{k})) where: \displaystyle x \displaystyle\sim\mathsf{ZIMultinomial}_{\xi_{k}}(n,r,q) \displaystyle q \displaystyle:=\frac{|\nabla F(w_{k})|+c}{\sum_{i=1}^{d}\left(|\nabla F(w_{k})|+c\right)}=\frac{|\nabla F(w_{k})|+c}{\left\lVert\nabla F(w_{k})\right\rVert_{1}+cd} The (non-zero-inflated) probabilities q are designed such that the expectation of \bar{g} is proportional to the gradient. The dimension of the weights is denoted d , and c is a Laplace-smoothing-like factor ensuring that q is defined when w_{k}=0 .

Read the complete text