2021

[1,2]Ying Lin

[1] School of Software, Yunnan University, Kunming, 650500, Yunnan Province,
China

2] Key Laboratory in Software Engineering of Yunnan Province

# Adaptive perturbation adversarial training: based on reinforcement learning

Zhishen Nie<EMAIL_ADDRESS><EMAIL_ADDRESS>Sp Ren  Lan Zhang
*  [

###### Abstract

Adversarial training has become the primary method to defend against
adversarial samples. However, it is hard to practically apply due to many
shortcomings. One of the shortcomings of adversarial training is that it will
reduce the recognition accuracy of normal samples. Adaptive perturbation
adversarial training is proposed to alleviate this problem. It uses marginal
adversarial samples that are close to the decision boundary but does not cross
the decision boundary for adversarial training, which improves the accuracy of
model recognition while maintaining the robustness of the model. However,
searching for marginal adversarial samples brings additional computational
costs. This paper proposes a method for finding marginal adversarial samples
based on reinforcement learning, and combines it with the latest fast
adversarial training technology, which effectively speeds up training process
and reduces training costs.

###### keywords:

adversarial training, decision boundary, robustness, adversarial samples,
reinforcement learning

##  1 Introduction

It has been widely known that DNNs (Deep Neural Networks, DNNs) are
susceptible to adversarial samples. Using adversarial samples for adversarial
training becomes an effective method to defend against adversarial attacks.
FGSM (Fast gradient sign method , FGSM) FGSM  is the first proposed
adversarial training method, known for its fast training speed. However, in
the literature PGD , it has been proved that this method cannot defend the
adversarial samples generated by multiple iterations, and therefore proposed a
more effective PGD (Project Gradient Descent, PGD) adversarial training
method. PGD adversarial training uses smaller perturbation steps to generate
stronger adversarial samples for multiple iterations to enhance the robustness
of the model. Although adversarial training can effectively defend against
adversarial samples, there are two main shortcomings: (1) The computational
cost is high. Compared with normal training, adversarial training usually
costs 2-10 times the computational cost; (2) In the field of computer vision,
although the robustness of the model is improved, all adversarial training
methods will destroy the generalization ability of the model to a certain
extent These two shortcomings greatly restrict its applications.

There have been several works Free-AT ; YOPO  researching how to reduce the
computational cost of adversarial training. For example, Fast adversarial
training FAT-RS  and its subsequent improved version FAT-Align ;
kim2020understanding  can reduce the number of back propagation necessary for
adversarial training to 2-3 times. In other words, the fast adversarial
training technology only spends 2-3 times the computational cost (compared to
regular training) while the model still obtains good robustness and better
generalization ability.

Aiming at the problem that adversarial training impairs the generalization
ability of the trained model, more effective adaptive perturbation adversarial
training methods MMA ; IAAT  were proposed. In traditional adversarial
training process, each sample was added with the same perturbation step. But
in the adaptive perturbation adversarial training process, the perturbation
step added by each sample is different. This improvement greatly enhances the
generalization ability of the model. However, due to the additional
computational cost of searching for marginal adversarial samples, the
computational cost is still higher than that of fast adversarial training.

Reinforcement learning (RL) is a technology that imitates the behavior of
living creatures seeking advantages and avoiding disadvantages. Unlike
supervised learning, reinforcement learning does not have a fixed method, and
everything must be done in interaction with the environment. A reinforcement
learning system can be thought of as a simulated world. This system includes
elements such as environment, agent, reward, policy, state and so on. The most
critical elements are rewards and policy. The reward function in reinforcement
learning is equivalent to the loss function in supervised learning. The
difference is that the reward function in reinforcement learning needs to be
maximized. policy is another key factor, which determines what actions the
agent will make based on observations. The cornerstone of reinforcement
learning is the Markov decision processes MDP , which allows the complex
environment to be simplified into a state transition equation to simplify the
problem.

Deep reinforcement learning combined with DNNs has also made significant
progress in recent years. Representative works include DQN ; DDPG ; TD3 ; TRPO
; PPO  etc. But they still have some shortcomings. For example, it is too
sensitive to hyperparameter (such as learning rate), which makes training
difficult, or the sample efficiency is too low, causing the agent to have a
lot of interaction with the environment. The proposed SAC (Soft Actor Critic,
SAC) SAC  solves the above problems. It uses the Actor-Critic architecture,
uses maximum entropy and random strategies to better explore possible optimal
paths, thereby improving generalization capabilities. At the same time, it is
an off-policy algorithm that can effectively use historical data, so the
sample efficiency is also very high. In addition, SAC is also one of the few
reinforcement learning algorithms that can be directly deployed in real
robots.

The contributions of this article are as follows:

(1) We use reinforcement learning to search for marginal adversarial samples,
and theoretically prove the rationality of the method. As far as we know, this
is the first application of reinforcement learning in searching for marginal
adversarial samples.

(2) We use the number of calculations as the standard to compare the
performance of different methods in calculating marginal adversarial samples
in detail.

(3) In the past, adaptive perturbation adversarial training was based on PGD,
and we adopted the latest fast adversarial training technology, which greatly
reduced the computational cost.

##  2 Related works

###  2.1 Adaptive perturbation adversarial training

Adaptive perturbation adversarial training is a recently proposed method.
Compared with traditional adversarial training such as PGD adversarial
training, its most prominent feature is to formulate a "unique" perturbation
step for each sample. Its idea is that if a larger perturbation is forcibly
added to the samples close to the decision boundary, the model will be forced
to change the decision boundary, resulting in poor generalization ability. The
MMA is the first proposed adaptive perturbation adversarial training MMA  and
its optimization goal is as follows:

$\mathop{min}\limits_{\theta}\\{\sum\limits_{i\in
S_{\theta}^{+}}max\\{0,d_{max}-d(x_{i},y_{i},\theta)\\}+\beta\cdot\sum\limits_{i\in
S_{\theta}^{-}}L(x_{i},y_{i},\theta))\\}$ (1)

where $\theta$ is the parameter of the classification neural network,
$d_{max}$ is a hyperparameter that represents the maximum value adversarial
perturbation, $\beta$ is also a hyperparameter, which is used to balance the
two loss terms, $L(\cdot)$ represents the classification loss, usually cross
entropy. $S_{\theta}^{+}$ represents the set of samples that are correctly
classified, $S_{\theta}^{-}$ represents the set of misclassified samples. MMA
maximizes the margins of correctly classified samples and minimizes the
classification loss of incorrectly classified samples. In addition, the author
also gives an experimental analysis, confirming the effectiveness of adaptive
perturbation adversarial training.

###  2.2 Fast adversarial training

With the rapid development of adversarial training, one of its drawbacks has
gradually emerged: the computational cost of adversarial training is too high,
especially the PGD. Therefore, some scholars restarted researchs of using
single-step iterative generation of adversarial samples (such as FGSM) for
adversarial training. These methods are collectively referred to as FAT (Fast
Adversarial Training, FAT). Free-AT (Free Adversarial Training, Free-AT) Free-
AT  was the first FAT method proposed to reduce computational cost. Compared
with PGD, Free-AT uses a larger perturbation step size to generate adversarial
samples, and each generated adversarial sample is used to train the model,
thus significantly speeding up the model convergence speed. However, the same
batch of data still needs to be backpropagated multiple times. In the
literature [5], the authors proposed a fast adversarial training method. The
author uses FGSM + RS (Random Step, RS) instead of PGD to generate adversarial
sample. This method fully inherits the advantages of FGSM adversarial
training, and does not require multiple backpropagation of the same batch of
data, so it significantly saves computational costs. However, the above-
mentioned methods all have such a problem: when the adversarial perturbation
is too large, catastrophic overfitting will occur. The model’s accuracy can
suddenly drop to zero when confronting PGD attacks, while increase
significantly when confronting FGSM attacks. The current solution is to stop
training before overfitting, so that the model can obtain sub-optimal
robustness.

The better solution to overfitting problem is FAT-Align . The authors believed
that the key to avoiding catastrophic overfitting is to maintain the
consistency of PGD adversarial samples and FGSM adversarial samples, and
ensuring consistency lies in the local linearity of the model. They proposed a
regularization of cosine similarity:

