# BufferSearch: Generating Black-Box Adversarial Texts With Lower Queries

Wenjie Lv1 Zhen Wang1 Yitao Zheng1 Zhehua Zhong1 Qi Xuan2&Tianyi Chen3
1Hangzhou Dianzi University
2Zhejiang University of Technology
3Microsoft
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Machine learning security has recently become a prominent topic in the natural
language processing (NLP) area. The existing black-box adversarial attack
suffers prohibitively from the high model querying complexity, resulting in
easily being captured by anti-attack monitors. Meanwhile, how to eliminate
redundant model queries is rarely explored. In this paper, we propose a query-
efficient approach BufferSearch to effectively attack general intelligent NLP
systems with the minimal number of querying requests. In general, BufferSearch
makes use of historical information and conducts statistical test to avoid
incurring model queries frequently. Numerically, we demonstrate the
effectiveness of BufferSearch on various benchmark text-classification
experiments by achieving the competitive attacking performance but with a
significant reduction of query quantity. Furthermore, BufferSearch performs
multiple times better than competitors within restricted query budget. Our
work establishes a strong benchmark for the future study of query-efficiency
in NLP adversarial attacks.

##  1 Introduction

In the recent years, Deep Neural Networks (DNNs) have been shown to be
effective in a variety of natural language processing applications, such as
machine translation, fake news detection, question answering, and sentiment
analysis Fan et al. (2021); Minaee et al. (2021); Zhong et al. (2023).
Meanwhile, the security of DNNs is receiving increasing attentions, since they
have been proved to be easily confused by adversarial samples by slightly
perturbing the original input Szegedy et al. (2014).

In general, there are two ways to fool NLP models via adversarial attack ,
i.e., white-box and black-box attack Zhang et al. (2021). The white-box attack
can access almost every aspects of the target model including the training
dataset, architecture and parameters, which are not transparent to the black-
box settings instead Wang et al. (2021). In practice, black-box attack is more
applicable since such inherent underlying information may be not accessible.
However, the success of the existing state-of-the-art black-box attackers
highly relies on querying the victim model sufficient many times Yoo et al.
(2020); Hossam et al. (2021a). Such massive model queries might be easily
detected by the anti-attack security system thereby still not convenient in
reality.

How to achieve efficient black-box NLP attack with the minimal number of model
queries now becomes an open and hot problem. In fact, the heavy model queries
derive from the two main stages of NLP black-box attacks, i.e., one stage to
calculate and rank word salience followed by another stage to employ
prescribed transformation onto the important words. Both stages contribute a
fair amount of model queries. To achieve high query efficiency, there are two
recent works concentrating on the first stage to optimize the important word
selection. In particular, E2A Hossam et al. (2021a) trains an interpretable
agent model to learn word salience scores by using a substitute training
corpora within the similar fields of the target model. Hossam et al. (2021b)
further improves the training process in E2A Hossam et al. (2021a). However,
to the best of our knowledge, there is no work to eliminate redundant model
queries on the second stage i.e., perform word transformation on the important
tokens.

On the other hand, in the related computer vision (CV) field, there exist a
few works that establish Bayesian attackers to reduce query complexity by
leveraging the historical information Zhao et al. (2019); Ru et al. (2019),
wherein they assume a Gaussian distribution to the perturbation variable and
determine its hype-parameters via Bayesian optimization. However, these
approaches cannot be easily extended to NLP tasks because of the discreteness
of the perturbation space.

In this paper, we study how to optimize the model query over the second stage
(word transformation stage) and propose a BufferSearch to effectively attack
NLP applications with significant amount of model query reduction. Our main
contributions are summarized as follows.

Algorithmic Design. We are the first work to optimize model queries of the
word transformation stage in the general black-box NLP adversarial attacks.
The proposed BufferSearch delicately makes use of historical attacking
information and conducts statistical test to avoid unnecessary model queries
effectively. As a result, BufferSearch fools the target model effectively
without incurring high query complexity.

Numerical Benchmark. We numerically demonstrate the effectiveness of
BufferSearch on the benchmark text classification experiments, across
different model architectures and various datasets. BufferSearch more
adequately leverages each model query than state-of-the-art competitors. As a
result, under unconstrained model query budget, BufferSearch dramatically
avoids 32.6% queries in average and achieves competitive adversarial attacking
performance. Furthermore, under constrained query budget, BufferSearch
outperforms others by attaining multi-times better attacking performance.

##  2 Related Work

###  2.1 Two Stage Attack In NLP

Most of the existing black-box word-based attackers consist of two main stages
to generate adversarial examples. Specifically, the first stage calculates
salience scores for each individual word based on various criteria. For
example, Gao et al. (2018) designs four scoring functions based model
prediction, i.e., Replace-1, Temporal Head, Temporal Tail and Combined Score.
Li et al. (2019), Ren et al. (2019), Ma et al. (2020), Jin et al. (2020) and
Goodman et al. (2020) compute the importance of word as the confidence score
deviation after deletion. The tokens are then sorted via the importance score
and fed into the second stage, wherein prescribed word transformation are
employed on the selected tokens with significant impact onto the prediction.
Both stages accompanies numerous model queries to compute either the salience
score or the impact of each transformation.

###  2.2 Query Efficiency in Black-Box NLP Attack

The query-efficiency study in NLP black-box adversarial attack is quite
limited. To the best of our knowledge, there are only a few related works. Two
of them focus on optimizing the first-stage discussed in Section 2.1. In
particular, E2A Hossam et al. (2021a) trains an interpretable agent model to
learn word importance scores on substitute training corpus from similar fields
of the target model. Hossam et al. (2021b) follows the same procedure but
improves the training process of E2A. Although both methods reduce the model
query complexity, the performance of such approaches might be sensitive to the
dataset selection and training quality. Furthermore, conducting such
additional training requires lots of extra efforts, which is typically not
convenient and scalable to large-scale intelligent NLP systems Brown et al.
(2020). Transfer-based attackers can generate adversarial samples without
accessing the target victim model He et al. (2021); Wang et al. (2022), but
have the same drawbacks as E2A. Recently, Berger et al. (2021) generates
adversarial samples within low model queries by random sampling, but such
method fails on large-scale document set such as IMDB which limits its
generality.

###  2.3 Query Efficiency in Black-Box CV Attack

In the field of computer vision black-box adversarial attack, the query
efficiency has been developed to some extent. Bhagoji et al. (2018) partitions
pixels into small groups and conduct group-wise queries. Then all pixels in
one group operate the same perturbation based on the shared query. Papernot et
al. (2017); Liu et al. (2017); Ma et al. (2021); Suya et al. (2020); Wang et
al. (2020) avoid querying target model by accessing substitute model instead,
while the construction of the substitution is costly and time-consuming. Cheng
et al. (2018) reduces model queries by forming zeroth order optimization. Li
et al. (2020) points out that the high query cost of black box attack is due
to the high dimension of image input, and proposes an attack method based on
dimension reduction. Chen et al. (2020) improves boundary attack by leveraging
gradient estimation of decision boundary. Because of the discreteness of text
space, these successful attack methods in CV are difficult to transfer to NLP
area directly.

##  3 Query Efficient Adversarial Attack

###  3.1 Target Problem Formulation

In this section, we formulate the target problem of query-efficient
adversarial attack for general natural language processing security tasks. To
the best of our knowledge, such target problem is rarely well formulated
across related computer vision and natural language processing applications.

For general NLP tasks, we aim at establishing an attacker $\mathcal{A}$ such
that given a victim text set $\mathcal{X}$, for each text $X\in\mathcal{X}$,
the attacker $\mathcal{A}$ consumes the minimal number of model queries
$\mathcal{Q}(\mathcal{A},\mathcal{M},X)$ to fool the model $\mathcal{M}$
Considering the popular classification problem, each document
$X\in\mathcal{X}$ is associated with a ground truth label $Y_{X}$. The target
problem becomes

$\small\begin{split}\mathop{\text{minimize}}\limits_{\mathcal{A}}\
\sum_{X\in\mathcal{X}}\mathcal{Q}(\mathcal{A},\mathcal{M},X),\text{s.t.}\
\mathcal{M}(\mathcal{A}(X))\neq Y_{X}\ \text{for}\
X\in\mathcal{X},\end{split}$ (1)

where the adversarial document $\mathcal{A}(X)$ yields a wrongly predicted
label by the model, i.e., $\mathcal{M}(\mathcal{A}(X))\neq Y_{X}$. However,
problem (1) is typically intractable in practice since the constraint is
usually hard to achieve for every document. As an alternative, we consider the
following more relaxable unconstrained problem,

$\small\begin{split}\mathop{\text{minimize}}\limits_{\mathcal{A}}\
&\sum_{X\in\mathcal{X}}\mathcal{Q}(\mathcal{A},\mathcal{M},X)-\lambda
r(\mathcal{A},\mathcal{M},X),\end{split}$ (2)

where $r(\mathcal{M},\mathcal{A},X)$ is a regularization term Chen et al.
(2022, 2021a, 2021b) that measures the deviation of label between ground truth
and adversarial example, e.g., $\|\mathcal{M}(\mathcal{A}(X))-Y_{X}\|_{2}$,
and $\lambda$ is some positive weighting parameter.

The majority of black-box adversarial attack in NLP tasks are two-stage
attackers as discussed in Section 2.1, i.e., the first-stage picks up
important words and the second-stage proceeds various attack on these
candidates. Both stages require numerous model queries. Consequently, the
total number of queries equals to the summation of quantity from both stages.
In this paper, we concentrate on optimizing the cost of model query in the
second stage, i.e., $\mathcal{Q}_{2}(\mathcal{A},\mathcal{M},X)$ is free to be
optimized. Therefore, the target problem becomes

$\small\mathop{\text{minimize}}\limits_{\mathcal{A}}\
\sum_{X\in\mathcal{X}}\mathcal{Q}_{2}(\mathcal{A},\mathcal{M},X)-\lambda
r(\mathcal{A},\mathcal{M},X).$ (3)

###  3.2 Overview

To the best of our knowledge, we are the first to study optimizing the cost of
model querying in the word transformation stage of black-box NLP attacks. To
solve problem (3), the proposed algorithm is stated in Algorithm 1. In
general, given a set of victim texts $\mathcal{X}$ and a target model
$\mathcal{M}$, we iteratively attack each text $X$ in $\mathcal{X}$ and
collect the intermediate information to form a table $\mathcal{T}$ as stated
in Algorithm 2. Within each individual adversarial attack, we leverage the
collected historical information $\mathcal{T}$ to refine the search space and
avoid unnecessary model queries as Algorithm 3. As a result, we obtain the set
of adversarial texts $\mathcal{X}_{\text{adv}}$ with much fewer number of
queries than the existing methods.

Algorithm 1 Query-Efficient Adversarial Attack

Input: A set of victim texts $\mathcal{X}$ with the ground truth labels
$\mathcal{Y}$, target model $\mathcal{M}$, sentence similarity `Sim(·)`,
attack ratio $\epsilon$ and candidate list ratio $\gamma\in(0,1]$.
Output: A set of adversarial examples $\mathcal{X}_{\text{adv}}$.

1: Construct an empty table $\mathcal{\mathcal{T}}$ to store historical
adversarial attack information.

2: for each text $X$ in $\mathcal{X}$ and label $Y$ in $\mathcal{Y}$ do

