# AbCD: A Component-wise Adjustable Framework for Dynamic Optimization
Problems

Alexandre Mascarenhas  University of TsukubaTsukubaIbarakiJapan ,  Yuri
Lavinas  0000-0003-2712-5340 University of TsukubaTsukubaIbarakiJapan and
Claus Aranha  University of TsukubaTsukubaIbarakiJapan

(2023)

###### Abstract.

Dynamic Optimization Problems (DOPs) are characterized by changes in the
fitness landscape that can occur at any time and are common in real world
applications. The main issues to be considered include detecting the change in
the fitness landscape and reacting in accord. Over the years, several
evolutionary algorithms have been proposed to take into account this
characteristic during the optimization process. However, the number of
available tools or open source codebases for these approaches is limited,
making reproducibility and extensive experimentation difficult. To solve this,
we developed a component-oriented framework for DOPs called Adjustable
Components for Dynamic Problems (AbCD), inspired by similar works in the
Multiobjective static domain. Using this framework, we investigate components
that were proposed in several popular DOP algorithms. Our experiments show
that the performance of these components depends on the problem and the
selected components used in a configuration, which differs from the results
reported in the literature. Using irace, we demonstrate how this framework can
automatically generate DOP algorithm configurations that take into account the
characteristics of the problem to be solved. Our results highlight existing
problems in the DOP field that need to be addressed in the future development
of algorithms and components.

Evolutionary computation, Evolutionary Dynamic Optimization, Dynamic
Optimization Problems, Component Design

††journalyear: 2023††copyright: rightsretained††conference: Genetic and
Evolutionary Computation Conference Companion; July 15–19, 2023; Lisbon,
Portugal††booktitle: Genetic and Evolutionary Computation Conference Companion
(GECCO ’23 Companion), July 15–19, 2023, Lisbon, Portugal††doi:
10.1145/3583133.3590655††isbn: 979-8-4007-0120-7/23/07††ccs: Computing
methodologies Bio-inspired approaches

##  1\. Introduction

Dynamic Optimization Problems (DOPs) are problems where the fitness landscape
changes over time. Because of this, a solution can have multiple fitness
values as the search progresses. DOPs include vehicle routing, which changes
depending on traffic conditions, and team scheduling, which changes as task
requests arrive. Many real-world problems have dynamic characteristics
(Nguyen, 2011), making the study of DOPs crucial.

Different from static problems, Evolutionary Algorithms (EAs) applied to DOPs
have to adapt to changes in the fitness functions in the middle of the
optimization process. So the EA needs to detect the change to the fitness
function and find the new optimum quickly.

Several EAs and variations have been proposed in the DOP literature in recent
years (Woldesenbet and Yen, 2009; Yang and Li, 2010; Blackwell and Branke,
2006; Yazdani et al., 2013, 2021a). However, there is a lack of analysis of
individual algorithm components and their interactions. One of the main
reasons for this is the lack of source codes (Yazdani et al., 2021b). This
causes problems with reproducibility and diminishes our progress and ability
to build upon previous knowledge.

In this work, we propose a component-wise framework for DOPs, which we call
the _AbCD_ : an Adjustable Component framework for Dynamic Problems. Our goals
with this framework are three-fold: 1) to make available an open-source tool
that facilitates the reproducible analysis of several DOP algorithms and
experiments; 2) to examine individual components from the literature, with
their individual impact and interaction with other components and problem
classes; and 3) to design new DOP algorithm configuration, both manually and
by automatically searching from the available components and their parameters.

We validate the proposed framework by applying it to the Moving Peaks DOP
Benchmark (MPB) (Branke, 1999). We design two algorithm configurations, one
manually by the analysis of individual components, and another automatically
by using Iterated Racing (López-Ibáñez et al., 2016). We compare both
configurations, as well as some algorithms from the literature, using standard
DOP metrics. The individual analysis of the components also shows interesting
insights about existing DOP EAs, and points to promising directions of how to
improve the state of the art.

##  2\. Related Works

Many algorithms have been proposed for DOPs, most of them based on Particle
Swarm Optimization (PSO), such as FTmPSO (Yazdani et al., 2013), RPSO (Hu and
Eberhart, 2002), CPSO (Yang and Li, 2010), and mQSO (Blackwell and Branke,
2006). Their approach is to add dynamic components to PSO that improve its
performance in dynamic environments. In particular, mQSO was one of the first
to use dynamic components to deal with fitness landscape changes over the
optimization time, while the other algorithms were strongly influenced by its
ideas. However, in spite of the large number of proposed algorithms, there was
little focus on creating and sharing tools to enable their use and study, a
problem that was well stated in 2013 (Rohlfshagen and Yao, 2013), and still
placed as one of the main issues in DOPs by 2021 (Yazdani et al., 2021b).

A very small number of works use a component-oriented approach to DOPs. For
example, Haluk et al. apply Hyper-heuristics to the Memory/Search algorithm to
improve characteristics that are important for DOPs, such as population
diversity (Topcuoglu et al., 2014). Danial et al. defines three strategies
(Cooperative Evolutionary, Tracking multiple moving optima, and Resource
allocation) that are applied to several optimizers such as CMA-ES, jDE, DynDE
and PSO (Yazdani et al., 2019). Even in these cases, the problems due to the
absence of source code remain, such as reproducibility and the difficulty of
analyzing components individually as well as their interaction effects,
although (Yazdani et al., 2019) discuss in detail the differences between
using or not certain strategies on the different algorithms.

##  3\. Performance measures

A _environment change_ happens when the parameters of the objective function
change in a dynamic problem. Let $NE\in\mathbb{N}$ be the total number of
evaluations in one run of an algorithm, an environment change can occur at any
evaluation $n\in[1,NE]\subset\mathbb{N}$. Let $CE\in\mathbb{N}$ be the total
number of changes that can occur ($CE<NE$), each $e\in[1,CE]\subset\mathbb{N}$
represents an environment in the run. $N(e)\in\mathbb{N}$ is the total number
of fitness evaluations on the $e^{th}$ environment.

_Subpopulations_ are often used in algorithms for dynamic optimization. Let
$pop\in\mathbb{N}$ the total number of individuals in the population, and
$N_{subpops}\in\mathbb{N}$ the number of subpopulations, and therefore,
$N_{subpops}<pop$, and each $subpop\in[1,N_{subpops}]\subset\mathbb{N}$
represents a subpopulation.

So, the term $I_{i,subpop}(e,n)$ is the individual $i$ of the subpopulation
$subpop$ at an environment $e$ at the evaluation $n$; The term
$I_{best_{i,subpop}}(e,n)$ is used to refer to the position with the highest
fitness an individual $I_{i,subpop}$ has had at the environment $e$ up to
evaluation $n$; The term $S_{best_{subpop}}(e,n)$ is the best individual of
the subpopulation $subpop$ at the environment $e$ up to evaluation $n$; and
the term $P_{best}(e,n)$ is used to refer to the best individual among the
entire population $pop$ at the environment $e$ up to evaluation $n$.

The metrics implemented in the AbCD Framework is the most frequently used in
the field of dynamic optimization, the Offline error ($E_{o}$) (Branke, 2002),
which is calculated as the average of the best results found up to a given
number of evaluations. Its Equation is as follows:

(1)
$E_{o}=\frac{1}{NE^{{}^{\prime}}}{\sum_{n=1}^{NE^{{}^{\prime}}}|f(G_{Op}(n))-f(P_{best}(n))|}$

where $f(G_{Op}(n))$ is the fitness value of the global optimum in the current
environment at the $nth$ fitness evaluation, $f(P_{best}(n))$ is the fitness
value of the best individual at the $nth$ fitness evaluation and
$NE^{{}^{\prime}}$ is the number of fitness evaluations so far. During the
execution of the algorithm $NE^{{}^{\prime}}$ is less than $NE$, and at the
end of the execution, we have $NE^{{}^{\prime}}=NE$.

##  4\. AbCD: Adjustable Components for Dynamic Problems

In this work, we create the Adjustable Component framework for Dynamic
Problems based on commonly used components of dynamic evolutionary algorithms.
We designed AbCD following the component-wise framework, similar to the
protocols used in the multiobjective domain (Bezerra et al., 2016; Campelo et
al., 2020; Lavinas et al., 2022).

The framework components are categorized according to how they act on
individuals in the population. The categories are Local (L), when it involves
only one subpopulation or Global (G) when it involves more than one
subpopulation. The list of all components in AbCD is shown in Table 1. Each
component can be classified given their functions: optimizer; change
detection; convergence detection; diversity control; and population division
and management (Yazdani et al., 2021a).

Table 1. Dynamic components in the AbCD framework Component Level | Component | Parameter(s)
---|---|---
Global component | Multipopulation | $N_{subpops}$
Exclusion | $r_{excl}$
Local component |  Reevaluation $S_{best}$ | None
Anti-convergence | $r_{conv}$
Local Search |  $r_{ls}$, $etry$
Optimizer | ES | $r_{cloud}$
PSO |  $\phi_{1}$, $\phi_{2}$
Hybrid(PSO+ES) |  $\phi_{1}$, $\phi_{2}$, $\%ES_{ind}$, $r_{cloud}$

##  5\. Experiments and Results

To evaluate the components as well as test the generated algorithms, the
Moving Peaks Benchmark (MPB) was used, as it is available from the Python
library DEAP (Fortin et al., 2012). This benchmark has several parameters
configurations, for example, the number of peaks, frequency of change, and
severity of the change, among others. Among the predefined scenarios,we set
MPB to the scenario 2, as it is frequently used (Nguyen, 2011; Blackwell and
Branke, 2006; Yang and Li, 2010; Yazdani et al., 2013, 2022).

For all the experiments in this section, the metrics presented are calculated
over the results of $50$ runs, each one with $500000$ fitness evaluation. Only
the change detection component is always enabled during all experiments, as it
is necessary in any DOP. The metrics used to evaluate the configurations are
the offline error ($E_{o}$).

###  5.1. Baseline

As a baseline, we configure PSO and ES in the AbCD framework. The PSO
parameters values used are $\chi=0.729$, $\phi_{1}=2.05$, and $\phi_{2}=2.05$,
these are commonly used in the literature, and more details about these values
can be seen in (Eberhart and Shi, 2000; Clerc and Kennedy, 2002).

Now, for the ES, and hybrid variations, we set the parameter value $r_{cloud}$
experimentally. We looked at the performance of $AbCD_{ES25}$, $AbCD_{ES50}$,
$AbCD_{ES75}$ and $ES$ in terms of variable values of $r_{cloud}$ in the MPB
set.

###  5.2. Manual Design

To design the Manual Designed AbCD configuration, $AbCD_{man}$, we use the
settings of MPB shown in Table 2, and the range of values for each component
are shown in Table 3. Each component was evaluated individually, as the only
addition to the main base algorithm, for each optimizers. The number of
individuals in a population is fixed in $pop=100$, a commonly used value from
the literature. The value $etry=20$ for the Local search component was chosen
based on the experiments in (Yazdani et al., 2013).

Table 2. MPB settings for baseline and manual design Parameter | Setting
---|---
Peak function |  $cone()$(Fortin et al., 2012)
Number of peaks | $10$
Number of dimensions | $10$
Peak heights | $\in[30,70]$
Peak widths | $\in[1,12]$
Change frequency |  Every $5000$ evaluations
Change severity $s$ | $1$
Correlation coefficient $\lambda$ | $0$
Table 3. Components search space for manual design Components | Domain
---|---
Optimizer | $PSO,AbCD_{ES25},_{ES50},_{ES75},ES$
Multipopulation | $N_{subpops}=1,5,10,25,50,100$
Exclusion | $r_{excl}\in[0,50]$
Anti-convergence | $r_{conv}\in[0,50]$
Local Search |  $r_{ls}\in[0,50]$ and $etry=20$

We first analyze the multipopulation component. Increasing the sub-population
size deteriorates the performance of the AbCD variants and that for the pair
instances and configurations tested, having $N_{subpops}=1$, or just a single
population, leads to the best results in terms of offline error.

That said, most of the dynamic components (with the exception of Local search)
depend on the configurations using multipopulations. Therefore, for the
setting of the parameters of such components, we follow the suggested value of
the number of subpopulations being equal to the number of peaks in the
problem, $N_{subpops}=10$, (Blackwell and Branke, 2006) .

Interestingly, we can only observe small differences for low values of radii
while higher values lead to higher error values. Given the limited positive
impact of the dynamic components, we select the $AbCD_{man}$ as the
$AbCD_{ES75}$ without dynamic components.

###  5.3. Automatic Design

To design the automatic AbCD configuration ($AbCD_{auto}$) we use different
settings of MPB for training and testing, as shown in Table 4. The range of
values for each component are shown in Table 5.

Table 4. MPB settings for automatic training and testing Parameter | training | testing
---|---|---
Peak function | $cone()$ | $cone()$
Peaks | $8,10$ | $9,11$
Dimensions | $8,10$ | $7,9$
Peak heights | $\in[30,70]$ | $\in[30,70]$
Peak widths | $\in[1,12]$ | $\in[1,12]$
Change frequency |  Every $5000$ evals |  Every $5000$ evals
Change severity $s$ | $1,2$ | $1.5,2.5$
Correlation $\lambda$ | $0$ | $0$
Table 5. Components search space for automatic design Components | Domain
---|---
Population size |  $100$, $150$, $200$, $300$
Optimizer |  $PSO$ $\rightarrow\phi_{1}\in[0,2.50],\phi_{2}\in[0,2.50]$
$ES$ $\rightarrow r_{cloud}\in[0,5]$
|  $AbCD_{ES{\%}}$ $\rightarrow$ $\begin{cases}\%=25,50,75\\\
\phi_{1}\in[0,2.50],\phi_{2}\in[0,2.50]\\\ r_{cloud}\in[0,5]\end{cases}$
---
Multipopulation |  True, $N_{subpops}=10,25,50,100$
False, not used
Exclusion |  True, $r_{excl}\in[0,80]$
False, not used
Anti-convergence |  True, $r_{conv}\in[0,80]$
False, not used
Local Search |  True, $r_{ls}\in[0,80],etry\in[1,50]$
False, not used

We were surprised by the $AbCD_{auto}$ configuration in terms of the number of
sub-populations and the Local search values. Having a large number of sub-
population seems to benefit $AbCD_{auto}$ by reducing the interaction among
the individuals in the population, probably allowing $AbCD_{auto}$ to explore
more peaks. Also, this configuration has Local search with a high $r_{ls}$
value and a small number of iterations ($etry=2$), which suggests that Local
search is used to explore a wider area near the best individual.

When we compare the results on $AbCD_{auto}$ with $AbCD_{man}$ we see some
consensus for most of the components. For example, both configurations use 75%
ES individuals (with 25% being PSO individuals). Also, they don’t use the
dynamic components exclusion and anti-convergence. The PSO and ES parameters
are slightly different. Moreover, the most divergent choices of components are
the number of sub-populations, in different extremes, and the presence of
local search in $AbCD_{auto}$. Although we can see a difference in the use of
the local search component, irace selected a small number of tries, which
suggests that the impact of this component is likely to be small. On the other
hand, the reasons behind the contrary number of sub-populations needs more
work.

###  5.4. Results

Here we compare PSO, ES, mQSO, $AbCD_{man}$, and $AbCD_{auto}$ using the
offline error ($E_{o}$). We evaluate them in five instances, generated under
the MPB scenario 2 setting. We refer to them first by their dimension, then by
the number of peaks, and finally by the severity. For example, the 5D-10P-1s
instance with 5 dimensions, 10 peaks, and severity 1. We show the results in
Table 6.