$\Omega(x,y,\theta)=\mathbb{E}_{(x,y)\thicksim
D,\eta\thicksim\mu([-\varepsilon,\varepsilon])}[1-cos(\nabla_{x}L(x,y,\theta),\nabla_{x}L(x+\eta,y,\theta)]$
(2)

It guarantees the local linearity of the model within
$\ell_{\infty}\mbox{-}balls$, and thus solves catastrophic overfitting well.
The authors also proved that this method still does not appear catastrophic
overfitting even under large perturbations.

##  3 Motivation

In the previous adaptive perturbation adversarial training, the general
process of finding marginal adversarial samples is as follows:

$x_{t}=x_{t-1}+\varepsilon\cdot sign(grad)$

if $f(x_{t})$ is right then $x_{t}=x_{t-1}+\varepsilon\cdot sign(grad)$

else $x_{t}=x_{t-1}-\varepsilon\cdot sign(grad)$

where $grad=\nabla_{x}L\left(x,y,\theta\right)$.However, this process is a
qualitative method rather than a quantitative method. It can only find the
sample closest to the decision boundary under the current perturbation step.
As for how far the sample is from the decision boundary, it cannot be
determined.

The IAAT (Instance Adaptive Adversarial Training, IAAT) IAAT  uses fixed
perturbation step length. However, the perturbation step length is a more
difficult value to determine. If a fixed perturbation step size is used, then
only a small perturbation step size can be taken, because if the step size is
too large, the calculated sample may be far away from the decision boundary.
However, the training cost is increased due to too many calculation times for
small steps. According to our observations in the experiments, in the
iterative process, if the perturbation step length is fixed each time, the
closer to the decision boundary, the more dramatic the change in confidence.
Confidence is a non-linear relationship in adversarial perturbations and is
closely related to many factors, such as data sets and network architectures.
Therefore, it is difficult to determine the size of a suitable fixed
perturbation step. MMA is based on the binary search to explore the
perturbation step size, which saves the calculation cost to a large extent
compared with the fixed perturbation step size. The upper bound of the half
search is difficult to determine, and an excessively large upper bound will
increase the number of search steps.

From the above analysis, it could be seen that the process of finding marginal
adversarial samples is a process of continuous interaction between the model
and the sample. Considering reinforcement learning is a process of continuous
interaction between the environment and the agent, which brings us
enlightenment: whether we can use reinforcement learning to optimize the
calculation process of marginal adversarial samples?

##  4 Problems and solutions

The core idea of this paper is to use a larger perturbation when the sample is
far from the decision boundary, so that the sample can quickly approach the
decision boundary, but when the sample is close to the decision boundary, a
smaller perturbation is used to make it close enough to the decision boundary.
In this paper we assumes that the output of all classification neural networks
has been normalized by softmax. Using adaptive perturbation setp faces two
problems that we must resolve.

Q1:How to measure the distance between the sample and the decision boundary?

Although the absolute distance can be used to measure the distance between the
sample and the decision boundary:

$L_{ad}=\underset{\varepsilon}{\min}(arg\max f(x+\varepsilon\cdot
sign(grad))\neq k)$ (3)

where $k$ represents the correct category. But we can’t get the value of the
absolute distance until we calculate it. We introduce the concept of relative
distance, which is easily obtained in the calculation process:

$L_{rd}=f\left(x+\varepsilon\cdot sign(grad)\right)\left[k\right]-arg\max
f\left(x+\varepsilon\cdot sign(grad)\right)\left[i\right]\left(i\neq k\right)$
(4)

The relative distance can not avoid the influence of some extreme samples, and
also can better describe the distance between the sample and the decision
boundary. In fact, MMA also used this distance initially, but due to the
instability of the first optimization term of formula (1), this distance was
not adopted anymore. As we do not directly optimize the neural network with
this distance, so this problem can be avoided.
Q2: How to dynamically adjust the step according to the $L_{rd}$?
The process of calculating marginal samples is nothing more than increasing or
reducing perturbation step size. We are keenly aware that the calculation
process of marginal adversarial samples based on FGSM satisfies Markov
properties.

######  Proposition 1.

For a classification neural network model f with fixed parameters and a sample
x,the calculation process of the marginal adversarial sample based on FGSM is
a Markov decision process. The formal description is as follows:

$f(x_{t}^{adv},y\mid
x_{t-1}^{adv},x_{t-2}^{adv},...,x_{0}^{adv})=f(x_{t}^{adv},y\mid
x_{t-1}^{adv})$ (5)

The certification process is detailed in Appendix A.1. We can use any
reinforcement learning method to optimize the process of computing marginal
adversarial samples. Considering that SAC is stable enough and insensitive to
most hyperparameters, we adopt the architecture of SAC in this article.

Algorithm 1 describes the marginal adversarial sample search based on
reinforcement learning.

Algorithm 1 Search $\varepsilon$ by Soft Actor-Critic

1:$f$: the classification neuralnetwork; $x$: the sample; $y$: the label of
$x$; $p$: the policy network of SAC; $\varepsilon_{max}$: Maximum perturbation
step size; $grad$: the gradient of $x$;$step_{max}$: The maximum number of
iterations;

2:$\varepsilon_{total},\varepsilon_{last},step\leftarrow 0$

3:$state_{0}\leftarrow(f(x)[k],f(x)[i],\varepsilon_{total},\varepsilon_{last})$

4:while $step>step_{max}$ or $reward>0$ do

5: $\varepsilon_{last}\leftarrow p(state_{0})$

6: $\varepsilon_{total}\leftarrow\varepsilon_{total}+\varepsilon_{last}$

7: calculate $reward$ by Equation (7)

8:
$state_{1}\leftarrow(f(x_{adv})[k],f(x_{adv})[i],\varepsilon_{total},\varepsilon_{last})$

9: $state_{0}\leftarrow state_{1}$

10: if the termination conditions are met then

11: $done=True$

12: $\varepsilon_{total}\leftarrow clamp(0,\varepsilon_{max}$)

13: else

14: $done=False$

15: end if

16: store $state_{0},state_{1},reward,done$

17: $step\leftarrow step+1$

18:end while

19:Return $\varepsilon_{total}$

The relevant elements of the reinforcement learning system are as follows:

(1) Environment: We regard Neural network models and samples as parts of the
environment.

(2) State space: the probability label of the sample output by the model
(environment) ,the total perturbation step size and the last perturbation step
size.

$\displaystyle
state=(f(x_{adv})[k],arg\,\,maxf(x_{adv})[i],\varepsilon_{total},\varepsilon_{last})$
(6)

where $x^{adv}=x+\varepsilon_{total}\cdot sign(grad)$ and $i\neq k$
(3) Reward function:

$reward=\begin{cases}-\frac{1}{1+e^{-\lvert
L_{rd}\rvert}},&L_{rd}>upper\,\,bound\\\
P(a\,\,positive\,\,constant),&low\,\,bound<=L_{rd}<=upper\,\,bound\\\
-\frac{1}{1+e^{-\lvert L_{rd}\rvert}},&L_{rd}<low\,\,bound\\\ \end{cases}$ (7)

There is $lower\,\,bound\leqslant 0\leqslant upper\,\,bound$. The working
mechanism is as follows: before finding the perturbation step that meets the
requirements, each step will receive a negative reward, until the step that
meets the conditions is found or the maximum number of iterations is exceeded.

The design of the reward function follows two principles:
Avoid sparse rewards. Reward sparseness refers to the fact that it is
difficult for the agent to receive a clear reward in most cases during
training. The reward function we designed will receive a positive or negative
reward at every iteration to avoid sparse rewards.
Increase the distinction between different positive rewards. Under the
condition of finding the adversarial perturbation satisfying the condition,
the computational step size of finding that should be reduced as much as
possible.

######  Definition 1 (Distinction).

For any positive real number $a,b,c,d\in\mathbb{R^{+}}$, If
$\frac{a}{b}>\frac{c}{d}$ then it is said that the distinction between $a$ and
$b$ is greater than that of $c$ and $d$.

The formula for calculating the lower bound of $P$ is as follows:

$P=\int_{\lvert
lower\,\,bound\lvert}^{1}\frac{1}{1+e^{-L_{rd}}}dL_{rd}+\int_{upper\,\,bound}^{1}\frac{1}{1+e^{-L_{rd}}}dL_{rd}$
(8)

It can be ensured that there will not be a situation where a perturbation that
satisfies the condition is found but the total reward is negative.

######  Proposition 2.

Taking into account the degree of discrimination, formula (8) is the optimal
value of $P$.

(4) Action space: Here we only need to add or subtract the steps to complete
the one-dimensional action space. What we need to do is to limit the upper and
lower limits of the action, that is, the upper and lower limits of adversarial
perturbation step size.

The above are some settings of the key elements of reinforcement learning. In
the actual training process, because the parameters of the model are
constantly updated, the policy network needs to be trained when it cannot work
well. But according to our observations in the experiment, the model needs to
be updated hundreds of times, and the policy network only needs to be updated
a few times.

The final loss function is as follows:

$\mathcal{L}\left(x,y,\theta\right)=L\left(x_{adv},y,\theta\right)+\lambda\cdot\varOmega\left(x,y,\theta\right)$
(9)

The reason why we did not use the loss functions used in MMA and IAAT is that
we sure that the generated marginal adversarial samples are close enough to
the decision boundary. The network based on regular cross-entropy loss could
learn enough information from the samples. In fact, our experiments have also
verified this hypothesis.

The pseudo code is shown in Algorithm 2.

Algorithm 2 Adaptive perturbation adversarial training

1:$f$: the classification neural network; $X$: the train set; $p$: The policy
network of SAC; $Epoch$: The maximum number of iterations;

2:for $i=1$; $i<Epoch$; $i++$ do

3: Read minibatch data $B_{(x,y)}\subset X$

4: $grad\leftarrow\nabla_{x}l(x,y,f)$

5: for $(x_{i},\ y_{i})\ in\ B_{(x,y)}$ do

6: Calculate $\varepsilon_{i}$ by Algorithm 1

7: end for

8: $x_{adv}\leftarrow x+\varepsilon\cdot sign(grad)$

9: $rate_{hit}\leftarrow$ calculate by Equation(10)

10: if $rate_{hit}<rate_{min}$ then

11: retrain policy networks

12: end if

13: update $f$ by Equation(9)

14:end for

##  5 Experiments Design

###  5.1 Fixed parameter classification model

We first conduct an experiment on a fixed-parameter model, that is , the
parameters of the classification model will not be updated. and only the model
in sac will be updated. The data set used here is MNIST MNIST .

Measurement matric. We use the hit rate to measure the pros and cons of the
method.If the relative distance of a marginal adversarial sample satisfies
$0\leqslant L_{rd}\leqslant 0.1$ , we call it a hit. The formula for
calculating the hit rate is as follows:

$hit\,\,rate=\frac{x_{success}}{x_{total}}$ (10)

Where $x_{success}$ represents the hit sample, $x_{total}$ is the total number
of samples calculated. We only perform calculations on samples correctly
identified by the model. Considering that it is possible to get the same
reward multiple times in the early training stage, the value of P in actual
training is set as follows:

$P_{\min}=step_{\max}\cdot\frac{1}{1+e^{-1}}$ (11)

Figure 1 shows the change in the hit rate of policy networks during the
training process. The structure of the classification network for MNIST is
shown in Table 6. What needs to be pointed out here is that the abscissa is
the number of batch size instead of the number of epochs. We compared the
impact of different $P$ values on the training process. The maximum number of
iterations for each sample is 10 times. Generally speaking, a smaller $P$ will
increase the upper limit of performance after convergence, which is consistent
with our theoretical derivation. However, from the experimental results, an
appropriate increase of this value will help speed up the training, but the
impact of an extreme $P$ value on training is disastrous.

Figure 1:  Hit rate of different positive reward.

We also compared different methods, as shown in Table 1. The data in Table 1
is calculated using the MNIST test set data, which has a total of 10,000
samples. Fixed policy parameters during testing. Set p=10. And the policy
networks trained with train data of MNIST for 1 epoch. The number of correctly
identified samples is 9914. The SAC hyperparameter settings of all experiments
are shown in Table 5. Using this parameter in all experiments.

Table 1: Comparison of different methods.

method | Number of hits | Total number of calculations | Hit rate
---|---|---|---
$\varepsilon_{step}=0.03$ ($step_{max}$ = 10) | 708 | 95890 | 7.14%
$\varepsilon_{step}=0.01$ ($step_{max}$ = 30) | 2015 | 271160 | 20.32%
Binary search($step_{max}$ = 5) | 4110 | 45567 | 41.36%
Binary search ($step_{max}$ = 10) | 8444 | 59176 | 85.17%
RL (ours) ($step_{max}$ = 5) | 8765 | 32337 | 88.41%
RL (ours) ($step_{max}$ = 10) | 9599 | 35398 | 96.82%

###  5.2 Adversarial training

We tested on two data sets, namely Cifar10 CIFAR-10  and SVHN SVHN , and the
used classification model is PreAct-ResNet-18 Pre-Act_Resnet-18 . The
parameter settings are shown in Table 4. Classification neural network uses
SGD optimizer, momentum=0.9 and weight decay=5$\times 10^{-4}$. The adjustment
method of learning rate is cyclical learning rates CLR . The Cifar10 data set
adjusts the learning rate within 1-30 epochs, SVHN adjusts the learning rate
within 1-15 epochs, and trains at a learning rate of 1e-3 in the remaining
epochs. If the average hit rate of the last 10 batches is less than 90%, the
policy network will be trained.

The experimental results on the cifar10 data set are shown in Table 2.
Compared with MMA, our method has similar performance, especially when PGD
attack iterations are less than 20. Our proposed method only requires 40
epochs to reach convergence, however, the MMA requires 50,000 epochs to reach
convergence. Therefore, considering the number of back propagation and the
epochs required for training, the training cost of our proposed method is
lower than that of MMA.

Table 2: Experimental results of different adversarial training on Cifar10.

Model | Attack
---|---
None | Pgd-10 | Pgd-20 | Pgd-50
Standard | 94.03% | 0.00% | 0.00% | 0.00%
FGSM +align ($\varepsilon$ = 8/255) | 81.80% | 50.83% | 49.04% | 48.14%
Free AT ($\varepsilon$ = 8/255) | 84.09% | 49.06% | 49.04% | 47.12%
PGD-10 AT ($\varepsilon$ = 8/255) | 80.86% | 52.05% | 51.16% | 50.74%
MMA ($\varepsilon_{max}$=12/255) | 88.59% | 49.05% | 46.32% | 45.10%
MMA ($\varepsilon_{max}$=20/255) | 84.36% | 54.94% | 52.87% | 51.69%
Ours ($\varepsilon_{max}$=8/255) | 87.52% | 50.86% | 46.60% | 44.03%
Ours ($\varepsilon_{max}$=10/255) | 85.80% | 55.73% | 52.09% | 49.78%

The experimental results on the SVHN data set are shown in Table 3. SVHN is a
data set that are difficult to train. If a constant perturbation step size is
applied to samples during the training process, then the training will fail.
Our proposed method, free-AT and FGSM + align prematurely converge to a local
optimal value, and the final recognition rate is about 23%. Only PGD-AT does
not be affected. Therefore, in the first five epochs of training, we gradually
increase the perturbation steps size from 0 to 8/255 or 10/255. As for Free-
AT, we use normal training in the first five epochs, and then switch to Free-
AT training.

Table 3: Experimental results of different adversarial training on SVHN.

Model | Attack
---|---
None | Pgd-10 | Pgd-20 | Pgd-50
Standard | 96.00% | 1.37% | 0.67% | 0.50%
FGSM +align ($\varepsilon$ = 8/255) | 91.13% | 52.93% | 49.70% | 47.95%
Free AT ($\varepsilon$ = 8/255) | 82.43% | 43.16% | 41.18% | 40.14%
PGD-10 AT ($\varepsilon$ = 8/255) | 91.31% | 59.77% | 57.97% | 57.20%
Ours ($\varepsilon_{max}$=8/255) | 94.40% | 55.14% | 48.60% | 43.37%
Ours ($\varepsilon_{max}$=10/255) | 93.96% | 56.45% | 49.65% | 45.46%

Table 4: Hyperparameter settings.

Dataset | Step size | Learning rate | $\Lambda$ | epoch
---|---|---|---|---
Cifar10 |  $\varepsilon_{max}$ = 8/255 | $lr_{max}=0.3,lr_{min}=1\times 10^{-3}$ | 0.2 | 40
$\varepsilon_{max}$ = 10/255 | 0.356
SVHN |  $\varepsilon_{max}$ = 8/255 | $lr_{max}=0.15,lr_{min}=1\times 10^{-3}$ | 2.5 | 20
$\varepsilon_{max}$ = 10/255 | 2.812

Table 5:  Hyperparameter of SAC.

Hyperparameter | Value
---|---
Batch size | 512
Critic network | (1024,1024)
Actor (Policy) network | (1024,1024)
Learning rate | $3\times 10^{-4}$
Optimizer | Adam
Replay buffer size | $1\times 10^{6}$
Exploration policy | Uniform Distribution, range (-8/255, 16/255)
Discount factor | 0.99
Target update rate | $5\times 10^{-3}$

Table 6:  Classification network architecture for MNIST.

Input: 1 × 28 × 28 image
---
4 x 4 conv ,16, stride=2, padding=1
Relu
4 x 4 conv ,32, stride=2, padding=1
Relu
Flatten
Linear(1538,100)
Relu
Linear(100, 10)
Output: 1 x 10 tensor

##  6 Conclusion

This paper in-depth analysis the calculation process of the marginal
adversarial samples, and also proposes the use of reinforcement learning to
calculate the perturbation step length, which further saves the calculation
cost, and can quantitatively calculate the marginal adversarial samples with a
specified relative distance, and demonstrates its superior performance through
exhaustive experiments. However, in terms of broadly searching the adversarial
sample space, the effect of PGD is still better than our proposed method and
MMA, Free-AT, etc. Therefore, exploring how to better search the adversarial
sample space may be the key to improving the performance of these methods. In
addition, reinforcement learning may not be the only way to perturbation step
and boundary distance modeling. We believe that if a better method is found,
the computational cost of searching for marginal adversarial sample will be
further reduced.

##  Appendix A Proofs

###  A.1 Proof of Proposition 1

Proof: For the FGSM-based marginal adversarial sample calculation process:

$\displaystyle x_{0}^{adv}=x+\varepsilon_{0}\cdot
sign(\nabla_{x}\ell\left(x,y,\theta\right))$ $\displaystyle
x_{0}^{adv}=x+\varepsilon_{0}\cdot
sign(\nabla_{x}\ell\left(x,y,\theta\right))$ $\displaystyle......$
$\displaystyle x_{t}^{adv}=x_{t-1}+\varepsilon_{t}\cdot
sign(\nabla_{x}\ell\left(x,y,\theta\right))$

Apparently

$x_{t}^{adv}=x+\sum_{t}^{i=0}{\varepsilon_{i}}\cdot\nabla_{x}\ell\left(x,y,\theta\right)$
(12)

For any sequence of perturbation steps
$\varepsilon_{a}=\left(\varepsilon_{0},\varepsilon_{1},...,\varepsilon_{a-1},\varepsilon_{a}\right)$
and
$\varepsilon_{b}=\left(\varepsilon_{0},\varepsilon_{1},...,\varepsilon_{b-1},\varepsilon_{b}\right)$,
if
$\varepsilon_{a}^{{}^{\prime}}\subseteq\varepsilon_{a}$,$\varepsilon_{b}^{{}^{\prime}}\subseteq\varepsilon_{b}$
and $\sum{\varepsilon_{a}^{{}^{\prime}}}=\sum{\varepsilon_{b}^{{}^{\prime}}}$,
from formula (A1) we know that
$x_{\varepsilon_{a}^{{}^{\prime}}}^{adv}=x_{\varepsilon_{b}^{{}^{\prime}}}^{adv}$.
That is to say, the adversarial sample is only related to the sum of the
elements of the perturbation sequence, and has nothing to do with the size of
a single element of the perturbation sequence and the order of the elements.
Therefore, for any sequence of perturbation steps
$\varepsilon=\left(\varepsilon_{0},\varepsilon_{1},...,\varepsilon_{k-1},\varepsilon_{k}\right)$
there must be:

$f(x_{t}^{adv},y\mid
x_{t-1}^{adv},x_{t-2}^{adv},...,x_{0}^{adv})=f(x_{t}^{adv},y\mid
x_{t-1}^{adv})$

###  A.2 Proof of Proposition 2

Proof. let $P_{1}$, $P_{2}$, satisfy $P_{1}<P_{2}$.
For any reward sequence $reward_{1}={r_{1},r_{2},...,r{j}}$ satisfy
$r_{m}<0.m<j$ and $reward_{2}={r_{1},r_{2},...,r{k}}$ satisfy $r_{m}<0.m<k$.
Substitute $P_{1}$, $P_{2}$ into $r_{j},r_{k}$.
For $P_{1}$,there is $P_{1}+\sum_{j-1}^{i=1}{r_{i}}$,
$P_{1}+\sum_{k-1}^{i=1}{r_{i}}$.
For $P_{2}$,there is $P_{2}+\sum_{j-1}^{i=1}{r_{i}}$,
$P_{2}+\sum_{k-1}^{i=1}{r_{i}}$.

$\frac{P_{1}+\sum_{j-1}^{i=1}{r_{i}}}{P_{1}+\sum_{k-1}^{i=1}{r_{i}}}-\frac{P_{2}+\sum_{j-1}^{i=1}{r_{i}}}{P_{2}+\sum_{k-1}^{i=1}{r_{i}}}\\\
=\frac{\left(P_{1}+\sum_{j-1}^{i=1}{r_{i}}\right)\left(P_{2}+\sum_{k-1}^{i=1}{r_{i}}\right)-\left(P_{2}+\sum_{j-1}^{i=1}{r_{i}}\right)\left(P_{1}+\sum_{k-1}^{i=1}{r_{i}}\right)}{\left(P_{1}+\sum_{k-1}^{i=1}{r_{i}}\right)\left(P_{2}+\sum_{k-1}^{i=1}{r_{i}}\right)}\\\
=\frac{\left[P_{1}P_{2}+\sum_{j-1}^{i=1}{r_{i}}\cdot
P_{2}+\sum_{k-1}^{i=1}{r_{i}}\cdot
P_{1}+\sum_{j-1}^{i=1}{r_{i}}\cdot\sum_{k-1}^{i=1}{r_{i}}\right]-\left[P_{1}P_{2}+\sum_{j-1}^{i=1}{r_{i}}\cdot
P_{1}+\sum_{k-1}^{i=1}{r_{i}}\cdot
P_{2}+\sum_{j-1}^{i=1}{r_{i}}\cdot\sum_{k-1}^{i=1}{r_{i}}\right]}{\left(P_{1}+\sum_{k-1}^{i=1}{r_{i}}\right)\left(P_{2}+\sum_{k-1}^{i=1}{r_{i}}\right)}\\\
=\frac{\left(\sum_{j-1}^{i=1}{r_{i}}\cdot P_{2}+\sum_{k-1}^{i=1}{r_{i}}\cdot
P_{1}\right)-\left(\sum_{j-1}^{i=1}{r_{i}}\cdot
P_{1}+\sum_{k-1}^{i=1}{r_{i}}\cdot
P_{2}\right)}{\left(P_{1}+\sum_{k-1}^{i=1}{r_{i}}\right)\left(P_{2}+\sum_{k-1}^{i=1}{r_{i}}\right)}\\\
=\frac{\sum_{j-1}^{i=1}{r_{i}}\left(P_{2}-P_{1}\right)+\sum_{k-1}^{i=1}{r_{i}}\left(P_{1}-P_{2}\right)}{\left(P_{1}+\sum_{k-1}^{i=1}{r_{i}}\right)\left(P_{2}+\sum_{k-1}^{i=1}{r_{i}}\right)}\\\
=\frac{\left(P_{1}-P_{2}\right)\left(\sum_{k-1}^{i=1}{r_{i}}-\sum_{j-1}^{i=1}{r_{i}}\right)}{\left(P_{1}+\sum_{k-1}^{i=1}{r_{i}}\right)\left(P_{2}+\sum_{k-1}^{i=1}{r_{i}}\right)}$

Because $P_{1}+\sum_{k-1}^{i=1}{r_{i}}>0$, $P_{2}+\sum_{j-1}^{i=1}{r_{i}}>0$,
$P_{1}<P_{2}$, and $\sum_{k-1}^{i=1}{r_{i}}<\sum_{j-1}^{i=1}{r_{i}}$, so there
is
$\frac{P_{1}+\sum_{j-1}^{i=1}{r_{i}}}{P_{1}+\sum_{k-1}^{i=1}{r_{i}}}>\frac{P_{2}+\sum_{j-1}^{i=1}{r_{i}}}{P_{2}+\sum_{k-1}^{i=1}{r_{i}}}$.
Therefore, under the premise that the sum of the reward queue is positive, the
smaller the P value, the greater the distinction.

## References

  *   * (1) Goodfellow, I.J., Shlens, J., Szegedy, C.: Explaining and harnessing adversarial examples. arXiv preprint arXiv:1412.6572 (2014)
  * (2) Madry, A., Makelov, A., Schmidt, L., Tsipras, D., Vladu, A.: Towards deep learning models resistant to adversarial attacks. arXiv preprint arXiv:1706.06083 (2017)
  * (3) Shafahi, A., Najibi, M., Ghiasi, A., Xu, Z., Dickerson, J., Studer, C., Davis, L.S., Taylor, G., Goldstein, T.: Adversarial training for free! arXiv preprint arXiv:1904.12843 (2019)
  * (4) Zhang, D., Zhang, T., Lu, Y., Zhu, Z., Dong, B.: You only propagate once: Accelerating adversarial training via maximal principle. arXiv preprint arXiv:1905.00877 (2019)
  * (5) Wong, E., Rice, L., Kolter, J.Z.: Fast is better than free: Revisiting adversarial training. arXiv preprint arXiv:2001.03994 (2020)
  * (6) Andriushchenko, M., Flammarion, N.: Understanding and improving fast adversarial training. arXiv preprint arXiv:2007.02617 (2020)
  * (7) Kim, H., Lee, W., Lee, J.: Understanding catastrophic overfitting in single-step adversarial training. arXiv preprint arXiv:2010.01799 (2020)
  * (8) Ding, G.W., Sharma, Y., Lui, K.Y.C., Huang, R.: Mma training: Direct input space margin maximization through adversarial training. arXiv preprint arXiv:1812.02637 (2018)
  * (9) Balaji, Y., Goldstein, T., Hoffman, J.: Instance adaptive adversarial training: Improved accuracy tradeoffs in neural nets. arXiv preprint arXiv:1910.08051 (2019)
  * (10) Puterman, M.L.: Markov decision processes. Handbooks in operations research and management science 2, 331–434 (1990)
  * (11) Mnih, V., Kavukcuoglu, K., Silver, D., Graves, A., Antonoglou, I., Wierstra, D., Riedmiller, M.: Playing atari with deep reinforcement learning. arXiv preprint arXiv:1312.5602 (2013)
  * (12) Lillicrap, T.P., Hunt, J.J., Pritzel, A., Heess, N., Erez, T., Tassa, Y., Silver, D., Wierstra, D.: Continuous control with deep reinforcement learning. arXiv preprint arXiv:1509.02971 (2015)
  * (13) Fujimoto, S., Hoof, H., Meger, D.: Addressing function approximation error in actor-critic methods. In: International Conference on Machine Learning, pp. 1587–1596 (2018). PMLR
  * (14) Schulman, J., Levine, S., Abbeel, P., Jordan, M., Moritz, P.: Trust region policy optimization. In: International Conference on Machine Learning, pp. 1889–1897 (2015). PMLR
  * (15) Schulman, J., Wolski, F., Dhariwal, P., Radford, A., Klimov, O.: Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347 (2017)
  * (16) Haarnoja, T., Zhou, A., Abbeel, P., Levine, S.: Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. In: International Conference on Machine Learning, pp. 1861–1870 (2018). PMLR
  * (17) LeCun, Y.: The mnist database of handwritten digits. http://yann. lecun. com/exdb/mnist/ (1998)
  * (18) Krizhevsky, A., Hinton, G., et al.: Learning multiple layers of features from tiny images (2009)
  * (19) Netzer, Y., Wang, T., Coates, A., Bissacco, A., Wu, B., Ng, A.Y.: Reading digits in natural images with unsupervised feature learning (2011)
  * (20) He, K., Zhang, X., Ren, S., Sun, J.: Identity mappings in deep residual networks. In: European Conference on Computer Vision, pp. 630–645 (2016). Springer
  * (21) Smith, L.N.: Cyclical learning rates for training neural networks. In: 2017 IEEE Winter Conference on Applications of Computer Vision (WACV), pp. 464–472 (2017). IEEE


# On the Hardness of Opinion Dynamics Optimization with $L_{1}$-Budget on
Varying Susceptibility to Persuasion

T-H. Hubert Chan The University of Hong Kong<EMAIL_ADDRESS>Chui Shan Lee
The University of Hong Kong<EMAIL_ADDRESS>
Recently, Abebe et al. (KDD 2018) and Chan et al. (WWW 2019) have considered
an opinion dynamics optimization problem that is based on a popular model for
social opinion dynamics, in which each agent has some fixed innate opinion,
and a resistance that measures the importance it places on its innate opinion;
moreover, the agents influence one another’s opinions through an iterative
process. Under certain conditions, this iterative process converges to some
equilibrium opinion vector. Previous works gave an efficient local search
algorithm to solve the unbudgeted variant of the problem, for which the goal
is to modify the resistance of any number of agents (within some given range)
such that the sum of the equilibrium opinions is minimized. On the other hand,
it was proved that the $L_{0}$-budgeted variant is NP-hard, where the
$L_{0}$-budget is a restriction given upfront on the number of agents whose
resistance may be modified.

Inspired by practical situations in which the effort to modify an agent’s
resistance increases with the magnitude of the change, we propose the
$L_{1}$-budgeted variant, in which the $L_{1}$-budget is a restriction on the
sum of the magnitudes of the changes over all agents’ resistance parameters.
In this work, we show that the $L_{1}$-budgeted variant is NP-hard via a
reduction from vertex cover. However, contrary to the $L_{0}$-budgeted
variant, a very technical argument is needed to show that the optimal solution
can be achieved by focusing the given $L_{1}$-budget on as small a number of
agents as possible, as opposed to spreading the budget over a large number of
agents.

##  1 Introduction

The process of social influence is a significant basis for opinion formation,
decision making and the shaping of an individual’s identity. It drives many
social phenomenon ranging from the emergence of trends, diffusion of rumor,
and the shaping of public views about social issues. An opinion formation
model was introduced by the works of DeGroot [DeG74] and Friedkin and Johnsen
[FJ99], which considered how agents’ influence one another’s opinions in
discrete time steps. In this model, each agent $i$ has some innate opinion
$s_{i}$ in $[0,1]$, which reflects the intrinsic position of the agent on a
certain topic. The expressed opinion of an agent is updated in each iteration
according to the weighted average of other agents’ opinions (according to the
_interaction matrix_) and its innate opinion. The weight that an agent assigns
to its own innate opinion is captured by a resistance parameter
$\alpha_{i}\in[0,1]$, where a higher value for the resistance parameter means
that the agent is less susceptible to persuasion by the opinions of other
agents. Under very mild conditions, the expressed opinions of the agents
converge to an equilibrium, which is a function of the innate opinions, the
interaction matrix between the agents and the agents’ resistance parameters.

Recent works by Abebe et al. [AKPT18] and Chan et al. [CLS19] have considered
the opinion dynamics optimization problem, in which the innate opinions and
the interaction matrix between agents are given as the input, and the goal is
to minimize the average equilibrium opinion by varying the agents’ resistance
parameter. As mentioned in their works, the motivation of the problem has been
inspired by empirical works in development and social psychology that studied
people’s susceptibility to persuasion, and more references to related work and
applications are given in [AKPT18, CLS19].

Restrictions on how the agents’ resistance parameters may be modified lead to
different variants of the problem with different hardness. At the trivial end
of the spectrum, if one can choose any $\alpha_{i}\in[0,1]$ for every agent
$i$, then the trivial solution to minimize the average equilibrium is to set
$\alpha_{i}=1$ for the agent with the minimum innate opinion and set the
resistance of all other agents to 0, provided that the interaction matrix
among the agents is _irreducible_ , in the sense that every agent has some
direct or indirect influence over every other agent. If the resistance of each
agent $i$ must be chosen from some restricted interval
$[l_{i},u_{i}]\subseteq[0,1]$, then an efficient local search method is given
in [CLS19] such that the minimum average equilibrium can be achieved by
setting each agent’s resistance parameter to either its lower $l_{i}$ or upper
$u_{i}$ bound. In addition to the restriction intervals, the problem gets
harder if one places further restrictions on the number of agents whose
resistance parameters may be modified. The $L_{0}$-budgeted variant has some
initial resistance vector $\widehat{\alpha}$ for all agents and some budget
$k$, and the algorithm is allowed to change the resistance parameters of at
most $k$ agents. Indeed, it is shown in [AKPT18] that the $L_{0}$-budgeted
variant is NP-hard via a reduction from the vertex cover problem.

Intuitively, in the reduction construction for proving the NP-hardness of the
$L_{0}$-budgeted variant, the set of agents whose resistance parameters are
modified corresponds to a set of vertices to be considered as a candidate as a
vertex cover in some graph. Hence, it seems that the binary nature of the
choice for each agent contributes to the hardness of the problem. A natural
question is whether the problem becomes easier if one is allowed to make
“fractional” decision for each agent. From a practical point of view, the
$L_{0}$-budget uses the implicit assumption that modifying the resistance
parameter of an agent a little takes the same effort as modifying it by a lot.
However, it is reasonable to assume that the effort it takes to modify an
agent’s resistance should be proportional to the magnitude of the change.

With such motivations in mind, we propose the $L_{1}$-budgeted variant in this
work. Similar to the $L_{0}$-budgeted variant in which an initial resistance
vector $\widehat{\alpha}$ and a budget $k$ is given, the goal is to minimize
the average equilibrium opinion by choosing a vector $\alpha$ (satisfying any
restriction interval placed on each agent) such that
$\lVert\alpha-\widehat{\alpha}\rVert_{1}\leq k$.

###  1.1 Our Contributions

At first sight, the efficient local search techniques in [CLS19] and the
fractional nature of the $L_{1}$-budget suggest that the problem might be
solved optimally by some gradient method or mathematical program. Indeed,
there are examples in which the optimal solution is achieved by assigning the
budget to modify the agents’ resistance partially, i.e., the resistance
parameter an agent does not reach its specified lower or upper bound. However,
it turns out that this variant is also NP-hard.

######  Theorem 1.1.

The $L_{1}$-budgeted variant of the opinion dynamics optimization problem is
NP-hard.

_Hardness Intuition._ Given an $L_{1}$-budget, whether one should spread the
budget among many agents or focus it on a small number of agents depends on
the interaction matrix among the agents. When we tried to understand the
structure of the problem by studying various examples, we discovered that if
two agents have little direct or indirect influence on each other, then the
$L_{1}$-budget should be shared among them. However, if all agents are well-
connected such as the case of a clique, then the budget should be as focused
as possible on a small number of agents. Hence, intuitively, the problem
should be hard if the underlying interaction matrix among the agents resembles
a well-connected graph.

The difficulty here is that we do not yet know how to quantify the well-
connectedness of the interaction matrix in relation to this _budget-focus_
effect. Furthermore, the hardness still relies on the reduction from the
vertex cover problem, whose hardness has not been extensively studied for
graphs with different connectivity. Our solution to the reduction construction
is to consider an interaction matrix that is a convex combination of a clique
and some given graph $G$ that is supposed to be an instance of the vertex
cover problem.

The high level argument is that as long as the weight of the clique is large
enough, the aforementioned budget-focus effect should be in place. However, as
long as there is a non-zero weight of the graph $G$ on the interaction matrix,
the existence of a vertex cover for $G$ of a certain size will have a
quantifiable effect on the optimal average equilibrium opinion given a certain
$L_{1}$-budget. Even though the general approach is not too complicated,
combining these ideas require quite technical calculations.

_Outline._ In Section 2, we will introduce the notation and formally recall
various variants of the problem. In Section 3, we will give our reduction
construction and explain the intuition behind the proofs. Finally, the most
technical details are deferred to Section 4.

##  2 Preliminaries

We recall the problem setting as described in [AKPT18, CLS19]. Consider a set
$N$ of _agents_ , where each agent $i\in N$ is associated with an _innate
opinion_ $s_{i}\in[0,1]$ (where higher values correspond to more favorable
opinions towards a given topic) and a parameter measuring an agent’s
susceptibility to persuasion $\alpha_{i}\in[0,1]$ (where higher values signify
agents who are less susceptible to changing their opinions). We call
$\alpha_{i}$ the _resistance parameter_.

The agents interact with one another in discrete time steps. The interaction
matrix captures the relationship between agents and is simply a row stochastic
matrix111 Given sets $U$ and $W$, we use the notation $U^{W}$ to denote the
collection of all functions from $W$ to $U$. Each such function can also be
interpreted as a vector (or a matrix if $W$ itself is a Cartesian product),
where each coordinate is labeled by an element in $W$ and takes a value in
$U$. As an example, a member of $[0,1]^{N\times N}$ is a matrix whose rows and
columns are labeled by elements of $N$. The alternative notation
$[0,1]^{n\times n}$ implicitly assumes a linear ordering on $N$, which does
not have any importance in our case and would simply be an artefact of the
notation. $P\in[0,1]^{N\times N}$ (i.e., each entry of $P$ is non-negative and
every row sums to 1, but $P$ needs not be symmetric). We denote
$A=\operatorname{Diag}(\alpha)$ as the diagonal matrix with
$A_{ii}=\alpha_{i}$, and $I$ as the identity matrix. Starting from some
arbitrary initial expressed opinion vector $z^{(0)}\in[0,1]^{N}$, the
expressed opinion vector is updated in each time step according to the
following equation:

$z^{(t+1)}:=As+(I-A)Pz^{(t)}.$ (1)

Equating $z^{(t)}$ with $z^{(t+1)}$, one can see that the equilibrium opinion
vector is given by $z=[I-(I-A)P]^{-1}As$, which exists under very mild
conditions such as the following.

######  Fact 2.1 (Convergence Assumption).

Suppose $P$ is irreducible and at least one $i\in N$ has $\alpha_{i}>0$. Then,
equation (1) converges to a unique equilibrium
$\lim_{t\rightarrow\infty}z^{(t)}$.

The opinion susceptibility problem is defined below. Intuitively, the
objective is to choose a resistance vector $\alpha$ to minimize the sum of
equilibrium opinions $\langle\mathbf{1},z\rangle=\mathbf{1}^{\top}z$, i.e.,
the goal is to drive the average opinion towards 0. Observe that one can also
consider maximizing the sum of equilibrium opinions. To see that the
minimization and maximization problems are equivalent, consider the
transformation $x\mapsto 1-x$ on the opinion space $[0,1]$ that is applied to
the innate opinions and expressed opinions in every time step. In this paper,
we will focus on the minimization problem as follows.

######  Definition 2.2 (Opinion Susceptibility Problem (Unbudgeted Variant)).

Given a set $N$ of agents with innate opinions $s\in[0,1]^{N}$ and interaction
matrix $P\in[0,1]^{N\times N}$, suppose for each $i\in N$, its resistance is
restricted to some interval $\mathcal{I}_{i}:=[l_{i},u_{i}]\subseteq[0,1]$
where we assume222In view of Fact 2.1, we assume that for at least one $i$,
$l_{i}>0$. that $0\leq l_{i}\leq u_{i}\leq 1$.

The objective is to choose $\alpha\in\mathcal{I}_{N}:=\times_{i\in
N}\mathcal{I}_{i}\subseteq[0,1]^{N}$ such that the following objective
function is minimized:

$f(\alpha):=\mathbf{1}^{\top}[I-(I-A)P]^{-1}As,$

where $A=\operatorname{Diag}(\alpha)$ is the diagonal matrix with
$A_{ii}=\alpha_{i}$. Observe that the assumption in Fact 2.1 ensures that the
above inverse exists.

_Budgeted Variants._ To describe different types of budgets, we use the
following norms. Given $x\in\mathbb{R}^{N}$, we denote its $L_{0}$-norm
$\lVert x\rVert_{0}:=|\\{i\in N:x_{i}\neq 0\\}|$ and its $L_{1}$-norm $\lVert
x\rVert_{1}:=\sum_{i\in N}|x_{i}|$. For $b\in\\{0,1\\}$, the $L_{b}$-budgeted
variant of the problem also has some initial resistance vector
$\widehat{\alpha}\in\mathcal{I}_{N}$ and a given budget $k>0$. The goal is to
find $\alpha\in\mathcal{I}_{N}$ to minimize $f(\alpha)$ subject to
$\lVert\alpha-\widehat{\alpha}\rVert_{b}\leq k$.

_Hardness of the Various Variants._ A polynomial-time algorithm is given for
the unbudgeted variant in [CLS19], while the $L_{0}$-budgeted variant is shown
to be NP-hard in [AKPT18] via a reduction from vertex cover problem. The main
result of this work is to show that the $L_{1}$-budgeted variant is also NP-
hard.

##  3 Hardness of $L_{1}$-Budgeted Variant

As in [AKPT18], we shall prove the NP-hardness of the $L_{1}$-budgeted variant
via reduction from the vertex cover problem on regular graphs [Fei03], where a
graph is $d$-regular if every vertex has degree $d$.

######  Fact 3.1 (Vertex Cover on Regular Graphs).

Given a $d$-regular undirected graph $G=(V,E)$ and some $k>0$, it is NP-hard
(even for $d=3$) to decide if $G$ has a vertex cover $T$ of size $k$, where
$T\subseteq V$ is a vertex cover for $G$ if every edge in $E$ has at least one
end-point in $T$.

###  3.1 Warmup: Reduction for $L_{0}$-Budget

Before we give our final reduction construction for $L_{1}$-budget, we give a
simplified reduction for $L_{0}$-budget, which will offer some intuition on
why the $L_{1}$-budget reduction is more complicated. The reduction here for
$L_{0}$-budget is similar to the one given in [AKPT18], but is even simpler
because we allow different agents $i$ to have different ranges $[l_{i},u_{i}]$
for their resistance parameters.

Recall that an instance of the vertex cover problem consists of a $d$-regular
graph $G=(V,E)$ with $n=|V|$ and some target vertex cover size $k$.

_Reduction Construction._ In addition to the original vertices in $V$, we
create one extra agent 0 to form $N:=V\cup\\{0\\}$. For the innate opinions,
$s_{0}=1$ and $s_{i}=0$ for $i\neq 0$; for the initial resistances,
$\widehat{\alpha}_{0}=1$ and $\widehat{\alpha}_{i}=0$ for $i\neq 0$. For the
range of resistance parameter, we restrict $\mathcal{I}_{0}=\\{1\\}$ and
$\mathcal{I}_{i}=[0,1]$ for $i\neq 0$; in other words, agent $0$ will always
remain the most stubborn, while agents in $V$ have 0 resistance initially, but
their resistance parameters could be increased to 1 subject to the budget
constraint. The $L_{0}$-budget is $k$, which is the same as the target cover
size. Our final construction for the $L_{1}$-budget will also share the above
parameter settings.

_Interaction Matrix for $L_{0}$-Budget Reduction._ We next describe the
interaction matrix $P$. For agent 0, we will always have resistance
$\alpha_{0}=1$, and so the corresponding row in $P$ is irrelevant, but we
could set $P_{0i}=\frac{1}{n}$ for $i\in V$ to be concrete. For $i\neq 0$, let
$P_{ij}=\frac{1}{d+1}$ if $j=0$ or $\\{i,j\\}\in E$ is an edge in $G$,
recalling that each node $i\in V$ has degree $d$ in $G$. As we shall see, the
reduction for $L_{1}$-budget will have a different interaction matrix.

_Intuition._ For the $L_{0}$-budgeted variant, if we wish to change the
resistance parameter of an agent $i\in V$ (who has innate $s_{i}=0$), we might
as well set it to $\alpha_{i}=1$, because the goal is to minimize the
expressed opinion. To complete the reduction proof, it suffices to give a
threshold $\vartheta$ for the objective function $f$ that can distinguish
between the YES and NO instances of the vertex cover problem. The following
two lemmas complete the reduction argument.

######  Lemma 3.2 (YES Instance).

Let $\vartheta:=1+\frac{n-k}{d+1}$. Suppose $G=(V,E)$ has a vertex cover $T$
of size $k$. Then, by changing the resistance parameters to $\alpha_{i}=1$ for
all $i\in T$ (while those for other agents are not changed), we can achieve
$f(\alpha)=\vartheta$.

###### Proof.

We compute the equilibrium expressed opinion of each agent. For agent $0$, we
have $z_{0}=1$; for $i\in T$ in the vertex cover, we have $z_{i}=0$.

For $i\in V\setminus T$, we still have $\alpha_{i}=0$. Since all its neighbors
in $V$ are in $T$ and $i$ is influenced by agent $0$, we have
$z_{i}=\frac{1}{d+1}$.

Therefore, $f(\alpha)=\sum_{i\in N}z_{i}=1+|T|\cdot 0+|V\setminus
T|\cdot\frac{1}{d+1}=\vartheta$, as required. ∎

######  Lemma 3.3 (NO Instance).

Suppose $G=(V,E)$ has no vertex cover of size $k$. Then, for any
$\alpha\in\mathcal{I}_{N}$ such that
$\lVert\alpha-\widehat{\alpha}\rVert_{0}\leq k$,
$f(\alpha)\geq\vartheta+\frac{2}{d(d+1)}$.

###### Proof.

Since the goal is to minimize $f$, the minimum can be achieved by using all of
the $L_{0}$-budget $k$. Moreover, as each $i\in V$ has innate $s_{i}=0$, if we
change its resistance parameter, we should set it to $\alpha_{i}=1$. Hence, we
can assume that there is some $T\subseteq V$ of size $|T|=k$ such that
$\alpha_{i}=1$ for $i\in T$ and $\alpha_{i}=0$ for $i\in V\setminus T$. We
remark that to reach the same conclusion for the $L_{1}$-budget reduction
later will require a lot more technical details.

As in Lemma 3.2, we can conclude $z_{0}=1$ and $z_{i}=0$ for $i\in T$.

For $i\in V\setminus T$, we now only have the inequality
$z_{i}\geq\frac{1}{d+1}$. However, we can now achieve a stronger lower bound
because $T$ is not a vertex cover for $G$.

Let $\gamma$ be the minimum over all $z_{i}$ such that $i$ is incident on an
edge in $E$ that is not covered by $T$. Suppose $i\in V\setminus T$ is a
vertex that attains $\gamma$ and the edge $\\{i,j\\}$ is not covered by $T$.
Then, we have $z_{j}\geq\gamma$. Hence, we have
$\gamma=z_{i}\geq\frac{1+\gamma}{d+1}$, which implies that
$\gamma\geq\frac{1}{d}=\frac{1}{d+1}+\frac{1}{d(d+1)}$.

Since there is at least one edge in $E$ that is not covered by $T$, we have
$f(\alpha)\geq\vartheta+\frac{2}{d(d+1)}$, as required. ∎

###  3.2 Reduction for $L_{1}$-Budget

We first describe the main challenge for adapting the reduction proof for
$L_{0}$-budget to $L_{1}$-budget. The issue is that to adapt Lemma 3.3 for the
NO instances of the vertex cover problem, we need a desirable structural
property on an optimal solution for the $L_{1}$-budgeted variant of the
opinion optimization problem. Specifically, we would like to argue that to
minimize the objective function $f$ with an integral budget $k$, one should
pick a subset $T\subseteq V$ of exactly $k$ agents on whom to use the budget,
as opposed to spreading the budget fractionally over more than $k$ agents.

Unfortunately, this is not true for the reduction construction given in
Section 3.1. Indeed, we have discovered that for two agents $i$ and $j$ that
are somehow not “well-connected” in $G$, if some fixed $L_{1}$-budget of less
than 2 is assigned to them, spreading the budget fractionally among the two
agents would yield a lower objective value than biasing the budget towards one
agent. On the other hand, we discovered that the desirable structural property
holds in some cases where all the vertices in $G$ are “well-connected”, for
instance, if $G$ is a clique on the $n$ vertices. However, since there is no
connectivity assumption on the given instance $G$ of vertex cover, we consider
the following interaction matrix.

_Interaction Matrix for $L_{1}$-Budget Reduction._ Recall that we are given a
$d$-regular graph $G=(V,E)$ with $n=|V|$, and $N=V\cup\\{0\\}$. Let
$C\in[0,1]^{N\times N}$ be a row-stochastic matrix such that for $i\neq j$,
$C_{ij}=\frac{1}{n}$, recalling that $|N|=n+1$; in other words, $C$ behaves
like a clique on $N$. Let $R\in[0,1]^{N\times N}$ be a row-stochastic matrix
such that $R_{00}=1$, and $R_{ij}=\frac{1}{d}$ _iff_ $\\{i,j\\}\in E$, where
all other entries of $R$ are 0; in other words, $R$ is the normalized
adjacency matrix of $G$ with an additional isolated vertex $0$. For some
appropriate $\delta\in(0,1)$ (that depends only on $d$ and $n$), we consider
the following interaction matrix $P^{(\delta)}:=(1-\delta)C+\delta R$.

Recall that the innate opinions and initial resistance parameters are the same
as in Section 3.1, i.e., $s_{0}=\widehat{\alpha}_{0}=1$ and
$s_{i}=\widehat{\alpha}_{i}=0$ for $i\in V$. Moreover, the $L_{1}$-budget can
be used to change the resistance parameters of only agents in $V$, i.e.,
$\alpha_{0}=1$ must remain.

The lemma for YES instance is similar as that in Section 3.1 We define the
threshold $\vartheta:=1+\frac{(1-\delta)(n-k)}{n-(1-\delta)(n-k-1)}$.

######  Lemma 3.4 (YES Instance).

Suppose $G=(V,E)$ has a vertex cover $T$ of size $k$. Then, by changing the
resistance parameters to $\alpha_{i}=1$ for all $i\in T$ (while those for
other agents are not changed), we can achieve $f(\alpha)=\vartheta$.

###### Proof.

As in Lemma 3.2, the equilibrium expressed opinions are $z_{0}=1$ and
$z_{i}=0$ for $i\in T$.

For $j\in V\setminus T$, recall that $\alpha_{j}=0$ and we exploit the
symmetry in $P_{\delta}=(1-\delta)C+\delta R$ to analyze the value of $z_{j}$.
Note that with respect to $C$, agent $j$ observes that agent $0$ has $z_{0}=1$
and the $k$ agents $i\in T$ have $z_{i}=0$, and there are $n-k-1$ other agents
like itself; with respect to $R$, agent $j$ observes that all its $d$
neighbors in $G$ are in $T$, and so have $z_{i}=0$.

Therefore, every agent $j\in V\setminus T$ has this same observation, and we
can conclude that $z_{j}$’s have some common value $\gamma$ for all $j\in
V\setminus T$ satisfying:

$\gamma=(1-\delta)\cdot\frac{1}{n}\cdot(1+k\cdot 0+(n-k-1)\cdot\gamma).$

This gives $\gamma=\frac{1-\delta}{n-(1-\delta)(n-k-1)}$, and so
$f(\alpha)=1+k\cdot 0+(n-k)\cdot\gamma=\vartheta$. ∎

The following structural property is needed for the analysis of NO instances.
Its proof is technical and is deferred to Section 4.

######  Lemma 3.5 (Structural Property of Optimal Solution).

Suppose $\delta:=\frac{d^{3}(2d-1)^{3n-3}}{(n+1)^{6}(2d+1)^{3n}}$ is set to
define the interaction matrix $P^{(\delta)}$ above, and an $L_{1}$-budget of
$k$ is given to change the resistance parameters of agents in $V$. Then, the
objective function $f$ can be minimized by picking some $T\subseteq V$ of size
$k$, and setting $\alpha_{i}=1$ for $i\in T$.

######  Lemma 3.6 (NO Instance).

Suppose $G=(V,E)$ has no vertex cover of size $k$, and $\delta\in(0,1)$ is
chosen to satisfy Lemma 3.5. Then, for any $\alpha\in\mathcal{I}_{N}$ such
that $\lVert\alpha-\widehat{\alpha}\rVert_{1}\leq k$,
$f(\alpha)\geq\vartheta+\frac{\delta}{dn}$.

###### Proof.

Because of Lemma 3.5, we can assume that the minimum $f(\alpha)$ is achieved
by picking some $T\subseteq V$ of size $k$ and set $\alpha_{i}=1$ for $i\in T$
and $\alpha_{j}=0$ remains for $j\in V\setminus T$.

Again, the equilibrium expressed opinions satisfy $z_{0}=1$ and $z_{i}=0$ for
$i\in T$.

Let $\gamma:=\min_{j\in V\setminus T}z_{j}$. Then, a similar argument as in
Lemma 3.4 gives the inequality
$\gamma\geq\gamma_{0}:=\frac{1-\delta}{n-(1-\delta)(n-k-1)}$.

We can get a stronger lower bound because $T$ is not a vertex cover for
$G=(V,E)$. Let $\widehat{\gamma}$ be the minimum $z_{j}$ among $j\in
V\setminus T$ such that $j$ is an end-point of an edge not covered by $T$.

Then, we have the inequality
$\widehat{\gamma}\geq(1-\delta)\cdot\frac{1}{n}\cdot(1+k\cdot
0+(n-k-1)\cdot\gamma_{0})+\delta\cdot\frac{\widehat{\gamma}}{d}=\gamma_{0}+\widehat{\gamma}\cdot\frac{\delta}{d}$.

Hence, we have
$\widehat{\gamma}\geq(1-\frac{\delta}{d})^{-1}\cdot\gamma_{0}\geq\gamma_{0}+\frac{\delta\gamma_{0}}{d}$.

Since there is at least one edge in $E$ that is not covered by $T$ (and such
an edge has two end-points), we have
$f(\alpha)\geq\vartheta+\frac{2\delta\gamma_{0}}{d}\geq\vartheta+\frac{\delta}{dn}$,
as required. ∎

######  Corollary 3.7.

It is NP-hard to solve the $L_{1}$-budgeted variant with additive error at
most $\frac{\delta}{dn}$ on the objective function $f$.

###### Proof.

Observe that from Lemmas 3.4 and 3.6, it suffices to use a precision of
$\Theta(\frac{\delta}{dn})$ on the objective function, which can be achieved
using $O(\log\frac{dn}{\delta})={\texttt{poly}}(n)$ number of bits. ∎

##  4 Technical Proofs for Well-Connected Interaction Matrices

To complete our hardness proof in Section 3.2, it suffices to proof Lemma 3.5.
Recall that the goal is to pick some $\delta\in(0,1)$ to define the
interaction matrix $P^{(\delta)}=(1-\delta)C+\delta R$ such that given an
$L_{1}$-budget $k\in\mathbb{Z}$, the objective function $f(\alpha)$ can be
minimized by allocating the budget to exactly $k$ agents in $V$. One way to
achieve this is to pick two arbitrary agents $i,j\in V$ and show that if some
fixed $L_{1}$-budget $b<2$ is assigned for $i$ and $j$ (while the other agents
are not modified), then the objective function $f(\alpha)$ can be minimized by
prioritizing the budget to either $i$ or $j$ as much as possible. Denoting
$e_{i}\in[0,1]^{N}$ as the unit vector with $i\in N$ as the only non-zero
coordinate, we shall prove the following.

Formal Goal. By setting
$\delta=\frac{d^{3}(2d-1)^{3n-3}}{(n+1)^{6}(2d+1)^{3n}}$, we will show that if
$i,j\in V$ are such that $0\leq\alpha_{i},\alpha_{j}<1$, then the second
derivative of $f$ in the direction $e_{i}-e_{j}$ satisfies:

$(e_{i}-e_{j})^{\top}\nabla
f(\alpha)=0\implies(e_{i}-e_{j})^{\top}\nabla^{2}f(\alpha)(e_{i}-e_{j})<0.$
(2)

Statement (2) implies that if two agents in $V$ both receive non-zero
fractional budget to change their resistance parameters, then it will not
increase the objective function $f$ by biasing the budget towards one of them.

Notation Recap. Recall that given $\alpha\in[0,1]^{N}$, we write
$A:=\operatorname{Diag}(\alpha)$. Moreover, we denote
$X=X(\alpha):=I-(I-A)P^{(\delta)}$. Under conditions such as Fact 2.1, we
write $M=M(\alpha):=X^{-1}$ and the equilibrium vector $z=z(\alpha):=MAs$,
where $s\in[0,1]^{N}$ is the innate vector from Section 3.2 such that
$s_{0}=1$ and $s_{i}=0$ for $i\in V$. Finally, the objective function is
$f(\alpha):=\mathbf{1}^{\top}z(\alpha)$. Note that the quantities have a
dependence on $\delta$, and we will use a superscript such as $f^{(\delta)}$
when we wish to emphasize this dependence.

######  Fact 4.1 (Technical Calculations [CLS19]).

Whenever the above quantities are well-defined, we have

  * •

$M\geq 0$ and $M_{ii}\geq 1$ for all $i\in N$.

  * •

If $\alpha_{k}\neq 1$, $(PM)_{kk}=\frac{M_{kk}-1}{1-\alpha_{k}}$ and
$(PM)_{kj}=\frac{M_{kj}-1}{1-\alpha_{k}}$ for $j\neq k$.

  * •

For $i\in N$, $e_{i}^{\top}\nabla f(\alpha)=\frac{\partial
f}{\partial\alpha_{i}}=\frac{s_{i}-z_{i}(\alpha)}{1-\alpha_{i}}\cdot\mathbf{1}^{\top}Me_{i}$.

Statement (2) inspires us to analyze the following quantities.

######  Lemma 4.2.

Suppose $i,j\in V$ such that $0\leq\alpha_{i},\alpha_{j}<1$ and
$(e_{i}-e_{j})^{\top}\nabla f(\alpha)=0$. Then, we have

$(e_{i}-e_{j})^{\top}\nabla^{2}f(\alpha)(e_{i}-e_{j})=\frac{2}{(1-\alpha_{i})(1-\alpha_{j})}\cdot\left\\{z_{i}(\alpha)y_{ij}(\alpha)+z_{j}(\alpha)y_{ji}(\alpha)\right\\}.$

where
$y_{ij}(\alpha):=\mathbf{1}^{\top}Me_{i}\cdot(M_{jj}-1)-\mathbf{1}^{\top}Me_{j}\cdot
M_{ji}$.

###### Proof.

By the definition of the inverse of a matrix $B$, we have $BB^{-1}=I$. The
partial derivative with respect to a variable $t$ is: $\frac{\partial
B}{\partial t}B^{-1}+B\frac{\partial B^{-1}}{\partial t}=0$. Hence, we have
$\frac{\partial B^{-1}}{\partial t}=-B^{-1}\frac{\partial B}{\partial
t}B^{-1}$. Applying the above result with $B=I-(I-A)P$ and $t=\alpha_{i}$, we
get $\frac{\partial M}{\partial\alpha_{i}}=-Me_{i}e_{i}^{\top}PM$. Combining
with the results in Fact 4.1, we obtain the second-order partial derivatives
of $f$ as follows:

$\displaystyle\frac{\partial^{2}f(\alpha)}{\partial\alpha^{2}_{i}}$
$\displaystyle=\frac{s_{i}-z_{i}(\alpha)}{1-\alpha_{i}}\mathbf{1}^{\top}\frac{\partial
M}{\partial\alpha_{i}}e_{i}+\frac{s_{i}-z_{i}(\alpha)}{(1-\alpha_{i})^{2}}\mathbf{1}^{\top}Me_{i}-\frac{1}{1-\alpha_{i}}\mathbf{1}^{\top}Me_{i}\frac{\partial
z_{i}(\alpha)}{\partial\alpha_{i}}$
$\displaystyle=-\frac{s_{i}-z_{i}(\alpha)}{1-\alpha_{i}}\mathbf{1}^{\top}Me_{i}e^{\top}_{i}PMe_{i}+\frac{s_{i}-z_{i}(\alpha)}{(1-\alpha_{i})^{2}}\mathbf{1}^{\top}Me_{i}-\frac{s_{i}-z_{i}(\alpha)}{(1-\alpha_{i})^{2}}\mathbf{1}^{\top}Me_{i}e^{\top}_{i}Me_{i}$
$\displaystyle=-\frac{s_{i}-z_{i}(\alpha)}{(1-\alpha_{i})^{2}}\mathbf{1}^{\top}Me_{i}\cdot(M_{ii}-1)+\frac{s_{i}-z_{i}(\alpha)}{(1-\alpha_{i})^{2}}\mathbf{1}^{\top}Me_{i}-\frac{s_{i}-z_{i}(\alpha)}{(1-\alpha_{i})^{2}}\mathbf{1}^{\top}Me_{i}\cdot
M_{ii}$
$\displaystyle=-\frac{s_{i}-z_{i}(\alpha)}{(1-\alpha_{i})^{2}}\left[\mathbf{1}^{\top}Me_{i}\cdot(M_{ii}-1)-\mathbf{1}^{\top}Me_{i}+\mathbf{1}^{\top}Me_{i}\cdot
M_{ii}\right]$
$\displaystyle=-2\cdot\frac{s_{i}-z_{i}(\alpha)}{(1-\alpha_{i})^{2}}\mathbf{1}^{\top}Me_{i}\cdot(M_{ii}-1),$
$\displaystyle\frac{\partial^{2}f(\alpha)}{\partial\alpha_{i}\partial\alpha_{j}}$
$\displaystyle=\frac{s_{i}-z_{i}(\alpha)}{1-\alpha_{i}}\mathbf{1}^{\top}\frac{\partial
M}{\partial\alpha_{j}}e_{i}-\frac{1}{1-\alpha_{i}}\mathbf{1}^{\top}Me_{i}\frac{\partial
z_{i}(\alpha)}{\partial\alpha_{j}}$
$\displaystyle=-\frac{s_{i}-z_{i}(\alpha)}{1-\alpha_{i}}\mathbf{1}^{\top}Me_{j}e^{\top}_{j}PMe_{i}-\frac{s_{j}-z_{j}(\alpha)}{(1-\alpha_{i})(1-\alpha_{j})}\mathbf{1}^{\top}Me_{i}e^{\top}_{i}Me_{j}$
$\displaystyle=-\frac{s_{i}-z_{i}(\alpha)}{1-\alpha_{i}}\mathbf{1}^{\top}Me_{j}\cdot\frac{M_{ji}}{1-\alpha_{j}}-\frac{s_{j}-z_{j}(\alpha)}{(1-\alpha_{i})(1-\alpha_{j})}\mathbf{1}^{\top}Me_{i}\cdot
M_{ij}$
$\displaystyle=-\frac{s_{i}-z_{i}(\alpha)}{(1-\alpha_{i})(1-\alpha_{j})}\mathbf{1}^{\top}Me_{j}\cdot
M_{ji}-\frac{s_{j}-z_{j}(\alpha)}{(1-\alpha_{i})(1-\alpha_{j})}\mathbf{1}^{\top}Me_{i}\cdot
M_{ij}.$

Therefore, we have:

$\displaystyle~{}~{}~{}~{}(e_{i}-e_{j})^{\top}\nabla^{2}f(\alpha)(e_{i}-e_{j})$
$\displaystyle=\frac{\partial^{2}f(\alpha)}{\partial\alpha^{2}_{i}}+\frac{\partial^{2}f(\alpha)}{\partial\alpha^{2}_{j}}-\frac{\partial^{2}f(\alpha)}{\partial\alpha_{i}\partial\alpha_{j}}-\frac{\partial^{2}f(\alpha)}{\partial\alpha_{j}\partial\alpha_{i}}$
$\displaystyle=2\cdot\frac{z_{i}(\alpha)}{(1-\alpha_{i})^{2}}\mathbf{1}^{\top}Me_{i}\cdot(M_{ii}-1)+2\cdot\frac{z_{j}(\alpha)}{(1-\alpha_{j})^{2}}\mathbf{1}^{\top}Me_{j}\cdot(M_{jj}-1)-$
$\displaystyle~{}~{}~{}~{}2\cdot\frac{z_{i}(\alpha)}{(1-\alpha_{i})(1-\alpha_{j})}\mathbf{1}^{\top}Me_{j}\cdot
M_{ji}-2\cdot\frac{z_{j}(\alpha)}{(1-\alpha_{i})(1-\alpha_{j})}\mathbf{1}^{\top}Me_{i}\cdot
M_{ij}.$

From the hypothesis of the lemma, we have:

$(e_{i}-e_{j})^{\top}\nabla f(\alpha)=\frac{\partial
f(\alpha)}{\partial\alpha_{i}}-\frac{\partial
f(\alpha)}{\partial\alpha_{j}}=-\frac{z_{i}(\alpha)}{1-\alpha_{i}}\mathbf{1}^{\top}Me_{i}+\frac{z_{j}(\alpha)}{1-\alpha_{j}}\mathbf{1}^{\top}Me_{j}=0,$

which gives

$\frac{z_{i}(\alpha)}{1-\alpha_{i}}\mathbf{1}^{\top}Me_{i}=\frac{z_{j}(\alpha)}{1-\alpha_{j}}\mathbf{1}^{\top}Me_{j}.$

Thus, we have

$\displaystyle~{}~{}~{}~{}(e_{i}-e_{j})^{\top}\nabla^{2}f(\alpha)(e_{i}-e_{j})$
$\displaystyle=2\cdot\frac{z_{j}(\alpha)}{(1-\alpha_{i})(1-\alpha_{j})}\mathbf{1}^{\top}Me_{j}\cdot(M_{ii}-1)+2\cdot\frac{z_{i}(\alpha)}{(1-\alpha_{i})(1-\alpha_{j})}\mathbf{1}^{\top}Me_{i}\cdot(M_{jj}-1)-$
$\displaystyle~{}~{}~{}~{}2\cdot\frac{z_{i}(\alpha)}{(1-\alpha_{i})(1-\alpha_{j})}\mathbf{1}^{\top}Me_{j}\cdot
M_{ji}-2\cdot\frac{z_{j}(\alpha)}{(1-\alpha_{i})(1-\alpha_{j})}\mathbf{1}^{\top}Me_{i}\cdot
M_{ij}$
$\displaystyle=\frac{2}{(1-\alpha_{i})(1-\alpha_{j})}\cdot\left\\{z_{i}(\alpha)\left[\mathbf{1}^{\top}Me_{i}\cdot(M_{jj}-1)-\mathbf{1}^{\top}Me_{j}\cdot
M_{ji}\right]+\right.$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\left.z_{j}(\alpha)\left[\mathbf{1}^{\top}Me_{j}\cdot(M_{ii}-1)-\mathbf{1}^{\top}Me_{i}\cdot
M_{ij}\right]\right\\}$
$\displaystyle=\frac{2}{(1-\alpha_{i})(1-\alpha_{j})}\cdot\left[z_{i}(\alpha)y_{ij}(\alpha)+z_{j}(\alpha)y_{ji}(\alpha)\right].$

as desired. ∎

In view of Lemma 4.2, it suffices to analyze the quantity $y_{ij}$. Since
every $i\in V$ with $\alpha_{i}<1$ is influenced by agent $0$ (with $z_{0}=1$)
in $P^{(\delta)}$, we have $z_{i}(\alpha)>0$ for all $i\in V$. Hence, to show
statement (2), it remains to show that $y_{ij}(\alpha)<0$. We next analyze
$y_{ij}$ as functions of $\alpha_{j}$ and $P$ respectively in the next two
lemmas.

######  Lemma 4.3 (Monotonicity).

Given $\alpha\in[0,1]^{n}$, let $A:=\operatorname{Diag}(\alpha)$ and $P$ be a
row-stochastic matrix such that $M:=[I-(I-A)P]^{-1}$ exists. For $i\neq j\in
V$, we fix $\alpha_{k}$ for $k\neq j$ and all entries of $P$ and consider the
following quantity as a function of $\alpha_{j}$:

$y_{ij}(\alpha_{j}):=\mathbf{1}^{\top}Me_{i}\cdot(M_{jj}-1)-\mathbf{1}^{\top}Me_{j}\cdot
M_{ji.}$

Then, $y_{ij}(\alpha_{j})$ is a strictly monotone or constant function of
$\alpha_{j}$ on $[0,1]$, i.e., it is either strictly increasing, strictly
decreasing, or constant. In addition, $y_{ij}(1)=0$.

###### Proof.

When $\alpha_{j}=1$, note that the $j$-th row of the matrix $I-(I-A)P$ is
equal to $e_{j}^{\top}$. By considering the $j$-th row of the equation
$[I-(I-A)P]M=I$, we have $M_{jj}=1$ and $M_{jk}=0$ for any $k\neq j$. Hence,
$M_{jj}-1=M_{ji}=0$ and so $y_{ij}(1)=0$.

We will now show that $y_{ij}(\alpha_{j})$ is a strictly monotone function of
$\alpha_{j}$. Notice that $y_{ij}$ is a continuous function of $\alpha_{j}$
since $y_{ij}$ is a continuous function of $M$, $M$ is a continuous function
of $\alpha_{j}$ (because of the continuity of matrix inversion), and a
composition of continuous functions is continuous. In addition, we know that
$\frac{\partial B^{-1}}{\partial t}=-B^{-1}\frac{\partial B}{\partial
t}B^{-1}$ for any invertible matrix $B$. Applying the above result with
$B=I-(I-A)P$ and $t=\alpha_{i}$, we get

$\frac{\partial M}{\partial\alpha_{i}}=-Me_{i}e_{i}^{\top}PM.$

Hence, when $\alpha_{j}\neq 1$, the partial derivative of $y_{ij}$ with
respect to $\alpha_{j}$ is

$\displaystyle\frac{\partial y_{ij}}{\partial\alpha_{j}}$
$\displaystyle=\frac{\partial}{\partial\alpha_{j}}\left[1^{\top}Me_{i}\cdot(e_{j}^{\top}Me_{j}-1)-1^{\top}Me_{j}\cdot
e_{j}^{\top}Me_{i}\right]$ $\displaystyle=1^{\top}\frac{\partial
M}{\partial\alpha_{j}}e_{i}\cdot(e_{j}^{\top}Me_{j}-1)+1^{\top}Me_{i}\cdot
e_{j}^{\top}\frac{\partial M}{\partial\alpha_{j}}e_{j}-1^{\top}\frac{\partial
M}{\partial\alpha_{j}}e_{j}\cdot e_{j}^{\top}Me_{i}-1^{\top}Me_{j}\cdot
e_{j}^{\top}\frac{\partial M}{\partial\alpha_{j}}e_{i}$
$\displaystyle=-1^{\top}Me_{j}e_{j}^{\top}PMe_{i}\cdot(e_{j}^{\top}Me_{j}-1)-1^{\top}Me_{i}\cdot
e_{j}^{\top}Me_{j}e_{j}^{\top}PMe_{j}+$
$\displaystyle~{}~{}~{}~{}~{}1^{\top}Me_{j}e_{j}^{\top}PMe_{j}\cdot
e_{j}^{\top}Me_{i}+1^{\top}Me_{j}\cdot e_{j}^{\top}Me_{j}e_{j}^{\top}PMe_{i}$
$\displaystyle=-1^{\top}Me_{j}\cdot\frac{M_{ji}}{1-\alpha_{j}}\cdot(M_{jj}-1)-1^{\top}Me_{i}\cdot
M_{jj}\cdot\frac{M_{jj}-1}{1-\alpha_{j}}+$
$\displaystyle~{}~{}~{}~{}~{}1^{\top}Me_{j}\cdot\frac{M_{jj}-1}{1-\alpha_{j}}\cdot
M_{ji}+1^{\top}Me_{j}\cdot M_{jj}\cdot\frac{M_{ji}}{1-\alpha_{j}}$ (Fact 4.1)
$\displaystyle=1^{\top}Me_{j}\cdot
M_{jj}\cdot\frac{M_{ji}}{1-\alpha_{j}}-1^{\top}Me_{i}\cdot
M_{jj}\cdot\frac{M_{jj}-1}{1-\alpha_{j}}$
$\displaystyle=-\frac{M_{jj}}{1-\alpha_{j}}[1^{\top}Me_{i}\cdot(M_{jj}-1)-1^{\top}Me_{j}\cdot
M_{ji}]$ $\displaystyle=-\frac{M_{jj}}{1-\alpha_{j}}y_{ij},$

where $M_{jj}\geq 1>0$ by Fact 4.1.

Rewriting $g(t)=-y_{ij}(1-t)$, we have an alternative form
$\frac{dg}{dt}=\frac{M(t)\cdot g}{t}$, where $M(t)\geq 1$ and
$g(0)=y_{ij}(1)=0$. It follows that if $g$ is a continuous function, then
either $g$ stays 0 in [0,1] or $g$ is strictly monotone. ∎

Recall that our goal is to choose some $\delta>0$ to define the interaction
matrix $P^{(\delta)}:=(1-\delta)C+\delta R$ such that we can prove that the
quantity $y_{ij}^{(\delta)}<0$. The next lemma shows that for the special case
$\delta=0$, we can argue that $y_{ij}^{(0)}<0$ for $\alpha_{j}<1$.

######  Lemma 4.4.

For $\delta=0$, consider $P=P^{(0)}=C$, whose diagonal entries are 0 and every
other entry is $\frac{1}{n}$. For $\alpha\in[0,1]^{N}$ (with $\alpha_{0}=1$),
we have $A:=\operatorname{Diag}(\alpha)$ and $M=[I-(I-A)C]^{-1}$. Fix some
$i\neq j\in V$, and consider

$y_{ij}(\alpha_{j}):=\mathbf{1}^{\top}Me_{i}\cdot(M_{jj}-1)-\mathbf{1}^{\top}Me_{j}\cdot
M_{ji}.$

as a function of $\alpha_{j}$; when $\alpha_{j}=0$,
$y_{ij}(0)\leq-\frac{1}{n+1}$. Moreover, $\mathbf{1}^{\top}M\mathbf{1}\leq n$.

###### Proof.

We write $C:=\frac{1}{n}(J-I)$, where every entry in $J$ is 1. By the Sherman-
Morrison formula,

$\displaystyle C^{-1}$
$\displaystyle=\left[\frac{1}{n}(J-I)\right]^{-1}=n\left[-I+\mathbf{1}\mathbf{1}^{\top}\right]^{-1}=n\left[-I-\frac{(-I)\mathbf{1}\mathbf{1}^{\top}(-I)}{1+\mathbf{1}^{\top}(-I)\mathbf{1}}\right]$
$\displaystyle=n\left[-I-\frac{J}{1-(n+1)}\right]=J-nI,$

so we have

$M=\left[I-(I-A)C\right]^{-1}=\left[C^{-1}C-(I-A)C\right]^{-1}=C^{-1}\left(C^{-1}-I+A\right)^{-1}=(J-nI)[J+A-(n+1)I]^{-1}.$

Denote $D:=A-(n+1)I$. Then $D$ is a diagonal matrix with
$D_{ii}=\alpha_{i}-n-1<0$ for each $i$ and

$M=(J-nI)(J+D)^{-1}.$

By the Sherman-Morrison formula again, we have

$(J+D)^{-1}=(D+\mathbf{1}\mathbf{1}^{\top})^{-1}=D^{-1}-\frac{D^{-1}\mathbf{1}\mathbf{1}^{\top}D^{-1}}{1+\mathbf{1}^{\top}D^{-1}\mathbf{1}}=D^{-1}-\frac{D^{-1}JD^{-1}}{1+\displaystyle\sum_{k\in
N}\frac{1}{\alpha_{k}-n-1}}.$

Since $D^{-1}$ exists, $M^{-1}$ also exists.

Denote $w:=\displaystyle\sum_{k\in N}\frac{1}{\alpha_{k}-n-1}<0$. Then
$(J+D)^{-1}=D^{-1}-\displaystyle\frac{D^{-1}JD^{-1}}{1+w}$. We then have

$M=(J-nI)\left[D^{-1}-\frac{D^{-1}JD^{-1}}{1+w}\right]=JD^{-1}-nD^{-1}-\frac{JD^{-1}JD^{-1}}{1+w}+\frac{nD^{-1}JD^{-1}}{1+w}.$

Since
$JD^{-1}J=\mathbf{1}\mathbf{1}^{\top}D^{-1}\mathbf{1}\mathbf{1}^{\top}=\mathbf{1}\displaystyle\left(\sum_{k\in
N}\frac{1}{\alpha_{k}-n-1}\right)\mathbf{1}^{\top}=wJ$,

$\displaystyle M$
$\displaystyle=JD^{-1}-nD^{-1}-\frac{w}{1+w}JD^{-1}+\frac{n}{1+w}D^{-1}JD^{-1}$
$\displaystyle=\frac{1}{1+w}JD^{-1}-nD^{-1}+\frac{n}{1+w}D^{-1}JD^{-1}$ (3)

and hence

$\displaystyle\mathbf{1}^{\top}M\mathbf{1}$
$\displaystyle=\frac{1}{1+w}\mathbf{1}^{\top}JD^{-1}\mathbf{1}-n\mathbf{1}^{\top}D^{-1}\mathbf{1}+\frac{n}{1+w}\mathbf{1}^{\top}D^{-1}JD^{-1}\mathbf{1}$
$\displaystyle=\frac{1}{1+w}\mathbf{1}^{\top}\mathbf{1}\mathbf{1}^{\top}D^{-1}\mathbf{1}-n\mathbf{1}^{\top}D^{-1}\mathbf{1}+\frac{n}{1+w}(\mathbf{1}^{\top}D^{-1}\mathbf{1})^{2}$
$\displaystyle=\frac{(n+1)w}{1+w}-nw+\frac{nw^{2}}{1+w}=\frac{w}{1+w}.$

Note that

$1+w=1+\displaystyle\sum_{k\in
N}\frac{1}{\alpha_{k}-n-1}=\displaystyle\sum_{k\in
N}\left(\frac{1}{n+1}+\frac{1}{\alpha_{k}-n-1}\right),$

and

$\frac{1}{n+1}+\frac{1}{\alpha_{k}-n-1}=\frac{\alpha_{k}-n-1+n+1}{(n+1)(\alpha_{k}-n-1)}=\frac{\alpha_{k}}{(n+1)(\alpha_{k}-n-1)}\leq
0$

for any $k\in N$ with strict inequality holds for $k=0$ since $\alpha_{0}=1$.

Therefore, $1+w<0$ and thus

$\mathbf{1}^{\top}M\mathbf{1}=\frac{w}{1+w}=\frac{\sum_{k\in
N}\frac{1}{\alpha_{k}-n-1}}{1+\sum_{k\in
N}\frac{1}{\alpha_{k}-n-1}}\leq\frac{\frac{n+1}{-(n+1)}}{1+\frac{n+1}{-n}}=\frac{1}{-1+\frac{n+1}{n}}=n.$

Also, from Equation 3, we have, for any $k\in V$,

$\displaystyle Me_{k}$
$\displaystyle=\frac{1}{1+w}JD^{-1}e_{k}-nD^{-1}e_{k}+\frac{n}{1+w}D^{-1}JD^{-1}e_{k}$
$\displaystyle=\frac{1}{\alpha_{k}-n-1}\left(\frac{1}{1+w}\mathbf{1}-ne_{k}+\frac{n}{1+w}D^{-1}\mathbf{1}\right).$

Then for any distinct $i,j\in V$,

$\displaystyle y_{ij}$
$\displaystyle=\mathbf{1}^{\top}Me_{i}\cdot(M_{jj}-1)-\mathbf{1}^{\top}Me_{j}\cdot
M_{ji}$
$\displaystyle=\mathbf{1}^{\top}Me_{i}\cdot(e_{j}^{\top}Me_{j}-1)-\mathbf{1}^{\top}Me_{j}\cdot
e_{j}^{\top}Me_{i}$
$\displaystyle=\frac{1}{\alpha_{i}-n-1}\left(\frac{n+1}{1+w}-n+\frac{nw}{1+w}\right)\cdot\left[\frac{1}{\alpha_{j}-n-1}\left(\frac{1}{1+w}-n+\frac{n}{1+w}\cdot\frac{1}{\alpha_{j}-n-1}\right)-1\right]-$
$\displaystyle~{}~{}~{}~{}\frac{1}{\alpha_{j}-n-1}\left(\frac{n+1}{1+w}-n+\frac{nw}{1+w}\right)\cdot\left[\frac{1}{\alpha_{i}-n-1}\left(\frac{1}{1+w}+\frac{n}{1+w}\cdot\frac{1}{\alpha_{j}-n-1}\right)\right]$
$\displaystyle=\frac{-n-(\alpha_{j}-n-1)}{(\alpha_{i}-n-1)(\alpha_{j}-n-1)}\left(\frac{n+1}{1+w}-n+\frac{nw}{1+w}\right)$
$\displaystyle=\frac{1-\alpha_{j}}{(\alpha_{i}-n-1)(\alpha_{j}-n-1)(1+w)}.$
(4)

Since the denominator is negative, $y_{ij}\leq 0$ with equality holds if and
only if $\alpha_{j}=1$.

Finally, when $\alpha_{j}=0$, equation 4 gives

$\displaystyle y_{ij}$
$\displaystyle=\frac{1-\alpha_{j}}{(\alpha_{i}-n-1)(\alpha_{j}-n-1)(1+w)}$
$\displaystyle=\frac{1}{(\alpha_{i}-n-1)(-n-1)(1+\sum_{k\neq
j}\frac{1}{\alpha_{k}-n-1}+\frac{1}{-n-1})}$
$\displaystyle\leq\frac{1}{(-n-1)(-n-1)(1+\frac{n}{1-n-1}+\frac{1}{-n-1})}$
$\displaystyle=\frac{1}{(n+1)^{2}(-\frac{1}{n+1})}$
$\displaystyle=-\frac{1}{n+1}$

as desired. ∎

Lemma 4.4 says that $y_{ij}^{(0)}(\alpha_{j}=0)\leq-\frac{1}{n+1}$. The hope
is that if $\delta>0$ is small enough, then $P^{(\delta)}$ would still be
close to $P^{(0)}=C$, and so $y_{ij}^{(\delta)}(\alpha_{j}=0)$ will stay
negative. Hence, we next analyze the quantity $y_{ij}$ as a function of the
interaction matrix $P$.

######  Lemma 4.5.

Fixing some $\alpha\in[0,1]^{N}$, let $A:=\operatorname{Diag}(\alpha)$ and let
$P$ be a row-stochastic matrix such that $M=M(P):=[I-(I-A)P]^{-1}$ exists. For
any distinct $i,j\in V$, denote

$y_{ij}(P):=\mathbf{1}^{\top}Me_{i}\cdot(M_{jj}-1)-\mathbf{1}^{\top}Me_{j}\cdot
M_{ji}$

as a function of $P$. Then, $\displaystyle\sum_{k,l\in N}\left|\frac{\partial
y_{ij}}{\partial P_{kl}}\right|\leq 4(\mathbf{1}^{\top}M\mathbf{1})^{3}$.

###### Proof.

By the definition of the inverse of a matrix $B$, we have $BB^{-1}=I$. The
partial derivative with respect to a variable $t$ is: $\frac{\partial
B}{\partial t}B^{-1}+B\frac{\partial B^{-1}}{\partial t}=0$. Hence, we have
$\frac{\partial B^{-1}}{\partial t}=-B^{-1}\frac{\partial B}{\partial
t}B^{-1}$. Applying the above result with $B=I-(I-A)P$ and $t=P_{kl}$ and
denoting $M=[I-(I-A)P]^{-1}$, we get

$\frac{\partial M}{\partial
P_{kl}}=-M[-(I-A)e_{k}e_{l}^{\top}]M=M(I-A)e_{k}e_{l}^{\top}M=(1-\alpha_{k})Me_{k}e_{l}^{\top}M.$

Hence, for any $k,l\in N$,

$\displaystyle\left|\frac{\partial y_{ij}}{\partial P_{kl}}\right|$
$\displaystyle=\left|\mathbf{1}^{\top}(1-\alpha_{k})Me_{k}e_{l}^{\top}Me_{i}(M_{jj}-1)+\mathbf{1}^{\top}Me_{i}e_{j}^{\top}(1-\alpha_{k})Me_{k}e_{l}^{\top}Me_{j}-\right.$
$\displaystyle~{}~{}~{}~{}\left.\mathbf{1}^{\top}(1-\alpha_{k})Me_{k}e_{l}^{\top}Me_{j}M_{ji}-\mathbf{1}^{\top}Me_{j}e_{j}^{\top}(1-\alpha_{k})Me_{k}e_{l}^{\top}Me_{i}\right|$
$\displaystyle=(1-\alpha_{k})\left|\mathbf{1}^{\top}Me_{k}M_{li}(M_{jj}-1)+\mathbf{1}^{\top}Me_{i}M_{jk}M_{lj}-\mathbf{1}^{\top}Me_{k}M_{lj}M_{ji}-\mathbf{1}^{\top}Me_{j}M_{jk}M_{li}\right|$
$\displaystyle\leq\left|\mathbf{1}^{\top}Me_{k}M_{li}(M_{jj}-1)\right|+\left|\mathbf{1}^{\top}Me_{i}M_{jk}M_{lj}\right|+\left|\mathbf{1}^{\top}Me_{k}M_{lj}M_{ji}\right|+\left|\mathbf{1}^{\top}Me_{j}M_{jk}M_{li}\right|$
$\displaystyle=\mathbf{1}^{\top}Me_{k}M_{li}(M_{jj}-1)+\mathbf{1}^{\top}Me_{i}M_{jk}M_{lj}+\mathbf{1}^{\top}Me_{k}M_{lj}M_{ji}+\mathbf{1}^{\top}Me_{j}M_{jk}M_{li},$

where the last inequality holds because $M$ is nonnegative by Fact 4.1.

Thus, we obtain

$\displaystyle~{}~{}~{}\sum_{k,l\in N}\left|\frac{\partial y_{ij}}{\partial
P_{kl}}\right|$ $\displaystyle\leq\sum_{k\in N}\sum_{l\in
N}(\mathbf{1}^{\top}Me_{k}M_{li}(M_{jj}-1)+\mathbf{1}^{\top}Me_{i}M_{jk}M_{lj}+\mathbf{1}^{\top}Me_{k}M_{lj}M_{ji}+\mathbf{1}^{\top}Me_{j}M_{jk}M_{li})$
$\displaystyle=\sum_{k\in
N}(\mathbf{1}^{\top}Me_{k}\mathbf{1}^{\top}Me_{i}(M_{jj}-1)+\mathbf{1}^{\top}Me_{i}M_{jk}\mathbf{1}^{\top}Me_{j}+\mathbf{1}^{\top}Me_{k}\mathbf{1}^{\top}Me_{j}M_{ji}+\mathbf{1}^{\top}Me_{j}M_{jk}\mathbf{1}^{\top}Me_{i})$
$\displaystyle=\mathbf{1}^{\top}M\mathbf{1}\mathbf{1}^{\top}Me_{i}(M_{jj}-1)+\mathbf{1}^{\top}Me_{i}e_{j}^{\top}M\mathbf{1}\mathbf{1}^{\top}Me_{j}+\mathbf{1}^{\top}M\mathbf{1}\mathbf{1}^{\top}Me_{j}M_{ji}+\mathbf{1}^{\top}Me_{j}e_{j}^{\top}M\mathbf{1}\mathbf{1}^{\top}Me_{i}$
$\displaystyle\leq 4(\mathbf{1}^{\top}M\mathbf{1})^{3}$

where the last inequality is obtained by applying Fact 4.1 again. ∎

In view of Lemma 4.5, we wish to bound the entries of $M^{(\delta)}$ for small
$\delta>0$. The next fact was given in Alfa et al. [AXY02] that gives two-
sided bounds to the inverse of a perturbed nonsingular diagonally dominant. We
use the operator $|\cdot|$ on a matrix to denote the matrix with the same
dimension by taking absolute values entrywise.

######  Fact 4.6 (Entrywise Bounds for Diagonally Dominant Matrix Inverse
[AXY02]).

