Thermometer encoding writes a real number as a run of ones followed by zeros: one bit per threshold, set when the value exceeds that threshold. It is the standard way to feed continuous sensor values into lookup-table ("weightless") networks that run in one to three clock cycles on FPGAs. The theory of training difficulty, meanwhile, says that fitting even a two-layer ReLU network is NP-hard in two input dimensions and ∃ℝ-complete in general. Those proofs assume raw continuous coordinates. Nobody has asked what happens to training difficulty once the inputs are thermometer codes. That is odd, because the code has unusual structure. A first-layer weight on thermometer bit $j$ of feature $i$ is exactly the size of a jump in a step function of $x_i$. Each hidden ReLU therefore computes the positive part of a sum of per-feature step functions, and weight decay on the first layer becomes a penalty on the squared jump sizes.
This note proposes to turn that observation into a complexity classification and a working solver. The classification asks when weight-decayed, unbounded-width two-layer training on thermometer-coded data can be solved exactly, with the number of thresholds $B$ per feature and the number of raw features $d$ as explicit parameters. The solver adds hidden units one at a time and returns a certificate of how far it is from the global optimum. That certificate is then used to measure how much gradient-trained thermometer networks and lookup-table networks lose to optimization rather than to capacity or encoding. If the loss is small, the field can stop blaming the optimizer. If it is large, the certificate shows where to look.
Core Claim
Thermometer encoding replaces the geometric difficulty that drives existing hardness proofs with a combinatorial difficulty controlled by the bit budget $B$. Concretely, the classification has three targets. First, with one raw feature, the inputs lie on a chain and the network is a sum of ReLUs of step functions. We conjecture that the step that adds one hidden unit is solvable in time polynomial in $B$ and the number of samples $n$. Second, with $d$ raw features, that step is NP-hard in general but fixed-parameter tractable in the interaction structure among features. Third, regularized training is exactly solvable in time polynomial in $n$ whenever the number of distinct encoded inputs, at most $(B+1)^d$, is bounded. This is the structure the proposal is built to test, prove, or refute.
The convex view makes the target precise. Weight-decayed two-layer ReLU training with unbounded width can be rewritten as a convex problem over hidden units. It is solved by repeatedly finding the single neuron most correlated with the current residual $r \in \mathbb{R}^n$ (the per-sample errors of the current model). On thermometer data this neuron-finding step is
$$\max_{g_1,\dots,g_d,\;b}\;\sum_{s=1}^{n} r_s \,\max\Big(0,\; b+\sum_{i=1}^{d} g_i(x_{s,i})\Big)\quad\text{s.t.}\quad b^2+\sum_{i=1}^{d}\sum_{j=1}^{B}\big(\Delta_j g_i\big)^2\le 1.$$
Here $g_i$ is a step function on feature $i$ with jumps $\Delta_j g_i$ at its $B$ thresholds, $b$ is the bias, and $x_{s,i}$ is feature $i$ of sample $s$. The jump penalty is a chain-structured quadratic form, because the inverse of the thermometer Gram matrix in one feature is tridiagonal. The central hypothesis is that this chain structure is what decides tractability.
Relation to Prior Work
Four hardness results motivate and constrain the work. Training Neural Networks is NP-Hard in Fixed Dimension proves NP-hardness of zero-error training with only two input dimensions. It uses ridge "levee" gadgets built from four ReLUs at arbitrary continuous positions and orientations, and shows fixed-parameter tractability only for convex networks. Training Fully Connected Neural Networks is ∃R-Complete and Training Neural Networks is ER-complete show that optimal weights can be irrational, which rules out combinatorial search on raw continuous data.
Thermometer coding changes both premises. Inputs become finitely many grid points, and a single neuron can bend its boundary along any staircase, which makes it more expressive than a raw ReLU. We study unbounded-width regularized training rather than fixed small width. So these results neither imply nor exclude our tractability claims, and the first theoretical task is to check whether a grid version of the levee gadget survives under the additive step structure.
On the Hardness of Training Deep Neural Networks Discretely constrains the design differently. It shows that choosing weights from a discrete set is NP-hard even with one sample and one input. We therefore never optimize discrete weights directly. We solve the continuous convex problem, round the jumps to small integers, and report the rounding loss separately.
Two papers supply the method. Polynomial-Time Solutions for ReLU Network Training recasts regularized two-layer training as a convex dual whose feasibility is tied to Max-Cut. Its exact and approximate tractable regimes are orthogonal-separable and negatively correlated data. Thermometer codes sit at the opposite extreme: two encoded values share a prefix of ones, so their inner product is the smaller bin index and all pairs are strongly positively correlated. Its tractable cases therefore do not apply. Our replacement hypothesis is that the Max-Cut instances become chain-structured for one feature, and bounded-treewidth when features interact sparsely, where Max-Cut is easy.
A Combinatorial Perspective on the Optimization of Shallow ReLU Networks views training as search over activation patterns, the vertices of a zonotope (a polytope generated by summing line segments, here one per data point). It shows that underparameterized gradient descent gets stuck where vertex search does not. This creates a real tension. On one-feature thermometer data every one of the $2^{B+1}$ on/off patterns over the bins is realizable, so the vertex count grows exponentially rather than collapsing. Any tractability must come from the jump-penalty structure, not from fewer patterns.
The universality line supplies the deployment step. Adi Shamir et al. and Gal Vardi et al. show that ReLU units with suitable integer weights compute exact Boolean threshold logic. After rounding, each hidden unit is a linear threshold function of thermometer bits, and the network compiles exactly into lookup tables of the kind used by Differentiable Weightless Neural Networks and Differentiable Weightless Controllers.
Those two systems motivate the empirical question. Both train lookup-table networks over thermometer inputs with a surrogate gradient, the Extended Finite Difference estimator. Neither analyzes optimality. The controller paper reports training 3x to 7x slower than ordinary networks and a capacity bottleneck on HalfCheetah-v4. Distributive Thermometer places thresholds at empirical quantiles without using labels. Our solver turns threshold placement into part of the same convex problem.
Research Program
The theory has three parts.
- Structural lemma. We will prove the exact correspondences between thermometer-coded networks and sums of ReLUs of additive step models: first-layer weights equal jumps, weight decay equals the squared-jump penalty, and rounded jumps give exact threshold-logic compilation.
- One feature. We will attempt a dynamic program over sorted bins for the neuron-finding step. The state is the current step value's sign and the remaining norm budget, exploiting the tridiagonal penalty. If that fails, we will prove hardness in $B$ and give an algorithm exponential only in $B$.
- Several features. We will try to carry the levee reduction onto product grids to establish NP-hardness of the neuron-finding step. We will also prove the $\text{poly}(n)\cdot f(B,d)$ bound for bounded distinct inputs, and pursue a treewidth-parameterized algorithm in which the graph links features that co-occur in the optimal neuron's active region.
The algorithm built from this is column generation: repeatedly solve the convex problem restricted to the current neurons, then add the best new neuron. The new neuron is found exactly by the dynamic program or by a mixed-integer program over activation patterns when $n$ is small, and heuristically at scale. Each round also produces a dual lower bound, so the solver always reports a certified optimality gap.
Supervised threshold placement enters by starting from all distinct observed values as candidate thresholds. The jump penalty, optionally strengthened with an $\ell_1$ term, then selects which $B$ thresholds carry nonzero jumps. This addresses the label-informed binning question left open by Distributive Thermometer.
Baselines
The naive reference is a linear classifier on thermometer bits. This equals an additive step model with no interactions, which is exactly our solver stopped at zero hidden units plus a linear term. It is trained by convex optimization to its global optimum, so any gain must come from the hidden units. A second naive point is a two-layer ReLU network on raw standardized features trained with Adam. This shows whether encoding helps at all.
The most direct competitor on the optimization question is the identical architecture, a two-layer ReLU network on the same thermometer bits, trained with stochastic gradient descent and weight decay. It is the strongest test because the model class and objective are identical; only the optimizer differs. It gets the same thresholds, the same regularization strength, a width matched to the solver's final neuron count and also eight times wider, and a learning-rate and initialization search with the same wall-clock budget as the solver. It is beaten if the solver reaches a regularized training objective lower by more than the run-to-run spread of gradient descent across 10 seeds, with no loss in test accuracy.
The strongest existing system is the Differentiable Weightless Network of Bacellar et al., trained with the Extended Finite Difference estimator. It reports an average rank of 2.5 across 11 AutoGluon tabular datasets, against 3.4 for XGBoost and 3.6 for CatBoost. On EEG Eye State the relevant reported number is the Distributive Thermometer's 85.2% accuracy with a WiSARD network (Distributive Thermometer). We will rerun the DWN with its published configuration on our splits. Comparison is at equal compiled lookup-table count after rounding our network, with the same thermometer bits. Beating it means equal or better test accuracy at equal or smaller table count, or matching accuracy with lower training time.
XGBoost is included as the non-neural reference, with its default tuning budget matched.
The ablations isolate the key ingredient, the chain structure of thermometer codes. We run the same column-generation solver, with mixed-integer neuron finding, on positional binary and one-hot codes of the same bins. We also compare supervised threshold selection against quantile thresholds at equal $B$.
Why not just…?
Why not just train a wider network with gradient descent? This is the real threat. Matena and Raffel argue that overparameterization lets random initializations reach good activation patterns, so the gap may already be near zero. The proposal measures this rather than assuming it. If eight-times-wide gradient descent sits within 1% of the certified bound on every dataset, the practical claim collapses to the theory alone, and we will report it that way. The tractability result would then explain why gradient descent succeeds on these inputs.
Why not just apply the existing convex-dual algorithms of Wang and Pilanci? Their exact and approximate tractable regimes require orthogonal-separable or negatively correlated data (Polynomial-Time Solutions for ReLU Network Training). Thermometer codes are maximally positively correlated. Their generic method still enumerates activation patterns, which number $2^{B+1}$ even for one feature. The ablation on one-hot and positional codes shows whether the chain structure, not convexity alone, produces the speedup.
Why not just use boosted trees, or pick thresholds from tree split points? Trees with depth-one splits produce additive step models, which is our naive baseline. Deeper trees produce a different hardware form factor from the parallel lookups that compile into FPGA tables (Differentiable Weightless Controllers). Tree split points are a reasonable threshold heuristic, and we include them as a third threshold-placement arm alongside quantiles and our supervised selection.
Proposed Experiments
The data are the nine UCI datasets of Distributive Thermometer, including Glass, Ecoli and EEG Eye State. We add the 11 AutoGluon tabular datasets used by Differentiable Weightless Neural Networks, and a thermometer-coded subset of MuJoCo observation logs from Differentiable Weightless Controllers as a regression target for behavior cloning. Metrics are:
- regularized training objective and certified optimality gap;
- test accuracy or mean squared error;
- compiled lookup-table count after rounding, and accuracy lost to rounding;
- solver and baseline wall-clock time.
Three checks decide the outcome.
- Scaling of the neuron-finding step. On synthetic one-feature data with $B$ from 4 to 256, solve time should grow polynomially if the dynamic-program conjecture holds. On two-feature product grids it should blow up, consistent with a hardness reduction.
- The optimality gap. On subsets with $n \le 2000$, where the mixed-integer neuron finder finishes, we report the gap of gradient descent and of the DWN at matched encoding. A gap above a few percent on most datasets would confirm that optimization, not capacity, limits these models.
- Code ablation. At fixed $n$, positional and one-hot codes should make exact solving markedly slower than thermometer codes.
If check 1 fails, so that one-feature thermometer training is also exponential in $B$, we report that hardness result and keep the solver as a small-scale measurement tool.
References
- Training Neural Networks is NP-Hard in Fixed Dimension
- Training Fully Connected Neural Networks is $\exists\mathbb{R}$-Complete
- Training Neural Networks is ER-complete
- On the Hardness of Training Deep Neural Networks Discretely
- Polynomial-Time Solutions for ReLU Network Training: A Complexity Classification via Max-Cut and Zonotopes
- A Combinatorial Perspective on the Optimization of Shallow ReLU Networks
- How to Securely Implement Cryptography in Deep Neural Networks
- Neural Networks with Small Weights and Depth-Separation Barriers
- Differentiable Weightless Neural Networks
- Differentiable Weightless Controllers: Learning Logic Circuits for Continuous Control
- Distributive Thermometer: A New Unary Encoding for Weightless Neural Networks