3: Get adversarial text $X_{\text{adv}}$ and update $\mathcal{T}$ via
Algorithm 2.
$X_{\text{adv}}\leftarrow\text{Attack}(X,Y,\mathcal{M},\mathcal{T},\verb|Sim|,\epsilon,\gamma).$

4: $\mathcal{X}_{\text{adv}}\leftarrow\mathcal{X}_{\text{adv}}\bigcup
X_{\text{adv}}$.

5: return  $\mathcal{X}_{\text{adv}}$.

Similarly to other state-of-the-arts black-box attackers, we design a two-
stage algorithm for generating each individual adversarial text. In
particular, the first stage picks up a set of words with high importance from
the victim text $X$ based on various criteria as line 3-5 in Algorithm 2. Then
in the second stage, the words are iterated by their ranked salience scores
and transformed by some prescribed mechanisms to yield the ultimate
adversarial example as line 6-19 in Algorithm 2, wherein the transformations
reply on the collected historical information $\mathcal{T}$ as shown Algorithm
3. All replacement information is fed into the table $\mathcal{T}$ for further
usage as line 8-7 in Algorithm 2.

###  3.3 Word Importance Calculation

In the stage one, we calculate the word salience score following the state-of-
the-art ranker proposed in Textfooler Jin et al. (2020). In particular,
suppose a victim text of $n$ words as
$X\text{=\\{}w_{1},w_{2},...,w_{n}\text{\\}}$. To calculate the importance of
$w_{i}$, i.e., $I(w_{i})$, we at first delete $w_{i}$ from $X$ to form
$X/\\{w_{i}\\}\text{=\\{}w_{1},...,w_{i-1},w_{i+1},...,w_{n}\text{\\}}$.
Following Textfooler, the $I(w_{i})$ has the following explicit forms.
$\mathbin{\vbox{\hbox{\scalebox{0.75}{$\bullet$}}}}$ Suppose the predicted
label remains the same after deletion, i.e.,
$\mathcal{M}(X)=\mathcal{M}\left(X/\\{w_{i}\\}\right)=Y_{X}$,

$I(w_{i})=\mathcal{M_{Y_{X}}}(X)-\mathcal{M_{Y_{X}}}\left(X/\\{w_{i}\\}\right).$
(4)

$\mathbin{\vbox{\hbox{\scalebox{0.75}{$\bullet$}}}}$ Suppose the predicted
label is changed after deletion, i.e.,
$\mathcal{M}(X)={Y_{X}}\neq{\hat{Y}_{X}}=\mathcal{M}(X/\\{w_{i}\\})$,

$\begin{split}I(w_{i})=&\mathcal{M}_{Y_{X}}(X)-\mathcal{M}_{Y_{X}}\left(X/\\{w_{i}\\}\right)+\\\
&\mathcal{M}_{\hat{Y}_{X}}(X)-\mathcal{M}_{\hat{Y}_{X}}\left(X/\\{w_{i}\\}\right),\end{split}$
(5)

where $\mathcal{M}(X)$ represents the predicted label of $X$ by model
$\mathcal{M}$, and $\mathcal{M}_{Y_{X}}(X)$ represents the predicted
confidence score of $X$ by $\mathcal{M}$ on label $Y_{X}$.

###  3.4 Query-Efficient Transformation Attack

In the second stage, given the set of words with high importance
$\mathcal{W}^{*}$ from the first stage, we iterate the ranked words by their
importance scores and perform a word replacement mechanism, wherein a proper
word replacement should (i) have similar semantic meaning with the original,
and (ii) confuse the target model to make wrong prediction.

Word Transformation. Without loss of generality, consider the most popular
synonym transformation as an illustrating example. For $w\in\mathcal{W}^{*}$,
we at first establish the candidate set for replacement of $w$
$\mathcal{C}(w)$ from $\mathcal{S}(w)$ via Algorithm 3. Then as line 18-19 of
Algorithm 2, during each replacement, we accomplish the replacement of $w$ as
the candidate $c^{*}\in\mathcal{C}(w)$ achieving the largest deviation of
prediction distribution,

$c^{*}:=\mathop{\operator@font{argmax}}_{c\in\mathcal{C}(w)}\
\mathcal{M}_{Y_{X}}(X_{\text{adv}})-\mathcal{M}_{Y_{X}}(X_{\text{adv},w\to
c})$ (6)

Consequently, the adversarial example $X_{\text{adv}}$ is constructed either
after all words in $\mathcal{W}^{*}$ are exhausted and replaced by
corresponding best synonym as (6) or until the attack has been succeeded in
advance as line 13-16 of Algorithm 2.

The existing state-of-the-art methods solve problem (6) by bruce-force
exploiting the whole synonym space, i.e.,
$\mathcal{C}(w)\equiv\mathcal{S}(w)$, so that calculating the prediction
deviation requires $|\mathcal{S}(w)|$ model queries totally for each
$w\in\mathcal{W}^{*}$. Thus the overall procedure performs
$\sum_{w\in\mathcal{W}^{*}}|\mathcal{S}(w)|$ model queries for the worst case,
while there may exist numerous redundant queries to be optimized.

Pruning Transformation Space. To increase the efficiency of word replacement,
we prune the feasible space of transformation by identifying redundant word
candidates to avoid potential unnecessary queries. Rather than utilizing the
whole synonym set $\mathcal{S}(w)$, we establish the candidate set
$\mathcal{C}(w)$ as a subset of $\mathcal{S}(w)$ which exhibits the largest
prediction deviation in the history and has high confidence to be significant
again verified via an efficient sorting algorithm and a statistical test.

To proceed, we at first initialize the candidate list of $w$ as
$C_{\text{initial}}$ from the global table $\mathcal{T}$ associated with the
previous attack information $\mathcal{H}(w,c)$ as line 5-6 in Algorithm 3,
wherein $\mathcal{H}(w,c)$ represents the history of confidence score changes
of replacing $w$ by $c$. Given a prescribed candidate list budget
$\gamma\in(0,1]$, we pick up a pivot candidate $c_{\text{pivot}}\in
C_{\text{initial}}$ which has the
$\lceil\gamma|\mathcal{C}_{\text{initial}}|\rceil$th largest confidence score
deterioration in average as line 8 in Algorithm 3. The pivot candidate
$c_{\text{pivot}}$ serves as the benchmark instance to filter out the
candidates that are less likely to confuse the target model.

We then iterate all candidates from $\mathcal{C}_{\text{initial}}$. For each
candidate $c$, a statistical test is employed to determine if $c$ can affect
the model more significantly than the pivot candidate $c_{\text{pivot}}$ as
line 9. For simplicity, we represent the impact of replacement from $w$ to $c$
and $c_{\text{pivot}}$ as $\mu_{c}$ and $\mu_{\text{pivot}}$, respectively.
Then, we propose to use the following one-sided test,

$\text{null:}\mu_{c}\leq\mu_{\text{pivot}}\ \text{vs. alternative:}\
\mu_{c}>\mu_{\text{pivot}}.$

To test these hypotheses, we make use of the historical $\mathcal{H}(w,c)$ and
$\mathcal{H}(w,c_{\text{pivot}})$. Since these two populations to be compared
may have unequal variance, Welch’s two-sample one-tail t-test is performed
here Welch (1947). In particular, given the samples from $\mathcal{H}(w,c)$
and $\mathcal{H}(w,c_{\text{pivot}})$, we at first compute the t-statistic as

$t=\frac{\widebar{\mathcal{H}}(w,c)-\widebar{\mathcal{H}}(w,c_{\text{pivot}})}{\sqrt{{\hat{\sigma}_{c}^{2}}/{|\mathcal{H}(w,c)|}+{\hat{\sigma}_{c_{\text{pivot}}}^{2}}/{|\mathcal{H}(w,c_{\text{pivot}})|}}},$
(7)

where the $\bar{(\cdot)}$ and $\hat{\sigma}^{2}$ represent the sample mean and
the variance estimator, respectively. Given a prescribed significance level
$\alpha$, we then figure out the $(1-\alpha)$ quantile of the student’s
t-distribution with degree of freedom corresponding to that in the variance
estimator, denoted as $t_{\alpha}^{*}$. Next, we reject the null hypothesis if
$t\geq t_{\alpha}^{*}$. If we fail to reject the null hypothesis that the
impact of $c$ is less than that of $c_{\text{pivot}}$, then $c$ should be
excluded from further consideration since replacing $w$ as $c$ largely
generate negligible model confusion. Otherwise, we accept the alternative
hypothesis of higher affect by $c$ and include it into the ultimate candidate
list $\mathcal{C}(w)$ as line 10-11.

Complexity Analysis. We here compare the complexity of model query by our
proposed transformation attack. Since for each word $w\in\mathcal{W}^{*}$, we
proceed a model-query-free statistical approach to filter out numerous
negligible candidates. The remaining candidates after pruning quantize up to
$\gamma|\mathcal{S}(w)|$, which result in an upper bound for the overall model
query quantity as $\sum_{w\in\mathcal{W}^{*}}\gamma|\mathcal{S}(w)|$.
Comparing to the $\sum_{w\in\mathcal{W}^{*}}|\mathcal{S}(w)|$ of the existing
state-of-the-art methods, our method performs linearly faster in the manner of
model query in theory and will be further verified in Section 4.

Algorithm 2 Black Box Adversarial Attack

Input: Victim text $X$, ground truth label $Y$, target model $\mathcal{M}$,
table $\mathcal{\mathcal{T}}$, similarity function $\text{Sim}(\cdot)$, and
ratio $\epsilon,\gamma\in(0,1]$ for words and candidates selection.
Output: Adversarial example $X_{\text{adv}}$.

1: Initialize $X_{\text{adv}}\leftarrow X$.

2: Pre-process $X$ and get target word set $\mathcal{W}$.

3: for each word $w$ in $X$ do

4: Compute the importance score $I(w)$.

5: Set $\mathcal{W}^{*}$ by the top $\lfloor\epsilon|\mathcal{W}|\rfloor$
words from $\mathcal{W}$ via $I(w)$.

6: for each word $w$ in $W$ do

7: Get the candidate list $\mathcal{C}_{w}$ from Algorithm 3.
$\mathcal{C}_{w}\leftarrow\text{CANDIDATE\\_LIST}(w,\mathcal{T},Y,\gamma).$

8: Get the recent soft label
$\hat{y}_{\text{adv}}\leftarrow\mathcal{M}_{Y}(X_{\text{adv}})$.

9: for each candidate $c$ in $\mathcal{C}_{w}$ do

10: $\hat{X}_{c}\leftarrow\text{Replace}\ w\ \text{with}\ c\ \text{in}\
X_{\text{adv}}$.

11: Get hard/soft label $\mathcal{M}(\hat{X}_{c})$ and
$\hat{y}_{c}\leftarrow\mathcal{M}_{Y}(\hat{X}_{c})$.

12: Update
$\mathcal{T}[w,Y,c]\leftarrow\mathcal{T}[w,Y,c]\bigcup(\hat{y}_{\text{adv}}-\hat{y}_{c}).$

13: if there exists $c\in\mathcal{C}_{w}$ such that
$\mathcal{M}(\hat{X}_{c})\neq Y$ then

14: Get the successful attack set
$\mathcal{C}_{\text{success}}\subseteq\mathcal{C}_{w}$.

15:
$c^{*}\leftarrow\mathop{\operator@font{argmax}}_{c\in\mathcal{C}_{\text{success}}}\text{Sim}(X,\hat{X}_{c})$.