Suppose $X$ and $\widetilde{X}$ are matrices of the form $I-B$, where $B\geq
0$ and has spectral norm strictly less than 1, and each row of $B$ sums to at
most 1.

Let $0\leq\varepsilon<1$ such that
$|X_{ij}-\tilde{X}_{ij}|\leq\varepsilon|X_{ij}|$ for $i\neq j$ and
$|X\mathbf{1}-\tilde{X}\mathbf{1}|\leq\varepsilon|X\mathbf{1}|$. Then,

$\frac{(1-\varepsilon)^{n}}{(1+\varepsilon)^{n-1}}X^{-1}\leq\tilde{X}^{-1}\leq\frac{(1+\varepsilon)^{n}}{(1-\varepsilon)^{n-1}}X^{-1}.$

Recall that $R$ is row-stochastic matrix that represents a normalized
adjacency matrix of a $d$-regular graph $G=(V,E)$ with the insertion of an
isolated vertex $0$; also, recall that $C=\frac{1}{n}(J-I)$ represents a
clique on $N$.

######  Lemma 4.7.

Let $\alpha\in[0,1]^{N}$ such that $\alpha_{0}=1$, and
$A:=\operatorname{Diag}(\alpha)$. For $0\leq\delta<\frac{d}{n}$, define
$P^{(\delta)}:=(1-\delta)C+\delta R$ and
$M^{(\delta)}:=(I-(I-A)P^{(\delta)})^{-1}$. Then,

