# Multi-Set Inoculation: Assessing Model Robustness Across Multiple Challenge
Sets

Vatsal Gupta1†, Pranshu Pandya1†, Tushar Kataria2, Vivek Gupta3 , Dan Roth3
1IIT Guwahati, 2University of Utah, 3University of Pennsylvania,
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
Corresponding Author,†Equal Contribution

###### Abstract

Language models, given their black-box nature, often exhibit sensitivity to
input perturbations, leading to trust issues due to hallucinations. To bolster
trust, it’s essential to understand these models’ failure modes and devise
strategies to enhance their performance. In this study, we propose a framework
to study the effect of input perturbations on language models of different
scales, from pre-trained models to large language models (LLMs). We use fine-
tuning to train a robust model to perturbations, and we investigate whether
exposure to one perturbation improves or degrades the model’s performance on
other perturbations. To address multi-perturbation robustness, we suggest
three distinct training strategies. We also extend the framework to LLMs via a
chain of thought(COT) prompting with exemplars. We instantiate our framework
for the Tabular-NLI task and show that the proposed strategies train the model
robust to different perturbations without losing accuracy on a given dataset.
Code and Data: https://msin-infotabs.github.io/

##  1 Introduction

Language models (LMs), which have become increasingly integrated into various
aspects of daily lives, hold immense potential to revolutionize how we
interact with technology. Their ubiquity underscores the importance of
thoroughly examining their robustness and generalizability, as this will be
instrumental in fostering trust among users. One notable challenge is their
sensitivity to even slight changes in input. For instance, while a human can
easily interpret and understand a statement regardless of minor alterations,
LMs struggle wang2023adversarial; nie-etal-2020-adversarial. This
inconsistency becomes notably apparent when minor perturbations to the input,
which do not inherently modify the underlying meaning, result in a decline in
the performance of the model shankarampeta2022enhancing; glockner-
etal-2018-breaking. An example of such perturbations for the task of tabular
inference gupta-etal-2020-infotabs, is illustrated in Table 1.

Case Closed
---
Written | Takahiro Arai
Publish | Shogakukan
Eng. Publish | SG Shogakukan Asia
Demographic | Shonen
Magazine | Weekly Shonen Sunday
Orig. Run | May 9, 2018 - present
Volumes | 2 (List of volumes)

H1: ’Case Closed’ was written by Takahiro Arai and published by Shogakukan.
(E) H1’: ’Case Closed’ was writtKen b Takhahiro Arai and publihsed by
Shogakukan.(E) H2: ’Case Closed’ was a long-running Japanese comic serial. (E)
H2’: ’Case Closed’ was not a long-running Japanese comic serial. (C) H3: ’Case
Closed’ was made into an anime called Detective Conan. (N) H3’: Detective
Conan was an anime adaptation of ’Case Closed’. (N) H4: ’Case Closed’ has been
running for more than 5 years. (E) H4’: ’Case Closed’ has been running for
more than 10 years. (C) H5: ’Case Closed’ was published in English by SG
Shogakukan Asia (E)
H5’: ’Case Closed’ was published in English by SG Shogakukan Australia (C)
---

Table 1: Tabular premise and hypotheses example from InfoTabS gupta-
etal-2020-infotabs. Original (H1-H5) and perturbed hypotheses (H1’-H5’)
represent character, negation, paraphrasing, numeric, and location
perturbations. Labeled as E, C, or N. Bold entries are keys; adjacent entries
are their values.

Figure 1: Language Models Sensitivity to Input Perturbations. Language models
trained on Tabular-NLI (Task A) with Original Hypothesis(Dataset D) are not
reliable for perturbed hypotheses (Dataset D’ for character, paraphrasing, or
numeric perturbations examples).

Addressing these sensitivities to input perturbation is crucial for the
advancement and reliability of LMs in real-world applications. Empirical
evidence supports the effectiveness of fine-tuning models using perturbed
input samples from challenge sets jiang-etal-2022-rose;
fursov2021differentiable. For instance, wang-etal-2020-cat; liu-
etal-2019-inoculation showcased that a pre-trained language model (PLM)
utilizing Masked Language Modeling (MLM) and trained for a specific NLP task
becomes significantly robust to input perturbations when further fine-tuned
using a small set of challenge examples. However, the ability of these models
to generalize across different types of perturbations is still a subject of
investigation liu2020adversarial. The implications of fine-tuning a model on a
particular challenge set, especially concerning its impact on handling other
perturbations, warrant further exploration. For example, refer to Figure 1, it
remains ambiguous whether a model’s enhanced robustness to character
perturbations, post-fine-tuning, implies its competence in addressing
challenges from distinct categories, such as those involving paraphrasing.

In this study, we address this challenge, seeking to answer the following two
questions: _How does fine-tuning a model on one challenge set affect
performance on others? Is it possible to guarantee consistent robustness
across multiple distinct challenge sets?_ In particular, we extend the
_single-set inoculation_ approach of liu-etal-2019-inoculation, to a more
generic multi-sets context, which we refer to as _multi-set inoculation_.
First, we introduce a comprehensive framework designed to address the
complexities of multi-set inoculation. To the best of our knowledge, we are
the first to introduce and extensively study this challenge.

Our framework is adept at handling both (a) transformer-based pre-trained
models such as BERT devlin-etal-2019-bert and RoBERTa liu2019roberta., which
are amenable to direct fine-tuning, and (b) extensive large generative
language models such as GPT 3.5 brown2020language, 4, and LLaMA, LLaMA-2
touvron2023llama, Flan-T5 chung2022scaling; kanakarajan-
sankarasubbu-2023-saama etc, which can’t be directly fine-tuned. For these
generative models, we leverage the few-shot Chain of Thought(COT)
wei2023chainofthought technique at inference, serving as an alternative
parallel to traditional fine-tuning. This methodology circumvents the
computational intricacies inherent in the fine-tuning of LLMs. It proficiently
manages the tuning of a multitude of model parameters using a limited
constrained set of training samples. To the best of our knowledge, we are the
first to study Inoculation with LLM, prior studies liu2019roberta;
wang2021infobert; liu-etal-2019-inoculation limit to a more traditional BERT
style model. Under our framework, we explore three distinct multi-set fine-
tuning methods, each aiming to strengthen model resilience across various
challenge sets with different perturbations. Our study made the following
contributions:

  * •

We introduce the problem of "Multi-set Inoculation" that examines the
implications of fine-tuning of one challenge set relative to others.

  * •

We proposed a framework to study the multi-set inoculation challenge. Our
framework encompasses of traditional PLMs like BERT and RoBERTa, as well as
LLMs including GPT 3.5 and LLaMA etc.

  * •

Using tabular NLI as our case study, we evaluated three distinct multi-set
fine-tuning approaches which hold potential to ensure concurrent robustness to
multiple challenge sets, i.e., several forms of input perturbations.

##  2 Our Proposed Framework

In this section, we detail our framework for Multiset Inoculation, i.e..
assessing model robustness across various input perturbations and introduce
our multiset fine-tuning strategies which enhanced model performance across
multiple challenge sets. Figure 2 represent a high level flowchart of our
proposed framework.

##### Terminology.

Given a PLM model, M, fine-tuned on the original (unperturbed) training set O
$=\\{(x_{i},y_{i})\\}_{i=1}^{N}$ for NLP task T. Let O${\sc{}_{S_{j}}}$
$=\\{(x_{i},y_{i})\\}_{i=1}^{n_{j}}$ be a sub-sample set Sj of the original
training set O, where $n_{j}\ll N$. Let $\pi_{j}$ represent an input
perturbation applied to O${\sc{}_{S_{j}}}$ to produce the challenge set
$\Pi_{j}^{S_{j}}$ $=\\{\pi_{j}(x_{i}),\pi_{j}(y_{i})\\}_{i=1}^{n_{j}}$. If we
have $m$ distinct perturbations $=\\{\pi_{j}\\}_{j=1}^{m}$ applied to $m$
sample subsets $\\{S_{j}\\}_{j=1}^{m}$ from the original set O, the final
perturbation challenge set becomes $\\{\Pi_{j}^{S_{j}}\\}_{j=1}^{m}$. We use
Pj as a shorthand for the final perturbation set $\Pi_{j}^{S_{j}}$.

We assess the performance of M using evaluation metric $\Theta$ across held
out challenge sets Qj for $j=1,\ldots,m$. Qj is test set for perturbation
$P_{j}$, yielding the performance $\theta_{j}$ for each respective challenge
set for perturbation Pj. Importantly, these metrics $\Theta$ serve as an
evaluation metric, enabling a consistent comparison of model M’s efficacy on
diverse challenge sets.

Figure 2: Multi-Set Inoculation Framework. High-level flowchart describing the
proposed frameworks for PLMs (via finetuning) and LLMs (via prompt design).

###  2.1 MultiModel Uniset Inoculation

Drawing from the insights presented in our introduction, we employ challenge
sets, denoted as Pj, as tools for refining a more robust model liu-
etal-2019-inoculation. Specifically, we fine-tune our PLM model using k
samples extracted from a challenge set Pj. This fine-tuning across different
Pj sets results in an array of robust models, each designated as RMj. We
subsequently evaluate these models’ performances across held-out challenge
test sets, Qj for every $j\in N$. This evaluation probes the efficacy of
inoculating models on a singular set in enhancing—or possibly
undermining—performance on both test sets and different challenge sets. While
this ’multi-model single set framework’ generates multiple robust models, a
clear downside emerges: as the variety of perturbation types (represented as
$N$) grows, managing multiple models becomes less practical.