16: Return  $X_{\text{adv}}\leftarrow\hat{X}_{c^{*}}$.

17: else

18: Computer the best candidate $c^{*}$ via (6).

19: Replace $w$ with $c^{*}$ in $X_{\text{adv}}$.

20: Return $X_{\text{adv}}$.

Algorithm 3 Compute Candidate List

Input: Victim word $w$, historical table $\mathcal{T}$, attack label $Y$, and
budget parameter $\gamma$.
Output: A candidate list $\mathcal{C}({w})$.

1: if $(w,Y)$ not found in $\mathcal{T}$ then

2: Initialize the default candidate list $\mathcal{C}({w})$.

3: Return $\mathcal{C}(w)$.

4: Initialize $\mathcal{C}(w)\leftarrow\emptyset$.

5: Get $\mathcal{C}_{\text{initial}}\leftarrow\text{the word list of}\
\mathcal{T}(w,Y)$.

6: Get history $\mathcal{H}(w,c)$ for each $c\in\mathcal{C}_{\text{initial}}$.

7: Set $c_{\text{pivot}}$ as the pivot candidate with the
$\lceil\gamma|\mathcal{C}|_{\text{initial}}\rceil$th largest average
historical score.

8: for each $c\in\mathcal{C}_{\text{initial}}$ do

9: Statistical test on $c_{\text{pivot}}$ impacts more than $c$ based on
$\mathcal{H}(w,c)$ and $\mathcal{H}(w,c_{\text{pivot}})$.

10: if null hypothesis is rejected then

11: Update $\mathcal{C}(w)\leftarrow\mathcal{C}(w)\bigcup c$.

12: Return $\mathcal{C}(w)$.

##  4 Experiments

###  4.1 Datasets and Target Models

To evaluate the effectiveness of our method, we apply BufferSearch on the
benchmark text classification task, which is perhaps the most popular and
representative task studied in NLP adversarial attack area Jin et al. (2020).
In particular, the experiments cover various datasets such as MR Pang and Lee
(2005), IMDB IMDB (Accessed on 2021) and Yelp Zhang et al. (2015) as well as
various model architectures ranging from WordCNN Kim (2014), WordLSTM
Hochreiter and Schmidhuber (1997) to BERT Devlin et al. (2019). Remark here
that though we demonstrate the effectiveness via text classification, our
method is generic to be extended to other scenarios with minimal
modifications.

###  4.2 Baselines

To quantitatively evaluate the performance, we compare BufferSearch with two
state-of-the-art adversarial attack methods PWWS Ren et al. (2019) and
Textfooler (TF) Jin et al. (2020) employed on the text classification tasks.
We include random.CS Berger et al. (2021) on IMDB to demonstrate the
generality of BufferSearch on reducing query complexity for various text
datasets. We exclude Hossam et al. (2021a, b), since their strategies focus on
the first stage and are complementary to our methodology.

###  4.3 Experimental Settings

In our black-box experiments, the attacker can only access the input text and
the output prediction (confidence scores) by querying the victim model. The
default candidate list in Algorithm 3 is set as the synonym set for each word,
which is constructed similarly to TF. Specifically, given the word embeddings
Mrkšić et al. (2016), we compute the cosine similarity across different
instances, then pick up the ones with top $N$ sufficiently high similarity
(greater than $\delta$) as the synonyms of each word. As other literatures, we
empirically set $N=50$ and $\delta=0.5$ Jin et al. (2020). The budget hyper-
parameter $\gamma$, which controls the number of candidate words, and the
significance level are set to be $0.3$ by default.

###  4.4 Automatic Evaluation Metrics

We evaluate the performance by four popular metrics. Adv Accuracy—the accuracy
of target model on the adversarial examples. Query Num—the number of model
queries during adversarial attack. Perturbation Rate—the rate of tokens
substituted in the origin texts. Semantic similarity—the semantic similarity
between the adversarial examples and the victim examples measured by the
popular open-source tool Cer et al. (2018). The first two measure the
effectiveness of adversarial attack, and the later ones measure the attack
invisibility.

###  4.5 Automatic Numerical Evaluation

The evaluation results of BufferSearch and strong baselines are reported in
Table 2 and 3, wherein the best numbers are marked as bold for the ease of
comparison. In general, our method achieves efficient and effective
adversarial attacks for all experiments with detailed descriptions as follows.

Efficiency. Compared to the state-of-the-art baselines, i.e., TF and PWWS,
BufferSearch requires significantly fewer model queries during the whole
attacking procedure. In particular, BufferSearch reduces the query cost by
32.6% in average across all experiments compared to TF, where a 42.2%
reduction is even achieved in the WordCNN on MR experiment. The superiority of
BufferSearch on query efficiency is due to the leverage of historical
information to avoid unnecessary queries in the second stage as shown in
Figure 2. PWWS is not comparable to BufferSearch and TF in terms of query
efficiency, which is $6-10$ times costly than our method. As drawn in Table 3,
random.CS fails to effectively attack IMDB(BERT) though achieves the lowest
query cost.

Effectiveness. Although BufferSearch dramatically reduces the model queries,
it still achieve outstanding attacking performance. Our method can greatly
fool all the three target models. Even for BERT with the best robustness, the
accuracy can be reduced from about 90% to no more than 12% on all benchmark
datasets. In fact, BufferSearch achieves the best (lowest) and the second best
After-Attack Accuracy on two and six out of nine experiments, respectively,
and competitive accuracy on the remaining one test with the gap less than
$1.1\%$. All methods perform closely in the manner of perturbation rate. For
example, BufferSearch is as low as 2.9% on the IMDB under WordCNN. That means
for a input containing 100 tokens, BufferSearch only needs to replace three
words or less to generate an adversarial output. Similar observations can be
found in the semantic similarity, which is inversely proportional to the
disturbance rate.

Discussion. Throughout the experiments, it is no doubt that BufferSearch is
the best in terms of query efficiency and attacking performance
comprehensively. The results demonstrate the effectiveness of our proposed
algorithm. On the other hand, although TF and PWWS consume dramatically more
resources to query the victim models, the gains they received on the attacking
performance are negligible. It consequently reveals the existence of numerous
query redundancy. We hope that BufferSearch establishes a baseline for future
studies to further push the boundary.

###  4.6 Human Evaluation

To further verify the quality of generated adversarial examples by
BufferSearch, we proceed additional human evaluation following the settings of
Jin et al. (2020). In particular, we designed three experiments in laboratory
environment to evaluate the following aspects. (i) Grammatical naturalness
score. We asked human judges to put a score (1-5) to evaluate the grammatical
validity of a sentence. (ii) Label prediction. We showed human judges $50$
samples randomly selected from MR training data, then asked them to classify
the motion adversarial example as either negative or positive. (iii) Semantic
similarity. We asked judges to put a score $0,0.5,1$ to evaluate the semantic
similarity between two sentences.

To proceed, we randomly selected $100$ adversarial samples generated on
dataset MR under BERT and their corresponding origin samples. Each experiment
was evaluated by 5 human judges, which average results are shown in Table 1.
As examples shown in Figure 1, the adversarial samples generated by
BufferSearch maintain the semantic information of origin input and
successfully fool the victim target model.

Figure 1: Adversarial samples generated by BufferSearch from MR (BERT) dataset. Target and replacement words are resp. in red and blue. The label predicted by BERT is changed. Text | origin text | adv text
---|---|---
Prediction accuracy | 72.3 | 65.2
Grammatical naturalness | 3.56 | 3.42
Semantic similarity | 0.869
Table 1: Average score of human evaluation. WordCNN
---
| MR | Yelp | IMDB
| TF | PWWS | BufferSearch | TF | PWWS | BufferSearch | TF | PWWS | BufferSearch
Original Accuracy | 78.0 | 78.0 | 78.0 | 94.0 | 94.0 | 94.0 | 89.2 | 89.2 | 89.2
Adv Accuracy | 1.2 | 1.4 | 1.5 | 0.1 | 1.1 | 1.2 | 0 | 0 | 0
% Perturbed | 12.6 | 10.9 | 12.7 | 6.4 | 5.7 | 7.7 | 2.5 | 2.2 | 2.9
Semantic Similarity | 0.963 | 0.960 | 0.957 | 0.989 | 0.989 | 0.987 | 0.998 | 0.998 | 0.997
Query Num | 97.7 | 285.1 | 52.3 | 384.3 | 1855.7 | 270.6 | 441 | 3302.7 | 345.5
WordLSTM
Original Accuracy | 80.7 | 80.7 | 80.7 | 96.0 | 96.0 | 96.0 | 89.8 | 89.8 | 89.8
Adv Accuracy | 1.1 | 2.1 | 1.2 | 0.4 | 2.1 | 1.7 | 0.3 | 0.6 | 0.3
% Perturbed | 12.9 | 11.2 | 13.1 | 7.2 | 8.1 | 9 | 3.1 | 3.1 | 3.7
Semantic Similarity | 0.960 | 0.960 | 0.955 | 0.987 | 0.984 | 0.983 | 0.997 | 0.996 | 0.995
Query Num | 99.1 | 285.9 | 52.3 | 429.8 | 1863.6 | 313.5 | 497.0 | 3306.6 | 385.1
BERT
Original Accuracy | 90.4 | 90.4 | 90.4 | 97.0 | 97.0 | 97.0 | 90.9 | 90.9 | 90.9
Adv Accuracy | 9.5 | 18.5 | 10.5 | 0.6 | 7.8 | 1.9 | 11.2 | 13.5 | 11.7
% Perturbed | 17.7 | 13.6 | 18.1 | 9.4 | 9.5 | 10.3 | 3.8 | 5.0 | 4.2
Semantic Similarity | 0.939 | 0.946 | 0.933 | 0.981 | 0.978 | 0.979 | 0.995 | 0.992 | 0.994
Query Num | 144.7 | 285.2 | 86.3 | 502.1 | 1811.7 | 347.4 | 693.8 | 3240.5 | 501.6
Table 2: Results under unlimited query budget. (Original Accuracy:the model prediction accuracy on $1000$ origin samples, Adv Accuracy:the model accuracy after attack, % Perturbed:the percentage of substitution of the original text, Semantic Similarity:the semantic similarity between original and adversarial samples, Query Num:the cost of query in attack, Average Text Length:the average length of original text.) | Ori Acc | Adv Acc | % Perturbed | Query Num
---|---|---|---|---
random.CS | 90.9 | 62.8 | 10.7 | 125.1
BufferSearch | 90.0 | 11.7 | 4.2 | 501.6
Table 3: BufferSearch versus random.CS on IMDB(BERT).

##  5 Discussion

(a) WordCNN

(b) WordLSTM

(c) BERT

Figure 2: Query cost comparison between TF and BufferSearch over WordCNN,
WordLSTM and BERT on MR, Yelp and IMDB.

###  5.1 Limited Query Budget Setting

Besides the setting of unlimited query budget in Section 4.5, we study the
performance of the attackers under restricted query budget $Q_{\text{max}}$’s.
This constraint forces the attacker to return adversarial examples within
$Q_{\text{max}}$ queries. We test a variety of $Q_{\text{max}}$’s from
$\\{30,90,150,300,450,750\\}$ for MR, and $\\{100,300,500,1000,1500,2500\\}$
for IMDB and Yelp. The performance is measured by the number of adversarial
examples that successfully fool the victim models. As displayed on Figure 3 ,
our method performs the best across all models and datasets. In particular,
BufferSearch performs multiple times better than TF and PWWS under low
$Q_{\text{max}}$’s. Then the successful attacking rates of all methods
converge as the query budget increases. These experiments serve as a strong
evidence that BufferSearch explored the word transformation space more
effectively than other competitors.

