The Conflict Between Logic and Memory: Learning Higher-Order Interactions in Shallow MLPs

Gongyue Zhang; Honghai Liu

cs.LGSep 30, 2026

The Conflict Between Logic and Memory: Learning Higher-Order Interactions in Shallow MLPs

Authors: Gongyue Zhang, Honghai Liu

Abstract

A network can fit its training examples while failing to recover the rule that generated their labels. We examine this separation in single-hidden-layer multilayer perceptrons (MLPs), using synthetic tasks that control interaction order and the presence of nuisance inputs. We establish elementary benchmark properties: pure parity contains no predictive lower-order marginals, admits an exact Bayes posterior, and can be represented on clean latent inputs by a width- $k$ ReLU network. Experiments then identify distinct optimization outcomes. In a matched order-2--4 sweep, SGD, Adam, and Muon all reach 100% peak test accuracy at order two; at order three they reach 96.25%, 50.87%, and 76.82%, respectively, while Muon reaches 99.21% at order four. In a separate mixed-order task, freezing only the first-layer weights connected to independent nuisance inputs raises AdamW's epoch-10 accuracy from 44.73% to 95.07%. Removing the same inputs only at test time raises it to 48.38%. Thus, nuisance-weight learning changes the training outcome beyond its immediate effect on prediction. Bias interventions expose a connection between target symmetry and shallow ReLU representations. In a compact signal-only regime, both SGD and Muon learn orders five through eight, with higher SGD peak accuracy at orders nine through eleven. Together, the results show how optimization and nuisance learning constrain the higher-order rules realized by a shallow network.

Figures & tables

Question	Input $\rightarrow$ output	Epoch budget	Selection
Order 2–4	$3124\rightarrow 2$	200	Common 13-rate grid
Noise intervention	$3124\rightarrow 8$	20	Fixed LR $0.05$ , epoch 10
Bias, orders 3–4	$3124\rightarrow 2$	300	Four rates per optimizer
Signal-only, orders 5–20	$32\rightarrow 2$	200	Four rates per optimizer

Table 1: Experiment sequence. All networks have one 64-unit ReLU hidden layer. The input regimes and outputs differ as indicated.

Figure 1: Fitting and rule generalization separate at order three. (a) Peak test accuracy from the common rate grid for the matched pure tasks. (b) Raw order-three trajectories at the selected rates: SGD 0.2, Adam 0.01, and Muon 0.02. Solid lines show test accuracy; dashed lines show online training accuracy. Muon’s line ends at its recorded loss-threshold termination. Peaks are descriptive selections from seed 42; the selected runs and epochs appear in Appendix B .

Figure 2: Nuisance learning affects the training trajectory. (a) AdamW factor-

C

accuracy under full, frozen-noise, and noise-absent training at learning rate 0.05. The full run terminates at epoch 12 under the experiment’s loss threshold. (b) Overall accuracy at the shared epoch 10. Test-time zeroing changes the input to the full-trained model; frozen training fixes the independent-noise weights throughout learning. The 60-dimensional spurious block remains present and trainable in every training condition.

Optimizer	Full	Test zero	Frozen	$C$ : full	$C$ : frozen
AdamW	44.73	48.38	95.07	50.07	97.49
SGD	96.86	97.79	98.22	98.01	99.10
Shampoo	96.90	97.71	98.28	97.99	99.12

Table 2: Interventions compared at the same epoch. Epoch-10 accuracies (%) in the mixed task. Full, Test zero, and Frozen are overall eight-class accuracies; the last two columns report factor-

C

accuracy. Every row uses learning rate 0.05 and seed 42.

Figure 3: Bias availability affects order three and order four differently. Peak test accuracy over the specified four-rate grids in the 300-epoch bias experiment. Zero init. and Default init. both permit bias learning; No bias removes it. An asterisk marks a selected run that later met the experiment’s divergence criterion. Results belong to this controlled bias experiment and are not changes relative to Figure 1 ’s separate sweep.

Figure 4: Higher-order capacity and realized generalization. (a) Peak test accuracy over the compact-task rate grids, with the generator’s Bayes oracle evaluated on the test observations. (b,c) Raw trajectories for the selected runs at orders 9 and 11. Solid lines show test accuracy and dashed lines online training accuracy; blue is SGD and purple is Muon. At order 9 the rates are 0.05 and 0.01, respectively; at order 11 they are 0.05 and 0.005. The entire order-5–20 sweep is included, including the near-chance regime.

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

