## Memorization Capacity for Additive Fine-Tuning with Small ReLU Networks

Jy-yong Sohn * 1

Dohyun Kwon * 2,3

Seoyeon An 1

Kangwook Lee 4

1 Department of Statistics and Data Science, Yonsei University, Republic of Korea 2 Department of Mathematics, University of Seoul, Republic of Korea

3 Center for AI and Natural Sciences, Korea Institute for Advanced Study, Republic of Korea

4 Department of Electrical and Computer Engineering, University of Wisconsin-Madison, WI, USA

## Abstract

Fine-tuning large pre-trained models is a common practice in machine learning applications, yet its mathematical analysis remains largely unexplored. In this paper, we study fine-tuning through the lens of memorization capacity. Our new measure, the Fine-Tuning Capacity (FTC), is defined as the maximum number of samples a neural network can finetune, or equivalently, as the minimum number of neurons ( m ) needed to arbitrarily change N labels among K samples considered in the fine-tuning process. In essence, FTC extends the memorization capacity concept to the fine-tuning scenario. We analyze FTC for the additive fine-tuning scenario where the fine-tuned network is defined as the summation of the frozen pre-trained network f and a neural network g (with m neurons) designed for fine-tuning. When g is a ReLU network with either 2 or 3 layers, we obtain tight upper and lower bounds on FTC; we show that N samples can be fine-tuned with m = Θ( N ) neurons for 2-layer networks, and with m = Θ( √ N ) neurons for 3layer networks, no matter how large K is. Our results recover the known memorization capacity results when N = K as a special case.

## 1 INTRODUCTION

As a branch of machine learning theory, the expressive power of neural networks is investigated for several decades. By using the concept of universal approximation, it is shown that neural networks can approximate a large classes of functions, either in the depth-bounded scenarios [Cybenko, 1989, Funahashi, 1989, Hornik et al., 1989, Barron, 1993] or width-bounded scenarios [Lu et al., 2017, Hanin and Sellke, 2017, Kidger and Lyons, 2020, Park et al., 2020]. Another line of research focused on the memorization ca-

* Equal Contribution

pacity of neural networks [Baum, 1988, Huang and Babri, 1998, Huang, 2003, Yun et al., 2019, Vershynin, 2020, Rajput et al., 2021, Vardi et al., 2021], exploring the capability of neural networks for memorizing finite samples.

Meanwhile, with the advent of large language models [Brown et al., 2020, OpenAI, 2023, Ouyang et al., 2022, Chowdhery et al., 2022, Zhang et al., 2022, Touvron et al., 2023] and foundation models [Bommasani et al., 2021, Radford et al., 2021, Ramesh et al., 2022], the paradigm of pre-training followed by fine-tuning is dominating the machine learning communities. Various empirical results show that a gigantic model pre-trained on large amount of data can be easily fine-tuned to perform well on downstream tasks, given only a small amount of additional data for the target task. Compared with the extensive empirical results, mathematical analysis on fine-tuning large pre-trained models remains largely unexplored.

̸

In this paper, we take the first step in understanding the fine-tunability of pre-trained networks through the lens of memorization capacity. We focus on the scenario where we fine-tune a pre-trained neural network f on dataset D = { ( x i , y i ) } K i =1 with K samples; here, x i ∈ R d and y i ∈ R for all i ∈ [ K ] where [ K ] = 1 2 { , , · · · , K } , and we assume x i = x j for all i = j . Let T := { i ∈ [ K ] : f ( x i ) = y i } be the set of indices of samples that the pre-trained network f does not fit. The cardinality of this set is denoted by N := | T | ≤ K . In other words,

̸

̸

$$f ( x _ { i } ) = y _ { i }$$

holds for all i ∈ [ K ] \ T , while not guaranteed for i ∈ T . Our aim is to add a neural network g θ (parameterized by θ ) to the pre-trained network f in a way that the fine-tuned network f + g θ satisfies

$$( f + g _ { \theta } ) ( x _ { i } ) = y _ { i }, \ \forall i \in [ K ]. \quad \quad ( 2 )$$

See Fig. 1 for the visualization of the additive fine-tuning scenario we focus on. This scenario is motivated by recently proposed additive fine-tuning methods [Zhang et al., 2020,

(

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00359v2-figure-4987b7f1-21da-459c-8d20-3fae8ec607ba.jpg)

)

̸

Figure 1: Additive fine-tuning scenario where the pretrained network f is fine-tuned to f + g θ , in order to fit the dataset D = { ( x i , y i ) } K i =1 . Here, the pre-trained network already fits N samples { ( x i , y i ) } i ∈ [ K ] \ T , where T ⊆ [ K ] is the set of indices where y i = f ( x i ) . We use g θ to fill the gap between f ( x i ) and y i , for i ∈ T .

Fu et al., 2021, Cao et al., 2022], and especially, the sidetuning [Zhang et al., 2020] where a side network g θ is added to the pre-trained network f . Since our model does not cover other popular fine-tuning methods including LoRA [Hu et al., 2021], extending our theoretical results to such popular methods is remained as a future work. Under such setting, we define the fine-tuning capacity (FTC) of a neural network g θ as below.

Definition 1.1 (FTC) . The fine-tuning capacity of a given neural network g θ is the maximum number N satisfying the following property: for all x i ∈ R d , y i ∈ R , for all T ⊆ [ K ] satisfying | T | = N , and for any choices of function f satisfying f ( x i ) = y i for all i ∈ [ K ] \ T , there exists parameter θ such that ( f + g θ )( x i ) = y i all i ∈ [ K ] .

Under such a setting, we establish the upper/lower bounds on FTC, when g is 2-layer ReLU network or 3-layer ReLU network. Our main contributions are summarized below:

- · We define a new metric called Fine-Tuning Capacity (FTC), which measures the maximum number of samples N ⋆ a neural network with m neurons can fine-tune. Equivalently, we define the minimum number of neurons m ⋆ needed to arbitrarily change N labels among K . FTC can be considered as an extension of memorization capacity, tailored for the fine-tuning scenario.
- · For 2-layer ReLU networks, we establish tight upper and lower bounds on m ⋆ , in Theorem 4.1. The upper bound is obtained by a novel neural network construction for fine-tuning. Our construction requires less number of neurons than conventional constructions developed in the memorization capacity literature when K ≥ 3 N +2 . By using our bounds on m ⋆ , we also provide an equivalent statement in Corollary 4.2, showing the tight bounds on the fine-tuning capacity N ⋆ .
- · For 3-layer ReLU networks, we obtain tight upper and lower bounds on m ⋆ in Theorem 5.1. Our results imply that N samples can be fine-tuned with m = Θ( √ N ) neurons without any dependence on K . We also provide an equivalent statement in Corollary 5.2, showing the tight upper and lower bounds on N ⋆ .

## 2 RELATED WORKS

Fine-Tuning Various methods for efficient fine-tuning are introduced in recent years [Houlsby et al., 2019, Zhang et al., 2020, Zaken et al., 2021, He et al., 2021], which fine-tune only a small part of pre-trained models to adapt it for target tasks. There are some mathematical analysis on fine-tuning [Wu et al., 2022, Zeng and Lee, 2023, Giannou et al., 2023, Englert and Lazic, 2022, Oymak et al., 2023, Du et al., 2020, Malladi et al., 2023] or more broadly on transfer learning [Tripuraneni et al., 2020, Maurer et al., 2016], but none of them analyzed the fine-tunability of large pre-trained models using the lens of memorization capacity.

6 Memorization One concept relevant to FTC is memorization capacity which measures the ability of memorizing given feature-label pairs { ( x i , y i ) } K i =1 . Finding the bounds on the memorization capacity is considered in recent works on various networks [Zhang et al., 2016, Yun et al., 2019, Vershynin, 2020, Rajput et al., 2021, Nguyen and Hein, 2018, Hardt and Ma, 2016, Kim et al., 2023, Madden and Thrampoulidis, 2024, Madden et al., 2024, Madden, 2024]. The effect of memorization in large language models is explored in recent works, both for pre-training [Carlini et al., 2022, Ippolito et al., 2022] and for fine-tuning [Zeng et al., 2023].

## 3 FINE-TUNING CAPACITY

Note that a notion of additive FTC given in Definition 1.1 contains the pre-trained network f , but one can confirm that FTC does not depend on f since f ( x i ) = y i holds for all i ∈ [ K ] \ T , for every pre-trained network f we are considering. Below we provide an equivalent simpler definition.

Definition 3.1 (FTC, equivalent form) . For a given positive integer K , the fine-tuning capacity (FTC) of a given neural network g θ is