(a) MR

(b) Yelp

(c) IMDB

Figure 3: The number of adversarial samples generated under varying the query
budget $Q_{\text{max}}$ on BERT.

###  5.2 Different Size of Historical Information

To explore the impact of different size of historical information onto the
attacking performance of BufferSearch, we randomly select ten subsets with
size ranging from $10^{3}$ to $10^{4}$ from Yelp and IMDB test datasets, then
employ our method onto these subsets to collect historical tables. These
tables are then leveraged into attacking the original $10^{3}$ test samples
for evaluation. As drawn in Figure 4, there is slight but not significant
improvement when more historical information is leveraged. It reveals that
BufferSearch does not highly rely on the historical accumulation after
information saturation.

(a) IMDB

(b) Yelp

Figure 4: Attacking performance based on varying size of historical information IMDB (BERT(a)) and Yelp (WordLSTM(b)). |  | WordCNN | WordLSTM | BERT
---|---|---|---|---
MR | WordCNN | 1.5 | 54.0 | 85.7
WordLSTM | 51.3 | 1.2 | 84.5
BERT | 57.7 | 59.6 | 10.5
Yelp | WordCNN | 1.2 | 83.2 | 91.3
WordLSTM | 80.3 | 1.7 | 90.4
BERT | 85.0 | 85.1 | 1.9
IMDB | WordCNN | 0.0 | 76.0 | 84.2
WordLSTM | 81.0 | 0.3 | 81.7
BERT | 70.5 | 83.3 | 11.7
Table 4: Transferability of adversarial examples generated by row-wise models
and datasets then evaluated on column-wise models.

###  5.3 Transferability

The transferability of adversarial examples refers to the property that the
same input can successfully confuse different models Srivastava et al. (2014).
We evaluate the transferability on $3$ datasets across BERT, WordCNN and
WordLSTM. As shown in Table 4, the adversarial samples generated by attacking
one model fool other models to varying extents. BERT exhibits the best
robustness to transferable attacks.

###  5.4 Adversarial Training

In order to verify the effect of adversarial examples on model robustness, we
retrain the BERT on MR over the training set augmented by the adversarial data
generated by BufferSearch. We then employ BufferSearch on the retrained BERT
and report the results in Table 5. It is apparent that the model becomes more
robust to the adversarial attacks after adversarial training, since the after
attack accuracy, perturbation rate and query number significantly increased.

Adv Training | Accuracy (%) | # of queries | Perturbation
---|---|---|---
Original | Adv
✗ | 87.9 | 3.5 | 63.0 | 14.7
✓ | 85.9 | 14.1 | 81.6 | 16.1

Table 5: Attacking BERT with(out) adversarial training on MR.

##  6 Conclusion And Future Work

We propose a query efficient attack method BufferSearch on text classification
task in black-box setting. Extensive experiments show that BufferSearch can
generate high quality adversarial samples with significantly fewer queries.
Our work establishes baselines for the future query efficient attack studies
in NLP related tasks.

## References

  * Berger et al. [2021] N Berger, S Riezler, et al.  Don’t search for a search method—simple heuristics suffice for adversarial text attacks.  In EMNLP, 2021.
  * Bhagoji et al. [2018] A Bhagoji, W He, et al.  Practical black-box attacks on deep neural networks using efficient query mechanisms.  In ECCV, 2018.
  * Brown et al. [2020] T Brown, Benjamin M, et al.  Language models are few-shot learners, 2020.
  * Cer et al. [2018] D Cer, Y Yang, et al.  Universal sentence encoder, 2018.
  * Chen et al. [2020] J Chen, M Jordan, et al.  Hopskipjumpattack: A query-efficient decision-based attack.  In SP, 2020.
  * Chen et al. [2021a] Tianyi Chen, Tianyu Ding, Bo Ji, Guanyi Wang, Yixin Shi, Jing Tian, Sheng Yi, Xiao Tu, and Zhihui Zhu.  Orthant based proximal stochastic gradient method for $\ell_{1}$-regularized optimization.  In Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2020, Ghent, Belgium, September 14–18, 2020, Proceedings, Part III, pages 57–73. Springer, 2021.
  * Chen et al. [2021b] Tianyi Chen, Bo Ji, Tianyu Ding, Biyi Fang, Guanyi Wang, Zhihui Zhu, Luming Liang, Yixin Shi, Sheng Yi, and Xiao Tu.  Only train once: A one-shot neural network training and pruning framework.  Advances in Neural Information Processing Systems, 34:19637–19651, 2021.
  * Chen et al. [2022] Tianyi Chen, Luming Liang, DING Tianyu, Zhihui Zhu, and Ilya Zharkov.  Otov2: Automatic, generic, user-friendly.  In The Eleventh International Conference on Learning Representations, 2022.
  * Cheng et al. [2018] M Cheng, T Le, et al.  Query-efficient hard-label black-box attack: An optimization-based approach.  In ICLR, 2018.
  * Devlin et al. [2019] J Devlin, M Chang, et al.  Bert: Pre-training of deep bidirectional transformers for language understanding.  In NAACL-HLT, 2019.
  * Fan et al. [2021] A Fan, S Bhosale, et al.  Beyond english-centric multilingual machine translation.  jmlr, 2021.
  * Gao et al. [2018] J Gao, J Lanchantin, et al.  Black-box generation of adversarial text sequences to evade deep learning classifiers.  In SPW, 2018.
  * Goodman et al. [2020] D Goodman, L Zhonghou, et al.  Fastwordbug: A fast method to generate adversarial text against nlp applications, 2020.
  * He et al. [2021] X He, L Lyu, et al.  Model extraction and adversarial transferability, your BERT is vulnerable!  In NAACL-HLT, 2021.
  * Hochreiter and Schmidhuber [1997] S Hochreiter and J Schmidhuber.  Long short-term memory.  Neural Computation, 1997.
  * Hossam et al. [2021a] M Hossam, T Le, et al.  Explain2attack: Text adversarial attacks via cross-domain interpretability.  In ICPR, 2021.
  * Hossam et al. [2021b] M Hossam, T Le, et al.  Improved and efficient text adversarial attacks using target information, 2021.
  * IMDB [Accessed on 2021] IMDB.  https://datasets.imdbws.com/, Accessed on 2021.
  * Jin et al. [2020] D Jin, Z Jin, et al.  Is bert really robust? a strong baseline for natural language attack on text classification and entailment.  In AAAI, 2020.
  * Kim [2014] Y Kim.  Convolutional neural networks for sentence classification.  In EMNLP, 2014.
  * Li et al. [2019] J Li, S Ji, et al.  Textbugger: Generating adversarial text against real-world applications.  NDSS, 2019.
  * Li et al. [2020] H Li, X Xu, et al.  Qeba: Query-efficient boundary-based blackbox attack.  In CVPR, 2020.
  * Liu et al. [2017] Y Liu, X Chen, et al.  Delving into transferable adversarial examples and black-box attacks.  In ICLR, 2017.
  * Ma et al. [2020] G Ma, H Yan, et al.  Adversarial text generation via probability determined word saliency.  In MLCS, 2020.
  * Ma et al. [2021] C Ma, S Cheng, et al.  Switching transferable gradient directions for query-efficient black-box adversarial attacks, 2021.
  * Minaee et al. [2021] S Minaee, N Kalchbrenner, et al.  Deep learning–based text classification: A comprehensive review.  CSUR, 2021.
  * Mrkšić et al. [2016] N Mrkšić, D Ó Séaghdha, et al.  Counter-fitting word vectors to linguistic constraints.  In NAACL-HLT, 2016.
  * Pang and Lee [2005] B Pang and L Lee.  Seeing stars: Exploiting class relationships for sentiment categorization with respect to rating scales.  In ACL, 2005.
  * Papernot et al. [2017] N Papernot, P McDaniel, et al.  Practical black-box attacks against machine learning.  In ASIA CCS, 2017.
  * Ren et al. [2019] S Ren, Y Deng, et al.  Generating natural language adversarial examples through probability weighted word saliency.  In ACL, 2019.
  * Ru et al. [2019] B Ru, A Cobb, et al.  Bayesopt adversarial attack.  In ICLR, 2019.
  * Srivastava et al. [2014] N Srivastava, G Hinton, et al.  Dropout: a simple way to prevent neural networks from overfitting.  jmlr, 2014.
  * Suya et al. [2020] F Suya, J Chi, et al.  Hybrid batch attacks: Finding black-box adversarial examples with limited queries.  In USENIX, 2020.
  * Szegedy et al. [2014] C Szegedy, W Zaremba, et al.  Intriguing properties of neural networks.  In ICLR, 2014.
  * Wang et al. [2020] L Wang, K Yang, et al.  Mgaattack: Toward more query-efficient black-box attack by microbial genetic algorithm.  In MM, 2020.
  * Wang et al. [2021] X Wang, Y Yang, et al.  Fast gradient projection method for text adversary generation and adversarial training.  AAAI, 2021.
  * Wang et al. [2022] Zhen Wang, Yitao Zheng, Hai Zhu, Chang Yang, and Tianyi Chen.  Transferable adversarial examples can efficiently fool topic models.  Computers & Security, 118:102749, 2022.
  * Welch [1947] Bernard L Welch.  The generalization of ‘student’s’problem when several different population varlances are involved.  Biometrika, 1947.
  * Yoo et al. [2020] J Yoo, J Morris, et al.  Searching for a search method: Benchmarking search algorithms for generating nlp adversarial examples.  2020\.
  * Zhang et al. [2015] X Zhang, J Zhao, et al.  Character-level convolutional networks for text classification.  In NIPS, 2015.
  * Zhang et al. [2021] Z Zhang, M Liu, et al.  Argot: generating adversarial readable chinese texts.  In IJCAI, 2021.
  * Zhao et al. [2019] P Zhao, S Liu, et al.  On the design of black-box adversarial examples by leveraging gradient-free optimization and operator splitting method.  In ICCV, 2019.
  * Zhong et al. [2023] Zhehua Zhong, Tianyi Chen, and Zhen Wang.  Mat: Mixed-strategy game of adversarial training in fine-tuning.  arXiv preprint arXiv:2306.15826, 2023.


# Continuous Optimization for Offline Change Point Detection and Estimation

Hans Reimann
Department of Mathematics
University of Potsdam
Potsdam, BRANDENBURG, GERMANY
<EMAIL_ADDRESS>
& Sarat Moka
School of Mathematics and Statistics
University of New South Wales
Sydney, NSW, AUSTRALIA
<EMAIL_ADDRESS>
& Georgy Sofronov
School of Mathematical and Physical Sciences
Macquarie University
Sydney, NSW, AUSTRALIA
<EMAIL_ADDRESS>

###### Abstract

This work explores use of novel advances in best subset selection for
regression modelling via continuous optimization for offline change point
detection and estimation in univariate Gaussian data sequences. The approach
exploits reformulating the normal mean multiple change point model into a
regularized statistical inverse problem enforcing sparsity. After introducing
the problem statement, criteria and previous investigations via Lasso-
regularization, the recently developed framework of continuous optimization
for best subset selection (COMBSS) is briefly introduced and related to the
problem at hand. Supervised and unsupervised perspectives are explored with
the latter testing different approaches for the choice of regularization
penalty parameters via the discrepancy principle and a confidence bound. The
main result is an adaptation and evaluation of the COMBSS approach for offline
normal mean multiple change-point detection via experimental results on
simulated data for different choices of regularisation parameters. Results and
future directions are discussed.

