The impact of allocation strategies in subset learning on the expressive power of neural networks
Authors: Ofir Schlisselberg
Ran Darshan
Venue: ICLR 2025 Poster (2025)
Keywords: subset learning
theoretical neuroscience
expressive power
neural networks
recurrent neural network
Primary area: applications to neuroscience & cognitive science
TL;DR: This paper takes the first step to theoretically analyzing the expressive power of different allocation strategies in subset learning.

Abstract: In traditional machine learning, models are defined by a set of parameters, which are optimized to perform specific tasks. In neural networks, these parameters correspond to the synaptic weights. However, in reality, it is often infeasible to control or update all weights. This challenge is not limited to artificial networks but extends to biological networks, such as the brain, where the extent of distributed synaptic weight modification during learning remains unclear. Motivated by these insights, we theoretically investigate how different allocations of a fixed number of learnable weights influence the capacity of neural networks. Using a teacher-student setup, we introduce a benchmark to quantify the expressivity associated with each allocation. We establish conditions under which allocations have \`maximal' or \`minimal' expressive power in linear recurrent neural networks and linear multi-layer feedforward networks. For suboptimal allocations, we propose heuristic principles to estimate their expressivity. These principles extend to shallow ReLU networks as well. Finally, we validate our theoretical findings with empirical experiments. Our results emphasize the critical role of strategically distributing learnable weights across the network, showing that a more widespread allocation generally enhances the network’s expressive power.

Published as a conference paper at TCLR 2025
THE IMPACT OF ALLOCATION STRATEGIES IN SUBSET LEARNING ON THE EXPRESSIVE POWER OF NEURAL NET- WORKS
Ofir Schlisselberg Tel Aviv University ofirs4@mail. acu.ac.il
Ran Darshan
Tel Aviv University Stalaanttauuxttaa waw.ssttaaa.....
ABSTRACT
In traditional machine learning, models are defined by a set of parameters, which are optimized to perform specific tasks. In neural nelworks, these parameters correspond lo the synaptic weights. However, in reality, it often infeasible to control update all weights. This challenge is not limited to artificial networks but extends to biological networks, such as the brain, where the extent of distributed synaptic weight modification during learning remains unclear. Motivated by these insights, we theoretically investigate how different allocations of fixed mumber of learnable weights influence the capacity of neural networks. Using teacher-student setup, we introduce a benchmark to quantify the expressivity associated with each allocation. We establish conditions under which allocations have 'maximal' or 'minimal' expressive power in linear recurrent neural networks and linear multi-layer feedforward networks. For suboptimal allocations, we propose heuristic principles to estimate their expressivity. These principles extend to shallow ReLU nersorks as well. Finally, we validate our theoretical findings with empirical experiments. Our results emphasize the critical role of strategically distributing learnable weights across the network, showing that a more widespread allocation generally enhances the network's 's expressive power.
1 INTRODUCTION
A foundational principle in neuroscience posits that changes in synaptic weights drive learning and adaptive behaviors (Martin et al., 2000; Humeau and Choquet, 2019). This principle is mirrored in artificial neural networks (NNs); where modern algorithms adjust weights when training a network to perform task. However, while typically in NNs it is common for all weights to be adaptable, the scale of this process in the brain is unclear.
Recent evidence suggests that only a small subset of synaptic weights is modified when an animal learns a new task (Hayashi-Takee broad changes in neural activity as animals acquire new skills (Kim et al., 2023). Perturbing just a few neurons has been shown to significantly alter decision-making, perception, and memory-guided behaviors (Daie et al., 2021; Marshel et al., 2019; Robinson et al., 2020). These findings raise fundamental questions about the distributed nature of learnable weights in intelligent systems: To what extent are synaptic weight changes spread throughout the network, and what strategics should the learnable system use to allocate the subset of learnable weights?
et al., 2015) and that training a subset of neurons can induce
While most algorithms used in NNs do not constrain which weights trained, few research directions explore this question, primarily from a practical standpoint. For example, training only subset of the weights is used for pruning networks to make models more suitable for storage- constrained environments (Guo et al., 2021), to reduce computational costs (Thangarasa et al., 2023) and to reduce communication overheads in distributed systems (Sung al., 2021). Similarly, transfer learning often fine-tunes large models by adjusting only a fraction of the weights ("parameter

---

Published as a conference paper at TCLR 2025
allocating," " Wang al. (2024)). Such strategy is particularly useful for continual learning, helping to mitigate catastrophic forgetting (e.g,, Mallya and Lazebnik, 2018; Mallya et al., 2018; Serrà al., 2018; Wortsman al., 2020; Zaken al., 2022).
In both biological and artificial neural network research, similar questions arise regarding learning with only a subset of the available weights: If resources are constrained, what are the most effective strategies to allocate the learnable weights? Should learnable weights be confined to specific subsets of neurons, or distributed more broadly? And given an allocation strategy, how well can a network perform a task? Motivated by these questions, we theoretically study how learnable weights should be allocated within a network. More generally, we consider model in which task is learned under resource constraints- where only a fraction of the model's paramcters is adaptable, while others remain fixed. In this setling, we explore how the selection of learnable parameters affects overall performance.
1.1 OUR CONTRIBUTION
In this paper, we provide the first theoretical framework for analyzing the expressive power of various allocation strategies in NNs. Motivated by our goal of understanding how learnable weights should be organized in the brain, we apply our framework to explore the impact of allocating learnable weights on the expressivity of recurrent neural networks (RNNs). RNNs are particularly relevant to neuroscience as they serve as models to how neural systems maintain and process information over time (Hopfield, 1982; Elman, 1990; Barak, 2017; Qian et al., 2024). We focus on linear RNNs (LRNNs) due to their analytical tractability, grounded in the well-established literature on linear dynamical systems (e.g Heij et al. (2006)). Notably, we found that subset learning in LRNNs often produces non-trivial results, with insights that extend to feedforward archilectures and even shallow ReL.U networks. Our specific contributions are:
We formalize the problem of how to allocate learnable parameters in a model using student-teacher setup. We introduce a benchmark (Definition 2.3), which defines the match probability- the likelihood that a student, with a specific allocation of lcarnable paramcters, can replicate the tcacher's outputs. This mcasure of expressivity allows us to determine which allocations maximize the model's expressive power.
For LRNNs, prove several theorems that highlight the effects of different allocation strategics for learnable parameters in the encoder, decoder, and in the recurrent interactions (Thoorems 3.1, 3.2, 3.4 and 3.5). These thcorems identify conditions under which allocations can be maximal, leading to full expressivity, or minimal, resulting in zero expressive power. For cases where neither conditions are met, we propose heuristic principles to estimate the match probability. These results show a sharp transition between allocations with minimal expressivity to maximal expressivity.
We show that similar concepts from LRNNs apply for fully connected multi-layer linear feed-forward works (LFFN). We use these concepts to provide similar conditions that identify allocations that lead to large match probability.
We show that similar concepts can be used to analyze the performance of the possible allocation strategies in one-layer ReLU feed-forward network.
Our theoretical findings suggest that, as rule of thumb, allocations tend to become more optimal when distributing the learnable weights throughout the work. Specifically, distributing the same number of learnable weights over more neurons, such that there are fewer learnable weights per neuron, increases the network's expressive power. This principle pertained to LRNN, LFFN and shallow ReLU networks.
1.2 RELATED WORK
Expressive Power of Neural Networks. The expressive power of neural networks has been extensively studied. Cover (1965) established limits on the expressivity of a single perceptron,

---

Published as a conference paper at TCLR 2025
while Cybenko (1989) and Hornik et al. (1989) demonstrated that shallow NNs serve as universal approximators. More recent work by Raghu et al. (2017); Cohen et al. (2016); Montúfar et al. (2014), highlighted the greater expressive power of deep networks compared to shallow ones. Additionally, the expressivity of specific architectures were investigated, like convolutional neural networks (CNNs) (Cohen et al., 2016), RNNs (Siegelmann and Sontag, 1995; Khrulkov et al., 2018), and graph neural networks (GNNs) (Joshi et al., 2024). Collins et al. (2017) showed that different RNN architectures, such as GRU, LSTM, and UGRNN, exhibit similar expressivity, suggesting that insights into RNN expressivity could generalize to other recurrent models. In contrast. to these studies that focus on the expressivity of a fully learned model, here we will study how different allocations of a subset of parameters affect the model expressivity.
Theory on subset. learning and related techniques. Adaptation, technique similar to subset learning, widely used for fine-tuning neural networks. Despite its prevalence in practice, few studies have explored the expressive power of these methods. For instance, Englert and Lazic (2022) demonstrated that neural reprogramming (Elsayed et al., 2018), a strategy that alters only the input while keeping the pretrained network unchanged, can adapt random two-layer ReLU network to achiove near-perfect accuracy on a specific data model. Similarly, Giannou et al. (2023) examined the expressive power of fine-tuning normalization parameters, while Zeng and Lee (2024) recently
analyzed the expressive power of low-rank adaplation, a concept that is reminiscent of subset learning. Furthermore, the lottery ticket hypothesis (Frankle and Carbin, 2019; Malach et al., 2020) suggests that within a neural network, subnetworks exist that are capable of matching the test accuracy of the full model.
2 SETTINGS AND DEFINITIONS
We consider a model Mw with weights W E RP:
y = Mw
with x I2 and ye E Rd We study expressivity using a sandent-teacher framework (Figure 1) (Gardner and Derrida, 1989). Both models share the same architecture but have different weights, where the teacher's weights W are fixed and known. Our goal is find a student model that can exactly match the teacher, but with limited resources. The challenge is to match the labels produced by the teacher, which uses all p weights, while the student controls only r < p weights. The remaining weights are randomly drawn, but are not learned. We will show that different strategies for allocating the subset of r learnable weights in the student model determine its ability to match the teacher. When considering the m inputs, and Y E Rdxm corresponds to the mn outputs produced by the model.
samples, we denote the output Y Mw Mw(X), where X Raxm represents
Definition 2.1 An allocation A for a model Mw with weights W E RP is defined as the subset A c (1,,,..... which identifies the indices of the learnable weights.
Definition 2.2 For an allocation A of size =A|=r and constant weights W E R let {= i i p i $ A} be the complement of A, the realization set of A with respect to W is defined as:
{ (WERS ER' R' s.t. WIA = w]
R R.W
In other words, the realization set R AWW consists of all vectors W that match the constant weights W at the positions indexed by A. When the constant weights W are clear from the context, we denote the realization set simply as RAA- We use this notation to define our benchmark:
Definition 2.3 Let A be an allocation of size =r. For some weights distribution W, teacher distribution T and samples distribution X, we define the match probability of A to be:
MP(A, = Pr ME E RAW s.t. Mw(X) Mw (x)
where W is sampled from W, W is sampled from T and X from x

---

Published as a conference paper at TCLR 2025
Namely, the match probability for allocation is the probability of the student, when learning the weights allocated, to express the same m labels for the same m samples as the teacher. Match probability will be used as a benchmark for the expressive power of an allocation in a given model, ic., higher MP for an allocation leads to better expressive power of the model. Since our focus is on evaluating expressivity, rather than the optimization algorithm, we will focus on the existence of such W, without considering the optimization process of how to find it. In addition, although throughout the paper that the teacher and student share the same architecture, this assumplion is not strictly required (see Appendix F). Using samples to measure expressivity is inspired by Cover (1965), where expressivity is assessed by having labeled samples and examining the probability of expressing those labels.
assume
In this paper we investigale MP(A, As said, our goal is to use weights to make the student output the same Y, consisting of dm independent entries. In the models we consider in this paper, if dm, complete match is unattainable and MP = O. Since we only use MP 5) we short it to MP(A).
Throughout this paper, we will frequently encounter conditions where allocations that meet them result in (PA)) or MP((A) 0. For brevity, we define 'minimal allocation' as an allocation A such that MP(A) = O, and 'maximal allocation' as an allocation A such that P(A) = 1.
Assumptions. In this paper, we assume that the weight distribution W is normal with mean 0 and that there no correlations between the different weights. This assumption guarantees that matrices are invertible and diagonalizable. Additionally, we assume that the distributions X' and T such that any drawn m samples and any m output vectors of the teacher are linear independent, which means that any square matrix of inputs is invertible (see Appendix F.1 for possible relaxation of the assumptions). In few of the sections there are additional assumptions that are stated in the relevant section. Furthermore, in the linear models, we assume that the model is such that fully-learned teacher can express any linear function. For example, in feed-forward linear network, assume that there is no layer with size smaller than the output.
Match Probability (MP) Exprcssive (*() ? ((AW)).) "pwwer of allocation A, setup. The match probability (MP) esti- mates the expressive power of a student with an allocation A; of its lcarnable weights by measuring its ability to match learned weights the teacher. fixed weights
Figure 1: Schema of the student-teacher
Teacher
(*))
inputx
M
Student
(WW))
(W).
2.1 WARM UP: LINEAR ESTIMATOR MODEL
To better understand the settings and the goal, start with simple example of a linear estimator, = Wx, with W E Rdxq, Considering m samples we write:
Y = Mw = WX
with X E Raxm, Y E ddd. We thus ask how to allocate the r learnable weights in W such that the student matches the teacher successfully all samples. For realization of W*, X and W, seek for W E A; W such that:
WX W*X
Denote We and Wi as the ith row the matrices, r2 the number learnable weights in Wo, and W; as the subset of W; corresponding to these r; weights. Additionally, let X represent the corresponding

---

Published as a conference paper at TCLR 2025
rows of the input samples, X, W, denote the remaining (fixed) weights of W;, and X represent the remaining rows of X. We then have:
W 1
(2.1)
where all the student and teacher weights on the r.h.s of Equation (2.1) are constants. As E R if ra m we will have more equations than variables in Equation (2.1) and there will be solution to the set of these linear equations. In contrast, if r. = m there is always a solution:
W; -w:x-Wx8)a
(2.2)
As ri is the number of learnable weights in the ith row of W, we have r - Ti. This means that an allocation must have an equal division between the rows of W, each row consisting of exactly à learnable weights. Based on Equation (2.2) we can allocate the learnable weights to create W RA such that W X = WX. Therefore, in that case MP(A) = 1, namely maximal allocation, and otherwise MP(A) = 0, namely minimal allocation.
Notice the dichotomy here there an allocation that perfectly matches the teacher, but its not robust. A slight change in the allocation, such as moving single learnable weight from one row to another, will create an allocation that will never match the teacher (a minimal allocation). This concept will return later on.
3 LINEAR RNN MODEL
We begin by applying our framework to study allocations of learnable weights in RNNs. We focus RNNs both because of their relevance to modeling neural circuits, as well as the non-trivial results arising from allocating the learnable weights in their recurrent weights.
Consider linear recurrent neural network:
ltt Wh4-1 + Ba,
(3.1)
y/ Dh
(3.2)
with the hidden state h2 E R", the initial state hyp = 0, a step input H, E RR, and with t = l...T. The imput to the network is driven through the encoder matrix B E Rabb and W Raxx is the recurrent connections. The hidden state is read out through the decoder D Rdxn such that the network's output is ye E Rd. We consider yr+1 the output of the network, and denote y = yr+1- The RNN is thus a function F: Rbb + Rd We assume n >> b, d. Additionally, when referring to m inputs, we denote X, 126m where each column represents one of the m inputs at step t across all samples.
First, due to key attribute of LRNN, assume that Tb & and Td (see Theorem B.1 for details).
Second, solving the recursion gives:
T Y Y= W T- 2+1 BX,
(3.3)
1=1
This implies that for the student to match the teacher, it must solve a system of dm = r polynomials (since Y E Rdxm) with r variables. Notably, the high polynomial degree arises only when allocating weights in W. As a result, we show that allocating the subset of learnable synapses to the encoder, decoder, or the recurrent interactions lead to very different allocation strategies.
3.1 LEARNING THE DECODER
We first consider allocations that learn the decoder, D. Denote X'= WT-++1BX, get that
Y = DX'. Learning the decoder is, therefore, analogous to that of a linear estimator. The conditions for the allocation to be optimal are the same those described in Section 2.1. We formalize that as theorem:

---

Published as conference paper at TCLR 2025
Theorem 3.1 For any allocation A learning the decoder D RRdxn, if every row has evactly m learnable weights the allocation is mazimal, else it is minimal.
3.2 LEARNING THE ENCODER
We continue with considering allocations that learn the encoder, B. In this section assume the sample distribution element-wiss i.i.d. Similar to the decoder, this scenario reduccs to a system of linear equations, where the matrix is regular for some allocations and singular for others, leading to match probability of either 1 or for each allocation. However, unlike the decoder, constructing and analyzing the matrix is more involved, B is embedded within the dynamics (see Equation (3.3)) rather than appearing at the end.
Theorem 3.2 Any allocation A leorning the encoder B E Raxh that follows both of the following conditions is marimal:
No row of has more than T'm learnable weights
2. No columns of B has more than Td. learnable weights
Every other allocation is minimal.
Notice that as the number of learnable weights are constant, allocating too many learnable weights in a row (column) leads to insufficient learnable weights in the other rows (columns). Furthermore, as in for the decoder, each allocation exhibits dichotomy being either minimal or maximal with maximal expressivity achieved when the allocation is more distributed.
3.3 LEARNING THE RECURRENT CONNECTIONS
Although the proofs for allocating the learnable subset the decoder or encoder differed, the underlying rationale was similar. In both cases, we transformed the problem into a system of linear equations, where maximality is achieved when the matrix is invertible and minimality when it is not. However, when the allocation is applied to learning the recurrent connections, as shown in Equation (3.3), the problem shifts solving a system of polynomials of degree T, making it more complex than the linear cases.
We illustrate this phenomenon in Appendix B.1.1 with a simple example network, where T' = 2. In this scenario. Equation (3.3) simplifies into two equations, one linear and one quadratic, which can be combined into single quadratic equation, represented as ax + bz + == O. It is well-known that this type of equation is solvable if and only if 6² 2 4ac. We demonstrate that for different allocations, distinct expressions for b, and e arise, leading to varying match probabilities. Moreover, for certain alno,ations, we find that O, which implies the equation is linear, and the match probability is This observation raises the question of whether this phenomenon, where maximal allocations exist even though the equations are non-linear, also occurs in larger models and how to identify such allocations.
To gain insights under which conditions allocations become maximal, we simplify the high-degree equations. The following lemma reduces the problem to a system of linear and quadratic equations: Lemma 3.3 Given samples X and labels Y created by the teacher, the student matches them using allocation A if and only if the following set of equations is solvable:
WgD(F) =
(3.4)
DFX =
(3.5)
with W E RA,, F E RaxTb and 9B is a linear operator that depends on B, formally defined in the appendix. Note that these equations essentially Equation (3.3) (sce appendix), where Equation (3.4) is just step of the dynamics. The key insight is that by treating the dynamic steps

---

Published as a conference paper at TCLR 2025
themselves as variables, we alter the problem's structure, making it more tractable. Introducing the nI'b new auxiliary variables, denoted as F, in addition to the variables in W, reduces the polynomial degree of T in Equation (3.3) a system of linear and quadratic equations in W and F.
Generally, the equations in Equation (3.4) quadratic, while those in Equation (3.5) are linear. However, if a full row in W has no learnable weights, the Tb equations corresponding to that row become linear, involving only the variables from F. As shown in Appendix B.1, similar observation applies to columns. This means that if an allocation uses fewer rows or columns for its learnable weights, the resulting system will contain more linear equations and fewer quadratic ones.
One might ask: How does altering the number of rows columns and thereby the number of quadratic equations affect overall solvability? First, if an allocation uses too few rows or columns, the match probability will be zero. This occurs because when there are too many equations involving only the variables from F, we end up with a situation where there are more variables than equations, resulting in " "waste" of variables. This idca is formalized in the following thcorem:
Theorem 3.4 Any allocation A learning the recurrent connections W E R=*= that follows at least one of the following conditions is minimal:
1. A row in W has more than Tb learnable weights
2. A column in W has more than Td learnable weights
Second, when an allocation utilizes a certain number of rows or columns, the problem can simplify into a linear system, which will be solvable with probability 1. In this case, the allocation becomes maximal. This concept is formalized in the following theorem:
Theorem 3.5 Any allocation A learning the recurrent connections W E guxa, that follows one of the following conditions is marimal:
1. Each row has Tb or 0 learnable weights
2. Each column has Td or learnable weights
Namely, allocation that uniformly distribute the learnable weights in TE rows or fa columns is always maximal. Notice that this is the least number of rows and columns that allocation should use, as less rows or columns can't 't satisfy the conditions in Theorem 3.4. Recall that we assumed Tb and Td to be smaller than n, ensuring that the number of learnable weights does not exceed the length of any row or column.
In other cases, we still need to solve a system of quadratic equations to determine whether the st udent matches the teacher. The problem of determining the number of solutions for set of polynomial equations is well studied in mathematics. For example, Smale's 17th problem (Smale, 1998) addresses the algorithmic challenges of root-finding for complex polynomials, though much less is known for polynomials with real cocfficients. Recently, Subag (2024) investigated the number of solutions for system of n polynomials in n variables with Gaussian coefficients and showed that the probability of finding at least one solution increases with the number of polynomials (and variables), eventually converging to 1. Therefore, we conjectured that as an allocation ion uses more rows thus introducing more quadratic equations -thh match probability will also increase. Moreover, increasing the model size increases the number of quadratic equations, we also anticipate that for large networks the match probability for all allocations will approach 1.
To test this conjecture, we used numerical simulations to estimate the match probability while restricting the allocation of learning synapses to a subset of the rows. Figure 2a shows that across different network sizes the match probability increases as more rows utilized in the allocation. Additionally, for the same percentage of rows, the match probability increases with the network size. This is consistent with the intuition that increasing the total number of polynomials (by increasing the network size) increases the probability to find a solution to the set of polynomials. Figure 2b depicts the match probability for models with constant r/n, which signifies the sharp transition from minimal (zero expressivity) to maximal expressivity at the To th row (see Theorems 3.4 and 3.5).

---

Published as conference paper at TCLR 2025
a
WE H recumentt weights
Linear recurrent neural nelwork
maximal allocations
Expressive power (MP)
Expressive powerr (MP)
minimal allocations
2.0
n=8 n=
3.6
n=1
BE encoder
De decoder
mm
Inarnad weights
376
0.4
0.6
0.8
Fraction of learned rows
Theoretical transition point
Frection learned rowe
Figure 2: a. Estimation of MP for allocations in the recurrent weights of LRNN with d = 4 for different sizes of the hidden state, n. Note that MP increases with n. Same as (a), but with fixed d/n = 1. In this case, Tь 3 which means that allocations using of the rows for every n follow Theorem 3.5, and are thus maximal. Allocations using less rows are minimal due Theorem 3.4. Note that MP approaches 1 as increases. All experiments ran with second order optimization methods. See Appendix for full details.
4 LINEAR MULTI-LAYER FEED-FORWARD MODEL
The findings for linear RNNs provide insights into the expressive power of subset learning in lincar multi-layer foedforward networks (LFFNs). In these models, the input is multiplied by several matrices. Formally:
== WWW W
where Wi E R"4xm-1, 2 < <. L 1, and WL E Rdxme-1, W1 E Raxx, Additionally, we require n 2 d.d for every 1 15 1 L. This ensures that the network dimension never decreases below q and d.
As the last layer acts as the decoder, has indeed the same altributes as learning the decoder in the LRNN model as we saw Section 3.1. Allocations of learnable synapses in one of the intermediate hidden layers, or the encoding layer, is reminiscent of allocations in the encoder of the LRNNs. This formalized in the next theorem:
Theorem 4.1 For any allocation A learning on intermediale or encoder layer W₁ E Ruixn is marimal if and only if il. follows of the following:
1. There is no rows that has more than m learnable weights
2. There is no columns that has more than d learnable weighls
Otherwise, the allocation is minimal.
Allocating learnable synapses across multiple matrices is analogous to learning the recurrent con- nections in LRNNs. This type of allocation results in polynomials with variables, where the degree of the polynomials corresponds to the number of learnable layers. Similarly, as we showed for allocations of the recurrent. connections, certain allocations can reduce the number of polynomials involved.
Using the same framework and arguments as Lemma 3.3, one can show that the student matches the teacher iff the following equations solvable:
W = Fj
(4.1)
WiF- Fi 2515
(4.2)
W.FL-1IW
(4.3)

---

Published as conference paper at TCLR 2025
a
Linear multi-layer feedforward
ReLU feedforward
Expressive power (MP) C
MNIST data
Expressive power (MP)
Expressive power (MP)
n=0
0.9
0.15
n=10
n=12
p=14
0.8
0.8
p+6
0.4
0.7
6=10
0.05
6=12
0
leamned weights fixe weights
0 0.2
0.4 0.6 0.8
(ReLU units)
0.6 0.8
20 Number of learned
Fraction of learned rows
Fraction of learned rows
Figure 3: Estimation of MP for FFNs. MP increases when distributing the weights. a. Estimation of MP for allocations in 3-layer linear FFNs network, for different sizes of the intermediate layer denoted as b. Allocation for shallow ReLU network for different sizes of the hidden layer size. All experiments ran with second order optimization methods. c. Allocations in a shallow ReLU network with n=1000 on structured data (MNIST). The MP when the allocation uses more then 40 rows was constant 1. See Appendix E for full details.
with Wi IR 2 S
Wz E [_d W1 E R F R , 1--S--L- We introduce many variables, denoted as F. However, if allocation is restricted to only small subset of rows, many the resulting equations become linear. By solving these lincar equations, reduce the number of polynomials to fewer than r.
As mentioned earlier, expect that the probability of a set of polynomials having solution to increase as the number of polynomials increases. Therefore, we expect that allocations restricted to small subset of rows across different layers will have a lower match probability. This expectation is confirmed empirically, as shown in Figure 3a.
Therefore, in FFNs, similar to learning the recurrent weights in LRNNs, the multiplication of multiple matrices (due to the layers) leads to non-linear equations, which motivates distributing the learnable weights to increase the match probability.
5 SHALLOW RELU MODEL
We saw that generally, it is better to distribute the learnable weights throughout the network (Figures 2 and 3a). We conclude with an intuition, backed by empirical evidence, that this also true in a shallow network of ReLU units.
Consider a 2-layer feedforward ReLU network:
Yi = W2 ((W1z))
with W1 E Rnxq, W2 Rdxa and where 2; and y/s the i'th sample and label respectively for < i m. We consider allocations learning W1. For the linear model, as long as some conditions hold (Theorem 4.1), all allocations are maximal. We now want. examine if the ReLU changes these results and whether it adds another incentive for distributing the learnable weights of an allocation.
For a given allocation A, let k S n be the number of rows that has learnable weights. Assume w.l.o.g that they are the upper rows, and denote Wil to be the first l rows and W? to be the other n Denote Wi and W? to be the corresponding columns in Ws. Thus we can write:
W22 ((W12.)) y1 W2 @WWfar))
Notice that the r.h.s is constant. For d(x) being the ReLU function, this equation be rewritten as:
W W.P.W a = - W3 (WPP,,)
(5.1)
Here, P; P Reck is diagonal matrix with 1s rows where Wi 0 and Os where it is negative, namely (2P: 1) > 0. For a fixed P m we get a linear equation in the r learning

---

Published as a conference paper at TCLR 2025
weights of WT- Thus, for the allocation to match, two conditions must hold: 1) the linear equation must be solvable, and 2) the solution of W1 must satisfy (2P; - W) > 0 for every 24-
The first observation is that if the allocation does not satisfy the conditions in Theorem 4.1, the linear equations will be vnbolv Another key point is that we need to " "guess" " P, which could, in theory, take one of possible configurations, solve for W1, and verify if it satisfies the inequalities. However, the actual number of feasible configurations is lower Lemmas D.3 and D.4 demonstrate that some configurations are inherently invalid due to the linear equations being unsolvable, Importantly, the fraction of feasible configurations increases as the allocation becomes more distributed Lemma D.3 shows that the number of valid configurations for P decreases when smaller values of k are used, and Lemma D.4 reveals that allocations with rows containing many Icarnable weights similarly face reduction in the number of possible configurations for P.
This suggests that allocations using more rows are more likely to increase the match probability. As shown in Figure 3b, the empirical trend aligns with our intuition. These results suggest that the ReLU non-lincarity introduces an added benefit for allocations that distribute their learnable weights more broadly across the network.
6 DISCUSSION
In this paper, we explored different strategies for learning under resource constraints, focusing on how to allocate a subset of learnable model weights from a standpoint of expressivity. Our main focus was linear RNNs and FFNs. Linear models have been fundamental across fields such as linear circuits and control thcory, despite being oversimplificatins of real-world systems. Their strength lies in simplifying complex idcas, providing a necessary foundation for understanding more intricate nonlinear behaviors (Saxe et al., 2014). Although the linearity of these models, we showed that the problem of how to allocate the resources when examining subset learning becomes highly non-linear, with linearity emerging only in specific cases (Theorems 3.4 and 3.5).
We conjectured that the number of non-lincar equations arising from subset learning in linear models improves model expressivity, and that distributing the lcarnable weights incrcases the number of non-linear equations, thus generally improves the expressive power of the model. This conjecture was backed-up with numerical simulations (Figures and 3). Interestingly, and perhaps unexpectedly, our results suggests that in large models, allocations can consistently achieve maximum expressivity.
While our work provides thcoretical insights into the impact of allocation strategics on expressivity, several limitations should be acknowledged. First, our paper should be viewed as first step in exploring how allocation strategies affect the network performance. As such, our analysis primarily focuses on expressivity, which does not encompass other important aspects of network performance, such as generalization or optimization, and these should be explored in future work. Additionally, our theoretical framework relies on assumptions like i.i.d. inputs and linear independence of certain matrices, which may not fully capture the complexities of practical neural networks. Another limitation is that many results were derived for simplified architectures, necessary to develop insights beyond numerical investigations. We took step toward generalizing the results by extending our framework to study expressivity in a non-linear shallow ReLU model, where we found that non- linearity itself motivates distributed allocations. Future work should extend these results numerically and theoretically to more complex architectures and structured datasets.
Despite these limitations, our paper presents a general framework for studying expressivity in neural networks. Match probability (MP) is a versatile and applicable measurement that captures the reduction in expressivity due to specific allocation strategies. While we use a student-teacher framework for clarity, our analysis does not rely on the teacher model itself, and MP can be naturally defined for general data distribution (sce Appendix F). In fact, we tested our approach on structured, real-world data by estimating the MP of a shallow ReLU network on the MNIST dataset (Figure 3c). These results suggest that our insights regarding distributing the learnable weights throughout the network may pertain practical applications.

---

Published as conference paper at TCLR 2025
7 ACKNOWLEDGEMENTS
We thank Oren Yakir, Lior Bary-Soroker and Roi Livni for their imput and constructive feedback. We thank Tomer Koren for his imput, constructive feedback and carefully reading the manuscript. This work was supported by research grants from the Israel Science Foundation (2097/24, /24, 2994/24)
REFERENCES
William E Allen, Michael Z Chen, Nandini Pichamoorthy, Rebecca H Tien, Marius Pachitariu, Liqun Luo, and Karl Deisseroth. Thirst regulates motivated behavior through modulation of brainwide neural population dynamics. Science, (64(6437))eaav3932) 2019.
Jean-Mare Azas and Mario Wschebor. Level sets and extrema of random processes and fields. Level Sets and Extrema of Random Processes and Fields, 01 2009. doi: 11.02/997904704344222
Omri Barak. Recurrent neural networks as versatile tools neuroscience research. Current opinion in neurobiology, 46:1 6, 2017.
Tsai-Wen Chen, Nuo Li, Kayvon Daie, and Karel Svoboda. map of anticipatory activity in mouse motor corlex. Newron, 94(4):866 879, 2017.
Nadav Cohen, Or Sharir, and Amnon Shashua. On the expressive power of deep learning: tensor analysis, 2016. URL
05009.
Jasmine Collins, Jascha Sohl-Dickstein, and David Sussillo. Capacity and trainability in recurrent neural networks, 2017. URL http://///xxvvv.oraa/sees/
Thomas M Cover. Geometrical and statistical propertics of systems of lincar incqualitics with applications in pattern recognition. IEEE transactions on electronic computers, (3):326-334, 1965.
Goorge V. Cybenko. Approximation by superpositions sigmoidal function. Mathematics of Control, Signals and Systems, 2:303-314, 1989. URL https: www.nticscoolleatt.....e http::///app..eaaatccccccoooorr Prrg/CorusID; 3958369.
Kayvon Daic, Karel Svoboda, and Shaul Druckmann. Targeted photostimulation uncovers circuit motifs supporting short-term memory. Nature neuroscience, 24(2) :200-2200 265, 2021.
Jeffrey L Elman. Finding structure in time. Cognitive science, 14(2):179 211, 1990.
Gamaleldin F. Elsayed, lan Goodfellow, and Jascha Sohl-Dickstein. Adversarial reprogramming of 11146.
neural networks, 2018. URL https://arxiv.orrt
Matthias Englert and Ranko Lazic. Adversarial reprogramming revisited, 2022. URL https:
//arxiv. org. abs//22//22226 03466.
Arseny Finkelstein, Kayvon Daie, Marton Rozsa, Ran Darshan, and Karel Svoboda. Connectivity underlying motor cortex activity during naturalistic goal-directed behavior. bioRwiv, pages 2023 11, 2023.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks, 2019. URL https://arxiv. http:////xxvvoor/aabbbee www.oorg///////eeeeeee 03635.
E Gardner and B Derrida. Three unfinished works on the optimal storage capacity of networks. Journal of Physics A: Mathematical and General, 22(12):1983, jun 1989. doi: (0008/0305-4470/ URL stttp://das dx. doi. org/ 10.
Angeliki Giannou, Shashank Rajput, and Dimitris Papailiopoulos. The expressive power of tuning only the normalization layers, 2023. URL
wwwpeiiii..or/eee. http//230207937

---

Published as a conference paper at TCLR 2025
Demi Guo, Alexander M. Rush, and Yoon Kim. Parameter--eficient transfer learning with diff pruning, 2021. URL https: htapsv//arxivoorrg aaaaaba/2222 07463.
Akiko Hayashi- Takagi, Sho Yagishita, Mayumi Nakamura, Fukutoshi Shirai, Yi I Wu, Amanda L Loshbaugh, Brian Kuhlman, Klaus M Hahn, and Haruo Kasai. Labelling and optical erasure of synaptic memory traces in the motor cortex. Nature, 525(7569):333 (1175699)3333335 2015.
C. Heij, A.C.M. Ran, and F. van Schagen. Introduction to Mathematical Systems Theory: Linear Systems, Idenlification and Control. Birkhäuser Basel, 2006. ISBN 9783764375492. URL https: //books. //books.google.... co. ii/bolkss d--ND___p_EEEeC..
John J Hopfield. Neural networks and physical systems with emergent collective computational abilities. Proceedings of the national academy of sciences, 79(5):2554 2558, 1982.
Roger A. Horn and Charles R. Johnson. Topics in Matria Analysis. Cambridge University Press, 1991.
Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks are universal approximators. Newral Networks, 2(5):359 366, 1989. ISSN 0893-6080. doi: https://dh /doi. URL
(00000/0000000000000)))000000000 pi1/089360808990020..
Yann Humeau and Daniel Choquet. The next generation of approaches to investigate the link between synaptic plasticity and learning. Nature neuroscience, 22((0):15366 1543, 2019.
Peter C Humphreys, Kayvon Daie, Karel Svoboda, Matthow Botvinick, and Timothy P Lillicrap. Bci learning phenomena can be explained by gradient- based optimization. bioRriv, pages 2022-12, 2022.
Chaitanya K. Joshi, Cristian Bodnar, Simon V. Mathis, Taco Cohen, and Pietro Liò. On the expressive power of geometric graph neural networks, 2024. URL https://arxix:
wrg//bs//3011 http:://aaxxivrorr//aa////333 09308.
Valentin Khrulkov, Alexander Novikov, and Ivan Oseledets. Expressive power of recurrent neural networks, 2018. URL https://arxiie https://arxiv.org/bbbll wttp/rggg//b/aaaaa//////a 00811.
Christopher M. Kim, Arseny Finkelstein, Carson C. Chow, Karel Svoboda, and Ran Darshan. Distributing task-related neural activity across cortical network through task-independent connections. Nature Communications, 14(1):2851, May 2023. ISSN 2041-1723. doi: 10.1038/ 541467-003-335599-y URL https://doi. org/10. 1110:/001110//1144-00------33330
Diederík P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization, 2017. URL
attps://arxiv. http:///aaxiivoo//a///////////// wwtp/o//////i///eo 1980.
Eran Malach, Gilad Yehudai, Shai Shalev-Shwarzz, and Ohad Shamir. Proving the lottery ticket hypothesis: Pruning all you need, 2020. URL attps://arxiie /wwxiv. org/abs/2002. 00585.
Arun Mallya and Svetlana Lazebnik. Packnet: Adding multiple tasks to a single network by itcrative pruning, 2018. URL https: / //arxiv...iiv///a// wwepxivvor//aae arg/abs//1ee abs/1711.05765
Arun Mallya, Dillon Davis, and Svetlana Lazebnik. Piggyback: Adapting a single network to multiple tasks by learning mask weights, 2018. URL https://arxiv erg/abs/1804 http//8811.6665 06519.
James Marshel, Yoon Seok Kim, Timothy Machado, Sean Quirin, Brandon Benson, Jonathan Kadmon, Cephra Raja, Adelaida Chibukhchyan, Charu Ramakrishnan, Masatoshi Inoue, et al. Cortical layer-speciti specific critical dynamics triggering perception. Science, (85(6443))eeaww522)) 2019.
Stephen Martin, Paul Grimwood, and Richard GM Morris. Synaptic plasticity and memory: an evaluation of the hypothesis. Annual review of neuroscience, (8(1):649-711 2000.
Guido Montúfar, Razvan Pascanu, Kyunghyun Cho, and Yoshua Bengio. On the number of linear regions of deep neural networks, 2014. URL www.wi.ww.aaaaaaa.aaooa absp///ba1442.....

---

Published as a conference paper at TCLR 2025
William Qian, Jacob A Zavatone-Veii Benjamin S Ruben, and Cengiz Pehlevan. Partial observation can induce mechanistic mismatches in data-constrained models of neural dynamics. bioltriv, pages 2024 05, 2024.
Maithra Raghu, Ben Poole, Jon Kleinberg, Surya Ganguli, and Jascha Sohl-Dickstein. On the expressive power of deep neural networks, 2017. URL http://///aiio.o/aa///////s///// https//666.0033300 05336.
Nick TM Robinson, Lucie AL Descamps, Lloyd Russell, Moritz O Buchholz, Brendan Bickuell, Georgy K Antonov, Joanna YN Lau, Rebecca Nutbrown, Christoph Schmidt-Hieber, and Michael Häusser. Targeted activation of hippocampal place cells drives memory- cenory-guided spatial behavior. Cell, 183(6):1586-1555) 2020.
Luca Saglictti, Stefano Mannelli, and Andrew Saxe. An analytical theory of curriculum learning in teacher-student networks. Advances in Neural Information Processing Systems, 35:21113 21127, 2022.
Andrew M. Saxe, James L. McClelland, and Surya Ganguli. Exact solutions to the nonlinear dynamics of learning in deep linear neural networks, 2014. URL https://arxiv.oo
Joan Serrà, Didac Surís, Marius Miron, and Alexandros Karatzoglou. Overcoming catastrophic lorgetting with hard attention to the task, 2018. URL
01423.
H.T. Siegelmann and E.D. Sontag. On the computational power of neural nets. Journal of Computer and System Sciences, 50(1):132 150, 1995. ISSN 0022-0000. doi: https://ttoi.org/100000000 1013. URL https://www wwtp::ssceeeeeeecccc.c..... www.sciincc/cc/ccccccccccccccccc http///ciene//erriireeeee/////// httpi/////arrceep//////0000000/0
1995.
Steve Smale. Mathematical problems for the next century. The Mathematical Intelligencer, 20()) 7-15, Mar 1998. ISSN 0343-6993. doi: (0.1007/BF030252)) URL / BF03025291.
Nicholas A Steinmetz, Peter Zatka- Haas, Matteo Carandini, and Kenneth D Harris. Distributed coding of choice, action and engagement across the mouse brain. Nature, 376(778)) 270,, 2019.
Eliran Subag. Concentration for the zero set of large random polynomial systems, 2024. URL
https://arxiv htttpp::/aarxiv.r//bbb///////// wtgg/bs////b////o/ee///////////e 11924.
Yi-Lin Sung, Varun Nair, and Colin Raffel. Training neural networks with fixed sparse masks, 2021.
URL https: wttpaaawwi....aaa////aaa..
Vithursan Thangarasa, Abhay Gupta, William Marshall, Tianda Li, Kevin Leong, Dennis DeCoste, Sean Lie, and Shreyas Saxena. Spdf: sparse pre-training and dense fine-tuning for large language models. In Proceedings of the Ninthh Conference on Uncertainly in Artificial Intelligence, UAI '23. JMLR.org, 2023.
Shinichiro Tsutsumi and Akiko Sayashi-Takaaee Optical interrogation of multi-scale neuronal plasticity underlying behavioral lcarning. Current Opinion in Neurobiology, 67:8-15, 2021.
Liyuan Wang, Xingxing Zhang, Hang Su, and Jun Zhu. A comprehensive survey of continual learning: Theory, method and application, 2024. URL
Mitchell Wortsman, Vivek Ramanujan, Rosanne Liu, Aniruddha Kembhavi, Mohammad Rastegari, Jason Yosinski, and Ali Farhadi. Supermasks in superposition, 2020. URL https://arxiv..
abs/2006. 14769.
Zhewei Yao, Amir Gholami, Sheng Shen, Kurt Keutzer, and Michael W Mahoney. Adahessian: An adaptive second order optimizer for machine learning. AAAI (Accepted), 2021.
Elad Ben Zaken, Shauli Ravfogel, and Yoav Goldberg. Bitfit: Simple efffmeter-efficient fine-tuning for transformer-basee masked language-model. models, 2022. URL
10199.
Yuchen Zeng and Kangwook Lec. The expressive power of low-rank adaptation, 2024. URL attps://arxiss wtlaaaaii...ooaaaaaaaaaaaaaaaaaa argg/bb//3110.7555

---

Published as conference paper at TCLR 2025
Appendix
A Linear Algebra Preliminaries: Kronecker Product and Vectorization
14
B Linear RNN
15
B.1 Learning the recurrent connections
16
B.2 Learning the encoder
C Linear feed-forward
23
D Shallow ReLU
24
E Experiments
25
E.1 Methods
25
E.2 Environment
26
E.3 Variance in the experiments
27
F Supplementary Discussion
27
F.1
Assumptions Relaxation
28
A LINEAR ALGEBRA PRELIMNAARIES: KRONECKER PRODUCT AND VECTORIZATION
We use In as the identity matrix of size x When the size is clear from context we write I. Definition A.1 The Kronecker product of two matrices A and B is denoted by A & B and is defined
as follows:
Let be an x n matria and B be a p matria:
a11
012
dim
bii
b12
big
Q21
022
02n
bu1
byz
bag
A
B
aml
am2
amn/
mxx
bp1
bp2
bpal
pxq
The Kronecker product A ② B is an (mp) (nq) matria defined by:
B1i B
B
ain
a21 B
B
B
a
B
A & =
0m1 B
Om B
amn B

---

Published as conference paper at TCLR 2025
Definition A.2 Let A be matrir. The vectorization of A, denoted by vec(A), is the mn column vector obtained by stacking the columns of A on top of one another. For ezample:
Q11
021
0ml
012
Q11
012
Ain
022
021
022
d2n
A
vec ())
0m2
0m1
am2
amn
d1n
amn
We will use two well known attributes of Kronecker product (sce Horn and Johnson (1991)):
Lemma A.3 For every A E Rdixdd, B E R.d2 xds C Rddaxd;
rec(ABC) = (CT ? B)
Lemma A.4 For every E Rdi xd2 B E xdd;:d1;
rank(A A 2 B) rank(A)) A)rank(B))
B LINEAR RNN
We start with key feature of LRNNs: although the total number of weights is p (d + b n)n, only p= (d + b)n of these are necessary to represent the network's output. This result is formalized in the following thcorem:
Theorem B.1 For every T, the output of the network can be expressed using n(d + b) variables.
Proof: From Equation (3.3) we get that if the value of DWT-1-CB for two networks is the same for all T, their output will always be equal.
The measure of real matrices that are not diagonalizable over the complex equals 0, the prob- ability for a random matrix with a continuous probability distribution to be non-diagonalizable vanishes. Since W is such matrix, we can safely assume it diagonizable. Let UXU-1 be the spectral decomposition of W.
For every diagonal matrix S, we can write:
W
Now fix such that D,SS= T, where T' is a vector of all I's and D the first row of D. Denote V = US, we have W = VXV-1 such that D,V Y. In other words, we can always pick the eigenvectors V of W to be such that D I.
Notice that DWT+I- = DV Thus, two networks that will have the same DV, V-1 B and À will always output the same system. There are bn variables in V-1B. and n variables in A. DV has dn entrics but we know that the first row is i so it has only dn Thus, these n(d + b) variables express the output of the network for every T.

---

Published as conference paper at TCLR 2025
From solving the recursion it becomes clear that LRNN linear transformation, receiving Tb inputs and producing d outputs, effectively acting as a Tb x d matrix. From the proof, we observed that this function (expressed DW for each 1 & T) can be represented using n(d + b) variables. This implies that the the function that the network represents becomes degenerate if Tbd > n(d ( b). To prevent degeneration, we require T S m(d+b) Given the assumption that > b, d, this simplifies to approximately Tb < and T'd S n.
B.1 LEARNING THE RECURRENT CONNECTIONS
In this section, we provide proofs for Theorem 3.4 and Theorem 3.5, and demonstrate their application through small network example.
Definition B.2 (Shift Operator) Given n1, n2, ny N, B E Rm1xm and F R2ix" Denote
F F= F1 F2
Fm-1 Fm such that for every Sis na, F3 E TERR Xn2, Then:
ga (F)) = F2 Fs
Fm-1
Fm (B)
Lemma B.3 Given samples X E Tbxm and labels Y E gdxmm created by the teacher, the student can express them using allocation A if and only if the following set of equations is solvable:
W FF) =
(B.1)
DFX =
(B.2)
W E RA F RRx22
We will start by showing that if the system is solvable, then the student can express the given labels. Assume the equations solvable using W E RA and F RaxTb Fy Raxb Notice that W and f are assumed to be solutions to the above equations and are unrelated to the teacher.
Proof:
From the definition of the operator JB: Equation (B.1) becomes:
W. = F
2515T
W
Solving the recursion get F2 (W+)T-++1B
Since FX = Er F,X,, Equation (B.2) is equivalent to:
T
Y= F DY (W*)T-(+IXX.
Since W valid realization of and outputs the correct labels, the student can match the teacher.
Now, on the other hand, assume that the student can express Y. We choose W to be the recurrent connections of that student, which implics Y = DD WT-++I By selecting F, WT is easy to verify that the equations hold.
Lemma B.4 For any allocation A, if [A] < dm then MP(A) =0
match with allocation A if set of dm polynomials is solvable with |A| variables. Thus, if the student can match with A,, a set of dm polynomials is solvable with less than dm variables. This is generally solvable w.p 0, for example from Theorem 6.8 of Azas and Wschebor (2009) this is true for polynomials with Gaussian coefficients. Therefore, the match probability of A is
Proof:
From Equation (3.3), the student
Thcorem B.5 (First part of Thcorem 3.4) Given allocation A, if there is with more than Tb learnable weights the allocation is minimal.

---

Published as a conference paper at TCLR 2025
We will prove that if the student can match with an allocation with more than Tb learnable weights in some row, it can match with an allocation with less than dm weights, which means from Lemma B.4 that the match probability is 0.
Proof:
dm that has ri > Tb learnable weights in the ith row and solves Lemma B.3. Notice that the rows of W, in Lemma B.3 participate in exactly Tb equations in Equation (B.1) the ith row only need to suffice:
Given an allocation A with A
(ig =F)==FF
Where F3 is the ith row of F.
Denote the solution as = and W = W Consider another allocation, A2, in which we replace Tb of the learnable weights of A in the i'th row with constants, which means that |Agl < dm. Define W as the learnable part of Wa, gi (F*) as the corresponding columns in 9B(F"), W as the remaining part of W,, and 9B (F*) the remaining part of (F(F"). Then:
(F + (F = Fi
F (FF
W; (F - (.T (TB (F"))
Which means that there is solution to Lemma B.3 with A2. In other words, every time Lemma B.3 is solvable with A, it is also solvable with Ag- Recall that [A2l < dm, therefore, from Lemma B.4, the match probability of A2 is 0, which means that the match probability of A is also O.
Theorem B.6 (First part of Theorem 3.5) Given an allocation A, if every row that has learn- able weights has eractly Tb learnable weights in it, the allocation is marimal.
Proof: The rank of the linear equation in Equation (B.2) is dm, which follows immediately from Lemma A.3 and Lemma A.4 (recall that m I Tb and < n)).
With r learnable weights in the model, the allocation consists of exactly Tb = dm rows, cach containing Tb learnable weights, while the remaining rows are fully constant. Without loss of generalily, assume that these constant rows are positioned at the bottom of W. We can express the first. equation of Lemma B.3 as:
WTOP 9B(F) FrOP W WBOT (9 = FBOT
(B.3)
(B.4)
Where the TOP rows are the rows with learnable weights and the BOT are the ones without.
Using Lemmn A.3, Equation (B.2) becomes:
(X & D)vec(F) =Y
(B.5)
And Equation (B.4) becomes:
(ITs @ (FO))uec(gB(F)) = FBOT
(B.6)
From Lemma A.4 the rank of Equation (B.5) is dm and the rank of Equation (B.6) is Tb(n dm
Tt
nTb - dm. These equations involve only the nTb variables of F, without including any learnable weights from W.
This implics that we have nTb lincar independent equations with nTb variables, leading to unique solution for F. Once we obtain a solution for F, we can substitute it into Equation (B.3), transforming it into linear equation as well each row of WTOP contains Tb linear equations corresponding to the size of F. Since every row of WToP contains precisely Tb variables, the equation is solvable.
The proof of the second condition both Theorem 3.4 and Theorem 3.5 has the same structuro as the first condition. It uses the shift operator, while introducing the auxiliary variables F, but now with the decoder matrix, D, instead of the encoder matrix, B.

---

Published as conference paper at TCLR 2025
Lemma B.7 Given samples X TR. Tbxm and labels Y E Rdxx created by the teacher, the student can eapress them using allocation A if and only if the following set of equations is solvable:
gD(F)W = F(r @ B)x=Y W WER RA, F Rdxx2
(B.7)
(B.8)
We will start by showing that the system is solvable, then the student can express the given labels. Assume the equations solvable using W E RA and F* E RdxaT FF" E Rdx* Notice that W and F are assumed to be solutions to the above equations and are unrelated to the teacher.
Proof:
From the definition of the operator 9D, Equation (B.7) becomes:
FTW" Fi-1 2 251ST
DW FT
Solving the recursion we get F? = T(W+)
Notice that:
BX1 BX2
(Lr @ B)X=
BXm-1
BXm
Y F= Σ D(W
Since W valid realization of A and it outputs the correct labels, the student can match the teacher.
Now, on the other hand, assume that the student can express Y. We choose W to be the recurrent connections of that student, which implies Y DE WT BX,, By selecting F; = T is easy to verify that the equations hold.
Thcorem B.8 (Second part of Theorem 3.4) Given an allocation A, if there is column with more than Td learnable weights the allocation is minimal.
Proof: We will prove that if the student can match with an allocation with more than Td learnable weights in some column, it can match with an allocation with less than dm weights, which means from Lemma B.4 that the match probability is 0.
Given an allocation with |A| = dm that has r; > Td learnable weights in the ith column and solves Lemma B.7. Notice that the column vector W, in Lemma B.7 participate in exactly Td equations Equation (B.7) the ith row only need to sulfice:
(D)F, =
Where F, is the ith of F.
Denote the solution as F and W W* Consider another allocation, A2, in which replace r Td > 0 of the learnable weights of A in the f'th column with constants, which means that [Az] < dm. Define W; as the learnable part of W,, FD(F") (F*) as the corresponding rows in (F(F*), W, as the remaining part of W,, and (D(F") as the remaining part of (F*).. Then:
9D OD(F))W; (F W F.
(D(F") W = = - -DD(F")
W; = (F) - go (FFF))

---

Published as a conference paper at TCLR 2025
Which means that there is a solution to Lemma B.7 with A2- In other words, every time Lemma B.7 is solvable with A. it is also solvable with Ag. Recall that [Ag] < dm, therefore, from Lemma B.4, the match probability of A2 is 0, which means that the match probability of A is also O.
Theorem B.9 (Second part of Theorem 3.5) Given an allocation A, if every column that has learnable weights has eroctly Td leornable weights in it, the allocation is marimal.
With r learnable weights in the model, the allocation consists of exactly Ta Ta T columns, each containing Td learnable weights, while the remaining columns are fully constant. Without loss of generality, assume that these constant columns are positioned at the right side of W. We can expross the first equation of Lemma B.7 as:
Proof:
dm
gD(F)- - WLEFT FLEFT
(B.9)
(D WRIGHT FRIGHT
(B.10)
Where the LEFT columns of W are the columns with learnable weights and the RIGHT are the ones without.
The matrix WRIGHT is of size (n- m) n, meaning that Equation (B.10) represents a linear equation (in F) with a rank of n for each row of gD(F). Given that there are Td such rows, we obtain a total of n'l'd - dm linear independent equations (in the same way obtained in the proof of Theorem B.6). When we include Equation (B.8), which is a lincar equation of rank dm, the cumulative total becomes nTd linear equations. These equations involve only the nTd variables of F, without including any learnable weights from W.
This implies that we have nfd linear equations with nI'd variables, leading to a unique solution for F. Once we obtain a solution for F, we can substitute it into Equation (B.9), transforming it into a linear equation as well-cach column of WLEFT contains Td linear equations corresponding to the size of F. Since every column of WLEFT contains preciscly Td variables, the equation is solvable.
B.1.1 EXAMPLE SMALL MODEL
Here, we present small model as an example that illustrates the different phenomena arising in subset learning of the recurrent connections of LRNN. For this example, we use the following weights: b= d 1, 2, 2, and m 2.
Since m Tb, this implies that the matrix X is square matrix, making it invertible. From Equation (3.3), we know that the LRNN model can eventually be reduced to a linear function. Let the matrix representing the linear function of the teacher be denoted by A* and for the student by A. If the student successfully matches the teacher, this implics:
AX = A
Given that X is invertible, this leads to A A'. Thus, we can disregard X, as the student will match the teacher if and only if A = A*. The matrix A" E RdxTb is a 1 x 2 matrix, meaning that A" is a vector with two entries, denoted as {Ai, A5). Therefore, the student matches the teacher if
DW B = Ai 2W B = A
(B.11)
(B.12)
For cach possible allocation, solving Equation (B.11) climinates one variable, and Equation (B.12) becomes a quadratic equation in one variable. We denote this equation as az² + be + 0, where a, b, and e are random variables that are derived from expressions involving all other random variables (iee, D, B, A", and the constant part of W). The equation is solvable if and only if 12 2 4ac. Thus, the match probability precisely the probability that b² 2 4ac.
There are 6 possible allocations for the r 2 weights in W. Interestingly, in four of these allocations, when manually calculating the expression for a, all coefficients reduce to yield a = 0. This

---

Published as conference paper at TCLR 2025
simplifies the equation to linear one, making it always solvable. These allocations are, therefore, maximal. As expected, these are the four allocations that satisfy the conditions of Theorem 3.5.
The two allocations that do not meet the conditions of Theorem 3.5 occur when the diagonal or ofl-diagonal entries allocated. Specifically, if:
Wi W22 W3
W
W
The two suboptimal allocations are (W1, W43 (the diagonal allocation) and (W2, Wa} (the off-diagonal allocation).
We evaluated the match probability for these allocations, drawing all weights from a normal distribu- tion with variance described in Appendix E.3. The match probability, MP(A), was 0.83 for the off- diagonal allocation and 0.74 for the diagonal allocation. The code for this analysis is included in the at- tached zip file under the scripts example mwdem -aadeeddigooal.. py and example model_off _i diagonal... . py.
This example reveals two key phenomena. First., unlike allocations involving the decoder and encoder, when learning the recurrent connections, there exist sub-optimal, non-minimal allocations due to the non-linearity of the equations. Second, even with non-linear equations, maximal allocations still exist.
B.2 LEARNING THE ENCODER
In this section, assumee that X is i.i.d. and not drawn from some underlying sample distribution X. This assumption is unnecessary in other sections because when B is constant and uncorrelated with X, we can treat the input as BX,, effectively eliminating any row-wise correlations (Corollary B.11). However, since B is learned in this context, the correlations within X will significantly impact the maximality conditions of A. Therefore, to avoid these complications, we assume no correlation in X for this section.
We start with few useful lemmas before proving the main theorem in Theorem B.14. A simpler but conceptually similar proof can be found in Theorem C.1. Therefore, the proof of Theorem C.1 can be considered as proof sketch for this theorem.
Lemma B.10 Let U1, E R be uncorrelated vectors with mean 0. Then, (V1, v2) is uncorrelated to (U1, 03)
Proof:
" Σ F( (
E
U u 1
Σ
(o))
Σ (((
F.
Corollary B.11 Let A be matrices such that there are no corvelations belween its rows. Then there corvelation between the rows of AB.
Lemma B.12 Let V (V: e mm and = [U, E Rkxdj be two sets of matrices such that any two entries of the matrices are uncorrelated. Let V (V. vidm be sequence of size dm containing matrices from V, and similarly, Ü = (Ü, E U) be sequence containing matrices from U. Denote dm dm as a sequence of matrices in Rmaxd such that |S| = dm (i.e., there is no i, such that V.O, = V,Ú,).
S = (V.0)
S is almost surely a basis if every entry of V appears in V more than kd limes and every entry of U appears in U no more than rd times. Otherwise, it is not basis.
Proof:

---

Published as conference paper at TCLR 2025
First direction Assume there exists V such that v appears in V kdd + times. Without loss of
generality, assume it is the first kd 1 entries of V (i.c., Vi V/2 =Va441). We will show that S is not a basis.
Let a # Ikd++1 be a vector such that:
Σ O,U, =0
Such vector exists because U consists of Rexd matrices, any kd + matrices are lincarly dependent. Thus:
kd+1
kd++1
kd+1
Σ
a
Σ VV = V. Σ au===00
:=1
This implies that there are linearly dependent vectors in S, meaning S is not a basis. The proof is exactly the same for the case where there exists u E U such that appears in U md + 1 times.
Second direction Assume that every appears in V no more than dk times, and every u U appears in Ú no more than dm times. We aim show that, almost surely, S is a basis, meaning the only a E dm satisfying:
dm Σ a;S, =0
(B.13)
i=1
is a = 0.
We will prove this by induction on the number of different entries from V and U used in S.
Base case: The minimal number different V's is +. We will show that S forms a basis this case; the same proof applics for minimal number of U's. Assume, without loss of generality, that the first dk entries of V are the same, followed by the next dk, and so on. Then:
dm
Σ S.S. Σ V.
Σ V
Since for every i, the set {Üika+s 1ر2 is linearly independent, we have ajkd+s = for every i, implying that a
Inductive step: Assume the statement holds for different V and E U in S, and prove it for n + 1. Assume by contradiction that a + 0. Let v E V such that there exists 1 < i S dm where V. = v and a; * 0, meaning u is part of the linear combination
(B.13).
Denote U, = (u E U 3s such that = wv), ie., the subset of U corresponding to entries paired with Define S. (we) Vu E U,}, the subset of S containing The probability that only elements in S, have non-zero coefficients in (B.13) is 0 because Ug is linearly independent (since [U,] s kd and the vectors in U, are uncorrelated).
Denote Lu, the set of all linear subspaces in pm formed by every subset of the entries of U.. If S S, spans one of the linear spaces in Lu., this contradicts the induction assumption, as this would imply linear dependence with different matrices in S.
If S S. does not span Lu., the set of linear subspaces of dimension |Sa] in Lu, that contain vectors in span(S (S,)
null set. Since span(S.) is such subspace, and uncorrelated with span(S) S.). the probability of having some of E span(S,)) such that v' E span(S) \ S,) is O. Therefore, the probability of this scenario occurring is indeed 0.
Lemma B.13 For any a, b < T and < j' S n, the correlation between W and W is or aiming to 0 as n aims to co.

---

Published as conference paper at TCLR 2025
Proof: Isserlis' theorem states that for any n gaussian random variables X1, X2 Xn=
2[X ... x,] = Σ II [[X,X,) PEp TJEP
Where the sum is over all the pairing of (....... n), ic all distinct way of partitioning (1,2....m) .n., into pairs {i,j}, and the product is over the pairs contained in p.
Now prove the lemma.
W
Σ
Wip W pip2 ... W Po
P1-P2---Pa
wh 815'
Σ
Wi Worgz- Wo.-1
Qn 02-92:096-11
B( Wb
Σ
Σ
B B Wpip....
Pa-- Wa W W
P1.P2...PP- 96-1
Denote =a+b b. Fix some P1. P2.P...... Pa-1 and qı, 42. 1--1- From Isserlis' theorem, in order to calculate EE [E[W,, Wmm.... ... W.. 1n Wen W Waye... ... Wn. ] we need to count the number of possible pairings. Since there are variables in the product, the number of pairs is:
cl
2
This can be obtained using a simple combinatorical calculation.
Now a specific pairing of the e variables. Since the entries of W are uncorrealted, the expectation of the sum of different entries is O. Thus, only if all the pairs in the pairing has two identical variables add value to the sum. Assume the pair of Wep is W We this means that i i= Pk- Since Ps is also in another pair, it will enforce another variable to be equal to i. This will end when the pair will be W P.-j or W W W--f In the first case it requires = j and in the latter i = j'. Another such chain will start from the pair of Wygn and again it requires /' j i' j/.
Therefore, for any pairing there is no more then single entry in the sum Epipp... E gg 28-1 that makes this pairing non-zero in expectation. Since the variance of the entrics of W is L variance of the product of the pairs is n ne/2 which means:
the no
cl
E (W by w
S
2 in
From Stirling inequality:
2 2
E (WT, w <
2n TC
Ze
c
nf
If = o(n) obviously e aims to 0. If c= (n). then e also aims to co. Recall that T S n, which means that < 2n < en, which means that (c) $ < 0() aims to 0.
Thcorem B.14 (Thcorem 3.2) Any allocation A learning the encoder B Roxb that follows both of the following conditions is maximal:

---

Published as conference paper at TCLR 2025
1. No row of B has more than Tm, learnable weights
2. No columns of B has more than Td. learnable weights
Every other allocation is minimal.
Proof: To avoid confusions with number of steps, T, use i to denote transpose matrix, e.g, At, From Lemma A.3, Equation (3.3) is equivalent to:
T
Σ
DW vec(Y)
For shortness, we denote D, DWT- and Dj its ith columns, and Xj the ith row of X, (which is the ith column of x,).
We separate the columns of Di=1 (xt @ DWT- to two parts the first part, denoted by is the columns that is multiplied by the learned entries of B, denoted by B. The other columns, denoted by C, are multiplied by the constant part of B, denoted by B. Thus:
Č = vec ČB
That means that the allocations matches iff Ö is invertible. Since r r= dm, E Rdmxdm we can say the allocation matches iff the columns of Ć are linear independent.
Every columns of kronecker product vectorization outer product of two vectors. In our case, it means that the columns of x @ Dr are X; @ DJ for some i, j. Denote:
V/ xi
Xi
x
X1
D
D
U
D
D4
The means that the the columns Ò is vec(V(U,) for some i, j. Specifically, if the (j, i) entry of B is in the allocation A, it means that ViU, will be in č.
Thus, the allocation matches iff (VUU)) is linear independent, namely a basis for maxd To use Lemma 1.12, we need to show that there no correlations. V4 built from the i.id X, so there should be no correlations, and there are not correlations in U, from Lemına B.13 and corollary B.11.
Since V; and U, has no internal correlations, from Lemma B.12 (with A: = 7') we get that (VUU)) (G. is if Vi is basis iff the set docsn't contain the same U, more then times the same V; more then times. Since the set contains the if the (j, i) entry of B is in the allocation A, it means that VüU will be in the set, it will be basis ifT follows exactly the conditions in the theorem.
C LINEAR PEED-FORWARD
Theorem C.1 For any allocation A learning an intermediate layer Wi E R is marimal if and only if it follows one of the following:
There is no rows that has more than learnable weights
2. There is no columns that has more than d learnable weights

---

Published as a conference paper at TCLR 2025
Otherwise, the allocation is minimal.
Proof: For any 1 siisis L, denote W, W ... Wi+1 W, Wjs--
Assume that the learned matrix is the 1-th layer, namely Wi. We can express the network as: Y= D-Waa+1 W.W,-.:XX
For brevity, denote A = WIA+1, W = W,,, and B = Wi-.. Here, A E B and B E Ruxxm From Lemma A.3, have:
(B" @ A))ec(W) = vec(Y)
Notice that every entry in vec(W) corresponds to a column in (B" @ A). Denote W as the learnable part of W and W as the constant part. Respectively, denote Ö as the matrix created from the columns of (B" & A) corresponding to W, and Č as the matrix from the columns corresponding to W. We can write:
CW vec(Y) CW
Since r= dm, we have Ö E Bddmxdm, The equation is solvable if and only if Ô is invertible.
Each different allocation corresponds to a distinct choice of dm columns out of the nm441 columns of (B" & A). Every column of Kronecker product is vectorization of the outer product of two vectors. In our case, denote A, as the i-th column A and B as the i-th column of B" (which is the i-th row of B). If the jith)-th entry of W included in the allocation, then the column created from the outer product of A, and BJ will be part of C.
Since Ö is square matrix, it is invertible if and only if its columns are linearly independent. As the columns are vectorizations of mal matrices, rices, they are linearly independent the matrices form a basis for pdxm From Corollary B.11, both A and B are uncorrelated, allowing us to use Lemma B.12 (with k= 1) to determine if these matrices indeed form basis. One can observe that the matrices will form a basis if and only if the conditions in this theorem hold.
D SHALLOW RELU
Lemma D.1 Let v E R. and P 10,1)"). Then, (2P T)u 2 0 if and only if Φ(v) = Pu; where is the ReLU function.
Proof: Let P. represent the i-th diagonal entry of P.
Assume (2P - -T' 2 O. This implies that for every i n, (2P. 1)., 2 0. When P: = 1, follows that v; 2 0, and when P: = 0, we have v; < 0. Therefore, Φ(v;) = Pau; holds for each i, and in general, Φ(v) = Pv.
1. First direction:
Now, assume Φ(v) Pe. This means that P = 1 when 2 0, and P. when 24 < O. Hence, (2P,-12 1)u; 2 holds for all i, which implies (2P- I)e 2 0. Lemma D.2 Let A be an allocation scheme that assigns learnable weights to k rows. Without loss of generality, assume
2. Second direction:
the first is rows.
Denote by W3 the first l columns of W2 and by W2 the remaining columns. Similarly, let Wt be the first lo rows of W, and W? the remaining rous.
For a set of samples X and labels Y generated by a teacher model, a student model matches the teacher if, for each 1 < is m, the following system of equations and inequalities is solvable:
W P.W.. yı- W2
(D.1)
(2P: 1)Wa; 0
(D.2)
P; E d 1),1)*), WIER,

---

Published as conference paper at TCLR 2025
Proof: Notice that the label yi is given by:
Di (2 = WW)(W + W. (W?));
From Lemma D.I, this leads the system of equations and inequalities described above, completing the proof.
Lemma D.3 For any allocation scheme, the probability that a given Pj has fewer than d ones and still satisfies Lemma D.2 is zero.
Proof:
Write P= P; for brevity. Suppose has fewer than ones. Then the rank of W2P is less than d. If the equations from Lemma D.2 are solvable, we can write:
(x.² @ P) ve) y: W3
Since (a @ W2 P) E Rdxmn and by Lemma A.4, the rank less than d, any matrix formed from subset of d columns will be invertible with probability zero. Therefore, the equation is solvable with probability zero.
This means that for every P., there are EnD (+) configurations for P. that are not usable. Notice that 2 = (1+ 1) = Eiz (1), which shows that as h grows larger, the fraction of configurations with probability decreases. For example, when k d, there is only valid configuration for P, as 2d -:- -1.
-1
Lemma D.4 Let A be allocation scheme that allocates learnable weights in the i-th row. Let Ps. represent the value in the i-th entry on the diagonal of Py. If the number of ones in {P is less than r,, then the probability that the system satisfies Lemma D.2 is zero.
Proof: For brevity, let the column vectors of W be {a, E R If the equations in Lemma D.2 are solvable, we can write:
(1f & P.) veo(W - yı W20(W7a:)
for 1 isis m. These represent dm linear equations.
Denote Diy E R as (X Pu) where Xl is the j-th entry of the I-th sample and Pti is the i-th diagonal element of Pt. In the matrix of this linear equation, the columms corresponding to index i, j in rec(W]) are the vectorizations of the outer products vy X a, Since have dm equations with r= dm variables, those columns must be linear independent for the equations to be solvable.
If r; columns corresponding to index i are selected, lincar independence must hold between the matrices Uig a, for r; choices of However, if the number of ones in (Pu), is less than rG, it means that each vector Vi has more than m - r; zero entries, which means that any set of r; options for j, the vectors Vi will be linear dependent. Therefore, the matrices Viy @ ag will also be linear dependent, which means that the equation is not solvable.
Notice that out of the zkm possible configurations for P, only Eh (7) are feasible. This shows that allocations using more rows (i.e,, larger k) and stacking fewer learnable weights per row (since the sum starts from r;) have significantly more possible configurations.
E EXPERIMENTS
E.1 METHODS
As we have seen multiple times in this paper, the match probability often boils down to the likelihood of set of polynomials having an exact solution. Standard gradient descent failed to find solution in this case. Typically, gradient descent can overfit a dataset because the model is often overparameterized relative to the data. However, in case, the model isn't overparameterized (as we use = dm), so second-order optimization methods were necessary.

---

Published as a conference paper at TCLR 2025
Instead of gradient descent methods, we used Python's scipy. -otliy..ppmizze.... fsolve. For each experi- ment, we ran the solver 1,000 times, and the match probability was calculated based on the number of solutions found. Since we used second order optimization, we were limited to use only small network sizes. However, the used networks sizes was enough to show the expected phenomena.
Each rum of fsolve begins with an initialization point zn for the algorithm. Empirically, we observed that fsolve frequently fails find a solution initially, but with multiple initializations, it eventually succeeds. Across all experiments, we identified threshold of initializations that, after being surassed, rarely leads to the discovery of additional solutions. We manually evaluated this threshold for each experiment and then doubled that number. For instance, in the LRNN experiments, we obscrved that no new solutions were found after 200 initializations, so we set the number of initializations to 400 lo ensure thoroughness.
In the ReLU experiment, we did not use fsolve as it failed to find any solutions in all cases. Instead, we employed Ada Hessian (Yao et al., 2021), and considered solution valid if the mean squared error (MSE) was below threshold of 10-2. Additionally, we recorded the number of solutions found across 1,000 attempls, and the resulting figure includes a shaded area to represent one standard error of the mean over these trials.
The experiment on MNIST data was the only one where we employed first-order optimization, specifically using the Adam algorithm (Kingma and Ba, 2017). This approach allowed us to utilizo larger network with n = 1000 parameters. We conjecture that first-order optimization performed better in this case due to two factors: (1) random data is inherently more challenging to learn as it lacks any underlying correlations, and (2) in the MNIST experiment, the task was to classify images (where the network predicts a label between 1-10) rather than reproducing a full vector, which simplifies the learning objective.
E.2 ENVIRONMENT
Figure Figure was created with T' 3, 1b=1, 4, and m = 3. All random variables were drawn from normal distribution with normalized variance (see Appendix E.3). Let the number of used rows be denoted as k. For every possible k we ran 1,000 trials and averaged the number of matches to estimate the match probability.
For each trial with given k an allocation was randomized in the first k rows, subject to the conditions in Theorem 3.4. Note that Theorem 3.4 identifies the minimal number rows for which below it there is no solution for any allocations (A < d; minimal allocations). This is why the graph docsn't start at = 0.
In Figure 2b, d 4- In this scenario, when k (0.25 on the x-axis), the only allocations that satisfy Theorem 3.4 are those that also satisfy Theorem 3.5. As expected, these allocations have a match probability of 1. Since the proof of Theorem 3.5 provides an algorithm to find a solution in this case, used that algorithm instead of scipy.solve The algorithm is included in the maximality irnn py file in the attached zip.
Figure 3 The foodforward network in Figure 3a was created with three layers, with = 4, d = 6, and = 4. The two hidden layer has the same size, denoted by in the graph. This mcans that there were r = md = 24 learnable weights, distributed as 8 per layer. Just like in the LRNN, the allocation was randomized across the rows, adhering to the conditions specified in Theorem 4.1. Notably, for the first layer, the number of rows does not impact the number of linear equations in Equation (4.2). Therefore, we set as limit for the number of columns utilized.
The ReLU network in Figure 3b was created with q = 6, d 4, and m 6. The size of the hidden layer, denoted by n, is provided in the graph.
26

---

Published as a conference paper at TCLR 2025
The experiment MNIST data shown in Figure 3e was conducted using network with 1000 and m = 1000, while the input and output sizes were set to = 784 and d = 10, respectively, reflecting the dimensions of the MNIST dataset.
E.3 VARIANCE IN THE EXPERIMENTS
Let u E R" and E R" be two random vectors, where v E g" drawn iid from N(0, g") and R ((1). Since they are uncorrelated, [[ h)] 0. However, the variance of their inner product is:
E (v, m3
E
E
= Σ B[a]] & &ng" = O(n)
Therefore, networks that multiply matrices repeatedly this way (e.g., Wh,, Dht) will cause the variance of the random variables to explode.
The solution is to sample all matrices with row size n with variance E. with g= (()) This ensures that the variance of the hidden state remains (1) throughout the process.
F SUPPLEMENTARY DISCUSSION
A natural point of comparison for our work is the Lottery Ticket Hypothesis (LTH) framework, which focuses on identifying sparse subnetworks within peramaarmeteii models that, when trained independently, achieve comparable performance to the full network. A key distinction between our work and LTH lies in the nature of the problem addressod and the context of sparsity. LTH focuses on identifying "winning tickets" - sparse subnetworks within an alrcady wer-paramettrized model that achieve comparable performance to the full network when trained independently. In contrast, our work examines how lo strategically allocate a fixed, limited nunber of learnable weights across a network to maximize its expressivity. This difference is critical: while LTH emphasizes discovering useful sparsity post hoc, our approach is about designing useful sparsity under strict resource constraints from the outset.
The student-teacher setup is a well-established framework for studying machine learning problems in controlled settings. It has been widely used in the literature to analyze generalization, expressivity, and optimization (c.g., see (Saglictti et al., 2022), which also includes a comprehensive set of references). The choice of student-teacher setup in work is deliberate and is done for clarity, as it isolates the reduction in expressive power arising solely from the allocation of learnable weights, rather than confounding factors such differences in architecture when the teacher and student share the same architecture, any decrease in the student's 's expressive power is attributable solely to the restriction in learned weights and their allocation. This allows us to rigorously estimate the approximation error stemming from allocation strategics, independent of other factors that might limit the student's ability to fit the labeled data. While we used the sendent-teacher setup for clarity, the framework is not inherently limited to this context. In fact, the teacher and student could differ in architecture, and the analysis could extend to general labeled data (the proofs in this paper remain valid under these conditions).
neuron nonlinearities. Specifically,
With respect to applications in neuroscience, little is known about the scale of learning (i.c., changes in synaptic weights) in the brain. Historically, technological constraints have made it notoriously difficult to track synaptic weight changes in real-time Mayashi-Takagi, 2021). However, it is well established that learning induces changes in neural activity that are often highly distributed both within and across brain regions (Chen et al., 2017; Steinmetz et al., 2019; Allen et al., 2019). Notably, a recent study demonstrated that even when learning is localized to subset of neurons and synaptic weights, the resulting activity fixeh-weight connections, leading to widespread changes in neural activity Kim et al. (2023). This obscrvation highlights the challenge of relating widespread neural activity to the specific extent of synaptic weight changes in the brain.
animals learn new tasks (Tsutsuni and
propagate through

---

Published as conference paper at TCLR 2025
Recent technological advances now enable neuroscientists to monitor changes in synaptic weights during learning, offering unprecedented insights into large-scale connectivity dynamics Daie et al. (2021); Humphreys al. (2022); Finkelstein et al. (2023). If the findings from our theoretical study extend to more complex network architectures and neuron nonlincarities, these innovations could make our predictions and insights testable in the near future. This possibility served one of the molivalions for conducting this research.
F.1 ASSUMPTIONS RELAXATION
In this paper, assumed that md (see Section 2). In the linear models we considered, this assumption is reasonable, as it ensures that the number of equations matches the number of free variables. As a result, teacher. This allowed us to establish "sufficient conditions" theorems (Theorems 3.1, 3.2, 3.5 and 4.1) to guarantce that no learnable weight is " "wasted". The reasoning straightforward since all learnable weights are generally needed to solve the equations, any excess usage in one subset of equations would lead to a shortage elsewhere.
md is the minimal number of learnable weights needed to match the
Consoquently, if > md, up to r- md learnable weights can be "wasted" without violating these conditions. This follows from the fact that when the number of free variables exceeds the number of constraints, there is additional flcxibility weight allocation, allowing some weights to be used inefficiently while still maintaining solvability.
One of the assumptions in this paper is that the input distribution X' is such that any samples drawn from it are linearly independent. In our linear models, if the samples are linearly dependent, the effective number of distinct samples is reduced. Specifically, for any set of m samples, there exists subset of m' independent samples (with m' S m) such that a match on these m' samples implies a match on all samples. Therefore, can treat the effective sample size as m' and assume m = m' in our analysis. This reinforces our assumption that, in the lincar case, the samples can be considered effectively linearly independent.


Reviews:
[{"review_id": "0SPpm8mAYb", "reviewer": "Reviewer_yDsn", "summary": "The paper investigates the conditions under which 'allocations' have maximal or minimal expressive power in linear RNN and linear MLPs.", "questions": "a. Could the authors comment on the practical implications of the theorems? \n\nb. L147 is joint not conditional? If so notation is confusing.", "limitations": "", "rating": 3, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 1, "strengths": "Originality: I think allocation is an interesting concept though it seems to significantly overlap with the concept of subnetwork in lottery ticket hypothesis. \n\nClarity: The paper is clearly written.", "weaknesses": "Quality: Studying expressivity of RNNs/MLPs from the perspective of linear solvable equations require strong assumptions such as 'the distribution $\\mathcal X$ is such that any drawn square matrix is invertible' (l197) and I'm having trouble extracting insights from the theorems. \n\nSignificance: Increasing the percentage of learnable weights leads to more expressivity seems trivial to me (maybe there are insights I'm not seeing from the paper?) so I'm not quite sure what we can learn from the submission.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wyzYmrVWrE", "reviewer": "Reviewer_mi9c", "summary": "This paper develops a theoretical framework for analyzing the expressive power of neural networks when only allowing a subset of the network to learn. The authors focus on a student-teacher setup and defines expressivity as the likelihood that the student can replicate the teacher’s outputs. Using this metric, this work analyzed linear RNNs and deep linear feedforward networks, and evaluated the expressive power of different allocation strategies, then extended their analysis to one-layer ReLU feedforward networks.", "questions": "1.\tBoth the student and the teacher weights are drawn from i.i.d. Gaussian, have you considered correlated weights in the teacher, or introducing structures into the teacher weights? \n2.\tThe central result that it is better to allocate the learnable weights throughout the network. Is this consistent with existing findings about learning in the brain?\n3.\tWhen stating that “the probability of finding at least one solution increases with the number of polynomials”, does the degree of the polynomials play a role?\n4.\tIn the proof of theorem B1, do you assume that W is diagonalizable? The sentence “the eigenvector xxx is a space” does not make sense to me. Furthermore, I do not see why it is important to prevent the network from being degenerate, it is still a valid function of the input sequence, and it’s simply that the degree of freedom is less than the amount of effective linear weights.", "limitations": "", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The paper presents several theoretical results about the expressive power of linear networks when allowing a subset of the network to learn, and concludes that spreading the learnable weights in different parts of the network allows for stronger expressive power.", "weaknesses": "1.\tThere are many ways to evaluate allocation strategies, including generalization performance, capabilities of transfer learning and continual learning, etc. These are the interesting problems that the authors used to motivate their work. However, this paper particularly focuses on how allocation strategy affects the expressivity of a network, in a very specific setting, limiting the scope and potential insights that could be obtained from this work.\n2.\tThe result of the work is restricted to a student-teacher framework in the sense that the central definition of the match probability is defined based on a student-teacher framework, where the student and the teacher have matching architectures, making it difficult to extend the results to real-world applications even heuristically. The numerical results shown in this paper is also limited to this synthetic task only.\n3.\tVarious assumptions are dispersed and showed up in various places within the text, it would be better if the authors could explicitly list their assumptions when stating the theorems.\n4.\tI did not check all proofs carefully but multiple proofs in this paper is written in a very informal way, making it difficult to judge the validity of the proofs.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "WbPxCboIix", "reviewer": "Reviewer_QyMh", "summary": "This paper provides a theoretical investigation into the distribution of learnable weights in neural networks, drawing inspiration from brain mechanisms. The study measures network expressivity as a function of these learnable weights, examining various network architectures and validating the theory through experiments.", "questions": "-  Are there any constraints preventing from running the experiments with gradient descent? Is it correct to think that if you did you could have access to results with larger networks? \n- Do you have any intuition on how these insights might scale to more complex networks? Specifically, if larger models contain an increasing number of polynomials increases the probability to find a solution , does this imply that weight distribution becomes less significant, given that the transition would be so abrupt that the network would almost never (with a probability tending to zero) have no solution or expressivity zero ? \n- (This may be outside the intended scope, but I’m curious.) I understand that the approach abstracts away the specifics of the learning algorithm. However, I’m interested in how your findings might depend on the network’s initialization under a particular learning algorithm (e.g., the scale and relative scaling of layers). Given that different initializations can influence the learning rates of certain weights more than others—effectively controlling which parts of the network learn more actively—how does the network’s expressivity vary under these conditions?\n\nI hope this review is helpful for the further development of the paper. I encourage the author to continue this research and incorporate the feedback provided.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Congratulations on your submission to ICLR! I commend the authors on producing this great piece of research. Below is my detailed review of the work:\n\n**Originality**\nThis paper introduces a theoretical framework for analyzing network expressivity as a function of learnable weight allocation. Its originality lies in drawing parallels with brain mechanisms and adopting a fresh theoretical approach.\n\n**Quality**\nThe paper demonstrates high quality with well-substantiated theoretical findings that are clearly explained and motivated. Key strengths include:\n- Thorough and detailed theoretical results, effectively show that predictions from smaller models generalize well to non-linear, shallow ReLU architectures.\n- Theoretical analysis is rigorously structured, adding robustness to the findings.\n- The mathematical derivations appear accurate and sound.\n\n**Clarity**\nThe paper is well-organized and accessible. \n\n- The use of a simplified linear network model as a toy example helps to build intuition, significantly enhancing readability. \n- The figures are clear, informative, and effectively support the main content.\n\n**Significance**\nThis work is a valuable contribution to the machine learning research community, especially in deepening our understanding of model expressivity as a function of trainable weights in the context of increasing training costs. Additionally, the proposed theoretical framework may offer valuable insights for the neuroscience community.", "weaknesses": "**Originality**\nNo notable weaknesses in originality.\n\n**Quality:**\nThe paper is of high quality, yet there are areas where further clarity and detail could strengthen its impact:\n\n- The paper would benefit from a more explicit discussion of its limitations. While valuable, the theoretical approach may not fully capture some empirical phenomena seen in practical neural networks. Highlighting these potential divergences between theory and real-world observations would add useful nuance.\n- A clearer connection to applications in neuroscience would enhance the paper’s relevance to that field.\n\n**Clarity**\nThe clarity of the paper is generally high but could be improved in specific areas:\n\n- An introductory figure would be helpful, particularly for readers unfamiliar with the topic. For instance, a visual summary of the student-teacher setup could make the content more accessible.\n- Including a discussion in the introduction on the growing computational demands—now requiring substantial resources—would add timely context to the study.\n- Strengthening the link between neural networks and brain mechanisms would clarify the relevance of the approach.\n- Developing Theorem 3.3 further, potentially in the appendix, would also improve clarity.\n\n**Significance**\nThe significance of the study could be enhanced with a few adjustments:\n- The benchmarks used primarily involve toy models, which may limit the generalizability of the findings. Extending the analysis to larger models could increase the impact and relevance of the results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "xGKnnOdsUj", "reviewer": "Reviewer_HB5t", "summary": "The authors investigate the capacity of neural networks under constrained conditions where only a fixed number of weights are plastic and can be changed. The authors present theoretical work and then relate the theory to empirical simulations in simple networks. \nThis work is quite interesting in that it forces us to think that not all weights are equal, that not all weights are needed, and that astute ways of choosing which weights to change can have a large impact in the capacity and efficacy of a neural network.", "questions": "The potential connections between the work presented here and weight protection strategies in continual learning is probably worth exploring further (though this is not a requirement by any means for the current work).", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "This work introduces an interesting question about the possibility to modify only certain weights in a network and ask how the choice of plastic weights impacts neural network capacity.\nThere has not been much work along these lines. Perhaps one related idea relates to continual learning. Upon learning new things, it may be useful to strategically decide which weights to change more. One instantiation of this is Kirkpatrick et al PNAS 2017 (the authors cite other work in this direction as well).\nThe work presents both theory and empirical simulations. \nThe work introduces a benchmark that would be useful for the field to compare different potential mechanisms to allocate learnable parameters.", "weaknesses": "The abstract states that “biological systems like the brain where evidence suggests that only a subset of synaptic weights are modified during learning”. This is a grandiose claim that is not substantiated by any references. I strongly suggest that they remove this claim. Otherwise, the authors should provide compelling evidence about this statement. The introduction provides a better assessment: “the scale of this process in the brain is unclear”. \nThe experiments presented are based on rather simple NNs. It is not clear how the conclusions extrapolate to more complex NNs. But this point does not distract from the beauty of the work presented here.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)