$\mathbf{1}^{\top}M^{(\delta)}\mathbf{1}\leq\displaystyle\frac{n(1+\varepsilon)^{n}}{(1-\varepsilon)^{n-1}}~{}~{}~{}\text{where}~{}\varepsilon=\frac{\delta
n}{d}.$

###### Proof.

For $0\leq\delta<\frac{d}{n}$, $X^{(\delta)}:=I-(I-A)P^{(\delta)}$ has the
required form as stated in Fact 4.6, because $\alpha_{0}=1$ and $P^{(\delta)}$
is irreducible.

We next check that the hypothesis of Fact 4.6 holds for $X^{(0)}$ and
$X^{(\delta)}$.

For any distinct $i,j\in V$, since $R_{ij}=0$ or
$R_{ij}=\displaystyle\frac{1}{d}$, we have

$\displaystyle|X_{i0}^{(0)}-X_{i0}^{(\delta)}|$
$\displaystyle=\left|-\frac{1-\alpha_{i}}{n}+\frac{(1-\alpha_{i})(1-\delta)}{n}\right|=\frac{\delta(1-\alpha_{i})}{n}=\delta|X_{i0}^{(0)}|<\varepsilon|X_{i0}^{(0)}|,$
$\displaystyle|X_{0j}^{(0)}-X_{0j}^{(\delta)}|$
$\displaystyle=|0-0|=0\leq\varepsilon|X_{0j}^{(0)}|,$
$\displaystyle|X_{ij}^{(0)}-X_{ij}^{(\delta)}|$
$\displaystyle=\left|-\frac{1-\alpha_{i}}{n}+(1-\alpha_{i})\displaystyle\left[\frac{1-\delta}{n}+\delta
R_{ij}\right]\right|$
$\displaystyle=\left|\delta(1-\alpha_{i})\left(R_{ij}-\frac{1}{n}\right)\right|\leq\frac{\delta(1-\alpha_{i})}{d}=\frac{\delta
n}{d}\cdot\frac{1-\alpha_{i}}{n}=\varepsilon|X_{ij}^{(0)}|.$