###  2.2 UniModel Multiset Inoculation

The proposed methodology involves fine-tuning the PLM using samples drawn from
every challenge set, aiming to cultivate a universally robust model, denoted
as RM, based on the original model M. We put forth three distinct fine-tuning
techniques:

  * •

Sequential (Seq): This technique systematically fine-tunes the model by
utilizing k samples from each challenge set Pj, aiming to evolve the model
into RM. The fine-tuning proceeds in an order/sequence (specified by Order),
which may be set at random or determined through particular criteria.

  * •

Mixed-Training (Mix): In this strategy, a composite dataset, termed PM, is
fashioned by randomly selecting k samples from all challenge sets, Pj. The
cumulative size of PM is given as mk, with k being a consistent sample size
across all sets, Pj. Subsequently, the model M is fine-tuned using the
aggregated PM to give rise to RM. In our implementation, we adopt a uniform,
random sampling approach, symbolized as $\Upsilon$.

  * •

Dynamic Mix-Training (DynMix): This approach mirrors Mixed-Training but
introduces variability in sample sizes across challenge sets, denoted as k1,
k2, and so on. Additionally, the sampling methodology $\Upsilon$ can be
tailored for each perturbation challenge set ($\Upsilon_{j}\forall$ Pj) .

Given that all three outlined techniques revolve around data sampling and
culminate in a singular robust model RM, we label this as the "Uni-model
multi-set" paradigm.

###  2.3 Inoculation via. Prompting for LLM

Fine-tuning LLMs on challenge sets is costly. In contrast, prompt tuning is
quicker and more effective for many NLP tasks shin2023prompt. We design a
prompt encapsulating the "task" description. We also add illustrative
instances (as "exemplars") from original sets ($\sc O$) which serve as main
guiding posts (a.k.a few shot). Each exemplar is enriched with a rationale,
mirroring a _"chain of thought"_ COT prompting wei2023chainofthought.

##### Original Prompt (OP).

This allows us to investigate the effectiveness of the perturbations
$\pi_{C},\pi_{N},\pi_{M},\pi_{L},\pi_{S}$ on LLMs. This serves as a baseline
for performance variations of LLMs under input perturbations. Here, we
consider two variant of LLM prompting:

  * •

Zero-shot (OP${}_{\text{ZS}}$). We create a prompt template consisting of only
the description of the task, without any exemplars or reasoning chains. This
serves as our baseline LLM.

  * •

Few-shot with COT (OP${}_{\text{COT}}$). Here, we consider NLI task
description along with few shot exemplars taken from the original set O their
reasoning chains a.ka. chain of thoughts prompting.

##### Single Exemplars Multiple Prompts (SEMP)

: For each perturbation type, denoted as $\pi_{j}$, we construct a prompt that
combines the task description, a description of that perturbation, and
exemplars from the original set O and Pj. The exemplars are accompanied by
corresponding labels and a reasoning chain (COT). This results in multiple
prompts, each tailored to a specific perturbation $\pi_{j}$. We called this
approach uni-type exemplars multi-prompts, similar to our multi-model uniset
framework (section 2.1).

##### Multiple Exemplars Single Prompt (MESP) :

Here, we consider descriptions and exemplars of all perturbations
($\forall\pi_{j}$) in a single prompt. We create a prompt by combining
multiple exemplars corresponding to each perturbation $\pi_{j}$, sampled from
Pj. Here, the prompt contains the task description, a description of all
perturbations, and exemplars from the original set O and each of the challenge
sets ($\forall_{j}$ Pj). Given token length constraints, we tradeoff between
the detail of perturbation descriptions and the number of perturbation
exemplars:

  * •

Mixed-Prompting-Instructional (MESP${}_{\text{MPI}}$): In this prompt, we
emphasize the perturbation description while reducing the number of exemplars.
Still, we ensure at least one exemplar is sampled from each perturbation.

  * •

Mixed-Prompting-Exemplar (MESP${}_{\text{MPE}}$): In this prompt, we
prioritize more perturbation exemplars and condense each perturbation’s
description. However, we ensure that each brief description captures the core
logic of the perturbation.

For a granular exploration into the model’s responsiveness to input
perturbations, the reader is directed to the ensuing section (3.3.2).

##  3 Case Study on Tabular Inference

For our framework evaluation, we focus on semi-structured tabular inference
task as a case study.

###  3.1 Dataset

##### Original Dataset (O).

We utilize the tabular-NLI dataset, InfoTabS, cited from (gupta-
etal-2020-infotabs), along with its adversarial perturbations as detailed in
shankarampeta2022enhancing. The InfoTabS dataset is characterized by its
extensive variety in table domains, categories, and keys, encompassing diverse
entity types and forms. MSIn-InfoTabS come with three test splits
($\alpha_{1}$, $\alpha_{2}$, $\alpha_{3}$) test sets- where $\alpha_{1}$ is
the original test set, $\alpha_{2}$ is an adversarial set, $\alpha_{3}$ is a
zero-shot (out of domain OOD) set as in gupta-etal-2020-infotabs.

##### Perturb Challenge Datasets (P, Q).

Our dataset incorporates perturbations from shankarampeta2022enhancing,
enhanced using tools such as TextAttack morris-etal-2020-textattack and NLP
Checklist ribeiro-etal-2020-beyond, alongside manual adjustments. Each
perturbation specifically targets the hypothesis of an input sample. For every
perturbation type, we curate challenge sets of up to 1,500 samples. Only those
samples that are pertinent post-perturbation are selected. When the number of
such samples exceeds 1500, we narrow down to the most diverse 1500 using
Fixed-Size Determinantal Point Processes ($\mathit{k}$-DPPs) kulesza2011k.
Perturbations pertinent to the Tabular-NLI tasks in our framework are
delineated in Table 2. The complete dataset, including the original InfoTabS
and its perturbations, is referred to as MSIn-InfoTabS.

Class | Key | Type
---|---|---
char | C | Character-level perturbation
neg | N | Negation-type perturbation
num | M | Numeric perturbation
loc | L | Location perturbation
stan | S | Paraphrasing as a perturbation
Table 2: Perturbation Types:  We use 5 distinct perturbations as challenge
sets for Tabular-NLI.

  * •

Train/Test for BERT’s Models. For any perturbation type, we represent Qj
consisting of 1000 examples for testing and Pj consisting of 500 examples for
fine-tuning. We define the union of all challenge test sets as $\text{{\sc
Q}}=\\{\cup_{j}^{m}\text{{\sc Q}}_{j}\\}$ and the corresponding training set
as $\text{{\sc P}}=\\{\cup_{j}^{m}\text{{\sc P}}_{j}\\}$.

  * •