_Keywords_ Best Subset Selection $\cdot$ Gradient Descent $\cdot$ COMBSS

##  1 Introduction

Change point detection and estimation are an incredibly diverse and widely
scattered field in applied and mathematical statistics, with a large variety
of applications. To provide a high-level intuition, change point detection may
be understood as a signal processing tool for identifying abrupt changes in
the generative parameters of a data sequence. While a strong line of work in
change point detection is well established with Page’s pioneering work (see
Page (1954)) and rigorous results by Chernoff and Zacks (1964), Lorden (1971)
and Sen and Srivastava (1975), many aspects of this problem are open and the
general understanding of good solutions depends strongly on the problem at
hand Niu et al. (2016), Truong et al. (2020), and Ma et al. (2020). Among the
open research questions, the simultaneous detection of multiple change points
in large data sets is of major interest.

Taking a machine learning and data scientific motivated approach, in this
paper, we explore the applicability of recent advances in best subset
selection of covariates in linear regression proposed by Moka et al. (2024).
This method, a continuous optimization approach for best subset selection,
claims to offer faster performance compared to existing exhaustive search
methods, while maintaining comparable accuracy. Furthermore, it achieves
superior accuracy relative to methods of similar speed, thus embodying highly
desirable properties for addressing the subset selection problem in offline
change point detection and estimation. Some of the existing methods including
Huang et al. (2005), Rinaldo (2009) and Qian and Jia (2016) utilize Lasso-
regularisation which provides convex relaxation of the underlying sparsity
problem. However, such Lasso-regularization approaches do not directly focus
on optimizing the actual discrete constrained best subset selection problem at
hand.

In this paper, we focus on the popular normal mean multiple change point model
assuming univariate, independent Gaussian random variable with a constant
variance. This simple yet challenging model has applications in several fields
including genomics and econometrics. Further, detection of change points can
be reduced to detecting change in mean in adapted sequences Niu et al. (2016)
such as detection of change in slope reducing to detection of mean in the
difference sequence. The challenge in detection and estimation of an unknown
number of change points in a piece-wise identical distributed sequence of
observations resembles a problem in choice of regularization penalty parameter
in practice.

We will explore two different methods and compare their performance assuming
knowledge on variance of the noise. This work formulates offline change point
detection as a best subset selection problem and it allows us to explore
recent advances in this domain. Our goal is to provide a proof of concept as
well as a stepping stone for future investigations. In particular, we employ
the novel advances in continuous optimization for best subset selection in the
given context to provide a new and modern perspective in approaching the
change point detection problem via modern machine learning methods. We believe
that the employed framework of simultaneous offline multiple change point
detection as a sparse linear regression problem has high potential in
utilizing the broad established toolbox of both areas.

The remaining paper is organized as follows. In Section 2, we formulate the
normal mean multiple change point model as a best subset selection problem in
linear regression and then discuss the key results of Moka et al. (2024). Our
method for change point detection problem is presented in Section 3. In
Section 4, linear time running time complexity of the proposed method is
presented. In Section 5 the simulation experimental designs and the
corresponding results are presented. Finally, a discussion on the results and
future directions for further studies are presented in Section 6.

##  2 Theoretical Background

In this section, we first provide formulation of offline multiple change point
detection as a subset selection problem in linear regression via boundary
conditions on sparsity of covariates (see Rinaldo (2009) and Niu et al.
(2016)). Then, we provide the gradient based continuous optimization
introduced of Moka et al. (2024) towards solving the subset selection problem.

###  2.1 Change Point Detection via Subset Selection

Let $Y=(Y_{1},\dots,Y_{n})$ be a sequence of independent random variables with
the distribution of $Y_{i}$ denoted as $F_{i}$. A change point is then a point
in the set of indices of the sequence $\tau\in\\{2,\dots,n\\}$ such that
$F_{\tau-1}\neq F_{\tau}$. The central aim in change point detection lies in
estimating the location of an instance $\tau$. In multiple change point
detection, the goal is to estimate both the locations of the change points and
their total number, denoted as $K$.

Consider the multiple mean change point detection problem with $K$ change
points with their locations denoted by $\tau_{1},\dots,\tau_{K}$ where
$\tau_{k}\in\\{2,\dots,n\\}$ and $\tau_{k}<\tau_{k+1}$ for each
$k\in\\{1,\ldots,K-1\\}$. Note that the case where $K=n-1$ (i.e., an instance
of change with every next sequence member) has generally very little insights
as the interest usually lies in detecting piece-wise independent and
identically distributed ($iid$) random variables in between instances of
change. On the other extreme, the case where $K\leq 1$ (i.e., whether a single
change point is present or not) is of great interest in that it quantifies
whether a full $iid$ assumption on a sequence of data is justified. For the
normal mean multiple change point model, which is central in this work, we
assume $K>1$ and take $Y_{i}\sim\mathcal{N}(\mu_{i},\sigma^{2})$ for each
$i\in\\{1,\dots,n\\}$ with mean $\mu_{i}$ and common variance $\sigma^{2}$. A
change point $\tau_{k}$ now refers to an unknown location in the sequence $Y$
with $\mu_{\tau_{k}-1}\neq\mu_{\tau_{k}}$. In addition, we make the usual
assumption that the total number of change points $K$ is unknown.
Consequently, the normal mean multiple change point model can be understood as
a sequence $Y$ generated by $K+1$ piece-wise constant signals $\mu_{i}$ and
zero-mean $iid$ noise sequence
$\varepsilon_{1},\dots,\varepsilon_{n}\sim\mathcal{N}(0,\sigma^{2})$, so that

$Y_{i}=\mu_{i}+\varepsilon_{i},\quad i\in\\{1,2,\ldots,n\\}.$

The central challenge then translates to estimating the mean sequence

$\mu_{1}=\ldots=\mu_{\tau_{1}-1}\neq\mu_{\tau_{1}}=\mu_{\tau_{1}+1}=\ldots=\mu_{\tau_{k}-1}\neq\mu_{\tau_{k}}=\ldots=\mu_{\tau_{K}-1}\neq\mu_{\tau_{K}}=\ldots=\mu_{n}.$

Besides, we introduce an artificial change point at $\tau_{0}=1$ whenever the
initial mean $\mu_{1}\neq 0$.

We now briefly discuss two major criteria in change point detection based on
signal-to-noise ratio and sparsity; refer to, e.g., Niu et al. (2016) for more
details. Both these criteria often provide the main assumptions and quantities
of interest in investigation and analysis. In order for the instances of mean
change to be insightful and identifiable, they need to have relevant degree of
distinction from one another which is measured in shift between means relative
to the noise. The corresponding parameter is the minimal difference in signal
standardized by the noise standard deviation, formally defined as,

$\delta=\underset{i\in\\{2,3,\ldots,n\\}}{\min}\frac{|\mu_{i}-\mu_{i-1}|}{\sigma},$

which is hereafter simply referred to as signal-to-noise ratio. Additionally,
two instances of change in too close proximity do not allow for any valuable
inference as there is too little data in between. This motivates control of
the minimal distance between instances of change, which is formally defined as

$L=\underset{k\in\\{1,2,\ldots,K\\}}{\min}\\{\tau_{k}-\tau_{k-1}\\}.$

The assumption on sparsity hereby also implicitly forms a boundary condition
of distance of the first and last instance of change from the respective start
and end of the data sequence. Further following Niu et al. (2016), both these
parameters are combined into the central quantity of signal strength
$S=\delta^{2}L$. While establishing the weakest possible condition on $S$ for
full recovery of all change points is an open problem, results by Arias-Castro
et al. (2005) show that $S\geq 2\log n$ could be a necessary condition for
full recovery of multiple change points. Additionally, Rinaldo (2009) and Qian
and Jia (2016) showed for their fused Lasso regression approach that the
consistency $\mathbb{P}(\hat{\mathbf{\tau}}=\mathbf{\tau})\rightarrow 1$ as
$n\to\infty$ with $\mathbf{\tau}=(\tau_{1},\dots,\tau_{K})\in\mathbb{R}^{K}$
denoting the vector of change point locations, where $\hat{\tau}$ being the
estimator of $\tau$. However, this requires a fairly strong assumption of
$\delta^{2}\gg\log n$, which may not be applicable in practice as indicated in
Niu et al. (2016).

The above mentioned linear regression approach to change point detection is
best understood in terms of the statistical inverse problem of recovering the
mean vector $\mu$ from the data sequence $y$, a realization of the random
vector $Y$. While a $L^{1}$-distance for tackling the problem may be
reasonable under considerations of robustness, we want to apply a $L^{2}$-norm
instead for desirable properties on differentiability. This results in the
ordinary least squares formulation $\|y-\mu\|^{2}_{2}$. Via introducing an
artificial design matrix $X$ and parameter vector $\beta$, we can further
transform the problem to a typical statistical inverse problem. In particular,
let $\beta_{i}=\mu_{i}-\mu_{i-1}$ for $i\in\\{1,2,\dots,n\\}$ with $\mu_{0}=0$
and $X$ be a $n\times n$ lower-triangular matrix with all the non-zero
elements being $1$. Then, we obtain $\mu=X\beta$ and $Y=X\beta+\varepsilon$.
The resulting statistical inverse problem is then

$\underset{\mu\in\mathbb{R}^{n}}{\min}\|y-\mu\|^{2}_{2}=\underset{\beta\in\mathbb{R}^{n}}{\min}\|y-X\beta\|^{2}_{2},$

which is the ordinary least squares approach for estimating the parameter
vector $\beta$ in linear regression. By construction, the piece-wise constant
structure of the mean vector $\mu$ translates to $0$ entries in $\beta$ as

$\mu_{i}=\mu_{i-1}\quad\text{if and only if}\quad\beta_{i}=0,$

for all $i\in\\{2,3,\dots,n\\}$. This motivates the use of modern high-
dimensional sparse regression methods for recovery of $\mu$, the central
connection exploited in this work.

With the given definition of $\beta$, we observe that $\beta_{i}\neq 0$ for
$i=\tau_{k}$ and $k\in\\{0,1,\ldots K\\}$, possibly including the artificial
change point $\tau_{0}$. That is, imposing sparsity in instances of change
translates to controlling the total number of non-zero entries of $\beta$.
Hence, we obtain

$\displaystyle\underset{\beta\in\mathbb{R}^{n}}{\min}\frac{1}{n}\|y-X\beta\|^{2}_{2}\quad\mathrm{subject}\
\mathrm{to}\,\,\|\beta\|_{0}:=\sum_{i=1}^{n}\mathbb{I}(\beta_{i}\neq 0)\leq
K,$ (1)

where $\mathbb{I}(\cdot)$ denotes the usual indicator function. This problem
is a reformulation of the normal mean change point detection to an ordinary
least squares regression problem with the sparsity induced by the
$L^{0}$-constraint $\|\beta\|_{0}\leq K$. This is a well studied highly non-
convex best subset selection problem in linear regression; refer to Müller and
Welsh (2010) and Hui et al. (2017) for details.

Among the existing methods for solving (1), the Lasso regression is a popular
convex relaxation of the subset selection problem where a $L^{0}$-norm
$\|\beta\|_{0}$ is replaced by a $L^{1}$-norm $\|\beta\|_{1}$. In particular,
the convex relaxation of the Lasso regularization is given by