In addition, as $P^{(\delta)}$ is row-stochastic, we have
$P^{(\delta)}\mathbf{1}=\mathbf{1}$ and hence

$|X^{(0)}\mathbf{1}-X^{(\delta)}\mathbf{1}|=|[X^{(0)}-X^{(\delta)}]\mathbf{1}|=|\delta(I-A)(P^{(0)}-P^{(\delta)})\mathbf{1}|=\mathbf{0}\leq\varepsilon|X^{(0)}\mathbf{1}|.$

Therefore, we have
$M^{(\delta)}\leq\displaystyle\frac{(1+\varepsilon)^{n}}{(1-\varepsilon)^{n-1}}M^{(0)}$
by Fact 4.6. Then, as $\mathbf{1}^{\top}M^{(0)}\mathbf{1}\leq n$ by Lemma 4.4,
we have

$\mathbf{1}^{\top}M^{(\delta)}\mathbf{1}\leq\displaystyle\frac{(1+\varepsilon)^{n}}{(1-\varepsilon)^{n-1}}\mathbf{1}^{\top}M^{(0)}\mathbf{1}\leq\frac{n(1+\varepsilon)^{n}}{(1-\varepsilon)^{n-1}},$

as desired. ∎

With the previous preparation, the next lemma proposes an exact universal
perturbation parameter $\delta$ that guarantees the negativity of $y_{ij}$
when $\alpha_{j}\in[0,1)$, for any distinct $i,j\in V$.