Train/Test for LLMs. As LLMs inference is costly we limit our evaluations to
300 samples from $\text{{\sc Q}}_{j}$, which we named $\text{{\sc
R}}_{j}$(${\text{{\sc R}}_{j}}\subset\text{{\sc Q}}_{j}$). ${\text{{\sc
R}}_{j}}$ is used to describe the challenge set comprising of premise and
perturbed hypothesis pairs and ${\text{{\sc R'}}_{j}}$ contains the same
premise along with the corresponding unperturbed hypothesis as pairs.
Specifically, ${\text{{\sc
R}}_{j}}=\\{$p$\colon$p$=\Pi_{k}^{-1}(x),x\in{\text{{\sc R}}_{j}}\\}$. We
define union of all evaluation sets as ${\text{{\sc
R}}}=\\{\cup_{j}^{m}{\text{{\sc R}}_{j}}\\}$. Demonstrations for prompts are
sampled from training sets ${\text{{\sc P}}_{j}}$ and ${\text{{\sc P'}}_{j}}$,
where ${\text{{\sc P'}}_{j}}$ is the set containing the original unperturbed
hypothesis and premise pairs for the examples in ${\text{{\sc P}}_{j}}$. The
testing is done on ${\text{{\sc R}}_{j}}$ and ${\text{{\sc R'}}_{j}}$ where
${\text{{\sc R'}}_{j}}$ is the set containing the original unperturbed
hypothesis and premise pairs for the examples in ${\text{{\sc R}}_{j}}$.

###  3.2 Representation and Evaluations

##### Table Representation.

Adapting from neeraja-etal-2021-incorporating, we used alignment methods
yadav-etal-2020-unsupervised to remove distracting rows (DRR). We consider the
top-8 rows for table representation as a premise (DRR@8). This facilitates a
more accurate representation by evidence grounding of the premise for
information pertinent to the hypothesis that requires labeling.

Evaluation Metric. We use accuracy which is equivalent to the micro-f1 score
for the NLI task where the label for each example can be only one of
entailment E, contradiction C, neutral N. The improvement over the multi-
challenge sets is considered by taking the average of the improved performance
over each challenge set $\sc Q_{\pi_{j}}$ and this is used as the score($\mu$)
for multi-perturbation setting.

###  3.3 Modeling

####  3.3.1 Fine-tuning Bert’s Model

We use RoBERTa-Large liu2019roberta as the baseline model wolf-
etal-2020-transformers finetuned on InfoTabS train set This baseline model is
henceforth referred to as RoBERTa${}_{\text{\sc InfoTabs}}$. 111Original
training with 10 epochs with a $1e^{-5}$ learning rate
shankarampeta2022enhancing; jain-etal-2021-tabpert.

We test the baseline model on both O and Q, by testing on Q we attempt to
demonstrate the effectiveness of the different perturbations
$\pi_{C},\pi_{N},\pi_{M},\pi_{L},\pi_{S}$ on RoBERTa${}_{\text{\sc
InfoTabs}}$.

##### MultiModel Uniset Inoculation

RoBERTa${}_{\text{\sc InfoTabs}}$ is further fine-tuned on different types of
challenge sets($\text{\sc P}_{j}$s), resulting in multiple robust models.

##### UniModel Multiset Inoculation

  * •

Sequential (Seq): We perform sequential fine-tuning of RoBERTa${}_{\text{\sc
InfoTabs}}$ across various challenge sets. The training order (Order) for
fine-tuning is based on average baseline model performance across challenge
sets. Our sequencing strategy aims to minimize the potential for catastrophic
forgetting induced by subsequent fine-tuning on different challenge sets. 222
For fine-tuning tasks on challenge set Pj, we use a learning rate of $3e^{-5}$
which outperform other rates.

  * •

Mixed-Training (Mix): Here, the RoBERTa${}_{\text{\sc InfoTabs}}$ is fine-
tuned samples obtained by mixing k instances drawn from each of the challenge
sets $\text{{\sc P}}_{M},\text{{\sc P}}_{N},\text{{\sc P}}_{L},\text{{\sc
P}}_{C},\text{{\sc P}}_{S}$. Here, k is an hyper-parameters, set equal to
$500$ examples, as discussed in section 3.1.

  * •

Dynamic Mix-Training (DynMix): This is similar to Mix, except the number of
samples drawn from each of the challenge sets is different. The number of
samples is determined by the inverse of the baseline performance for
RoBERTa${}_{\text{\sc InfoTabs}}$ for challenge sets Pjs.

Evaluations are reported on all sets Q and original set O. This helps in
comprehending the impact uniset inoculated model has on other forms of
perturbation.

####  3.3.2 LLM Prompting

We used GPT-3.5-Turbo with low temperature of $0.3$, LLaMA-2 after
quantization using QLoRA dettmers2023qlora, and Flan-T5 series. We develop
methodologies for LLMs that rely solely on prompting and exclude fine-tuning.
The broad template we use is outlined in Table 3 and adapted under different
settings as outlined below.

Broad Prompt Template
---
NLI Task Explanation |  In this task, we will ask you to make an inference about the information presented as the premise. We will show you a premise and a hypothesis…
Perturbation Awareness |  The concept of numeric and character typos in questions is important for maintaining the integrity and meaning of a sentence…
Description of Limitation |  It is very important and critical that you do not use information other than the premise that you may know if you believe that it is not generally known…
Answering |  (Restriction for Answering) Answer with an explanation in the following format, restricting the answer to only one of the following: "yes" or "no" or "it is not possible to tell" + Answering Format
Demonstrations |  Demonstrations from different sets with reasoning (COT).

Table 3: A broad structure of the prompt used for fine-tuning LLMs.

##### Original Prompt (OP).

This is the original prompt zero shot (OP${}_{\text{ZS}}$) setting with NLI
task description. In COT setting (OP${}_{\text{COT}}$), where we consider
perturbation $\pi_{j}\in\\{\pi_{C},\pi_{N},\pi_{M},\pi_{L},\pi_{S}\\}$, the
exemplars for COT are taken from challenge sets Pj $\in$ $\\{\text{{\sc
P}}_{M},\text{{\sc P}}_{N},\text{{\sc P}}_{L},\text{{\sc P}}_{C},\text{{\sc
P}}_{S}$}.

##### Single Exemplars Multiple Prompts.

For a designated perturbation $\pi_{j}$ from the set
$\\{\pi_{C},\pi_{N},\pi_{M},\pi_{L},\pi_{S}\\}$, our prompts integrate the NLI
task outline, a brief on the perturbation $\pi_{j}$, and its Chain of Thought
(COT) exemplars sourced from the respective challenge set $\text{{\sc
P}}_{j}$.

##### Multiple Exemplars Single Prompt.

These prompts contain NLI task description, description of all perturbations
$\pi_{i}\in\\{\pi_{C},\pi_{N},\pi_{M},\pi_{L},\pi_{S}\\}$ and exemplars
sampled from each challenge set Pj $\in$ $\\{\text{{\sc P}}_{M},\text{{\sc
P}}_{N},\text{{\sc P}}_{L},\text{{\sc P}}_{C},\text{{\sc P}}_{S}$}. Here , we
consider two different prompts settings MESP${}_{\text{MPI}}$ and
MESP${}_{\text{MPE}}$, as described earlier in section 2.3.

##  4 Results and Analysis

Our experiments are designed to answer the following questions:-

  * •

Do input perturbations pose challenges for language models?

  * •

Can multi-model single-set inoculation improve performance across multiple
perturbations?

    * –

How does fine-tuning on a specific perturbation affect performance across
various perturbations?

    * –

Do descriptions and exemplars of perturbations enhance LLM performance? And
does COT prompting offer advantages for LLM?

  * •

How to implement UniModel Multi-Set Inoculation?

    * –

Does it outperform multi-model uniset inoculation?

    * –

What is significant: the quality of perturbation descriptions or the quantity
of corresponding exemplars?

We now showcase the effectiveness of the inoculation framework through
performance on both Bert-style models and LLMs.

###  4.1 Results: Bert Style Models

##### MultiModel Uniset Inoculation.

The baseline performance of RoBERTa${}_{\text{\sc InfoTabs}}$ original and
challenge sets is shown in Table 4. We also report the performance after fine-
tuning each challenge set in the same table.

| Original Test Sets | Challenge Test Sets
---|---|---
Train Test | $\boldsymbol{\alpha_{1}}$ | $\boldsymbol{\alpha_{2}}$ | $\boldsymbol{\alpha_{3}}$ | char | neg | num | loc | stan
baseline | 72.72 | 64.83 | 62.33 | 57.30 | 46.90 | 67.20 | 70.20 | 67.10
char | 75.28 | 63.83 | 63.33 | 59.20 | 43.70 | 64.30 | 66.00 | 68.30
neg | 66.94 | 64.56 | 58.06 | 52.80 | 71.90 | 69.60 | 69.70 | 62.40
num | 62.06 | 60.83 | 52.50 | 47.30 | 49.60 | 85.40 | 83.00 | 57.60
loc | 55.78 | 58.67 | 49.67 | 47.40 | 53.90 | 84.60 | 86.10 | 53.50
stan | 73.56 | 62.61 | 60.44 | 58.30 | 40.80 | 70.30 | 67.80 | 66.80

Table 4: Multi-model Uniset Inoculation: RoBERTa${}_{\text{\sc InfoTabs}}$
when fine-tuned on one of the challenge sets(Pj), but tested on all challenge
sets (Qj) with number of sample used equal 500.

Analysis. (a.) Baseline performance of RoBERTa${}_{\text{\sc InfoTabs}}$ on
challenge sets is notably lower than on original sets, emphasizing PLMs’
vulnerability to input perturbations, especially with negation challenges."
(b.) Fine-tuning via single-set inoculation significantly bolsters the model
against specific perturbations, improving negation accuracy by +25 points from
baseline.  (c.) Despite fine-tuning, the model’s robustness to paraphrasing
remains largely unchanged.  (d.) While the fine-tuned model excels against
specific perturbations, it struggles with others. Interestingly, character
perturbations inadvertently boost its proficiency in challenges like
paraphrasing.  (e.) Inoculation effects differ: character set inoculation
consistently improves performance on original test sets, but others, like
number and location, lead to a marked performance decline in both original and
other challenge test sets.

##### UniModel Multiset Inoculation.

We present results on Sequential training (Seq), Mixed Training (Mix), and
Dynamic Mixed Training (DynMix) in Table 5, 6, 7 respectively.

Seq. Table 5 presents the results using Sequential Training (Seq). The method
trains RoBERTa${}_{\text{\sc InfoTabs}}$ on varied challenge sets in distinct
sequences. For instance, Order MNLCS with k samples implies training
sequentially on subsets of $\\{\text{{\sc P}}_{M},\text{{\sc
P}}_{N},\text{{\sc P}}_{L},\text{{\sc P}}_{C},\text{{\sc P}}_{S}$} of size k.
This is denoted as Seq${}_{\text{MNLCS}}$.

| Original Test Sets | Challenge Test Sets |
---|---|---|---
Type | $\boldsymbol{\alpha_{1}}$ | $\boldsymbol{\alpha_{2}}$ | $\boldsymbol{\alpha_{3}}$ | char | neg | num | loc | stan | $\boldsymbol{\mu}$
baseline | 72.72 | 64.83 | 62.33 | 57.30 | 46.90 | 67.20 | 70.20 | 67.10 |
COL-ASC | 61.67 | 60.94 | 50.11 | 48.80 | 54.60 | 85.40 | 85.40 | 56.60 | 4.42
COL-DSC | 74.67 | 62.72 | 60.44 | 58.90 | 57.30 | 56.10 | 65.30 | 68.00 | -0.62
ROW-ASC | 55.00 | 58.11 | 47.22 | 46.80 | 50.90 | 84.50 | 85.90 | 51.30 | 2.14
ROW-DSC | 73.44 | 63.39 | 57.44 | 56.50 | 45.10 | 60.00 | 71.60 | 65.80 | -1.94

Table 5: Seq Results: RoBERTa${}_{\text{\sc InfoTabs}}$ Sequential Training
Seq with 500 samples from each Pj. Here, col-asc: csnlm, col-dsc: mlnsc, row-
asc: scnml, row-dsc: lmncs. $\mu$ is the average improvement over baseline.

Terminology. To define the sequence we consider (a.) Column Wise Average. This
configuration assesses the aggregate impact of fine-tuning across all
perturbations on each individual perturbation., (b.) Row Wise Average. This
configuration evaluates the aggregate impact of fine-tuning on an individual
perturbation against all other perturbations. Formally,

  * •

Column Wise Average. The column-wise average (COL) for a given perturbation
$\pi_{d}$ is the average performance improvement over the baseline on Qj
(Table 4) for models fine-tuned on all other perturbation P${}_{j},\text{{ for
}}j\neq d$ (except itself).

  * •

Row Wise Average. The row-wise average (ROW) for a given perturbation
$\pi_{d}$ is the average performance improvement over the baseline performance
(Table 4) for the model fine-tuned on Pd on other challenge dataset sets Qj,
for  $j\neq d$.

We compute both COL and ROW values for each perturbation. By sorting these
values, we derive sequences in ascending and descending order, yielding the
col-asc, col-dsc, row-asc, row-dsc as the order sequences333These sequences
represent the most commonly observed orders after conducting experiments as
outlined in Table 4, capturing the most frequent positions of perturbations in
the constructed sequences.

Analysis. Sequential training introduces the forgetting issue he-
etal-2021-analyzing; chen-etal-2020-recall, where models recall sets trained
on later in the sequence more effectively than earlier ones. (a.) With column-
wise averages, we capture how easy a perturbation $\pi_{j}$ is to learn by
fine-tuning on other perturbations by testing improvement in accuracy on set
Qj. Therefore in the order col-asc, an "easier" perturbation appears later and
hence improves the average performance. (b.) With row-wise averages, we
capture how much fine-tuning on Pj improves the overall performance of other
perturbation types. Hence, in the order row-asc with samples from Pj wherein
$\pi_{j}$ has a higher score appearing later, benefit other better
perturbation more effectively. Additionally, in both scenarios, the
performance for C and S decreases as they appear earlier in the sequence.

Mix. Table 6 presents the outcomes from multi-set inoculation using mixed
training.

| Original Sets | Challenge Sets |
---|---|---|---
k | $\boldsymbol{\alpha_{1}}$ | $\boldsymbol{\alpha_{2}}$ | $\boldsymbol{\alpha_{3}}$ | char | neg | num | loc | stan | $\boldsymbol{\mu}$
baseline | 72.72 | 64.83 | 62.33 | 57.30 | 46.90 | 67.20 | 70.20 | 67.10 | -
100 | 70.40 | 65.16 | 59.48 | 56.00 | 58.48 | 78.78 | 78.50 | 66.04 | 5.82
200 | 70.42 | 65.06 | 59.21 | 56.86 | 59.50 | 80.94 | 80.36 | 64.68 | 6.73
300 | 71.92 | 64.54 | 59.49 | 56.50 | 61.30 | 81.22 | 79.68 | 65.12 | 7.02
400 | 72.11 | 64.48 | 59.78 | 56.58 | 63.70 | 81.60 | 80.38 | 64.64 | 7.64
500 | 72.62 | 64.34 | 59.20 | 56.98 | 66.06 | 82.02 | 80.52 | 65.64 | 8.50

Table 6: Mix Results : RoBERTa${}_{\text{\sc InfoTabs}}$ finetuned on a mixed
set of samples from different perturbation sets Pj.

Analysis. Models trained via mixed training outperform those from SEQ. As we
increase the number of samples for fine-tuning, we notice consistent gains
across most challenge sets and original test sets. The most prominent
improvements are seen in the negation and location sets. While there’s a minor
performance dip in some original and challenge sets, it’s less pronounced
compared to results from single-set inoculation and SEQ.

DynMix. Table 7 displays the results from dynamic mixed training. The sample
ratio of $0.201:0.245:0.182:0.200:0.172$ for $C:N:M:L:S$ was determined based
on the inverse of baseline performance values (i.e., poorer baseline
performance warrants more samples from that perturbation set).

| Original Sets | Challenge Sets |
---|---|---|---
k | $\boldsymbol{\alpha_{1}}$ | $\boldsymbol{\alpha_{2}}$ | $\boldsymbol{\alpha_{3}}$ | char | neg | num | loc | stan | $\boldsymbol{\mu}$
baseline | 72.72 | 64.83 | 62.33 | 57.30 | 46.90 | 67.20 | 70.20 | 67.10 | -
500 | 71.28 | 64.42 | 60.39 | 56.26 | 59.22 | 77.84 | 76.24 | 65.38 | 5.25
1000 | 71.07 | 64.72 | 59.60 | 57.04 | 63.24 | 79.94 | 79.06 | 65.50 | 7.22
1500 | 72.07 | 64.81 | 59.73 | 56.50 | 65.42 | 80.84 | 79.54 | 65.64 | 7.85

Table 7: DynMix Results: RoBERTa${}_{\text{\sc InfoTabs}}$ fine tuned on
$\boldsymbol{K}$ samples taken from all perturbation sets in ratio
$0.201:0.245:0.182:0.200:0.172$ for $C:N:M:L:S$.

Analysis. Though the dynamic mixed training surpasses SEQ, it only edges out
the mixed training approach when utilizing a total of 1000 and 1500 samples
for fine-tuning (see table 6 for k = 200, 300). This suggests that dynamically
adjusting the challenge set size can enhance unimodel multi-set inoculation
outcomes.

In summary, multi-set inoculation proves more effective than its single-set
counterpart in cultivating robust models. Further, the Mix and DynMix
strategies for fine-tuning across multiple challenge sets stand out as more
resilient compared to Seq.

###  4.2 Results: LLMs

We present results on Zero-Shot(OP${}_{\text{ZS}}$), Few-
Shot(OP${}_{\text{COT}}$), Single Exemplars Multiple Prompts (SEMP), Multiple
Exemplars Multiple Prompts(MESP) are shown in Table 8, 9, 10 and 12.

Set | Model | char | neg | num | loc | stan | avg.
---|---|---|---|---|---|---|---
Original Sets from R’ | Flan-t5-small | 39.30 | 48.60 | 39.30 | 59.60 | 47.00 | 46.76
Flan-t5-base | 55.60 | 63.60 | 55.60 | 68.00 | 58.60 | 60.28
Flan-t5-large | 70.60 | 75.00 | 64.60 | 77.00 | 71.60 | 71.76
Flan-t5-XL | 72.30 | 76.30 | 66.70 | 78.60 | 75.30 | 73.84
Flan-t5-XXL | 70.60 | 77.30 | 69.00 | 74.00 | 79.00 | 73.98
LLaMA-2-13b | 51.33 | 54.00 | 49.67 | 62.33 | 53.00 | 54.07
LLaMA-2-70b | 59.00 | 63.60 | 64.60 | 67.00 | 60.00 | 62.84
GPT-3.5 | 68.00 | 69.00 | 68.66 | 71.60 | 70.00 | 69.45
Challenge Sets from R | Flan-t5-small | 33.00 | 40.00 | 49.30 | 71.00 | 47.00 | 48.06
Flan-t5-base | 44.00 | 54.00 | 55.60 | 68.60 | 58.00 | 56.04
Flan-t5-large | 54.00 | 66.00 | 62.30 | 65.00 | 67.60 | 62.98
Flan-t5-XL | 63.00 | 68.00 | 64.00 | 66.00 | 71.30 | 66.46
Flan-t5-XXL | 63.00 | 70.00 | 63.00 | 65.00 | 69.30 | 66.06
LLaMA-2-13b | 39.67 | 39.33 | 45.67 | 56.67 | 44.67 | 45.20
LLaMA-2-70b | 54.00 | 51.60 | 49.60 | 57.00 | 54.30 | 53.30
GPT-3.5 | 51.00 | 53.00 | 62.66 | 61.00 | 60.30 | 57.59

Table 8: Zero Shot Results (OP${}_{\text{ZS}}$): Baseline accuracy for LLMs
for Original prompts in zero-shot setting.

Type | Model | char | neg | num | loc | stan | $R^{\prime}$
---|---|---|---|---|---|---|---
BASE | llama-2-70b | 54.00 | 51.60 | 49.60 | 57.00 | 54.30 | 62.84
llama-2-13b | 39.67 | 39.33 | 45.67 | 56.67 | 44.67 | 45.20
gpt-3.5 | 51.00 | 53.00 | 62.66 | 61.00 | 60.30 | 69.45
OP${}_{\text{COT}}$ | llama-2-70b | 63.00 | 60.00 | 63.00 | 61.30 | 66.00 | 70.82
llama-2-13b | 61.33 | 57.00 | 57.67 | 59.33 | 60.00 | 64.27
gpt-3.5 | 63.00 | 69.60 | 59.30 | 61.00 | 68.00 | 72.18

Table 9: Few-shot with COT (OP${}_{\text{COT}}$). Results for Original Prompt
using chain of thought prompting with exemplars sampled from Original dataset.

Original Prompt. Table 8 and 9 shows the results for Original Zero-Shot
Prompts (OP${}_{\text{ZS}}$ and Few-shot with COT 444We used 6 demonstrations
for OP${}_{\text{COT}}$ (OP${}_{\text{COT}}$),respectively.

Analysis. • On the Original Zero-Shot Prompts we observe that,  (a.) Comparing
the results of challenge datasets Rj and their unperturbed version sets R’j
reveals that LLMs similar to PLMs are also sensitive to input data
perturbations.  (b.) However, the Flan-T5 series, specifically XL and XXL,
performs significantly better than other LLMs as it’s fine-tuned specifically
for the NLI task chung2022scaling. Even the drop in performance due to data
perturbation is relatively less.  (c.) The poor performance of relatively
smaller LLMs, such as LLaMA-2-13b, demonstrates the ineffectiveness of such
models in responding to an instruction prompt555LLaMA-2-13b often labeled
examples as Neutral (N), even when the reasoning was correct..  (d.) One
reason for performance on original numerical set (R’M), is due to model
inability to handle mathematical reasoning (wallace2019nlp; min2021recent;
hendrycks2021measuring; imani-etal-2023-mathprompter). Additionally, we find
that all models enhanced with COT (Table 9) outperform those using Zero Shot
original prompts. This suggests that simply adding exemplars can enhance a
model’s resilience to perturbations.

##### Single Exemplars Multiple Prompts (SEMP)

: Table 10 presents results for GPT-3.5, with diagonal elements as an analogue
to single set inoculation. LLaMA-2 results can be found in Table 11666For
SEMP, we utilized three demonstrations from the challenge set and three from
the original set..

Prompt Test | char | neg | num | loc | stan | $R^{\prime}$
---|---|---|---|---|---|---
baseline | 51.00 | 53.00 | 62.66 | 61.00 | 60.30 | 69.05
char | 67.60 | 65.30 | 66.00 | 69.00 | 67.60 | 68.05
neg | 60.30 | 64.60 | 58.00 | 59.60 | 63.30 | 71.62
num | 62.30 | 66.30 | 61.00 | 60.60 | 64.30 | 70.24
loc | 62.60 | 63.60 | 61.00 | 59.30 | 64.00 | 71.30
stan | 59.00 | 67.60 | 61.30 | 61.00 | 67.30 | 73.76

Table 10: Single Exemplars Multiple Prompts (SEMP) Results: The last column is
the average performance on all sets of R′ which is representative of the
original unperturbed set.

Analysis. From Tables 10 and 11, it’s evident that incorporating an input
perturbation explanation within the prompt enhances the model’s accuracy. The
results in Table 10 suggest that even a singular perturbation explanation
prompts the model to anticipate other perturbations, essentially priming it
for a noisy environment. This adaptability is especially pronounced for
character perturbations, where improvements span across all challenge sets.
When juxtaposed with instructional prompt outcomes, it becomes clear that
pairing demonstrations with perturbation descriptions bolsters performance.

set $\pi_{j}$ | char | neg | num | loc | stan
---|---|---|---|---|---
R${}^{\prime}_{j}baseline$ | 59.00 | 63.60 | 64.60 | 67.00 | 60.00
R${}^{\prime}_{j}$ | 69.00 | 71.00 | 72.00 | 72.30 | 68.60
R${}_{j}baseline$ | 54.00 | 51.60 | 49.60 | 57.00 | 54.30
Rj | 53.00 | 58.00 | 62.00 | 62.00 | 68.30

Table 11: Single Exemplars Multiple Prompts on llama-2-70b: We only perform
self-testing on same perturbation type $\pi_{j}$ with prompt for $\pi_{j}$ and
test on Rj and R’j.

We note a correlation between semantic (N, S) perturbations, which modify
sentence meaning, and syntactic (C, M, L) perturbations, which alter specific
words in a sentence. Demonstrations from PC prompt the model to refine the
hypothesis before drawing an inference, leading to notable improvements in RC,
RM, and RL. Similarly, when provided with details about $\pi_{S}$, we see
marked performance gains on RN.

##### Multiple Exemplars Multiple Prompts (MESP)

:The results for Mixed-Prompting-Instructional and Mixed-Prompting-Exemplar
are shown in Table 12.

Model | Type | char | neg | num | loc | stan | $R^{\prime}$
---|---|---|---|---|---|---|---
llama-2 | Base | 39.67 | 39.33 | 45.67 | 56.67 | 44.67 | 45.20
MESP${}_{\text{{MPI}}}$ | 58.33 | 51.33 | 59.67 | 55.00 | 62.33 | 62.53
MESP${}_{\text{{MPE}}}$ | 60.97 | 56.67 | 59.33 | 60.67 | 62.00 | 65.67
gpt-3.5 | Base | 51.00 | 53.00 | 62.66 | 61.00 | 60.30 | 69.45
MESP${}_{\text{{MPI}}}$ | 59.60 | 65.30 | 62.00 | 59.00 | 59.60 | 68.76
MESP${}_{\text{{MPE}}}$ | 70.00 | 63.60 | 58.30 | 60.00 | 66.80 | 72.52

Table 12: Mixed Prompting Results on LLMs. llama-2-13b and gpt-3.5: We report
the average performance of each model for unpertubed set(R’).

Analysis. Both models show marked improvement with mixed prompting777We use 10
demonstrations for gpt-3.5 in the MESP${}_{\text{MPI}}$ setting and 15 in the
MESP${}_{\text{MPE}}$ setting. For LLaMA-2, we used 8 demonstrations in
MESP${}_{\text{MPI}}$ setting and 11 in the MESP${}_{\text{MPE}}$ setting,
indicating that LLMs, when guided with perturbation descriptions and examples,
yield more stable outputs. The superior performance of Mixed-Prompting-
Exemplar over Mixed-Prompting-Instructional suggests that including more
examples in prompts is more beneficial than detailed perturbation
descriptions.

In conclusion, LLMs too face challenges with input perturbations. Merely
describing a single perturbation in prompts primes the LLM to contemplate
other perturbation forms. Our results emphasize that a mixed prompting
strategy, blending ample perturbation examples with succinct explanations,
bolsters prompt resilience.

##  5 Related Works

##### Robustness to Adversarial Examples.

Deep learning models in vision mahmood2021robustness; elsayed2018adversarial
and language chang2021robustness; ren2019generating; mccoy-etal-2019-right;
wang2021infobert display sensitivity to adversarial examples. Ensuring model
robustness wang2021measure; wang-etal-2020-cat is crucial for credibility.
Small input perturbations can dramatically affect performance due to model
complexity and overfitting glockner-etal-2018-breaking; rice2020overfitting;
zhu-rao-2023-exploring; moradi2021evaluating. While fine-tuning on adversarial
examples tong2022robust; liu-etal-2019-inoculation; yuan-etal-2023-hype can
mitigate some effects, it doesn’t guarantee broad robustness. Distinctly, our
approach investigates multi-dataset fine-tuning, offers a comprehensive
robustness framework, and extends insights to LLMs through chain-of-thought
prompting.

##### Tabular Datasets and Models.

Research on semi-structured tabular data has delved into tasks like tabular
natural language inference, fact verification (chen2019tabfact; gupta-
etal-2020-infotabs; Zhang:2019:ADC), and more. Techniques for improving
tabular inference include pre-training methods (yu2018spider; yu2020grappa;
eisenschlos2020understanding; neeraja-etal-2021-infotabskg). Moreover,
recently shared tasks such as SemEval’21 Task 9 (semeval_2021:task9) and
FEVEROUS’21 (aly2021feverous) have expanded upon these topics.

##  6 Conclusion and Future Works

We demonstrate that input perturbation poses difficulties for language models
at all scales. While finely tuned models on single challenge sets can produce
robust models, their generalizability to unfamiliar perturbations remains
questionable. This motivates the problem of multi-set inoculation, aiming to
train a singular model resilient to a myriad of distinct perturbations. To
this end, we introduce a comprehensive framework to evaluate language model
robustness against multiple input perturbations systematically. In addition,
we propose three strategies to fine-tune the model on multiple challenge sets.
Our results underscore the superiority of mixed training in training robust
models. Furthermore, we augment our framework to encompass large language
models (LLMs), leveraging a ’chain of thought’ prompting strategy enriched
with exemplar demonstrations.

##### Future Directions:

We consider the following future directions:  (a.) Expansion to Various NLP
Tasks:Our framework, initially for language model robustness, can extend to
tasks like question-answering and sentiment classification, which we plan to
explore.  (b.) Complex Sample Selection Strategies:While we haven’t used
advanced sample selection strategies yet, insights from roh2021sample;
swayamdipta2020dataset suggest ways to enhance model robustness during fine-
tuning, which we intend to explore.  (c.) Composite Perturbation Approach:We
aim to explore the successive application of multiple perturbations on a
single sample, represented as $\pi_{i}(\pi_{j}(x))$, to understand their
combined impact on model performance.  (d.) Instructional Fine-tuning on
LLMs:In our current study, we haven’t explored the effects of instructional
fine-tuning on large language models (LLMs) within challenge sets, a domain
with potential valuable insights into LLM behavior.

## Ethics Statement

We, the authors of this work, affirm that our work complies with the highest
ethical standards in research and publication. In conducting this research, we
have considered and addressed various ethical considerations to ensure the
responsible and fair use of computational linguistics methodologies. We
provide detailed information to facilitate the reproducibility of our results.
This includes sharing code, datasets (in our case, we deal with publicly
available datasets and comply with the ethical standards mentioned by the
authors of the respective works.), and other relevant resources to enable the
research community to validate and build upon our work. The claims in the
paper match the experimentation results. However, a certain degree of
stochasticity is expected with black-box large language models, which we
attempt to minimize by keeping a fixed temperature. We describe in the fullest
detail the annotations, dataset splits, models used, and prompting methods
tried, ensuring the reproducibility of our work.


# Lottery Tickets in Linear Models: An Analysis of Iterative Magnitude Pruning

Bryn Elesedy
Department of Computer Science
University of Oxford &Varun Kanade
Department of Computer Science
University of Oxford &Yee Whye Teh
Department of Statistics
University of Oxford Correspondence to<EMAIL_ADDRESS>
###### Abstract

We analyse the pruning procedure behind the lottery ticket hypothesis [4],
_iterative magnitude pruning_ (IMP), when applied to linear models trained by
gradient flow. We begin by presenting sufficient conditions on the statistical
structure of the features under which IMP prunes those features that have
smallest projection onto the data. Following this, we explore IMP as a method
for sparse estimation.

##  1 Introduction

The lottery ticket hypothesis [4] asserts that a randomly initialised, densely
connected feed-forward neural network contains a sparse sub-network that, when
trained in isolation, attains equal or higher accuracy than the full network.
These sub-networks are called _lottery tickets_ and the method used to find
them is iterative magnitude pruning (IMP). A network is given a random
initialisation, trained by some form of gradient descent for a specified
number of iterations and a proportion of its smallest weights (by absolute
magnitude) are deleted. The remaining weights are then reset to their
initialised values and the network is retrained. This procedure can be
performed multiple times, resulting in a sequence of sparse yet trainable sub-
networks.111These sub-networks are _weight_ sub-networks, formed by setting to
0 entries of the weight matrices (edges in the graph). This is in contrast to
the neuron pruning, which removes entire neurons (nodes in the graph). All
mentions of sub-network in this paper refer to weight sub-networks.

This simple procedure gives quite surprising results. The sub-networks
uncovered by IMP are trainable from their original initialisation and achieve
accuracies comparable with, and often better than, the full network. The same
sub-networks perform poorly when reinitialised [4]. Moreover, as observed in
[18], many of the sub-networks found by IMP have better than random test loss
at initialisation, suggesting that IMP has some ability to select good
inductive biases for a problem. These results point to avenues for better
computational and memory efficiency in neural networks, as well as to
properties of deep networks and their training dynamics that we do not fully
understand. In particular, it is not yet known why weight magnitude provides a
good signal on which to base a pruning heuristic in neural networks. In other
words, why is IMP effective in neural networks?

Our paper aims to address this question for linear models, with the hope that
this will lay the groundwork for similar study in neural networks. We make a
minor adaptation to the version of IMP used in [4], shown in Algorithm 1, the
difference being that in Algorithm 1 we consider pruning one weight per
iteration, while in [4] a proportion of the weights are pruned. It is
straightforward to extend our results to the latter case. It is similarly easy
to modify them to discrete time gradient descent with appropriate step sizes.

Input: Loss function $L:\mathbb{R}{}^{p}\to\mathbb{R}$, training time
$T\in\mathbb{R}{}_{+}$, initialisation
$\bm{w}^{\text{init}}\in\mathbb{R}{}^{p}$, iterations of pruning $q<p$.

Output: $\bm{w}^{(q)}(T)$

1 Set $M=\mathbb{I}_{p}$

2 for  _$k=0$ to q_ do

3 Initialise $\bm{w}^{(k)}(0)=M\bm{w}^{\text{init}}$

4 Train $\dot{\bm{w}}^{(k)}(t)=-M\nabla L(\bm{w}^{(k)}(t))$ for $t\in[0,T]$

5 Set
$i=\operatorname*{argmin}_{j\in[p]}\left\\{\left|{}w^{(k)}_{j}(T)\right|{}:M_{jj}=1\right\\}$

6 Set $M_{ii}=0$

7

8return $\bm{w}^{(q)}(T)$

Algorithm 1 Iterative Magnitude Pruning

###  1.1 Related Work

The lottery ticket hypothesis [4] has sparked a lot of interest. Already,
there are more follow up works than it is possible to cover in this article.
To name a few: more reliable discovery of lottery tickets in deep networks
with rewinding [5], generalising lottery tickets across tasks [12],
constructing networks that perform well with random weights [18, 6], pruning
at initialisation [7] and finding lottery tickets in randomly weighted
networks [15]. For an empirical comparison of various pruning methods see [1].

Theoretical work has mainly focussed on lottery tickets at at initialisation.
[10] showed that any continuous function can be approximated by a sub-network
of a sufficiently large, randomly weighted neural network. Following this,
there is a body of work on the approximation properties of lottery tickets at
initialisation [13, 14]. The theory relating to IMP is relatively undeveloped,
which is a key motivation for this paper.

We note some similarities between IMP and methods in compressive sensing,
which is a subfield of signal processing that attempts to find sparse
reconstructions of noisy signals. For a systematic review see [16] and for a
comprehensive discussion of thresholding and similar denoising techniques see
[11, Chapter 11]. Most similar to IMP are two well known thresholding methods
that we discuss below, each of which attempts to recover a sparse signal
$\bm{s}\in\mathbb{R}{}^{p}$ from noise corrupted measurements
$\bm{y}\in\mathbb{R}{}^{n}$.

Hard thresholding, studied in the wavelet basis by [3], performs least-squares
estimation $\hat{\bm{s}}$ of $\bm{s}$ and then applies elementwise to
$\hat{\bm{s}}$ the thresholding operator
$H_{\tau}(z)=\mathds{1}\left\\{\left|{}z\right|{}>\tau\right\\}z$. Iterative
hard thresholding [2] consists of linear projection of $\bm{s}$ onto a feature
matrix $\Psi\in\mathbb{R}{}^{n\times p}$ and then iteratively solving the
linear system $\bm{y}=\Psi\bm{s}$, thresholding the solution at each stage.
Specifically, iterative hard thresholding estimates $\bm{s}$ by $\hat{\bm{s}}$
using the update rule
$\hat{\bm{s}}_{i}^{n}=H_{\tau}(\hat{\bm{s}}^{n}_{i}+\eta\Psi^{\top}(\bm{y}-\Psi\hat{\bm{s}}^{n}_{i}))$
with initialisation chosen by the user and where $\eta$ is a step size. The
argument of $H_{\tau}$ is exactly the update from gradient flow on the squared
error loss
$\frac{1}{2}\left\lVert\bm{y}-\Psi\hat{\bm{s}}\right\rVert_{2}^{2}$. IMP can
therefore be viewed as a variation of iterative hard thresholding, where the
threshold operator is replaced by the restriction to a subset of indices that
is chosen at time $T$ of each training run.

###  1.2 Setup and Notation

We write $[n]$ for the set $\\{1,\dots,n\\}$. Let the training inputs be
$\bm{x}_{1},\,\dots,\,\bm{x}_{n}$ and targets be
$y_{1},\,\dots,\,y_{n}\in\mathbb{R}$. For the parameters we write
$\bm{w}\in\mathbb{R}{}^{p}$ and the features are written $\phi_{i}(\bm{x})$
for $i\in[p]$. In this work we consider the training data and features to be
deterministic, but it is possible to extend our main result to a random design
setting. Let $X\in\mathbb{R}{}^{n\times d}$ and $\bm{y}\in\mathbb{R}{}^{n}$ be
the usual row stacking of the training examples and write
$\Phi\in\mathbb{R}{}^{n\times p}$ for the row stacking of the features. For
each $i\in[p]$, write $\phi_{i}(X)\in\mathbb{R}{}^{n}$ for the vector with
components $(\phi_{i}(\bm{x}_{1}),\,\dots,\,\phi_{i}(\bm{x}_{n}))^{\top}$. A
linear model is any predictor
$f_{\bm{\theta}}(\bm{x})=\bm{\theta}^{\top}\bm{\phi}(\bm{x})$ that is linear
in the features, where $\bm{\theta}\in\mathbb{R}{}^{p}$ are the learned
parameters. The features can be arbitrary non-linear functions, for instance,
the outputs of the penultimate layer of a pre-trained neural network (with
earlier weights fixed) or gradients of a neural network at initialisation as
with linearised networks [9]. Write $\Sigma=\frac{1}{n}\Phi^{\top}\Phi$ for
the empirical covariance matrix and notice that
$\Sigma_{ij}=\frac{1}{n}\phi_{i}(X)^{\top}\phi_{j}(X)$. We write $\Sigma^{+}$
for the Moore-Penrose pseudo-inverse of $\Sigma$ and
$\lambda_{\text{max}}=\left\lVert\Sigma\right\rVert_{2}$ for its operator
norm.222We define the Moore-Penrose pseudo-inverse of $\Sigma$ as the matrix
that is diagonal in any basis in which $\Sigma$ is diagonal and has
eigenvalues $\gamma_{i}$ $i=1,\dots,p$ where $\gamma_{i}=0$ if $\lambda_{i}=0$
and $\gamma_{i}=1/\lambda_{i}$ otherwise, where $\lambda_{i}$ $i=1,\dots,p$
are the eigenvalues of $\Sigma$. For any matrix $A$, let
$\lambda_{\text{min}}^{\scaleobj{0.75}{\neq 0}}(A)$ denote the smallest non-
zero eigenvalue of $A$. Recall that at each iteration of Algorithm 1 the
diagonal matrix $M\in\mathbb{R}{}^{p\times p}$ records the weights pruned so
far, that is $M_{ij}=\mathds{1}\left\\{i=j\,\land\,w_{i}\text{ not yet
pruned}\right\\}$. Pruning can be seen as either removing features entirely
(so reducing the dimension of $\Phi$) or setting to 0 the corresponding
weights or column of $\Phi$ (but preserving all the dimensions). For the work
in this paper these perspectives are equivalent and we will use each
description interchangeably.

##  2 Warm Up: Pruning Heuristic of IMP

In this section we give an analysis to demonstrate that, given some
statistical assumptions on the features, IMP preferentially prunes the
features that explain the data the least in terms of linear projections. We
call this pruning heuristic the _alignment heuristic_. Specifically, the
alignment heuristic prunes $w_{i}$ where
$i=\operatorname*{argmin}_{j}\\{\left|{}\phi_{j}(X)^{\top}\bm{y}\right|{}:M_{jj}=1\\}$.
We consider examples of various $\Sigma$ and examine the pruning heuristic
that arises. For now we assume that $\Sigma$ is full rank, so training to
convergence with
$L(\bm{w})=\frac{1}{2n}\left\lVert\Phi\bm{w}-\bm{y}\right\rVert_{2}^{2}$ gives
$\bm{w}^{(i)}(\infty)=\frac{1}{n}\Upsilon_{i}^{-1}P_{i}^{\top}\bm{y}$ where
$\Upsilon_{i}$ and $P_{i}$ are, respectively, the restrictions of $\Sigma$ and
$\Phi$ to the parameters not yet pruned at iteration $i$ of Algorithm 1.
$\Upsilon_{i}$ will always be invertible as long as $\Sigma$ is invertible,
which follows from the Cauchy interlace theorem and $\Sigma$ being positive
definite. We will relax our notation back to $\Sigma$ and $\Phi$ for the
following examples, with the understanding that each of these results apply
for each iteration of Algorithm 1, restricting the matrices accordingly. In
particular, it should be noted that in the following examples the conditions
on $\Sigma$ transfer to conditions on $\Upsilon_{i}$ and $P_{i}$. Finally, for
the rest of this section we normalise the features so that $\Sigma_{ii}=1$
$\forall i\in[p]$.

######  Example 1 ($\Sigma=\mathbb{I}$).

Gradient flow converges to
$n\,w_{i}(\infty)=\Sigma^{-1}\Phi^{\top}\bm{y}=\phi_{i}(X)^{\top}\bm{y}$.
According to Algorithm 1 the weight then pruned is $w_{i}$ where
$i=\operatorname*{argmin}_{j\in[p]}\\{|{}w^{(i)}_{j}(\infty)|{}:M_{jj}=1\\}$.
We see immediately that this is equivalent to the alignment heuristic.

######  Example 2 (Uniform correlations).

We express

$\Sigma=\mathbb{I}+\alpha(\bm{1}\bm{1}^{\top}-\mathbb{I})$

for $\alpha\in(0,1)$, where $\bm{1}={(1,1,\dots,1)}^{\top}\in\mathbb{R}^{p}$.
We can use the Sherman-Morrison formula to calculate

$\Sigma^{-1}=\frac{1}{1-\alpha}\mathbb{I}-\frac{\alpha(1-\alpha)}{1+\alpha(p-1)}\bm{1}\bm{1}^{\top}$

and we see that

$n\,w_{i}(\infty)=\frac{1}{1-\alpha}\phi_{i}(X)^{\top}\bm{y}-\frac{\alpha(1-\alpha)}{1+\alpha(p-1)}\sum_{j}\phi_{j}(X)^{\top}\bm{y}.$

We conclude that, if $\alpha\ll 1$ is small enough, then Algorithm 1 will
prune according to the alignment heuristic. The case $\alpha\approx 1$ gives
this outcome too, but in this case $\Sigma$ is barely invertible. Intuitively,
in the case $\alpha\approx 1$ the features are similar and pruning one is as
good as pruning another.

######  Example 3 (Pairwise incoherence).

We say that $\Phi$ satisfies the pairwise incoherence assumption with
parameter $\delta_{\text{PW}}$ if

$\delta_{\text{PW}}=\max_{i,j}\left|{}\frac{1}{n}(\Phi^{\top}\Phi)_{ij}-\mathds{1}\left\\{i=j\right\\}\right|{}.$

Assume that this is the case. Write $\Sigma=\mathbb{I}-A$, then formally we
have

$\Sigma^{-1}=(\mathbb{I}-A)^{-1}=\sum_{j=0}^{\infty}A^{j}.$

Note that $a\coloneqq\left\lVert A\right\rVert_{2}\leq\sqrt{\left\lVert
A\right\rVert_{1}\left\lVert
A\right\rVert_{\infty}}\leq(p-1)\,\delta_{\text{PW}}$ by Hölder’s inequality,
where $\left\lVert\cdot\right\rVert_{2}$ denotes the operator norm when acting
on a matrix. Taking $\delta_{\text{PW}}<1/(p-1)$ therefore ensures that the
series converges in operator norm. Also, provided the above series converges,
we have

$\left\lVert\sum_{k=2}^{\infty}A^{k}\right\rVert_{2}\leq\frac{a^{2}}{1-a}.$

If $a\ll 1$ we can write $\Sigma^{-1}\approx\mathbb{I}+A$. This gives

$n\,w_{i}(\infty)\approx\phi_{i}(X)^{\top}\bm{y}+\sum_{j\neq
i}A_{ij}\phi_{j}(X)^{\top}\bm{y}.$

The alignment heuristic will be followed if the magnitude of the first term
dominates that of the second, which is $O(\delta_{\text{PW}})$. Therefore,
given a suitable pairwise incoherence assumption, Algorithm 1 prunes according
to the alignment heuristic.

##  3 Support Recovery with IMP

Empirically, IMP has been found to result in sparse yet performant sub-
networks. In this section we explore this phenomenon analytically in the
context of linear models, where the natural application is to sparse
estimation. In our analysis we will make use of a strengthened form of the
restricted nullspace property [17].

######  Definition 4 (Orthogonal nullspace property).

Let $S\subset[p]$ be a subset of indices. Define the cone

$C(S)=\\{\bm{x}\in\mathbb{R}{}^{p}:\left\lVert\bm{x}_{S^{\text{c}}}\right\rVert_{1}\leq\left\lVert\bm{x}_{S}\right\rVert_{1}\\}$

where $\bm{x}_{Q}$ are the components of $\bm{x}$ with indices in $Q$. A
matrix $A$ acting on $\mathbb{R}{}^{p}$ satisfies the _orthogonal nullspace
property_ with respect to $S$ if all elements of the nullspace of $A$ are
orthogonal to all elements of $C(S)$

$\text{null}(A)\perp C(S).$

Notice that the cone $C(S)$ is the set of vectors whose 1-norm on the index
set $S$ dominates that on the other indices $S^{\text{c}}$. In particular, a
sparse signal supported on $S$ will belong to $C(S)$. In the context of
Theorem 5, the above condition ensures that the signal $\bm{s}$ is
recoverable. We now present our sparse estimation result for Algorithm 1.

######  Theorem 5 (Sparse Estimation with IMP).

Assume that $\bm{y}=\Phi\bm{s}+\bm{\xi}$ for $\bm{s}\in\mathbb{R}{}^{p}$ and
that $\\{\xi_{i}$: $i=1,\dots,p\\}$ are independent, zero mean sub-Gaussian
random variables with variance proxy $\sigma^{2}$. Let
$\Sigma\coloneqq\frac{1}{n}\Phi^{\top}\Phi$ and let
$\lambda_{\text{min}}^{\scaleobj{0.75}{\neq 0}}>0$ be the smallest non-zero
eigenvalue of $\Sigma$, which we assume to exist. Suppose that $\bm{s}$ is
$k$-sparse and supported on a set $S\subset[p]$ with $\left|{}S\right|{}=k$,
and that $\Sigma$ satisfies the orthogonal nullspace property with respect to
$S$. Let
$L(\bm{w})=\frac{1}{2n}\left\lVert\Phi\bm{w}-\bm{y}\right\rVert_{2}^{2}$ be
the mean squared error loss. Consider running Algorithm 1 with $L$,
$\bm{w}^{\text{init}}=\bm{0}$, $T=\infty$ and $q\leq p-k$, and denote the
output by $\bm{v}$. Let $\gamma>0$, if

$n\geq\frac{8\sigma^{2}}{\gamma^{2}\lambda_{\text{min}}^{\scaleobj{0.75}{\neq
0}}}\log(2p/\delta)$

then, with probability at least $1-\delta$ we have

  1. (i)

$\bm{v}$ is at least $(p-q)$-sparse.

  2. (ii)

No false exclusion above $\gamma$: $v_{i}\neq 0$ for any $i$ with
$\left|{}s_{i}\right|{}\geq\gamma$.

###### Proof.

Point (i) is obvious. We establish point (ii). Consider the first iteration of
Algorithm 1. Let $V$ be the column space of $\Sigma$. Since $\Sigma$ satisfies
the orthogonal nullspace condition with respect to the support of $\bm{s}$, we
know that the projection of $\bm{s}$ on to $V$ is $\bm{s}$. By diagonalising,
we can see that $\Sigma^{+}\Sigma$ is exactly this projection. Training until
convergence therefore gives

$w_{i}(\infty)=s_{i}+\frac{1}{n}(\Sigma^{+}\Phi^{\top}\bm{\xi})_{i}.$

Then on this iteration we can be sure not to prune any $i$ with
$\left|{}s_{i}\right|{}\geq\gamma$ if

$\frac{1}{n}\left|{}\left(\Sigma^{+}\Phi^{\top}\bm{\xi}\right)_{i}\right|{}<\gamma/2\quad\forall\,i.$

By Lemma 6, this happens with probability at least $1-\delta$ if
$n\geq\frac{8\sigma^{2}}{\gamma^{2}\lambda_{\text{min}}^{\scaleobj{0.75}{\neq
0}}}\log(2p/\delta).$ To demonstrate (ii), we show that this is sufficient to
guarantee (with high probability) that no $i$ with
$\left|{}s_{i}\right|{}\geq\gamma$ is pruned on any iteration of Algorithm 1.
We conclude the proof with this argument.

Let $\Upsilon$ be the sub-matrix of $\Sigma$ formed by removing the rows and
columns with indices $i_{1},\dots,i_{k}$ $k<p$, let $P$ be the sub-matrix of
$\Phi$ by removing the same columns. The orthogonal nullspace condition on
$\Sigma$ means that the restriction of $\bm{s}$ has no component in the null
of $\Upsilon$ at any iteration. Hence, we need only show that

$\frac{1}{n}\left|{}(\Upsilon^{+}P^{\top}\bm{\xi})_{i}\right|{}<\gamma/2.$

Again by Lemma 6, this happens with probability at least $1-\delta$ if
$n\geq\frac{8\sigma^{2}}{\gamma^{2}\lambda_{\text{min}}^{\scaleobj{0.75}{\neq
0}}(\Upsilon)}\log(2p/\delta).$ $\Sigma$ is symmetric, so we may apply
Cauchy’s interlace theorem (see [8], Theorem 4.3.17) to obtain
$\lambda_{\text{min}}^{\scaleobj{0.75}{\neq
0}}(\Upsilon)\geq\lambda_{\text{min}}^{\scaleobj{0.75}{\neq 0}}(\Sigma)$. The
proof is complete. ∎

This result tells us that if we have $n=O(\gamma^{-2}\log(2p/\delta))$ samples
then, with high probability, IMP can recover the support of a sparse signal
wherever it has magnitude at least twice the noise level
$\nicefrac{{\gamma}}{{2}}$. It is not possible to place guarantees on recovery
of components with magnitude smaller than $\gamma$ without assumptions on the
relative sizes of the components of $\bm{s}$. It should be straightforward to
modify Theorem 5 to account for random features by a bound on
$\lambda_{\text{min}}^{\scaleobj{0.75}{\neq 0}}$.

##  4 Discussion

We have shown that IMP can recover the support of a sparse signal under mild
assumptions on the design matrix and we gave bounds for the estimation error
in this setting. Further work may seek to extend the results of this paper to
neural networks, a tractable route for which might be found using linearised
networks [9]. Alternatively, it may be interesting to consider random
features.

## Acknowledgments and Disclosure of Funding

We thank Sheheryar Zaidi and Bobby He for helpful feedback on early versions
of this work. We would also like to thank Zhanyu Wang for pointing out two
errors in a previous version of this work. BE is supported by the UK EPSRC CDT
in Autonomous Intelligent Machines and Systems (grant reference EP/L015897/1).
VK is supported in part by the Alan Turing Institute under the EPSRC grant
EP/N510129/1.

##  Appendix A Sub-Gaussian Concentration

######  Lemma 6.

Define $\Phi\in\mathbb{R}{}^{n\times p}$ and $\Sigma\in\mathbb{R}{}^{p\times
p}$ with $\Sigma^{+}$ the Moore-Penrose pseudo-inverse of $\Sigma$ and
$\lambda_{\text{min}}^{\scaleobj{0.75}{\neq 0}}$ the non-zero eigenvalue of
$\Sigma$ that is smallest in absolute magnitude (which we assume exists). Let
$\bm{\xi}\in\mathbb{R}{}^{n}$ be a vector with elements $\xi_{i}$ that are iid
sub-Gaussian with zero mean and variance proxy $\sigma^{2}$. If
$n\geq\frac{2\sigma^{2}}{\epsilon^{2}\lambda_{\text{min}}^{\scaleobj{0.75}{\neq
0}}}\log(2p/\delta)$ then with probability at least $1-\delta$ we have
$\max_{j}\left|{}\frac{1}{n}(\Sigma^{+}\Phi^{\top}\bm{\xi})_{j}\right|{}<\epsilon$.

###### Proof.

Define $\bm{\alpha}=\frac{1}{n}\Sigma^{+}\Phi^{\top}\bm{\xi}$. Let
$A=\frac{1}{n}\Sigma^{+}\Phi^{\top}$, then it is straightforward to check
that, for any $i$, $\alpha_{i}=\sum_{j}A_{ij}\xi_{j}$ is sub-Gaussian with
variance proxy $\sigma^{2}\sum_{j}A_{ij}^{2}$. In addition to this, we have

$\sum_{j}A_{ij}^{2}=(AA^{\top})_{ii}=\frac{1}{n}\Sigma^{+}_{ii}\leq\frac{1}{n}\max_{ij}\left|{}\Sigma^{+}_{ij}\right|{}\leq\frac{1}{n}\left\lVert\Sigma^{+}\right\rVert_{2}=\frac{1}{n\lambda_{\text{min}}^{\scaleobj{0.75}{\neq
0}}},$

So the standard tail bound gives, for any $i$,
$\mathbb{P}\lparen\left|{}\alpha_{i}\right|{}>\epsilon\rparen\leq
2\exp\left(-\frac{n\lambda_{\text{min}}^{\scaleobj{0.75}{\neq
0}}\epsilon^{2}}{2\sigma^{2}}\right)$ and the conclusion follows from a union
bound. ∎

## References

  * [1] Davis Blalock, Jose Javier Gonzalez Ortiz, Jonathan Frankle and John Guttag  “What is the State of Neural Network Pruning?”  In _arXiv preprint arXiv:2003.03033_ , 2020
  * [2] Thomas Blumensath and Mike E Davies  “Iterative thresholding for sparse approximations”  In _Journal of Fourier analysis and Applications_ 14.5-6 Springer, 2008, pp. 629–654
  * [3] David L Donoho and Jain M Johnstone  “Ideal spatial adaptation by wavelet shrinkage”  In _biometrika_ 81.3 Oxford University Press, 1994, pp. 425–455
  * [4] Jonathan Frankle and Michael Carbin  “The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks”  In _ICLR_ , 2019
  * [5] Jonathan Frankle, G Karolina Dziugaite, DM Roy and M Carbin  “Stabilizing the Lottery Ticket Hypothesis”  In _arXiv_ , 2019
  * [6] Adam Gaier and David Ha  “Weight Agnostic Neural Networks”  In _Advances in Neural Information Processing Systems 32_ Curran Associates, Inc., 2019, pp. 5364–5378
  * [7] Soufiane Hayou, Jean-Francois Ton, Arnaud Doucet and Yee Whye Teh  “Robust Pruning at Initialization”  In _arXiv preprint arXiv:2002.08797_ , 2020
  * [8] Roger A Horn and Charles R Johnson  “Matrix analysis”  Cambridge university press, 2012
  * [9] Jaehoon Lee et al.  “Wide neural networks of any depth evolve as linear models under gradient descent”  In _Advances in neural information processing systems_ , 2019, pp. 8570–8581
  * [10] Eran Malach, Gilad Yehudai, Shai Shalev-Schwartz and Ohad Shamir  “Proving the lottery ticket hypothesis: Pruning is all you need”  In _International Conference on Machine Learning_ , 2020, pp. 6682–6691  PMLR
  * [11] Stephane Mallat  “A Wavelet Tour of Signal Processing: The Sparse Way”  Academic Press, 2008
  * [12] Ari Morcos, Haonan Yu, Michela Paganini and Yuandong Tian  “One ticket to win them all: generalizing lottery ticket initializations across datasets and optimizers”  In _Advances in Neural Information Processing Systems 32_ Curran Associates, Inc., 2019, pp. 4932–4942
  * [13] Laurent Orseau, Marcus Hutter and Omar Rivasplata  “Logarithmic pruning is all you need”  In _Advances in Neural Information Processing Systems_ 33, 2020
  * [14] Ankit Pensia et al.  “Optimal lottery tickets via subsetsum: Logarithmic over-parameterization is sufficient”  In _arXiv preprint arXiv:2006.07990_ , 2020
  * [15] Vivek Ramanujan et al.  “What’s Hidden in a Randomly Weighted Neural Network?”  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2020
  * [16] Meenu Rani, SB Dhok and RB Deshmukh  “A systematic review of compressive sensing: Concepts, implementations and applications”  In _IEEE Access_ 6 IEEE, 2018, pp. 4875–4894
  * [17] Martin J Wainwright  “High-dimensional statistics: A non-asymptotic viewpoint”  Cambridge University Press, 2019
  * [18] Hattie Zhou, Janice Lan, Rosanne Liu and Jason Yosinski  “Deconstructing Lottery Tickets: Zeros, Signs, and the Supermask”  In _Advances in Neural Information Processing Systems 32_ Curran Associates, Inc., 2019, pp. 3597–3607