$$\text{mong} \quad \text{s.u.v.\ } y o \, \infty \\ \text{nemo} _ { \text{nario} } \quad N _ { \text{FTC} } ^ { * } ( g, K ) \coloneqq \max _ { N \in \{ 0, 1, \cdots, K \} } N \text{ such that} \\ \text{upper} \quad \forall T \subseteq [ K ] \text{ with } | T | = N, \forall x _ { i } \in \mathbb { R } ^ { d }, \forall z _ { i } \in \mathbb { R }, \\ \text{he up} _ { \text{k con} } \quad \exists \theta \text{ satisfying } \begin{cases} g _ { \theta } ( x _ { i } ) = z _ { i } & \forall i \in T, \\ g _ { \theta } ( x _ { i } ) = 0 & \forall i \in [ K ] \, \bar { \ } T. \\ \text{ns de} \quad & \text{$\quad $\quad $\quad $\quad $\quad $\quad $\quad $\quad $\quad $\quad $\quad $\quad $\quad $\quad $\quad $\quad $\quad $\quad $\quad $\quad $\quad $\quad $\quad $\quad $\quad $\quad $\quad $\quad $\quad $\quad $\quad $\quad $\quad $\quad $\quad $\quad $\quad $\quad $\quad $\quad $\quad $\quad $\quad $\quad $\quad $\quad $\quad $\quad $\quad $\quad $\quad $\quad $\quad $\quad $\quad $\quad $\quad $\quad $\quad $\quad $\quad $\quad $\quad $\quad $\quad $\quad $\quad $\ \end{cases}$$

This definition is a generalization of conventional memorization capacity shown below, when the condition is relaxed to a special case, T = [ N ] .

Definition 3.2 (Memorization Capacity [Yun et al., 2019]) . The memorization capacity of a neural network g θ is

$$N _ { \text{MC} } ^ { * } ( g ) \coloneqq \max _ { N \geq 0 } N \text{ such that}$$

$$\mu _ { \mu } x _ { i } \in \mathbb { R } ^ { d }, \forall z _ { i } \in \mathbb { R }, \exists \theta \, \text{with} \, g _ { \theta } ( x _ { i } ) = z _ { i } \ \forall i \in [ N ] \ ( 4 )$$

z

Figure 2: Proving Theorem 4.1 for K = 14 , N = 4 .

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00359v2-figure-3b77b133-8562-4ed4-88e4-791b38dd301c.jpg)

z

Figure 3: Proving Theorem 4.1 for K = 9 , N = 4 .

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00359v2-figure-cf6b4064-649a-4610-b3a7-d8111065ba22.jpg)

Remark 1. The memorization capacity and the fine-tuning capacity has a trivial bound: for any neural network g and for arbitrary K &gt; 0 ,

$$N _ { \text{FTC} } ^ { * } ( g, K ) \leq N _ { \text{MC} } ^ { * } ( g ). \quad \quad ( 5 ) \quad \text{Th}$$

Note that FTC is defined as the maximum number of samples N we can fine-tune using a given network g . One can also consider an equivalent definition: the minimum number of neurons m contained in g to successfully fine-tune N samples, which is formally stated below.

Definition 3.3 (FTC, equivalent form, in terms of # neuron) . The minimum number of neurons required for fine-tuning arbitrary N out of K samples, is defined as m ⋆ FTC ( N,K ) := min m ≥ 0 m such that

$$\cdot \cdot \quad & \quad m \geq 0 \\ & \forall T \subseteq [ K ] \text{ with } | T | = N, \forall x _ { i } \in \mathbb { R } ^ { d }, \forall z _ { i } \in \mathbb { R }, \\ & \exists \text{ neural network } g _ { \theta } \text{ with } m \text{ neurons satisfying } \text{ Corol} \\ & \begin{cases} g _ { \theta } ( x _ { i } ) = z _ { i } & \text{ for all } i \in T, \\ g _ { \theta } ( x _ { i } ) = 0 & \text{ for all } i \in [ K ] \, \text{ } T. \end{cases}$$

Throughout the paper, we use N ⋆ as a short-hand notation for N ⋆ FTC , and use m ⋆ as a short-hand notation for m ⋆ FTC . Our theoretical results provide bounds on m ⋆ and N ⋆ , e.g., Theorem 4.1 is bounding m ⋆ , while an equivalent result in Corollary 4.2 is bounding N ⋆ .

## 4 FTC OF 2-LAYER FC RELU NETWORKS

A 2-layer fully-connected neural network g θ : R d → R with ReLU activation can be represented as

$$g _ { \theta } ( x ) = W _ { 2 } \sigma ( W _ { 1 } x + b _ { 1 } ) + b _ { 2 }, \quad \ ( 6 )$$

which is parameterized by θ = [ W W b b 1 , 2 , 1 , 2 ] where W 1 ∈ R m d × , W 2 ∈ R 1 × m , b 1 ∈ R m , and b 2 ∈ R . Here, m is the number of hidden neurons, and σ is the ReLU activation. The below result states the bounds on m for 2-layer FC ReLU networks.

## Theorem 4.1. Let K ≥ 3 .

- 1. For all T ⊆ [ K ] , | T | = N , x i ∈ R d , z i ∈ R , i ∈ [ K ] , there exists a 2-layer fully-connected ReLU network g with m neurons satisfying equation 3 and

$$m \leq \min \{ 3 N + 1, K - 1 \}.$$

2. For given T ⊆ [ K ] , | T | = N , x i ∈ R d , z i ∈ R , i ∈ [ K ] , suppose that equation 3 holds for some 2layer fully-connected ReLU network g with m neurons. Then,

$$\min \{ 3 N, K - 2 \} \leq m.$$

1

Thus,

$$\ m d \quad \min \{ 3 N, K - 2 \} \leq m ^ { * } \leq \min \{ 3 N + 1, K - 1 \}. \ \ ( 7 )$$

The proof of this theorem is given in Sec. 4.1 and Sec. 4.2.

2

Remark 2. If N = K (i.e., fine-tuning changes all labels), then the result of Theorem 4.1 reduces to

$$m ^ { * } + 1 \leq N = K \leq m ^ { * } + 2.$$

The upper bound of N coincides with the upper bound of memorization capacity studied in the result of [Yun et al., 2019]. On the other hand, the lower bound is consistent with the one given in [Zhang et al., 2016].

Below we state the bounds for the fine-tuning capacity of a 2-layer fully-connected ReLU, directly obtained from the above theorem.

Corollary 4.2 (FTC of 2-layer FC ReLU) . Suppose K ≥ 3 . For given m ∈ N , let N ⋆ be the fine-tuning capacity of a 2-layer fully-connected ReLU network g given in equation 6 with m neurons.

1. If K ≥ m +2 , then

$$\left \lfloor \frac { m - 1 } { 3 } \right \rfloor \leq N ^ { * } \leq \frac { m } { 3 }. \text{ \quad \ \ } ( 8 )$$

2. If K ≤ m +1 , then N ⋆ = K .

Proof. Suppose that K ≥ m + 2 . By Theorem 4.1.1, for | T | = ⌊ m -1 3 ⌋ , there exists a 2-layer fully-connected ReLU network g where the number of neurons of g is less than or equal to

$$\min \left \{ 3 \left \lfloor \frac { m - 1 } { 3 } \right \rfloor + 1, K - 1 \right \} = 3 \left \lfloor \frac { m - 1 } { 3 } \right \rfloor + 1 \leq m.$$

Here, K ≥ m +2 yields the first equality while the second inequality follows from the definition of the floor function. This yields the lower bound of equation 8. On the other hand, due to Theorem 4.1.2 and K ≥ m +2 , we conclude the upper bound of equation 8.

Suppose that K ≤ m + 1 . Similarly, by Theorem 4.1.1 for | T | = K , there exists a 2-layer fully-connected ReLU network g where (the number of neurons of g ) ≤ K -1 ≤ m . This yields N ≥ K . As N ≤ K always holds due to our construction, we conclude N = K .

In other words, for sufficiently large K , the fine-tuning capacity N does not depend on the size K of the underlying dataset D but the number of neurons m .

## 4.1 PROOF OF LOWER BOUND ON m ⋆

We first prove the lower bound in Theorem 4.1 when K ≥ 3 N +2 . Define T = { 3 6 9 , , , ..., 3 N } , and define x i = i u for all i ∈ [ N ] for arbitrary vector u ∈ R d . Let z i = 2 if i = 6 k for some k ∈ N and z i = -1 if i = 6 k -3 for some k ∈ N . See Fig. 2 when K = 14 and N = 4 . Then, ¯ ( ) := g θ t g θ ( t u ) is a piecewise affine function with at least 3 N +1 pieces. Recall that using Theorem 3.3 of [Yun et al., 2019] for 2-layer ReLU network, ¯ ( ) g θ t is having m + 1 pieces, since ReLU activation is a piecewise linear function with two pieces. Thus, m ≥ 3 N holds. Note that given K and N , the above proof scheme specifies T, { x i , z i } K i =1 and counts the number of pieces for the piecewise-linear function ¯ ( ) = g θ t g θ ( t u ) , under the setting of x i = i u .

We use a similar technique for proving the lower bound on m when N ≤ K &lt; 3 N +2 . Consider revising ( T, x , z i i ) triplet (defined for K ≥ 3 N +2 case), so that K &lt; 3 N +2 condition is satisfied. For example, when K = 2 N + 1 , the triplet is revised as T = { 2 4 , , · · · , 2 N } , z i = 2 if i = 4 k for some k ∈ N and z i = -1 if i = 4 k -2 for some k ∈ N , as illustrated in Fig. 3, which has K -1 = 8 pieces. For general K and N satisfying K &lt; 3 N +2 , one can choose ( T, x , z i i ) triplet such that the corresponding ¯ ( ) g θ t = g θ ( t u ) has K -1 pieces. Thus, the number of pieces p K ( ) of ¯ ( ) g θ t we constructed can be represented as

$$p ( K ) = \begin{cases} 3 N + 1, & \text{if $K\geq 3N+2$} \\ K - 1, & \text{if $N\leq K<3N+2$} \end{cases} ( 9 ) \quad H e r e,$$

This completes the proof.

## 4.2 PROOF OF UPPER BOUND ON m ⋆

We here establish the upper bound in Theorem 4.1. To be specific, in Theorem 4.4, we establish the upper bound on m ⋆ in terms of the partition of [ K ] \ T . The key idea is to remove all points of [ K ] \ T except for the endpoints of each block as in Figure 4. More discussion will be provided below.

Let us introduce some terminology. For a given set I , a partition P of I is a set of nonempty subsets P of I such that every element in I is in exactly one of these subsets. We denote P ∈ P by the block of P .

Definition 4.3. For I ⊂ [ K ] , we say that P ( I ) is the consecutive partition of I if all consecutive integers in I are

z

Figure 4: Illustration of the neural network constructed in Theorem 4.4 with K = 14 and T = { 4 7 9 14 , , , } . P ([ K ] \ T ) is the partition P ( I ) given in Example 1. The gray points are the removed ones.

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00359v2-figure-b3e952e7-15ca-4a47-9062-e4ce7380554b.jpg)