Table 6. $E_{o}$ of the different configurations Algorithm | 5D-10P | 8D-10P | 10D-10P
---|---|---|---
$PSO$ | $E_{o}=15.12(1.62)$ | $E_{o}=13.01(2.43)$ | $E_{o}=19.42(0.03)$
$ES$ | $E_{o}=14.63(1.71)$ | $E_{o}=13.17(2.71)$ | $E_{o}=19.04(0.12)$
$mQSO$ | $E_{o}=7.97(1.21)$ | $E_{o}=13.64(0.66)$ | $E_{o}=23.36(0.89)$
$AbCD_{man}$ | $E_{o}=14.78(1.71)$ | $E_{o}=12.80(2.53)$ | $E_{o}=18.72(0.03)$
$AbCD_{auto}$ | $E_{o}=6.37(0.71)$ | $E_{o}=11.10(1.23)$ | $E_{o}=19.90(2.49)$

For lower dimensions, 5D-10P-1s instance, we can see that the performance of
the configurations can be divided into two groups, those with a good
performance value, with mQSO and $AbCD_{auto}$, and the second group with the
other configurations. The performance of both mQSO and $AbCD_{auto}$
deteriorates as the number of dimensions increases, although $AbCD_{auto}$
keeps a good overall performance.

This good performance of $AbCD_{auto}$ comes without a surprise since irace
searched for a configuration that would perform well in most of the instances.
Interestingly, $AbCD_{auto}$ was designed for instances with high dimensions,
but it could extrapolate its good performance to an easier problem. We ask
ourselves if the same would be true for more challenging instances.

A more interesting result is that dimensionality has a big impact on the
performance of the configurations. For example, mQSO is among the best in the
problem with the lowest dimension and the worse as the number of dimensions
increases. This goes in agreement with the results of the manual and automatic
design, which found that using the main components of mQSO, exclusion, and
anti-convergence, lead to a reduction in the performance of the
configurations. We believe one of the reasons for this loss in performance in
high dimensions could be given that these two components use the Euclidean
distance and a more suited metric for distances in many dimensions should be
considered in future works.

Another remarkable result is that a recombination of commonly used
evolutionary algorithms in static problems can lead to good dynamic
configurations, as shown by the increments in performance by the
configurations $AbCD_{man}$ and $AbCD_{auto}$. This suggests that
incorporating even more effective evolutionary algorithms into the AbCD
framework would benefit the dynamic community.

##  6\. Conclusion

The aim of this work was to introduce a new component-wise based on commonly
used operators in DOPs, the Adjustable Component framework for Dynamic
Problems. The main goals were to make it available as a framework for
extensive experimentation of dynamic EAs and the analysis of new dynamic
components and to facilitate the design of ones as well as a tool to simplify
the manual and automatic design of algorithms. All the code and experimental
scripts as well the most current version of the framework is available and can
be found in GitHub https://github.com/mascarenhasav/AbCD111The source code for
the framework, as well as experimental data used in this paper, is available
in the supplementary materials. It will also be on an online repository by the
final submission.

This analysis allowed us to verify that, contrary to our expectations, the
dynamic components were less influential in leading to increments in the
performance of the algorithm configurations studied here. It seems that the
effect can only be observed in problems with low dimensionality. We understand
that this suggests that more work should be done to improve their influence in
more dimensions. We also found that the dimensionality of the problem seems to
have a higher impact on the search ability of the EAs studied in this work.

We conducted an analysis on the choices of components in the $AbCD_{man}$ and
the $AbCD_{auto}$, and we observed that there is an agreement in the choice of
the percentage of the number of individuals that are optimized by ES or PSO
and in the choice of the dynamic components, not selected in both
configurations. However, it seems that there is some interaction among some
components since the choice of Local search and the number of sub-population
is clearly different between these two configurations. More focus should be
directed towards clarifying these interactions.

Then, we studied PSO, ES, mQSO, $AbCD_{man}$, and $AbCD_{auto}$. The first two
algorithms are commonly used metaheuristics, mQSO is a representative of EAs
for dynamic problems, and the $AbDC_{man}$ and $AbCD_{auto}$ are algorithm
configurations generated using the components available in our framework. The
results have shown that their relative efficiency depends on the problem’s
difficulty: mQSO and $AbCD_{auto}$ are the best in lower dimensional problems
while PSO, ES, and $AbCD_{man}$ achieve a higher performance as the number of
dimensions increase. These results show the power of the AbCD framework, since
we can develop established and new EAs and study their performance in dynamic
problems.