$\displaystyle\underset{\beta\in\mathbb{R}^{n}}{\min}\frac{1}{n}\|y-X\beta\|^{2}_{2}+\lambda\|\beta\|_{1},$

where the parameter $\lambda$ in the penalty allows us to control the sparsity
in the solution. Application of the Lasso regularization to the normal mean
change point detection was studied in Huang et al. (2005) and Harchaoui and
Lévy-Leduc (2010) with additional constraints for a fused Lasso penalty
explored in Tibshirani and Wang (2008) and further work in Rinaldo (2009) and
Qian and Jia (2016). While this change yields desired properties in fast
computation and estimation, it does not generally guarantee to address the
best subset problem as above; refer, e.g., Zhu et al. (2020) and Hazimeh and
Mazumder (2020). However, the main insight from all these studies is the
necessity of tuning $\lambda$ in penalty Friedman et al. (2007), e.g. via
cross-validation as heuristic for parameter choice.

Two very recent works by Wang et al. (2020) and Verzelen et al. (2023) support
the sketched approach and show minimax optimality of their respective
estimators. Additionally, in emphasizing the value of post-processing of
detected instances of change, they provide a valuable future line of work.
Both these works focus on deriving lower bounds for the described multiple
change point model, however, with some adaptations and extensions, i.e., a
more general sub-Gaussian noise term. Each then introduces an estimator based
on the best subset selection approach with additional focus on the estimation
of the total number of changes. Yet in both cases, estimators constructed
based on (1) are shown to reach minimax optimal rates with high computational
efficiency. The gradient based estimator described in this work aims to fall
in line with these results and provide a solution via continuous optimization
similar to the Lasso approach.

###  2.2 Continuous Optimization for Subset Selection

We now introduce the key idea of Moka et al. (2024) that enables a continuous,
gradient based optimization for best subset selection. Towards this, recall
the optimization problem (1) and consider a vector $s\in\\{0,1\\}^{n}$ with

$s_{i}=\begin{cases}1,&\text{if $i=\tau_{k}$ for some $k\in\\{0,1,\ldots
K\\}$},\\\ 0,&\text{otherwise},\end{cases}$

that is, the indices of non-zero elements $s$ correspond to the location of
the change points. Hence, $|s|=\sum_{i=1}^{n}s_{i}=K$ is equivalent to
$\|\beta\|_{0}=K$. With this notation, for any $s\in\\{0,1\\}^{n}$, let
$X_{[s]}$ be the matrix of size $n\times|s|$ obtained from $X$ by keeping only
the columns with indices $j$ where $s_{j}=1$. Then, for any $K\in\\{1,2,\ldots
p\\}$, the exact best subset problem (1) can be restated as

$\displaystyle\underset{s\in\\{0,1\\}^{n}}{\min}\frac{1}{n}\|y-X_{[s]}\widehat{\beta}_{[s]}\|^{2}_{2},\quad$
$\displaystyle\mathrm{subject}\ \mathrm{to}\,\,|s|\leq K,$ (2)

where $\hat{\beta}_{[s]}$ is the low-dimensional ordinary least squares
solution utilizing $X_{[s]}$ instead of the full model design matrix $X$ for
estimation.

Even for a given $K$, the resulting problem in (2) is in general non-
deterministic polynomial-time hard (NP-hard) as stated in Natarajan (1995).
Exact methods are only feasible for small values of $n$. A more recent
approach via mixed integer optimization as in Bertsimas et al. (2016),
although faster than the exact method, remains fairly slow for practical
application Hazimeh and Mazumder (2020). The Lasso regularization, mentioned
above, is a reasonable relaxation regarding feasibility concerns, however, it
does not recover the best subset as in (1) or (2), as stated before recalling
Hazimeh and Mazumder (2020) and Zhu et al. (2020). As a novel approach,
continuous optimization method towards best subset selection, COMBSS, aims to
combine computational feasibility and accuracy in enabling modern gradient
based continuous optimization methods for the best subset selection problem;
see COMBSS with SubsetMapV1 in Moka et al. (2024) for details.

The central idea of COMBSS is to relax the binary vector $s\in\\{0,1\\}^{n}$
in (2), which takes values at the corners of the hypercube $[0,1]^{n}$, to a
vector $t\in[0,1]^{n}$ evolving on the entire hypercube. For each such $t$,
let

$M_{t}=X_{t}^{\top}X_{t}+n\,(I-\operatorname*{Diag\,}(t\odot t)),$

with $X_{t}=X\mathrm{Diag}(t)$, where $I$ is the identity matrix,
$\operatorname*{Diag\,}(v)$ is the diagonal matrix with $v$ as its diagonal,
and $\odot$ denotes the Hadamard (or, element-wise) product. Further, let
$\widetilde{\beta}_{t}$ be a solution of the linear equation (in terms of
$u$),

$\displaystyle M_{t}u=X_{t}^{\top}y.$ (3)

Then, the continuous Boolean relaxation of (2) is

$\displaystyle\underset{t\in[0,1]^{n}}{\min}\frac{1}{n}\|y-X_{t}\widetilde{\beta}_{t}\|^{2}_{2},\quad\mathrm{subject}\,\,\mathrm{to}\sum_{i=1}^{n}t_{i}\leq
K.$ (4)

The construction of $\tilde{\beta}_{t}$ hereby guarantees equality of (4) and
(2) at the corner points of the hypercube $[0,1]^{n}$. Instead of solving this
linear constrained problem, COMBSS aim to optimize its Lagrangian form as

$\displaystyle\underset{t\in[0,1]^{n}}{\min}\frac{1}{n}\|y-X_{t}\widetilde{\beta}_{t}\|^{2}_{2}+\lambda\sum_{i=1}^{n}t_{i},$
(5)

where the regularization penalty parameter $\lambda$, analogous to $K$ in the
exact problem, allows us to control the sparsity in the solution obtained.
Further, the continuous relaxation inside the hypercube enables the desired
smoothness in $t$ of the objective function
$\|y-X_{t}\widetilde{\beta}_{t}\|^{2}_{2}$ and the Lagrangian function in (5).
COMBSS main insight lies in suggesting candidates of best subsets by utilizing
this smoothness, without discrete constraints, while directly addressing the
best subset selection unlike previous continuous optimization approaches. This
way popular gradient based optimization methods in machine learning, such as
Adam optimizer, can easily be applied to optimize (5). Further, via a
transformation from $[0,1]^{n}$ to $\mathbb{R}^{n}$, COMBSS transforms the
box-constrained optimization (5) to an equivalent unconstrained optimization
so that the continuous optimizer does not face any boundary issues. The final
point $t$ for each $\lambda$ is mapped to an approximate solution $s$ of (2)
by taking $s_{i}=1$ if $t_{i}$ is close to $1$, otherwise $s_{i}=0$, for all
$i$.

The algorithm and exact mathematical framework with full details of the
procedure as well as the respective guarantees for smoothness are given in
Moka et al. (2024). The key enabling feature for computational feasibility
lies in efficiently solving the linear equation (3). Further, there is
software made available for both Python and R to implement the method. Our
experimental results emphasize the ability of COMBSS to recover best subsets
in both low and high dimensions. To summarize, by providing smooth solution
paths in the continuous relaxation of the exact best subset selection problem,
COMBSS has enabled a new and promising line of work. Among the benefactors may
well be the best subset selection problem in simultaneous normal mean multiple
change point detection.

##  3 Methodology

The central idea of this work is eminent: Normal mean multiple change point
detection and estimation in recovering the piece-wise constant mean vector
$\mu$ is equivalent to finding the best subset of covariates via sparsity
conditions imposed on the artificial design matrix $X$ and parameter vector
$\beta$ with $\mu=X\beta$ in (1). This optimization problem is equivalent to
the reduced lower-dimensional discrete optimization problem in (2). Solving
the best subset selection using an exact method, such as leaps-and-bounds, is
only computationally feasible when $n$ is less than $31$ Furnival and Wilson
(2000). However, the novel results of Moka et al. (2024) enable approaching it
via continuous optimization for solving (5). Furthermore, the regularisation
penalty parameter $\lambda$ enables us to control the total number of change
points. Thus, we create a grid of $\lambda$ values and execute COMBSS for each
$\lambda$ to produce a vector $t_{\lambda}^{*}\in[0,1]^{n}$, which is further
mapped to a binary vector $s_{\lambda}^{*}\in\\{0,1\\}^{n}$. This binary
vector $s_{\lambda}^{*}$ has $1$’s at locations corresponding to the change
points. So, using $s_{\lambda}^{*}$, we compute
$\widehat{\beta}_{[s_{\lambda}^{*}]}$ with the non-zero elements corresponding
to the shift in the mean values at the change points.

Taking a supervised perspective, where we assume that the number of change
points $K$ is known, the problem then translates into finding a suitable
$\lambda$ over a grid corresponding to $K$ change points. This is
straightforward, e.g., via a simple grid search or interval-halving algorithm.
However, the more practical problem is to take an unsupervised perspective
assuming that $K$ is unknown. This turns the challenge at hand into a typical
regularisation penalty parameter choice for statistical inverse problems.
While we do have a better understanding of the respective penalty parameter
$\lambda$ compared to the previously introduced Lasso approaches, it still
leaves us with a similar conclusion to Rinaldo (2009) in the unsupervised case
– it is an important open problem.

To address this issue of penalty parameter choice, we intend to employ
established methods for regularization choice in the context of inverse
problems. In particular, we investigate the discrepancy principle and an
adaptation of the discrepancy principle based on a lower confidence bound. Let
$\beta_{\lambda}$ denote the parameter vector $\beta$ obtained for a given
choice of $\lambda$. Following Richter (2021), the discrepancy principle for
statistical inverse problems aims to choose $\lambda$ such that the error of
$\|y-X\beta_{\lambda}\|^{2}_{2}$ aligns with the expected model error,
$\mathbb{E}[\|Y-X\beta\|^{2}_{2}]$. However, an analytical evaluation of this
expectation is only feasible in specific cases for the data sequence $y$.
Given the data sequence as introduced via the normal mean multiple change
points and constant noise variance $\sigma^{2}$, we can standardize the
inverse problem and find $\beta_{\lambda}$ such that it recovers
$\|\frac{1}{\sigma}(y-X\beta_{\lambda})\|^{2}_{2}=n$, as under the true model
$\|\frac{1}{\sigma}(y-X\beta)\|^{2}_{2}\sim\chi^{2}(n)$ with expectation equal
to the degrees of freedom. Again, the basic idea hereby is that the
regularization penalty is chosen so that the average or expected level of
error given the estimated parameter vector should resemble that of a true
parameter vector given the model. For a much more sophisticated and thorough
analysis of the discrepancy principle for statistical inverse problems see
Blanchard and Mathé (2012). Adaptation to a confidence bound extends this
comparison via using a $\chi^{2}$-quantile instead of the expectation, to
control the effect of the model error in the inverse problem. This then leads
to the choice of a regularization penalty that is at least as restrictive as
with the discrepancy principle. The intuition here is that of a one-sided
composite hypothesis of the regularisation penalty $\lambda$ that recovers the
parameter vector $\beta$ in $H_{0}:\ \lambda\leq\lambda_{0}$ vs $H_{1}:\
\lambda>\lambda_{0}$ for $\lambda_{0}$ the penalty parameter recovering the
true model. The $\chi^{2}$-distribution of the standardized regularization
again provides a decision threshold. The regularisation penalty is chosen such
that the supposedly plausible error is maximal within the confidence bound
$\underset{\lambda>0}{\max}\|\frac{1}{\sigma}(y-X\beta_{\lambda})\|^{2}_{2}\leq\chi^{2}_{1-\alpha}(n)$
for $\alpha\in(0,1)$. In essence this means increasing $\lambda$ and thus
decreasing $K$, right until $H_{0}$ needs to be rejected. The basic idea then
is that under the true parameter vector the accumulated model error is
plausible up to the threshold $\chi^{2}_{1-\alpha}(n)$. As noted, this
accommodates at least as much error as the discrepancy principle and therefore
may allow for more restrictive choices of regularisation penalty and smaller
values of $K$. The main limitation of the discrepancy principle and its
adaptation is that they require knowledge of the noise variance of the
sequence. whereas they do not require a constant variance assumption.Solutions
via estimating the variance from the sequence itself are difficult, but could
be implemented via pooled variance estimators. Via an iterative scheme,
repeated estimation of the pooled covariance and change point detection may
provide ways of implementation of the discrepancy principle even for unknown
covariance. However, this is likely to lead to problems in dependence of the
estimated variance and the analysis of the expected error after
standardization. Accordingly, the main insight for the following experiments
lies in a simple litmus test of whether and to what extent information about
the variance helps in the choice of the regularisation penalty.