$k$	Optimizer	LR	Peak (%)	Epoch	Run status
2	Adam	0.005	100.00	45	ok
2	Muon	0.5	100.00	4	diverged
2	SGD	0.5	100.00	1	ok
3	Adam	0.01	50.87	12	ok
3	Muon	0.02	76.82	118	diverged
3	SGD	0.2	96.25	181	ok

Appendix

Table 3: Selections for Figure 1 . Diverged indicates a run stopped under the recorded divergence rule after or at its selected peak; it does not mean the peak is a terminal stable solution.

$k$	SGD peak (%)	Muon peak (%)	SGD LR	Muon LR
5	100.00	100.00	0.05	0.005
6	99.96	99.99	0.05	0.005
7	99.27	98.63	0.05	0.005
8	98.11	97.78	0.05	0.005
9	92.42	86.29	0.05	0.01
10	82.75	75.57	0.05	0.005

Appendix

Table 4: Complete compact order sweep underlying Figure 4 . Rates are selected using peak test accuracy. All selected runs in this table completed their 200-epoch budget.

Explore similar work

Implicit Bias of SGD in Multivariate ReLU Networks: Effective Width Collapse
Jul 3, 2026Shuang Liang, Tom Jacobs, Guido MontúfarRectified Linear Unit Networks Stochastic Gradient Descent
Department of Statistics & Data Science University of California, Los Angeles Los Angeles, CA 90095, USA · CISPA Helmholtz Center for Information Security · Departments of Mathematics and Statistics & Data Science University of California, Los Angeles; and Max Planck Institute for Mathematics in the Sciences
Revenge of Monosemanticity: Neuron Specialization as a New Form of Feature Learning in MLPs
Aug 25, 2026Amirhesam Abedsoltan, Enric Boix-Adsera, Fivos Kalogiannis +1Feature Learning Multilayer Perceptrons
Department of Computer Science and Engineering, UC San Diego · Department of Statistics and Data Science, The Wharton School, University of Pennsylvania · Halıcıoğlu Data Science Institute, UC San Diego
Let the Neurons Die: Exploiting ReLU-Induced Model Degradation
Sep 28, 2026Kexin Li, Wenjun Qiu, Joshua Abraham +2Rectified Linear Unit Networks Neurons
University of Toronto, Toronto, Ontario, Canada

Jul 3, 2026, cs.LGJ/K move · Enter open · S save

Implicit Bias of SGD in Multivariate ReLU Networks: Effective Width Collapse

Shuang Liang, Tom Jacobs, Guido Montúfar

Department of Statistics & Data Science University of California, Los Angeles Los Angeles, CA 90095, USA · CISPA Helmholtz Center for Information Security · Departments of Mathematics and Statistics & Data Science University of California, Los Angeles; and Max Planck Institute for Mathematics in the Sciences

Rectified Linear Unit Networks Stochastic Gradient Descent Gradient Mean-Field Limit Representation Collapse

Open paper AskPDF arXiv

We study the implicit bias of noisy stochastic gradient descent in training wide two-layer ReLU networks for multivariate regression. In a mean-field regime, the training dynamics are approximated by a Wasserstein gradient flow that converges to a unique stationary measure. We characterize the structure of this stationary measure and the predictor it represents. We show that, despite the network being infinitely overparameterized, the learned predictor admits an effectively finite representation: the input weights and biases align along finitely many directions, leading to an effective width collapse. In particular, the solution function is continuous piecewise affine, with affine regions determined by the cells of a finite hyperplane arrangement. The number of learned directions, and hence hyperplanes, is bounded above by

2\mathcal{P}-1

, where

\mathcal{P}

denotes the number of linear dichotomies realizable on the training inputs. We further establish a non-redundancy property of the learned representation by proving that each learned direction induces a unique ternary activation pattern on the training data. Consequently, the complexity of the learned predictor is governed by the combinatorial geometry of the training data.

Abstract

Explore similar work

Implicit Bias of SGD in Multivariate ReLU Networks: Effective Width Collapse

Revenge of Monosemanticity: Neuron Specialization as a New Form of Feature Learning in MLPs

Let the Neurons Die: Exploiting ReLU-Induced Model Degradation