######  Lemma 4.8.

Let $\alpha\in[0,1]^{N}$ and $M^{(t)}:=[I-(I-A)P^{(t)}]^{-1}$ for $0\leq
t<\displaystyle\frac{d}{n}$ be as defined in Lemma 4.7. For any distinct
$i,j\in V$, define:

$y_{ij}^{(t)}:=\mathbf{1}^{\top}M^{(t)}e_{i}\cdot(M_{jj}^{(t)}-1)-\mathbf{1}^{\top}M^{(t)}e_{j}\cdot
M_{ji}^{(t)}.$

Let $\displaystyle\delta=\frac{d^{3}(2d-1)^{3n-3}}{(n+1)^{6}(2d+1)^{3n}}$. If
$\alpha_{j}\in[0,1)$, then $y_{ij}^{(\delta)}<0$.

###### Proof.

Recall that $P^{(t)}:=(1-t)\cdot C+tR$ as defined in Lemma 4.7. We have:

$P_{ij}^{(t)}=\begin{cases}t&\text{if}~{}i=j=0\\\
\frac{1-t}{n}&\text{if}~{}i\neq j~{}\text{and
either}~{}i=0~{}\text{or}~{}j=0\\\ 0&\text{if}~{}i=j\neq 0\\\
\frac{1-t}{n}+\frac{t}{d}~{}\text{or}~{}\frac{1-t}{n}&\text{if}~{}i\neq
j~{}\text{and both}~{}i,j\neq 0\end{cases}.$