included in the same block, i.e., for i, j ∈ I , i and j are in the same block of P ( I ) if and only if | i - | j = 1 .

Example 1. If I = 1 2 3 5 6 8 10 11 12 13 { , , , , , , , , , } , then the consecutive partition is defined as

$$\stackrel { \dots } { \text{ast} } \quad \mathcal { P } ( I ) = \{ \{ 1, 2, 3 \}, \{ 5, 6 \}, \{ 8 \}, \{ 1 0, 1 1, 1 2, 1 3 \} \}, \ ( 1 0 )$$

and the blocks of P ( I ) are { 1 2 3 , , } { , 5 6 , } , { 8 } , and { 10 11 12 13 , , , } .

The following theorem shows that the upper bound of m is given in terms of the size of the blocks in P ([ K ] \ T ) . For proving Theorem 4.1, we find the uniform bound for general datasets using this bound and Lemma 4.7.

Theorem 4.4. Consider the same setting as in Theorem 4.1, and suppose that

$$a ^ { T } x _ { 1 } < a ^ { T } x _ { 2 } < \dots < a ^ { T } x _ { K } \quad \quad ( 1 1 )$$

holds for some a ∈ R d . Then, there exists an m -neuron network g θ ( x ) = W 2 σ ( 1 m a x T + b 1 )+ b 2 , such that equation 3 holds, and

$$\stackrel {! } { ; } \quad m ^ { * } \leq K - 1 - \sum _ { P \in \mathcal { P } ( [ K ] \langle T ) } \max \{ | P | - 2, 0 \} \quad ( 1 2 )$$

Here, W 2 ∈ R 1 × m , b 1 ∈ R m , and b 2 ∈ R .

Remark 3. To minimize the width m of the network, a smaller number of blocks of bigger sizes would be ideal. If we only have one block in the partition P ([ K ] \ T ) , then Eq. 12 is given as

$$m ^ { * } \leq K - 1 - | [ K ] \, \smallsetminus T | + 2 = N + 1.$$

This happens when a x T i s for i ∈ [ K ] \ T are segregated for some a , e.g., when [ K ] \ T = { i, i +1 , · · · , j } for some i &lt; j in [ K ] . Thus, some appropriate projection yields a smaller number of neurons required.

Remark 4. The worst scenario is when every block of P ([ K ] \ T ) has 2 or less elements, as in Figures 2 and 3. Note that if K -N is much larger than N , then this scenario cannot occur. This is because the number of blocks cannot be larger than min { K -N,N } +1 from Lemma 4.6.

Proof of Theorem 4.4. First, we consider the case when

$$| P | \leq 2 \text{ for all } P \in \mathcal { P } ( [ K ] \, \smallsetminus T ). \quad \ \ ( 1 3 ) \quad ^ { r \, \vee }$$

In this case, it suffices to prove m ≤ K. As K neurons can represent K data points, the inequality directly follows from the standard argument as in Zhang et al. [2016] and also shown in Lemma 4.5.

Let us consider general cases. The main strategy is to remove data points so that equation 13 holds. Specifically, except for two endpoints of each block P ∈ P ([ K ] \ T ) , we remove i ∈ [ K ] \ T from [ K . ] Let us denote this new subset of [ K ] by

$$J = \{ j _ { 1 } < j _ { 2 } < \dots < j _ { | J | } \} \quad \quad ( 1 4 ) \quad \text{The}$$

For example, when K = 14 and T = { 4 7 9 14 , , , } as in Fig. 4, the consecutive partition P ( I ) is given in Eq. 10, and thus we remove { 2 11 12 , , } from [ K ] = 1 2 { , , · · · , 14 } , which gives us J = { 1 3 4 5 6 7 8 9 10 13 14 , , , , , , , , , , } . Note that the number of data points in J is

$$| J | \coloneqq K - \sum _ { P \in \mathcal { P } ( [ K ] \langle T ) } \max \{ | P | - 2, 0 \}. \quad ( 1 5 ) \quad \text{Lem} _ { \ h a v e }$$

Applying Lemma 4.5 with A := { ( a x T j , z j ) } j ∈ J and m = | J | -1 , there exist W 2 ∈ R 1 × m , b 1 ∈ R m , and b 2 ∈ R such that

$$h _ { \theta } ( a ^ { T } x _ { j } ) = W _ { 2 } \sigma ( 1 _ { m } a ^ { T } x _ { j } + b _ { 1 } ) + b _ { 2 } = z _ { j }$$

for all j ∈ J . Thanks to h θ ( a x T ) = g θ ( x ) , we conclude g θ ( x j ) = z j for all j ∈ J .

Lastly, for i ∈ [ K ] \ J , there exist two endpoints j i &lt; j i +1 such that [ j , j i i +1 ] ∩ ([ K ] \ T ) in P ([ K ] \ T ) , and j i &lt; i &lt; j i +1 . Note that h θ constructed in Lemma 4.5 is linear in [ a x T j i , a x T j i +1 ] . Since g θ ( x j i ) = g θ ( x j i +1 ) = 0 , we conclude that g θ ( x i ) = 0 as desired.

Lemma 4.5. For m ≥ 1 and A = { ( w , z i i ) } m +1 i =1 where w 1 &lt; w 2 &lt; · · · &lt; w m +1 , w i ∈ R and y i ∈ R . There exist W 2 ∈ R 1 × m , b 1 ∈ R m , and b 2 ∈ R such that

$$h _ { \theta } ( x ) = \frac { z _ { i } - z _ { i + 1 } } { w _ { i } - w _ { i + 1 } } ( x - w _ { i } ) + z _ { i } \quad \ \ ( 1 6 ) \quad \ \ & \quad \ \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \ \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad\ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad \ & \quad$$

for x ∈ [ w , w i i +1 ] , i = 1 2 , , · · · , m -1 and equation 16 with i = m holds in [ w m , ∞ ) where h θ ( x ) = W 2 σ ( 1 m x + b 1 ) + b 2 .

Proof. Weprove this by induction. For m = 1 , choose b 1 = -w 1 and b 1 = z 1 , then h θ ( w 1 ) = z 1 . Take W 2 = z 1 -z 2 w 1 -w 2 and we get equation 16 with i = 1 in [ w , 1 ∞ ) .

Suppose that the above result holds for m = k . Then, there exist W 2 ∈ R 1 × k , b 1 ∈ R k , and b 2 ∈ R satisfying equation 16 in [ w , w i i +1 ] for i = 1 2 , , · · · k -1 and [ w , k ∞ ) . Using this, we choose ˜ W 2 = ( W 2 , z k +1 -z k +2 w k +1 -w k +2 ) and ˜ b 1 = ( b 1 , -w k +1 ) . Then, ˜ h θ ( x ) = W 2 σ ( 1 m x + b 1 )+ b 2 satisfies equation 16 with i = k +1 in [ w k +1 , ∞ ) .

Lemma 4.6. For I ⊂ [ K ] and the consecutive partition, P ( I ) , it holds that

$$| \mathcal { P } ( I ) | \leq \min \{ | I |, | [ K ] \, \sum I | + 1 \}.$$

Proof. First, |P ( I ) | ≤ | I | directly follows from the definition of the partition.

On the other hand, let a i and b i be the end point of each block in P ([ K ] \ I ) :

$$\mathcal { P } ( [ K ] \, \smallsetminus I ) = \{ [ a _ { i }, b _ { i } ] \cap [ K ] \, \colon 1 \leq i \leq | [ K ] \, \smallsetminus I | \}.$$

Then,

$$\underset { \mathfrak { l } { q }, \, 1 4 \} } { \text{ as in} } \quad \mathcal { P } ( I ) & = \{ [ b _ { i } + 1, a _ { i + 1 } - 1 ] \cap [ K ] \, \colon 1 \leq i \leq | [ K ] \, \sum I | - 1 \} \\ \quad \, \cup \{ [ 1, b _ { i } - 1 ] \cap [ K ], [ a _ { [ K ] \vee I } + 1, K ] \cap [ K ] \}$$