## References

  * (1)
  * Bezerra et al. (2016) Leonardo C. T. Bezerra, Manuel López-Ibáñez, and Thomas Stützle. 2016.  Automatic Component-Wise Design of Multiobjective Evolutionary Algorithms.  _IEEE Transactions on Evolutionary Computation_ 20, 3 (2016), 403–417.  https://doi.org/10.1109/TEVC.2015.2474158
  * Blackwell and Branke (2006) T. Blackwell and J. Branke. 2006.  Multiswarms, exclusion, and anti-convergence in dynamic environments.  _IEEE Transactions on Evolutionary Computation_ 10, 4 (2006), 459–472.  https://doi.org/10.1109/TEVC.2005.857074
  * Branke (1999) J. Branke. 1999\.  Memory enhanced evolutionary algorithms for changing optimization problems. In _Proceedings of the 1999 Congress on Evolutionary Computation-CEC99 (Cat. No. 99TH8406)_ , Vol. 3. 1875–1882 Vol. 3.  https://doi.org/10.1109/CEC.1999.785502
  * Branke (2002) Jürgen Branke. 2002\.  _Empirical Evaluation_.  Springer US, Boston, MA, 67–98.  https://doi.org/10.1007/978-1-4615-0911-0_5
  * Campelo et al. (2020) Felipe Campelo, Lucas Batista, and Claus Aranha. 2020\.  The MOEADr Package: A Component-Based Framework for Multiobjective Evolutionary Algorithms Based on Decomposition.  _Journal of Statistical Software_ (2020).  In press. Available from: https://arxiv.org/abs/1807.06731.
  * Clerc and Kennedy (2002) M. Clerc and J. Kennedy. 2002.  The particle swarm - explosion, stability, and convergence in a multidimensional complex space.  _IEEE Transactions on Evolutionary Computation_ 6, 1 (2002), 58–73.  https://doi.org/10.1109/4235.985692
  * Eberhart and Shi (2000) R.C. Eberhart and Y. Shi. 2000.  Comparing inertia weights and constriction factors in particle swarm optimization. In _Proceedings of the 2000 Congress on Evolutionary Computation. CEC00 (Cat. No.00TH8512)_ , Vol. 1. 84–88 vol.1.  https://doi.org/10.1109/CEC.2000.870279
  * Fortin et al. (2012) Félix-Antoine Fortin, François-Michel De Rainville, Marc-André Gardner, Marc Parizeau, and Christian Gagné. 2012.  DEAP: Evolutionary Algorithms Made Easy.  _Journal of Machine Learning Research_ 13 (jul 2012), 2171–2175.
  * Hu and Eberhart (2002) Xiaohui Hu and R.C. Eberhart. 2002.  Adaptive particle swarm optimization: detection and response to dynamic systems. In _Proceedings of the 2002 Congress on Evolutionary Computation. CEC’02 (Cat. No.02TH8600)_ , Vol. 2. 1666–1670 vol.2.  https://doi.org/10.1109/CEC.2002.1004492
  * Lavinas et al. (2022) Yuri Lavinas, Marcelo Ladeira, Gabriela Ochoa, and Claus Aranha. 2022.  Component-Wise Analysis of Automatically Designed Multiobjective Algorithms on Constrained Problems. In _Proceedings of the Genetic and Evolutionary Computation Conference_ _(GECCO ’22)_. New York, NY, USA, 538–546.  https://doi.org/10.1145/3512290.3528719
  * López-Ibáñez et al. (2016) Manuel López-Ibáñez, Jérémie Dubois-Lacoste, Leslie Pérez Cáceres, Mauro Birattari, and Thomas Stützle. 2016.  The irace package: Iterated racing for automatic algorithm configuration.  _Operations Research Perspectives_ 3 (2016), 43–58.  https://doi.org/10.1016/j.orp.2016.09.002
  * Nguyen (2011) Trung Nguyen. 2011\.  _Continuous dynamic optimisation using evolutionary algorithms_.  Ph. D. Dissertation.
  * Rohlfshagen and Yao (2013) Philipp Rohlfshagen and Xin Yao. 2013.  Evolutionary Dynamic Optimization: Challenges and Perspectives. In _Evolutionary Computation for Dynamic Optimization Problems_ , Shengxiang Yang and Xin Yao (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 65–84.
  * Topcuoglu et al. (2014) Haluk Rahmi Topcuoglu, Abdulvahid Ucar, and Lokman Altin. 2014\.  A hyper-heuristic based framework for dynamic optimization problems.  _Applied Soft Computing_ 19 (2014), 236–251.  https://doi.org/10.1016/j.asoc.2014.01.037
  * Woldesenbet and Yen (2009) Yonas G. Woldesenbet and Gary G. Yen. 2009.  Dynamic Evolutionary Algorithm With Variable Relocation.  _IEEE Transactions on Evolutionary Computation_ 13, 3 (2009), 500–513.  https://doi.org/10.1109/TEVC.2008.2009031
  * Yang and Li (2010) Shengxiang Yang and Changhe Li. 2010.  A Clustering Particle Swarm Optimizer for Locating and Tracking Multiple Optima in Dynamic Environments.  _IEEE Transactions on Evolutionary Computation_ 14, 6 (2010), 959–974.  https://doi.org/10.1109/TEVC.2010.2046667
  * Yazdani et al. (2021a) Danial Yazdani, Ran Cheng, Donya Yazdani, Jürgen Branke, Yaochu Jin, and Xin Yao. 2021a.  A Survey of Evolutionary Continuous Dynamic Optimization Over Two Decades—Part A.  _IEEE Transactions on Evolutionary Computation_ 25, 4 (2021), 609–629.  https://doi.org/10.1109/TEVC.2021.3060014
  * Yazdani et al. (2021b) Danial Yazdani, Ran Cheng, Donya Yazdani, Jürgen Branke, Yaochu Jin, and Xin Yao. 2021b.  A Survey of Evolutionary Continuous Dynamic Optimization Over Two Decades—Part B.  _IEEE Transactions on Evolutionary Computation_ 25, 4 (2021), 630–650.  https://doi.org/10.1109/TEVC.2021.3060012
  * Yazdani et al. (2013) Danial Yazdani, Babak Nasiri, Alireza Sepas-Moghaddam, and Mohammad Reza Meybodi. 2013.  A novel multi-swarm algorithm for optimization in dynamic environments based on particle swarm optimization.  _Applied Soft Computing_ 13, 4 (2013), 2144–2158.  https://doi.org/10.1016/j.asoc.2012.12.020
  * Yazdani et al. (2019) Danial Yazdani, Mohammmad Nabi Omidvar, Jurgen Branke, Trung Nguyen, and Xin Yao. 2019\.  Scaling Up Dynamic Optimization Problems: A Divide-and-Conquer Approach.  _IEEE Transactions on Evolutionary Computation_ PP (03 2019), 1–1.  https://doi.org/10.1109/TEVC.2019.2902626
  * Yazdani et al. (2022) Danial Yazdani, Mohammad Nabi Omidvar, Ran Cheng, Jürgen Branke, Trung Thanh Nguyen, and Xin Yao. 2022.  Benchmarking Continuous Dynamic Optimization: Survey and Generalized Test Suite.  _IEEE Transactions on Cybernetics_ 52, 5 (2022), 3380–3393.  https://doi.org/10.1109/TCYB.2020.3011828


11institutetext: CASOS Institute, Carnegie Mellon University,
{rkuzma2<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
http://www.casos.cs.cmu.edu/

# Influencing the Influencers: Evaluating Person-to-Person Influence on Social
Networks Using Granger Causality ††thanks: The research for this paper was
supported in part by the Knight Foundation and the Office of Naval Research
Grant (N000141812106) and an Omar N. Bradley Fellowship, and by the center for
Informed Democracy and Social-cybersecurity (IDeaS) and the center for
Computational Analysis of Social and Organizational Systems (CASOS) at
Carnegie Mellon University. The views and conclusions are those of the authors
and should not be interpreted as representing the official policies, either
expressed or implied, of the Knight Foundation, Office of Naval Research or
the US Government.

Richard Kuzma  Iain J. Cruickshank  Kathleen M. Carley

###### Abstract

We introduce a novel method for analyzing person-to-person content influence
on Twitter. Using an Ego-Alter framework and Granger Causality, we examine
President Donald Trump (the Ego) and the people he retweets (Alters) as a case
study. We find that each Alter has a different scope of influence across
multiple topics, different magnitude of influence on a given topic, and the
magnitude of a single Alter’s influence can vary across topics. This work is
novel in its focus on person-to-person influence and content-based influence.
Its impact is two-fold: (1) identifying “canaries in the coal mine” who could
be observed by misinformation researchers or platforms to identify
misinformation narratives before super-influencers spread them to large
audiences, and (2) enabling digital marketing targeted toward upstream Alters
of super-influencers.

###### keywords:

Influence, Social Media, Granger Causality

##  1 Introduction

Influence in social networks remains one of the mainstays of social network
analysis. Recently, with the advent of online social networks and the
influence that online misinformation and disinformation can have, social
influence has taken on added importance and dimensions. In this work, we build
upon the foundations of social influence by examining social influence at the
Ego network level. Using an Ego-Alter framework we identify an Ego (Donald
Trump), examine which Twitter accounts he retweets most to identify key Alters
(e.g. Ivanka Trump, Linsdey Graham), identify tweet topics from the Ego using
unsupervised machine learning, build a supervised machine learning classifier
to classify tweets of Alters into those topics [2, 3]. Then for a given topic,
we measured the influence of each Alter on the Ego by measuring the Granger
causality on the Alter’s tweet time series on the Ego’s tweet time series.

We devised this method in order to answer the question, “who influences the
influencers?” Given the role that social media super-influencers may play in
the spread of (mis)information online, identifying who influences them, what
topics they are influenced on, and how much they are influenced could be key
to future misinformation studies.

Figure 1: Example of an Alter’s Tweets affecting the Ego’s Tweets for a given
topic. Certain topics in the Alter’s tweets are then Tweeted, with a time-
delay by the Ego.

Our work is novel from other applications of Granger causality for a few
reasons. Most Granger causality research on social media focuses on (1)
population-level influence, (ours focuses on person-to-person influence); (2)
sentiment analysis, (ours focuses on topics analysis); and (3) impact of
social media behavior on real world events such as financial markets or
protests (our work focuses on influence within online behavior on Twitter) [7,
27, 4]. Other work using Granger causality to examine person-to-person
influence on social media examined sharing of explicit URLs between Twitter
accounts, but not the content or topic of tweets as we do [35].

##  2 Background

The last few years have seen incredible advances in, and need for, social
cybersecurity. Social Cybersecurity is an emerging field that looks at the
intersection of human behavior in a cyber mediated information environment
[10]. In particular, recent events like the COVID-19 pandemic and use of
online disinformation in various national elections have highlighted the need
to better understand the ways in which mis- and disinformation are spread
online [36, 8]. Previous works have generally focused on the role of bots and
trolls in their roles in spreading mis- and disinformation [5, 6, 24, 26, 10,
37]. More recently, coordination among cyborg or fully human accounts has been
studied as means by which malicious actors can propagate mis- and
disinformation [20, 31, 30]. The insight of coordinated spread by social media
accounts is even being used to investigate cross-platform mis- and
disinformation spread [34]. To date, much of the research in online mis- and
disinformation campaigns has focused on particular types of accounts and
coordination among accounts.

One area of the spread of online mis- and disinformation that is less well-
studied is the role of online social media influencers. Social media
influencers, or those online accounts with the ability to reach hundreds of
thousands, if not millions, of other social media users with their content
represent an important component of the social media landscape, by virtue of
their reach. Recent work has shown that social media influencers can often
have an outsized impact on the information quality of any given online
discussion. For example, one study showed that the former U.S. President
Donald Trump was responsible for over 30% of the COVID-19 misinformation on
Twitter [15]. As another example, the ‘dirty dozen’, a collection of only
twelve accounts, are responsible for the vast majority of anti-vaccination
content online [14]. Additionally, recent disinformation campaigns, like
Secondary Infektion have deliberately sought to target social media
influencers to get them to spread disinformation [1, 17]. Thus it is clear
that social media influencers can play a tremendous role in the spread of mis-
and disinformation.

It is also important to note that the study of influence in social networks
has a long history with much research into the topic. The study of influence
in social networks pre-dates online social networks and has been used to
understand everything from individuals’ behaviors to collective action of
groups [13, 19, 18]. Many of the models designed for understanding social
influence work at the adjacency matrix-level of the social networks, and are
fundamentally matrix based models [28, 16]. As such, these models tend to look
more at population levels of influence. Less studied within the social network
analysis community is the role and exercise of social influence of Ego
networks.

An important consideration when studying influence is the role of causality.
Granger causality is a statistical method that examines whether $X$ has
predictive power in describing $Y$ [22]. $X_{t}$ is said to Granger-cause
$Y_{t}$ if $Y_{t+1}$ can be better explained by past values of $Y_{t}$ and
past values of $X_{t}$ than by the presence of past values of $Y_{t}$ alone.

###  2.1 Data and Definitions

We retrieved tweets from Donald Trump from the Trump Twitter Archive [9]. This
repository contains 56,571 tweets and retweets from Donald Trump’s twitter
account. Reports indicate that not all tweets from the @RealDonaldTrump
twitter account come directly from Donald Trump. Prior to the presidency, it
was believed that tweets from an Android device were from Donald Trump while
other platforms (iPhone, web) were not. Once Donald Trump became president, he
switched to a specially-issued iPhone. At least one staffer was trusted with
@RealDonaldTrump twitter privileges. Tweets came from Donald Trump, direct
dictations to staffers, and presumably from the close, trusted staffers
themselves attempting to channel Donald Trump’s head space [12]. Given the
importance of the Twitter audience to Donald Trump, we believe that all tweets
from the account, even those from staffers instead of Trump himself,
accurately reflect Donald Trump’s wishes and are worth studying as if they
came from Trump himself.

##  3 Methods

Figure 2: Overview of Method. Our method consists of three, main steps:
gathering the data and constructing the ego-later network, finding topics in
the textual data and building a classifier of those topics, and then testing
for causality in the ego-alter network on those topics.

Our method has three stages: gathering data, identifying topics of
conversation, and determining granger causality.

###  3.1 Gathering Data

We gathered tweets from the Trump Twitter Archive, which retained copies of
all of Trump’s tweets and retweets from before Trump’s Twitter suspension. CSV
and JSON files with all captured tweets are available at the Trump Twitter
Archive. We limited tweets to the time that Donald Trump was President of the
United States and active on Twitter, January 20th, 2017 to January 8th, 2020.
We hypothesized that the information Trump ingested affected the information
he output. In other words, what he retweeted affected what he tweeted. We
found 12 accounts from individuals Trump retweeted the most (the Alters). We
excluded Trump’s retweets of @WhiteHouse and of himself (@RealDonaldTrump).
These Alters included family members, conservative media pundits, and members
of Congress. We used SNScrape, an open-source tool, to get the tweet IDs of
these 12 Alter accounts [25]. The original tweets of these accounts were
available, but data was not available on who these Alters retweeted. We used
these tweet IDs to get the tweet content and metadata through a process known
as hydration, using Hydrator, another open-source tool [29].

###  3.2 Identifying Topics

We cleaned Trump’s tweets by extracting URLs, mentions, and “RT” (used for
manual retweets when Trump quoted another twitter user) from tweets. We also
used the gensim Python library to preprocess tweets by removing punctuation
and making all words lowercase. We then tokenized the tweets and found common
bigrams and trigrams using the gensim library. Bigrams are two-word sequences
like “crooked hillary” or “sleepy joe” and trigrams are three-word sequences
like “make america great.” Following tokenization, we embedded the tweets
using the Universal Sentence Encoder (USE) from Google Research which was
available at the TensorFlow Hub [11, 21]. We also featurized all tweets using
the term frequency-inverse document frequency (TF-IDF) from the scikit learn
library [32].

We chose the USE because it was built for short sequences ranging from a
sentence to a short paragraph in length, which is similar to the length of a
tweet, and performs well in semantic similarity tasks, determining if one
sequence is similar to another. We performed k-medoids clustering [38] on the
USE embeddings to identify topic clusters and within those topic groups
examined the most important words by averaging the TF-IDF scores of all
documents within a given USE cluster.

We chose to cluster only on the Ego’s tweets because including Alter tweets in
the topic classifier would dilute the Ego’s tweet content with Alter content
when forming clusters. With 12 Alters in our case study, it is possible topics
would drift toward Alter content rather than Ego content, making a classifier
predict whether a given Alter’s tweet was like other Alter tweets rather than
similar to the Ego’s tweet. We settled on eight topics for Trump’s tweets
through a combination of silhouette score [33] from the k-medoid clustering of
USE embeddings and interpretation of the TF-IDF top words for each cluster.

Figure 3: Top 50 words and phrases used by Donald Trump in each topic (ranked
by TF-IDF score). Clusters determined by USE embeddings.

We categorized each Alter’s tweets into one of the categories of Trump’s
tweets. To do this we train a Support Vector Classifier on Trump’s tweets,
using the USE embeddings as features and the unsupervised topic clusters as
the label. Our final model had a weighted F-1 score of 0.91.

For each Alter, we clean the tweets using the same cleaning pipeline as
Trump’s tweets then embed the tweets using USE embeddings. We then use the
model trained to predict Trump’s tweet categories to predict the Alter’s tweet
categories. Now that the Alter’s tweets are categorized, we turn them into
eight time series, one for each of the topic clusters. We use weeks as time-
steps because we found days contained too few tweets to make an effective time
series for each topic.

###  3.3 Granger Causality

We create a time-series with units of weeks on the x-axis and number of user’s
tweets on a given topic on the y-axis. The Ego, $E$, and Alters, $A_{1}$ to
$A_{n}$, each each have $m$ time series, where $m$ is the number of topics.
Then, for a given Alter (e.g. Ivanka Trump) and a given topic (e.g. Campaigns)
we want to find if the Alter’s tweets granger-cause (have predictive power to
describe) the the tweets of the Ego (e.g. Donald Trump).

We first considered granger causality at the level of days, but found that
most users did not have enough data when viewing topics at the day level. We
think weeks are a viable time scale because intuition suggests that an Alter
may tweet about a topic of importance to them repeatedly. In future work, it
would be worth considering a 2-3 day rolling window

Testing for granger causality requires that both time series are stationary,
that is, the mean, variance, and autocorrelation do not change with time.
Stationary was checked with the Augmented Dickey Fuller test [23]. If a time
series is not stationary, it may be made stationary by differencing the time
series. This requires subtracting the number of tweets at time $t$ from the
number of tweets at time $t-1$. If the time series of the Alter’s or Trump’s
tweets for a given topic are not stationary, both time series were differenced
and stationarity re-examined. This way both time series always had the same
amount of differencing.

If the time series could be made stationary, a granger causality test can then
be done. Again, this test determines if $Y_{t}$ (Trump’s tweets on a topic) is
better explained by $Y_{t-n}$ (Trump’s previous tweets on that topic) alone or
$Y_{t-n}$ and $X_{t-n}$ (Alter’s previous tweets on that same topic).

##  4 Results

Different Alters influence the Ego on different topics. Even among Alters
whose tweets granger-cause Trump’s tweets, some Alters have a more immediate
effect (1 week) while others affect Trump’s tweets with six to eight weeks of
lag.

Members of Congress (Mark Meadows, Jim Jordan, GOP Chairwoman) had influence
on the “Congress” topic with one week lag between their tweets and Trump’s.
Jim Jordan and GOP Chairwoman also influenced the “Investigations” topic with
a one week lag.

Conservative pundits (Mark Levin, Gregg Jarrett, and Tom Fitton) influenced
the most topics (6-7), though not all with immediate effect. Their tweets on
“Fake News,” “Campaigning,”, and “Investigations” (along with pundit Charlie
Kirk, though less so with Tom Fitton) had 1-3 week lags between their tweets
and Trumps.

Donald Trump Jr had influence on “Fake News,” “Congress,” “Campaigning,” and
“America First” topics, all with 1-3 week lags. Ivanka Trump only influenced
“America First” and “Praising Trump” but with 5-6 week lags. Eric Trump had
influence on more topics, but a mix of immediate lag (1-3 week) and delayed
lag (6-7 week) influence.

Among Alters that influenced five or more topics (Eric Trump, Mark LEvin,
Gregg Jarrett, and Tom Fitton), the immediacy of influence was not consistent.
Often the Alter had a few topics with immediate lag influence (1-2 week) and a
few with delayed lag influence (7-8 week).

We chose to do individual hypothesis testing and felt the low p-values would
not substantively change with multiple hypothesis testing, but future work may
choose to multiple hypothesis testing for added rigor.

Figure 4: P-Values for granger causality test. Num lags in parenthesis (max 8
weeks). Alters shown in three groups: (1) family/close advisors, (2) members
of Congress, and (3) political commentators.

##  5 Discussion

In this paper we ask “who influences the influencers?” and introduce a novel
method for examining person-to-person influence on Twitter using an Ego-Alter
framework for finding which Alters influence the Ego’s posts on social media,
on which topics these Alters influence the Ego, and the time delay between
Alter posts and Ego posts. We show this specifically with tweets from Donald
Trump and the first-order Alters he interacts with on Twitter, but believe
this work could be extended to examine other influencers on Twitter and their
networks, to include second and third-order Alters farther away from the Ego’s
immediate network, and attempted on other social media platforms (Parler,
Facebook).

Our results show substantial variation in the influence of Alters on an Ego.
While our work confirms the general theories of social influence in that
social influence affects an individual’s behavior, we also note what
influences an individual and when they influence that individual are
heterogeneous entities. Some Alters have a greater scope of influence. Of
Donald Trump’s eight tweet topics, some Alters influence only one or two
topics while others influence seven of the eight topics. Some Alters have
narrow, but powerful, influence. Charlie Kirk, a conservative talk show host,
influences Trump on only two topics, “investigations” and “democrat
obstruction.” Trump’s tweets lag Kirk’s by only one week, showing that Kirk
has high influence on these topics. Five other Alters influence the
“investigations” topic and three of them also have a one-week lag on their
influence, so Kirk is not special in this category. On “democrat obstruction,”
however, only two other Alters with influence. Kirk has a one-week lag between
his “democrat obstruction” tweets and Trumps, while the other Alters have a
seven-week lag, indicating less influence on this topic.

Different Alters influence different topics and should not be viewed as
substitutable. Tom Fitton, a conservative activist and President of Judicial
Watch, is very influential in the “fake news,” “america first,” and “praising
trump” categories whereas Jim Jordan, a Congressman from Ohio, is highly
influential on topics of “congress,” “campaigning,” and “investigations.”

Some Alters influence different topics differently. This suggests that some
Alters are more influential on certain topics than others. For instance, Gregg
Jarrett, a conservative American television commentator, influences Trump’s
tweets on seven of eight topics. On “fake news” and “investigations” his
tweets influence Trump’s after a one-week lag. On “MAGA” and “America First”
his tweets influence Trump’s after a five-week and seven-week lag,
respectively. Jarett would be a good influence vector for “fake news” and
“investigations” but not as good for “MAGA” and “America First”

###  5.1 Future Work

Despite the useful results and demonstration of using granger-causality in
understanding peer-to-peer influence on social media, there are limitations to
this work. We examine a specific case of influence surrounding Donald Trump,
without any comparison to how these Alters affected other Twitter users or how
other Egos are influenced by their respective Alters . We focused on this base
case because the Trump Twitter Archive permitted us to study the retweets of
the Ego to identify the most-retweeted Alters. Generally, retweets of specific
Twitter accounts are not available through the Twitter API nor are they
available through Python libraries like SNScrape, making data collection
difficult. If retweets of Alters were available, research could be done on
whether second-order Alters (e.g. someone who Ivanka Trump retweets a lot) has
influence on the Ego (Donald Trump) through the first-order Alter (Ivanka
Trump).

We see two uses of this influence work. First, in the disinformation space,
using Alters as “canaries in the coal mine” who could be observed by
misinformation researchers or platforms to notice new misinformation
narratives before super-influencers catch hold of these narratives and spread
them to millions of people. Second, in the marketing space, advertisers may
not have the budget to pay a super-influencer to market their product, but by
paying the Alters of the Ego, the advertiser may be able to influence the
super-influencer to support the product being marketed.

## References

  * [1] Secondary infektion (2021), https://secondaryinfektion.org/
  * [2] Arnaboldi, V., Conti, M., Passarella, A., Pezzoni, F.: Analysis of ego network structure in online social networks. International Conference on Privacy, Security, Risk and Trust and 2012 International Conference on Social Computing 10, 31–40 (2012)
  * [3] Arnaboldi, V., Conti, M., Passarella, A., Pezzoni, F.: Ego networks in twitter, an experimental analysis pp. 3459–3464 (2013)
  * [4] Bastos, M.T., Mercea, D., Charpentier, A.: Tents, tweets, and events: The interplay between ongoing protests and social media. Journal of Communication 65(2) (2015)
  * [5] Beskow, D.: Finding and Characterizing Information Warfare Campaigns. Ph.D. thesis (2020)
  * [6] Bessi, A., Ferrara, E.: Social bots distort the 2016 u.s. presidential election online discussion. First Monday 21(11) (2016)
  * [7] Bolllen, J., Mao, H., Zeng, X.: Twitter mood predicts the stock market. Journal: of Computational Science 2(1), 1–8 (2011)
  * [8] Brangham, W.: “tech heads testify on misinformation in the aftermath of jan 6 riots. ” PBS. org, https://www.pbs.org/newshour/show/tech-heads-testify-on-misinformation-in-the-aftermath-of-jan-6-riots, Mar 25 (2021)
  * [9] Brendan: Trump twitter archive v2 (2021), https://www.thetrumparchive.com/
  * [10] Carley, K.M.: Social cybersecurity: an emerging science (2020)
  * [11] Cer, D, e.a.: Universal Sentence Encoder. ArXiv (2018), https://arxiv.org/abs/1803.11175
  * [12] Chute, N.: He writes trump’s tweets and has been with trump’s campaign since day one (2019)
  * [13] Coussi-Korbel, S., Fragaszy, D.M.: On the relation between social dynamics and social learning. Animal Behaviour 50(6), 1441–1453 (1995)
  * [14] Dozen, T.D.: Center for Countering Digital Hate (2021)
  * [15] Evanega, S, e.a.: Quantifying sources and themes in the covid-19 ‘infodemic’ (2020)
  * [16] Flache, A., Mäs, M., Feliciani, T., Chattoe-Brown, E., Deffuant, G., Huet, S., Lorenz: Models of social influence: Towards the next frontiers. Journal of Artificial Societies and Social Simulation 20(4) (2017), http://jasss.soc.surrey.ac.uk/20/4/2.html¿.doi:10.18564/jasss.3521
  * [17] Foundation, M.: Disinformation about belarus spreads in the balkans via online portals and social media (2020)
  * [18] Friedkin, N., Johnsen, E.: Social influence network theory: A sociological examination of small group dynamics (structural analysis in the social sciences) (2011)
  * [19] Friedkin, N.E., Proskurnikov, A.V., Tempo, R., Parsegov, S.E.: Network science on belief system dynamics under logic constraints. Science 354(6310), 321–326 (2016), https://science.sciencemag.org/content/354/6310/321
  * [20] Giglietto, F., Righetti, N., Rossi, L., Marino, G.: It takes a village to manipulate the media: coordinated link sharing behavior during 2018 and 2019 italian elections. Information, Communication & Society 23(6), 867–891 (2020)
  * [21] Google: Universal sentence encoder [computer software] (2018)
  * [22] Granger, C.W.J.: Investigating causal relations by econometric models and cross-spectral methods. Econometrica 37(3), 424–438 (1969)
  * [23] Greene, W.H.: Econometric Analysis. Macmillan Publishing Company (199)
  * [24] Hui, P.M., Yang, K.C., Torres-Lugo, C., Monroe, Z., McCarty, M., Serrette, B.D., Pentchev, V., Menczer, F.: Botslayer: real-time detection of bot amplification on twitter. Journal of Open Source Software 4(42), 1706 (2019), https://doi.org/10.21105/joss.01706
  * [25] JustAnotherArchivist: snscrape [computer software] (2021), https://github.com/JustAnotherArchivist/snscrape
  * [26] M, H.W., S, G., A, D., M, R., L, U., HA, S., DH, E., L, L., Curtis: Bots and misinformation spread on social media: Implications for covid-19. Journal of Medical Internet Research 23(5) (2021)
  * [27] Mittal, A., Goel, A.: Stock prediction using twitter sentiment analysis (2011), http://cs229.stanford.edu/proj2011/GoelMittal-StockMarketPredictionUsingTwitterSentimentAnalysis.pdf
  * [28] Nedić, A., Olshevsky, A., Uribe, C.A.: Graph-theoretic analysis of belief system dynamics under logic constraints. Scientific Reports 9 (2019)
  * [29] the Now, D.: Hydrator [computer software], https://github.com/docnow/hydrator
  * [30] Pacheco, D., Hui, P., Torres-Lugo, C., Truong, T., B, F., A, Menczer, F.: Uncovering coordinated networks on social media: Methods and case studies (2020)
  * [31] Pacheco, D., Flammini, A., Menczer, F.: Unveiling coordinated groups behind white helmets disinformation. Companion Proceedings of the Web Conference 2020 (WWW ’20), Association for Computing Machinery pp. 611–616 (2020)
  * [32] Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V., Vanderplas, J., Passos, A., Cournapeau, D., Brucher, M., Perrot, M., Duchesnay, E.: Scikit-learn: Machine learning in python. Journal of Machine Learning Research 12, 2825–2830 (2011)
  * [33] Shahapure, K.R., Nicholas, C.: Cluster quality analysis using silhouette score. In: 2020 IEEE 7th International Conference on Data Science and Advanced Analytics (DSAA). pp. 747–748 (2020)
  * [34] Starbird, K., Wilson, T.: Cross-platform disinformation campaigns: Lessons learned and next steps (2020)
  * [35] Steeg, G., Galstyan, A.: Information transfer in social media. Proceedings of the 21st international conference on World Wide Web p. 509–518 (2012)
  * [36] T, N., N, K., C, C., A, H., A., H.: The danger of misinformation in the COVID-19 crisis. Missouri Medicine 117(6) (2020)
  * [37] Uyheng, J., Carley, K.M.: Characterizing network dynamics of online hate communities around the covid-19 pandemic. Applied Network Science 6(20) (2021)
  * [38] Velmurugan, T., et al.: Efficiency of k-means and k-medoids algorithms for clustering arbitrary data points. Int. J. Computer Technology & Applications 3(5), 1758–1764 (2012)


$\displaystyle=\sum_{\mathbf{s}:s_{1}+\cdots+s_{k+1}=k,\,s_{k+1}>0}(-1)^{1+\tau(\mathbf{s})}\mathfrak{P}^{-s_{1}}\mathbf{Z}\mathfrak{P}^{-s_{2}}\cdots\mathfrak{P}^{-s_{k}}\mathbf{Z}\mathfrak{P}^{-s_{k+1}}{\mathbf{U}}{\boldsymbol{\Lambda}}{\mathbf{U}}^{\top}$
$\displaystyle=\sum_{\mathbf{s}:s_{1}+\cdots+s_{k+1}=k,\,s_{k+1}=1}(-1)^{1+\tau(\mathbf{s})}\mathfrak{P}^{-s_{1}}\mathbf{Z}\mathfrak{P}^{-s_{2}}\cdots\mathfrak{P}^{-s_{k}}\mathbf{Z}{\mathbf{U}}{\mathbf{U}}^{\top}$
$\displaystyle{~{}~{}~{}}+\sum_{\mathbf{s}:s_{1}+\cdots+s_{k+1}=k,\,s_{k+1}\geq
2}(-1)^{1+\tau(\mathbf{s})}\mathfrak{P}^{-s_{1}}\mathbf{Z}\mathfrak{P}^{-s_{2}}\cdots\mathfrak{P}^{-s_{k}}\mathbf{Z}\mathfrak{P}^{1-s_{k+1}}$

The operator norm of $\|\mathcal{S}_{\mathbf{M},k}(\mathbf{Z})\mathbf{M}\|$
could be bounded with

$\|\mathcal{S}_{\mathbf{M},k}(\mathbf{Z})\mathbf{M}\|\leq\binom{2k-1}{k}\frac{\|\mathbf{Z}\|^{k}}{|\lambda_{r}|^{k-1}}\leq\|\mathbf{Z}\|\left(\frac{4\|\mathbf{Z}\|}{|\lambda_{r}|}\right)^{k-1},$

which implies

$\displaystyle\|\sum_{k\geq
2}\mathcal{S}_{\mathbf{M},k}(\mathbf{Z})\mathbf{M}\|\leq\frac{8\|\mathbf{Z}\|^{2}}{|\lambda_{r}|}.$

Specifically, when $k=1$, it is
$\mathcal{S}_{\mathbf{M},1}(\mathbf{Z})\mathbf{M}=\mathbf{U}_{\perp}\mathbf{U}_{\perp}^{\top}\mathbf{Z}\mathbf{U}\mathbf{U}^{\top}$.
Similarly, $\|\sum_{k\geq
2}\mathbf{M}\mathcal{S}_{\mathbf{M},k}(\mathbf{Z})\|\leq\frac{8\|\mathbf{Z}\|^{2}}{|\lambda_{r}|}$
holds. In parallel, Frobenius norm of
$\mathcal{S}_{\mathbf{M},k}(\mathbf{Z})\mathbf{M}$ has

$\|\mathcal{S}_{\mathbf{M},k}(\mathbf{Z})\mathbf{M}\|_{\mathrm{F}}\leq\binom{2k-1}{k}\frac{\|\mathbf{Z}\|^{k-1}}{|\lambda_{r}|^{k-1}}\|\mathbf{Z}\|_{\mathrm{F}}\leq\|\mathbf{Z}\|_{\mathrm{F}}\left(\frac{4\|\mathbf{Z}\|}{|\lambda_{r}|}\right)^{k-1},$
$\displaystyle\|\sum_{k\geq
2}\mathcal{S}_{\mathbf{M},k}(\mathbf{Z})\mathbf{M}\|_{\mathrm{F}}\leq\frac{8\|\mathbf{Z}\|_{\mathrm{F}}\|\mathbf{Z}\|}{|\lambda_{r}|},\quad\|\sum_{k\geq
2}\mathbf{M}\mathcal{S}_{\mathbf{M},k}(\mathbf{Z})\|_{\mathrm{F}}\leq\frac{8\|\mathbf{Z}\|_{\mathrm{F}}\|\mathbf{Z}\|}{|\lambda_{r}|}.$
(31)

Then expand $\operatorname{SVD}_{r}(\hat{\mathbf{M}})-\mathbf{M}$,

$\begin{split}&{~{}~{}~{}~{}}\operatorname{SVD}_{r}(\hat{\mathbf{M}})-\mathbf{M}\\\
&=\hat{\mathbf{U}}\hat{\mathbf{U}}^{\top}(\mathbf{M}+\mathbf{Z})\hat{\mathbf{U}}\hat{\mathbf{U}}^{\top}-\mathbf{M}\\\
&=\hat{\mathbf{U}}\hat{\mathbf{U}}^{\top}(\mathbf{M}+\mathbf{Z})\hat{\mathbf{U}}\hat{\mathbf{U}}^{\top}-\mathbf{U}\mathbf{U}^{\top}\mathbf{M}\mathbf{U}\mathbf{U}^{\top}\\\
&=(\hat{\mathbf{U}}\hat{\mathbf{U}}^{\top}-\mathbf{U}\mathbf{U}^{\top})\mathbf{M}\mathbf{U}\mathbf{U}^{\top}+\hat{\mathbf{U}}\hat{\mathbf{U}}^{\top}\mathbf{M}(\hat{\mathbf{U}}\hat{\mathbf{U}}^{\top}-\mathbf{U}\mathbf{U}^{\top})+\hat{\mathbf{U}}\hat{\mathbf{U}}^{\top}\mathbf{Z}\hat{\mathbf{U}}\hat{\mathbf{U}}^{\top}\\\
&=\sum_{k\geq
2}\mathcal{S}_{\mathbf{M},k}(\mathbf{Z})\mathbf{M}\mathbf{U}\mathbf{U}^{\top}+\hat{\mathbf{U}}\hat{\mathbf{U}}^{\top}\mathbf{M}\sum_{k\geq
2}\mathcal{S}_{\mathbf{M},k}(\mathbf{Z})+\mathbf{U}_{\perp}\mathbf{U}_{\perp}^{\top}\mathbf{Z}\mathbf{U}\mathbf{U}^{\top}\\\
&{~{}~{}~{}}+\hat{\mathbf{U}}\hat{\mathbf{U}}^{\top}\mathbf{U}\mathbf{U}^{\top}\mathbf{Z}\mathbf{U}_{\perp}\mathbf{U}_{\perp}^{\top}+\hat{\mathbf{U}}\hat{\mathbf{U}}^{\top}\mathbf{Z}\hat{\mathbf{U}}\hat{\mathbf{U}}^{\top},\end{split}$

where the last equation follows from Theorem 11 and
$\mathcal{S}_{\mathbf{M},1}(\mathbf{Z})\mathbf{M}=\mathbf{U}_{\perp}\mathbf{U}_{\perp}^{\top}\mathbf{Z}\mathbf{U}\mathbf{U}^{\top}$,
${\mathbf{M}}{\mathcal{S}}_{{\mathbf{M}},1}({\mathbf{Z}})={\mathbf{U}}{\mathbf{U}}^{\top}{\mathbf{Z}}{\mathbf{U}}_{\perp}{\mathbf{U}}_{\perp}^{\top}$.
Then consider the latter three terms of the above equations,

$\displaystyle{~{}~{}~{}}\mathbf{U}_{\perp}\mathbf{U}_{\perp}^{\top}\mathbf{Z}\mathbf{U}\mathbf{U}^{\top}+\hat{\mathbf{U}}\hat{\mathbf{U}}^{\top}\mathbf{U}\mathbf{U}^{\top}\mathbf{Z}\mathbf{U}_{\perp}\mathbf{U}_{\perp}^{\top}+\hat{\mathbf{U}}\hat{\mathbf{U}}^{\top}\mathbf{Z}\hat{\mathbf{U}}\hat{\mathbf{U}}^{\top}$
$\displaystyle={\mathbf{U}}_{\perp}{\mathbf{U}}_{\perp}^{\top}{\mathbf{Z}}{\mathbf{U}}{\mathbf{U}}^{\top}+{\mathbf{U}}{\mathbf{U}}^{\top}{\mathbf{Z}}{\mathbf{U}}_{\perp}{\mathbf{U}}_{\perp}^{\top}+{\mathbf{U}}{\mathbf{U}}^{\top}{\mathbf{Z}}{\mathbf{U}}{\mathbf{U}}^{\top}$
$\displaystyle{~{}~{}~{}}+(\hat{\mathbf{U}}\hat{\mathbf{U}}^{\top}-\mathbf{U}\mathbf{U}^{\top})\mathbf{U}\mathbf{U}^{\top}\mathbf{Z}\mathbf{U}_{\perp}\mathbf{U}_{\perp}^{\top}+(\hat{\mathbf{U}}\hat{\mathbf{U}}^{\top}\mathbf{Z}\hat{\mathbf{U}}\hat{\mathbf{U}}^{\top}-\mathbf{U}\mathbf{U}^{\top}\mathbf{Z}\mathbf{U}\mathbf{U}^{\top})$
$\displaystyle=\mathbf{Z}-\mathbf{U}_{\perp}\mathbf{U}_{\perp}^{\top}\mathbf{Z}\mathbf{U}_{\perp}\mathbf{U}_{\perp}^{\top}$
$\displaystyle{~{}~{}~{}}+(\hat{\mathbf{U}}\hat{\mathbf{U}}^{\top}-\mathbf{U}\mathbf{U}^{\top})\mathbf{U}\mathbf{U}^{\top}\mathbf{Z}\mathbf{U}_{\perp}\mathbf{U}_{\perp}^{\top}+(\hat{\mathbf{U}}\hat{\mathbf{U}}^{\top}\mathbf{Z}\hat{\mathbf{U}}\hat{\mathbf{U}}^{\top}-\mathbf{U}\mathbf{U}^{\top}\mathbf{Z}\mathbf{U}\mathbf{U}^{\top}),$

where the last equation is due to
${\mathbf{U}}{\mathbf{U}}^{\top}+{\mathbf{U}}_{\perp}{\mathbf{U}}_{\perp}^{\top}={\mathbf{I}}$
and
${\mathbf{Z}}=({\mathbf{U}}{\mathbf{U}}^{\top}+{\mathbf{U}}_{\perp}{\mathbf{U}}_{\perp}^{\top}){\mathbf{Z}}({\mathbf{U}}{\mathbf{U}}^{\top}+{\mathbf{U}}_{\perp}{\mathbf{U}}_{\perp}^{\top})$.
Hence, we get the expansion of $\textrm{SVD}_{r}(\hat{{\mathbf{M}}})$,

$\displaystyle{~{}~{}~{}~{}}\operatorname{SVD}_{r}(\hat{\mathbf{M}})-\mathbf{M}$
$\displaystyle=\sum_{k\geq
2}\mathcal{S}_{\mathbf{M},k}(\mathbf{Z})\mathbf{M}\mathbf{U}\mathbf{U}^{\top}+\hat{\mathbf{U}}\hat{\mathbf{U}}^{\top}\mathbf{M}\sum_{k\geq
2}\mathcal{S}_{\mathbf{M},k}(\mathbf{Z})+\mathbf{Z}-\mathbf{U}_{\perp}\mathbf{U}_{\perp}^{\top}\mathbf{Z}\mathbf{U}_{\perp}\mathbf{U}_{\perp}^{\top}$
$\displaystyle{~{}~{}~{}}+(\hat{\mathbf{U}}\hat{\mathbf{U}}^{\top}-\mathbf{U}\mathbf{U}^{\top})\mathbf{U}\mathbf{U}^{\top}\mathbf{Z}\mathbf{U}_{\perp}\mathbf{U}_{\perp}^{\top}+(\hat{\mathbf{U}}\hat{\mathbf{U}}^{\top}\mathbf{Z}\hat{\mathbf{U}}\hat{\mathbf{U}}^{\top}-\mathbf{U}\mathbf{U}^{\top}\mathbf{Z}\mathbf{U}\mathbf{U}^{\top}).$

Take Frobenius norm on each side of the above equation and it leads to

$\begin{split}&{~{}~{}~{}~{}}\|\operatorname{SVD}_{r}(\hat{\mathbf{M}})-\mathbf{M}\|_{\mathrm{F}}\\\
&\leq\underbrace{\|\sum_{k\geq
2}\mathcal{S}_{\mathbf{M},k}(\mathbf{Z})\mathbf{M}\mathbf{U}\mathbf{U}^{\top}\|_{\mathrm{F}}}_{A_{1}}+\underbrace{\|\hat{\mathbf{U}}\hat{\mathbf{U}}^{\top}\mathbf{M}\sum_{k\geq
2}\mathcal{S}_{\mathbf{M},k}(\mathbf{Z})\|_{\mathrm{F}}}_{A_{2}}+\underbrace{\|\mathbf{Z}-\mathbf{U}_{\perp}\mathbf{U}_{\perp}^{\top}\mathbf{Z}\mathbf{U}_{\perp}\mathbf{U}_{\perp}^{\top}\|_{\mathrm{F}}}_{A_{3}}\\\
&{~{}~{}~{}}+\underbrace{\|(\hat{\mathbf{U}}\hat{\mathbf{U}}^{\top}-\mathbf{U}\mathbf{U}^{\top})\mathbf{U}\mathbf{U}^{\top}\mathbf{Z}\mathbf{U}_{\perp}\mathbf{U}_{\perp}^{\top}\|_{\mathrm{F}}}_{A_{4}}+\underbrace{\|\hat{\mathbf{U}}\hat{\mathbf{U}}^{\top}\mathbf{Z}\hat{\mathbf{U}}\hat{\mathbf{U}}^{\top}-\mathbf{U}\mathbf{U}^{\top}\mathbf{Z}\mathbf{U}\mathbf{U}^{\top}\|_{\mathrm{F}}}_{A_{5}}.\end{split}$
(32)

Note that by Equation (31), we have upper bound of $A_{1}$ and $A_{2}$,

$\displaystyle A_{1}\vee A_{2}\leq\|\sum_{k\geq
2}\mathcal{S}_{\mathbf{M},k}(\mathbf{Z})\mathbf{M}\|_{\mathrm{F}}\vee\|\mathbf{M}\sum_{k\geq
2}\mathcal{S}_{\mathbf{M},k}(\mathbf{Z})\|_{\mathrm{F}}\leq\frac{8\|\mathbf{Z}\|_{\mathrm{F}}\|\mathbf{Z}\|}{|\lambda_{r}|}.$

Besides, it has
${\mathbf{Z}}-{\mathbf{U}}_{\perp}{\mathbf{U}}_{\perp}^{\top}{\mathbf{Z}}{\mathbf{U}}_{\perp}{\mathbf{U}}_{\perp}^{\top}={\mathbf{U}}_{\perp}{\mathbf{U}}_{\perp}^{\top}{\mathbf{Z}}{\mathbf{U}}{\mathbf{U}}^{\top}+{\mathbf{U}}{\mathbf{U}}^{\top}{\mathbf{Z}}{\mathbf{U}}_{\perp}{\mathbf{U}}_{\perp}^{\top}+{\mathbf{U}}{\mathbf{U}}^{\top}{\mathbf{Z}}{\mathbf{U}}{\mathbf{U}}^{\top}$
and
$\|{\mathbf{Z}}\|_{\rm{F}}^{2}=\|({\mathbf{U}}{\mathbf{U}}^{\top}+{\mathbf{U}}_{\perp}{\mathbf{U}}_{\perp}^{\top}){\mathbf{Z}}({\mathbf{U}}{\mathbf{U}}^{\top}+{\mathbf{U}}_{\perp}{\mathbf{U}}_{\perp}^{\top})\|_{\rm{F}}^{2}=\|{\mathbf{U}}{\mathbf{U}}^{\top}{\mathbf{Z}}{\mathbf{U}}{\mathbf{U}}^{\top}\|_{\rm{F}}^{2}+\|{\mathbf{U}}_{\perp}{\mathbf{U}}_{\perp}^{\top}{\mathbf{Z}}{\mathbf{U}}{\mathbf{U}}^{\top}\|_{\rm{F}}^{2}+\|{\mathbf{U}}{\mathbf{U}}^{\top}{\mathbf{Z}}{\mathbf{U}}_{\perp}{\mathbf{U}}_{\perp}^{\top}\|_{\rm{F}}^{2}+\|{\mathbf{U}}_{\perp}{\mathbf{U}}_{\perp}^{\top}{\mathbf{Z}}{\mathbf{U}}_{\perp}{\mathbf{U}}_{\perp}^{\top}\|_{\rm{F}}^{2}$
and it leads to

$\displaystyle
A_{3}^{2}=\|{\mathbf{U}}{\mathbf{U}}^{\top}{\mathbf{Z}}{\mathbf{U}}{\mathbf{U}}^{\top}\|_{\rm{F}}^{2}+\|{\mathbf{U}}_{\perp}{\mathbf{U}}_{\perp}^{\top}{\mathbf{Z}}{\mathbf{U}}{\mathbf{U}}^{\top}\|_{\rm{F}}^{2}+\|{\mathbf{U}}{\mathbf{U}}^{\top}{\mathbf{Z}}{\mathbf{U}}_{\perp}{\mathbf{U}}_{\perp}^{\top}\|_{\rm{F}}^{2}\leq\|{\mathbf{Z}}\|_{\rm{F}}^{2},$

which shows $A_{3}\leq\|{\mathbf{Z}}\|_{\rm{F}}$. With Equation (30), $A_{4}$
could be upper bounded by

$\displaystyle
A_{4}\leq\|\hat{{\mathbf{U}}}\hat{{\mathbf{U}}}^{\top}-{\mathbf{U}}{\mathbf{U}}^{\top}\|_{\rm{F}}\|{\mathbf{Z}}\|\leq\frac{8\|\mathbf{Z}\|_{\mathrm{F}}\|\mathbf{Z}\|}{|\lambda_{r}|}.$

Note that with triangular inequality and in a similar fashion, it has

$\displaystyle
A_{5}\leq\|\hat{{\mathbf{U}}}\hat{{\mathbf{U}}}^{\top}{\mathbf{Z}}(\hat{{\mathbf{U}}}\hat{{\mathbf{U}}}^{\top}-{\mathbf{U}}{\mathbf{U}}^{\top})\|_{\rm{F}}+\|(\hat{{\mathbf{U}}}\hat{{\mathbf{U}}}^{\top}-{\mathbf{U}}{\mathbf{U}}^{\top}){\mathbf{Z}}{\mathbf{U}}{\mathbf{U}}^{\top}\|_{\rm{F}}\leq\frac{16\|\mathbf{Z}\|_{\mathrm{F}}\|\mathbf{Z}\|}{|\lambda_{r}|}.$

Thus, Equation (32) could be further upper bounded by

$\displaystyle\|\operatorname{SVD}_{r}(\hat{\mathbf{M}})-\mathbf{M}\|_{\mathrm{F}}\leq\|{\mathbf{Z}}\|_{\rm{F}}+40\frac{\|\mathbf{Z}\|_{\mathrm{F}}\|\mathbf{Z}\|}{|\lambda_{r}|}=\|\hat{{\mathbf{M}}}-{\mathbf{M}}\|_{\rm{F}}+40\frac{\|\hat{{\mathbf{M}}}-{\mathbf{M}}\|_{\rm{F}}\|\hat{{\mathbf{M}}}-{\mathbf{M}}\|}{|\lambda_{r}|}.$

Likewise, one has the bound of the operator norm

$\|\operatorname{SVD}_{r}(\hat{\mathbf{M}})-\mathbf{M}^{*}\|\leq\|\hat{{\mathbf{M}}}-{\mathbf{M}}\|+40\frac{\|\hat{{\mathbf{M}}}-{\mathbf{M}}\|^{2}}{|\lambda_{r}|}.$

The proof completes. ∎

Then we are ready to prove Lemma 14, the assymetric case.

###### Proof of Lemma 14.

To apply Lemma 18, first construct symmetrization of $\mathbf{M}$ and
$\hat{\mathbf{M}}$,

$\mathbf{Y}:=\left(\begin{matrix}0&\mathbf{M}\\\
\mathbf{M}^{\top}&0\end{matrix}\right)\in{\mathbb{R}}^{(d_{1}+d_{2})\times(d_{1}+d_{2})},\,\hat{\mathbf{Y}}:=\left(\begin{matrix}0&\hat{\mathbf{M}}\\\
\hat{\mathbf{M}}^{\top}&0\end{matrix}\right)\in{\mathbb{R}}^{(d_{1}+d_{2})\times(d_{1}+d_{2})}.$

Denote the perturbation matrix as $\mathbf{Z}:=\hat{\mathbf{M}}-\mathbf{M}$
and similarly define

$\hat{\mathbf{Z}}:=\left(\begin{matrix}0&\mathbf{Z}\\\
\mathbf{Z}^{\top}&0\end{matrix}\right)=\left(\begin{matrix}0&\hat{\mathbf{M}}-\mathbf{M}\\\
\hat{\mathbf{M}}^{\top}-\mathbf{M}^{\top}&0\end{matrix}\right).$

Note that
$\operatorname{rank}(\mathbf{Y})=2\operatorname{rank}({\mathbf{M}})=2r$. First
analyze SVD of matrix ${\mathbf{Y}}$ and $\hat{{\mathbf{Y}}}$. Notice that

$\frac{1}{\sqrt{2}}\left(\begin{matrix}\mathbf{U}&\mathbf{U}\\\
\mathbf{V}&-\mathbf{V}\end{matrix}\right)\in\mathbb{R}^{2d\times 2r}$

contains orthonormal columns. Besides, it has

$\displaystyle\frac{1}{\sqrt{2}}\left(\begin{matrix}\mathbf{U}&\mathbf{U}\\\
\mathbf{V}&-\mathbf{V}\end{matrix}\right)\left(\begin{matrix}{\boldsymbol{\Sigma}}&0\\\
0&-{\boldsymbol{\Sigma}}\end{matrix}\right)\frac{1}{\sqrt{2}}\left(\begin{matrix}\mathbf{U}&\mathbf{U}\\\
\mathbf{V}&-\mathbf{V}\end{matrix}\right)^{\top}=\left(\begin{matrix}0&{\mathbf{U}}{\boldsymbol{\Sigma}}{\mathbf{V}}^{\top}\\\
{\mathbf{V}}{\boldsymbol{\Sigma}}{\mathbf{U}}^{\top}&0\end{matrix}\right)$
$\displaystyle=\left(\begin{matrix}0&{\mathbf{M}}\\\
{\mathbf{M}}^{\top}&0\end{matrix}\right)={\mathbf{Y}},$

by which we obtain SVD of ${\mathbf{Y}}$. Without loss of generality, suppose
$d_{1}\geq d_{2}$ and
$\hat{{\mathbf{M}}}=\tilde{{\mathbf{U}}}\tilde{{\boldsymbol{\Sigma}}}\tilde{{\mathbf{V}}}^{\top}$
is full SVD of $\hat{{\mathbf{M}}}$, with
$\tilde{{\mathbf{U}}}\in{\mathbb{R}}^{d_{1}\times d_{2}}$,
$\tilde{\boldsymbol{\Sigma}}=\text{diag}(\tilde{\sigma}_{1},\dots,\tilde{\sigma}_{d_{2}})\in{\mathbb{R}}^{d_{2}\times
d_{2}}$, $\tilde{{\mathbf{V}}}\in{\mathbb{R}}^{d_{2}\times d_{2}}$, where
$\tilde{\sigma}_{1}\geq\cdots\geq\tilde{\sigma}_{d_{2}}\geq 0$. Thus, leading
$r$ components of $\hat{{\mathbf{M}}}$ is
$\operatorname{SVD}_{r}(\hat{{\mathbf{M}}})=\hat{{\mathbf{U}}}\hat{{\boldsymbol{\Sigma}}}\hat{{\mathbf{V}}}^{\top}$,
where $\hat{{\mathbf{U}}}$ and $\hat{{\mathbf{V}}}$ are first $r$ columns of
full matrix $\tilde{{\mathbf{U}}}$ and $\tilde{{\mathbf{V}}}$ respectively and
$\hat{{\boldsymbol{\Sigma}}}=\text{diag}(\tilde{\sigma}_{1},\dots,\tilde{\sigma}_{r})$.

Notice that since $\hat{{\mathbf{Y}}}$ is symmetrization for
$\hat{{\mathbf{M}}}$, its full SVD is

$\displaystyle\hat{{\mathbf{Y}}}=\frac{1}{\sqrt{2}}\left(\begin{matrix}\tilde{{\mathbf{U}}}&\tilde{{\mathbf{U}}}\\\
\tilde{{\mathbf{V}}}&-\tilde{{\mathbf{V}}}\end{matrix}\right)\left(\begin{matrix}\tilde{{\boldsymbol{\Sigma}}}&0\\\
0&-\tilde{{\boldsymbol{\Sigma}}}\end{matrix}\right)\frac{1}{\sqrt{2}}\left(\begin{matrix}\tilde{{\mathbf{U}}}&\tilde{{\mathbf{U}}}\\\
\tilde{{\mathbf{V}}}&-\tilde{{\mathbf{V}}}\end{matrix}\right)^{\top},$ (33)

which has eigenvalues
$\tilde{\sigma}_{1},-\tilde{\sigma}_{1},\dots,\tilde{\sigma}_{d_{2}},-\tilde{\sigma}_{d_{2}}$.
Thus, largest $2r$ eigenvalues of $\hat{{\mathbf{Y}}}$ in absolute are
$\tilde{\sigma}_{1},-\tilde{\sigma}_{1},\dots,\tilde{\sigma}_{r},-\tilde{\sigma}_{r}$.
Thus, since $\hat{{\mathbf{U}}}$, $\hat{{\mathbf{V}}}$ are first $r$ columns
of $\tilde{\mathbf{U}}$, $\tilde{\mathbf{V}}$ respectively, Equation (33)
infers

$\displaystyle\frac{1}{\sqrt{2}}\left(\begin{matrix}\hat{\mathbf{U}}&\hat{\mathbf{U}}\\\
\hat{\mathbf{V}}&-\hat{\mathbf{V}}\end{matrix}\right)^{\top}\hat{\mathbf{Y}}\frac{1}{\sqrt{2}}\left(\begin{matrix}\hat{\mathbf{U}}&\hat{\mathbf{U}}\\\
\hat{\mathbf{V}}&-\hat{\mathbf{V}}\end{matrix}\right)=\left(\begin{matrix}\hat{\boldsymbol{\Sigma}}&0\\\
0&-\hat{\boldsymbol{\Sigma}}\end{matrix}\right),$

which means $\operatorname{SVD}_{2r}(\hat{{\mathbf{Y}}})$ is

$\displaystyle\operatorname{SVD}_{2r}(\hat{{\mathbf{Y}}})=\frac{1}{\sqrt{2}}\left(\begin{matrix}\hat{\mathbf{U}}&\hat{\mathbf{U}}\\\
\hat{\mathbf{V}}&-\hat{\mathbf{V}}\end{matrix}\right)\left(\begin{matrix}\hat{\boldsymbol{\Sigma}}&0\\\
0&-\hat{\boldsymbol{\Sigma}}\end{matrix}\right)\frac{1}{\sqrt{2}}\left(\begin{matrix}\hat{\mathbf{U}}&\hat{\mathbf{U}}\\\
\hat{\mathbf{V}}&-\hat{\mathbf{V}}\end{matrix}\right)^{\top}$
$\displaystyle=\left(\begin{matrix}0&\hat{\mathbf{U}}\hat{\boldsymbol{\Sigma}}\hat{\mathbf{V}}^{\top}\\\
\hat{\mathbf{V}}\hat{\boldsymbol{\Sigma}}\hat{\mathbf{U}}^{\top}&0\end{matrix}\right)$
$\displaystyle=\left(\begin{matrix}0&\operatorname{SVD}_{r}(\hat{{\mathbf{M}}})\\\
\operatorname{SVD}_{r}(\hat{{\mathbf{M}}})^{\top}&0\end{matrix}\right),$

and
$\frac{1}{\sqrt{2}}\left(\begin{matrix}\hat{\mathbf{U}}&\hat{\mathbf{U}}\\\
\hat{\mathbf{V}}&-\hat{\mathbf{V}}\end{matrix}\right)$ contains leadning $2r$
eigenvectors of $\hat{{\mathbf{Y}}}$. Thus, we have

$\displaystyle\operatorname{SVD}_{2r}(\hat{{\mathbf{Y}}})-{\mathbf{Y}}=\left(\begin{matrix}0&\operatorname{SVD}_{r}(\hat{{\mathbf{M}}})-{\mathbf{M}}\\\
\operatorname{SVD}_{r}(\hat{{\mathbf{M}}})^{\top}-{\mathbf{M}}^{\top}&0\end{matrix}\right).$

It infers

$\displaystyle\|\operatorname{SVD}_{2r}(\hat{{\mathbf{Y}}})-{\mathbf{Y}}\|_{\rm{F}}=\sqrt{2}\|\operatorname{SVD}_{r}(\hat{{\mathbf{M}}})-{\mathbf{M}}\|_{\rm{F}}.$
(34)

Then apply Lemma 18 to the rank $2r$ symmetric matrix ${\mathbf{Y}}$ and the
symmetric perturbed matrix $\hat{{\mathbf{Y}}}$,

$\|\operatorname{SVD}_{2r}(\hat{\mathbf{Y}})-\mathbf{Y}^{*}\|_{\rm{F}}\leq\|\hat{{\mathbf{Y}}}-{\mathbf{Y}}\|_{\rm{F}}+40\frac{\|\hat{{\mathbf{Y}}}-{\mathbf{Y}}\|_{\rm{F}}\|\hat{{\mathbf{Y}}}-{\mathbf{Y}}\|}{\sigma_{r}},$
(35)

which uses $|\lambda_{2r}({\mathbf{Y}})|=\sigma_{r}$. Note that definition of
${\mathbf{Y}}$ and $\hat{{\mathbf{Y}}}$ implies
$\|\hat{{\mathbf{Y}}}-{\mathbf{Y}}\|_{\rm{F}}=\sqrt{2}\|\hat{{\mathbf{M}}}-{\mathbf{M}}\|_{\rm{F}}$
and $\|\hat{{\mathbf{Y}}}-{\mathbf{Y}}\|=\|\hat{{\mathbf{M}}}-{\mathbf{M}}\|$,
respectively. Then, Equation (34), Equation (35) infer,

$\displaystyle\|\operatorname{SVD}_{r}(\hat{{\mathbf{M}}})-{\mathbf{M}}\|_{\rm{F}}\leq\|\hat{{\mathbf{M}}}-{\mathbf{M}}\|_{\rm{F}}+40\frac{\|\hat{{\mathbf{M}}}-{\mathbf{M}}\|_{\rm{F}}\|\hat{{\mathbf{M}}}-{\mathbf{M}}\|}{\sigma_{r}}.$

Notice that proof of operator norm version
$\|\operatorname{SVD}_{r}(\hat{\mathbf{M}})-\mathbf{M}\|\leq\|\hat{{\mathbf{M}}}-{\mathbf{M}}\|+40\frac{\|\hat{{\mathbf{M}}}-{\mathbf{M}}\|^{2}}{\sigma_{r}}$
is similar to the Frobinius norm case and hence it is skipped.

Apply the perturbated eigenvector results of Lemma 18 to the symmetric rank
$2r$ matrix ${\mathbf{Y}}$ and symmetric perturbed matrix
$\hat{{\mathbf{Y}}}$,

$\bigg{\|}\frac{1}{\sqrt{2}}\left(\begin{matrix}\hat{\mathbf{U}}&\hat{\mathbf{U}}\\\
\hat{\mathbf{V}}&-\hat{\mathbf{V}}\end{matrix}\right)\frac{1}{\sqrt{2}}\left(\begin{matrix}\hat{\mathbf{U}}&\hat{\mathbf{U}}\\\
\hat{\mathbf{V}}&-\hat{\mathbf{V}}\end{matrix}\right)^{\top}-\frac{1}{\sqrt{2}}\left(\begin{matrix}\mathbf{U}&\mathbf{U}\\\
\mathbf{V}&-\mathbf{V}\end{matrix}\right)\frac{1}{\sqrt{2}}\left(\begin{matrix}\mathbf{U}&\mathbf{U}\\\
\mathbf{V}&-\mathbf{V}\end{matrix}\right)^{\top}\bigg{\|}\leq\frac{8\|\hat{{\mathbf{Y}}}-{\mathbf{Y}}\|}{\sigma_{r}},$

which could be simplified as

$\displaystyle\|\left(\begin{matrix}\hat{{\mathbf{U}}}\hat{{\mathbf{U}}}^{\top}&0\\\
0&\hat{{\mathbf{V}}}\hat{{\mathbf{V}}}^{\top}\end{matrix}\right)-\left(\begin{matrix}{\mathbf{U}}{\mathbf{U}}^{\top}&0\\\
0&{\mathbf{V}}{\mathbf{V}}^{\top}\end{matrix}\right)\|\leq\frac{8\|\hat{{\mathbf{Y}}}-{\mathbf{Y}}\|}{\sigma_{r}}.$

Then by
$\|\hat{{\mathbf{Y}}}-{\mathbf{Y}}\|=\|\hat{{\mathbf{M}}}-{\mathbf{M}}\|$ and
block matrix properties, it arrives at

$\|\hat{\mathbf{U}}\hat{\mathbf{U}}^{\top}-\mathbf{U}\mathbf{U}^{\top}\|\leq\frac{8}{\sigma_{r}}\|\hat{\mathbf{M}}-\mathbf{M}\|,\quad\|\hat{\mathbf{V}}\hat{\mathbf{V}}^{\top}-\mathbf{U}\mathbf{U}^{\top}\|\leq\frac{8}{\sigma_{r}}\|\hat{\mathbf{M}}-\mathbf{M}\|.$

∎

##  Appendix H Proof of Matrix Recovery Empirical Process Proposition 3

###### Proof.

The proof follows from Theorem 14. Recall
${\mathbb{M}}_{r}:=\\{{\mathbf{M}}\in{\mathbb{R}}^{d_{1}\times
d_{2}}:\text{rank}({\mathbf{M}})\leq r\\}$ is the set of matrices with rank
bounded by $r$. Consider

$\displaystyle~{}~{}~{}~{}Z:=\sup_{\begin{subarray}{c}\Delta{\mathbf{M}}\in{\mathbb{M}}_{r}\\\
{\mathbf{M}}\in{\mathbb{R}}^{d_{1}\times
d_{2}}\end{subarray}}\left|f({\mathbf{M}}+\Delta{\mathbf{M}})-f({\mathbf{M}})-{\mathbb{E}}(f({\mathbf{M}}+\Delta{\mathbf{M}})-f({\mathbf{M}}))\right|\cdot\|\Delta{\mathbf{M}}\|_{\rm{F}}^{-1}.$

Note that
$f({\mathbf{M}})=\sum_{i=1}^{n}\rho(\langle{\mathbf{X}}_{i},{\mathbf{M}}\rangle-
Y_{i})$ and then we have

$\displaystyle{\mathbb{E}}Z$ $\displaystyle\leq
2{\mathbb{E}}\sup_{\begin{subarray}{c}\Delta{\mathbf{M}}\in{\mathbb{M}}_{r}\\\
{\mathbf{M}}\in{\mathbb{R}}^{d_{1}\times
d_{2}}\end{subarray}}\left|\sum_{i=1}^{n}\widetilde{\epsilon}_{i}\cdot\big{(}\rho(\langle{\mathbf{X}}_{i},{\mathbf{M}}+\Delta{\mathbf{M}}\rangle-
Y_{i})-\rho(\langle{\mathbf{X}}_{i},{\mathbf{M}}\rangle-
Y_{i})\big{)}\right|\cdot\|\Delta{\mathbf{M}}\|_{\rm{F}}^{-1}$
$\displaystyle\leq
4\tilde{L}\cdot{\mathbb{E}}\sup_{{\mathbf{M}}\in{\mathbb{M}}_{r}}\left|\sum_{i=1}^{n}\widetilde{\epsilon}_{i}\cdot\langle{\mathbf{X}}_{i},\Delta{\mathbf{M}}\rangle\right|\cdot\|\Delta{\mathbf{M}}\|_{\rm{F}}^{-1}$
$\displaystyle\leq
4\tilde{L}\cdot{\mathbb{E}}\|\sum_{i=1}^{n}\widetilde{\epsilon}_{i}{\mathbf{X}}_{i}\|_{\mathrm{F,r}}\leq
4\tilde{L}\cdot\sqrt{r}{\mathbb{E}}\|\sum_{i=1}^{n}\widetilde{\epsilon}_{i}{\mathbf{X}}_{i}\|,$

where $\\{\widetilde{\epsilon}_{i}\\}_{i=1}^{n}$ is Rademacher sequence
independent of ${\mathbf{X}}_{1},\ldots,{\mathbf{X}}_{n}$. The first
inequality is from Theorem 12 and the second inequality is from Theorem 13.
Notice that
$\text{vec}\left(\sum_{i=1}^{n}\widetilde{\epsilon}_{i}{\mathbf{X}}_{i}\right)\sim
N(\boldsymbol{0},\sum_{i=1}^{n}{\boldsymbol{\Sigma}}_{i})$ and
$\|\sum_{i=1}^{n}{\boldsymbol{\Sigma}}_{i}\|\leq nC_{{\tiny u}}$. Lemma 15
implies
${\mathbb{E}}\|\sum_{i=1}^{n}\widetilde{\epsilon}_{i}{\mathbf{X}}_{i}\|\leq
C_{1}\sqrt{nd_{1}C_{{\tiny u}}}$ for some absolute constant $C_{1}>0$. Thus we
have

${\mathbb{E}}Z\leq C_{1}\tilde{L}\sqrt{nd_{1}rC_{{\tiny u}}}.$

For simplicity, denote
$f_{i}({\mathbf{M}},\Delta{\mathbf{M}}):=|\rho(Y_{i}-\langle\mathbf{X}_{i},{\mathbf{M}}+\Delta{\mathbf{M}}\rangle)-\rho(Y_{i}-\langle\mathbf{X}_{i},{\mathbf{M}}\rangle)|\cdot\|\Delta{\mathbf{M}}\|_{\rm{F}}^{-1}$.
Then we have

$\displaystyle{~{}~{}~{}}\|\max_{i=1,\ldots,n}\sup_{\begin{subarray}{c}\Delta{\mathbf{M}}\in{\mathbb{M}}_{r}\\\
{\mathbf{M}}\in{\mathbb{R}}^{d_{1}\times
d_{2}}\end{subarray}}|f_{i}({\mathbf{M}},\Delta{\mathbf{M}})-{\mathbb{E}}f_{i}({\mathbf{M}},\Delta{\mathbf{M}})|\|_{\Psi_{1}}$
$\displaystyle\leq 2\log
n\max_{i=1,\ldots,n}\|\sup_{\begin{subarray}{c}\Delta{\mathbf{M}}\in{\mathbb{M}}_{r}\\\
{\mathbf{M}}\in{\mathbb{R}}^{d_{1}\times
d_{2}}\end{subarray}}|f_{i}({\mathbf{M}}+\Delta{\mathbf{M}})|\|_{\Psi_{1}}+2\log
n\max_{i=1,\ldots,n}{\mathbb{E}}\sup_{\begin{subarray}{c}\Delta{\mathbf{M}}\in{\mathbb{M}}_{r}\\\
{\mathbf{M}}\in{\mathbb{R}}^{d_{1}\times
d_{2}}\end{subarray}}|f_{i}({\mathbf{M}}+\Delta{\mathbf{M}})|,$

which uses inequality for maximum of sub-exponential variables. Moreover, for
each $i=1,\dots,n$, it has

$\displaystyle~{}~{}~{}~{}\|\sup_{\begin{subarray}{c}\Delta{\mathbf{M}}\in{\mathbb{M}}_{r}\\\
{\mathbf{M}}\in{\mathbb{R}}^{d_{1}\times
d_{2}}\end{subarray}}|f_{i}({\mathbf{M}}+\Delta{\mathbf{M}})|\|_{\Psi_{1}}$
$\displaystyle=\|\sup_{\begin{subarray}{c}\Delta{\mathbf{M}}\in{\mathbb{M}}_{r}\\\
{\mathbf{M}}\in{\mathbb{R}}^{d_{1}\times
d_{2}}\end{subarray}}|\rho(Y_{i}-\langle\mathbf{X}_{i},{\mathbf{M}}+\Delta{\mathbf{M}}\rangle)-\rho(Y_{i}-\langle\mathbf{X}_{i},\mathbf{M}\rangle)|\cdot\|\Delta{\mathbf{M}}\|_{\rm{F}}^{-1}\|_{\Psi_{1}}$
$\displaystyle\leq\tilde{L}\|\sup_{\Delta{\mathbf{M}}\in{\mathbb{M}}_{r}}|\langle\mathbf{X}_{i},\Delta{\mathbf{M}}\rangle|\cdot\|\Delta{\mathbf{M}}\|_{\rm{F}}^{-1}\|_{\Psi_{1}}$
$\displaystyle\leq\tilde{L}\|\|{\mathbf{X}}_{i}\|_{\mathrm{F,r}}\|_{\Psi_{1}}\leq\tilde{L}\sqrt{r}\|\|{\mathbf{X}}_{i}\|\|_{\Psi_{1}}\leq
C_{2}\tilde{L}\sqrt{d_{1}rC_{{\tiny u}}},$

for some absolute constant $C_{2}>0$ and the last line is from definition of
partial Frobenius norm Lemma 12 and random multivariate Gaussian matrix norm
Lemma 15. Similarly, we have

$\displaystyle{\mathbb{E}}\sup_{\begin{subarray}{c}\Delta{\mathbf{M}}\in{\mathbb{M}}_{r}\\\
{\mathbf{M}}\in{\mathbb{R}}^{d_{1}\times
d_{2}}\end{subarray}}|f_{i}({\mathbf{M}})|$
$\displaystyle={\mathbb{E}}\sup_{\begin{subarray}{c}\Delta{\mathbf{M}}\in{\mathbb{M}}_{r}\\\
{\mathbf{M}}\in{\mathbb{R}}^{d_{1}\times
d_{2}}\end{subarray}}|\rho(Y_{i}-\langle\mathbf{X}_{i},{\mathbf{M}}+\Delta{\mathbf{M}}\rangle)-\rho(Y_{i}-\langle\mathbf{X}_{i},\mathbf{M}\rangle)|\cdot\|\Delta{\mathbf{M}}\|_{\rm{F}}^{-1}$
$\displaystyle\leq\tilde{L}\cdot{\mathbb{E}}\|{\mathbf{X}}_{i}\|_{\mathrm{F,r}}\leq
C_{3}\tilde{L}\sqrt{d_{1}rC_{{\tiny u}}}.$

Combine the above three equations and then it has

$\displaystyle\|\max_{i=1,\ldots,n}\sup_{{\mathbf{M}}\in{\mathbb{M}}_{r}}|f_{i}({\mathbf{M}})-{\mathbb{E}}f_{i}({\mathbf{M}})|\|_{\Psi_{1}}\leq
C_{4}\tilde{L}\sqrt{d_{1}rC_{{\tiny u}}}\log n.$

Also, note that $\langle{\mathbf{X}}_{i},\Delta{\mathbf{M}}\rangle\sim
N(0,\text{vec}(\Delta{\mathbf{M}})^{\top}{\boldsymbol{\Sigma}}_{i}\text{vec}(\Delta{\mathbf{M}}))$
and
$\text{vec}({\mathbf{M}}-{\mathbf{M}}^{*})^{\top}{\boldsymbol{\Sigma}}_{i}\text{vec}({\mathbf{M}}-{\mathbf{M}}^{*})\leq
C_{{\tiny u}}\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}^{2}$. Then we have

$\displaystyle{~{}~{}~{}~{}}\mathbb{E}\big{[}\big{(}\rho(Y_{i}-\langle\mathbf{X}_{i},{\mathbf{M}}+\Delta{\mathbf{M}}\rangle)-\rho(Y_{i}-\langle\mathbf{X}_{i},\mathbf{M}\rangle)\big{)}^{2}\big{]}/\|\Delta{\mathbf{M}}\|_{\rm{F}}^{2}$
$\displaystyle\leq\tilde{L}^{2}\mathbb{E}\langle\mathbf{X}_{i},\Delta{\mathbf{M}}\rangle^{2}/\|\Delta{\mathbf{M}}\|_{\rm{F}}^{2}$
$\displaystyle\leq C_{{\tiny u}}\tilde{L}^{2}.$

Invoke Theorem 14 and Remark 2, and take $\alpha=1$, $\eta=1$, $\delta=0.5$
and there exists some constant $C>0$, such that

$\displaystyle\mathbb{P}(Z$ $\displaystyle\geq C_{2}\tilde{L}\sqrt{C_{{\tiny
u}}nd_{1}r}+t)\leq\exp\left(-\frac{t^{2}}{3nC_{{\tiny
u}}\tilde{L}^{2}}\right)+3\exp\left(-\frac{t}{C_{5}\tilde{L}\sqrt{C_{{\tiny
u}}d_{1}r}\log n}\right)$

holds for any $t>0$. Take $t=C\sqrt{nd_{1}rC_{{\tiny u}}}\tilde{L}$ and then
we have

$\mathbb{P}(Z\geq C\tilde{L}\sqrt{nd_{1}rC_{{\tiny
u}}})\leq\exp\left(-\frac{C^{2}d_{1}r}{3}\right)+3\exp\left(-\frac{\sqrt{n}}{\log
n}\right),$

which completes the proof. ∎

######  Theorem 12 (Symmetrization of Expectations, [Van Der Vaart et al.,
1996]).