Hence, differentiating with respect to $t$, we have:

$\frac{d}{dt}P_{ij}^{(t)}=\begin{cases}1&\text{if}~{}i=j=0\\\
-\frac{1}{n}&\text{if}~{}i\neq j~{}\text{and
either}~{}i=0~{}\text{or}~{}j=0\\\ 0&\text{if}~{}i=j\neq 0\\\
-\frac{1}{n}+\frac{1}{d}~{}\text{or}~{}-\frac{1}{n}&\text{if}~{}i\neq
j~{}\text{and both}~{}i,j\neq 0\end{cases}.$

Next, we treat $P$ as an $(n+1)^{2}$-dimensional vector, we have
$\left\|\frac{d}{dt}P^{(t)}\right\|_{1}=\sum_{i\in N}\sum_{j\in
N}|\frac{d}{dt}P_{ij}^{(t)}|\leq(n+1)^{2}$. Moreover, we consider $P^{(t)}$ as
a function on $t$, and recalling that $M(P):=[I-(I-A)P]^{-1}$, we can treat
the following as a function on $P$:

$y_{ij}(P):=\mathbf{1}^{\top}M(P)e_{i}\cdot(M_{jj}(P)-1)-\mathbf{1}^{\top}M(P)e_{j}\cdot
M_{ji}(P).$