$$\nu \intertext { \ \ and thus we conclude that | \mathcal { P } ( I ) | \leq | [ K ] \, \sum I | + 1. \quad \Box$$

Lemma 4.7. Under the same setting as in Theorem 4.4, we have

$$\text{and} \quad \sum _ { P \in \mathcal { P } ( [ K ] \langle T ) } \max \{ | P | - 2, 0 \} \geq \max \{ K - 3 N - 2, 0 \}.$$

In particular, J given in equation 15 satisfies

$$| J | \leq \min \{ 3 N + 2, K \}.$$

Proof. Recall that ∑ P ∈P ([ K ] \ T ) | P | = [ | K ] \ T | = K -N. Using this, we have

$$\underset { \substack { 0, \, \text{we} \\ \Box } } { \text{mea} } \quad \sum _ { P \in \mathcal { P } ( [ K ] \L T ) } \max \{ | P | - 2, 0 \} & \geq \sum _ { P \in \mathcal { P } ( [ K ] \L T ) } ( | P | - 2 ) \\ \text{where} \quad \ \ & \geq K - N - 2 | \mathcal { P } ( [ K ] \, \searrow T ) |.$$

By Lemma 4.6, the number of blocks in the partition cannot be larger than min { K -N,N +1 } .

̸

̸

̸

Proof of upper bound in Theorem 4.1: Since x i = x j for all i = j , there exists a ∈ R d satisfying x a T i = x a T j all i = j . Without the loss of generality, we assume that equation 11 holds. Then, using Theorem 4.4 and choosing W 1 = 1 m a T , there exists

̸

$$g _ { \theta } ( x ) = W _ { 2 } \sigma ( W _ { 1 } x + b _ { 1 } ) + b _ { 2 },$$

satisfying equation 3 and

$$m \leq K - 1 - \sum _ { P \in \mathcal { P } ( [ K ] \searrow T ) } \max \{ | P | - 2, 0 \}.$$

By Lemma 4.7, we conclude that m ≤ K -1 -max { K -3 N -2 0 , } = min 3 { N +1 , K - } 1 .

## 5 FTC OF 3-LAYER RELU NETWORK

Now we analyze FTC of 3-layer fully-connected neural network g θ : R d → R with ReLU activation. Note that 3-layer network can be represented as

$$g _ { \theta } ( x ) = W _ { 3 } \sigma ( W _ { 2 } \sigma ( W _ { 1 } x + b _ { 1 } ) + b _ { 2 } ) + b _ { 3 }. \quad ( 1 7 ) \quad 3. \ i$$

As before, σ is the ReLU activation and the network is parameterized by θ = [ W W W b b 1 , 2 , 3 , 1 , 2 , b 3 ] where v ∈ R d 2 , W 1 ∈ R d 1 × d , W 2 ∈ R d 2 × d 1 , W 3 ∈ R 1 × d 2 , b 1 ∈ R d 1 , b 2 ∈ R d 2 and b 3 ∈ R . Following the setting considered in the memorization capacity of 3-layer neural network [Yun et al., 2019], we consider the scenario when z i ∈ -[ 1 +1] , for all i ∈ [ K ] . For notational simplicity, we denote z i = 0 for i ∈ [ K ] \ T . Below theorem summarizes the upper/lower bound on FTC of 3-layer network.

Theorem 5.1 (FTC of 3-layer FC ReLU) . Let K ≥ 3 , T ⊆ [ K ] , | T | = N , and g be a 3-layer FC ReLU network with m neurons.

- 1. For all x i ∈ R d , z i ∈ R , i ∈ [ K ] , there exists g with m neurons satisfying equation 3 where

$$m \leq \min \{ 2 \sqrt { K } + \min \{ 2 \sqrt { K }, 3 N \}, 6 \sqrt { 3 N + 2 } \}.$$

- 2. For given x i ∈ R d , z i ∈ R , i ∈ [ K ] , suppose that equation 3 holds for some g with m neurons. Then,

$$\sqrt { 2 \min \{ 3 N, K - 2 \} + \frac { 1 } { 4 } } - \frac { 1 } { 2 } \leq m.$$

Thus, the minimum number of neurons m ⋆ is bounded as

$$\int$$

$$\sqrt { 2 \min \{ 3 N, K - 2 \} + \frac { 1 } { 4 } } - \frac { 1 } { 2 } & 6 \sqrt { 3 \, ( } \\ \leq m ^ { * } \leq \min \{ 2 \sqrt { K } + \min \{ 2 \sqrt { K }, 3 N \}, 6 \sqrt { 3 N + 2 } \} & N ^ { * } \geq$$

Remark 5. The upper bound in Theorem 5.1 directly shows that m ⋆ ≤ Θ( √ N ) . The lower bound in Theorem 5.1 indicates two facts:

- · If 3 N ≤ K -2 , then m ⋆ ≥ Θ( √ N ) ,
- · If 3 N &gt; K -2 , then m ⋆ ≥ Θ( √ K ) . Combining this with K ≥ N , we have m ⋆ ≥ Θ( √ N ) .

All in all, m ⋆ = Θ( √ N ) .

Corollary 5.2 (FTC of 3-layer FC ReLU) . For given m ∈ N , let N ⋆ be the fine-tuning capacity of a 3-layer fullyconnected ReLU network g given in equation 17 with m neurons. Then, N ⋆ is bounded as below, for different range of K :

$$1. \ I f K \leq \left \lfloor \frac { m ^ { 2 } } { 1 6 } \right \rfloor, t h$$

$$N ^ { * } = K. \quad \quad \ ( 1 8 ) \quad N$$

$$\begin{matrix} \vdots \\ \vdots \\ \end{matrix} \Big |, \, t h e n & & \\ & & N ^ { * } = &$$

$$2. \ I f \left \lfloor \frac { m ^ { 2 } } { 1 6 } \right \rfloor + 1 \leq K < \frac { m ^ { 2 } + m + 4 } { 2 }, \, t h e n$$

$$\left \lfloor \frac { m ^ { 2 } } { 1 0 8 } - \frac { 2 } { 3 } \right \rfloor \leq N ^ { * } \leq K. \text{ \quad \ \ } ( 1 9 )$$

3. If K ≥ m 2 + m +4 2 , then

$$\left \lfloor \frac { m ^ { 2 } } { 1 0 8 } - \frac { 2 } { 3 } \right \rfloor \leq N ^ { * } \leq \frac { m ^ { 2 } + m } { 6 }. \quad ( 2 0 )$$

Proof. Suppose K ≤ ⌊ m 2 16 ⌋ . By Theorem 5.1.1, for | T | = K , there exists a 3-layer fully-connected ReLU network g where the number of neurons of g is less than or equal to

$$\stackrel { \mu } { \text{er} } \min \{ 4 \sqrt { K }, 2 \sqrt { K } + 3 K, 6 \sqrt { 3 K + 2 } \} = 4 \sqrt { K } \leq m.$$

This implies that N ≥ K , and since N ≤ K always holds, we can conclude N ⋆ = K .

$$\text{Suppose } K \, \geq \, \left \lfloor \frac { m ^ { 2 } } { 1 6 } \right \rfloor + 1. \, By \, \text{Theorem } 5. 1. 1, \, \text{for } | T | \, =$$

⌊ m 2 108 -2 3 ⌋ , there exists a 3-layer fully-connected ReLU network g where the number of neurons of g is less than or equal to

$$\min \{ 4 \sqrt { K }, 6 \sqrt { 3 \left \lfloor \frac { m ^ { 2 } } { 1 0 8 } - \frac { 2 } { 3 } \right \rfloor + 2 } \} \quad \ ( 2 1 )$$

$$= 6 \sqrt { 3 \left \lfloor \frac { m ^ { 2 } } { 1 0 8 } - \frac { 2 } { 3 } \right \rfloor + 2 } \leq m, \text{ \quad \ \ } ( 2 2 )$$

where the inequality is derived from the fact that 4 √ K ≥ m for K ≥ ⌊ m 2 16 ⌋ + 1 , and 6 √ ⌊ 3 m 2 108 -2 3 ⌋ +2 ≤ 6 √ ( 3 m 2 108 -2 3 ) +2 = m . Now we can conclude that N ⋆ ≥ ⌊ m 2 108 -2 3 ⌋ .

Now we derive the upper bound on N ⋆ . If K ≥ m 2 + m +4 2 , then

$$\begin{array} { c c c } \cdots & - & z \\ n \\ m & \geq \sqrt { 2 \min \{ 3 N, K - 2 \} + \frac { 1 } { 4 } } - \frac { 1 } { 2 } \\ & \geq \sqrt { \min \{ 6 N, m ^ { 2 } + m \} + \frac { 1 } { 4 } } - \frac { 1 } { 2 } \\ & = \min \left \{ \sqrt { 6 N + \frac { 1 } { 4 } }, \, m + \frac { 1 } { 2 } \right \} - \frac { 1 } { 2 } \\ & = \min \left \{ \sqrt { 6 N + \frac { 1 } { 4 } } - \frac { 1 } { 2 }, \, m \right \}, \\ \end{array}$$

where the first inequality is from Theorem 5.1.2, and the second inequality is from K ≥ m 2 + m +4 2 . We can simplify the above inequalities as m ≥ √ 6 N + 1 4 -1 2 . Since this holds for any number of fine-tunable samples N , we have 2

Figure 5: Visualization of FTC for 3-layer network in corollary 5.2. In this figure, A = ⌊ m 2 108 -2 3 ⌋ and B = m 2 + m 6 .

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00359v2-figure-d8b977bc-cb3f-4fe0-8ff8-de5e59636c76.jpg)

$$\begin{array} { c } \text{If } \left \lfloor \frac { m ^ { 2 } } { 1 6 } \right \rfloor + 1 \leq K < \frac { m ^ { 2 } + m + 4 } { 2 }, \, \text{we use a trivial upper bound} \\ N ^ { * } \leq K, \, \text{which completes our proof.} \end{array} \quad \Box \quad \text{contai} \quad \text{$r$} \colon - \, c \end{array}$$

Fig. 5 illustrates the results in Corollary 5.2. For different ranges of K , we have either a constant N ⋆ = K , or upper/lower bounds on N ⋆ .

## 5.1 PROOF OF LOWER BOUND ON m

We follow the proof technique used in section 4.1. Since the number of minimum pieces p K ( ) provided in Eq. 9 is still valid for 3-layer neural network, we just need to check how many pieces ¯ ( ) g θ t has. As stated in the proof of Theorem 3.3 of [Yun et al., 2019], ¯ ( ) g θ t has 2 d d 1 2 + d 2 +1 pieces, where d 1 and d 2 are the number of neurons in layer 1 and 2, respectively. Thus, we have

$$\min \{ 3 N, K - 2 \} \leq 2 d _ { 1 } d _ { 2 } + d _ { 2 } \leq \frac { m ^ { 2 } } { 2 } + \frac { m } { 2 },$$

where the last inequality is from the fact that 2 d d 1 2 + d 2 is having its maximum value when d 1 = d 2 = m/ 2 . Reformulating the above inequality with respect to m completes the proof.

## 5.2 PROOF OF UPPER BOUND ON m

We can prove m ≤ U for an upper bound U by constructing a 3-layer neural network g θ having U neurons, which satisfies Eq. 3 for given N and K . Below we construct different types of neural networks satisfying the condition, where each construction gives different upper bounds U 1 = 4 √ K,U 2 = 2 √ K +3 N and U 3 = 6 √ 3 N +2 . This completes the proof of m ≤ min { U , U , U 1 2 3 } .

Figure 6: Construction of 3-layer network that achieves upper bound U 1 = 4 √ K in Sec. 5.2. This construction is directly from [Yun et al., 2019], and each neuron uses hard-tanh activation in Eq. 23. This illustration gives an example when T = { 7 } , i.e., we change the label for x 7 , while maintaining the label for other samples.

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00359v2-figure-44be2c08-a4a7-438a-bf7e-b74cffaaac02.jpg)