Consider $\mathbf{X}_{1},\mathbf{X}_{2},\cdots,\mathbf{X}_{n}$ independent
matrices in $\chi$ and let $\mathcal{F}$ be a class of real-valued functions
on $\chi$. Let $\tilde{\varepsilon}_{1},\cdots,\tilde{\varepsilon}_{n}$ be a
Rademacher sequence independent of
$\mathbf{X}_{1},\mathbf{X}_{2},\cdots,\mathbf{X}_{n}$, then

$\mathbb{E}\big{[}\sup_{f\in\mathcal{F}}\big{|}\sum_{i=1}^{n}(f(\mathbf{X}_{i})-\mathbb{E}f(\mathbf{X}_{i}))\big{|}\big{]}\leq
2\mathbb{E}\big{[}\sup_{f\in\mathcal{F}}\big{|}\sum_{i=1}^{n}\tilde{\varepsilon}_{i}f(\mathbf{X}_{i})\big{|}\big{]}$
(36)

######  Theorem 13 (Contraction Theorem, [Ludoux and Talagrand, 1991]).

Consider the non-random elements $x_{1},\ldots,x_{n}$ of $\chi$. Let
$\mathcal{F}$ be a class of real-valued functions on $\chi$. Consider the
Lipschitz continuous functions $\rho_{i}:\mathbb{R}\rightarrow\mathbb{R}$ with
Lipschitz constant $L$, i.e.