##  4 Time Complexity

We now show that our implementation of COMBSS exhibits $O(n)$ running time
complexity. In the general COMBSS approach of Moka et al. (2024), for
optimizing (5), computational complexity of the gradients of the objective
function is dictated by computations of solving linear equations of the form
$M_{t}u=b$. The matrix $M_{t}$ can be shown to be dense positive-definite for
$t\in(0,1)^{n}$ and thus, exact gradient computation can be expensive with a
time complexity of $O(n^{3})$. When a conjugate gradient method is used for
approximately solve such a linear equation, the general COMBSS exhibits
$O(n^{2})$ complexity.

It is important to note that in the general setting, the design matrix $X$ is
part of the data. However, in our case, $X$ has an artificial design of being
lower triangular matrix with the non-zero elements equal to $1$. We now take
advantage of this fact to modify the COMBSS algorithm to achieve a time
complexity of $O(n)$. Towards this, Lemma 1 establishes that the inverse of
$X^{\top}X$ is tridiagonal.

######  Lemma 1.

Consider the lower triangular matrix $X$ with the non-zero elements being $1$.
Then, $A=(X^{\top}X)^{-1}$ is a tridiagonal matrix with the principle diagonal
being $(1,2,2,\dots,2)$ (i.e., first element is $1$ and all other elements are
equal to $2$) and both the sub-diagonals being $(-1,-1,\dots,-1)$ (i.e., all
elements equal to $-1$).

We can easily establish Lemma 1 using a proof by induction. Start with the
basic case at $n=2$ and assume that it is true for $n$. Then, we can show that
this is true for $n+1$ via using the Banachiewicz inversion lemma Tian and
Takane (2005).

######  Lemma 2 (Woodbury Matrix Identity).

For any conformable matrices $A$, $U$, $C$ and $V$,

$(UAV+C)^{-1}=C^{-1}-C^{-1}U(A^{-1}+VC^{-1}U)^{-1}VC^{-1}.$

Refer to Woodbury (1950) for a proof of Lemma 2. Note that with
$T_{t}=\operatorname*{Diag\,}(t)$ and $D_{t}=d(I-T_{t}^{2})$, we can write
$M_{t}=\left(T_{t}X^{\top}XT_{t}+D_{t}\right)/n$. Further, as a consequence of
Lemma 2, we have the following result

######  Theorem 1.

Let $\widetilde{M}_{t}=(X^{\top}X)^{-1}+T_{t}D_{t}^{-1}T_{t}$. Then, for the
lower triangular matrix $X$, $\widetilde{M}_{t}$ is a tridiagonal matrix, and

$\displaystyle
M_{t}^{-1}=n\,D_{t}^{-1}-n\,D_{t}^{-1}T_{t}\widetilde{M}_{t}^{-1}T_{t}D_{t}^{-1},\quad
t\in[0,1)^{n}.$ (6)

Proof of Theorem 1 is straightforward: Since $(X^{\top}X)^{-1}$ is tridiagonal
given in Lemma 1 and $T_{t}D_{t}^{-1}T_{t}$ is diagonal, $\widetilde{M}_{t}$
must be tridiagonal. Selecting $A=X^{\top}X$, $C=D_{t}$, and $U=V=T_{t}$ in
Lemma 2, we get (6).

Recall that we want to compute the expressions of the form $M_{t}^{-1}b$.
Since $D_{t}$ is diagonal, computing expressions of the form $D_{t}^{-1}v$ has
$O(n)$ complexity. This means, the bottleneck is the complexity of computing
expressions of the form $\widetilde{M}_{t}^{-1}v$. Since $\widetilde{M}_{t}$
is a tridiagonal matrix, this operation is easy to execute using the popular
method of the Thomas algorithm or tridiagonal matrix algorithm which is known
to have $O(n)$ complexity; see, e.g., Lee (2011) and Higham (2002). In
conclusion, the computational complexity of solving a linear equation of the
form $M_{t}u=b$ is $O(n)$ only. Moka et al. (2024) have shown that the COMBSS
method approaches an $\epsilon$-stationary point in $O(1/\epsilon^{2})$
iterations (independent of $n$). Thus, our implementation has $O(n)$ time
complexity.

##  5 Empirical Evaluation Results

By construction and with the extensive simulation results in Moka et al.
(2024), the proposed approach appears reliable in best subset selection in
linear regression. The experimental simulation study in this paper aims to
investigate the two levels of knowledge. First, there is the supervised level
with knowledge about the number of change points $K$. How well does our
continuous optimization method recover the locations of change given $K$ is
known? Second is the unsupervised level with knowledge about the variance of
the noise. How well do the discrepancy principle and the confidence bound
perform for our method in recovering the true number of change points as well
as their locations? All experiments follow a basic set up reduced to its
essentials. We conduct two sets of experiments for known and unknown number of
change points. In each set, the first respective experiment scales signal-to-
noise ratio, $\delta^{2}$, with a fixed distance between change points. The
second experiment then scales minimal distance between change points, $L$, for
fixed signal-to-noise ratio. We set $\sigma^{2}=1$ throughout all experiments
only adjusting the difference in mean values to set signal-to-noise ratio. We
conduct $100$ Monte Carlo simulations of the noise for each experiment and
value of the scaling quantities $\delta$ and $L$. Following Aminikhanghahi and
Cook (2017) and Truong et al. (2020), the metrics for evaluation will be the
F1-score and the Hausdorff distance metric. The F1-score hereby serves as a
measure of accuracy combining sensitivity and precision with a tolerance level
of $\tau_{k}\pm L/20$ to allow for negligible inaccuracies. The Hausdorff
distance metric serves as evaluation of robustness of the detection procedure
in measuring the largest difference between a change point and its closest
estimated counterpart. For better comparison under scaling minimal distance,
we also standardize the Hausdorff metric by $L$. The evaluation criteria are
averaged over all Monte-Carlo simulations for a concrete value of $\delta$ or
$L$. All experiments are conducted in R (version 4.2.2).

###  5.1 Experiment A - Known Number of Change Points

For each Monte-Carlo simulation, the regularization penalty $\lambda$ for the
proposed algorithm is chosen via a interval halving approach until it produces
a result with the right number of change points $K$. In very rare instances,
if the interval halving fails to produce a result with right number $K$ in a
certain number of steps, the corresponding Monte-Carlo sample will be skipped
in the aggregation of the Hausdorff metric.

####  5.1.1 Experiment A1 - Scaling $\delta^{2}$

Set $n=150$ with a total of $4$ change points at $\tau=(31,61,91,121)$, so
$L=30$. The mean sequence has a simple staircase form with difference in mean
at the change points $\mu_{\tau_{k}}-\mu_{\tau_{k}-1}$ for $k\in\\{1,2,3,4\\}$
ranging from $0.25$ to $4$ with step-size $\triangle\delta=0.25$ and
$\mu_{\tau_{0}}=0$, so it should not be detected. The necessary condition in
Arias-Castro et al. (2005) is therefore
$\delta_{\mathrm{crit}}\geq\sqrt{\frac{2\log(150)}{30}}\approx 0.58$ and is
surpassed after two steps of $\delta$.

(a) Scaling signal-to-noise ratio via $\delta$ and resulting
F1-score.

(b) Scaling signal-to-noise ratio via $\delta$ and resulting
Hausdorff metric.

Figure 1:  Figure 2: Histogram of estimated change points over all Monte Carlo
runs for selected values of $\delta$.

There are two main insight obtained from this experiment. First, the approach
yields the desired result in that both measures, F1-score and Hausdorff
metric, improve for increasing signal-to-noise ratio $\delta$ with reliable
estimation after $\delta\approx 2.5$. The second, and much more valuable
insight at this stage, is best portrayed by the histogram of change point
locations over all Monte-Carlo simulations. The proposed algorithm seems to
have a tendency in selecting change points in close proximity to each other
for a given $K$ and struggles to recover the last change point – even for
larger values of $\delta$. To give a concrete example, it tends to choose
$\mathbf{\hat{\tau}}=(31,61,90,91)$ or something similar for a given $K=4$
instead of the actual vector $\mathbf{\tau}$ and it seemingly does so
consistently. This emphasizes the need of post-treatment of suggested
candidates of change point locations, i.e., via clustering, before matching a
given $K$. Furthermore, this behavior shows consistently throughout all
experiments although we only include the histogram here.

####  5.1.2 Experiment A2 - Scaling $L$

Again, set $K=4$ with the mean sequence of a simple staircase form with
difference in mean $\delta=2$ at the change points, so
$\mu_{\tau_{k}}-\mu_{\tau_{k}-1}=2$ for $k\in\\{1,2,3,4\\}$. We take
$\mu_{\tau_{0}}=0$ for the artificial change point $\tau_{0}=1$ so it should
not be detected. The choice of $\delta$ is hereby taken from the previous
experiment indicating good detection for a minimal distance $L=30$ yet with
potential for showing effect in either direction. Scaling now the distance
between change points $L$ taking values from $15$ to $65$ with step-size
$\triangle L=5$, we therefore have change points at
$\tau=(L+1,2L+1,3L+1,4L+1)$ and sequence length $n=5L$.

(a) Scaling signal-to-noise ratio via $L$ and resulting
F1-score.

(b) Scaling signal-to-noise ratio via $L$ and resulting
Hausdorff metric.

Figure 3:

Again, w observe the desired behavior in improving performance measures for
increasing $L$ tempering off for larger values. Accordingly, we may conclude
the generally desired behavior of the approach in both metrics of interest for
increasing signal strength $S$ even for this more pilot implementation.

###  5.2 Experiment B - Unknown Number of Change Points

For each Monte-Carlo simulation, the regularization penalty $\lambda$ for the
COMBSS algorithm is chosen via both of the described methods. The discrepancy
principle and the confidence bound hereby start at $\lambda=0$ and then
increase with a step size $\triangle\lambda=0.005$ until the respective
conditions are surpassed. The discrepancy principle then picks whichever
$\lambda$ is closer to the expected error and the confidence bound chooses the
previous penalty value $\lambda$ before the threshold is exceeded. Both
estimate $\mathbf{\hat{\tau}}$ for their respective choice of $\lambda$.