̸

Proof of m ≤ 4 √ K : Recall the neural network g θ constructed in the proof of Theorem 3.1 of [Yun et al., 2019], containing √ K neurons in both 1st layer and 2nd layer. See Fig. 6 for the illustration of such network, when K = 16 and N = 1 , where the index of fine-tuning sample is T = 7 { } . In such case z 7 = 0 from the definition of T . Each box (node) in the figure is a neuron, where the curve inside the box represents the activation function of the neuron. In this figure, each neuron uses hard-tanh activation defined as

$$\sigma _ { H } ( x ) = \begin{cases} - 1, & t \leq - 1 \\ t, & - 1 < t < + 1 \\ + 1, & t \geq + 1, \end{cases} \quad ( 2 3 )$$

where [ -1 1] , is the non-clipping region of σ H , and [ -1 1] , c is the clipping region of σ H . Note that the digit i in the box represents the location where the feature x i for the i -th sample is mapped to. For example, for the first neuron of layer 1, we have α 1 1 ( x i ) ∈ -[ 1 1] , for i ∈ { 1 2 3 4 , , , } and α 1 1 ( x i ) &gt; 1 for i ∈ { 5 6 , , · · · , 16 } , where

$$\alpha _ { j } ^ { l } ( x ) = W _ { l, j } x + b _ { l, j } \text{ \quad \ \ } ( 2 4 )$$

is the input value of node j in layer l , when the input for the network g θ is given as x . Here, the weight matrix and the bias for layer 1 are denoted by W 1 = [ W T 1 1 , ; · · · ; W T 1 , √ K ] and b 1 = [ b 1 1 , , · · · , b 1 , √ K ] , respectively. Given target { z i } K i =1 , the proof of Theorem 3.1 of [Yun et al., 2019] specified parameters θ = [ W W W b b 1 , 2 , 3 , 1 , 2 , b 3 ] satisfying g θ ( x i ) = z i for all i ∈ [ K . ] Assigning z i = 0 for i ∈ [ K ] \ T and reusing these parameters is enough to satisfy the desired condition for fine-tuning in Eq. 3. Note that this network uses 2 √ K neurons with hard-tanh activations, which can be converted to a ReLU neural network with 4 √ K neurons, using the fact that one hard-tanh neuron can be expressed with two ReLU neurons. This directly proves

Figure 7: Construction of 3-layer network that achieves upper bound U 2 = 2 √ K +3 N in Sec. 5.2. This illustration gives an example when T = { 7 } .

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00359v2-figure-799686d3-52d8-449d-af41-e3e6133f16fe.jpg)

that 4 √ K ReLU neurons are sufficient for changing the labels of N ≤ K samples.

̸

Proof of m ≤ 2 √ K +3 N : We construct a 3-layer neural network with U 2 = 2 √ K +3 N neurons which successfully fine-tunes N samples. Fig. 7 illustrates the example of such construction when K = 16 and N = 1 . Here, we assumed T = { 7 } , i.e., the label for 7-th sample is fine-tuned, but similar proof can be applied to arbitrary T with | T | = N = 1 . Here, our goal is to construct g θ satisfying g θ ( x 7 ) = z 7 = 0 and g θ ( x i ) = 0 for all i = 7 . Our basic idea is, to follow the construction in Fig. 6, except the activation used in layer 2. The activation in layer 2 is defined as

̸

$$\sigma _ { B } ( t ) = \begin{cases} 0, & t \notin [ z _ { 7 } - \delta, z _ { 7 } + \delta ] & \quad \text{i} \\ \frac { z _ { 7 } } { \delta } ( t - z _ { 7 } + \delta ), & t \in [ z _ { 7 } - \delta, z _ { 7 } ) & \quad i \\ - \frac { z _ { 7 } } { \delta } ( t - z _ { 7 } - \delta ), & t \in [ z _ { 7 }, z _ { 7 } + \delta ) & \quad \text{s} \\. &. &. \end{cases}$$

̸

̸

for arbitrary δ &lt; min i = j | z i -z j | 2 , which is having a small bump near z 7 as in Fig. 7. Among √ K hard-tanh neurons in layer 2 in Fig. 6, we only choose the neuron containing z 7 (the non-zero target label) in the non-clipping region of the activation, e.g., the second neuron of layer 2. Given that W 2 is the weight matrix for 2nd layer in the construction of Fig. 6, the weight matrix for 2nd layer in the construction of Fig. 7 is defined as ˜ W 2 := W 2 2 , , the 2nd row of W 2 . Then, the overall network looks like g θ ( x ) = σ B ( W 2 2 , σ H ( W x 1 + b 1 ) + b 2 ) , which satisfies g θ ( x 7 ) = z 7 and g θ ( x i ) = 0 for all i = 7 . Note that the activation σ B with 4 pieces can be constructed by 3 ReLU neurons. Consider constructing g θ by adding new neurons (with σ B activation) in layer 2 for each sample we want to fine-tune, which allocates total 3 N ReLU neurons in layer 2. Since layer 1 (as in Fig. 6) contains 2 √ K ReLU neurons, one can confirm that our construction contains 2 √ K +3 N ReLU neurons.

Proof of m ≤ 6 √ 3 N +2 : It is worth nothing that some techniques developed for showing m ≤ 4 N +4 (shown in

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00359v2-figure-c07e1830-a0ef-4cfa-9c5b-b19ae2cb6f56.jpg)

𝑾𝑾1

𝑾𝑾2

Figure 8: The construction of 3-layer network achieving the upper bound U 3 = 6 √ 3 N +2 in Sec. 5.2. Here, we consider the case when K = 16 , N = 3 and T = 2 4 9 { , , } .

Appendix) are used to prove m ≤ 6 √ 3 N +2 . Thus, we refer to some equations in Appendix during the proof.

We construct a neural network g θ with 6 √ 3 N +2 ReLU neurons, which fine-tunes N samples. For simplicity, here we provide an example construction when K = 16 , N = 3 , and T = 2 4 9 { , , } . By using the definition of J in Eq. 14, we have J = { 1 2 3 4 5 8 9 10 16 , , , , , , , , } . We will now construct a 3-layer neural network g θ satisfying

$$g _ { \theta } ( x _ { i } ) = z _ { i }, \ \ i \in J, \quad \ \ ( 2 5 )$$

$$g _ { \theta } ( x _ { i } ) = 0, \ \ i \notin J, \quad \quad \quad ( 2 6 )$$

which is illustrated in Fig. 8. Note that Eq. 25 can be easily proved by fitting the network using the samples x i with i ∈ J . In the rest of the proof, we will show that for such g θ satisfying Eq. 25, we can prove Eq. 26. As an example, we will only show g θ ( x 6 ) = 0 , but a similar proof technique can be applied to arbitrary x i with i / J ∈ .

We construct the first layer by only using samples x i with i ∈ J . We partition the | J | samples into √ | J | groups, following the trick used in [Yun et al., 2019] for 3-layer network. Let us denote the first index of j -th group as s min j and the last index of j -th group as s max j . In other words, J is decomposed into √ | J | groups as J = { s min 1 , · · · , s max 1 , } ∪ · · · ∪ { s min √ | J | , · · · , s max √ | J | } .

Without loss of generality, we can assume that samples are ordered as v T x 1 &lt; v T x 2 &lt; · · · &lt; v T x K for some v . Let c i := v T x i and define c 0 = c 1 -ϵ , c K +1 = c K + ϵ for arbitrary ϵ &gt; 0 . Then, we choose W 1 , b 1 as in Eq. 28, using v and ϵ defined above.