$\left|\rho_{i}(\mu)-\rho_{i}(\tilde{\mu})\right|\leq
L|\mu-\tilde{\mu}|,\text{ for all }\mu,\tilde{\mu}\in\mathbb{R}$

Let $\tilde{\varepsilon}_{1},\ldots,\tilde{\varepsilon}_{n}$ be a Rademacher
sequence . Then for any function $f^{*}:\chi\rightarrow\mathbb{R}$, we have

$\mathbb{E}\left[\sup_{f\in\mathcal{F}}\left|\sum_{i=1}^{n}\tilde{\varepsilon}_{i}\left\\{\rho_{i}\left(f\left(x_{i}\right)\right)-\rho_{i}\left(f^{*}\left(x_{i}\right)\right)\right\\}\right|\right]\leq
2\mathbb{E}\left[L\sup_{f\in\mathcal{F}}\mid\sum_{i=1}^{n}\tilde{\varepsilon}_{i}\left(f\left(x_{i}\right)-f^{*}\left(x_{i}\right)\right)\mid\right]$
(37)

######  Theorem 14 (Tail inequality for suprema of empirical process
[Adamczak, 2008]).

Let $\mathbf{X}_{1},\ldots,\mathbf{X}_{n}$ be independent random variables
with values in a measurable space $(\mathcal{S},\mathcal{B})$ and let
$\mathcal{F}$ be a countable class of measurable functions
$f:\mathcal{S}\rightarrow\mathbb{R}$. Assume that for every $f\in\mathcal{F}$
and every $i,\mathbb{E}f\left(\mathbf{X}_{i}\right)=0$ and for some
$\alpha\in(0,1]$ and all
$i,\left\|\sup_{\mathcal{F}}\left|f\left(\mathbf{X}_{i}\right)\right|\right\|_{\Psi_{\alpha}}<\infty.$
Let

