###### tags: `PaperReview`
[Paper Link](https://arxiv.org/pdf/2211.15583)
# On the Effectiveness of Parameter-Efficient Fine-Tuning

> Zihao Fu, Haoran Yang, Anthony Man-Cho So, Wai Lam, Lidong Bing, Nigel Collier
>
> Language Technology Lab, University of Cambridge
> The Chinese University of Hong Kong
> DAMO Academy, Alibaba Group
> AAAI 2023

## Introduction
- Fine-tuning pre-trained models is effective in NLP tasks but is parameter inefficient as it yields a new model for each task.
- Methods that only fine-tune a small portion of parameters while keeping most shared are effective and stable, but **selecting the suitable parameters remains a challenging problem**.
- Existing methods are categorized into **random, rule-based, and projection-based approaches**, all of which are sparse fine-tuned models.
- Sparsity imposes regularization and upper bounds of stability, leading to better generalization capabilities.
- The proposed **Second-order Approximation Method (SAM)** optimizes the approximation function for better parameter tuning and outperforms many strong baseline models in experiments.

## Unified View of Parameter Efficient Fine-tuning
### Sparse Fine-tuned Model
- Definition 1: *(p-Sparse Fine-tuned Model). Given a pre-trained model $\mathcal{M}^0$ with parameters $\theta^0$, if a fine-tuned model $\mathcal{M}$ with parameters $\theta$ has the same structure as $\mathcal{M}^0$ such that $\left\|\theta-\theta^0\right\|_0 \leq p \text{ dim}(\theta)$; $p \in (0,1)$, we say the model $\mathcal{M}$ is a p-sparse fine-tuned model with the sparsity p.*
- For a fixed sparsity coefficient $p$, the sparse fine-tuned model is trying to solve this problem:
$$
\begin{gathered}
\min _{\Delta \theta, M} \mathcal{L}\left(\theta^0+M \Delta \theta\right) \\
\text { s.t. } \quad\|M\|_0=\lfloor m p\rfloor ; \quad M_{i j}=0, \forall i \neq j ; \quad M_{i i} \in\{0,1\},
\end{gathered}(1)
$$
- $\lfloor · \rfloor \Longrightarrow$ floor function
- $m = dim(\theta)\Longrightarrow$ parameter number
- $M \in \{0, 1\}^{m\times{m}} \Longrightarrow$ parameter mask matrix with diagonal equal 0 or 1 while other elements are 0
- $\mathcal{L} \Longrightarrow$ loss function

- Definition 2: (Equivalent Model). Given a pre-trained model $\mathcal{M}^0$ with parameters $\theta^0$, we say that a model $\tilde{\mathcal{M}^0}$ with parameters $\tilde{\theta^0}$ is an equivalent model for model $\mathcal{M}^0$ if $\forall x, \mathcal{M}^0(x) = \tilde{\mathcal{M}^0}(x)$.

### Parameter Efficient Fine-tuning as Sparse Fine-tuned Model
- Problem (1) is NP-Hard due to the nonconvexity of the feasible region of matrix M, and existing methods propose to solve it by estimating M and optimizing other parameters.
- Methods for choosing M are categorized into random, rule-based, and projection-based approaches, all of which are actually sparse fine-tuned models. Theory can be proven based on properties in Definition 1 without referring to any specific model's property.

#### Random Approach
- Randomly select parameters to be fine-tuned
- Random approaches for parameter tuning include the **Random** and **Mixout** models.
- **Random** model randomly selects parameters to be fine-tuned with respect to a given sparsity ratio while **Mixout** model resets a portion of the fine-tuned model's parameters to the pre-trained parameters with respect to a ratio.

#### Rule-Based Approach
- Pre-define rule to fix the parameters to be tuned.
- Rule-based approaches for parameter fine-tuning include **BitFit, MagPrunning, Adapter, and LoRA**.
- **BitFit** only fine-tunes the biases-term.
- **MagPrunning** fine-tunes the weights with high absolute value.
- **Adapter** adds an adapter layer inside the transformer layer.
- **LoRA** adds a new vector calculated by recovering an hidden vector from a lower dimension space.
- Both **Adapter** and **LoRA** can be considered sparse fine-tuned model shown in Figure 1.

#### Projection-Based Approaches
- Choose the optimal parameter mask $M$ and optimize the parameters $\theta$ alternately.
- First relax $M$ as a continuous variable to get an optimized value and then project the optimized value onto the feasible region which can be denoted as $\hat{M} = \Pi_\Omega(M) = arg\,min_{\hat{M} \in \Omega} \|\hat{M} - M\|$ where $\Omega=\left\{M \mid\|M\|_0=\lfloor m p\rfloor ; M_{i j}=0, \forall i \neq j ; M_{i i} \in \{0,1\}\}\right.$ and $\Pi_\Omega$ denotes denotes the projection operator onto the feasible region $\Omega$ which is an *L*~0~ ball.
- **DiffPruning** model the parameter selection mask as a Bernoulli random variable and optimize the variable with a reparametrization method. It then projects the mask onto M’s feasible region $\Omega$ and do the optimization alternately.
- **ChildPruning** iteratively train the full model parameters and then calculates the projected mask to find the child network.
- Projection-based methods **suffer from the projection discontinuity problem**.
- The feasible region of M is *non-convex*, which means that a small perturbation on M can lead to a totally different projection.
- This problem makes the projection sensitive to the parameters updating noise, which leads to inconsistency and impairs the overall performance.

### Theoretical Analysis of the Sparse Fine-tuned Model
- They show that **sparsity implies a regulatization** of the original model
- They prove that if a model is sparse fine-tuned model, **the model stability can benefit from the sparsity**
- They provide theoretical analysis of the model generalization error bound and show that **sparsity contributes to reducing the generalization error**.
- These theories is **applicable to all model** categories since the theory only uses properties from Definition 1.
-
#### Sparse Fine-tuned Model as a Regularizer
- The sparse fine-tuned optimization in Problem (1) can be reformulated as:
$$
\begin{gathered}
\min _\theta \mathcal{L}(\theta) \\
\text { s.t. }\left\|(I-M)\left(\theta-\theta^0\right)\right\|^2=0,
\end{gathered}
$$
- $M = diag\{M_{11}, \cdots\, M_{mm}\} \Longrightarrow$ diagonal matrix with $M_{ii} \in \{0,1\}$
- By langrangian duality, solving the modified problem is equivalent to solving the following problem:
$$
\bar{L}=\min _\theta \max _\lambda \mathcal{L}(\theta)+\lambda\left\|(I-M)\left(\theta-\theta^0\right)\right\|^2
$$
**Proposition 1.** Optimizing problem above implies to optimizing the upper bound $\bar{L}$ of the following regularized problem:
$$
L_R=\min _\theta \mathcal{L}(\theta)+\left\|(I-M)\left(\theta-\theta^0\right)\right\|^2 \leq \bar{L}
$$

#### Stability Analysis
- Their research focus on Pointwise **Hypothesis Stability (PHS)** which focuses on **analyzing the change of model output after a training sample is removed**.
- Denote original trainig data as $S = \{z_1,\cdots,z_n\}$ and dataset without one sample as $S^i = \{z_1, \cdots, z_{i-1}, z_{i+1},\cdots, z_n\}$.
- $i \sim U(n)$ as a sampling procedure from a uniform distribution with *n* samples.
- $\mathcal{A}(S)$ is defined as model parameters obtained by running algorithm $\mathcal{A}$ on data $S$
- **Definition 3** (Pointwise Hypothesis Stability). A learning algorithm $\mathcal{A}(S)$ has pointwise hypothesis stability $\epsilon$ with respect to a loss function $\ell$, if
$$
\mathrm{E}_{S, i \sim U(n)}\left[|\ell\left(\mathcal{A}\left(S^i\right), z_i\right)-\ell\left(\mathcal{A}(S), z_i\right) \mid\right]\leq \epsilon
$$
- $\ell(\theta, z_i) \Longrightarrow$single sample loss for $z_i$ when the model parameter is $\theta$
- Assuming $\mathcal{A}(S^i)$ is close to $\mathcal{A}(S)$, as $\mathcal{A}(S)$ is the optimal solution, the Hessian matrix at $\mathcal{A}(S)$ is a **positive semi-definite matrix**.
- **Theorem 1** Stability. If the loss function $\ell$ is $\rho$-Lipschitz, $\mathcal{A}(S^i)$ is close to $\mathcal{A}(S)$, the Hessian matrix $\nabla^2 \mathcal{L}(\mathcal{A}(S))$ at $\mathcal{A}(S)$ at $\mathcal{A}(S)$ is positive-semidefinite with a singular value decomposition $U \operatorname{diag}(\Lambda) U^{-1}, \Lambda= \{\Lambda_1, \cdots, \Lambda_m\}$ and $\Lambda_{min} = min\{\Lambda_1, \cdots, \Lambda_m\}$, then the expectation of the loss $\mathbb{E}_ML_R$ has a pointwise hypothesis stability as:
$$
\mathbb{E}_{S, i \sim U(n)}\left[\left|\ell\left(\mathcal{A}\left(S^i\right), z_i\right)-\ell\left(\mathcal{A}(S), z_i\right)\right|\right] \leq \frac{2 \rho^2}{\left(\Lambda_{\min }+2(1-p)\right) n}
$$
- It can be observed that as the sparsity parameter $p$ decreases, the upper bound also decreases.

#### Generalization Analysis
- **Theorem 2** (Generalization). Denote the generalization error as $R(\mathcal{A}, S)=\mathbb{E}_z \ell(\mathcal{A}(S), z)$ and the empirical error as $\hat{R}(\mathcal{A}, S)=\frac{1}{n} \sum_{i=1}^n \ell(\mathcal{A}(S), z)$. Then, for some constant $C$, with probability $1-\delta$,
$$
R(\mathcal{A}, S) \leq \hat{R}(\mathcal{A}, S)+\sqrt{\frac{C^2+\frac{24 C \rho^2}{\Lambda_{\min }+2(1-p)}}{2 n \delta}}
$$

## Second Order Approximation Method (SAM)
- Remind that random and rule-based approach are **robust to noise perturbation** but **do not utilize the information from the task-specific data**.
- Projection-based approaches **utilizing data information** but **suffer from projection discontinuity problem**.
- They propose Second Order Approximation Method (SAM) to utilize data information while avoiding discontinuity problem.
- They propose a novel second-order approximation of Problem (1) to make the optimization target analytically solvable.
- They approximate the loss function with its **second-order Taylor expansion** as $\mathcal{L}\left(\theta^0+M \Delta \theta\right) \approx \mathcal{L}\left(\theta^0\right)+\nabla \mathcal{L}\left(\theta^0\right)^{\mathrm{T}} M \Delta \theta+$ $\frac{1}{2}(M \Delta \theta)^{\mathrm{T}} H M \Delta \theta$.
- They approximate the Hessian matrix with a diagonal matrix denoted as $H = diag\{h_1, h_2, \cdots,h_n\}$ and also assume that H is positive semidefinite.
- Problem (1) then can be reformulate as:
$$
\begin{array}{r}
\min _{\Delta \theta} \mathcal{L}\left(\theta^0\right)+\nabla \mathcal{L}\left(\theta^0\right)^{\mathrm{T}} M \Delta \theta+\frac{1}{2}(M \Delta \theta)^{\mathrm{T}} H M \Delta \theta \\
\text { s.t. } \quad\|M\|_0=\lfloor m p\rfloor ; \quad M_{i j}=0, \forall i \neq j ; \quad M_{i i} \in\{0,1\}
\end{array}(8)
$$
and we can obtain optimal parameter mask M with the following theorem:
- **Theorem 3.** If $\hat{M}_{i i}=\mathbb{1}\left(\sum_{j=1}^m \mathbb{1}\left(\left|\frac{\nabla \mathcal{L}\left(\theta^0\right)_i^2}{h_i}\right|>\left|\frac{\nabla \mathcal{L}\left(\theta^0\right)_j^2}{h_j}\right|\right) \geq m-\lfloor m p\rfloor\right)$, where $\nabla \mathcal{L}\left(\theta^0\right)_i$ is the i-th element of the gradient vector $\nabla \mathcal{L}\left(\theta^0\right)$, then
$$
\inf _{\Delta \theta} \mathcal{L}\left(\theta^0+\hat{M} \Delta \theta\right) \leq \inf _{\substack{\Delta \theta,\|M\|_0=\lfloor m p\rfloor ; \\ M_{i j}=0, \forall i \neq j ; M_{i i} \in\{0,1\}}} \mathcal{L}\left(\theta^0+M \Delta \theta\right)
$$
- Calculating the diagonal of the Hessian matrix is very complex, hence instead of minimizing the target function in Problem (8), we propose to optimize its upper bound
$$
\begin{array}{r}
\quad \min _{\Delta \theta} \mathcal{L}\left(\theta^0\right)+\nabla \mathcal{L}\left(\theta^0\right)^{\mathrm{T}} M \Delta \theta+\frac{1}{2}(M \Delta \theta)^{\mathrm{T}} D M \Delta \theta \\
\text { s.t. } \quad\|M\|_0=\lfloor m p\rfloor ; \quad M_{i j}=0, \forall i \neq j ; \quad M_{i i} \in\{0,1\} .
\end{array}
$$
- $D = diag\{|\lambda_{max}|, |\lambda_{max}|,\cdots,|\lambda_{max}|\}$ and $\lambda_{max}$ = max eigenvalue of $H$.
- This can be directly calculated from the Rayleigh quotient that $\forall x \neq 0, x^T H x \leq x^T x \lambda_{\max } \leq$ $x^T x\left|\lambda_{\max }\right|=x^T D x$. Therefore, the SAM algorithm is quite straightforward based on Theorem 3.
- First get the gradient $\nabla\mathcal{L}(\theta^0)_i$ for the i-th parameter $\theta_i$, then calculate $|\nabla\mathcal{L}(\theta^0)_i^2|$ and take the top $\lfloor mp \rfloor$ parameters to optimize.
-
## Experiments
### Experimental Setup
- The **original development** set is used as the test set to report scores since the **original test sets are only available via the leaderboard** with a limited submission number.
- The training set is split by **randomly sampling 10%** as the new development set while using the **remaining 90% samples** to train the model.
- **Early stop training** is done by setting the tolerance for all models to **40**.
- The **jiant2 framework** is used to build the models and they are tested on **several GLUE and SuperGLUE tasks**.
- The baseline models include **Random, Mixout, BitFit, MagPruning, Adapter, LoRA, DiffPruning, and ChildPruning**.
- Each experiment is **run 10 times** with **different random seeds** and the scores are reported with corresponding standard deviations.
- All baseline models are **re-implemented with the jiant framework** to give a fair comparison.
- The **sparsity** is set to **0.005** for all models.
- Burn-in steps are chosen from {500, 600, 700, 800, 900, 1000, 2000} as a hyper-parameter for calculating $\nabla\mathcal{L}(\theta^0)_i$ in SAM. (600 for CoLA and MRPC, 700 for RTE, CB, and COPA, 1000 for STS-B, 2000 for WSC)
- The models are fine-tuned based on **RoBERTa-base** provided by the transformers toolkit and run on NVIDIA TITAN RTX GPU with 24GB memory.

### Experimental Results
#### Main Experiment


- Most of the parameter-efficient models achieve better performance than the FullTuning model which is also consistent with the observations in many previous works.
- Most of the parameter-efficient models are more stable than the FullTuning model.
- Random model outperforms the FullTuning model
- The proposed SAM model outperforms several baseline models in several tasks and it ranks in the top 3 of most tasks

#### Project Discontinuity Problem
- plot the training curve of the DiffPruning method on the CB task.
- Mask was adjusted every 600 training steps.
- This result shows that **changing the mask severely affects the training procedure** due to the projection discontinuity problem.

#### Relation between Stability and Overall Performance
- x-axis is the stability rank in each main experiment while the y-axis is the corresponding overall performance rank.
- The dot indicates the overall performance mean rank value while the line length indicates the standard deviation.
- They calculate Spearman's rank correlation coefficient for the two ranks. It can be denoted as $\rho=\frac{\operatorname{cov}(R(S), R(V))}{\sigma_{R(S)} \sigma_{R(V)}}$, where $R(S)$ and $R(V)$ are the rank variables, $\operatorname{cov}(R(S), R(V))$ is the covariance of $R(S)$ and $R(V)$ while $\sigma_{R(V)}$ is the standard deviation of the rank variable $V$. They calculated $\rho=0.4356$ with $\mathrm{p}$-value $=0.000014<0.05$ indicating that the correlation between the two rank variables is significant.

#### Effectiveness of Sparsity
- They change the sparsity of the SAM model in {0.0002, 0.0005, 0.001, 0.002, 0.005, 0.01, 0.02, 0.05, 0.1, 0.2} and plot the relationship between sparsity and the mean/standard deviation in both the test set and training set.
- **as the sparsity ratio decreases, the mean and the standard deviation of most tasks also decrease** which means the models become more stable with better generalization.
- **If the sparsity ratio drops below a certain threshold, the models become quite unstable and the performance also sees a sharp drop** due to the drastic increase in the empirical error.
- At the same time, under such circumstances, **decreasing the sparsity ratio cannot further lower the bound effectively**.

#### Data Perturbation Stability
- They **conduct a new experiment** to **verify the data perturbation stability** by training the model on **10 different** training sets.
- Each of them is made by randomly **removing 10% training samples** from the original training set.
- The data perturbation stability performance is similar to the main experiment and the proposed SAM model still has the best data perturbation stability as well as the overall performance among all the models.


## Related Works
- Other approaches such as regularization, adversarial training, and lottery ticket approaches have also been proposed to enhance the generalization capability.
- Prompt-tuning and continuous prompts methods adapt the model to new domains without changing parameters.
- This work focuses on parameter-efficient methods that only fine-tune a small part of the model.

## Conclusion
- They proposes to understand the effectiveness of parameter-efficient fine-tuning models.
- Most models are categorized into three categories: random, rule-based, and projection-based.
- They shows that all models in the three categories are sparse fine-tuned models.
- They gives a theoretical analysis of the stability and generalization error of these models.
- The random and rule-based approaches do not utilize task data, while the projection-based approaches have the projection discontinuity problem.
- The paper proposes a novel SAM model to alleviate both problems.
- The paper conducts extensive experiments to show the correctness of the theoretical analysis and effectiveness of the proposed models.