Here, we focus on the relationship between the outputs of layer 1, when the neural network inputs are x 5 , x 6 , x 8 , respectively. From the definition of c i , we have c 6 ∈ ( c 5 , c 8 ) . Using Eq. 24 and Eq. 28, we have α 1 j ( x 6 ) ∈ ( α 1 j ( x 5 ) , α 1 j ( x 8 )) , meaning that the input α 1 j of layer 1 (for x 6 ) is bounded by α 1 j for x 5 and α 1 j for x 8 . After passing it through the ReLU activation, we also have

$$\beta _ { j } ^ { 1 } ( x _ { 6 } ) \in ( \beta _ { j } ^ { 1 } ( x _ { 5 } ), \beta _ { j } ^ { 1 } ( x _ { 8 } ) ), \quad \quad ( 2 7 ) \quad.$$

for all j ∈ { 1 , · · · , √ J } using the monotonicity of ReLU. Kore precisely, we have β 1 1 ( x 6 ) = +1 , - ≤ 1 β 1 2 ( x 6 ) ≤ +1 , and β 1 3 ( x 6 ) = -1 . This is illustrated in the first layer in Fig. 8. Now we move to the construction of the second layer. Recall that the main idea of constructing W 2 , b 2 is using the linear system in Eq. 33. Using Eq.32 and the fact that we can set all elements of W 2 as positive (as shown in [Yun et al., 2019]), Eq. 27 implies α 2 j ( x 6 ) ∈ ( α 2 j ( x 5 ) , α 2 j ( x 8 )) for all j ∈ { 1 , · · · , √ J } . Finally, we set the activation function of layer 2 as

$$\sigma _ { L } ( t ) = \begin{cases} t, & \text{if $|t|\leq 1$}, \\ 0, & \text{if $|t|\geq 1$} \end{cases}$$

and arbitrarily increase λ such that β 2 j ( x 6 ) = 0 . Then, the output of the network g θ ( x ) = σ L ( W 2 ( σ H ( W x 1 + b 1 )) + b 2 ) satisfies g θ ( x 6 ) = 0 .

Now the question is, what is the upper bound on | J | ? Recall that Lemma 4.7 guarantees that | J | ≤ 3 N +2 . Since σ H and σ L can be represented by 2 ReLUs and 4 ReLUs, respectively, 2 √ 3 N +2 + 4 √ 3 N +2 = 6 √ 3 N +2 ReLU neurons are sufficient for our 3-layer network construction.

## 6 EXTENSION TO OTHER NEURAL NETWORKS

For deeper neural networks, a lower bound on N can be obtained in terms of the maximum width d , the number of layers L , and the number of pre-trained samples K .

Proposition 6.1. For L ≥ 4 , K ≥ 3 , T ⊆ [ K ] , | T | = N , there exists an L -layer ReLU network with maximum width d satisfying equation 3 and

$$d \leq 4 \min \left \{ \sqrt { \frac { 3 N } { \sqrt { \lfloor \frac { L - 1 } { 2 } \rfloor } } + 5 }, \sqrt { K } \right \} + 2.$$

The main challenge for proving Proposition 6.1 lies in constructing a suitable neural network, which can be addressed by utilizing our 3-layer network from Section 5 and the construction idea provided in Figure 2 of [Yun et al., 2019]. See Appendix B for the proof of Proposition 6.1.

## 7 EXPERIMENTS

In this section, we provide experimental results on a synthetic dataset, which supports our theoretical results. The experimental setup is as follows. We first randomly generate K samples D = { ( x i , y i ) } K i =1 where the feature

Fine-Tuning Performance on Synthetic Data

Figure 9: Fine-tuning loss ℓ FT computed for a network trained on a synthetic dataset, for various N and m . Here, the number of data points used for pre-training is set to K = 1000 . As shown in the orange line, the number of neurons m required in the fine-tuning network to achieve a small loss ℓ FT grows in the order of Θ( √ N ) , the square root of the number of modified samples. This result coincides with our theoretical result in Theorem 5.1.

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00359v2-figure-ab1dbee6-182a-4509-a6d4-677be7280442.jpg)

and the label of i -th sample have the following distributions: x i ∼ N (0 , I d ) and y i ∼ Unif [ -1 1] , , where the feature dimension is d = 10 . Then, we train a network ReLU network f that fits the dataset D , i.e., equation 1 holds, thus having zero mean-squared-error (MSE) loss ℓ = 1 K ∑ K i =1 ( f ( x i ) -y i ) 2 . Considering the fine-tuning scenario, we construct another dataset D ′ = ( { x i , y ′ i ) } K i =1 as follows. We first initialize D ′ = D . Then, we randomly choose N out of K samples in D ′ , and re-define the label of the N samples as y ′ i ∼ Unif [ -1 1] , . Finally, we implement the fine-tuning process. Following our additive fine-tuning scenario, we freeze f and train a 3-layer ReLU network g θ with m neurons, in a way that f + g θ fits the new dataset D ′ . We define the fine-tuning loss as ℓ FT = 1 K ∑ K i =1 ( f ( x i ) + g θ ( x i ) -y ′ i ) 2 .

Figure 9 shows the fine-tuning loss ℓ FT for different m and N . As expected, for a given N , the fine-tuning loss decreases as m increases. For each N , the yellow line in the figure shows the minimum m satisfying ℓ FT ( m,N ) ≤ 0 04 . . This yellow line indicates that the required number of neurons to achieve small fine-tuning loss follow the tendency of Θ( √ N ) shown in the red line in the figure, which coincides with our theoretical result in Theorem 5.1.

## 8 CONCLUSION

We introduced Fine-Tuning Capacity (FTC), a generalization of memorization capacity concept for fine-tuning applications. This concept is defined to provide theoretical view on current paradigm of fine-tuning large pre-trained models. As an initial step towards analyzing FTC, we focused on the additive fine-tuning scenario where a side network is added to the frozen pre-trained network. We obtained upper/lower bounds on FTC for shallow ReLU networks. For 2-layer network, we showed that fine-tuning N samples is possible by using ReLU networks with m = Θ( N ) neurons, irrespective of the size of the pre-trained network and the number of total samples K used during pre-training. For

3-layer network, the required amount of neurons reduces to m = Θ( √ N ) , for practical scenarios where the number of samples N we want to change labels is far less than the number of total samples K used for pre-training.

## Acknowledgements

JS acknowledges the support of the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT) No. RS-2024-00345351. DK was partially supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT) (No. RS-2023-00252516) and the POSCO Science Fellowship of POSCO TJ Park Foundation. KL was supported by the NSF Award CCF-2339978 and a grant from FuriosaAI.

## References

Andrew R Barron. Universal approximation bounds for superpositions of a sigmoidal function. IEEE Transactions on Information theory , 39(3):930-945, 1993.

Eric B Baum. On the capabilities of multilayer perceptrons. Journal of complexity , 4(3):193-215, 1988.

Rishi Bommasani, Drew A Hudson, Ehsan Adeli, Russ Altman, Simran Arora, Sydney von Arx, Michael S Bernstein, Jeannette Bohg, Antoine Bosselut, Emma Brunskill, et al. On the opportunities and risks of foundation models. arXiv preprint arXiv:2108.07258 , 2021.

Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems , 33:1877-1901, 2020.

Jin Cao, Chandana Satya Prakash, and Wael Hamza. Attention fusion: a light yet efficient late fusion mechanism for task adaptation in nlu. In Findings of the Association for Computational Linguistics: NAACL 2022 , pages 857-866, 2022.

Nicholas Carlini, Daphne Ippolito, Matthew Jagielski, Katherine Lee, Florian Tramer, and Chiyuan Zhang. Quantifying memorization across neural language models. arXiv preprint arXiv:2202.07646 , 2022.

Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, et al. Palm: Scaling language modeling with pathways. arXiv preprint arXiv:2204.02311 , 2022.

George Cybenko. Approximation by superpositions of a sigmoidal function. Mathematics of control, signals and systems , 2(4):303-314, 1989.

Simon S Du, Wei Hu, Sham M Kakade, Jason D Lee, and Qi Lei. Few-shot learning via learning the representation, provably. arXiv preprint arXiv:2002.09434 , 2020.

Matthias Englert and Ranko Lazic. Adversarial reprogramming revisited. Advances in Neural Information Processing Systems , 35:28588-28600, 2022.

Cheng Fu, Hanxian Huang, Xinyun Chen, Yuandong Tian, and Jishen Zhao. Learn-to-share: A hardware-friendly transfer learning framework exploiting computation and parameter sharing. In International Conference on Machine Learning , pages 3469-3479. PMLR, 2021.

Ken-Ichi Funahashi. On the approximate realization of continuous mappings by neural networks. Neural networks , 2(3):183-192, 1989.

Angeliki Giannou, Shashank Rajput, and Dimitris Papailiopoulos. The expressive power of tuning only the norm layers. arXiv preprint arXiv:2302.07937 , 2023.

Boris Hanin and Mark Sellke. Approximating continuous functions by relu nets of minimal width. arXiv preprint arXiv:1710.11278 , 2017.

Moritz Hardt and Tengyu Ma. Identity matters in deep learning. arXiv preprint arXiv:1611.04231 , 2016.

Junxian He, Chunting Zhou, Xuezhe Ma, Taylor BergKirkpatrick, and Graham Neubig. Towards a unified view of parameter-efficient transfer learning. arXiv preprint arXiv:2110.04366 , 2021.

Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks are universal approximators. Neural networks , 2(5):359-366, 1989.

