Convergence for Discrete Parameter Update Schemes

AI summary

Overview

Research area: Optimization theory for machine learning, specifically low-precision and fully discrete training of neural networks. The paper sits at the intersection of stochastic gradient descent (SGD) convergence analysis and quantised/discrete learning.

Technical level: Advanced. The paper is primarily a mathematical contribution: it requires comfort with Lipschitz continuity, stochastic gradient assumptions, expectation/telescoping arguments, and multinomial distributions. The empirical section is small and accessible.

Scope (one sentence): The authors define a training update whose update function is integer-valued by construction rather than a rounded continuous gradient, prove convergence for a general class of such schemes, and instantiate the theory with a "zero-inflated multinomial" (ZIM) update evaluated on MNIST.

What This Paper Is About

Modern deep learning models with hundreds of billions of parameters make low-precision training attractive, but existing quantised training methods typically compute a real-valued update and then discretise it (for example by round-to-nearest or stochastic rounding). This paper asks what happens if the update rule itself is discrete from the outset, mapping real-valued weights to integer-valued updates without any quantisation of a continuous update. The goal is to establish convergence guarantees for a general class of such discrete schemes, provide a concrete example, and check it empirically.

Key Contributions

1. A discrete stochastic gradient update scheme (Definition 1). The standard update w_{k+1} ← w_k − α_k · g(w_k, ξ_k) is replaced by w_{k+1} ← w_k − ḡ(w_k, ξ_k), where ḡ: R^d → S^d ⊆ Z^d is integer-valued and there is no separate learning-rate multiplication step.

2. A general convergence theorem (Proposition 4). Under a "discretised" version of the assumptions used by Bottou et al. (2018) — Lipschitz-continuous objective gradients (Assumption 2) and an update bound on the first and second moments (Assumption 3) — the authors prove that the average squared gradient norm converges to a residual error term.

3. A concrete discrete rule: the zero-inflated multinomial (ZIM) update (Definitions 5 and 6). Samples are drawn from a multinomial whose probabilities are proportional to the (absolute) gradient, with a Bernoulli-style "zero inflation" that plays the role of the learning rate, and a Laplace-smoothing-like constant c that keeps the distribution well defined when the gradient is zero.

4. An empirical proof of concept on MNIST. A simple convolutional model and a larger ResNet are trained for 10 epochs under the ZIM update and compared with SGD, showing convergence in both cases.

Main Findings

• Convergence bound. For fixed learning rate ᾱ with 0 < ᾱ ≤ μ / (L M_G), the theorem states that E[(1/K) Σ_{k=1}^{K} ||∇F(w_k)||²₂] ≤ 2(F(w₁) − F_inf)/(K μ ᾱ) + LM/μ, and this tends to LM/μ as K → ∞. The result holds for possibly non-convex F.

• The residual error does not depend on the learning rate. The paper emphasises that the term LM/μ contains no ᾱ, in contrast to (Bottou et al., 2018, Theorem 4.8). The authors describe this as the error bound resulting from the use of discrete weights, a phenomenon they note is common in other work on quantised learning (Nguyen et al., 2024; Li et al., 2017; Li and Sa, 2019).

• The ZIM update satisfies the assumptions. Proposition 7 gives the constants μ = n / (√d L + cd), M = n, and M_G = n² − n, with α_k = r. Here n is the number of multinomial trials, d the weight dimension, L the Lipschitz constant, c the smoothing constant, and r the zero-inflation probability.

• Comparison with BOLD. Specialising Proposition 4 to the ZIM update, taking r = ᾱ, gives a bound proportional to √d L², compared with dL for the discrete update used in BOLD (Nguyen et al., 2024). The authors state their bound is tighter when the Lipschitz constant L grows slowly relative to model dimension d.

• A concrete numerical comparison. Using L = 17 from (Fazlyab et al., 2023, Figure 3(a)) for a single-layer MNIST network with 100 hidden units, the paper reports a bound of 1.4 × 10⁶ for their method against 2.7 × 10⁶ for BOLD.

• Empirical results. Figure 1 shows both the convolutional and ResNet models converging over 10 epochs under the ZIM update compared with SGD. Each curve is averaged over 10 runs with shaded regions showing ±1 std. The authors report a 0.5 %–1 % accuracy penalty, which they attribute to the "noise floor" of Section 2, and note the method works "out of the box" with existing architectures.

• Positioning relative to BOLD. BOLD is described as the closest work in spirit: it fully eliminates floating-point latent values and saves memory in training and inference, but relies on a bespoke backpropagation framework tailored to boolean architectures with convergence analysis specific to that setting. This paper instead aims for a general framework under relatively weak assumptions that encompasses boolean-specific methods such as BOLD.

