Composing Global Solutions to Reasoning Tasks via Algebraic Objects in Neural Nets
Authors: Yuandong Tian
Venue: NeurIPS 2025 poster ()
Keywords: landscape analysis
modular addition; gradient dynamics; reasoning; symmetry; representation learning
Primary area: theory
TL;DR: Semi-ring structure exists in 2-layer neural nets for reasoning tasks on Abelian group (e.g., modular addition), trained with L2 loss, which enables constructing global solutions analytically from non-optimal ones instead of gradient descent.

Abstract: We prove rich algebraic structures of the solution space for 2-layer neural networks with quadratic activation and $L_2$ loss, trained on reasoning tasks in Abelian group (e.g., modular addition). Such a rich structure enables \emph{analytical} construction of global optimal solutions from partial solutions that only satisfy part of the loss, despite its high nonlinearity. We coin the framework as \ours{} (\emph{\underline{Co}mposing \underline{G}lobal \underline{S}olutions}). Specifically, we show that the weight space over different numbers of hidden nodes of the 2-layer network is equipped with a semi-ring algebraic structure, and the loss function to be optimized consists of \emph{sum potentials}, which are ring homomorphisms, allowing partial solutions to be composed into global ones by ring addition and multiplication. Our experiments show that around $95\%$ of the solutions obtained by gradient descent match exactly our theoretical constructions. Although the global solutions constructed only required a small number of hidden nodes, our analysis on gradient dynamics shows that overparameterization asymptotically decouples training dynamics and is beneficial. We further show that training dynamics favors simpler solutions under weight decay, and thus high-order global solutions such as perfect memorization are unfavorable. The code is open sourced\footnote{\url{https://github.com/facebookresearch/luckmatters/tree/yuandong3/ssl/real-dataset}}.

Composing Global Solutions to Reasoning Tasks via Algebraic Objects in Neural Nets
Yuandong Tian
Meta Superintelligence Lab (FAIR) yuandonglmeta.com com
Abstract
We prove rich algebraic structures of the solution space for 2-layer neural networks with quadratic activation and L2 loss, trained on reasoning tasks in Abelian group (e.g., modular addition). Such a rich structure enables analytical construction of global optimal solutions from partial solutions that only satisfy part of the loss, despite its high nonlinearity. We coin the framework as CoGS (Composing Global Solutions). Specifically, we show that the weight space over different numbers of hidden nodes the 2-layer network equipped with a semi-ring algebraic structure, and the loss function to be optimized consists of potentials, which ring homomorphisms, allowing partial solutions to be composed into global ones by ring addition and multiplication. Our experiments show that around 95% of the solutions obtained by gradient descent match exactly our theoretical constructions. Although the global solutions constructed only required small number of hidden nodes, our analysis on gradient dynamics shows that overparameterization asymptotically decouples training dynamics and beneficial. We further show that training dynamics favors simpler solutions under weight decay, and thus high-order global solutions such perfect memorization are unfavorable. The code open sourced
1 Introduction
Large Language Models (LLMs) have shown impressive results in various disciplines (OpenAl 2024 Anthropic; Team 2024b a Dubey et al., 2024, Jiang et al. 2023), while they also make surprising mistakes in basic reasoning tasks (Nezhrria al. 2024 Berglund al. 2023). Therefore, it remains an open problem whether it can truly do reasoning tasks. On one hand, existing works demonstrate learn efficient algorithms (e.g., dynamic programming (Ye al.
that the models
(024) for
language structure modeling, etc) and good representations (Jin & Rinard [024]] Wijmans et al.
2023). Some reports emergent behaviors (Wei al. (022) when scaling up with data and model size.
On the other hand, many works also show that LLMs cannot self-correct (Huang et al. 2002)) and
cannot generalize very well beyond the training set for simple tasks (Dziri et al.[]2023] Yehudai et al.
2024 Ouellette et al. 2023). let alone complicated planning tasks (Kambhampati et al. 2024 Xie 2024).
To understand how the model performs reasoning and further improve its reasoning power, people have been studying simple arithmetic reasoning problems in depth. Modular addition (Nanda et al.) 2023 Zhong et al. 2024), i.c., predicting a mod d given a and b, is a popular one due to its simple and intuitive structure yet surprising behaviors in learning dynamics (e.g., grokking (Power
let al. 2022) and learned representations (e.g., Fourier bases (Zhou et al., 2024 Most works focus various metrics to measure the behaviors and extracting interpretable circuits from trained models (Nanda et al. 2023; Varma et al. 2023: Huang et al., (022)) Analytic solutions can be
constructed and/or reverse-engineered (Gromov 2023 Zhong et al. [ Nanda et 2023) but
is not clear how to construct a systematic framework to explain and generalize the results.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

In this work, we systematically analyze 2-layer neural networks with quadratic activation and L2 loss on predicting the outcome of group multiplication in Abelian group G, which is an extension of modular addition. We find that global solutions can be constructed algebraically from small partial solutions that are optimal only for parts of the loss. We achieve this by showing that (1) for the 2-layer network, there exists semi-ring structure over the weights space across different order (i.e., number of hidden nodes or network width), with specifically defined addition and multiplication (Sec. D. and (2) the L2 loss is a function of sum potentials (SPs), which are ring homomorphisms (Theorem D that allow compositions of partial solutions into global ones using ring operations.
As result, our theoretical framework, named CoGS (i.e., Composing Global Solutions), successfully constructs two distinct types of Fourier-based global solutions of per-frequency order (or "2 2")) and order 6 (or "2 x 3"), and global solution of order df that correspond to perfect memorization. Empirically, we demonstrate that around 95% of the solutions obtained from gradient descent (with weight decay) have the predicted structure and match exactly with our theoretical construction of order-4 and order-6 solutions. In addition, we also analyze the training dynamics, and show that the dynamics favors low-order global solutions, since global solutions algebraically connected by ring multiplication can be proven to also be topologically connected. Therefore, high-order solution like perfect memorization is unfavorable in the dynamics. When the network width goes to infinity, the dynamics of sum potentials becomes decoupled, demystifying why overparameterization improves the performance.
To our best knowledge, we are the first to discover such algebraic structures inside network training. apply it to analyze solutions to reasoning tasks such as modular additions, and show our theoretical constructions occur actual gradient descent solutions.
2 Related Works
Algebraic structures for maching learning. Many works leverage symmetry and group structure in deep learning. For example, in geometric deep learning, different forms of symmetry are incorporated into network architectures (Bronstein et al., 202T). However, they do not open the black box and explore the algebraic structures of the network itself during training.
2022) gives explicit Expressibility. Existing works on expressibility (Li et al. 2024 Liu et al.
weight construction of neural networks weights (e.g.. Transformers) for reasoning tasks like automata, which includes modular addition. However, their works do not discover algebraic structures in the weight space and loss, nor learning dynamics analysis, and it is not clear whether the constructed weights coincide with the actual solutions found by gradient descent, even in synthetic data.
Fourier Bases in Arithmetic Tasks. Existing works discovered that pre-trained models use Fourier bases for arithmetic operations (Zhou et al., 2024). This is true even for simple Transformer, or even a network with one hidden layer (Morwani et al., 2023). Previous works also construct analytic Fourier solutions (Gromov 2023) for modular addition, but with the additional assumption of infinite width, unaware of the algebraic structures we discover. Existing theoretical work (Morwani et al. 2023) also shows theorrtteatt results algebraic tasks related to finite groups, also for networks with one-hidden layers and quadratic activations. Compared to ours, they use the max- margin framework with special regularization (L2.a norm) rather than L2 loss, do not characterize and leverage algebraic structures in the weight space, and do not analyze the training dynamics.
3 Lg Loss Decoupling for Abelian group
Basic group theory. A set G forms a group, which means that (1) there exists an operation (i.e., "multiplication") ) G x G + G and it satisfies association: (g) 992) So = 91' (g2 1 ga). Often write 9192 instead of 91 92 for brevity. (2) there exists an identity element e E G so that eg = ge- g. (3) for every group element g E G. there is unique inverse g -1 that gg -1
g -g = In some groups, the multiplication operation is commutative, i.e., gh = hg for any g, h E G. Such groups are called Abelian group. Modular addition forms a Abelian (more specifically, cyclic) group by noticing that there exists a mapping + 2wai/ and + b mod d is 2mai/d _2xbi// (nj04/
Basic Ring theory. A set 2 forms a ring, there exists two operations, addition + and multiplication so that (1) (2,4 +) forms an Abelian group, (2) (Z. +) is a monoid (i.e., a group without inverse). and (3) multiplication distributes with addition (i.e., a* (b + e) = a a& + a e and (b-c) c) + = bea + c*aa.
Z is called a semi-ring if (Z, +) is monoid.
2

---

Neural Architecture
Teglg and kpkg (z) are ring hongmommmsssss
(2, +,+ is semi-ring
Partial Eays
sol
n butzen
*
Compositing solutions ring muttiplcation
Highly nontingar!
Loss Function
MSE loss (2) d Eiso (2(2) +
1/d
Better solution
(,(+) - 2
Σ
E
E
R R, n,,
Composting solutiions using ring addition
Sufficient Conditions of Global Solutions:
Global Solutioon MSE loss
R
Ri
R
Constraints
TO
Figure I: Overview of proposed theoretical framework CoGS. (1) The family of 2-layer neural networks, 2, form semi-ring algebraic structure (Theorem 2 with ring addition and multiplication (Def. 5). 2 - 1و20 Eg where 2, is collection all weights with order-q (i.e., q hidden nodes). (2) For outcome prediction of Abelian group multiplication, the MSE loss (()) ) is function of sum potentials (SPs) Tk ky (z) and Ap (z) (Theorem D. which are ring homomorphisms (Theorem B). (3) Thanks to the property of ring bomomorphism, global solutions to MSE loss {(z) with quadratic activation can be constructed algebraically from partial solutions that only satisfy subset of constraints (Sec. [S] using ring addition and multiplication, instead of running gradient descent. Examples include Fourier solution zFG (Corollary) 2 and z (Corollary and perfect memorization solution z (Corollary 33 In Sec. [6] we analyze the role played of SPs in gradient dynamics, showing that the dynamics favors low-order global solutions (Theorem (S) under weight decay regularization, and the dynamics of SPs become decoupled with infinite width (Theorem In Sec. 7 we show that the gradient descent solutions match exactly with our thcoretical construction.
Notation. Let be the real field and C be the complex field. For a complex vector z, 2 is its transpose, 2 is its complex conjugate and z" its conjugate transpose. For tensor Zijks 2.jk vector along its first dimension, 21.k along its second dimension, and 2ij. along its last dimension.
Problem Setup. We consider the following 2-layer networks with g hidden nodes, trained with (projected) &g loss on prediction of group multiplication Abelian group G with |G|
t=
Σ
||
ptt
2 - eija) ||
oli] = Σ Wejo E.ll + Way eg2is)
(I)
2d
Input and Output. The input contains the two group elements 9n 92] E G to be multiplied,
li Gg2l Rd are one-hot representation of gi [i] and ga[t]. Here the sample index. The target
ei(] one-hot representation of [[i] 91 [i]g2 G, the group product of g1 [i] and gzld].
Architectures. In Eqn. I we quadratic activation (xx) = x² Du & Lee 2018 Allen- Zhu & Li
P = -- 1111 is the zero-mean projection, Waj, Waj- Wej Rd are learnable parameters I S q) Note that variants of quadratic activation have been used empirically, e.g. squared ReLU and gated activations (So et al. 2021 Shazeer 2020; Zhang et al. 2024).
2023
We extend framework group action prediction, in which 92 may not be group element but any object (e.g., discrete state in reinforcement learning). See Appendix
Let Φb |dx (g) Od be the scaled Fourier bases (or more formally, character function of the finite Abelian group G, see Appendix B). Then the weight vector W := {W,} can written as:
Waj
Σ k-
Zaki De.
Woj
Σ App50
Ebky OR
W
Σ Rorg Φx
where = } are the complex coefficients, p E (a, hidden nodes. For convenience, we define s = Φx as the (complex) conjugate representation of db. We exclude Φ because the constant bias term has been filtered out by the top-down gradient from the loss function. Leveraging the property quadratic activation functions, we can write down the loss function analytically (see Appendix
d and j runs through

---

Theorem 1 (Analytic form of L2 loss with quadratic activation). The objective of 2- 2-layer MLP network with quadratic activation can be written d'' Ekyo lx + (d 1)/d. where
b. = -
ETAAe Σ
pp m k(, Σ k²
(3)
k2
PE(a,b) Ky
mzF0 (a,b)
Here Pkykak = Ej Pakij Fbk2) (asks)Ree Rekj and Tpkikzk
Ej 2 Spkaj
Note that for cyclic group G, the frequency k is mod-d integer. For general Abelian group which can be decomposed into a direct sum of cyclic groups according to Fundamental Theorem of Finite Abelian Groups (Diaconis 1988), k is multidimensional frequency index. Since {Wpih } are all real,
the Hermitian constraints hold, i.e. Enkj Φ Waj &ej Wej
Zc,-ki (and similar for žakj and =. Therefore, kp = Epkj. r-k, = Tkkk and f is real and can be minimized.
Eqn. contains different terms, which play important role in determining global solutions.
Definition 1 (0/1-set), Let R == {r} be a collection of terms. The weight is said to have O-set Rg and 1-set R1 (or 0/1-sets (Ro, R1)), if) for all E Ro and r(z) for all E R1.
With 0/1-sets, we can characterize rough structures of the global solutions to the loss: Lemma 1 (A Sufficient Conditions of Global Solutions of Eqn. 3 If the weight z to Eqn. has O-sets Re Rn U R. and 1-set Rg. i.e.
[= = 1(k + 0), Tkik2k(Z) =0, Tpkikzk(2)=
(4)
then it is a global solution with {(z) O. Here Rg == (TuNAs K + 0}. (Tkkkzks k1, k2, k not all equal}, R2 == - and R. == (Tpp k. m 0}.
Re
Lemma ! provides sufficient conditions since there may exist solutions that achieve global optimum (e.g., Ex' "p.
but mm. (=) * 0). However, we will see, it already leads to rich algebraic structure, and serves as a good starting point. Directly finding the global solutions using Eqn. 4 4can be bit complicated and highly non-intuitive, due highly nonlinear structure of Eqn. 3. However, there are nice structures we can leverage, as we will demonstrate below.
Algebraic Property of the Weight Space
We define the weight space Z, = {z} to include all the weight matrices with hidden nodes (Zo means an empty network), and 2 = Ug20
920 2g be the solution space of all different number of hidden nodes. Interestingly, naturally is equipped with semi-ring structure, and each term of the loss function can effective interact with such a semi-ring structure, yielding provable global solutions. including both the Fourier solutions empirically reported in previous works (Zhou al. 2024 Gromov 2023). and the perfect memorization solution (Morwani et al. 2023).
To formalize argument, start with few definitions.
Definition 2 (Order of 2). The order (rd(2) of E Z is its number of hidden nodes. Definition 3 (Scalar multiplication). az E Z is element-wise multiplication [orzpks] of 2 E Z. Definition 4 (Identification of 2). In Z, two solutions of the same order that differ only by permutation along hidden dimension j are considered identical.
We define operations for 21 : (2 and 22 = pk J:
(2) (
Definition 5 (Addition and Multiplication in 2). Define
21 22 in which 2pk- _(2) and 2 22, in which zpk- == pp. & pp.. The addition and multiplication concat(z 2p pp.
(2)
respect Hermitian constraints and the identity element 1 is the 1-order solutions with {žpAo = 1}.
Note that the multiplication definition one special case Khatri-Rao product (Khatri & Rao 1968). Although the Kronecker product and concatenation not commutative, thanks to the identification (Def. 4.. it is clear that z1 + Ø2 x2 + 21 and 2 * x2 = 22 * Æ and thus both operations are commutative. Then we can show:
Theorem 2 (Algebraic Structure of Z). (Z, *) is commutative semi-ring.

---

As we shall see, Thm. alloww the construction of global solutions. Now let us explore the structure of the loss (Eqn. B. which turns out to be connected with the semi-ring structure of Z. For this, we first define the concept of sum potentials:
Definition 6 (Sum potential (SP)). Lel sum potential be rer())== == Eg II kEidx((() Fpkj which takes the summation of monomial term over all hidden nodes. Here idx(() specifies the terms involved.
Following this definition, terms in the loss function (Theorem are examples of SPs. Observation 1 (Specitic SPs). (z) and "pk,kzk(2 defined Theorem are SPs.
So what is the relationship between SPs, which functions that map weight z to complex scalar, and the semi-ring structure 2? The following theorem tells that SPs are ring homomorphisms, that is, these mappings respect addition and multiplication:
Theorem 3. For any potential r Z + C, r(1) 1, r(z1 + x2) =((z)) + r(z2) and r(21 * 22) = ((2))((2)))))) and thus r is ring homomorphism.
Observation 2. The order function ord : 2 + N is also a ring homomorphism.
Since the loss function {(z) depends on the weight x entirely through Tki Tke Makkk (z)) and rppa (z)
which are SPs, due to the property of ring homomorphism, it is possible to construct a global solution from partial solutions that satisfy only some of the constraints
Lemma 2 (Composing Partial Solutions). 2 1 has 0/1-sets (Rī RT) and z2 has 0/1-sets (R.z R ). then (1) 22 has 0/I-sets (RT U Rig R n R2t)) and (2) 21 22 have 0/1-sets (Rı n R (Rf n
R U (RT n )R
Once we reach 0/1-sets (Re U Rn U R., Rg), we find a global solution. In addition, we also immediately know that there exists infinitely many global solutions, via ring multiplication (Def. 55): Definition 7 (Unit). is a unit if (xsx((2) (z) for all ls & O.
Corollary 1. If is a global solution and y is a unit, then y is also a global solution.
5 Composing Global Solutions
Constructing Partial Solutions with Polynomials. While intuitively one can get global solutions by manually crafting some partial solutions and combining, in this section, we provide more systematic approach to compose global solutions as follows. Since 2 enjoys a semi-ring structure, we consider polynomial in Z:
2 u + C1 u t-1 c h-² ... + et
(5)
where the generator and coefficients C₁ are order-1 and the power operation u' is defined by ring multiplication. Then partial solution can be constructed:
Theorem 4 (Construction of partial solutions). Suppose u has 1-set RG, QR(u) := (r())rr e R} C C is set of evaluations on Rt (multiple values counted once), then if & QR. then the polynomial solution Pa(u) == II (u 8) has 0/1-set (R, R1) up to a scale. Here $ is any order-1 weight that satisfies r(5) = -5 for any T R U R4. For example, s -2/331
For convenience, we use p(u) to represent the maximal polynomial, i.e., when R arg mmxxggR(()) [u)) the largest subset of SPs with & (u)( Our goal is to find low-order (partial) solutions, since gradient descent prefers low order solutions (see Theorem (5). Although there exist high-degree but low-order polynomials, e.g., u + 1, in general, degree and order q are correlated, and we can find low-degree ones instead. To achieve that, u should be properly selected (e.g., symmetric weights) to create as many duplicate values (but not 1) in R as possible.
Composing Global Solutions. We first consider the case that the generator u is only nonzero at frequency (and thus -k by Hermitian constraints), but zero in other frequencies, i.c., Upkro for k' + tk. Such solutions correspond to Fourier bases in the original domain. Also, a has 1-set R1 (reEk). This means that u can be characterized by three numbers d,k0D Ubko, Meko with
Matteeaticallyy, the kernel Ker(r) == {x r(*) = 0} of a ring homomorphism is an ideal of the ring. and the intersection of ideals are still ideals. For brevity, we omit the formal definitions.
5

---

Evaluation on SPs
Re
Ru
R
Maximal polynomial p(u)
Symbol
aa. b,
abc abe abc
aac
bbc
aac
bbc
ade
bbc
order
1x
1, 1,
ig
[-1 1, 1,
Uone
[1 1,-11: -1 1
u + +
2
Mayn
Was wa, was
W3
W3
Wg
W3
1
W3
u
3
USc
Wa, Wa, 1
W3
W3
W3
W3
W3
W3
u u 144+1
3
M3a
1. wg. W3
W3
W3
u²
3
u.c
[1
2
U4a
11
u + u² +++1
4
Uy
-1, -
9-th degree
10
Table I: Exemplar order-1 single frequency generator u with Tkkk (u In the fingle-frquuency case, for each MP r we use "ābe" represent & and "āäc" represent Ta, R. ctc. For brevity, superscript
"(k)" and conjugate columns (i.e., abc conjugate to abe) omitted. Here, roots of unity. The constructions are partial, ie., the evaluation of some SPs yields 1 (red cell) and cannot be the root of the polynomial (Theorem Note that uu is general case with u
e 2w//3 and 4/ := i are 3rd/4th
Wone Uy=i Udc.
Fd
Figure 2: Solutions obtained by Adam optimizers on & loss for modular addition task with |G| and q 20 hidden nodes. Top: For each frequency tk, exactly 6 hidden nodes exist (Corollary)
Bottom:
Optimizing Eqn. without the term Σmyo Epe(u.a) Σ. Tp. mm- (i.e., without constraint R.).
Now each frequency has exactly hidden nodes, corresponding to the solution Zayn p p(usyn) in Tbl.
MakuMakoMeko 1. In this case, only subset of sum potentials (SPs) whose indices only involve a single frequency & are non-zero (e.g., -k,-k,k R. and rb,-k,k,k Ru), facilitating construction.
Following Theorem we can construct different partial solutions. Some examples are shown in T These solutions do not make all sum potentials in R. U R, U R. vanish and therefore are not global. Note that is possible create global solution this way, but then [(2r(u)] will be too large, producing high-degree/order polynomials (e.g., U4 U4j gives 10th-degree polynomial). Instead, utilizing these partial solutions, with Lemma we can construct global solutions with smaller orders:
Corollary 2 (Order-6 global solutions). The following "3 x 2 Fourier solutions satisfy the sufficient condition (Lemma) 7 and thus are global solutions when d is odd:
1d-1)/2
2r6
Σ
(K) syn * 20
(k)
yk
(6)
26
Here zeyn plu are defined in Table y is an order-1 unit. As result, ord(zr6) =
(k)
Uuvn and 2x))
(k)
uhy
(K) + 11 (i.e., not maximal polynomial), where Usyu and u. 1)/2 = 3(d 1)
and each frequency are affiliated with hidden nodes (order-6).
Remarks. We may replace Ugyn and u. with other pairs that collectively cover all SPs. For example, be coupled with Usa U4a etc. Uyyn can be combined with any of {uge Usa U4a and U.
Here we pick one with a small order. Compared to Gromov (202)), our construction is more concise without infinite-wiee approximation. For even d, simply replace (d 1)/2 with [d 1)/2 and add an additional order-2 2 term p(uone) = Uone + 1 (Tbl. I for frequency = d/2, which only has Tikk, Takkk and PbRRA, and all other combinations are absent.
Fig. 2 shows case with d = 7. In this case, each frequency, out (d 1)/2 total number of frequencies, is associated with 6 hidden nodes. If we remove the last term in the loss that corresponds

---

to Rx, then an order-3 solution suffices (i.e. Zayn = p(uayn)). Perfect- solutions
can also be constructed. Let two generators be uhe with u 40 = [w 1, a2]0(k & 0), and ug with (18) u.ko - [1, : (k)+) Here wid = 22r/dd is the d-th root of unity. Then, Corollary 3 (Perfect Memorization). We construct two d-order weights (Za, zz) from order-1 I generators (Ua, Uz):
d-1
d
Σ ==0
Σ
Za
B3
=
j=0
Here Za E Rc(k1 # R, (p. b m k), zS E Rk
R m + k).
Then 2M = dd za 2g satisfies the sufficient condition (Lemma) and is the perfect memorization solution with ord 2M) = d²:
(M) Zakjida
d Wh,
bbiiid
(M) d k0,
(M) ckinda w
(8)
where each hidden node indexed by j (1 f2). h1 < d. +
To see why this corresponds to perfect memorization, simply apply an inverse Fourier transform for each hidden node (j1-j2). which leads (zero-mean delta weights located j1. j2 and jı + J2- Interestingly, there also exists a lower-order solution, 2 x 2, that meets R. and R. but not R,;
Corollary (Order-4 single frequency solution). Define single frequency order-2 solution xç:
Zak- [1,5], Zbk- -iE); Zek- = [1.i]
where [5] 1. Then the order-4 solution 2F4 == p( 2 (k) has 0-sets Re and R. (but not Ra).
Although ((k) does not satisfy the sufficient condition (Eqn.44) it is part of global solution when z44 mixed with Zpp:
Corollary (Mixed order-4/6 global solutions). With (R) there is a global solution to Equ. that P4
does not meet the sufficient condition, i.e., Ex Tp, 0 but Tp. , m # 0:
(d-1)/2 Σ
(k))
FF4/6 = 36 FG
F4
(10)
k= I,k
where (Ko) is a perturbation of #FG zayn
(ko)
(ka)
(ka) by adding constant biases to its (c, k) entries
for l + kg- The order is lower than z56: ord(2F4/6) = 6 + 4 ((d 1)/2 - 1) = 2d < ord()
FG The specific formats of (No) is shown in Appendix (please check the proof and Equ. 68p. Multiple
order-6 solutions per frequency can be inserted in this construction. Compared to z this order-4/6 mixture solution has lower order and perceived the experiments (See Fig. 6 in particular when d is large (Tbl. 2 showing a strong preference of gradient descent towards lower order solutions.
Exploring the solution solution with Gradient dynamics
Now we have characterized the structures of global solutions. One natural question arises: why does the optimization procedure not converge to the perfect memorization solution zas, but to the Fourier solutions 2P6 and F4//6? Although characterizing the full gradient dynamics is beyond the scope of this paper, we theoretically characterize some rough behaviors below.
Corollary T shows that by ring multiplication, we could create infinitely many global solutions from one. Then Thm. T answers which solution the gradient dynamics may pick:
Theorem 5 (The Occam's 's Razer: Preference of low-ordd oow-rrder solutions). If z= = y
x' and both z (of order q) and z' are global optimul solutions, then there exists a path of zero loss connecting z and z' in the space of Zy. As result, lower-order solutions are preferred if trained with Lo2 regularization.
This shows that gradient dynamics (with weight decay) may pick lower-order (i.e., simpler) solution. This suggests that gradient dynamics may not favor perfect memorization, which is of high order. We leave it future work to prove the existence of a path that connects perfect memorization solutions with lower-order one. The following theorem shows that the dynamics enjoys asymptotic freedom:
7

---

diughfl--sg Paatt
12.
1.0
9.8 Joan
Survenc
10
0.-
3.0
120
10
103
301
incresses ordar-4 solution
vansshes orden-5 solaton
varisnes both order and orden-
0.100
0.4
5,500
1-
0.2
6.300
6:025
Exery
Figure 3: Dynamics of sum potentials (SPs) over the training process for modular addition with d 23 and q = 1024 hidden nodes. Top Row. Left: Training/test accuracy reaches 100% and loss close to 0. Test accuracy jumps after training reaches 100% (grokking). Mid: After 10k epochs, the distribution solution orders are concentrated at 4 and 6 (Corollary [Conollary[Jand]) Right: Dynamics of Tk, k2t- Summation of diagonal TRRK converges towards d' 1 (dotted line) with ripple effects, while off -d-iggoonal &yy converges towards O. Boftom Row, Dynamics of different SPs. Order-4 and order-6 behave differently on -k because order-4 does not satisfy the sufficient condition (Lemma IT but mixture of order-4 and order-6 (i.e., #F4/6) is still the global solution to the L2 loss (Corollary5) 5)
d-23, wd-1n-05
d+23, wd-See05
d-23, www0.0000 0.000
d-23, wd=0.0002 0.002
d+23, wdw..d0000. 0005
Counts
20-
20
20-
18
19
dm71,, wd-1e-05
d=71, wid 56-05
dm71, wdw 0001
dm7),, ad=0.0007
d= wdw 0005
Coints
100
100
100
30
127, wdm1e-05
dm127. 5d-5e-05
wd-0.0005
Connt
200
200
100
Figure 4: Solution distribution (accumulated over 5 random seeds) over different weight decay regularization for q = 512, trained with 10k epochs with Adam with learning rate 0.01 on modular addition (i.c., predicting a + mod d) with E {23, 71, 127}. Red dashed lines correspond to order-4/6 solutions.
Theorem 6 (Infinite Width Limits at Initialization). Considering the modified loss of Eqn. J only the first two terms: &s := -2 + +K ky [rk,k2kl?, the weights are i.i.d Gaussian and network width + +00, then JJ converge to diagonal and the dynamics of SPs is decoupled.
Intuitively, this means that a large enough network width (q + +00) makes the dynamics much easier to analyze. On the other hand, the final solution may not require that large q. As analyzed in Corollary 2 for each frequency, to achieve global optimality, hidden nodes suffice.
7 Experiments
Setup. We train the 2-layer MI.P on the modular addition task, which is special case of outcome prediction of Abelian group multiplication. We use Adam optimizer with learning rate 0.01, MSE loss, and train for 10000 epochs with weight decays. We tested on |G| data are generated synthetically and training/test split is 90% 10%. Each training with a fixed set of hyperparameter configuration is conducted on NVIDIA V100 for few minutes.
{23, 71, 127). All
Solution Distributions. As shown in Fig. 3 we see order-4 and order-6 solutions in each frequency emerging from well-trained networks on d 23. The mixed solution F4/6 can be clearly observed in a small-scale example (Fig. ( This is also true for larger d (Fig. 4). Although the model is trained with heavily over-parameterized networks, the final solution order remains constant, which consistent with Corollary [ Large weight decay shifts the distribution to the left (i.e., low-order solutions) until model collapses (i.c., all weights become zero), consistent with our Theorem 5 that
8

---

%not
fenon-factorabl
error
(x10-3) 3)
solution distribution (%) in factorable ones
order-4/6
order-4
order-6
order-4
order-6
=
(k)
= ayy..
others
23
0.0=0.0
0.00
7.71
0,05
47.07 0.80
11
39.80+2 11
1.82
71
0.0
0.00
0.03 0.00=0.00
72.57 2.
1.00=1.14
21.14+2.14
2.29
127
0.0=a.0
1.50=a.02
0...0..0000000000 0.00=00.0
0..6
0.93
02.96+0.33
2.25=0.64
11.13+0.87
0.66
Table 2: Matches between order-4/6 solutions from gradient descent and those constructed by CoGS. Number
of hidden nodes = 512 and weight decay is 5 x 10-5. Around 95% gradient descent solutions are factorable with very small factorization error (~ 0.04 compared solution norm the order of 1). Furthermore, CoGS successfully predicts ~ 98% of the structure of the empirical solutions, while the remaining 2% are largely due to insufficient training, near miss against known theoretical construction. Here zg is defined in Corollary 4 Zo == uy + 1 is defined in Tbl. 1 and Zuy is defined in Eqn. 68 The mtanda/t deviations are computed over 5 seeds.
demonstrates that gradient descent with weight decay favors low-order solutions. Similar conclusions follow for fewer and more overparameterizatioo (Appendix [].
Exact match between theoretical construction and empirical solutions. A follow-up question arises: do the empirical solutions match exactly with our constructions? After all, distribution of solution order is a rough metric. For this, we identify all solutions obtained by gradient descent at each frequency, factorize them and compare with theoretical construction up to conjugation/oormaiizaaiio. To find such a factorization, we use exhaustive search (Appendix D
The answer is yes. Tbl. 2 shows that around 95% of order-4 and order-6 solutions from gradient descent can be factorized into 2 2 and 2 x 3 and each component matches our theoretical construction in Corollary 2 and 4 with minor variations. Furthermore, when d is large, most of the solutions become order-4, which is consistent with our analysis for mixed solution 2F4/0 (Corollary 5) that one 6 solution in the form of Zy=i 2syn,a.3 suffices achieve global solution, with all other frequencies taking order-4s. In fact, for d = 127, the number of order-6 solution taking the form of Zumi Zsy is (d 1)/2 2.25% RJ 1.26, coinciding with the theoretical results.
Implicit Bias of gradient descent. Our construction gives other possible solutions (e.g., 23c Zayn) which are never observed in the gradient solutions. Even for the observed solutions, e.g. Zy Zsyn. the distribution of free parameters is highly non-uniform (see Fig. [2 in Appendix), showing a strong preference of parameters that lead to symmetry. These suggest strong implicit bias in optimization, which we leave for future work.
8 Conclusion and future work
In this work, propose CoGS (Composing Global Solutions), a theoretical framework that models the algebraic structure of global solutions when training a 2-layer network on reasoning tasks of Abelian group with L2 loss. We find that the global solutions can be algebraically composed by partial solutions that only fit parts of the loss, using ring operations defined in the weight space of the 2-layer neural networks across different network widths. Under CoGS, also analyze the training dynamics, show the benefit of over- parameterization, and the inductive bias towards simpler solutions due to topological connectivity between algebraically linked high-order (i.c., involving more hidden nodes) and low-order global solutions. Finally, we show that the gradient descent solutions exactly match what constructed solutions (e.g. F/4/ and zys, see Corollary and Corollary 2
Develop novel training algorithms. Instead of applying (stochastic) gradient descent to overpa- rameterized networks, CoGS suggests completely different path: decompose the loss, find the SPs, construct low-order solutions and combine them to achieve the final solutions on the fly using algebraic operations. Such an approach may be more efficient and scalable than gradient descent, due to its factorable nature. Also, our framework works for losses depending on sum potentials (T-2 loss just one example), which opens a new dimension for loss design.
Putting different widths into the same framework. Many existing thcoretical works study proper- ties of networks with fixed width. However, CoGS demonstrates that nice mathematical structures emerge when putting networks of different widths together, which is an interesting direction to consider. This is related to dynamically adding/pruning neurons during training Yoon et al. (2017)
Yu et al. (018); Wu et al. (2019).
Grokking. When learning modular addition, there exists a phase transition from memorization to generalization during training, known as grokking (Varma et al. 2023) Power et al.) (022). long after the training performance becomes (almost) perfect. While our work does not directly address

---

grokking, which involves more complicated training dynamics than described in Sec. 6 our framework may be extended nonuniformly distributed training set (e.g. some input pairs (g), 92) are missing in the training set), in order to study the dynamics of representation learning on grokking.
Extending to other activations and loss functions. For other activations (e.g., SiLU) with (0) 0, with a Taylor expansion, the same framework may still apply, but with higher rank sum potentials (SPs). For other loss functions, can do similar Taylor expansion. We leave them for future work.
10

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification:
We have tried out best to write the abstract and introduction accurately.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: We have discussed the limitation of the work in the introduction, conclusion, and related works.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: We have provided all assumptions and proofs in the submission. The proofs are correct to our best knowledge.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: We have provided all information required reproduce the main experimental results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
The anonymous github has been provided here: https: //
anonymous
4open. science/ T/ anon_ swbmissiionn-7333
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: The paper has specified the training and test details.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: The paper reports experimental results with error bars to support the main claims of the paper.
8. Experiments compute resources
Question: For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [Yes]

---

The paper has provided sufficient information about the computational re- sources to reproduce the experiments.
Justification:
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics httpp::/nnurrppptttsts http://uuuripsccppplllleleeeeeee wwtpcccccpppcaeeeeeeeccccc Stabblicc/Ehicasee htwpe/tiiiiiuceeeeneeeeeeeeeeeee
Answer: [Yes]
Justification: The authors have reviewed the NeurlPS Code of Ethics and the research confirms to
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The paper is mostly technical and theoretical. It does not incur social impact.
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses such risks.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: The paper does any existing licensed asserts.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects. 15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approvals (or an equivalent approval/review based on the re- quirements your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve research with human subjects.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact core methodology, scientific rigorousness, originality of the research, declaration is not required.
12

---

Answer: [NA]
Justification: We do not use LLMs in our paper writing and code implementation.
13

---

References
Zeyuan Allen- -hu and Yuanzhi Li. Backward feature correction: How deep learning performs deep (hierarchical) learning. In The Thirty Sixth Annual Conference Learning Theory, pp. 4598-4598. PMLR, 2023,
Authropic. The claude model family: Opus, sonnet, haiku. URL BoRLhtttss:/wwwwattrrropp com/ news/ http//claaeeeeeeee
Lukas Berglund, Meg Tong, Max Kaufmann, Mikita Balesni, Asa Cooper Stickland, Tomasz Korbak, and Owain Evans. The reversal curse: Lims trained on" n is b" fail to learn" b is a". arXiv preprins arXiv:2309.12288 2023.
Michael M Bronstein, Joan Bruna, Taco Cohen, and Petar Veličković. Geometric deep learning: Grids, groups, graphs, geodesics, and gauges. arXiv preprint 100.::2000413777 2021.
Keith Conrad. Characters of finite abelian groups. Lecture Notes, 17, 2010.
Persi Diaconis. Group representations in probability and statistics. Lecture notes-monograph series, 11:i-192, 1988.
Simon Du and Jason Lee. On the power of over parametrizzzno in neural networks with quadratic activation. In International conference on machine learning, pp. 3329-1338, PMLR, 2018.
Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, and et. al. The llama 3 herd of models, 2024. URL
https://arxiv org/ 2207/ 21783
Nouha Dziri, Ximing Lu, Melanie Sclar, Xiang Lorraine Li, Liwei Jiang, Bill Yuchen Lin, Peter West, Chandra Bhagavatula, Ronan Le Bras, Jena D Hwang, al. Faith and fate: Limits of transformers on compositionality (2023). arXiv preprint arXiv:2305. 10005.1666. 18654, 2023.
William Fulton and Joe Harris. Representation theory: a ffrrstt course, volume 129, Springer Science & Business Media, 2013.
Quentin Garrido, Mahmoud Assran, Nicolas Ballas, Adrien Bardes, Laurent Najman, and Yann LeCun. Learning and leveraging world models in visual representation learning, arXiv preprint 20X1v:2403.00504, 2024.
Andrey Gromov. Grokking modular arithmetic. arXiv preprint arXiv:2301.0280 2023.
Jie Huang, Xinyun Chen, Swaroop Mishra, Huaixiu Steven Zheng, Adams Wei Yu, Xinying Song, and Denny Zhou. Large language models cannot self-correct reasoning yet. arXiv preprini arXiv:2310.01798. 2023.
Yufei Huang, Shengding Hu, Xu Han, Zhiyuan Liu, and Maosong Sun. Unified view of grokking, double descent and emergent abilities: A perspective from circuits competition. arXiv preprint 4rXiv:2402.15175. 2024.
Albert Q. Jiang, Alexandre Sablayrolles, Arthur Mensch, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Florian Bressand, Gianna Lengyel, Guillaume Lample, Lucile Saulnier, Lélio Renard Lavaud, Marie-Anne Lachaux, Pierre Stock, Teven Le Scao, Thibaut Lavril, Thomas Wang. Timothée Lacroix, and William El Sayed. Mistral 7b, 2023. URL htt.:http://// http//axxiv... org/ 2ts//2310.06880
Charles Jin and Martin Rinard. Emergent representations of program semantics in language models trained on programs, 2024.
Subbarao Kambhampati, Karthik Valmeekam, Lin Guan, Mudit Verma, Kaya Stechly, Siddhant Bhambri, Lucas Saldyt, and Anil Murthy. Lims can't plan, but can help planning in Ilm-modulo frameworks, 2024. URL https:///trtiiii org/abs/ /202/.2422222 01817
CG Khatri and C Radhakrishna Rao. Solutions to some functional equations and their applications to characterization of probability distributions. Sankhyā: the Indian journal of statistics, series A, pp- 167-180, 1968.
14

---

Zhiyuan Li, Hong Liu, Denny Zhou, and Tengyu Ma. Chain of thought empowers transformers to solve inherently serial problems. ICLR, 2024.
Bingbin Liu, Jordan Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang. Transformers learn shortcuts automata. arXiv preprini arXiv:2210. 10749, 2022.
Depen Morwani, Benjamin Edelman, Costin-Andrei Oncescu, Rosie Zhao, and Sham Kakade. Feature emergence via margin maximization: case studies in algebraic tasks. arXiv preprint arXiv:2311.07568, 2023.
Neel Nanda, Lawrence Chan, Tom Lieberum, Jess Smith, and Jacob Steinhardt, Progress measures for grokking via mechanistic interpretability. In The Eleventh International Conference on Learning Representations, 2023. /tttttttss//oppeeeeeee wwwpreewwwweeeeeoouuuuuuuaa dddepmmmdddd
Marianna Nezhurina, Lucia Cipolina-Kum Mehdi Cherti, and Jenia Jitsev. Alice in wonderland: Simple tasks showing complete reasoning breakdown in state-of-the-art large language models, 2024. URLbttts:
httgg/bbs2240..0000
OpenAI. Gpt-4 technical report, 2024. URL http://aawwv...og//b///2388888
Simon Ouellette, Rolf Pfister, and Hansueli Jud. Counting and algorithmic generalization with transformers. arXiv preprint arXiv:2310.08661 2023.
Alethea Power, Yuri Burda, Harri Edwards. Igor Babuschkin, and Vedant Misra. Grokking: Gen- eralization beyond overfitting on small algorithmic datasets. arXiv preprint arX1v:2201.02117, 2022.
Noam Shazeer. Glu variants improve transformer. arXiv preprint arXiv:2002.002022 2020.
David R. So, Wojeiech Manke, Hanxiao Liu, Zihang Dai, Noam Shazeer, and Quoc V. Le. Primer: Searching for efficient transformers for language modeling. NeurIPS, 2021. URL https://
arxiv. wrwg/bbb///iieeeeeeeeee 211./1199990008888
Benjamin Steinberg. Representation theory of finite groups. Carleton University, 2009.
Richard Sutton. Reinforcement learning: An introduction. A Bradford Book, 2018.
DeepSeek Team. Deepseek-v2: A strong, economical, and efficient mixture-of-experts language
model, 2024a. URL/tttp::/arrivoorr/// abs /205 04434
Gemini Team. Gemini 1.5: Unlocking multimodal understanding across millions tokens of context, 2024b. URL https:://ariv..og//ubaaa o2tp 245330553000000
Vikrant Varma, Rohin Shah, Zachary Kenton, János Kramár, and Ramana Kumar. Explaining grokking through circuit efficiency. arXiv preprint 2mxiv:2309.02390, 2023.
Jason Wei, Yi Tay, Rishi Bommasani, Colin Raffel, Barret Zoph, Sebastian Borgeaud, Dani Yogatama, Maarten Bosma, Denny Zhou, Donald Metzler, et al. Emergent abilities large language models. TMLR, 2022.
Erik Wijmans, Manolis Savva, Irfan Essa, Stefan Lee, Ari S Morcos, and Dhruv Batra. Emergence of maps in the memories of blind navigation agents. Al Matters, 9(2): --,4,814,. 2023.
Lemeng Wu, Dilin Wang, and Qiang Liu. Splitting steepest descent for growing neural architectures. Advances in neural information processing systems, 32, 2019.
Jian Xie, Kai Zhang, Jiangjie Chen, Tinghui Zhu, Renze Lou, Yuandong Tian, Yanghua Xiao, and Yu Su. Travelpaanne: A benchmark for real-world planning with language agents, 2024.
Tian Ye, Zicheng Xu, Yuanzhi Li, and Zeyuan Allen-Zhu. Physics of language models: Part 2.1, grade-school math and the hidden reasoning process. arXiv preprint arXiv:2407.20311 2024.
Gilad Yehudai, Haim Kaplan, Asma Ghandeharioun, Mor Geva, and Amir Globerson. When can transformers count to n? arXiv preprint arXi::2407.15166 2024.
15

---

Jachong Yoon, Eunho Yang. Jeongtae Lee, and Sung Ju Hwang. Lifelong learning with dynamically expandable networks. arXiv preprint arXiv:1708.01547, 2017.
Jiahui Yu, Linjie Yang, Ning Xu, Jianchao Yang, and Thomas Huang. Slimmable neural networks. arXiv preprint arXiv: 111i::/81..088288, 2018.
Zhengyan Zhang, Yixin Song, Guanghui Yu, Xu Han, Yankai Lin, Chaojun Xiao, Chenyang Song, Zhiyuan Liu, Zeyu Mi, and Maosong Sun. Relu² wins: Discovering efficient activation functions for sparse 1lms, 2024. URL https::/atxii..tt org/ abs/ /b02 03804
Ziqian Zhong, Ziming Liu, Max Tegmark, and Jacob Andreas. The clock and the pizza: Two stories in mechanistic explanation of neural networks. Advances in Neural Information Processing Systems, 36, 2024.
Tianyi Zhou, Deqing Fu, Vatsal Sharan, and Robin Jia. Pre-trained large language models use fourier features to compute addition. arXiv preprint arXiv:2406.034455, 2024.
16

---

A
Notation Table
Symbol
Description
C
The set of complex numbers. The complex field.
The set natural numbers.
i
The imaginary unit. i= v-I.
a. A
The complex conjugate of a scalar a, vector matrix A.
A
The conjugate transpose of matrix A. A" = A
((x)
The indicator function.
1(x) 1 if is true, otherwise 0.
G
The Abelian group to be studied.
g E G
Group element g G.
9192
Production of group element 9i and 92 under group multiplication. Size of the group G. GG| d.
d
Cg
One-hot representation of group element g. The dimension of eg is d. The k-th character function of G. If G' is cyclic and 0 S < d, then xx(g) = el2nkg/d
Øx : G + C
ØE E Dd
The k-th character function in vector form. Φ; = (gx(g)
P
Zero-mean projection matrix P
]11
Waj. Woj
Fan-in weight vectors for node j in 2-layer networks defined in Equ.
Woj
The fan-out weight vector for node in 2-layer networks defined in Eqn. Collection of weight (in Fourier space) of all 2-layer networks with g hidden nodes.
Zy
Z
Collection weight (in Fourier space) of all 2-layer networks. Z U920 2q.
2
Weight matrices of specific instance of 2-layer network.
ord(z)
The number of hidden nodes in z.
21 + #2, ø1 x2
The ring addition and multiplication (Def. 5)
r: + + C
The sum potential (Def. 6).
R
Collection of sum potentrals. E.g., Rg {rkkk, k + 0}.
Rg. Re, Ru, Rx
Collections of sum potentials (Lemmal I] that appear in MSE loss function (Eqn. 3 Table 3: The notation table.
B Decoupling L2 Loss (Proof)
We use the character function é : C. which maps group element g into complex number. Lemma 3. For finite Abelian group, the character function ó has the following properties Fullon & Harris 2013); Steinberg (2009):
It is I-dimensional (irreducible) representation of the group G, i.e., |o(g)) 1 for g E G and for any 01.92 E G. Φ(g192) = ((91)))))) (g(2))
There exists d character functions {Ør] that satisfy the orthonormal condition 1 EgEG &n (g())( 1(k K²). Here th is the complex conjugate of & and is also a character function.
The sel of character functions forms character group & under pairwise mulliplication:
tk2 =kk, o @02
the trivial representation (i.e., all g E G maps to 1). According to the Fundamental Theorem of Finite Abelian Groups, each finite Abelian group can be decomposed into a direct sum of cyelic groups, and the character function of each cyclic group is exactly (scaled) Fourier bases. Therefore, in Abelian group, k is multi- dimensional frequency index. [Conrad (0110) shows that & & G (Theorem 3.13) each character function o & can also be indexed by g itself. Right we keep the index kt
Note that the frequency l goes from d 1, where do
For convenience, we define Φ_ = & as the (complex) conjugate representation of Óx-
Let Φx (g)leee E Cd be the vector that contains the value of the character function Φu over G. Then ) form orthogonal base in Cd and represent the weight vector Was as the
17

---

following, where p E ba,b
Waj= =
Eaky Øk,
Waj =
Ebky Ok:
Wej =
Σ
Reky
Fckj&b
(11)
R=00
R+E0
where = : {2pks} are the complex coefficients. Here p E fa,b, 0 S ls d and j runs through hidden nodes.
Theorem 1 (Analytic form of L2 loss with quadratic activation). The objective of 2-layer MLP network with quadratic activation can be writlen - -x= lx (d (d-1)/d, where
E. = +
Maak + +
- / pE(a,b) 10'
Σ Σ
+ 1 Σ
Pp on kk, (3)
k1
mcF0 Pc (o.b)
Here Tkikak = Ej Baki, Sbk,, Rekj and Tpkskak == Eg 2pkis 5 & Pekjj-
Proof. Note that the objective & can be written down as
e 00 (o(g) (2)ggig2)/2d e 11
(o(g)
(12)
Em |0
P P 0/4 Ad o o e m eg PI E
(13)
For notation brevity, let Eakj = Okjj 2bkj == bوj and Zckj Ckj. For E [o Pf eg since
e 6 P
Ee e Pi Weyo + e()e
(14)
Σ
Σ
C Sw
(wijee + woseep) )²
(15)
Σ
Σ
ckr (9192)
Σ Σ
2pRy ZpRy ( DE(a.))
(16)
Kg0
Therefore, leveraging the fact that (gig2) ox (g1 Jow (92), we have:
Egi.ga 1e Pt
Σ
2k kpzka E 91
(91) (92) (9p, )okk (9pz)]
(17)
Since Eg [dx(g)@w (9)] = 0(k: = k²), there are only few cases that the summand is nonzero:
Pi = o. P2 = b, = ki k2 0.
P1 = b. P2 = a, = k1 = k2 + O.
In both cases, the summation reduces to Exsuo Ckj Zakk = Enzo,s Ckjakzbaj- Let Pkikak
Σn jkr, then we have
En [o (g1. p =2 Σ
axybRiCkj
Σ
Tkkk
(18)
kęU,
For E [TTppto pto
we have:
ppoo C... + l eog)
(19)
j.
here
T
TTP. Wey' =
w oj
Σ 5
Σ du
Σ
(20)
18

---

due to the fact that 0 0K Eg (1) dl(k = k').
Then the key part is to compute the following terms:
Egi.92 (2p Spakafi Spakasz Pp jh'j Ck/ 0k, (gps 2ok (gpz Jokn (gps Jok, (9ps)]
(21)
summing over (p1, P2, Pa. P4, k1, k2, 33, k4 k + O, j1, j2}. Note that since each E {a, b). there use (1,3) to represent the subset of p that takes the value of a (e.g., (1,3) means that p1 = Ps = a and P2 = Pa = b). It is clear that for odd assignments such 31), since 2p0j 0, the summation is zero. Then, we only discuss the even cases as follows:
are 2 = 16 choices of (P1, P2, Pa. Pa.Pa). For notation brevity,
Case 1: (1,3), (2, 4), (1,4), 4), (2,3). The 4 cases are identical so we only need to analyze one. We
take (1, 3) as an example. For (1,3), p1 = P3 = a. P2 = p4 = and the only nonzero terms when kj K3 = 0 mod d, l2 + k4 = 0 mod d, since g1 (Kk, (91 (g)) (01)] 0(kk + K3 = O mod d)
(and similar in other cases). Then Eqn. 21 becomes:
Fakyj Fbbgg Fa, Jo 2b, ka.Ja Ckfij Ci'ja
(22)
ka de 200 51j2
Σ
Σ
Zakita 2bbizda Ch/ Zakih 2okezi Ckisa
(23)
ka,
=
Σ
Σ
akis bkadh Ch/s
Σ
Olks J2 bkest CW
(24)
ka, k'00 $1
J2
Σ
1rky 1
(25)
Since there are 4 such cases, have:
El
Σ A 52500 A
Σ
1
(26)
Case (1,2) and
(3,4). The two cases are identical. Take (1,2) as an example. In this case,
P1 P2 = a and P3 14 b. The only non-zero terms are when kn + k2 O, his + his = 0. Then
Eqn. 21 becomes:
Σ
Zakin Zakin 2bkaja Rbkcaio Cie Okidz
(27)
As ke Ao' #f0 5132
Σ
ukihh Peeeh Σ Ibkaja Po
(28)
kk. kf' #4
Σ
lakin 12
Ckrs
Σ
Σ
Iheais
2
(29)
k0#0
Ris
Let raan = E3 (En (ki))kzs) Cwa (similar for rom ) then the above becomes
En'o 8 "000 6ok
Similarly, for (3, 4), the above equation becomes Enso g 8 "oo bok Therefore, we have:
E2
eok bok
+ abl buk
(30)
R #0
Note that this term can be negative. However, we will see that when is combined with the following terms, all terms will be non-negative.
19

---

Case 3: (1,2,3,4) and () In this case we have:
ΣE Σ
E
Spkisi Sphasi Apkada Spkaya CK Cp/
(31)
k'40 in pe () by & th
ΣΣ Σ
E
Apkiji Splaai pkaaj Spkaja Ck'ji Ckiiaa
(32)
k'0 pEla,) ka
= ΣΣ
E
E
E
Epkiis Splzsi Epkaja Spkaia Co Ck'
(33)
M40 m p) Jida by tgmm Ri Rm=m
EE
Σ
Σ
Σ
Σ
Ephash 2pkzti
2
#20
DE (a,b)
ji
J2
Aka+ku=m
Σ
Ir ammk
+ |r lrbmmr
(34)
k'
In particular, when m O, we have
Irauxe
11 1 Therefore, we have
62 + C3
Σ
1r a0k + ''BOK
(35)
k'
Finally, putting them together, we have:
E E o]
d(e1 + 62 + +3) = d(e1 + (e2 + 63 + <3,m440
(36)
P ? + Iaau
r Tbo
2 +
Σ nammer? +
himer
mzK
(37)
Putting them together, we arrived at the conclusion.
Lemma 1 (A Sufficient Conditions of Global Solutions of Eqn. O-sets Re U Rn U R. and 1-set Rgy i.e.
If the weight z to Eqn. 3 has
TxRx(()) = 1(k + 0), (2) = 0, "pkiksh(z) =0
(4)
then it is a global solution with ((z) O. Here Rg = {TRMN K # 0}. Re
(Tuckski k1, k2, k not all equal}, Rn == (Tp. xb and R. == (r m- m # 0}.
Proof. Note that Ex Pakk En |TARE|? has minimizer TRRK = 1. Therefore, the best loss value any assignment of weights able to achieve is the following:
Kakkkk =
Σ
a akashassCs = 1(k1 hi2 = k')
k #0 0
(38)
& a0k
"OOk"
Σ
Σ |akzl2 2 |baj 2
Ckij =
W +
(39)
x amkk
akzj
Ck'j = 0
W/ + 0, m + #0
(40)
Vis Mi
bmuk'
Ckij
k' + 0, #
(41)
Therefore the sufficient conditions (Eqn. will make all above come true.
C Semi-ring structure of Z (Proof)
Theorem 2 (Algebraic Structure of Z). (Z, + x) is commutative semi-ring.
20

---

Proof. Straightforward from the definition of addition and multiplication (Def. 5 and identification of hidden nodes under permutation (Def. Note that ring addition (i.e.. concatenation) does not have inverse and thus it is a semi-ring.
Theorem For any sum potential r Z C. r(1) 1, r(z1 + x2) r((1) + r(z2) and r(2) * x2) = ((z1)r((z)) and thus r is ring homomorphism.
Proof. Let (z) Σ, ())dkdi)) 3pkj- Since the ring identity 1 is order-1 and all 2pkj 1, is obvious that r(1) 1.
Let supp(z1) be the subset of the hidden nodes that corresponds to 21 in the concatenated solution 21 22, similar for supp(z2). Note that
r(21 x2)
Σ
II
Σ
II
(2) ppkj
r(21) + r((2)
(42)
pke
jEsupp(z:) (p.))Eidx(r)
jEsupp(z2) 22) (p.k)Eidx(r)
On the other hand, we have
r(21 * 22)
Σ
II
(pki Spkja
(1) (2)
(43)
fide (v.A)Eidx(r)
Σ
II (p.N))idx(()
plahh
(I)
2 pkita
(44)
jida
(n.))eidx())
Σ
II (e.i)t)
"plcis
Σ ja (p.A)Eidx(r)
2pkis
(1)
(45)
Ji
r(21)r(z2)
(46)
Corollary 1. If z is a global solution and y is a unit, then * y is also a global solution.
Proof. Straightforward by leveraging the property of ring homomorphism. E.g.
TAkA (z y) T'kk (z) (2)
(47)
and the proof is complete.
D Solution Construction (Proof)
D.1 Construction of Partial Solutions
Theorem 4 (Construction of partial solutions). Suppose u has 1-set R1, Q2(u) := (r()):=rrww)lre R} S C is set of evaluations on R (multiple values counted once), then if & Qn. then the polynomial solution pn(u)= = I II (u has 0/1 (R, R1) up to scale. Here & any order-1 weight that satisfies r()) for any R R4. For example, $ 1/33
Proof. By definition, for any r E we have:
r(z(u))= II #EQR(M)
(r(u)+r(8)
II (r(u) - 8) =0
(48)
sEfgg(u)
similarly for any Takk R4 we have:
(ka)(((u))
II (ruee(u) + (8)) = II sEfg(u)
(1 - #
#0
(49)
(EQR(w)
which is constant over different k. So =u) satisfies Lemma up to scaling factor.
21

---

D.2
Construction of Global Solutions
Corollary 2 (0rder-6 global solutions), The following "3 2" Fourier solutions satisfy the sufficient condition (Lemmal 7 and thus are global solutions when d is odd:
(d-1)/2
2F6
(R) syn * 20
yk
(6)
V6
Here (k) := p( Uayin and 2he := uy + 1x (i..,, not maximal polynomial), where Usy and are defined Table !
(K)
y is an order-1 unit. As result, (z = 3 2- 1-1-(6 (d 1)/2 3(d - 1)
and each frequency are affiliated with 6 hidden nodes (order-6).
Proof. Just notice that Esyn == p(uayn) Ugyn + Usyn + 1, (superscript (k) are omitted for brevity)
makes all MPs Rm, R2 and part of R, (Tbl. [T) equal to O, except for "aac" and "bbe", which corresponds to monomial polynomials Takkk
Ej Fakj FakjEckj and TbRkk == ES =bkj Rekj- Fejj On the other hand, according to Tbl. [ Zr uu + 1x has Takkk
PbRAA (b)))(Z)) 0. Therefore,
using ring homomorphism, we know that for any r E Rn U Re U R., r(zyyn * zu) = and thus Rn U Re U R. is the O-sets.
On the other hand for any k,, we have:
(d-1)/2
TRIEK (ErS) = TRIKK
Σ
(k) (b) * yE
(50)
V6
syn
k=1
(d- 1)/2
(2
syn
(h)
2/(0) yya
(51)
6
(d-1)/2
Σ
6(0(A: = k²) + 0(k: = -k)) =1
(52)
6
The last equality is due to the fact that we only sum over half of the frequency. This means that
Rg is a 1-set of 2rg. Therefore, mg satisfies the sufficient condition (Eqn. 4 and the conclusion follows.
Corollary 3 (Perfect Memorization). We construct two d-order weights (Zn, Za) from order-I generators (U))
Σ U
Za
2B
Here za E Ro(k1 # Rn, DR b m + k), z5 E Rc RR) m + k).
Then 2M = d- 2n, 2g satisfies the sufficient condition (Lemma) 7 solution with ord (M) = d::
and is the perfect memorization
Rakjnja
(MM d kh,
bkisib = d kb
(M)
zokjija d ww
(M)
(8)
where each hidden node indexed by j j2). 0 < j1,52 < d, #0. 0.
Proof. Simply plugging in the solution and check whether the equations specified the equations. For Za, for k = 0 everything is zero; for ls # O, we have:
Tkikgk(Zz) (Za) = Σ
akkz Ckasbkajkk =
Σ Wwili = =D(ki = k + 0)
(53)
(Zm)
Σ
aa jm- Σ (i((m))) = 11m k + 0)
(54)
Tbmk)k(Zo))
Σ
bw bur5bm-kk.jC3
Σ w- 1(k 0) =0
(55)
22

---

Therefore, 2a E Rk * RR n (p b or m # k). Similar for 2b. For 2M == d Zu 2b. it satisfies all O-sets constraints (i.e., for any 7, either zn satisfies with r(za) or 2 satisfies with r(z)) = 0) and we have:
TRRk (d 2/3 Za zb) (2. = =d2
2/3
(56)
So am satisfies the sufficient conditions (Eqn. Corollary (Order-4 single frequency solution). Define single frequency order-2 solution z
Zak- = [1, Zbk- = -i]), Zck- = =[1,i]
(9)
where [6] 1. Then the order-4 solution 2 2F4 == p p(u) 2
(k) has O-sets Re and R. (but not Rad.
Proof. First, Myyi Wdd in Tbl. [ thus p(uv=i) has O-sets R. and R. except for "abe", which corresponds to MP - E Re. the other hand, we have
Tk ( = 1 + E (-iE) (-i)=0
(57)
With the property of ring homomorphism, the conclusion follows.
Corollary (Mixed order-4/6 global solutions). With p44, there is a global solution to Eqn. that does not meet the sufficient condition, i.e., Ex Tp.kk - .m 0 but , + 0:
(d-1)/2
FF4/6
46
(hv)
F6
Σ
F4
(k)
(10)
1.1kko
F6 for k + kg- The order is lower than pn: ord(22116)) + 4 ((d- 1)/2 = 2d < ord(zro).
where 2(ho) a perturbation of pF6
(ko)
= Zayn
(ka)
z by adding constant biases to its (c, k) entries
(ka)
(k) Proof. While zP1 does not satisfy Rg a weaker condition for global optimizer to Theorem is (kv)
that Ex T O. We show that by adding constants to (c, k) entries of 2F6 for k + tko. we can achieve that while not changing the value other MPs.
To see this, we compute for each m + tkk:
Σ Tp.k' lo.k',kk,,n mm (2 (kok =
Σ
(
lok'sl 52 | (itf I
(58)
Ae'
2
(ko) lpkks
(ka) F6
Jems 2 >
(ko) F6
Jems
(59)
The second equality because all (a, k') and (b, k') entries are 0 except for tho. and the last equality is because all nonzero entries of 2P6 On the other hand, we have:
(Ro)
have magnitude 1.
Σ R''
Tp.k'. -k kmm
(k) 2F1
Σ
To - -n (p(u(())) ( - (2(mm) k
(60)
prpm m. (p (0 (1m)
)) (2 (m))
(61)
2(1 + 1) +i) = 4(1 +
(62)
For m = =ko, we have Tp. m m= (2(ka)) = and Pp. - ml (z (b)) = 0 for 1: + m. Therefore, we just let
(kg) cmy = 4(1 +i) = (1 (1+i)
(63)
2.6
3
and Σx To.k'- -K -M (ZFA/6) = 0 for all m. See Fig. 5 for the construction.
23

---

akoo
bkoo
Ckoo
0
a
bko1
Ckp1
0
2
2((6)
F6
akoz
ak03
bko2
bk03
Ckp2
Ckp3
0
0
Ckj
constx
a
bko*
Ckp4
0
0
ako5
bk05
Ckp5
0
Figure 5: Visualization of =(oo)
To see why such a modification of 2F6 won't change other MPs, simply notice that candidate MPs that may not be zero anymore are ko Komm and ry, ko. for m f thg. For kh. (Ko) F6
are well behaved.
Note that too (#/oe) (Aaa))
the same as applying kooo to solution which replaces (c, ki)) Frb by (c, m) entries. Let üsyn = [W3. 1] and done = [1.- 1, Then &
entries of (ka)
p(úsyn) (Hooe) and thus for m # t,g, we have:
komo (ZF4/6) Hom (2fte) (kt)) x Rooko (2)
(64)
ko (((()y)))))))))))))))())) #oo (p( (p(thonn))
(65)
since tokk (p (one)) = O. Similarly for m + =
Tpkokum Tphakom(2P4/6) = Tpkooom (# (ka))) x Tokokoko (2)
(66)
Pkookoko (pl (((ssy)) pkokokk (p((oon)) =
(67)
since Po (p(ūayu)) = 0. Similarly for rp.- m-
Remarks. To construct FG, in addition to žeyn z,=1 shown in the main proof, could use other compositions to achieve the same effects. For example, Zayn,a9 * Zy=l, where Zayn,o88 is:
Zak-
[1, (uya,Wy31)
Dbk- (lwyā,WzB)
Zck- Ws]
(68)
where [a] |8|
1. Note that Zyyn p( Usya)) is special case of Zayn,a3 when 3
D.3 Canonical Forms
Definition 8. A solution is called canonical ko. E Cko if ZpRO for all and k: =ko-
Lemma (Canonical Decomposition). Any solution with Tkokoko (2) + can be decomposed into = z' * y, where z' is canonical at ho and ord(y) = 1. Both Thokako (2') * 0 and Tkokoko (y) # O.
Proof. Since Tkodkkko (2) (z)=E, Okoj * 0, there must exist some j so that Zake) Pbkoj Zokos * which means that Zakaj + Ú, Zbkmj * 0 and Zekoj # Since the node index can be permuted, we can let node j be the first node and Upko = Zpk- and Eypgy- = žpky" "pkj for p E {a, b, c} and kgg then is canonical at ku and ord(y) = 1. Finally, by ring homomorphism, since
Kkokoko (z) = Tkokoko (20)rrkk (v) +
(69)
we know that both kokooko (z') * O and Tookako (1) + O.
Lemma 5 (Necessary Condition for R.). All order-1 and order-2 solutions satisfying R. (Tkg 0, k1, K2, l not all equal} must have TEkk = 0 for all (i.e. the first equation Eqn. cannot be satisfied).
24

---

Proof. For any order-1 solution, for any k, in order to make rk- = Zoko -.. 2oooR 0, either 2ak0, 2bk0 or 2ek0 has be zero, which means that TRRE 0.
For order-2, first of all if any =pk0 = O for any p E {a, b, c), then a constraint like rk,k,-k = Pako=btoFckk Fak12bk1
and thus Tkkt 0. If not, then for any two complex numbers 2pk0 and 2pk1, there always exist four real numbers 0g E (-T, T]. 0% (-TT, T], mpp and mp1
#bk1 Eck1 = yields Pak1 #bk1
that
Ppk = mane 660
2ph1
my1c 50 10p
(70)
Then a constraint like r = Zako Z + 2ab1 Eck1 can be written as Zako2bko 2ak1 2bk1 Zek1, or equivalently:
mae 10% +0%++0+ +6)) (0.
ama me1 Mel (0'
(71)
Moo 10. e iile = -Ma i0. -00
(72)
Comparing their magnitude and phase, we have mao = mal m and
0. 0b 0g = = mod 2x
(73)
Similarly, we have:
0g + 0. 0, = 17/2 mod 2x,
0. + - 0o 2 mod 2T
(74)
Solving the three equations and we have 6 possible solutions:
(0a, G. 02) (0,0, mod 2
(75)
(0a, 0. 02) = #0,+ mod 2m
(76)
(0, Og 0.) (##/2,0,0) mod 2%
(77)
For all such solutions, let m == moomomo = maiMsMMll. then we have:
Thkk
ZakOZbROZckO + =akl Zbk F
(78)
me +0,0%% +%)) (c0 + e -(((..06++0))
(79)
(%,+++ (c (in/ + Fia/22
(80)
0
(81)
Lemma 6 (Property of order-3 solutions satisfying R. and Rg). With small La regularization, all per- frequency order-3 canonical solutions z at frequency ko that satisfy Re and Bg are in the following form:
ppko =
[1, a,t03 ByW5), for E (a,b,c)
(82)
where app = +1 and 3p +1 with the constraint that agasae = Ba 1. For & Ko: Zpk-
Proof.
We first prove that satisfies RS and Rg. To see this, we have
Σ
l(k1 k2 = k = ko) + Σ 1(-ki = ko)wg
(83)
+... + -1( 0(-k1 = --k = -k = Ko ko)
(84)
=1((k = 22 k = ko) + 330(k: = k22 = -ko
(85)
Note that all cross terms are gone since Σ3 w/ 0. It is clear that Agk of 0 unless K k2 so z satisfies R. and Rg.
Now we consider any per-frequency order-3 canonical solution (Def. at frequency Let ay == Eakj. by := žbkj and cy := 2ckj. Let a [a,] E C3, b [b,] E C and c [cg] C3 Since the solution is canonical, we have = by = co 1.
Then the conditions yield that
(ao c= 0, (aob) T= c= 0, (a= c= 0, (aob)Te c 0
(86)
25

---

which means that in R space, the following condition holds:
span(R(a b), 3(a b)) span(R(cc) 3(c))
(87)
where R((-) and 3-)) are real and imaginary parts of a complex vector. Since Equ. 87 holds in R must be the following cases: either R(a b) is co-linear with 3(a b), R(c) is co-linear with 3(c).
If the latter is true (i.e., there exists 3 so that (R(c) = 3())), then since co = 1 is real, 8 = 0 and (ic) = So e real. In this case,
Tkkk (aob) c= (a b c=
(88)
the former is true, then similarly we conclude that 3ia e b) = and a b is real. Applying the same reasoning symmetrically, in order to find cases such that Pkkk 7 0, necessary condition is that
a b.b,boc,coaEE
(89)
Let Epkj = Ižpky (el Let's first consider the case that a o b. o, a E R
20- Then we
have 0a0 = Oso 0.0 = dg = 0. 0,1 = 0n1 = dct = 01, 0a2 = 022 = Ocr = 02. Letting
my == |aylbbyllcy|, then the corresponding Tkkk can be written as:
PARK
Σ m m
(90)
with the constraints that Σラ mye = 0 imposed by Re.
Minimal Norm solutions. One interesting question is that what the minimal norm representation that achieves the highest objective? For this we can solve the following optimization problem:
Σ mi + (300,,,)) (my ,
max
E m
Σ Em =0
(91)
which achieves the maximal when my l/e, 0, 2 and 0g = 4Ti/3 (or vise versa). Note that the optimal 03 is fixed no matter how small the regularization coefficient e is.
To see that, let uy = e0,, Then we have:
Em + +,,)3 Σ mnlu? + 0,) + n3]
mm + a))
(92)
Therefore, letting 2y 2Ruj. we just need to consider the real part of the objective, and solve the following optimization in l::
max
myjr - Σ m s.l. Emyar = 0
(93)
(m.- 20
whose solutions give a sufficient condition. Using Lagrangian multiplier, we have: ØL m3(3x² - >) 0, dm, Oz,
aL
= 23 2cmy λæạ 0
(94)
which leads to = 3, my I/e a and 1 = x2 = -1 This corresponds to the solution
Epk = [1,wg,
W3. Wz).
wherep E b,,
(95)
Note that the original necessary condition is a a b, č,co E R². Considering the possible negativity, the solutions can be written as
for p E {a, where Opp = 1 and 3, = 1 with the constraint that O,,00 B By = 1.
2pk- = [1, apW's 3,03),
(96)
L
Remarks. Note that this conclusion does not contradict with the constructed solution 2 in Eqn. 68 in which a and 33 are allowed to be any complex number with magnitude 1. This is because
Z does not satisfy all the constraints R. (but Z * Zu=i will) unless a and / are real and
thus +1.
26

---

[2]]
[R at 300
[2 at = 400
12 at 2900
10
14 18
10
12 16
10
10
16
Figure 6: The convergence path of ze.. when training modular addition using Adam optimizer (learning
0.05, weight decay 0.005). The final solution contains 2 order-6 (z (4) and I order-4 (z(²)) solutions. Note that for ze... unlike Fig. 2 each order-6 solution contains constant bias term cancel the artifacts of order-4
solution (Corollary For cach hidden node j. once a dominant frequency emerges, others fade away.
E Gradient Dynamics (Proof)
Let (r kpk,kkk] Cddd be vector of all MPs, and J= dr be the Jacobian matrix of the mapping r = r(2(W)) in which W is the collection of original weights. Note that when we take derivatives with respect to r and apply chain rules, we treat and its complex conjugate (e.g.. Tkkk and -k FRRA) as independent variables. Since we run the gradient descent on W, will such (indirect) optimization leads descent of towards the desired targets (Lemma] T)? The following lemma confirms that:
8= 6y
Lemma 7 (Dynamics of MPs). The dynamics of MPs satisfies i = JJJ'V which has positive inner product with the negative gradient direction V
Proof. By gradient descent of W, we have W = -ww.. By chain rule, we have:
W = - -ww - =
(97)
Then the dynamics of r= r(z(W)), as driven by the dynamics of W, is given by
ト= ==
(98)
To show positive inner product, have:
V - V.
(99)
Theorem (The Occam's 's Razer: Preference of low-order solutions). If 4 x' and both z (of order q) and z' are global optimul solutions, then there exists a path of zero loss connecting z and z' in the space of Zq. As result, lower-order solutions are preferred if trained with To2 regularization.
Proof. Let ord(2 )) yg and ord(z') =q Then d'lg. Since both and z' are global optimal. Since Tkkk is ring homomorphism, we know that TRAK (z) ) = -akk (z'))Au (y) = 1/2d = Txxx(2') and thus Takk ( = 1 for all & # 0.
Let the augmented identity e E Zg be 6pm) I(j = 0). Then mlLk (e) for all +
We want to construct a path in 2y, the space of order-q solutions as follows:
(t) = g(( z',
(100)
which 5(0) = e, 5(1) = y. and FRAu (ū())) = for any To see why this is possible, pick continuous family of trajectories g(t 2) with [0, so that they satisfies
50; A) {(1;A) y. (u 0)) = 1,
(u 1)) 21
(101)
27

---

which can always be achieved by scaling some trajectory with a factor that depends on A. Then by intermediate theorem, there exists A(t) so that TREK (;t;; X(t))) = 1 for some k. Note that for different frequency k and K, Tkak and TReK involves disjoint components of so we could find such a path for all #
Therefore, for any monomial potential r included in MSE loss (Eqn. 3 we have
r((()) - (((()))(((())(2'))) = {
finite 0 = 0 1 1/2d = 1/2d
r + Tikk
(102)
r= Tkkk
and thus the entire trajectory 2(1) = 5() z' E 2, connecting and z', which is z' in the space of Zg. is also globally optimal.
To see why weight decay regularization leads to lower-order solution, we could simply compare the E norm of y z' and z'. At each frequency this reduces the following optimization
problem:
min Σ lay 2 + 1byl2 +
tol
s.t. -abbo =1
(103)
where a := Yakj. by = yous and Cj := Yckj- geometric mean:
Since we know that arithmetic mean is no less than
laj" 22 + bb 2 leg 2
/ Masbyes12
(104)
We have:
Elas+ + + +1,112 2 3 Σ 10,b,e,12/3 23
(105)
The last inequality holds because (1) if any lazbycz 2 1. then it holds, (2) if all laybyeyl < 1, then since af is decreasing function for < 1, E, la,b,e, 1/3 > E, Jazb,ccl 2 IΣ, a,bرe 1.
The minimizer is reached when la |by| lcyl. Note that if aydec, has any complex phase or negative, then in order to satisfy Σ; a,bbC, 1, objective function needs to larger. So without
loss of generality, we could study 0j bj Cj Ij 2 0 and the optimization problem becomes
min
s.t. Σ 2 1,
zj 2 0
(106)
which has minimizer at the corners (l.0,..... This corresponds aj = b; = Cj 1(j 0), which the augmented identity e Zg.
Theorem 6 (Infinite Width Limits at Initialization). Considering the modified loss of Eqn. 3 with only the first two terms: Ex == -2 + Eeyko ke Tr 12, if the weights are i.i.d Gaussian and network width q +00, then JJ converge diagonal and the dynamics of SPs is decoupled.
Proof. Let = En Vla. Let's compute the dynamics of MPs following Theorem =-=
First it is clear that
ot Orkk
Ol. Ork,
21(kk = .22 kk) + 2r Agk
(107)
So the (Ai,, k2, k) component of v only contains Agg
28

---

Then we compute H == JJJ and show that it is asymptotically diagonal. To see this, each component
of H, iec. A can be computed as the following:
Orky ÖTRM
hks Kaka, KG
(108)
0zpms
Ōzpmj
prny
=I(k1 = =k()
bkon buiy Ckat
(109)
+ 00k22
K2)) Σ S (Cka) Cka)
(110)
+ 0(k3 k/)) Σ akk و b b
(111)
where akj == 2akj. baj == 2bkj and Ckj Rckj- Then for component (k1 K2ks, Ky, K2, Kg). if any
kp # Kg for some p E {a, b, c). then the corresponding Epk,s 2 has random phase for hidden node j. and A + when + +000
Combining the two, we know that the dynamics of MPs is decoupled, that is, each Ky evolves independently over time.
Ripple effects. While Theorem only holds at initialization, the resulting decoupled MP dynamics, e.g., drREa/dd /df 1 TRAk that leads to (t)a(t)
e- already captures the rough shape of the curve (Fig. top right). To capture its fine structures (e.g.. ripples before stabilization), we can also model the dynamics of the diagonal element in JJ Consider symmetric ID case on fixed frequency k, where all diagonal Fikkk ro - (where ro = 1/2d) and all off-diagonal Pkyk then
i -PRR K((KAR=TO) KT, k = a(ro TRAA) 110001111000 -1-aa111 co (2a-1)r-c) (112)
where K 0 is the diagonal element of JJ and is coefficient that characterizes the relative strength of two negative gradient Vreus = Tkak and -V = ky and co is the gradient terms caused by asymmetry and/or other frequencies. This yields a second-order ODE that has complex roots in the characteristic function when co > 0.
29

---

G = (e.g.g".g'*
Cyclic group G Co
8
X = {xo. X1, X33
X' = X53
Figure 7: An example case of group action state set X. X can be partitioned into several disjointed components, each is transitive graph w.r. the group actions G.
F
Extending CoGS to Group Action Prediction
While in this work we mainly focus on Abelian group, CoGS can be extended to more general group action prediction: given group element g E G and the current state x E X, the goal is to predict gz E X, i.e. the next state after action g. Such tasks include modular addition//ultiiplcction in which the group acts on itself (i.e., X' G), and also includes the transition function in reinforcement learning (Sutton 2018) and world modeling (Garrido et al. 2024), in which an action changes the current state to a new one.
Setup. Consider a state space X' and group action G x X' + X' where G is group element acting on a state æ E X' to get an update state gr E satisfies two axioms (1) the group identity maps everything to itself: ex I, and (2) the group action is compatible with group multiplication: g(hxx) (gh)æ æ for any g, h E and x X.
Equipped with the group action, the state space now can be decoupled into a disjoint of transitive components.
Definition 9 (Transitive group action). A group action is transitive, for any æ1, 22 E X, there exists g E G so that gæ = 22-
Since the group action is compatible with multiplication, X' under G' will be partitioned into disjoint components X' = U, Xi and we can analyze each component separately (Fig. 7
Transitive Group Action. For each transitive component X' (dropping for brevity), under certain conditions, we could define a state multiplication operation (a formal definition in Def. [0 in Appendix) so that for any group action gr E X. there is an associated state x' E X so that x' x gr. Furthermore, under the multiplication, X' itself becomes group:
Theorem 7 (X' = Z.) If the group stabilizer Go, :=
{glgzo zo } is normal subgroup of G. then X isomorphic to the quotient group G/ G/Gzo and thus forms a group.
Moreover, can prove that for any group element g G, there exists 4v(g) X' that for any state x', the group action gx' is the same as the state multiplication x' x. Therefore, for group action prediction tasks, we have (note the difference compared to Eqn. II]:
w, = UG (Powlic G + wHo) + Ux
(113)
where wH. E R| is the "in-graph" component of G. wit E RRG is the "out-of-graph" component for g E 4, (z)) and wio 1 Powlll j.- 3.G- Since any just behaves like to(g) when acting on X, our framework can be applied to characterize the learning of w!! 3.G-- Intuitively, we only learn representation of G's element "module" its kernel Gzn, since element in the kernel is indistinguishable from each other.
of G, and Po E [|G|||| "lifts" from X' to G using to, i.e., (Po)
On the other hand, the behavior of w will be influenced by g acting on other graphs, and the final leamned representation of a group element is the direct sum of them.
30

---

G Detailed explanation of Sec. F
Matrix Representation. Each group element 9 can be represented by a matrix Rg. i..., its matrix representation, so that it respects the group multiplication (i.e., homomorphism): Rihh = Rg R2 for any group elements g, G.
The dimension of such a representation may differ widely. Some representation can be 1-dimensional (e.g., for Abelian group), while others be infinitely dimensional. The permutation representation Rg E Rdxd maps a one-hot representation ex E Rd of an object X'' into its image Egz E R", also one-hot representation. Intuitively, (Ry)ix element.
means that it maps the k-th element into the j-th
Lemma (Structure of Rg). For any g E G, Rg is a permutation matrix.
[c] 11 Lemma 9 (Summation of Rg). If the group action is transitive, then Eger Rg d
G.1 Transitive Case
To construct the multiplication operation on X, we first pick reference point zo E X, and establish a mapping to G + X: (n(g) = gazo. Note that ig is not necessarily bijection; in fact we have:
Lemma 10 (Co-set Mapping t0). There is a bijection between 1/5²(z)) (x) Jaex and co-sets [G Gapl
of group stabilizer Go == {g E Gigro zo}. which is subgroup of G fixing To.
Lemma 11 (Uniqueness Multiplication Mapping). If Gzo is a normal subgroup, then for all 91 E E (x1) and g2 E to (x2), all g1922.z. correspond to the same coset.
Definition 10 (The multiplication operator X). When Gzo is normal subgroup, define multiplication on X: X X + X' to be x1 == 10(9192Gao) for In = F1 and x22 = 92 Under this definition, Zo is the identity element.
Lemma 12. If g E to (z), then for any x' E X, gx' = xx'.
This means that in terms of group action, the group element g indistinguishable on X.
G.2 General group action
In this case, Rg can be decomposed into a direct sum of smaller matrices, and all our analysis applies to each of these small matrices.
In the main text, to simplify the notation, we assume that the group action is transitive, i.e., for any y. s/ E Y, there exists E G so that gy = y In the following we will show that for general group actions, the conclusion still follows.
Group orbit. For any x E X, Let G y: (gylg E G} C Y be its orbit. Lemma 13. For y, n' E G, either G G. yy' (Iwo orbits collapse) or G y G. y + (two orbits are disjoint). Therefore, orbits form a partition of X.
Let X/G = {G- y|ı X3 be the collection of all orbits. The following lemma tells that the matrix representation Ry can be decomposed into a direct sum (i.e., block diagonal matrix) on each orbit. Lemma 14 (Direct sum decomposition of Rgy)
Rg
Ry
(114)
Y'EYIG
and each RYy E RIX'IxI'' is permutation matrix with E, R
G
11
Proof. By the definition of group orbits, the group action g is closed within each Y', Therefore, Rg is a direct sum (i.e., block-diagona
For each element. X", let's check its destination under G. It is clear that if two group elements E G maps X' to the same destination, then
gy hy + y= == 'hy + g The Gy = h= gG
(115)
31

---

where Gy is the stabilizer of X, subgroup of G. Therefore, g and h map A' to the same destination, if and only if they from the same coset of Gy. Therefore, each entry of Eg Ry the column X equals to the size of cosets of Gy. which is Gyyl- Furthermore, for y1. Y', since they belong to the same orbit, there exists that 9V1 = y/ and thus for any g' E Gyg we have
I'y y1
g9 y1 9V1 92
99 9 y2 1/2
9gو9 Gyz
(116)
So there exists bijection between Gy and Gyz- This means that |Gyl is constant for any x E X and thus all elements in Σg R2y are equal to |GI/[Y"| (i.e., the number of the group elements that send X' out to various destinations in Y', divided by the possible distinct destinations |Y'), results in the number times each destination gets hit).
H Proofs for the content in Appendix
Lemma 8 (Structure of Rg). For any E G, Rg is permutation matrix.
Proof. Since every element needs to have a destination, every column of Rg sums to 1, i.e., 1 1Rg. = 1 Then we prove that the mapping y + is a bijection. Suppose there exists yı, 92 so that
gV1 9V2. Therefore by compatibility we have:
9 (gv1) (gv2) > (g 9) g)
ey1
ey2
y1
y/2
(117)
So any is a bijective mapping on X. Since every element of Rg either 0 or 1, Rg is permutation matrix.
Lemma 9 (Summation of Rg). If the group action is transitive, then Eger Rg |G| 11T.
Proof. Simply apply Lemma 14 and notice that for transitive group action, X/G (Y}.
Lemma 10 (Co-set Mapping tu). There is bijection between {1o (I) Juex and co-sets [G G of group stabilizer Ga. := {g E Glgro = 2 which is a subgroup of G fixing Zn-
Proof. First have
()(g) = (h) + gyo hyo = h = h G = h gG (118)
So for any 9Wo. all elements in 4n (v) are also in gGy, and vice versa. The bijection is:
l (y) gG
for y gy0
(119)
or equivalently,
y + 4o(9Ggo)
(120)
Lemma 12. If E (x), then for any x' E X, gx' = xx'
Proof. For g E 1o (x)), we have gag = x. For any = hro, we have:
gz' -hooo (gh)xo
(121)
On the other hand, by definition, xx' == to(ghGzo) = (gh) So for any x', gr' xx'
32

---

Counts
20
10
d=71, wd=1e.05
d=71, 5d:
d=71. wd=0,0000
d=71. wd=0.0002
d=71. wdw wd=0.0005
Count
100
d=127. wd=le 05
d=127, wd=5e 95
d=127. ad=000001
d=1277 ww:
d=:27, wd=000005
100
5
Salucion onter
Solution order
Solution orter
Soaicion onder
Solution order
Figure 8: Distribution of solutions with hidden size 256.
Additional Experiments
Algorithm to extract factorization from gradient descent solutions. Given the solutions obtained by gradient descent using Adam optimizer, we first compute the corresponding z via the Fourier transform (that is. Eqn. [1]. Here [zpkj] 3-by-d-by-g tensor. Here d |G] and q is the number of hidden nodes in the 2-layer neural networks.
Then for each frequency k, we extract the salient components of by thresholding with a universal threshold (c.g. 0.05). The number of salient components (c.g., 6 or 4) is the order the per-frequency solution.
Suppose we now get (k) for frequency k. which a 3-by-6 (and thus an order-6) solution. Then we enumerate all possible permutation of 6 hidden nodes (6! = 720 possibilities) to find one permutation that ||ppk(()) 2pk- 2ppk-l is minimized, following ring multiplication defined in Def. Note that for each permutation, we also need to consider whether := [-1, -1, can be applied to each hidden node (i is also defined in Tbl. []. This is because both + 22 and ø1 + 1 * have
exactly the same values all sum potentials (SPs) we consider, due to the fact that r(1) 1 for any r E Rgg R. U Rn R. Therefore call "pseudo-1".
For search efficiency, we therefore first consider the permutation т so that [| - =ck- 2 = is minimized, since the component is invariant to the pseudo-1 1 transformation 1, and then for those cligible T, we search whether 1 should be applied when considering E (a,
Once find such 21 and 22, convert them into their canonical forms ει and ΣΑ (Def. 8 to eliminate any possible multiplicative term so that 2 y 21. We then compare the canonical forms (up complex conjugate) with various order-3 and order-2 partial solutions constructed by CoGS, as detailed in Sec.5) [ If their distance is below a certain threshold (e.g., < 10% of the norm after normalizing both and ε2), then match is detected.
33

---

6-23, wd-1e.05
d-23, wd-5e-05
d=23, wd=0,0001
6-23, wd=0,0002
4-23, wd=0 wd=0.0005 0005
Courts
20
26
dm71, wdm1e.05
dm71, wd-5e-05
dw71, wdm0.0001
dm71. wdm0.0002
d-71,
Counts
200
100
100
100
30
wd-le-05
wd=5e-05
wd=0
d-127, wd-0
200
200
200
100
100
Solation
Figure 9: Distribution of solutions with hidden size 512.
d-23, wdw
dw23, wd-5e-05
dw23, wdm8.0001
d-23,
d=23, 0005
couns
20-
20
10-
5d=5e-05
wd=000001
wd=0.0002
d-71,
Counts
50
d-127. wd-1e.05
d=127. wd=5e-05
dl=127, ad=0.0001
d=127, www.//ww.0000000 0002
d=127, wdw0 wd00,0005 0005
200
100
Sutucam onder
Solution order
Solution orter
Soltion order
Solution onder
Figure 10: Distribution of solutions with hidden size = 1024.
wd=1e.05
5d-5e-05
d=23, wd-0.0001
d-23,, wd=0.000
d-23, wdl 0005
Counts
Gm wd-1e.05
dm Wdl
d-71, wd=0000001
d=71, wd=0.0002
d-71, www 0.00
Counts
30-
100
100
100
50
50
d=127, wd-1e-05
d2727, wd=5e-05
d-127, wd=0.0001
d-127, wdd000000
d=127, wd-d 0005
100
100
10
5
10
Solucion ander
Solution order
Soludon oderr
Soluzion order
Solution order
Figure 11: Distribution of solutions with hidden size g 2048.
-3p4
174
3m04
-2m23
-103
m13
2nn²3
//2
112
40
2
-2
3
-2
-2
Angle
Angle 8
Figure 12: Distribution of free parameters (E. v. a and 3, all with magnitude 1) in three kinds of gradient descent solutions identified by CoGS. While any value of these parameters makes a global solution, gradient descent dynamics has particular preference in picking them during optimization.
34


Reviews:
[{"review_id": "1I7XV3M6QF", "reviewer": "Reviewer_FLjB", "summary": "This paper introduces CoGS (Composing Global Solutions), a theoretical framework that reveals a rich algebraic structure in the weight space of 2-layer neural networks with quadratic activation trained on group multiplication task. By showing that the weights form a commutative semi-ring and that the L2 loss decomposes into sum potentials, CoGS enables global solutions to be analytically composed from partial ones. The authors construct low-order Fourier-based and perfect memorization solutions and demonstrate that approximately 95% of solutions found by gradient descent match these theoretical forms.", "questions": "Overall, I find this to be a strong theoretical paper with a meaningful contribution to the algebraic aspects of neural network learning. However, there are a few points I would like the authors to clarify:\n- The empirical results focus primarily on synthetic group multiplication tasks. To what extent do the authors believe the key findings could generalize to real-world settings where the underlying structure is implicit or unknown? It would strengthen the work to either discuss this more explicitly or explore empirical validations beyond group-structured tasks.\n- The paper briefly touches on grokking in the conclusion. Given that this is a well-known behavior that usually occurs during training, can the authors comment more specifically on how the CoGS framework can be extended to explain this phenomenon?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strength**\n- The paper introduces a rigorous algebraic framework (CoGS) that reveals a previously unrecognized semi-ring structure in the weight space of 2-layer neural networks and interprets the L2 loss through ring homomorphisms. This perspective provides clear, sufficient conditions for identifying global optima and offers a systematic way to construct them analytically.\n- The theoretical predictions are validated by experiments showing that about 95% of gradient descent solutions exactly match the proposed constructions, with minimal reconstruction error. This high degree of empirical alignment reinforces the practical relevance of the theoretical insights.\n- The paper provides good explanations for why gradient descent with weight decay prefers low-order, structured solutions over high-order ones like perfect memorization. It links this preference to topological and algebraic connectivity between solutions of different orders.\n\n**Weaknesses**\n- The theoretical framework is developed specifically for 2-layer networks with quadratic activations trained on group operations (e.g., modular addition), assuming full knowledge of the data's algebraic structure. This limits its applicability to real-world settings where such structure is unknown or more complex. \n- While CoGS successfully constructs a family of global solutions, it does not cover all possible global optima.", "was_revised": true, "final_justification": "I recommend acceptance for this paper due to its theoretical contribution which is supported by the empirical evident.", "rebuttal": "We thank the reviewers for the insightful and encouraging feedback! We are glad to hear that the reviewer thinks that the paper is rigorous theoretically, able to identify previously unknown structures, performs thorough experiments that align well with the theory, and provides good explanation. We address the questions below:\n\n# Application to real-world settings\n\nFirst we want to clarify that in our current setting, we don’t need to know the underlying specific group structure (e.g., for order-6 group, whether it is $Z_6$ or $Z_2 \\otimes Z_3$) before the learning, and after learning, solutions of specified structure emerge according to the theory, given that it is an Abelian group.  \n\nFurthermore, in the appendix (Appendix F), we have extended this work to group action prediction, which concerns a state space $\\mathcal{X}$ and group $G$ that acts on it, to yield a different state in the state space. This setting covers more practical scenarios such as learning of a transition function in RL that takes the state and action pair $(s,a)$ as the input and returns the next state $s’$. \n\nGoing beyond, in order to deal with real-world data distributions (e.g., mixture of group structures, missing data, noise, etc), extended analysis is needed. For example, instead of using quadratic activations, we may need to consider truncated quadratic activations, or squared ReLU (e.g., $\\sigma(x) = \\max^2(x, 0)$, which is empirically used in large model training (check [1])), and study whether different neurons can capture various local structures, by masking out irrelevant structures and noise automatically. Also, self-attention is needed when the text input contains compositional and heterogeneous structures (e.g., a sequence “The modular addition of 2 and 4 mod 5 is 1” rather than “2 4 1”). The intuition is that self-attention will force the model to focus on important parts of the previous input, and omit others. Ideally, the model focuses on “2” and “4” when predicting the answer “1”, and it focuses on “modular addition” when reading “mod 5”. How the learning picks such a mechanism remains a mystery. \n\n# Grokking\n\nOur analysis gives some intuition regarding grokking. Theorem 1 shows that the loss function is a summation of a linear term ($r_{kkk}$) and a few quadratic (sum of squares) terms in the Fourier domain. When the weights are small, the quadratic terms are much smaller than the linear term and the weights grow at a uniform pace. This means that all the weights are similar in magnitude (in the Fourier domain) and memorization happens (check the perfect memorization solution in Eqn. 7 in Corollary 3, in which all weights in Fourier domains have the same magnitude). However, when the weight magnitude becomes larger, the quadratic terms (as well as weight decay) catch up, which leads to specialization of hidden neurons into different frequencies, which is the generalization solutions (order-4 and order-6 solutions in Corollary 2 and 5).\n\nFrom this analysis, it is clear that we need a small learning rate to demonstrate the entire phase transition process, and a fairly large weight decay to trigger node specialization, converging to low-order solutions, as suggested in Theorem 6. This simple analysis seems to align with existing studies [2], i.e. small learning rate and reasonably large weight decay lead to grokking, and the model stays in memorization with super small weight decay (e.g., Fig. 7(b) and 8(b) in [2]).\n\nNote that this is a very rough qualitative analysis and lots of questions remain, e.g. percentage of training samples out of all possible distinct pairs to enable such transition, etc. The current framework will lead to additional terms of Theorem 1, if the training distribution is no longer uniform across all input pairs. This makes analysis complicated. Therefore, we leave it for future work.\n\n# Not covering all possible global optima\n\nWe agree that we do not cover all possible global optima in this paper, and there may exist solutions that do not satisfy the sufficient condition shown in Lemma 1. Actually we have constructed it (Corollary 5, $F4/6$). Nevertheless, the fact that the gradient descent solutions fall into the constructed solutions shows that these constructions are useful and may connect to the gradient dynamics that governs the training process. \n\n\n# References \n\n[1] Noam Shazeer. Glu variants improve transformer. arXiv preprint arXiv:2002.05202, 2020.\n\n[2] Towards Understanding Grokking: An Effective Theory of Representation Learning (https://arxiv.org/abs/2205.10343)"}, {"review_id": "Rv2uXppgQ6", "reviewer": "Reviewer_LrXm", "summary": "This work introduces CoGS (Composing Global Solutions), a theoretical framework that identifies and characterizes an algebraic structure that exists over global solutions to group multiplication tasks with 2-layer neural networks. The authors identify a sufficient condition for global solutions, construct examples of global solutions that do (Z_F6) and do not (Z_F4/6) satisfy the sufficient conditions, and demonstrate how partial solutions can be combined to form global solutions. The work supports its theoretical framework with empirical experiments, finding that up to 95% of neural networks trained with gradient descent can be decomposed into solutions that match the provided constructions. The authors provide a theoretical statement of Occam's Razor in the CoGS setting, proving that gradient dynamics prefer simpler solutions that have lower order under the proposed algebraic structure.", "questions": "- Lemma 1 provides sufficient conditions for global optimality, and the authors identify global solutions that do not satisfy them (e.g. Z_F4/6). Does the CoGS framework characterize the full set of global solutions, or are there also classes of zero-loss solutions that exist outside the algebraic framework?\n- Relatedly, were the authors able to identify what solutions the neural networks were converging to in the 2-5% of cases for which gradient descent did not converge to a composition of your constructions?\n- How generalizable are the work's results/framework to changes in activation (e.g. ReLU) or loss (e.g. cross-entropy)?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths:\n- The work is original. The idea of identifying algebraic structure over neural network solutions is novel, as far as I am aware. Furthermore, the work is related to an important problem in the field, understanding grokking and how NNs solve arithmetic tasks.\n- Theoretical analysis is novel and comprehensive. The authors provide sufficient conditions for global solutions, propose constructed solutions, and analyze gradient dynamics.\n- Empirical results are comprehensive and convincing. The fact that the authors identify compositions of their constructions within neural networks trained with gradient descent strongly supports their proposed framework.\n\nWeaknesses:\n- The work focuses on 2-layer neural networks with quadratic activations, L2 loss, and abelian group multiplication tasks. This setting is already interesting, but the work would be strengthened if the framework were extendable to further settings.", "was_revised": true, "final_justification": "After reading the response from the authors and the discussion from the other reviewers, I am more confident in my assessment about the work and maintain my score accordingly.", "rebuttal": "Thanks the reviewer for the insightful and encouraging comments! We are glad to hear that the reviewer thinks the work is original, is related to important problems in the field, and with comprehensive and convincing experiments. We reply the questions below. \n\n> Does the CoGS framework characterize the full set of global solutions, or are there also classes of zero-loss solutions that exist outside the algebraic framework?\n\nNo it doesn’t characterize the full set of global solutions. F4/6 (Corollary 5) is an example that does not satisfy the sufficient condition but still remains global optimal. \n\n> Relatedly, were the authors able to identify what solutions the neural networks were converging to in the 2-5% of cases for which gradient descent did not converge to a composition of your constructions?\n\nDuring our empirical study, these solutions are solutions that fit “almost” into our construction, but are ruled out due to the fact that they didn’t pass the pre-defined numerical thresholds when determining which composition the solution should belong to. If we train longer, they may fall into the threshold. We haven’t seen solutions that are fundamentally different from our theoretical construction yet. \n\n> How generalizable are the work's results/framework to changes in activation (e.g. ReLU) or loss (e.g. cross-entropy)?\n\nFor **cross-entropy**, note that in Theorem 1, we use projected $\\ell_2$ loss (i.e., $\\|P_1^\\perp (\\mathbf{y} - \\mathbf{o} / 2d)\\|^2$), and cross entropy can be written in a similar form as well. Please check Lemma B.2 in [3] for details. Roughly speaking, the gradient of cross entropy loss $-\\log\\left[\\exp(\\mathbf{o}^\\top \\mathbf{y}) / \\mathbf{1}^\\top \\exp(\\mathbf{o})\\right]$ is the same as the gradient of the following surrogate loss $|P_1^\\perp (\\mathbf{y} - \\gamma \\mathbf{o} / d)|^2$, where $\\gamma = (1 + \\mathbf{o}^\\top P_1^\\perp \\mathbf{o} / 2d + o(\\mathbf{o}^\\top P_1^\\perp \\mathbf{o} / 2d) )^{-1}$ depends on the zero-mean norm of $\\mathbf{o}$, the unnormalized logits before softmax. When this norm is much smaller than $d$, then $\\gamma \\approx 1$, then the exact sample analysis can be applied to cross entropy loss, except for some changes of the constant coefficients in the loss decomposition (Eqn. 3). \n\nIn practice, the unnormalized logits $\\mathbf{o}$ may grow unbounded in magnitude. This makes $\\gamma$ shrink to a very small number, and thus the first loss term $\\sum_{k\\neq 0} r_{kkk}$ in Lemma 1 will dominate. If we only consider this term in finding our global solutions, the found solution would be much simpler and of lower order. Experiments also support that. \n\nFor **other activations**, we can do a Taylor expansion and analyze the high order teams that would appear in Theorem 1 (and quadratic activation is just a special case). Unfortunately, it will make the terms quite complicated. So there should be a better way of doing it, which we leave for future work.\n\n\n[3] J. Zhao, GaLore: Memory-Efficient LLM Training by Gradient Low-Rank Projection, ICML’25"}, {"review_id": "VljJNi6O1A", "reviewer": "Reviewer_S1jd", "summary": "This work aims to study how neural networks with one set of hidden neurons learns to perform computations on Abelian groups - with modular addition being a notable instantiation of the problem which has received recent interest in the community. The primary result of this work shows that global solutions can be obtained by composing local solutions which, in the case of neural networks, means that portions of the network's hidden layers will each perform meaningful parts of a larger computation which results in the globally optimal solution. Experiments on modular addition show that the vast majority of neural networks converge to these composable solutions rather than learning monolithic solutions, corresponding to memorisation.", "questions": "It is difficult to phrase my concerns as questions, but I would be happy to continue the discussion on my above points during the rebuttals phase. It would help if the authors could clarify any mistakes I may have made in my comments above, and answer any of the smaller questions mixed in there.", "limitations": "I don't feel the limitations of this work were accurately stated and I have raised this as a weakness for quality above.", "rating": 2, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 1, "clarity": 1, "significance": 2, "originality": 2, "strengths_and_weaknesses": "# Strengths\n## Quality and Significance\nThe experimental results seem to support the broad points of the theory and I agree that it is important to the community that we begin to understand how neural networks solve more algorithm tasks. The fact that modular addition has been a recent task of interest to the mechanistic interpretability community speaks to this works potential significance. Additionally, the generality of the work in considering tasks on an abelian group further increases its applicability.\n\n# Weaknesses\n# Clarity\nIn general I find this work to be extremely unclear. Grammatically the text itself is difficult to read and contains long sentences which end abruptly. The abstract for example has the following sentence: \"Specifically, we show that the weight space over different numbers of hidden nodes of the 2-layer network is equipped with a semi-ring algebraic structure, and the loss function to be optimized consists of sum potentials, which are ring homomorphisms, allowing partial solutions to be composed into global ones by ring addition and multiplication\". Unfortunately this problem persists throughout the writing. Secondly, almost no effort is made to limit the jargon which is very specific to the group theory tasks being considered. For example in the introduction it says: As a result, our theoretical framework, named CoGS (i.e., Composing Global Solutions), successfully constructs two distinct types of Fourier-based global solutions of per-frequency order 4 (or “2 ×2”) and order 6 (or “2 ×3”), and a global solution of order d2 that correspond to perfect memorization\". At this point in the text the notion of \"per-frequency order\" had not been discussed at all. This is particularly problematic in this case as it is the sentence highlighting the contribution of the proposed CoGS framework. A few other examples in the early paragraphs of points I found vague (to try highlight my point and make things more actionable):\n- Lines 67 and 68: \"Existing works on expressibility (Li et al., 2024; Liu et al., 2022) gives explicit weight construction of neural networks weights (e.g., Transformers)\". I have no idea what it means to give a weights construction of neural network weights.\n- Lines 110 and 111: \"We exclude $\\phi_0 ≡ 1 $ because the constant bias term has been filtered out by the top-down gradient from the loss function\". What does it mean for the bias term to be filtered out by the gradient?\n- Figure 1: While Figure 1 is helpful to try contextualise everything (and I found myself returning to this figure often), the numbers in the caption are not present in the image.\n\nConsidering the clarity of the mathematics. Notation is not always introduce well and there a typos which make the already dense notation even more taxing. For example on Lines 109 and 110 $\\phi_{-k}$ is used to be the complex conjugate of $\\phi_k$ but the notation for complex conjugates had already been introduced. Another example is on Line 101, where $P_1^\\perp$ is introduced with little justification for its need. Also, Definition 5 seems to try to define concatenation twice but using different notation each time. I also find it quite unhelpful to refer to notation as nouns in text, especially when the notation is given no explicit intuition to help ground the variable. The worst example of this is the \"$r$ terms\" which are defined mathematically on Line 115 and then referenced as entities thereafter. This serves a particular disservice to Definition 1. Lastly, the absence of proof sketches (or even references in the main text to proves in the appendix) makes it very difficult to understand the contributions of the work - especially when coupled with the complex notation and needless definitions in some cases. For example, it is surprising that Definition 2 and 3 were deemed necessary but then the Kernel of $r$ was left as a footnote and without formal definition at all (and it seems necessary to connect the geometry of the weights to the loss, no?). Another example here is that Sum Potentials are referenced four times before Definition 6 and after Theorem 1 where it is necessary to appreciate the point of the theorem (as is stated on Lines 45 and 46).\n\n## Quality\nI have three main concerns for quality. The first two are quick to summarise: firstly I do not feel the assumptions of the theory or work are clearly stated. This could be a consequence of the other clarity issues, but I find it surprising that no assumptions seem to be mentioned (especially when prior work had such strong assumptions such as infinite width). Secondly, there is little acknowledge of the limitations of this work. The problem setup and architecture is very specific and the use of one-hot encodings is a big limitation (other works in this space allow for an initial embedding layer even). In addition, the experiments show that gradient descent follows the theoretical construction in most cases, but this is on one instantiation of a reasoning task on an Abelian group. There is no guarantee any other task would similarly follow the theory but the work seems to see the modular arithmetic example as conclusive. This leads me to my final concern, I think the claims around the theory matching experiments is too imprecise and the in some cases the text over claims how close this fit is. For example the abstract says the experiments fit the theory 95% of the time, but then Lines 246 and 247 actually make it clear that \"Although characterizing the full gradient dynamics is beyond the scope of this paper, we theoretically characterize some rough behaviors below\". This is then followed by Lines 277 to 282 which claim exact matches between the theoretical construction and empirical solutions. None of those three statements seems to be consistent to me.\n\nI hope my comments here at least serve to constructively guide the exposition of the paper. While the work itself seems promising, the paper as it stands feels rushed.", "was_revised": true, "final_justification": "I have considered the authors rebuttal closely and reread the paper with the additional information and explanations in mind. I remain sceptical that the paper is ready for publication at this time. I do think the research itself is interesting and addressing a timely setting which is of present interest to the community. However, the presentation of the work and lack of formal statements means it is difficult to determine the full extent of the authors claims and to assess the rigour of the work. These are important considerations and to me are dealbreakers regardless of how much I like the work itself.", "rebuttal": "Thanks the reviewer for the comments! We are glad to hear that the reviewer acknowledges that our work has addressed important problems that the community cares (modular addition and more broadly Abelian group), and come up with experiments that align with the theoretical construction.  \n\nIn general we agree that the notation can be improved to make them easier to understand. We are addressing the detailed questions below. \n\n> I have no idea what it means to give a weights construction of neural network weights\n\nWe want to make sure the reviewer knows that there is a large body of literature on network expressibility, which aims to explicitly construct weights for the network so that they can accomplish certain tasks. E.g., expressibility of Transformers [4][5], CoTs [7][8], Graph Neural Networks[9], general Deep Neural Networks [10], etc. Here we just list a few literatures. The goal is to find the upper bound of capability for a certain network architecture. Whether the training procedure may achieve the constructed solution remains an orthogonal question. \n\nReferences:\n\n[4] https://aclanthology.org/2024.tacl-1.30.pdf \n\n[5] https://www.jmlr.org/papers/volume22/20-302/20-302.pdf \n\n[6] https://arxiv.org/abs/1912.10077 \n\n[7] https://openreview.net/pdf?id=NjNGlPh8Wh\n\n[8] https://arxiv.org/abs/2402.12875 \n\n[9] https://arxiv.org/abs/1810.00826 \n\n[10] https://arxiv.org/abs/1606.05336 \n\n\n> What does it mean for the bias term to be filtered out by the gradient?\n\nSince we are optimizing a projected $\\ell_2$ loss $\\|P^\\top_1 (\\mathbf{o}/2d - \\mathbf{y})\\|^2$, the output $\\mathbf{o}$ is zero-meaned (i.e., projected by $P^\\top_1$) before sending to loss. So if we shift $\\mathbf{o}$ by a constant vector, then it won’t change the loss. \n\nOn the other hand, the backpropagated gradient also contains the $P^\\top_1$ term, which makes the gradient zero-mean. So if there is any bias term in the weights, such a bias term will neither affect the output nor change over time. Therefore, we can just ignore them when finding global solutions (that’s also why we have $k\\neq 0$ for all the Fourier expansions of the weights (Eqn.2)). \n\n> the numbers in the caption are not present in the image\n\nThanks for the suggestions. We will update it in our next revision to make the story more clear. \n\n\n> “I find it surprising that no assumptions seem to be mentioned (especially when prior work had such strong assumptions such as infinite width)” \n\nThat’s one of the core contributions of this work. We don’t assume infinite width in our analysis (and do not leverage the existing framework such as Neural Tangent Kernel or mean field) and theoretically characterize the fine-grained algebraic structure of the global solutions in the setting we have specified. To our best knowledge, such a structure hasn’t been studied before in the literature (other reviewers also agree upon it). \n\n\n> the use of one-hot encodings is a big limitation (other works in this space allow for an initial embedding layer even\n\nUsing one-hot encoding is for mathematical clarity and simplicity. We can always extend this analysis to any fixed orthogonal embedding matrix, which corresponds to a global rotation of all the weight matrices. Many peer-reviewed top-conference papers also leverage such assumptions (e.g., reverse curse [11], Joma [12], etc) to facilitate theoretical study. For embedding matrices whose embeddings are not orthogonal or updates during training, we leave it for future work. \n\n[11] https://arxiv.org/abs/2405.04669 (NeurIPS'24)\n\n[12] https://arxiv.org/abs/2310.00535 (ICLR'24)\n\n> For example the abstract says the experiments fit the theory 95% of the time, but then Lines 246 and 247 actually make it clear that \"Although characterizing the full gradient dynamics is beyond the scope of this paper, we theoretically characterize some rough behaviors below\"\n\nWe want to make it clear that there are two different (and often orthogonal) aspects of theoretical study, (1) studying the solution structures (i.e., what solutions we get after training) and (2) studying the gradient dynamics (i.e., how we get there). Our paper is about (1), which itself is a nontrivial topic, and we leave (2) as the future work. For (1), our work characterizes the algebraic structures of the final solutions, by leveraging the property of the loss function. \n\n> For example on Lines 109 and 110  is used to be the complex conjugate of  but the notation for complex conjugates had already been introduced\n\nThis is for notation convenience. E.g., we can write $\\sum_k c_k \\phi_k$ rather than separating it into two summations, $\\sum_{k=1}^{\\lfloor d/2 \\rfloor} c_k \\phi_k$ and its complex conjugate counterpart. \n\n> Definition 5 seems to try to define concatenation twice but using different notation each time.\n\nWe kindly disagree. Def. 5 defines the addition and multiplication operations of the weights, which are the key operations for the semi-ring structure that support the entire algebraic framework. The concatenation (as the addition) and the Kronecker’s product (as the multiplication) are two very different operations and cannot be regarded as “defining two concatenations twice”. \n\n> … but this is on one instantiation of a reasoning task on an Abelian group. There is no guarantee any other task would similarly follow the theory but the work seems to see the modular arithmetic example as conclusive.\n\nTheory always has its assumption and range of applications. We never claim that we solve *all* reasoning tasks on Abelian groups, but a representative example like modular additions, and never regard the modular arithmetic problem as conclusive for the reasoning tasks.  \n\n> For example, it is surprising that Definition 2 and 3 were deemed necessary but then the Kernel of  was left as a footnote and without formal definition at all \n\nThe paper is math heavy and we don’t want to introduce additional formal definitions in the main text. On the other hand, we want to give more math details for people who have relevant mathematical backgrounds and are interested."}, {"review_id": "kkzhDW6G3G", "reviewer": "Reviewer_thrr", "summary": "This paper analyzes the algebraic structure of the loss minimum for a two-layer network with quadratic activations trained to do modular arithmetic.  They find the weight space has the structure of a semi-ring and the loss can be decomposed in terms of ring homomorphisms.  Using this ring structure, the authors construct explicit weight values which minimize the loss and show empirically that gradient descent usually converges to these solutions, favoring lower order (fewer non-zero neurons) solutions.  The authors also prove mode connectivity implying gradient flow will favor lower order solutions under L2 regularization.", "questions": "- Can you help me understand Thm 6? What is J and what does it mean for the dynamics of the SPs to be decoupled? \n- In some sense, cross-entropy loss would make more sense for the task.  I assume L2 loss was chosen to make the analysis work? \n- Is it possible to say how much of the minimum Lemma 1 describes?\n- For Fig. 2 why do the weights for z_a z_b and z_c look so similar?", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "## Strengths\n- The theoretical analysis in this paper is inventive, rigorous, and insightful.  Despite the simple setting, the authors are able to explicitly describe the minimum.  \n- The algebraic structure they describe for the weight space is very interesting on its own, but it also provides insight to gradient dynamics. \n- The experiments show that GD actually converges to these minima most of the time. \n- The decomposition of the loss into SPs and the leveraging of the ring structure to create an algorithm to produce solutions is clever.  Moreover, from my (incomplete) understanding of Thm 6, this decomposition is relevant to finding the full solution via gradient descent as well since as q grows, the SPs are \"decoupled.\"   \n- I found Thm 5 interesting since it provides a theoretical backing for mode connectivity (in this simple setting) and theoretical justification for preference for simpler more generalizable solutions.  There is minimal theoretical progress in this area and this work provides an interesting and different perspective.\n- The limitations are clear and the future work is nicely described.  I particularly appreciate that point that its useful to put different widths in the same framework.  I think the idea to develop new training algorithms based on this seems like a longshot, given that we don't know how this generalizes, but I appreciate the idea.  \n\n## Weaknesses \n- The current work is limited to a fairly toy problem (modular arithmetic / abelian group composition) and a small network (2-layer) with an uncommon and simple activation \\sigma(x)=x^2.  The authors acknowledge this limitation and suggest taylor approximations can be used to generalize their work to other activations.  While I am noting this limitation and the fact that the insights here may not scale to larger networks or other problems, I still think these choices make for a reasonable trade-off.  The paper is able to reach very insightful conclusions  in this restricted setting which makes these restrictions reasonable. \n- The notation and indexing could be a big cleaner.  Overall, this is not so easy to solve since there is a lot to keep track of, but I wasn't a huge fan of using {a,b,c} as index values.   For example w_{aj} is a 2-dim tensor, but the group index is actually suppressed here and \"a\" refers to the layer but as a layer name, not an index.  The index value for layer is p.   \\mathbb{I} is not defined, but I can infer its the characteristic function.  Also, in Thm 6 J is not defined.  \n- There is some informal terminology would I appreciate if it were made more precise.  For example, L234 \"mixed\", L243 \"solution solution\".  The argmax on L190, it took me a bit to understand the arg is considered \\mathbf{u}, so maybe clarify that. L174: \"once we reach 0/1-sets\" -- Can you spell out precisely what this means?  I believe I understand L193-L194 but it could be clearer.   \n- The related works section on algebraic structures in ML is pretty short.  Are there no other instances?", "was_revised": true, "final_justification": "The rebuttal answered my questions. Per my comments, I do think clarity and precision can be slightly improved. I keep my positive score.", "rebuttal": "We thank the reviewer for their insightful and encouraging comments. We are glad to hear that \"the theoretical analysis in this paper is inventive, rigorous, and insightful\". Thanks! Here are the answers to the questions. \n\n> The related works section on algebraic structures in ML is pretty short. Are there no other instances?\n\nThere are relatively few papers on algebraic structures in ML. We list a few more below and will add them to extended literature sections in the appendix. Most of the existing literatures focus on injecting algebraic structures (e.g., invariants) into the features and/or neural networks to improve its performance, while our paper focuses on the emerging algebraic structures after training a neural networks on structured data. So overall the research direction is very different. \n\n[1] 1990, On the algebraic structure of feedforward network weight spaces\n\nThis paper focuses on “universal” invariant transformation (and associated group) of the network weights that leads to identical output for any given inputs. This includes permutations of nodes, scale up one layer while scale down other layers, etc, which is universal to any input/output pairs. In contrast, our formulation focuses on algebraic structures induced by a family of specific (yet important) problems. Such specificity (e.g. the task to be learned has group structure) leads to rich structures in the resulting weights. Our formulation also automatically removes the invariants studied by the paper, by identifying networks with permuted hidden nodes and by normalizing the coefficients z, and focus on algebraic structure beyond [1]. \n\n[2] 2021, Algebraic neural networks: Stability to deformations\n\nThis paper constructs a novel network architecture called AlgNN, by adding algebraic layers which apply group operation to the intermediate representation of the neural network to achieve certain properties. AlgNN is mostly used as a framework to unite multiple existing data processing pipelines (e.g. convnet, discrete time signal processing, graph/group neural network, etc). While our paper studies the structure of global solutions and performs experiments to verify the theoretical findings, [3] does not cover these topics. \n\n[3] 2024, Unitary convolutions for learning on graphs and groups\n\nThis paper imposes a set of constraints on the network weight (unitary group convolution) to enable stable training (and avoid over-smoothing problems) for graph neural networks. It does not try to characterize the structure of global solutions led by the gradient descent, but more focuses on improvement of empirical performance. \n\n[4] 2024, A Galois theorem for machine learning: Functions on symmetric matrices and point clouds via lightweight invariant features\n\nThis paper focuses on constructing invariant features on matrices subject to joint permutation of rows and columns using Galois theorem, and uses such features for point clouds classification. The paper also shows how many such features are needed in order to yield a good classification. Overall it does not concern neural networks and its internal mechanism and representations, which is the topic of our paper. \n\n\n> Can you help me understand Thm 6? What is J and what does it mean for the dynamics of the SPs to be decoupled?\nPlease check Appendix E for the definition of Jacobian matrix $J$, which is defined as the partial derivative between a collection of sum potentials (SPs) and the weights. Theorem 7 means that if we have infinite width and if the loss function is simplified, then the dynamics of each sum potential r is decoupled, that is, the dynamics of r_1 and r_2 are independent and does not interfere with each other, at least at (or near) the initialization. \n\n> In some sense, cross-entropy loss would make more sense for the task. I assume L2 loss was chosen to make the analysis work?\n\nYes. Here is an analysis when the loss function is cross-entropy. Note that in Theorem 1, we use projected $\\ell_2$ loss (i.e., $\\|P_1^\\perp (\\mathbf{y} - \\mathbf{o} / 2d)\\|^2$), and cross entropy can be written in a similar form as well. Please check Lemma B.2 in [3] for details. Roughly speaking, the gradient of cross entropy loss $-\\log\\left[\\exp(\\mathbf{o}^\\top \\mathbf{y}) / \\mathbf{1}^\\top \\exp(\\mathbf{o})\\right]$ is the same as the gradient of the following surrogate loss $|P_1^\\perp (\\mathbf{y} - \\gamma \\mathbf{o} / d)|^2$, where $\\gamma = (1 + \\mathbf{o}^\\top P_1^\\perp \\mathbf{o} / 2d + o(\\mathbf{o}^\\top P_1^\\perp \\mathbf{o} / 2d) )^{-1}$ depends on the zero-mean norm of $\\mathbf{o}$, the unnormalized logits before softmax. When this norm is much smaller than $d$, then $\\gamma \\approx 1$, then the exact sample analysis can be applied to cross entropy loss, except for some changes of the constant coefficients in the loss decomposition (Eqn. 3). \n\nIn practice, the unnormalized logits $\\mathbf{o}$ may grow unbounded in magnitude. This makes $\\gamma$ shrink to a very small number, and thus the first loss term $\\sum_{k\\neq 0} r_{kkk}$ in Lemma 1 will dominate. If we only consider this term in finding our global solutions, the found solution would be much simpler and of lower order. Experiments also support that. \n\n> For Fig. 2 why do the weights for z_a z_b and z_c look so similar?\n\nThey are so similar since they all converge into Fourier bases with the same frequency, and thus their magnitudes peaked at the same frequency in the Fourier domain. Their phrases are different though (which is not plotted in the figure).\n\n> Is it possible to say how much of the minimum Lemma 1 describes?\n\nWe are not sure what the reviewer means. Lemma 1 characterizes a sufficient condition to achieve global minimal (i.e., the loss function becomes zero, which is the smallest number of a $\\ell_2$ loss could achieve)."}]

Author rebuttal:

Meta-review: This work presents a theoretical approach that uncovers algebraic properties within the weight parameters of two-layer neural networks using quadratic activations when trained on group multiplication problems. Specifically, it shows that these weight exhibit the mathematical structure of a commutative semi-ring, while the L2 loss function can be broken down in terms of ring homomorphisms. The authors provide some theoretical results that further allow an analytical construction of global solutions by combining partial solution components, and also establish a mode connectivity result.

The empirical studies/simulations in this work show that gradient-based optimization with L2 regularization tends to converge toward solutions of lower order solution, which tends to support the theoretical results.

During the internal discussion, a couple of reviewers championed this paper, and it is therefore recommended for acceptance.

Nevertheless, I encourage the authors to consider the feedback from Reviewer S1jd (and others as well) when revising the paper, in order to make it accessible to a broader community. Here is a *partial* list:
1. Two reviewers who gave positive reviews were not sure about the significance and implications of Theorem 6. One of them stated that they didn't fully understand Theorem 6.
2. During the internal discussion, Reviewer S1jd wrote "The authors in the rebuttals did not seem inclined to add assumption statements or other more formal ways of presenting the limits of their theory and so I do not feel inclined to adjust my scores."
Decision: Accept (poster)