Neil Houlsby, Andrei Giurgiu, Stanislaw Jastrzebski, Bruna Morrone, Quentin De Laroussilhe, Andrea Gesmundo, Mona Attariyan, and Sylvain Gelly. Parameter-efficient transfer learning for nlp. In International Conference on Machine Learning , pages 2790-2799. PMLR, 2019.

Edward J Hu, Yelong Shen, Phillip Wallis, Zeyuan AllenZhu, Yuanzhi Li, Shean Wang, Lu Wang, and Weizhu Chen. Lora: Low-rank adaptation of large language models. arXiv preprint arXiv:2106.09685 , 2021.

Guang-Bin Huang. Learning capability and storage capacity of two-hidden-layer feedforward networks. IEEE transactions on neural networks , 14(2):274-281, 2003.

Guang-Bin Huang and Haroon A Babri. Upper bounds on the number of hidden neurons in feedforward networks with arbitrary bounded nonlinear activation functions. IEEE transactions on neural networks , 9(1):224-229, 1998.

Daphne Ippolito, Florian Tramèr, Milad Nasr, Chiyuan Zhang, Matthew Jagielski, Katherine Lee, Christopher A Choquette-Choo, and Nicholas Carlini. Preventing verbatim memorization in language models gives a false sense of privacy. arXiv preprint arXiv:2210.17546 , 2022.

Patrick Kidger and Terry Lyons. Universal approximation with deep narrow networks. In Conference on learning theory , pages 2306-2327. PMLR, 2020.

Junghwan Kim, Michelle Kim, and Barzan Mozafari. Provable memorization capacity of transformers. In International Conference on Learning Representation (ICLR) , 2023.

Zhou Lu, Hongming Pu, Feicheng Wang, Zhiqiang Hu, and Liwei Wang. The expressive power of neural networks: A view from the width. Advances in neural information processing systems , 30, 2017.

Liam Madden. Memory capacity of three-layer neural networks with non-polynomial activations. arXiv preprint arXiv:2405.13738 , 2024.

Liam Madden and Christos Thrampoulidis. Memory capacity of two layer neural networks with smooth activations. SIAM Journal on Mathematics of Data Science , 6(3): 679-702, 2024.

Liam Madden, Curtis Fox, and Christos Thrampoulidis. Upper and lower memory capacity bounds of transformers for next-token prediction. arXiv preprint arXiv:2405.13718 , 2024.

Sadhika Malladi, Alexander Wettig, Dingli Yu, Danqi Chen, and Sanjeev Arora. A kernel-based view of language model fine-tuning. In International Conference on Machine Learning , pages 23610-23641. PMLR, 2023.

Andreas Maurer, Massimiliano Pontil, and Bernardino Romera-Paredes. The benefit of multitask representation learning. Journal of Machine Learning Research , 17 (81):1-32, 2016.

Quynh Nguyen and Matthias Hein. Optimization landscape and expressivity of deep cnns. In International conference on machine learning , pages 3730-3739. PMLR, 2018.

R OpenAI. Gpt-4 technical report. arXiv , pages 230308774, 2023.

Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. Training language models to follow instructions with human feedback. Advances in Neural Information Processing Systems , 35:27730-27744, 2022.

Samet Oymak, Ankit Singh Rawat, Mahdi Soltanolkotabi, and Christos Thrampoulidis. On the role of attention in prompt-tuning. arXiv preprint arXiv:2306.03435 , 2023.

Sejun Park, Chulhee Yun, Jaeho Lee, and Jinwoo Shin. Minimum width for universal approximation. arXiv preprint arXiv:2006.08859 , 2020.

Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. Learning transferable visual models from natural language supervision. In International conference on machine learning , pages 8748-8763. PMLR, 2021.

Shashank Rajput, Kartik Sreenivasan, Dimitris Papailiopoulos, and Amin Karbasi. An exponential improvement on the memorization capacity of deep threshold networks, 2021.

Aditya Ramesh, Prafulla Dhariwal, Alex Nichol, Casey Chu, and Mark Chen. Hierarchical text-conditional image generation with clip latents. arXiv preprint arXiv:2204.06125 , 1(2):3, 2022.

Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. Llama 2: Open foundation and fine-tuned chat models. arXiv preprint arXiv:2307.09288 , 2023.

Nilesh Tripuraneni, Michael Jordan, and Chi Jin. On the theory of transfer learning: The importance of task diversity. Advances in neural information processing systems , 33:7852-7862, 2020.

Gal Vardi, Gilad Yehudai, and Ohad Shamir. On the optimal memorization power of relu neural networks. arXiv preprint arXiv:2110.03187 , 2021.

Roman Vershynin. Memory capacity of neural networks with threshold and relu activations, 2020.

Jingfeng Wu, Difan Zou, Vladimir Braverman, Quanquan Gu, and Sham Kakade. The power and limitation of pretraining-finetuning for linear regression under covariate shift. Advances in Neural Information Processing Systems , 35:33041-33053, 2022.

Chulhee Yun, Suvrit Sra, and Ali Jadbabaie. Small relu networks are powerful memorizers: a tight analysis of memorization capacity. Advances in Neural Information Processing Systems , 32, 2019.

Elad Ben Zaken, Shauli Ravfogel, and Yoav Goldberg. Bitfit: Simple parameter-efficient fine-tuning for transformer-based masked language-models. arXiv preprint arXiv:2106.10199 , 2021.

Shenglai Zeng, Yaxin Li, Jie Ren, Yiding Liu, Han Xu, Pengfei He, Yue Xing, Shuaiqiang Wang, Jiliang Tang, and Dawei Yin. Exploring memorization in fine-tuned language models. arXiv preprint arXiv:2310.06714 , 2023.

Yuchen Zeng and Kangwook Lee. The expressive power of low-rank adaptation. arXiv preprint arXiv:2310.17513 , 2023.

- Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint arXiv:1611.03530 , 2016.

Jeffrey O Zhang, Alexander Sax, Amir Zamir, Leonidas Guibas, and Jitendra Malik. Side-tuning: a baseline for network adaptation via additive side networks. In Computer Vision-ECCV 2020: 16th European Conference, Glasgow, UK, August 23-28, 2020, Proceedings, Part III 16 , pages 698-714. Springer, 2020.

Susan Zhang, Stephen Roller, Naman Goyal, Mikel Artetxe, Moya Chen, Shuohui Chen, Christopher Dewan, Mona Diab, Xian Li, Xi Victoria Lin, et al. Opt: Open pretrained transformer language models. arXiv preprint arXiv:2205.01068 , 2022.

## Memorization Capacity for Additive Fine-Tuning (Supplementary Material)

Jy-yong Sohn * 1

Dohyun Kwon * 2,3

Seoyeon An 1

Kangwook Lee 4

- 1 Department of Statistics and Data Science, Yonsei University, Republic of Korea 2 Department of Mathematics, University of Seoul, Republic of Korea
- 3 Center for AI and Natural Sciences, Korea Institute for Advanced Study, Republic of Korea

4 Department of Electrical and Computer Engineering, University of Wisconsin-Madison, WI, USA

## A PROOF OF m ≤ 4 N +4 (DEFERRED FROM SEC. 5.2)

̸

We construct a 3-layer neural network g θ with 4 N +4 ReLU neurons which fine-tune N samples. Note that we can find v such that v T x i = v T x j for all i = j , since we assume x i = x j for all i = j . Without loss of generality, we order samples such that v T x 1 &lt; v T x 2 &lt; · · · &lt; v T x K . Let c i := v T x i and define c 0 = c 1 -ϵ , c K +1 = c K + ϵ for arbitrary ϵ &gt; 0 . Recall that the indices for the samples we want to fine-tune is denoted by T = { T , 1 · · · , T N } . We define dummy indices T 0 = 1 and T N +1 = K . Consider 2 N +1 groups of disjoint indices,

̸

̸

̸

$$s _ { 1 } = \{ T _ { 0 }, \cdots, T _ { 1 } - 1 \}, \quad s _ { 2 } = \{ T _ { 1 } \}, \\ s _ { 3 } = \{ T _ { 1 } + 1, \cdots, T _ { 2 } - 1 \}, \quad s _ { 4 } = \{ T _ { 2 } \}, \\ \cdots, \quad s _ { 2 N } = \{ T _ { N } \}, \\ s _ { 2 N + 1 } = \{ T _ { N } + 1, \cdots, T _ { N + 1 } \},$$

where group s 1 is empty when T 1 = 1 , and group s 2 N +1 is empty when T N = K . We denote the maximum/minimum element of set s j as s max j and s min j , respectively, i.e., s max j = max s j and s min j = min s j . We place 2 N +1 neurons on layer 1, and define parameters for layer 1 as

$$W _ { 1, j } & = ( - 1 ) ^ { j - 1 } \frac { 4 } { c _ { s _ { j } ^ { \max } } + c _ { s _ { j + 1 } ^ { \min } } - c _ { s _ { j - 1 } ^ { \max } } - c _ { s _ { j } ^ { \min } } } v ^ { T }$$

$$b _ { 1, j } = ( - 1 ) ^ { j } \frac { \ell ^ { 2 + \ell } _ { s _ { j } ^ { \max } } + c _ { s _ { j + 1 } ^ { \min } } + c _ { s _ { j - 1 } ^ { \max } } + c _ { s _ { j } ^ { \min } } } { c _ { s _ { j } ^ { \max } } + c _ { s _ { j + 1 } ^ { \min } } - c _ { s _ { j - 1 } ^ { \max } } - c _ { s _ { j } ^ { \min } } }$$