Hence, we can also treat $\nabla_{P}\,y_{ij}(P)$ as an $(n+1)^{2}$-dimensional
vector, and use $\langle\cdot,\cdot\rangle$ to denote the corresponding inner
product operation. We have the following.

$\displaystyle|y_{ij}^{(\delta)}-y_{ij}^{(0)}|$
$\displaystyle=\left|\int_{0}^{\delta}\langle\nabla_{P}\,y_{ij}(P^{(t)}),\frac{d}{dt}P^{(t)}\rangle~{}dt\right|$
(Fundamental theorem for line integrals)
$\displaystyle\leq\int_{0}^{\delta}\left|\langle\nabla_{P}\,y_{ij}(P^{(t)}),\frac{d}{dt}P^{(t)}\rangle\right|~{}dt$
$\displaystyle\leq\int_{0}^{\delta}\left\|\nabla_{P}\,y_{ij}(P^{(t)})\right\|_{2}\cdot\left\|P^{\prime}(t)\right\|_{2}~{}dt$
(Cauchy-Schwarz Inequality)
$\displaystyle\leq\int_{0}^{\delta}\left\|\nabla_{P}\,y_{ij}(P^{(t)})\right\|_{1}\cdot\left\|P^{\prime}(t)\right\|_{1}~{}dt$
$\displaystyle\leq\int_{0}^{\delta}\left[\sum_{k\in N}\sum_{l\in
N}\left|\frac{\partial y_{ij}(P^{(t)})}{\partial
P_{kl}}\right|\right]\cdot(n+1)^{2}~{}dt$
$\displaystyle\leq\int_{0}^{\delta}4(\mathbf{1}^{\top}M^{(t)}\mathbf{1})^{3}\cdot(n+1)^{2}~{}dt$
(Lemma 4.5)
$\displaystyle\leq\int_{0}^{\delta}4\left[\frac{n(1+\varepsilon)^{n}}{(1-\varepsilon)^{n-1}}\right]^{3}\cdot(n+1)^{2}~{}dt$
(Lemma 4.7)
$\displaystyle\leq\frac{4\delta(n+1)^{5}(1+\varepsilon)^{3n}}{(1-\varepsilon)^{3n-3}}$

where $\displaystyle\varepsilon=\frac{\delta n}{d}$. Since
$\displaystyle\delta=\frac{d^{3}(2d-1)^{3n-3}}{(n+1)^{6}(2d+1)^{3n}}<\frac{1}{2n}$,
$\varepsilon=\displaystyle\frac{\delta n}{d}<\frac{1}{2d}$. Hence, we have

$|y_{ij}(\delta)-y_{ij}(0)|<\frac{4\delta(n+1)^{5}(1+\frac{1}{2d})^{3n}}{(1-\frac{1}{2d})^{3n-3}}=\frac{\delta(n+1)^{5}(2d+1)^{3n}}{2d^{3}(2d-1)^{3n-3}}.$

Also, since
$\displaystyle\delta=\frac{d^{3}(2d-1)^{3n-3}}{(n+1)^{6}(2d+1)^{3n}}$, we have

$|y_{ij}^{(\delta)}-y_{ij}^{(0)}|<\frac{(n+1)^{5}(2d+1)^{3n}}{2d^{3}(2d-1)^{3n-3}}\cdot\frac{d^{3}(2d-1)^{3n-3}}{(n+1)^{6}(2d+1)^{3n}}=\frac{1}{2(n+1)},$

for any $\alpha\in[0,1]^{N}$ with $\alpha_{0}=1$ and $\alpha_{k}\in[0,1]$ for
any other $k\in V$. In particular, this is true when $\alpha_{j}=0$. From
Lemma 4.4, $y_{ij}^{(0)}|_{\alpha_{j}=0}\leq\displaystyle-\frac{1}{n+1}$.
Hence, $y_{ij}^{(\delta)}|_{\alpha_{j}=0}<\displaystyle-\frac{1}{2(n+1)}<0$.
Then by Lemma 4.3, $y_{ij}^{(\delta)}<0$ for any $\alpha_{j}\in[0,1)$. ∎

Finally, we are ready to prove the main result of this section.

Proof of Lemma 3.5:

As mentioned before, the formal goal is to show statement (2). Lemma 4.2 says
that it suffices to show that $y_{ij}(\alpha)<0$ when $\alpha_{j}<1$. Finally,
Lemma 4.8 says that by choosing
$\delta=\frac{d^{3}(2d-1)^{3n-3}}{(n+1)^{6}(2d+1)^{3n}}$ to define
$P^{(\delta)}=(1-\delta)C+\delta R$, we have $y^{(\delta)}_{ij}(\alpha)<0$ for
$\alpha_{j}<1$, as required. ∎

## References

  * [AKPT18] Rediet Abebe, Jon M. Kleinberg, David C. Parkes, and Charalampos E. Tsourakakis.  Opinion dynamics with varying susceptibility to persuasion.  In KDD, pages 1089–1098. ACM, 2018.
  * [AXY02] Attahiru Alfa, Jungong Xue, and Qiang Ye.  Entrywise perturbation theory for diagonally dominant M-matrices with applications.  Numerische Mathematik, 90:401–414, 2002.
  * [CLS19] T.-H. Hubert Chan, Zhibin Liang, and Mauro Sozio.  Revisiting opinion dynamics with varying susceptibility to persuasion via non-convex local search.  In WWW, pages 173–183. ACM, 2019.
  * [DeG74] Morris H. DeGroot.  Reaching a consensus.  Journal of the American Statistical Association, 69(345):118–121, 1974.
  * [Fei03] Uriel Feige.  Vertex cover is hardest to approximate on regular graphs.  Manuscript, 2003.
  * [FJ99] Noah E. Friedkin and Eugene C. Johnsen.  Social influence networks and opinion change.  Advances in Group Processes, 16:1–19, 01 1999.