$Z=\sup_{f\in\mathcal{F}}\left|\sum_{i=1}^{n}f\left(\mathbf{X}_{i}\right)\right|$

Define moreover

$\sigma^{2}=\sup_{f\in\mathcal{F}}\sum_{i=1}^{n}\mathbb{E}f\left(\mathbf{X}_{i}\right)^{2}$

Then, for all $0<\eta<1$ and $\delta>0$, there exists a constant
$C=C(\alpha,\eta,\delta)$, such that for all $t\geq 0$

$\begin{split}\mathbb{P}(Z&\geq(1+\eta)\mathbb{E}Z+t)\\\
&\leq\exp\left(-\frac{t^{2}}{2(1+\delta)\sigma^{2}}\right)+3\exp\left(-\left(\frac{t}{C\left\|\max_{i}\sup_{f\in\mathcal{F}}\left|f\left(\mathbf{X}_{i}\right)\right|\right\|_{\Psi_{\alpha}}}\right)^{\alpha}\right)\end{split}$

and

$\displaystyle\mathbb{P}(Z$ $\displaystyle\leq(1-\eta)\mathbb{E}Z-t)$
$\displaystyle\leq\exp\left(-\frac{t^{2}}{2(1+\delta)\sigma^{2}}\right)+3\exp\left(-\left(\frac{t}{C\left\|\max_{i}\sup_{f\in\mathcal{F}}\left|f\left(\mathbf{X}_{i}\right)\right|\right\|_{\Psi_{\alpha}}}\right)^{\alpha}\right)$