for all j = 1 , · · · , 2 N +1 . Under such setting, it can be easily checked that

$$\alpha _ { j } ^ { 1 } ( x _ { i } ) & \in [ - 1, 1 ] \quad \text{for $i\in s_{j}$} \\ \alpha _ { j } ^ { 1 } ( x _ { i } ) & \not \in [ - 1, 1 ] \quad \text{for $i\not\in s_{j}$}$$

for all j ∈ [2 N +1] , where α l j ( x ) defined in Eq. 24 is the input value of node j in layer l , when the input for the network is x . Fig. 10 shows the example of such construction, when K = 16 , N = 2 and T = { 4 7 , } . In such case, we have 2 N +1 = 5 disjoint groups:

$$s _ { 1 } = \{ 1, 2, 3 \}, \quad s _ { 2 } & = \{ 4 \}, \quad s _ { 3 } = \{ 5, 6 \}, \\ s _ { 4 } & = \{ 7 \}, \quad s _ { 5 } = \{ 8, 9, \cdots, 1 6 \}.$$

As in Fig. 10, the input of j -th neuron lie in the non-clipping region α j 1 ( x i ) ∈ -[ 1 1] , when i ∈ s j . For example, the first neuron ( j = 1 ) in the first layer has α 1 1 ( x i ) ∈ -[ 1 1] , for i ∈ s 1 = 1 2 3 { , , } .

* Equal Contribution

* Equal Contribution

Figure 10: The construction of 3-layer network achieving upper bound U 3 = 4 N +4 in Sec. 5.2. Here, we consider the case when K = 16 , N = 2 and T = 4 7 { , } .

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00359v2-figure-3331cd3b-adf1-4c01-9c99-0992d496f700.jpg)

Now we construct layer 2 as below. Let S = ∪ 2 N +1 j =1 { s min j } be the index set containing the minimum index of each group s j for j ∈ [2 N +1] , which is S = { 1 4 5 7 8 , , , , } in the above example. Our goal is to construct W 2 ∈ R 2 N +1 and b 2 ∈ R such that a single node in layer 2 locates (1) { x i } i ∈ S to the desired target z i , and (2) { x i } i/S ∈ to the clipping region [ -1 1] , c . In other words, our desired conditions are

$$\alpha _ { 1 } ^ { 2 } ( x _ { i } ) = z _ { i }, \quad \forall i \in S,$$

$$\alpha _ { 1 } ^ { 2 } ( x _ { i } ) \in [ - 1, 1 ] ^ { c }, \quad \forall i \notin S.$$

Note that the input of the first node in the second layer is represented as

$$\alpha _ { 1 } ^ { 2 } ( x _ { i } ) = \sum _ { j = 1 } ^ { 2 N + 1 } W _ { 2, j } \beta _ { j } ^ { 1 } ( x _ { i } ) + b _ { 2 }$$

where W 2 = [ W 2 1 , ; · · · ; W 2 2 , N +1 ] and

$$\beta _ { j } ^ { 1 } ( x _ { i } ) = \sigma _ { H } ( \alpha _ { j } ^ { 1 } ( x _ { i } ) )$$

is the output of node j in layer 1, when the input to the network is x i . Thus, the first condition in Eq. 30 can be represented as a linear system

$$K \begin{bmatrix} W _ { 2 } \\ b _ { 2 } \end{bmatrix} = \begin{bmatrix} z _ { i _ { 1 } } \\ \vdots \\ z _ { i _ { 2 N + 1 } } \end{bmatrix}$$

where i k for k ∈ [2 N +1] is defined the as the elements of S = { i 1 , · · · , i 2 N +1 } and

$$K = \begin{bmatrix} \beta _ { 1 } ^ { 1 } ( x _ { i _ { 1 } } ) & \dots & \beta _ { 2 N + 1 } ^ { 1 } ( x _ { i _ { 1 } } ) & 1 \\ \vdots & \ddots & \vdots & \vdots \\ \beta _ { 1 } ^ { 1 } ( x _ { i _ { 2 N + 1 } } ) & \dots & \beta _ { 2 N + 1 } ^ { 1 } ( x _ { i _ { 2 N + 1 } } ) & 1 \end{bmatrix}.$$

In our above example, we have

$$K = \begin{bmatrix} \beta _ { 1 } ^ { 1 } ( x _ { 1 } ) & + 1 & - 1 & + 1 & - 1 & 1 \\ + 1 & \beta _ { 2 } ^ { 1 } ( x _ { 4 } ) & - 1 & + 1 & - 1 & 1 \\ + 1 & - 1 & \beta _ { 3 } ^ { 1 } ( x _ { 5 } ) & + 1 & - 1 & 1 \\ + 1 & - 1 & + 1 & \beta _ { 4 } ^ { 1 } ( x _ { 7 } ) & - 1 & 1 \\ + 1 & - 1 & + 1 & - 1 & \beta _ { 5 } ^ { 1 } ( x _ { 8 } ) & 1 \end{bmatrix}$$

Using a similar technique used in [Yun et al., 2019], this matrix K ∈ R (2 N +1) × (2 N +2) satisfies two conditions:

$$& ( 1 ) \text{ rank} ( K ) = 2 N + 1, \\ & ( 2 ) \text{ } \exists \nu = [ \nu _ { 1 }, \cdots, \nu _ { 2 N + 2 } ] \in \text{null} ( K ) \\ & \quad \text{ such that } \nu _ { i } > 0 \quad \forall i \in [ 2 N + 1 ].$$

$$\begin{smallmatrix} \\ \end{smallmatrix}$$

Thus, the linear system in Eq. 33 has infinitely many solution in the form of

$$\begin{bmatrix} W _ { 2 } \\ b _ { 2 } \end{bmatrix} = \mu + \lambda \nu$$

for any scalar λ and a particular solution µ . With the logic used in the proof of Lemma B.1 in [Yun et al., 2019], we can scale λ sufficiently such that the second condition in Eq. 30 holds. Thus, by using such weight W 2 and bias b 2 , the input of layer 2 looks like in Fig. 10. Let the neuron in layer 2 has activation function

$$\sigma _ { T } ( t ) = \begin{cases} t, & \text{if $t < 1$} \\ - \frac { 1 } { \delta } ( t - 1 - \delta ), & \text{if $1 \leq t < 1 + \delta$} \\ 0, & \text{if $t \geq 1 + \delta$} \end{cases}$$

Then, the output of the network satisfies

$$g _ { \theta } ( \boldsymbol x _ { i } ) = \begin{cases} z _ { i }, & i \in T \\ 0, & i \in [ K ] \, \bar { \ } T \end{cases}$$

by using the definition of σ T and Eq. 30. Note that the first layer of this construction uses 2 N +1 neurons with σ H activation, and the second layer uses 1 neuron with σ T activation. Since σ H and σ T can be converted into 2 ReLU neurons, our construction use total 4 N +4 neurons, which completes the proof.

## B PROOF OF PROPOSITION 6.1

Recall the 3-layer network illustrated in Figure 8. For given T ⊂ [ K ] , let us denote this 3-layer network satisfying equation 3 by g θ,T which has maximum width 4 min { √ 3 | T | +2 , √ K } . In what follows, we construct an L -layer network based on g θ,T .

We partition T into ⌊ L -1 2 ⌋ subsets: T , T 1 2 , · · · , T ⌊ L -1 2 ⌋ satisfying | T i | ≤ | T / | ⌊ L -1 2 ⌋ +1 for all i . It can be easily seen that g θ,T 1 ( x ) + g θ,T 2 ( x ) + · · · + g θ,T ⌊ L -1 2 ⌋ ( x ) satisfies equation 3. Using the construction idea provided in Figure 2 of [Yun et al., 2019], the above function can be represented as an L -layer network, which has a maximum width less than or equal to

$$\max _ { i } \{ 4 \min \{ \sqrt { 3 | T _ { i } | + 2 }, \sqrt { K } \} + 2 \},$$

and we conclude.

$$g _ { \theta } ( x ) = \sigma _ { T } ( W _ { 2 } ( \sigma _ { H } ( W _ { 1 } x + b _ { 1 } ) ) + b _ { 2 } ) = \sigma _ { T } ( \alpha _ { 1 } ^ { 2 } ( x ) )$$
Jy-yong Sohn Dohyun Kwon Seoyeon An Kangwook Lee
Memorization Capacity for Additive Fine-Tuning with Small ReLU Networks
Fine-tuning large pre-trained models is a common practice in machine learning
applications, yet its mathematical analysis remains largely unexplored. In this
paper, we study fine-tuning through the lens of memorization capacity. Our new
measure, the Fine-Tuning Capacity (FTC), is defined as the maximum number of
samples a neural network can fine-tune, or equivalently, as the minimum number
of neurons ($m$) needed to arbitrarily change $N$ labels among $K$ samples
considered in the fine-tuning process. In essence, FTC extends the memorization
capacity concept to the fine-tuning scenario. We analyze FTC for the additive
fine-tuning scenario where the fine-tuned network is defined as the summation
of the frozen pre-trained network $f$ and a neural network $g$ (with $m$
neurons) designed for fine-tuning. When $g$ is a ReLU network with either 2 or
3 layers, we obtain tight upper and lower bounds on FTC; we show that $N$
samples can be fine-tuned with $m=\Theta(N)$ neurons for 2-layer networks, and
with $m=\Theta(\sqrt{N})$ neurons for 3-layer networks, no matter how large $K$
is. Our results recover the known memorization capacity results when $N = K$ as
a special case.