• Not reported. The paper does not report specific accuracy numbers, memory savings, wall-clock timings, parameter counts for the trained models used in the experiments, or speedups relative to SGD.

Methodology in Plain English

The authors take the standard SGD setup and remove the step that would normally apply a continuous learning-rate-scaled gradient. Instead, they assume the update is produced directly as an integer vector, and ask what conditions are needed for training to still converge.

Their proof strategy mirrors the well-known framework of Bottou et al. (2018), but the assumptions are rewritten in a form suited to discrete jumps. They require that the objective's gradient is Lipschitz continuous, that the objective is bounded below along the trajectory, and that two inequalities hold about the discrete update: the average (over the random draw) update is aligned with the negative gradient by at least a factor proportional to α_k, and the second moment of the update is bounded by α_k M + α_k² M_G ||∇F(w_k)||²₂.

With these in place, the proof follows the same shape as the continuous case: bound the expected improvement in the objective at each step, sum over K steps, rearrange, and take the limit. The key structural difference from the continuous analysis is that the second-moment bound carries an α_k rather than an α_k² in the constant term, which produces a leftover LM/μ that does not vanish with the learning rate.

For the concrete example, the authors design a sampling rule whose expectation is proportional to the gradient. They use a multinomial distribution over the d coordinates with probabilities proportional to |∇F(w_k)| + c, multiply the sampled counts elementwise by the sign of the gradient to get the direction, and use the "zero inflation" probability r to control how often no coordinate is updated at all — effectively acting as the step size. They then verify analytically that this rule satisfies the two moment conditions, and demonstrate it on MNIST image classification against a standard SGD baseline. Code is linked at https://github.com/hellas-ai/neurips2025-convergence-for-discrete-parameter-updates.

Why This Matters

Impact on research. The paper reframes discretisation: rather than treating low precision as an approximation to a continuous method, it treats the discrete update as the object of study and provides convergence guarantees for a general class of such rules. If the approach is extended, it could give a theoretical foundation for training systems whose parameters and updates are never real-valued. It also provides a general framework intended to encompass boolean-specific schemes such as BOLD while covering a broader space of discrete training schemes.

Real-world applications (as motivated or implied by the paper):

• Training and inference on hardware constrained to low-precision or integer arithmetic, where fixed-precision operations are cheap and floating point is expensive.
• Fully discrete learning systems, which the authors describe as the door their method opens.
• Non-real-valued systems such as arithmetic or Boolean circuits, as developed in Wilson and Zanasi (2023, 2020).
• Binarised neural networks (Qin et al., 2020).

Industry relevance. The motivation is explicitly resource-driven: state-of-the-art models comprise hundreds of billions of parameters and require sizeable computational and memory resources, making hardware constraints a central challenge. Recent work has shown quantised training (at 8-bit, 4-bit, or even 2-bit integers) is feasible at scale, with stability addressed through various techniques (Peng et al., 2023; Fishman et al., 2025; DeepSeek-AI et al., 2025). A discrete update rule that needs no floating-point update computation is potentially attractive for memory- and compute-constrained training pipelines. The paper notes the method works with existing architectures, which matters for adoption, but the reported 0.5 %–1 % accuracy penalty is a current cost.

Future Directions

1. Systematic exploration of discrete update schemes. The authors explicitly state that a more systematic exploration of such schemes is left for future work; this paper focuses on laying the mathematical foundations.

2. Closing the accuracy gap. The 0.5 %–1 % accuracy penalty is attributed to the discrete-weight "noise floor" (LM/μ); the authors expect significant improvements from modifying architectures and update schemes.

3. Tightening the theory. The residual error LM/μ is independent of the learning rate, and the comparison with BOLD's dL bound depends on how the Lipschitz constant grows relative to model dimension — an open question about when the discrete approach is provably preferable.

4. Extending to fully discrete learning systems. The authors frame the empirical results as a proof of concept and identify fully discrete learning systems as the broader possibility the method opens up, alongside wider evaluation beyond the MNIST experiments presented here.

Target Audience

Researchers working on low-precision, quantised, or fully discrete training; optimisation theorists interested in convergence analysis under non-standard update rules; and engineers building training or inference systems for integer-only or extremely memory-constrained hardware. It is also relevant to those working on boolean or binarised neural architectures, since the framework is designed to generalise schemes such as BOLD. Readers without a background in stochastic optimisation convergence proofs will likely find Sections 2 and the appendices the most demanding parts, while Section 4 is readable on its own as a proof of concept.

Authors’ 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.