######  Remark 2.

Notice that here we require $\mathbb{E}f(\mathbf{X}_{i})=0$ and when
$\mathbb{E}f(\mathbf{X}_{i})\neq 0$, $\mathbf{Z}$ should be

$Z=\sup_{f\in\mathcal{F}}\left|\sum_{i=1}^{n}f\left(\mathbf{X}_{i}\right)-\mathbb{E}f(\mathbf{X}_{i})\right|,$

and tail inequality of $Z$ would be

$\begin{split}\mathbb{P}(Z&\geq(1+\eta)\mathbb{E}Z+t)\\\
&\leq\exp\left(-\frac{t^{2}}{2(1+\delta)\sigma^{2}}\right)+3\exp\left(-\left(\frac{t}{C\left\|\max_{i}\sup_{f\in\mathcal{F}}\left|f\left(\mathbf{X}_{i}\right)-{\mathbb{E}}f({\mathbf{X}}_{i})\right|\right\|_{\Psi_{\alpha}}}\right)^{\alpha}\right)\end{split}$

##  Appendix I Proof of Outlier Case

### Proof of Theorem 7

We only need to prove the following two-phase regularity properties, with
which we could obtain the convergence dynamics similarly to Section B.

######  Lemma 19.

Suppose Assumptions 1 holds and 2 holds for inliers. There exist absolute
constants $C_{1},C_{2},C_{3},c_{0}>0$ such that if $n\geq C_{1}C_{{\tiny
u}}C_{{\tiny l}}^{-1}\tilde{s}\log(2d/\tilde{s})$ and
$\epsilon\leq\frac{\sqrt{C_{{\tiny l}}}}{4\sqrt{C_{{\tiny l}}}+\sqrt{C_{{\tiny
u}}}}$, then with probability over
$1-2\exp\big{(}-c_{0}\tilde{s}\log\big{(}2d/\tilde{s})\big{)}-3\exp\big{(}-((1-\epsilon)n\log(2d/\tilde{s}))^{1/2}\log^{-1}(1-\epsilon)n\big{)}$,
we have

  1. (1)

for all
${\boldsymbol{\beta}}\in\left\\{{\boldsymbol{\beta}}\in{\mathbb{R}}^{d}:\;\|{\boldsymbol{\beta}}-{\boldsymbol{\beta}}^{*}\|_{2}\geq
8C_{{\tiny l}}^{-1/2}\gamma,\
|\text{supp}({\boldsymbol{\beta}})|\leq\tilde{s}\right\\}$ and for all sub-
gradient ${\mathbf{G}}\in\partial f({\boldsymbol{\beta}})$,

$\displaystyle
f({\boldsymbol{\beta}})-f({\boldsymbol{\beta}}^{*})\geq\frac{n}{5}C_{{\tiny
l}}^{1/2}\|{\boldsymbol{\beta}}-{\boldsymbol{\beta}}^{*}\|_{2}\quad{\rm
and}\quad\|{\mathcal{P}}_{\Omega\cup\Pi\cup\Omega^{*}}({\mathbf{G}})\|_{2}\leq
nC_{{\tiny u}}^{1/2},$

where $\Omega:=\text{supp}({\boldsymbol{\beta}})$ and
$\Pi:=\text{supp}\big{(}{\mathcal{H}}_{\tilde{s}}({\mathcal{P}}_{\Omega^{\rm
c}}({\mathbf{G}}))\big{)}$;

  2. (2)

for all

$\displaystyle{\boldsymbol{\beta}}\in\left\\{{\boldsymbol{\beta}}\in{\mathbb{R}}^{d}:\
C_{2}C_{{\tiny u}}^{1/2}C_{{\tiny l}}^{-1}\cdot
b_{0}\max\left\\{\big{(}\tilde{s}/n\cdot\log(2d/\tilde{s})\big{)}^{1/2},\epsilon\right\\}\leq\|{\boldsymbol{\beta}}-{\boldsymbol{\beta}}^{*}\|_{2}\leq
8C_{{\tiny
l}}^{-1/2}\gamma,|\text{supp}({\boldsymbol{\beta}})|\leq\tilde{s}\right\\}$

and for all sub-gradient ${\mathbf{G}}\in\partial f({\boldsymbol{\beta}})$,

$\displaystyle
f({\boldsymbol{\beta}})-f({\boldsymbol{\beta}}^{*})\geq\frac{nC_{{\tiny
l}}}{12b_{0}}\|{\boldsymbol{\beta}}-{\boldsymbol{\beta}}^{*}\|_{2}^{2}\quad{\rm
and}\quad\|{\mathcal{P}}_{\Omega\cup\Pi\cup\Omega^{*}}({\mathbf{G}})\|_{2}\leq
C_{3}\frac{nC_{{\tiny
u}}}{b_{1}}\|{\boldsymbol{\beta}}-{\boldsymbol{\beta}}^{*}\|_{2},$

where $\Omega:=\text{supp}({\boldsymbol{\beta}})$ and
$\Pi:=\text{supp}\big{(}{\mathcal{H}}_{\tilde{s}}({\mathcal{P}}_{\Omega^{\rm
c}}({\mathbf{G}}))\big{)}$.

###### Proof of Lemma 19.

The difference with Lemma 1 is the appearance of outliers and we shall treat
inliers, outliers differently. Denote

$\displaystyle
f_{i}({\boldsymbol{\beta}}):=\sum_{i\in{\mathcal{I}}}\left|Y_{i}-\langle{\mathbf{X}}_{i},{\boldsymbol{\beta}}\rangle\right|,\quad
f_{o}({\boldsymbol{\beta}}):=\sum_{i\in{\mathcal{O}}}\left|Y_{i}-\langle{\mathbf{X}}_{i},{\boldsymbol{\beta}}\rangle\right|.$

Notice that we have
$f({\boldsymbol{\beta}})=f_{i}({\boldsymbol{\beta}})+f_{o}({\boldsymbol{\beta}})$.
We shall assume the event