####  5.2.1 Experiment B1 - Scaling $\delta^{2}$

Set $n=100$ with a total of $3$ change points at $\tau=(26,51,76)$, so minimum
distance $L=25$. The mean sequence has a simple staircase form with the
difference of the mean at the change points $\mu_{\tau_{k}}-\mu_{\tau_{k}-1}$
for $k\in\\{1,2,3\\}$, so $\delta$, ranging from $1$ to $4$ with step-size
$\triangle\delta=0.5$. The artificial change point is set to
$\mu_{\tau_{0}}=0$, so it should not be detected. The necessary condition for
detection derived in Arias-Castro et al. (2005) is
at$\delta_{\mathrm{crit}}\geq\sqrt{\frac{2\log(100)}{25}}\approx 0.61$ and is
exceeded after the first step.

(a) Scaling signal-to-noise ratio via $\delta$ and resulting
F1-score for both penalty choice approaches.

(b) Scaling signal-to-noise ratio via $\delta$ and resulting
Hausdorff metric for both penalty choice approaches.

Figure 4:

We observe the desired behavior for both curves, similar to the previous
experiments. The confidence bound seems to provide a slightly better choice of
$\lambda$ for larger values of $\delta$, but further investigation is needed.

####  5.2.2 Experiment B2 - Scaling $L$

Again, set $K=3$ with the mean sequence of a simple staircase form with
difference in mean $\delta=2$ at the change points
$\mu_{\tau_{k}}-\mu_{\tau_{k}-1}=1$ for $k\in\\{1,2,3\\}$ and
$\mu_{\tau_{0}}=0$ for the artificial change point $\tau_{0}=1$ so it should
not be detected. $\delta$ is hereby chosen for the same reasons as in
experiment A2 to provide range for chnage in performance in both directions.
Scaling now the distance between change points $L$ taking values from $10$ to
$50$ with step-size $\triangle L=5$, we therefore have change points at
$\tau=(L+1,2L+1,3L+1)$ and sequence length $n=4L$.

(a) Scaling signal-to-noise ratio via $L$ and resulting
F1-score for both penalty choice approaches.

(b) Scaling signal-to-noise ratio via $L$ and resulting
Hausdorff metric for both penalty choice approaches.

Figure 5:

Similar to before, we observe improving performance in both metrics for
increasing minimal distance $L$ between change points. There does not seem to
be a major difference in the two choices of penalty value $\lambda$. Both
methods seem viable with good performance and should be included in follow up
studies.

##  6 Discussion, Conclusions and Outlook

The presented work is a proof of concept to show that there is great value to
the approach utilizing COMBSS for candidates of change points in the normal
mean change point model. This approach here still has plenty of room for
improvement in implementation, yet the results provide a valuable basis for
further investigation. While the experiments in the work at hand do not
include a direct comparison to current Lasso approaches, results in Moka et
al. (2024) suggest for COMBSS competitive results in the more general case.
Additionally, a real world application is highly desirable but needs to be
subject for future investigations.
The main insights currently are the computational cost and the spurious change
points estimated. The term spurious change points as mentioned in Pilliat et
al. (2023) hereby refers to the tendency to detect change points in close
proximity to each other. In practice, they can simply be aggregated into a
single change point in post treatment whenever they are in too close proximity
to each other. This problem mainly influenced the first two supervised
experiments while the unsupervised experiments simply gave too large of a
number of change points without this treatment, however, neither of the
metrics were influenced by that in a meaningful way. For the F1-score, the
tolerance accounted for that and in the Hausdorff metric only the closes
change point is of interest. A possible line of future work arising from this
problem could be to investigate the vast toolbox of linear regression for
testing significance of supposed spurious change points. Other future lines of
work will lie in exploring advances in adjacent topics. One such, is in
investigating the discrepancy principle for choice of regularisation penalty
under the sophisticated results in Blanchard and Mathé (2012). The artificial
design matrix is of trace type and can therefore be fit to their results for
better statistical guarantees. Further, great interest lies in the gradient of
the COMBSS algorithm given its specific choice of $X$. It promises high
potential for improving computational efficiency and in combination with the
approach of Niu et al. (2016) in utilizing symmetry by connecting the ends of
a data sequence, it may help addressing the current issue of the neglected
last change point.

To conclude, utilizing the key concept in COMBSS in continuous relaxation of
the best subset selection problem for modern gradient based optimization
yields a novel, promising and valuable line of work for simultaneous offline
multiple change point detection in the normal mean multiple change point
model. It offers a large variety of directions for detailed investigations,
optimizations and adaptations. With ongoing research on COMBSS, both fields
may very much profit from each other sharing their advances. With the addition
of COMBSS to the vast topic of change point detection has a new, additional
connection to popular research in machine learning, further opening it up to
interested researchers.

## References

  * Page [1954] Ewan S Page.  Continuous inspection schemes.  _Biometrika_ , 41(1/2):100–115, 1954.
  * Chernoff and Zacks [1964] Herman Chernoff and Shelemyahu Zacks.  Estimating the current mean of a normal distribution which is subjected to changes in time.  _The Annals of Mathematical Statistics_ , 35(3):999–1018, 1964.
  * Lorden [1971] Gary Lorden.  Procedures for reacting to a change in distribution.  _The Annals of Mathematical Statistics_ , 42(6):1897–1908, 1971.
  * Sen and Srivastava [1975] Ashish Sen and Muni S Srivastava.  On tests for detecting change in mean.  _The Annals of Statistics_ , 3(1):98–108, 1975\.
  * Niu et al. [2016] Yue S Niu, Ning Hao, and Heping Zhang.  Multiple change-point detection: a selective overview.  _Statistical Science_ , 31(4):611–623, 2016.
  * Truong et al. [2020] Charles Truong, Laurent Oudre, and Nicolas Vayatis.  Selective review of offline change point detection methods.  _Signal Processing_ , 167:107299, 2020.
  * Ma et al. [2020] Lijing Ma, Andrew J. Grant, and Georgy Sofronov.  Multiple change point detection and validation in autoregressive time series data.  _Statistical Papers_ , 61(4):1507–1528, 2020\.  ISSN 0932-5026.
  * Moka et al. [2024] Sarat Moka, Benoit Liquet, Houying Zhu, and Samuel Muller.  Combss: best subset selection via continuous optimization.  _Statistics and Computing_ , 34(2):75, 2024.
  * Huang et al. [2005] Tao Huang, Baolin Wu, Paul Lizardi, and Hongyu Zhao.  Detection of dna copy number alterations using penalized least squares regression.  _Bioinformatics_ , 21(20):3811–3817, 2005.
  * Rinaldo [2009] Alessandro Rinaldo.  Properties and refinements of the fused lasso.  _The Annals of Statistics_ , 37(5B):2922–2952, 2009.
  * Qian and Jia [2016] Junyang Qian and Jinzhu Jia.  On stepwise pattern recovery of the fused lasso.  _Computational Statistics & Data Analysis_, 94:221–237, 2016.
  * Arias-Castro et al. [2005] Ery Arias-Castro, David L Donoho, and Xiaoming Huo.  Near-optimal detection of geometric objects by fast multiscale methods.  _IEEE Transactions on Information Theory_ , 51(7):2402–2425, 2005.
  * Müller and Welsh [2010] Samuel Müller and Alan H. Welsh.  On model selection curves.  _International Statistical Review_ , 78(2):240–256, 2010.
  * Hui et al. [2017] Francis KC Hui, Samuel Müller, and AH Welsh.  Joint selection in mixed models using regularized pql.  _Journal of the American Statistical Association_ , 112(519):1323–1333, 2017.
  * Harchaoui and Lévy-Leduc [2010] Zaıd Harchaoui and Céline Lévy-Leduc.  Multiple change-point estimation with a total variation penalty.  _Journal of the American Statistical Association_ , 105(492):1480–1493, 2010.
  * Tibshirani and Wang [2008] Robert Tibshirani and Pei Wang.  Spatial smoothing and hot spot detection for cgh data using the fused lasso.  _Biostatistics_ , 9(1):18–29, 2008.
  * Zhu et al. [2020] Junxian Zhu, Canhong Wen, Jin Zhu, Heping Zhang, and Xueqin Wang.  A polynomial algorithm for best-subset selection problem.  _Proceedings of the National Academy of Sciences_ , 117(52):33117–33123, 2020.
  * Hazimeh and Mazumder [2020] Hussein Hazimeh and Rahul Mazumder.  Fast best subset selection: Coordinate descent and local combinatorial optimization algorithms.  _Operations Research_ , 68(5):1517–1537, 2020\.
  * Friedman et al. [2007] Jerome Friedman, Trevor Hastie, Holger Höfling, and Robert Tibshirani.  Pathwise coordinate optimization.  _The Annals of Appplied Statistics_ , 1(2):302–332, 2007.
  * Wang et al. [2020] Daren Wang, Yi Yu, and Alessandro Rinaldo.  Univariate mean change point detection: Penalization, CUSUM and optimality.  _Electronic Journal of Statistics_ , 14:1917–1961, 2020\.
  * Verzelen et al. [2023] Nicolas Verzelen, Magalie Fromont, Matthieu Lerasle, and Patricia Reynaud-Bouret.  Optimal change-point detection and localization.  _The Annals of Statistics_ , 51(4):1586–1610, 2023.
  * Natarajan [1995] Balas Kausik Natarajan.  Sparse approximate solutions to linear systems.  _SIAM journal on computing_ , 24(2):227–234, 1995\.
  * Bertsimas et al. [2016] Dimitris Bertsimas, Angela King, and Rahul Mazumder.  Best subset selection via a modern optimization lens.  _The Annals of Statistics_ , 44(2):813–852, 2016\.
  * Furnival and Wilson [2000] George M Furnival and Robert W Wilson.  Regressions by leaps and bounds.  _Technometrics_ , 42(1):69–79, 2000.
  * Richter [2021] Mathias Richter.  _Inverse Problems: Basics, Theory and Applications in Geophysics_.  Springer Nature, 2021.
  * Blanchard and Mathé [2012] Gilles Blanchard and Peter Mathé.  Discrepancy principle for statistical inverse problems with application to conjugate gradient iteration.  _Inverse problems_ , 28(11):115011, 2012.
  * Tian and Takane [2005] Yongge Tian and Yoshio Takane.  Schur complements and banachiewicz-schur forms.  _The Electronic Journal of Linear Algebra_ , 13:405–418, 2005.
  * Woodbury [1950] Max A Woodbury.  _Inverting modified matrices_.  Department of Statistics, Princeton University, 1950.
  * Lee [2011] WT Lee.  Tridiagonal matrices: Thomas algorithm.  _MS6021, Scientific Computation, University of Limerick_ , 2011.
  * Higham [2002] Nicholas J Higham.  _Accuracy and Stability of Numerical Algorithms_.  SIAM, 2002.
  * Aminikhanghahi and Cook [2017] Samaneh Aminikhanghahi and Diane J Cook.  A survey of methods for time series change point detection.  _Knowledge and information systems_ , 51(2):339–367, 2017.
  * Pilliat et al. [2023] Emmanuel Pilliat, Alexandra Carpentier, and Nicolas Verzelen.  Optimal multiple change-point detection for high-dimensional data.  _Electronic Journal of Statistics_ , 17(1):1240–1315, 2023.