$\displaystyle{\boldsymbol{\mathcal{E}}}_{i}$
$\displaystyle:=\left\\{\sup_{{\boldsymbol{\beta}}\in{\mathbb{R}}^{d},\;|\text{supp}(\Delta{\boldsymbol{\beta}})|\leq
3\tilde{s}}\left|f_{i}({\boldsymbol{\beta}}+\Delta{\boldsymbol{\beta}})-f_{i}({\boldsymbol{\beta}})-{\mathbb{E}}\left[f_{i}({\boldsymbol{\beta}}+\Delta{\boldsymbol{\beta}})-f_{i}({\boldsymbol{\beta}})\right]\right|\cdot\|\Delta{\boldsymbol{\beta}}\|_{2}^{-1}\right.$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\left.\leq
C\sqrt{(1-\varepsilon)n\tilde{s}C_{{\tiny u}}\log(2d/\tilde{s})}\right\\}$

holds. Proposition 2 proves ${\mathbb{P}}({\boldsymbol{\mathcal{E}}}_{i})\geq
1-\exp(-\frac{C^{2}\tilde{s}\log(2d/\tilde{s})}{3})-3\exp\left(-\frac{\sqrt{(1-\epsilon)n\log(2d/\tilde{s})}}{\log(1-\epsilon)n}\right)$.
Also, we assume the event

$\displaystyle{\boldsymbol{\mathcal{E}}}_{o}:=\left\\{\sup_{|\text{supp}(\Delta{\boldsymbol{\beta}})|\leq
3\tilde{s}}\sum_{i\in{\mathcal{O}}}\bigg{|}|\langle{\mathbf{X}}_{i},\Delta{\boldsymbol{\beta}}\rangle|-{\mathbb{E}}|\langle{\mathbf{X}}_{i},\Delta{\boldsymbol{\beta}}\rangle|\bigg{|}\cdot\|\Delta{\boldsymbol{\beta}}\|_{2}^{-1}\leq
C\sqrt{\epsilon n\tilde{s}C_{{\tiny u}}\log(2d/\tilde{s})}\right\\}$

holds and epsilon net theory or Gaussian process theory shows
${\mathbb{P}}({\boldsymbol{\mathcal{E}}}_{o})\geq
1-\exp(-\frac{C^{2}\tilde{s}\log(2d/\tilde{s})}{3})$.

##### Phase One

First, show $\mu$-sharpness. Notice that

$f({\boldsymbol{\beta}})-f({\boldsymbol{\beta}}^{*})=f_{i}({\boldsymbol{\beta}})-f_{i}({\boldsymbol{\beta}}^{*})+f_{o}({\boldsymbol{\beta}})-f_{o}({\boldsymbol{\beta}}^{*}).$

Same as Section B, under event ${\boldsymbol{\mathcal{E}}}_{i}$, we have

$f_{i}({\boldsymbol{\beta}})-f_{i}({\boldsymbol{\beta}}^{*})\geq(1-\epsilon)n\sqrt{C_{{\tiny
l}}\pi/2}\|{\boldsymbol{\beta}}-{\boldsymbol{\beta}}^{*}\|_{2}-C\sqrt{(1-\epsilon)n\tilde{s}C_{{\tiny
u}}\log(2d/\tilde{s})}\|{\boldsymbol{\beta}}-{\boldsymbol{\beta}}^{*}\|_{2}-2(1-\epsilon)n\gamma.$

At the same time, under event ${\boldsymbol{\mathcal{E}}}_{o}$, we have

$\displaystyle\big{|}f_{o}({\boldsymbol{\beta}})-f_{o}({\boldsymbol{\beta}}^{*})\big{|}$
$\displaystyle=\big{|}\sum_{i\in{\mathcal{O}}}\left|Y_{i}-\langle{\mathbf{X}}_{i},{\boldsymbol{\beta}}\rangle\right|-\sum_{i\in{\mathcal{O}}}\left|Y_{i}-\langle{\mathbf{X}}_{i},{\boldsymbol{\beta}}^{*}\rangle\right|\big{|}$
$\displaystyle\leq\sum_{i\in{\mathcal{O}}}\left|\langle{\mathbf{X}}_{i},{\boldsymbol{\beta}}-{\boldsymbol{\beta}}^{*}\rangle\right|$
$\displaystyle\leq{\mathbb{E}}\sum_{i\in{\mathcal{O}}}\left|\langle{\mathbf{X}}_{i},{\boldsymbol{\beta}}-{\boldsymbol{\beta}}^{*}\rangle\right|+C\sqrt{\epsilon
n\tilde{s}C_{{\tiny
u}}\log(2d/\tilde{s})}\|{\boldsymbol{\beta}}-{\boldsymbol{\beta}}^{*}\|_{2}$
$\displaystyle\leq\epsilon n\sqrt{\frac{2}{\pi}C_{{\tiny
u}}}\|{\boldsymbol{\beta}}-{\boldsymbol{\beta}}^{*}\|_{2}+C\sqrt{\epsilon
n\tilde{s}C_{{\tiny
u}}\log(2d/\tilde{s})}\|{\boldsymbol{\beta}}-{\boldsymbol{\beta}}^{*}\|_{2},$

where the last line follows from Lemma 16. Thus, we have lower bound of
$f({\mathbf{M}})-f({\mathbf{M}}^{*})$,

$\displaystyle~{}~{}~{}f({\boldsymbol{\beta}})-f({\boldsymbol{\beta}}^{*})$
$\displaystyle\geq
f_{i}({\boldsymbol{\beta}})-f_{i}({\boldsymbol{\beta}}^{*})-\left|f_{o}({\boldsymbol{\beta}})-f_{o}({\boldsymbol{\beta}}^{*})\right|$
$\displaystyle\geq(1-\epsilon)n\sqrt{\frac{2}{\pi}C_{{\tiny
l}}}\|{\boldsymbol{\beta}}-{\boldsymbol{\beta}}^{*}\|_{2}-C\sqrt{(1-\epsilon)n\tilde{s}C_{{\tiny
u}}\log(2d/\tilde{s})}\|{\boldsymbol{\beta}}-{\boldsymbol{\beta}}^{*}\|_{2}$
$\displaystyle{~{}~{}~{}}-\epsilon n\sqrt{\frac{2}{\pi}C_{{\tiny
u}}}\|{\boldsymbol{\beta}}-{\boldsymbol{\beta}}^{*}\|_{2}-C\sqrt{\epsilon
n\tilde{s}C_{{\tiny
u}}\log(2d/\tilde{s})}\|{\boldsymbol{\beta}}-{\boldsymbol{\beta}}^{*}\|_{2}-2(1-\epsilon)n\gamma$
$\displaystyle\geq\frac{n}{5}\sqrt{C_{{\tiny
l}}}\|{\boldsymbol{\beta}}-{\boldsymbol{\beta}}^{*}\|_{2},$

where the last line is due to $\epsilon\leq\sqrt{C_{{\tiny
l}}}/(\sqrt{C_{{\tiny l}}}+4\sqrt{C_{{\tiny u}}})\leq 0.2$, $1-\epsilon\geq
0.8$, $n\geq C_{1}C_{{\tiny u}}C_{{\tiny l}}^{-1}\tilde{s}\log(2d/\tilde{s})$
and phase one region constraint
$\|{\boldsymbol{\beta}}-{\boldsymbol{\beta}}^{*}\|_{2}\geq 8C_{{\tiny
l}}^{-1/2}\gamma$. We could prove upper bound of
$\|{\mathcal{P}}_{\Omega\cup\Pi\cup\Omega^{*}}({\mathbf{G}})\|_{2}$ in a
similar fashion,

$\|{\mathcal{P}}_{\Omega\cup\Pi\cup\Omega^{*}}({\mathbf{G}})\|_{2}\leq
n\sqrt{C_{{\tiny u}}}.$

##### Phase Two

First consider lower bound of
$f({\boldsymbol{\beta}})-f({\boldsymbol{\beta}}^{*})$. Follow Section B and we
obtain when $C_{2}\sqrt{\frac{C_{{\tiny u}}}{C_{{\tiny
l}}^{2}}}b_{0}\max\\{\sqrt{\frac{\tilde{s}\log(2d/\tilde{s})}{n}},\epsilon\\}\leq\|{\boldsymbol{\beta}}-{\boldsymbol{\beta}}^{*}\|_{2}\leq
8\sqrt{C_{{\tiny l}}^{-1}}\gamma$,

$\displaystyle
f_{i}({\boldsymbol{\beta}})-f_{i}({\boldsymbol{\beta}}^{*})\geq(1-\epsilon)\frac{n}{12b_{0}}C_{{\tiny
l}}\|{\boldsymbol{\beta}}-{\boldsymbol{\beta}}^{*}\|_{2}^{2}.$

Besides, same as phase one analyses, under event
${\boldsymbol{\mathcal{E}}}_{o}$, it has

$\displaystyle\big{|}f_{o}({\boldsymbol{\beta}})-f_{o}({\boldsymbol{\beta}}^{*})\big{|}\leq\epsilon
n\sqrt{\frac{2}{\pi}C_{{\tiny
u}}}\|{\boldsymbol{\beta}}-{\boldsymbol{\beta}}^{*}\|_{2}+C\sqrt{\epsilon
n\tilde{s}C_{{\tiny
u}}\log(2d/\tilde{s})}\|{\boldsymbol{\beta}}-{\boldsymbol{\beta}}^{*}\|_{2}.$

Thus, the above two equations lead to

$\displaystyle f({\boldsymbol{\beta}})-f({\boldsymbol{\beta}}^{*})$
$\displaystyle=f_{i}({\boldsymbol{\beta}})-f_{i}({\boldsymbol{\beta}}^{*})+f_{o}({\boldsymbol{\beta}})-f_{o}({\boldsymbol{\beta}}^{*})$
$\displaystyle\geq
f_{i}({\boldsymbol{\beta}})-f_{i}({\boldsymbol{\beta}}^{*})-\left|f_{o}({\boldsymbol{\beta}})-f_{o}({\boldsymbol{\beta}}^{*})\right|$
$\displaystyle\geq(1-\epsilon)\frac{n}{12b_{0}}C_{{\tiny
l}}\|{\boldsymbol{\beta}}-{\boldsymbol{\beta}}^{*}\|_{2}^{2}-\epsilon
n\sqrt{\frac{2}{\pi}C_{{\tiny
u}}}\|{\boldsymbol{\beta}}-{\boldsymbol{\beta}}^{*}\|_{2}-C\sqrt{\epsilon
n\tilde{s}C_{{\tiny
u}}\log(2d/\tilde{s})}\|{\boldsymbol{\beta}}-{\boldsymbol{\beta}}^{*}\|_{2}$
$\displaystyle\geq\frac{n}{C_{3}b_{0}}C_{{\tiny
l}}\|{\boldsymbol{\beta}}-{\boldsymbol{\beta}}^{*}\|_{2}^{2},$

where the last line uses
$\|{\boldsymbol{\beta}}-{\boldsymbol{\beta}}^{*}\|_{2}\geq
C_{2}\sqrt{\frac{C_{{\tiny u}}}{C_{{\tiny
l}}^{2}}}b_{0}\max\\{\sqrt{\frac{\tilde{s}\log(2d/\tilde{s})}{n}},\epsilon\\}$.
Similar to Section B, we have

$\displaystyle\|{\mathcal{P}}_{\Omega\cup\Pi\cup\Omega^{*}}({\mathbf{G}})\|_{2}\leq
C_{4}C_{{\tiny
u}}\frac{n}{b_{1}}\|{\boldsymbol{\beta}}-{\boldsymbol{\beta}}^{*}\|_{2}.$

∎

### Proof of Theorem 8

We only need to prove the following regularity properties.

######  Lemma 20.

Assume $\\{\xi_{i}\\}_{i\in{\mathcal{I}}}$ and $\\{{\rm
vec}({\mathbf{X}}_{i})\\}_{i=1}^{n}$ satisfy Assumptions 2 and 1,
respectively. There exist absolute constants $C_{1},C_{2},C_{3},c_{1}>0$ such
that if $n\geq C_{1}rd_{1}C_{{\tiny u}}C_{{\tiny l}}^{-1}$,
$\epsilon\leq\sqrt{C_{{\tiny l}}}/(4\sqrt{C_{{\tiny l}}}+\sqrt{C_{{\tiny
u}}})$ and ${\mathbb{B}}_{1}$, ${\mathbb{B}}_{2}$ are given by

$\displaystyle{\mathbb{B}}_{1}:=\left\\{{\mathbf{M}}\in{\mathbb{M}}_{r}:\|{\mathbf{M}}-{\mathbf{M}}^{\ast}\|_{\rm
F}\geq 8\sqrt{C_{{\tiny l}}^{-1}}\gamma\right\\},$
$\displaystyle{\mathbb{B}}_{2}:=\left\\{{\mathbf{M}}\in{\mathbb{M}}_{r}:C_{2}b_{0}\cdot\sqrt{\frac{C_{{\tiny
u}}}{C_{{\tiny
l}}^{2}}}\cdot\max\left\\{\sqrt{\frac{d_{1}r}{n}},\epsilon\right\\}\leq\|{\mathbf{M}}-{\mathbf{M}}^{\ast}\|_{\rm
F}<8\sqrt{C_{{\tiny l}}^{-1}}\gamma\right\\},$

then with probability at least $1-2\exp(-c_{1}rd_{1})-3\exp(-\sqrt{n}/\log
n)$, the absolute loss
$f({\mathbf{M}})=\sum_{i=1}^{n}|Y_{i}-\langle{\mathbf{M}},{\mathbf{X}}_{i}\rangle|$
satisfies Condition 1:

  1. (1)

the rank-$r$ restricted two-phase sharpness with respect to
${\mathbf{M}}^{\ast}$,

$f({\mathbf{M}})-f({\mathbf{M}}^{\ast})\geq\begin{cases}\frac{n}{4}\sqrt{C_{{\tiny
l}}}\|{\mathbf{M}}-{\mathbf{M}}^{\ast}\|_{\rm F},&\textrm{ for }\ \
{\mathbf{M}}\in{\mathbb{B}}_{1};\\\ \frac{n}{12b_{0}}C_{{\tiny
l}}\|{\mathbf{M}}-{\mathbf{M}}^{\ast}\|_{\rm F}^{2},&\textrm{ for }\ \
{\mathbf{M}}\in{\mathbb{B}}_{2};\end{cases}$

  2. (2)

the rank-r restricted two-phase sub-gradient bound with respect to
${\mathbf{M}}^{\ast}$,

$\|{\mathbf{G}}\|_{\rm F,r}\leq\begin{cases}2n\sqrt{C_{{\tiny u}}},&\textrm{
for }\ \ {\mathbf{M}}\in{\mathbb{B}}_{1};\\\ C_{3}nb_{1}^{-1}C_{{\tiny
u}}\|{\mathbf{M}}-{\mathbf{M}}^{\ast}\|_{\rm F},&\textrm{ for }\ \
{\mathbf{M}}\in{\mathbb{B}}_{2},\end{cases}$

where ${\mathbf{G}}\in\partial f({\mathbf{M}})$ is any sub-gradient.

Proof of Lemma 20 would be a combination of absolute loss low-rank study in
Lemma 6 and outlier analyses in Lemma 19. We also study loss function of
inliers and outliers seperately,

$\displaystyle
f_{i}({\mathbf{M}}):=\sum_{i\in{\mathcal{I}}}\left|Y_{i}-\langle{\mathbf{X}}_{i},{\mathbf{M}}\rangle\right|,\quad
f_{o}({\mathbf{M}}):=\sum_{i\in{\mathcal{O}}}\left|Y_{i}-\langle{\mathbf{X}}_{i},{\mathbf{M}}\rangle\right|.$

Hence, we skip the proof.