∎

11institutetext: 1 Netherlands eScience Center, Amsterdam, Netherlands
2 Universiteit van Amsterdam, Amsterdam, Netherlands
3 Leiden University, Leiden, Netherlands

# Community membership consistency applied to corporate board interlock
networks

Dafne E. van Kuppevelt1 Rena Bakhshi1 Eelke M. Heemskerk2 Frank W. Takes2,3

(October 2021111This manuscript has been accepted for publication at the
Journal of Computational Social Science)

###### Abstract

Community detection is a well established method for studying the meso scale
structure of social networks. Applying a community detection algorithm results
in a division of a network into communities that is often used to inspect and
reason about community membership of specific nodes. This micro level
interpretation step of community structure is a crucial step in typical social
science research. However, the methodological caveat in this step is that
virtually all modern community detection methods are non-deterministic and
based on randomization and approximated results. This needs to be explicitly
taken into consideration when reasoning about community membership of
individual nodes. To do so, we propose a metric of _community membership
consistency_ , that provides node-level insights in how reliable the placement
of that node into a community really is. In addition, it enables us to
distinguish the _community core_ members of a community. The usefulness of the
proposed metrics is demonstrated on corporate board interlock networks, in
which weighted links represent shared senior level directors between firms.
Results suggest that the community structure of global business groups is
centered around persistent communities consisting of core countries tied by
geographical and cultural proximity. In addition, we identify fringe countries
that appear to associate with a number of different global business
communities.

###### Keywords:

board interlocks interlocking directorates community detection network
analysis modularity

††journal: Pre-print

##  1 Introduction

Community detection has established itself as method for detecting groups in
social systems, unveiling the meso level structure of networked environments.
The obtained division of a network in communities is often used in the social
sciences to understand how individual nodes in the network belong to
particular communities and how strong or durable such an affiliation is.

Unfortunately, a general problem with community detection methods is the
inherent uncertainty as a result of randomization and approximation. This
hinders interpretation of community membership on the node level. Therefore,
we propose a solution to this methodological challenge and demonstrate how
this leads to meaningful insights. In order to illustrate our approach we
consider networks of interlocking directorates, where weighted ties represent
shared directors between firms. These so-called board interlock networks have
been extensively studied in corporate governance and social network analysis
literature carroll2013making ; kogut2012small ; davis2003small ;
davis1991agents ; carroll2004corporate ; takes2016centrality ;
valeeva2020duality . The community structure of these board interlock networks
has been shown to provide valuable insights related to global business elites
and transnationalization heemskerk2016corporate ;
Heemskerk2016WhereDirectorates .

Multiple community detection methods and algorithms have been developed over
the past decades, each returning a different division of the network into
communities Blondel2008FastNetworks ; traag2019leiden ; rosvall2008maps ;
Lancichinetti_Radicchi_Ramasco_Fortunato_2011 . Several methods are based on
the notion of optimizing a quality score, such as modularity
newman2004modularity . This score indicates for a given network divided into
communities, also called a clustering, how well this was done; often in some
way favoring many links within a community, and few links between communities.
This is in line with theoretical as well as intuitive understandings of the
concept of community. As this process of optimization is analytically
intractable, popular algorithms available in standard network analysis
tooling, such as Louvain Blondel2008FastNetworks  and the Leiden algorithm
traag2019leiden , use heuristics to find a high-quality clustering. Typically,
these heuristic algorithms, upon multiple runs, return different divisions of
the network into communities. These solutions may all be optimal or near-
optimal solutions with a high quality score. However, the solutions may differ
substantially in terms of which node is in which community. This is in some
contexts referred to as the degeneracy of multiple solutions
Good2010PerformanceContexts . While this is a direct result of the randomness
and heuristics involved in the underlying algorithms, it hinders scholars from
meaningfully interpreting community detection results, especially when this
interpretation takes place at the level of individual nodes.

A method that has been proposed to solve this problem, is consensus clustering
Lancichinetti_Fortunato_2012 . In this method, multiple runs of a community
detection algorithm help determine the most consistent clustering of the
network into communities. This approach mitigates the uncertainty of one
community detection solution, obtaining in the clustering for which there is
the most ‘consensus’ across many runs of the algorithm. An accelerated version
of the algorithm was introduced in tandon2019fast . While interesting for
providing a stable meso level view of the network, there may still be
substantial differences in terms of which nodes are consistently placed in the
same community across multiple runs of the algorithm. Regardless, the final
outcome of the consensus clustering algorithm is an assignment of all nodes to
a particular community, in essence treating each node as being an equal member
of its community. This makes it challenging to reason about individual nodes
and their community membership, as we do not know whether this particular node
was consistently in the same community. However, it is exactly this type of
community membership information that is often needed to obtain actionable
insights in real-world networked systems nagy2018friendship ;
sporns_structure_2013 ; de_leo_community_2013 , including the board interlock
networks considered in this paper, as we will discuss later.

The problem of proper interpretation of the community detection outcomes
becomes even more pronounced when scholars move to a comparative approach and
compare different community detection solutions. After all, the differences
such a comparison uncovers may very well be because particular nodes did not
“fit” very well in one particular community. Examples of such comparative
studies include replications, but also longitudinal studies in which we
ultimately want to understand whether a node that moves from one to another
community is actually doing so as a result of substantive change in the
underlying system.

The discrepancy between the technical solution to the problem of community
consensus at the meso level and reliable community membership inference at the
micro level, is the topic of this study. The latter is crucial for proper
interpretation of the community detection results. To close this gap, we
propose a metric for nodes called _community membership consistency_. This
metric assesses the extent to which a node’s community assignment is
consistent across different runs of the community detection algorithm.
Ultimately, in addition to the actual node’s community membership based on
consensus clustering, it allows one to quantify how consistent this node’s
community membership actually is. Moreover, the consistency score can be used
to distinguish between _community core and fringe_ members.

Several related consistency metrics have been proposed in previous works, but
often with a goal different than interpreting an individual node’s community
membership. For example, these are metrics with the aim of defining new
centrality measures based on the consensus between different runs of a
community detection algorithm kim_community_2015 ; kim_relational_2019 , or
with the goal of proposing a method to find more stable communities
seifi_stable_2013 . The concept of community cores or ‘building blocks’ has
been explored in previous work as well. In seifi_stable_2013 , the consensus
matrix is used to define cores that are (almost) always placed in the same
community. The authors of Riolo_Newman_2019  take an information-theoretic
approach, optimizing for building blocks that maximizes the mutual information
of community assignment, conditioned on the building blocks. A similar study
looked at invariant groups of nodes in communities and investigated their
properties Chakraborty_Srinivasan_Ganguly_Bhowmick_Mukherjee_2013 . In
gilbert2018clusters , the outcomes of a number of runs of community detection
are used for semi-supervised learning, expanding a seed set of nodes based on
a similarity measure computed from the consensus matrix. A recent study
Peixoto_2020  proposes a method for computing the consensus and dissensus
between the degenerate partitions, by aligning the different clusterings and
describing the posterior distribution based on a stochastic block model.

Compared to the works discussed above, our approach differs in the sense that
it focuses on enabling the interpretation of results in an actual
computational social science context. This means that we aim for interpretable
metrics that provide an understanding of community membership at the level of
an individual node, as well as community core formation of multiple nodes.

In this paper, we use board interlock networks as an illustrative example for
the proposed metric. Board interlocks, where two firms share at least one
board member, are widely studied in order to understand the network structure
in corporate governance and corporate elites. These corporate networks allow
scholars to investigate how corporations and the individuals involved exert
power over others, gain access to information and in general interact within
the global economy. Exploring corporate network structures using network
analysis techniques has greatly improved our understanding of the global
corporate system kogut2012small ; davis2003small ; takes2016centrality ;
heemskerk2016corporate . Network studies have aided in unraveling the spread
of corporate practices davis1991agents , the formation of a corporate elite
davis2003small ; carroll2004corporate , and the formation of business groups
and elite transnationalization heemskerk2016corporate . We extend on this line
of research by studying the consistency of the community structure of the
board interlock network at the node level. We will investigate and compare the
community detection results at three levels of granularity: at the level of
firms, at the aggregated level of cities, and at the aggregated level of
countries, similar to how this is done in previous work takes2016centrality ;
Heemskerk2016WhereDirectorates ; heemskerk2016corporate . We focus on the last
level of aggregation when zooming in on individual nodes in the network,
describing their community membership in relation to their consistency score.
For this particular network, we look in detail at community cores and fringes,
allowing us to assess which countries form consistent clusters of power, and
which countries are at the fringe of these power centers.

The rest of the paper is structured as follows. In Section 2 we explain our
methodology and the concepts needed to define the proposed metrics of
community membership consistency and community cores. In Section 3 we present
our results of applying these measures to board interlock network data, both
on a high level for all three networks, and in a more detailed manner for the
country level network. Section 4 discusses the implications of the results for
the research field as well as directions for future work, whereas finally
Section 5 concludes the paper and summarizes the main findings.

##  2 Method

In this section we describe our methodology, of which the input is a network,
and the output is a division into communities together with interpretable node
consistency scores, that can subsequently be used for identifying community
cores. The approach builds on consensus clustering (Section 2.1), after which
a number of edge- and node-specific measures are derived in Section 2.2 in
order to compute the proposed measure of community membership consistency in
Section 2.3. Finally, the approach to derive community cores is explained in
Section 2.4.

###  2.1 Consensus clustering

As discussed in Section 1, a key problem in modern community detection methods
is the instability of results across multiple runs of a particular community
detection algorithm. To overcome this problem and obtain a stable
partitioning, we apply consensus clustering Lancichinetti_Fortunato_2012  to
the input network. In this method, a community detection algorithm is applied
$n$ times to a network represented as a weighted adjacency matrix $A$, but
with different initial random states. This means that we obtain multiple
clusterings of the network from which a so-called ‘consensus matrix’ can be
constructed. For each combination of nodes $i$ and $j$, the value of the
consensus matrix $c_{ij}$ denotes the fraction of clusterings in which $i$ and
$j$ are placed in the same community. As a next step, all values in the
consensus matrix below a threshold $\tau$ are set to zero. Then the filtered
consensus matrix is regarded as a weight matrix of a new network, which is
used as input to a next iteration of community detection and thresholding.
This process is repeated until convergence of the clustering, that is, the
clustering does not change in subsequent iterations. It was found empirically
that in most cases, only one to three iterations are needed to obtain
convergence.

Because the method above works _independent of the community detection
algorithm_ that is used, it can easily be extended to more complex network
data. While we work with undirected weighted networks in the remainder of this
paper, including for example directionality or a multilayer structure is
possible as long as the employed community detection algorithm properly
handles these aspects, for example using the methodology proposed in
mucha2010community .

In this work we exemplify our approach using the Leiden algorithm
traag2019leiden  for community detection. The Leiden algorithm optimizes the
modularity score, similar to the well known Louvain algorithm
Blondel2008FastNetworks . Modularity is defined as:

$Q=\frac{1}{2m}\sum_{ij}(A_{ij}-\gamma\frac{k_{i}k_{j}}{2m})\delta(C_{i},C_{j})$

Here, $A_{ij}$ is the adjacency matrix, $m_{c}$ is the number of edges in
community $c$, $C_{i}$ is the community assignment of node $i$ and $k_{i}$ is
the degree of node $i$. The parameter $\gamma$ controls the resolution at
which communities are detected, which we leave untouched at a value of $1$.
Whereas the Louvain algorithm heuristically optimizes the modularity score by
merging clusters and moving nodes, the Leiden algorithm also includes
improvements for overcoming the problem of badly connected clusters that may
result from the original Louvain algorithm.

(a) $p$: 5%, $Q$: 0.37

(b) $p$: 29%, $Q$: 0.40

(c) $p$: 3%, $Q$: 0.37

(d) $p$: 57%, $Q$: 0.40

(e) $p$: 6%, $Q$: 0.37

(f) Consensus clustering

Figure 1: Five divisions into communities (a)–(e) of a toy network (from
kim_relational_2019 ), listing $p$, the percentage of iterations resulting in
this clustering over 100 runs and corresponding modularity quality score $Q$.
The consensus clustering in (f).

As an example, Figure 1 shows the result of running the Leiden algorithm for
100 iterations. It finds five different clusterings in these 100 runs (Figure
1(a)–(e)), with modularity values $Q$ that are very close (or equal) to each
other. The value of $p$ indicates the percentage of runs resulting in that
particular clustering. For this example, the consensus clustering happens to
coincide with the most common clustering (Figure 1(d)). Although this is not
the case in general, in Lancichinetti_Fortunato_2012  as well as in our
experiments in Section 3 it is empirically shown that with a proper choice of
a threshold value, the quality of the consensus clustering is similar to the
individual runs of community detection, but has a more stable character.
Therefore in the remainder of this work, we choose the threshold value $\tau$
that corresponds to the division of the network into communities with the
largest modularity value.

Note that the algorithmic runtime and memory usage of the consensus clustering
is also the determining factor in our methodology. This can, in theory, get
close to quadratic in the number of nodes, because the full consensus matrix
is calculated. In subsequent steps, we will only need the elements from the
consensus matrix that correspond to edges in the network. Therefore, the fast
consensus clustering method from tandon2019fast  can be used, which uses a
reduced consensus matrix, making the complexity of consensus clusering and
thus our method linear in the number of edges.

###  2.2 Edge consistency

Consensus clustering results in a stable partitioning, but no insight in how
reliable this partitioning really is. We therefore take a closer look at the
consensus matrix, as calculated in the first iteration of the consensus
clustering algorithm. For each combination of nodes $i$ and $j$, the consensus
value $c_{ij}$ is a value between 0 and 1 that denotes how often those two
nodes were clustered together. This allows us to define the node pair
consistency $s_{ij}$ for each node pair $i$,$j$ as follows:

$s_{ij}=2|c_{ij}-0.5|$

This consistency value can be considered a dispersion metric of the consensus
values, equivalent to the mean absolute difference. The value is multiplied by
2 to scale the consistency value to a more easily interpretable range between
$0$ and $1$. If $s_{ij}$ is equal to maximum value 1, then this means that the
combination of nodes always lies either within one community or in two
separate communities, i.e., those two nodes are very consistently placed with
respect to each other. A value of 0 denotes maximum disagreement between the
clusterings: half of the clusterings groups the nodes together and the other
half assigns the two nodes to different communities. Note that the consistency
score above is defined for all possible node pairs, including those that are
not connected by an edge in the network. If nodes pairs are connected with an
edge, we will henceforward refer to the corresponding consistency score as the
edge consistency.

###  2.3 Community membership consistency

Next, we must move from the measure of edge consistency discussed above to a
node-specific consistency score. Note that this step from an edge-centered
metric to a node-centered metric is not trivial. We propose to consider the
distribution of edge consistency scores for the edges attached to this node,
to assess whether this node is consistently put in the same community as its
neighbors. Between different clusterings, a node might move to a different
community together with some of its neighbors. This means that the consistency
of edges to those neighbors will be high, whereas it will be low for the edges
to neighbors that do not move. Recall that our objective is to develop a
metric for community membership consistency for each node in our network. We
do not want to assign a high consistency value to a node that moves together
with its neighbors, even though it has some high consistency edges. This
disqualifies the use of the mean of edge consistency scores over all edges
attached to a node, as suitable node-specific score. As we will see later in
experiments, the distribution of edge consistency values is very skewed, so
that the mean value is usually high, while there are clearly some outliers
with a very low value.

To illustrate, see node 7 in the example network of Figure 1. Node 7 is almost
always clustered together with node 6, so if we would take the mean of edge
consistencies from node 7, it would be pulled up by this highly consistent
edge. Intuitively, however, we would not assign node 7 a high consistency
because, between the different clusterings, it moves communities together with
node 6.

As we are interested in the effect of the low edge consistencies on the node’s
consistency, we introduce a threshold method. For a node $i$ and a chosen
threshold $\theta$ we define the community membership consistency
$s_{i}^{\theta}$ of a node as:

$s_{i}^{\theta}=\frac{\sum_{j}\delta_{ij}\mathbf{1}_{s_{ij}\geq\theta}}{\sum_{j}\delta_{ij}}$

Here, $\delta_{ij}$ denotes the existence of an edge between node $i$ and $j$,
i.e., whether $A_{ij}>0$. The community membership consistency
$s_{i}^{\theta}$ essentially denotes the fraction of the edges connected to
the node with an edge-consistency larger than $\theta$. Thus, the threshold
parameter $\theta$ denotes how often nodes should be clustered consistently so
that we find it trustworthy enough to derive conclusions from it. This may
depend on the number of partitions we find in the first place, and the
modularity landscape they form. To choose a meaningful value for the
threshold, we consider possible values that follow from the distribution of
edge consistencies. Ideally, we choose a threshold that is high enough to
distinguish inconsistent nodes, but not too high as this may lead to many
inconsistent nodes due to small disturbances in the community assignments. In
general, a higher threshold leads to lower values of node consistency. As an
example, see Figure 2 where community membership consistency is plotted for
all possible threshold values in this toy example (see Figure 1). The
different threshold values in this small example correspond to the unique
values of edge consistency in the network. Compared to the mean consistency
over the node’s edges, community membership consistency has a less skewed
distribution. We observe the same difference in larger networks, as we will
see in Section 3.

(a) Mean consistency

(b) Community membership consistency $s_{i}^{0.82}$

(c) Community membership consistency $s_{i}^{0.84}$

(d) Community membership consistency $s_{i}^{0.94}$

(e) Community membership consistency $s_{i}^{1}$

Figure 2: Community membership consistency, depicted by node color intensity,
for all possible thresholds in an example network. Edge consistency, depicted
by edge thickness.

###  2.4 Community cores

Similar to how this is done in seifi_stable_2013 , we can use the community
membership consistency scores to reason about groups of nodes that are
consistent members of a community. This allows us to define community cores,
that is, set of nodes that are consistently placed together in the same
community. If a node is almost always placed in the same community as all of
its neighbors, it will have a consistency value of exactly $1$. We call these
nodes the hard community core. Note that the hard community core could be
disconnected, as groups of nodes can be moved to a different community
together.

It is also useful to distinguish in a less strict way, _community core nodes_
that have a high community membership consistency. For this, we choose a
threshold $\kappa$ close to 1. Similarly, _fringe_ members are nodes that have
a very low community membership consistency, for which we choose another,
typically much lower, threshold $\phi$. The values of these thresholds can be
chosen empirically, possibly considering the robustness of the community cores
around these threshold values.

##  3 Experiments

We start by describing the board interlock network data used to evaluate the
method in Section 3.1, after which the experimental setup is discussed in
Section 3.2. We inspect the results of the consensus clustering in Section
3.3, before evaluating the node consistency scores in Section 3.4. An
interpretation of the results is given in Section 3.5.

###  3.1 Data

We apply the method on board interlock data derived from a 2015 snapshot of
the ORBIS database ORBIS . This database contains global firm-level
information, including positions of directors at these firms as well as the
firm’s location city, country and operating revenue. We use the latter as an
indicator of company size, and consider only firms above a certain threshold
revenue, as a previous study has shown that the quality of this data is high
for large firms garcia2018effects . From this database, we created the
following three network datasets by projecting the raw data on positions of
directors at firms to a firm-by-firm board interlock network:

  1. 1.

Firm network: all board interlocks between firms with an operating revenue of
at least $50M.

  2. 2.

City network: all board interlocks between firms with an operating revenue of
at least $5M, aggregated at the city level, similar to the network used in
Heemskerk2016WhereDirectorates ;

  3. 3.

Country network: all board interlocks between firms with an operating revenue
of at least $5M, aggregated at the country level, similar to the network used
in heemskerk2016corporate ;

From each network, we only considered the largest connected component (which
in all cases captured over $95\%$ of all edges), and we do not consider self-
loops (which correspond to the number of shared directors within one country
or city). Basic descriptive statistics of these datasets are shown in Table 1.
All networks are undirected, weighted networks. Next to the number of nodes
and edges, we show the mean degree, indicating to how many other nodes a node
is connected on average. Lastly, the mean weighted degree denotes the mean
value of the weighted degree, i.e. the sum of weights of all edges adjacent to
a node.

###  3.2 Experimental setup

For the threshold in the calculation of community membership consistency, as
described in Section 2.3, we choose edge consistency threshold $\theta=0.9$
based on the edge consistency distribution. For the community cores and
fringes, as described in Section 2.4, we choose core and fringe threshold
parameters of respectively $\kappa=0.9$ and $\phi=0.5$.

Our method has been implemented in Python and is available as a python package
nwtools222DOI:10.5281/zenodo.3247681. Scripts and notebooks to generate the
plots in this paper can be found online333https://github.com/research-
Dafne/consistency-paper.

Table 1: Descriptive statistics of the networks used. Density denotes the average number of edges per node. Network | Nodes | Edges | Mean degree | Mean weighted degree
---|---|---|---|---
Countries | 170 | 2,554 | 30.0 | 3312.4
Cities | 24,747 | 859,665 | 69.5 | 1238.3
Firms | 73,167 | 271,169 | 7.4 | 11.3

(a) Countries

(b) Cities

(c) Firms

Figure 3: The (sorted) modularity values of the individual clusterings (blue
line) and of the consensus clustering for different thresholds (red dots)

(a) Countries

(b) Cities

(c) Firms

Figure 4: The (sorted) modularity values of the individual clusterings (blue
line) and of the consensus clustering for $\tau=0.5$ (red line)

###  3.3 Modularity landscape and consensus clustering

We describe the results from the consensus clustering, as described in Section
2.1, and investigate the degeneracy of the modularity landscapes for our
networks, to show the necessity of a node community consistency score.

Figure 3 shows the modularity value of the initial clusterings, obtained with
the Leiden algorithm, for the different networks, together with the modularity
values for consensus clustering with different thresholds. For all three
networks, we proceed with threshold $\tau=0.5$ as this gives the highest
modularity values. The resulting modularity value is plotted, together with
the modularity values of the initial clusterings, in Figure 4. For all three
networks, the range of modularity values of the different clusterings is very
small, confirming the degeneracy in the modularity landscape. As can be
expected, the consensus clustering does not always have the highest possible
modularity value, but is similar to the modularity values of the original
clusterings.

Table 2: Results of modularity optimization for the three networks. We report the number of unique partitions, the mean modularity score of those partition, the modularity of the consensus clustering, the mean Normalized Mutual Information (NMI) of all pairs of clusterings, and the mean NMI between the consensus clustering and individual clusterings. Network | Countries | Cities | Firms
---|---|---|---
Unique partitions | 64 | 100 | 100
Mean modularity | 0.276 | 0.707 | 0.907
Consensus modularity | 0.276 | 0.707 | 0.908
Mean NMI | 0.866 | 0.972 | 0.856
Mean Consensus NMI | 0.931 | 0.980 | 0.882

More details on the solutions of the modularity optimization are given in
Table 2, where we calculate the NMI (Normalized Mutual Information) between
the consensus clustering and the individual clusterings, and among the
individual clusterings. NMI is a similarity measure and in this context thus
tells us how diverse the set of clusterings is in terms of similarity between
clusterings. Although there are many different clusterings, the mean NMI
between clusterings is high for all three networks. The mean NMI between the
consensus clustering and the individual clusterings is even higher. This
suggests that the effects of the degeneracy for the overall clustering of
these networks is not so pronounced, because the clusterings are all quite
similar. This means we can safely take the consensus clustering as reference
clustering when looking at community membership consistency in Section 3.4.
However, the degeneracy can still affect individual nodes, as we will see
later in the results. The large variety of high-quality clusters shows the
need to obtain insights in the effects on the individual nodes.

###  3.4 Community membership consistency

Here we investigate the node-level consistency scores, as proposed in Section
2.3 and compare the values to other node-specific measures. Figure 5 plots the
weighted degree of each node against its community membership consistency, and
denotes the Spearman rank correlation between these values. These results
suggest that the community membership consistency may be less informative for
low-degree nodes, because there are fewer possible values of community
membership consistency. In the most extreme case, nodes that have only one
neighbor will have a community membership consistency of either 0 or 1. An
interesting observation is that community membership consistency is negatively
correlated with weighted degree. Note that based on the colors in the plot,
there is indeed a high density of nodes in the upper left part bins, having a
low weighted degree and high consistency score.

In fact, the unweighted node degree also shows a negative Spearman correlation
with community membership consistency (e.g. for the country network,
$\rho=-0.38,p=0$). Note that, as can be seen in the plot, there are many low-
degree nodes that have very high consistency. Thus, if a node has low
community membership consistency, it is more likely to have a higher degree.
High degree nodes are often viewed as interesting because of their central
position in the network, but these results suggests we need to be careful in
drawing conclusions about their positions in communities.

(a) Countries:
$\rho=-0.21,p=5.6\cdot 10^{-3}$

(b) Cities:
$\rho=-0.36,p=0$

(c) Firms:
$\rho=-0.15,p=0$

Figure 5: Two-dimensional histogram of community membership consistency scores
$s_{i}^{(0.9)}$ and weighted degree in the country, city and firm networks,
listing the Spearman correlation ($\rho$) between the two. Color denotes the
number of nodes in the bin (cell).

###  3.5 Results

We now turn to a descriptive analysis of the community detection outcomes,
using the node consistency scores for meaningful interpretation. A geographic
representation of the country network is presented in Figure 6. Here, the
community membership consistency scores are visualized by means of the
transparency of the corresponding node color. The color itself is based on the
community assignment according to the consensus clustering. This allows us to
easily identify the community of a node as well as the extent to which it is a
consistent community member. Descriptive statistics on the composition of each
community’s hard community core, community core and fringe are shown in Table
3. It also lists for each community the three heaviest nodes (nodes with the
highest sum of weighted edges connected to it).

Figure 6: Consensus communities for the countries. The transparency of the color denotes the community membership consistency $s_{i}^{(0.9)}$. Community |  I |  II |  III |  IV |  V |  VI |  VII
---|---|---|---|---|---|---|---
Number of countries |  42 |  51 |  28 |  23 |  15 |  8 |  3
Mean consistency |  0.81 |  0.95 |  0.88 |  0.80 |  0.72 |  1.00 |  1
Hard community core members |  14 |  18 |  12 |  13 |  4 |  8 |  3
Hard community core (relative) |  33% |  35% |  43% |  57% |  27% |  100% |  100%
Community core |  24 |  45 |  17 |  16 |  7 |  8 |  3
Community core (relative) |  57% |  88% |  61% |  70% |  47% |  100% |  100%
Fringe members |  5 |  1 |  1 |  5 |  2 |  0 |  0
Heaviest nodes |  CN SG MY |  FR IT ES |  GB US IE |  AE SA EG |  BR CO CL |  SE NO FI |  WS TO VU
Table 3: Descriptives of the communities in the country network

Community I, which is the second largest community, gravitates around Asia,
with as its community core members China, Japan, South Korea, Singapore and
Malaysia. Interestingly, this community also contains as core members well
known offshore financial centres such as the Cayman Islands, and British
Virgin Islands, corroborating previous work takes2016centrality . The
community core has 24 members. This includes a sizeable number of relatively
small Asian economies such as Bhutan, Mongolia, and Laos. There are five
countries that score under 0.5 on consistency, including Mauritius, Papua New
Guinea, Nepal and Sri Lanka. While both Nepal and Bhutan are members of this
community, Nepal is a fringe member and Bhutan a community core member. The
node consistency score helps us to see this important difference between these
economies’ membership of the Asian community. These findings corroborate
previous work that finds a coherent Asian community in the board interlock
network heemskerk2016corporate , but adds to this work by showing which
smaller economies are fringe or core members.

Community VI is of interest as it shows full consistency. The eight members of
this Nordic-Baltic community are always positioned together. Earlier work
already found that this cluster of countries is strongly interconnected
heemskerk2016corporate . However, with the overview of consistency scores we
can now conclude that all of the eight economies have a similar fit. The same
goes for community VII, with as its only members three Pacific island states:
Tonga, Vanuatu and Samoa. These three small economies are oriented upon
themselves.

Community V brings together the major economies on the South American
continent, but in a relatively inconsistent manner. Under half of its members
are part of the community core, and the large economic players such as
Argentina ($0.56$), Mexico ($0.66$) and Brazil ($0.65$) are all outside the
community core. This suggests low levels of economic integration through
corporate board interlocks, corroborating previous findings on this matter
(see for example cardenas2015latin ). A more detailed analysis would aim to
reveal if the orientation of these core Latin economies are markedly
different, for instance such that Mexico is more oriented to North America and
Brazil to Europe.

If we move on to community IV, we see 23 members, and a community core of 16
(hard community core of 13). It contains the key economies in the middle and
near east, such as Saudi Arabia, Egypt, but also Iran and Lebanon. A few
African economies are included in this community as well, but given their low
consistency score we cannot consider Burkina Faso, Mali, or Niger meaningful
members. Benin and Madagascar score zero consistency, which means that they
are not integrated in this community at all. It is of interest to see
economies that are strongly opposed in the geopolitical and military realm
such as Iran and Saudi Arabia in one community together with Iraq and Syria.
This suggest that the political and military divisions have not washed away
the economic integration, although it should be noted that these connections
may run through countries not involved in these conflicts. Interestingly,
Sudan is placed with the Middle East cluster, whereas its geographical
counterpart and military rival South Sudan is placed in the Asian community.
Also, it is notably that the largest economy in the region, Israel, is part of
another community, namely community IV.

Community III centres around North America (USA and Canada) and also contains
Ireland, the United Kingdom, and South Africa. It reflects to some extent the
old British Empire (see also takes2016centrality ). However, the consistency
scores hint at a rather interesting dynamic as the main economies UK (0.86)
and the USA (0.84) in this community are not in the hard community core. Also,
it is remarkable that Australia and New Zeeland are not in this community but
rather placed as non-core members in community zero. Previous work found that
the Anglophone cluster was a strong backbone of the transnational network of
board interlocks. Our more detailed analysis shows that to the extent that
this community is still discernible, it may be moving towards disintegration.

This leaves community II, where the European economies are located. With 51
members it is the largest community we find. Given the high level of European
economic integration and the relatively small geographic size of many of the
European countries this may come as no surprise. Like other communities, we
see that the hard community core members are typically smaller economies such
as Moldova, Albania, and Kosovo. We also see that some small non-European
economies such as Cameroon, Congo, and Algeria are firmly positioned in this
community, signalling a European rather than an Asian or North American
orientation. There are hardly fringe members in this community, and only
Azerbaijan (with a consistency of 0.17) should not be considered as a member
of this community from a substantive point of view. Of some interest is that
The Netherlands is positioned in this European community, and not in the
transatlantic Anglophone community as previous research found
heemskerk2016corporate .

This descriptive analysis of the community detection results illustrates the
usefulness and importance of considering node level consistency scores for a
proper interpretation of the outcomes. An important observation is that
economies with the highest consistency scores are typically smaller economies,
while the larger and more dominant community members are typically in the
community core with at least 0.9 consistency score. This coincides with the
negative correlation we found between weighted node degree (number of
connections of a country) and consistency. We saw that almost all communities
had some members with rather low consistency scores. This information allows
us to refrain from any meaningful interpretation of these countries’
particular results. The empirical outcome that Azerbaijan is positioned in the
European community (consistency of $0.17$) or Guatamala in the Latin community
(consistency of $0.11$) has no substantive meaning. This is an example of how
considering the node consistency scores makes one prone to serious errors in
the interpretation of the community detection results.

##  4 Discussion

The goal of this study was to offer a way to draw reliable conclusions from
community detection. For this purpose, we introduced community membership
consistency, based on the consensus matrix from different runs of a modularity
maximization algorithm. We showed the value of this method for board interlock
networks, where indeed there are central nodes for which we cannot rely on
their placement in the community by the consensus clustering method.

It is important to note that modularity optimization is only one of many
community detection methods available, and it has known limits, other than the
degeneracy problem fortunato2010community ; Fortunato2007 . However, many
other popular community detection algorithms, such as Infomap rosvall2008maps
and OSLOM Lancichinetti_Radicchi_Ramasco_Fortunato_2011 , are also non-
deterministic or depend on node ordering, and may also result in different
solutions upon multiple runs, essentially suffering from the same limitations.
Our proposed method is thus equally applicable to those algorithms.

As noted in Section 1, the proposed measure is similar to community
(in)consistency as defined by kim_community_2015 ; kim_relational_2019 , which
uses the sum of squares of the distances to the consensus matrix for each
node. The definition used in that work differs from our definition in a few
aspects. First, it computes the node-level score from the consistency values
of all node pairs, in contrast to our approach where we only look at the
direct neighborhood of a node. Second, it aggregates the node pair scores
using the mean, somewhat mitigating the skewedness of the distribution of node
pair consistency by defining it using a square function instead of absolute
value. Community inconsistency is then shown to be informative as a centrality
metric. It thus serves a different goal than our community membership
consistency, which is used to define community cores and fringe members and
get a better understanding of node-specific community membership.

The community membership consistency score heavily depends on the modularity
landscape formed by the initial clusterings, which is shaped by the topology
of the network. Explorations of the shape of the modularity landscape have
been done in previous research. For example, in Calatayud_Bernardo-
Madrid_Neuman_Rojas_Rosvall_2019 , the solution landscape is investigated by
clustering the resulting solutions. Other work de_santiago_role_2016  shows
that low-degree nodes are most influential on the number of suboptimal
partitions. This contradicts with our finding that community membership
consistency is negatively correlated with (weighted) degree.

Future work can investigate the relationship between community membership
consistency and node properties such as degree. It can further explore the
generalizibility of our method to different types of networks. Note that the
community membership consistency is highly dependent on the node degree, so it
is possible that the method has limitations in very sparse networks. It may be
interesting to study effects of the network structure on the interpretability
of the results, as well as the choice of threshold $\theta$.

The extent to which the degeneracy leads to diversity in the clusterings,
depends of course on the optimization algorithm, as was also shown by
Good2010PerformanceContexts . To calculate and use consistency in a sensible
way, one could argue that a large diversity of clusterings is positive, as
long as they are all close to the optimum. However, this is not what
optimization algorithms are designed for and it is unclear to which extent
different algorithms explore the modularity space. We have observed that the
Leiden algorithm, which we use in this paper, results in a more diverse set of
outcomes than its predecessor, the Louvain algorithm. In Riolo_Newman_2019 , a
generative model is used so that it is possible to sample from the posterior
distribution over clusterings. It would be interesting to combine this
approach with our proposed consistency metric.

Additionally, it should be noted that in the example of corporate networks,
and in general for our approach, the multilayer aspect of networks could be
considered, taking into account the different types of links, in our case,
e.g., both board interlocks and ownership links between firms
takes2018multiplex . However, when applying the proposed community membership
consistency method to community detection methods for more complex network
models, such as multilayer networks, the interpretation also becomes more
challenging. It would make it for example difficult to do a systematic
interpretation from a domain perspective as we did in Section 3. This warrants
further investigation in future work. Even more generally, it could be
investigated how our approach could be used in other complex networks models,
such as temporal networks and higher-order networks lambiotte2019networks .

Another direction of future research is the interpretability of nodes with low
consistency and the relationship between consistency and community dynamics.
When a node has low consistency, applied researchers may be interested into
why the node is not a stable member of the community. Of course this can be
done from a domain perspective, attempting to see if there is substantive
change going on in the system. Interestingly, unstable nodes could also be a
sign that communities are simply not well separable. While this may suggest
different things, one explanation may be that we are in fact dealing with
overlapping communities. This could in particular be the case for high degree
nodes. In future work it might be interesting to see to what extent unstable
nodes are in fact members of overlapping communities as found by an
overlapping community detection method xie2013overlapping . Yet another
explanation for unstable nodes that may be valuable to investigate further, is
whether inconsistencies in the obtained clustering are a sign of instability
in the network itself, and are thus related to changes in the network
structure over time. Investigating this further would obviously require
dynamic network data.

##  5 Conclusion

Community detection algorithms are widely used to understand the meso-scale
structure of networks. This work contributed to quantitatively drawing micro-
level conclusions about the community membership of individual nodes. To
achieve this, we proposed community member consistency, which is a node-
specific metric to indicate reliability alongside a division into communities
using consensus clustering.

We applied this metric on the global board interlock network, and showed that
we can distinguish between community core members and fringe members. We
showed that the non-core members are sometimes high-degree nodes, and that the
consistency metric prevents us from viewing these nodes as central in the
community. We found a negative correlation between community membership
consistency and node degree, suggesting that it is more likely for a high-
degree node to jump communities.

The proposed measure may prove useful in other social science contexts where
community detection results are used to gain insight about the role of
individual nodes within a community. Future work may investigate the
generalizability of the method for different types of networks, and the
relationship of consistency scores with higher order structural properties of
the network. Finally, the metric could be used to reliably infer movements of
nodes between communities in a dynamically evolving network.

## References

  * (1) W.K. Carroll, _The making of a transnational capitalist class: Corporate power in the 21st century_ (Zed Books Ltd., London, 2013)
  * (2) B.M. Kogut, _The small worlds of corporate governance_ (MIT Press, Boston, 2012)
  * (3) G.F. Davis, M. Yoo, W.E. Baker, The small world of the American corporate elite, 1982-2001, Strategic organization 1(3), 301 (2003)
  * (4) G.F. Davis, Agents without principles? The spread of the poison pill through the intercorporate network, Administrative Science Quarterly 36(4), 583 (1991)
  * (5) W.K. Carroll, _Corporate power in a globalizing world: A study in elite social organization_ (Oxford University Press, 2004)
  * (6) F.W. Takes, E.M. Heemskerk, Centrality in the global network of corporate control, Social Network Analysis and Mining 6(1), 97 (2016)
  * (7) D. Valeeva, E.M. Heemskerk, F.W. Takes, The duality of firms and directors in board interlock networks: A relational event modeling approach, Social Networks 62, 68 (2020)
  * (8) E.M. Heemskerk, F.W. Takes, The corporate elite community structure of global capitalism, New Political Economy 21(1), 90 (2016)
  * (9) E.M. Heemskerk, F.W. Takes, J. Garcia-Bernardo, M.J. Huijzer, Where is the global corporate elite? A large-scale network study of local and nonlocal interlocking directorates, Sociologica 2, 1 (2016).  DOI 10.2383/85292
  * (10) V.D. Blondel, J.L. Guillaume, R. Lambiotte, E. Lefebvre, Fast unfolding of communities in large networks, Journal of Statistical Mechanics: Theory and Experiment 2008(10), P10008 (2008).  DOI 10.1088/1742-5468/2008/10/P10008
  * (11) V.A. Traag, L. Waltman, N.J. van Eck, From Louvain to Leiden: guaranteeing well-connected communities, Scientific Reports 9(1) (2019).  DOI 10.1038/s41598-019-41695-z
  * (12) M. Rosvall, C.T. Bergstrom, Maps of random walks on complex networks reveal community structure, Proceedings of the National Academy of Sciences 105(4), 1118 (2008)
  * (13) A. Lancichinetti, F. Radicchi, J.J. Ramasco, S. Fortunato, Finding statistically significant communities in networks, PLoS ONE 6(4), e18961 (2011).  DOI 10.1371/journal.pone.0018961
  * (14) M.E.J. Newman, M. Girvan, Finding and evaluating community structure in networks, Phys. Rev. E 69(2), 026113 (2004).  DOI 10.1103/PhysRevE.69.026113
  * (15) B.H. Good, Y.A. de Montjoye, A. Clauset, Performance of modularity maximization in practical contexts, Physical Review E 81(4), 046106 (2010).  DOI 10.1103/PhysRevE.81.046106
  * (16) A. Lancichinetti, S. Fortunato, Consensus clustering in complex networks, Scientific Reports 2(1), 336 (2012).  DOI 10.1038/srep00336
  * (17) A. Tandon, A. Albeshri, V. Thayananthan, W. Alhalabi, S. Fortunato, Fast consensus clustering in complex networks, Physical Review E 99(4), 042301 (2019)
  * (18) L. Nagy, M. Ormos, Friendship of Stock Market Indices: A Cluster-Based Investigation of Stock Markets, Journal of Risk and Financial Management 11(4), 88 (2018).  DOI 10.3390/jrfm11040088
  * (19) O. Sporns, Structure and function of complex brain networks, Dialogues in Clinical Neuroscience 15(3), 247 (2013)
  * (20) V. De Leo, G. Santoboni, F. Cerina, M. Mureddu, L. Secchi, A. Chessa, Community core detection in transportation networks, Physical Review E 88(4) (2013).  DOI 10.1103/PhysRevE.88.042810.  ArXiv: 1304.0141
  * (21) H. Kim, S.H. Lee, P. Holme, Community consistency determines the stability transition window of power-grid nodes, New Journal of Physics 17(11), 113005 (2015).  DOI 10.1088/1367-2630/17/11/113005
  * (22) H. Kim, S.H. Lee, Relational flexibility of network elements based on inconsistent community detection, CoRR abs/1904.05523 (2019).  URL http://arxiv.org/abs/1904.05523
  * (23) M. Seifi, I. Junier, J.B. Rouquier, S. Iskrov, J.L. Guillaume, Stable Community Cores in Complex Networks, Complex Networks 424, 87 (2013).  DOI 10.1007/978-3-642-30287-9“˙10
  * (24) M.A. Riolo, M.E.J. Newman, Consistency of community structure in complex networks, arXiv:1908.09867 [physics] (2019).  DOI 10.1103/PhysRevE.101.052306.  URL http://arxiv.org/abs/1908.09867.  ArXiv: 1908.09867
  * (25) T. Chakraborty, S. Srinivasan, N. Ganguly, S. Bhowmick, A. Mukherjee, Constant communities in complex networks, Scientific Reports 3(1) (2013).  DOI 10.1038/srep01825.  URL http://www.nature.com/articles/srep01825
  * (26) J.P. Gilbert, J. Twycross, From clusters to queries: exploiting uncertainty in the modularity landscape of complex networks, In Proc. 14th Workshop on Mining and Learning with Graphs (MLG) (2018)
  * (27) T.P. Peixoto, Revealing consensus and dissensus between network partitions, arXiv:2005.13977 [physics, stat] (2020).  URL http://arxiv.org/abs/2005.13977.  ArXiv: 2005.13977
  * (28) P.J. Mucha, T. Richardson, K. Macon, M.A. Porter, J.P. Onnela, Community structure in time-dependent, multiscale, and multiplex networks, science 328(5980), 876 (2010)
  * (29) Bureau van Dijk.  Orbis marketing database.  https://orbis.bvdinfo.com/
  * (30) J. Garcia-Bernardo, F.W. Takes, The effects of data quality on the analysis of corporate board interlock networks, Information systems 78, 164 (2018)
  * (31) J. Cárdenas, Are latin america’s corporate elites transnationally interconnected? a network analysis of interlocking directorates, Global Networks 15(4), 424 (2015)
  * (32) S. Fortunato, Community detection in graphs, Physics Reports 486(3-5), 75 (2010).  DOI 10.1016/j.physrep.2009.11.002
  * (33) S. Fortunato, M. Barthelemy, Resolution limit in community detection, Proceedings of the National Academy of Sciences 104(1), 36 (2007).  DOI 10.1073/pnas.0605965104
  * (34) J. Calatayud, R. Bernardo-Madrid, M. Neuman, A. Rojas, M. Rosvall, Exploring the solution landscape enables more reliable network community detection, arXiv:1905.11230 [physics] (2019).  URL http://arxiv.org/abs/1905.11230.  ArXiv: 1905.11230
  * (35) R. de Santiago, L.C. Lamb, in _2016 IEEE Congress on Evolutionary Computation (CEC)_ (IEEE, Vancouver, BC, Canada, 2016), pp. 4618–4625.  DOI 10.1109/CEC.2016.7744379
  * (36) F.W. Takes, W.A. Kosters, B. Witte, E.M. Heemskerk, Multiplex network motifs as building blocks of corporate networks, Applied Network Science 3(1), 1 (2018)
  * (37) R. Lambiotte, M. Rosvall, I. Scholtes, From networks to optimal higher-order models of complex systems, Nature physics 15(4), 313 (2019)
  * (38) J. Xie, S. Kelley, B.K. Szymanski, Overlapping community detection in networks: The state-of-the-art and comparative study, ACM Comput. Surv. 45(4) (2013).  DOI 10.1145/2501654.2501657.  URL https://doi.org/10.1145/2501654.2501657


+ | (M(\widehat{P}(t+1)))^{-1} | \cdot | S(t+1) - \widehat{S}(t+1) | ,  \notag   \\
& + \big| [ M(\widehat{P}(t+1)) ]^{-1} \big| \cdot |\lambda | \cdot
\big| \Theta^\star - \Theta^\star_{(N)} \big| . \notag
\end{align}

By the induction hypothesis, (<ref>),
(<ref>), and Remark <ref>,  the above inequality implies that

\begin{align}
|\boldsymbol{\alpha}(t) - \widehat{\boldsymbol{\alpha}}(t)|
\leq & C \cdot \Big\{ \bar{N} N^{3/2} \max_{1\leq i, k, l \leq N} \Big| \frac{1}{N^3} -  w^\star_k w^\star_l w^\star_i \Big|
\notag \\
& \hspace{1cm} + \bar{N} N^{1/2} \max_{1\leq k, l\leq N} \Big| \frac{1}{N^2} - w^\star_k w^\star_l \Big|
+ |\Theta^\star - \Theta^\star_{(N)}| \Big\}  . \label{|a(t)-hata(t)|est}
\end{align}

We have shown by induction that (<ref>) holds for all $t=0$, $1$, ..., $T-1$,
and therefore (<ref>) follows.

Under the hypothesis of Proposition <ref>, the costs (<ref>) under the controls (<ref>)
and (<ref>), respectively, satisfy the estimate

\begin{align}
\big| L^\star (  \boldsymbol{\alpha} ; \mathcal{D} )
-  L^\star (  \widehat{\boldsymbol{\alpha}} ;  \mathcal{D} )  \big|
\le &  C  \cdot \Big\{ \bar{N} N^3 \max_{1\leq i, k, l \leq N} \Big| \frac{1}{N^3} -  w^\star_k w^\star_l w^\star_i \Big|
+ \bar{N} N^{3/2} \max_{1\leq k, l\leq N} \Big| \frac{1}{N^2} - w^\star_k w^\star_l \Big|
\notag \\
& \hspace{3cm}
+ \bar{N} \max_{1\leq i \leq N} \Big|\frac{1}{N} - w_i^\star \Big|
+ N |\Theta^\star - \Theta^\star_{(N)}| \Big\}  ,
\label{stabilityLw-L1/N}
\end{align}

where $C>0$ is a constant depending on $\lambda$, $\beta$, $\Theta^\star$, $(w_1^\star, ..., w_N^\star)$,
$K_x$, $K_y$ and $T$.

Let $L^\star(\widehat{\boldsymbol{\alpha}}; \overline{1/N} , \mathcal{D})$,
$L^\star( \widehat{\boldsymbol{\alpha}}; w^\star, \mathcal{D})$, and
$L^\star(\boldsymbol{\alpha}; w^\star , \mathcal{D})$ be as defined in
Lemmas <ref>
and <ref>.
The difference $L^\star(\boldsymbol{\alpha}; \mathcal{D}) - L^\star( \widehat{\boldsymbol{\alpha}}; \mathcal{D})$ can be decomposed as

\begin{align}
L^\star(\boldsymbol{\alpha}; \mathcal{D}) - L^\star( \widehat{\boldsymbol{\alpha}}; \mathcal{D})
= L^\star(\boldsymbol{\alpha}; w^\star, \mathcal{D}) - L^\star(\widehat{\boldsymbol{\alpha}}; \overline{1/N}, \mathcal{D})
+ L^\star(\widehat{\boldsymbol{\alpha}}; \overline{1/N} , \mathcal{D})
- L^\star( \widehat{\boldsymbol{\alpha}}; w^\star, \mathcal{D}) ,\notag
\end{align}

and satisfies

\begin{align}
| L^\star(\boldsymbol{\alpha}; \mathcal{D}) - L^\star( \widehat{\boldsymbol{\alpha}}; \mathcal{D}) |
\leq | L^\star(\boldsymbol{\alpha}; w^\star, \mathcal{D}) - L^\star(\widehat{\boldsymbol{\alpha}}; \overline{1/N}, \mathcal{D}) |
+ | L^\star(\widehat{\boldsymbol{\alpha}}; \overline{1/N} , \mathcal{D})
- L^\star( \widehat{\boldsymbol{\alpha}}; w^\star, \mathcal{D}) | . \notag
\end{align}

The desired estimate (<ref>) then follows from the above inequality and (<ref>)
and (<ref>).

Let $L^\star(\widehat{\boldsymbol{\alpha}}; w^\star, \mathcal{D})$ be (<ref>) with
information sharing weights $w^\star=(w_1^\star, ..., w_N^\star)$ and $\Theta(t+1)-\Theta(t)=\widehat{\boldsymbol{\alpha}}(t)$,
and let $L^\star(\widehat{\boldsymbol{\alpha}}; \overline{1/N} , \mathcal{D})$ be (<ref>) with information sharing weights $\overline{1/N}=(1/N, ..., 1/N)$ and $\Theta(t+1)-\Theta(t)=\widehat{\boldsymbol{\alpha}}(t)$.
Then it satisfies

\begin{align}
| L^\star(\widehat{\boldsymbol{\alpha}}; \overline{1/N} , \mathcal{D})
- L^\star( \widehat{\boldsymbol{\alpha}}; w^\star, \mathcal{D}) | \leq C  \cdot
\Big\{ \bar{N} \max_{1\leq i \leq N} \Big|\frac{1}{N} - w_i^\star \Big| + N^{1/2} |\Theta^\star-\Theta^\star_{(N)}| \Big\}
\label{|L(hata,1/N)-L(hata,w)|est} ,
\end{align}

where $C>0$ is a constant depending on $\lambda$, $\beta$, $\Theta^\star$,
$(w^\star_1, \cdots, w^\star_N)$, $K_x$, $K_y$ and $T$.

By (<ref>) and (<ref>), we have

\begin{align}
L^\star(\widehat{\boldsymbol{\alpha}}; \overline{1/N} , \mathcal{D})
- L^\star( \widehat{\boldsymbol{\alpha}}; w^\star, \mathcal{D})
= & \sum_{t=0}^{T-1} \big( |\Theta(t+1) - \Theta^\ast|^2 - |\Theta(t+1) - \Theta_{(N)}^\ast|^2 \big) \notag \\
& + l(\Theta(T), \overline{1/N}; \mathcal{D} ) - l(\Theta(T), w^\star ; \mathcal{D} ) .\notag
\end{align}

We have that

\begin{equation}
\label{|L(hata,1/N)-L(hata,w)|rcest}
\begin{aligned}
&  \Big| \sum_{t=0}^{T-1} \big( |\Theta(t+1) - \Theta^\ast|^2 - |\Theta(t+1) - \Theta_{(N)}^\ast|^2 \big) \Big|
\\
=&   \Big| \sum_{t=0}^{T-1} (\Theta^\star_{(N)} - \Theta^\star)^\top (2 \Theta(t+1) - \Theta^\star - \Theta^\star_{(N)}) \Big| \notag \\
\le & \sum_{t=0}^{T-1} | \Theta^\star_{(N)} - \Theta^\star | \cdot
| 2 \Theta(t+1) - \Theta^\star - \Theta^\star_{(N)}|
\leq C N^{1/2} \cdot  |\Theta^\star_{(N)} - \Theta^\star| ,
\end{aligned}
\end{equation}

\begin{align}
& l(\Theta(T), \overline{1/N}; \mathcal{D} ) - l(\Theta(T), w^\star ; \mathcal{D} )  \notag \\
= &  \sum_{i=1}^N w^\star_i \sum_{j=1}^{|\mathcal{D}_i|}  \Big[ u^{i\top}_j \sum_{k=1}^N w^\star_k \theta_k - y^i_j  \Big]^2
- \sum_{i=1}^N \frac{1}{N} \sum_{j=1}^{|\mathcal{D}_i|}  \Big[ u^{i\top}_j \sum_{k=1}^N \frac{1}{N} \theta_k - y^i_j  \Big]^2
\notag \\
=& \sum_{i=1}^N (w^\star_i - 1/N) \sum_{j=1}^{|\mathcal{D}_i|}  \Big[ u^{i\top}_j \sum_{k=1}^N w^\star_k \theta_k - y^i_j  \Big]^2 \notag \\
&  + \sum_{i=1}^N \frac{1}{N} \sum_{j=1}^{|\mathcal{D}_i|}
\Big[ u^{i\top}_j \sum_{k=1}^N (w^\star_k -1/N) \theta_k   \Big]
\Big[ u^{i\top}_j \sum_{k=1}^N ( w^\star_k + 1/N ) \theta_k - 2 y^i_j  \Big]^2 , \notag
\end{align}

which implies that

\begin{align}
| l(\Theta(T), \overline{1/N}; \mathcal{D} ) - l(\Theta(T), w^\star ; \mathcal{D} ) |
\leq C \bar{N} \max_{1\leq i \leq N} |1/N - w_i^\star| .
\label{|L(hata,1/N)-L(hata,w)|Test}
\end{align}

The estimate (<ref>) then follows from
and (<ref>).

Let $L^\star(\alpha; w^\star, \mathcal{D})$ be (<ref>) with
information sharing weights $w^\star=(w_1^\star, ..., w_N^\star)$ and $\Theta(t+1)-\Theta(t)= \boldsymbol{\alpha}(t)$,
and let $L^\star(\widehat{\boldsymbol{\alpha}}; \overline{1/N} , \mathcal{D})$ be (<ref>) with information sharing weights $\overline{1/N}=(1/N, ..., 1/N)$ and $\Theta(t+1)-\Theta(t)=\widehat{\boldsymbol{\alpha}}(t)$.
Then it satisfies

\begin{align}
& | L^\star(\boldsymbol{\alpha}; w^\star , \mathcal{D})
- L^\star( \widehat{\boldsymbol{\alpha}}; \overline{1/N}, \mathcal{D}) |
\leq
C \cdot  \Big\{ \bar{N} N^3 \cdot \max_{1\leq i, k, l \leq N} \Big| \frac{1}{N^3} -  w^\star_k w^\star_l w^\star_i \Big|
\notag \\
& \hspace{1.5cm}
+\bar{N} N^{3/2} \max_{1\leq k, l\leq N} \Big| \frac{1}{N^2} - w^\star_k w^\star_l \Big|  + \bar{N} \cdot \max_{1\leq i \leq N} \Big| \frac{1}{N} - w_i^\star \Big|
+ N |\Theta^\star - \Theta^\star_{(N)}| \Big\} ,
\label{|L(a,w)-L(hata,1/N)|est}
\end{align}

where $C$ is a constant depending on $\lambda$, $\beta$, $\Theta^\star$,
$(w^\star_1, \cdots, w^\star_N)$, $K_x$, $K_y$ and $T$.

By the similar argument for (<ref>), we have

\begin{align}
L^\star( \widehat{\boldsymbol{\alpha}}; \overline{1/N}, \mathcal{D})
= \Theta^{\star\top}  \widehat{P}(0)  \Theta^\star
+ 2\widehat{S}(0)^\top \Theta^\star + \widehat{r}(0) . \label{ansatzV1/N}
\end{align}

By (<ref>) and (<ref>), the difference $L^\star(\boldsymbol{\alpha}; w^\star, \mathcal{D}) - L^\star( \widehat{\boldsymbol{\alpha}}; \overline{1/N}, \mathcal{D})$ can be written as

\begin{align}
L^\star(\boldsymbol{\alpha}; w^\star, \mathcal{D}) - L^\star( \widehat{\boldsymbol{\alpha}}; \overline{1/N}, \mathcal{D})
= \Theta^{\star\top} ( P(0) - \widehat{P}(0) ) \Theta^\star
+ 2 ( S(0) - \widehat{S}(0) )^\top \Theta^\star + r(0)-\widehat{r}(0) ,
\notag
\end{align}

and by Lemma <ref>, the difference satisfies

\begin{align}
\big| L^\star (  \boldsymbol{\alpha} ; w^\star, \mathcal{D} )
-  L^\star (  \widehat{\boldsymbol{\alpha}} ; \overline{1/N} , \mathcal{D} ) \big|
\le & |\Theta^\star|^2 \cdot |  P(0) - \widehat{P}(0) |
+ 2 | S(0) - \widehat{S}(0) | \cdot | \Theta^\star|
\nonumber
\\
& + | r(0)-\widehat{r}(0) | . \label{|L(a,w)-L(hata,1/N)|leqQudratic}
\end{align}

We claim that $r(0)-\widehat{r}(0)$ has the estimate

\begin{align}
| r(0)-\widehat{r}(0) | \le &  C  \cdot  \Big\{ \bar{N} N^3 \cdot \max_{1\leq i, k, l \leq N} \Big| \frac{1}{N^3} -  w^\star_k w^\star_l w^\star_i \Big|
+\bar{N} N^{3/2} \max_{1\leq k, l\leq N} \Big| \frac{1}{N^2} - w^\star_k w^\star_l \Big|
\notag \\
& \hspace{2cm}
+ \bar{N} \cdot \max_{1\leq i \leq N} \Big| \frac{1}{N} - w_i^\star \Big|
+ N \cdot |\Theta^\star - \Theta^\star_{(N)}| \Big\}  ,
\label{eqn:estrw-tilder1/N}
\end{align}

where $C$ is a constant depending on $\lambda$, $\beta$, $\Theta^\star$,
$(w^\star_1, \cdots, w^\star_N)$, $K_x$, $K_y$ and $T$.
Then the desired estimate (<ref>) is established by (<ref>), (<ref>), (<ref>) and (<ref>).

Now we prove the claim (<ref>).
From (<ref>) and (<ref>), we obtain the equation that $\widehat{r}$ satisfies on $0\leq t \leq T$:

\begin{align}
\widehat{r}(t) =  - ( \widehat{S}(t+1) - \lambda \Theta_{(N)}^\star )^\top
[(\lambda+\beta)I_{Np} + \widehat{P}(t+1)]^{-1} \cdot ( \widehat{S}(t+1) - \lambda \Theta_{(N)}^\star )   \\
\hspace{1.1cm}   + \lambda \| \Theta_{(N)}^\star \|_2^2 + \widehat{r}(t+1),
\label{eqnhatr(t)} \\ \widehat{r}(T) = \sum_{i=1}^N (1/N) \sum_{j=1}^{|\mathcal{D}_i|} |y^i_j|^2 .
\end{cases}
\end{align}

Then $r-\widehat{r}$ satisfies the equation on $0\leq t \leq T$

\begin{align}
& r(t) - \widehat{r}(t) \notag \\
= &  r(t+1) - \widehat{r}(t+1) + \lambda (\Theta^\star - \Theta^\star_{(N)}) (\Theta^\star + \Theta^\star_{(N)}) \notag \\
& - (S(t+1) - \lambda \Theta^\star)^\top \big[ (M(P(t+1)))^{-1} - (M(\widehat{P}(t+1)))^{-1} \big] (S(t+1)-\lambda \Theta^\star) \notag \\
& - \big[ S(t+1) - \widehat{S}(t+1) - \lambda (\Theta^\star - \Theta_{(N)}^\star ) \big]
\cdot
\\
\notag
& \qquad
\big[ S(t+1) + \widehat{S}(t+1) - \lambda (\Theta^\star + \Theta_{(N)}^\star ) \big] , \notag \\
& r(T) - \widehat{r}(T) = \sum_{i=1}^N (w_i^\star - 1/N) \sum_{j=1}^{|\mathcal{D}_i|} |y^i_j|^2 . \notag
\end{align}

Inductively, we have

\begin{align}
r(0) - \widehat{r}(0)
= &   r(T) - \widehat{r}(T) + T \lambda (\Theta^\star - \Theta^\star_{(N)}) (\Theta^\star + \Theta^\star_{(N)})   \notag \\
& - \sum_{t=1}^T (S(t) - \lambda \Theta^\star)^\top \big[ (M(P(t)))^{-1} - (M(\widehat{P}(t)))^{-1} \big] (S(t)-\lambda \Theta^\star)   \notag  \\
&  - \sum_{t=1}^T \big[ S(t) - \widehat{S}(t) - \lambda (\Theta^\star - \Theta_{(N)}^\star ) \big]
(M(\widehat{P}(t)))^{-1} \big[ S(t) + \widehat{S}(t) - \lambda (\Theta^\star + \Theta_{(N)}^\star ) \big] . \notag
\end{align}

By Lemma <ref>, we have

\begin{align}
& | r(0) - \widehat{r}(0) | \leq |r(T) - \widehat{r}(T)|
+ T \lambda | \Theta^\star - \Theta^\star_{(N)} | \cdot | \Theta^\star + \Theta^\star_{(N)} |   \notag \\
&  + \sum_{t=1}^T  \big| (M(P(t)))^{-1} - (M(\widehat{P}(t)))^{-1} \big| \cdot
\big| S(t)-\lambda \Theta^\star \big|^2   \notag  \\
&  + \sum_{t=1}^T \big[ | S(t) - \widehat{S}(t) | + \lambda | \Theta^\star - \Theta_{(N)}^\star | \big] \cdot
\big| (M(\widehat{P}(t)))^{-1} \big| \cdot \big| S(t) + \widehat{S}(t) - \lambda (\Theta^\star + \Theta_{(N)}^\star ) \big| .  \label{estrw(0)-tilder1/N(0)}
\end{align}

Then the estimate (<ref>) follows from
(<ref>), (<ref>),
(<ref>), and Remark <ref>.

Under Assumptions <ref> and <ref>, the existence of the regret-optimal algorithm $\theta_{\cdot}$ is implied by Theorem <ref>.  The first claim follows from Proposition <ref> upon noting that the constant “$C_w$” therein is bounded as a function of $w$; whence we take the constant $C$ hidden by $\mathcal{O}$ to be $C\eqdef \sup_{w\in [0,1]^N\,\sum_{i=1}^N\,w_i=1}\, C_w$.  Likewise, the second statement follows directly from Corollary <ref> upon defining the constant hidden by $\mathcal{O}$ as before.

Further investigation of the “symmetrized system” (<ref>) reveals a symmetric form of $\widehat{P}$, which suggests that  $\widehat{P}$ can be decomposed into homogeneous submatrices of lower dimensions.
Specifically, if we decompose the high dimensional $Np\times Np$ matrix $\widehat{P}$ into $N\times N$ submatrices of dimensions $p\times p$ each,  and either exchange two submatrices symmetrically positioned with respect to the diagonal of $\widehat{P}$ or exchange two submatrices on the diagonal, the system (<ref>) is invariant.
This suggests that all the submatrices on the diagonal are homogeneous and all the off-diagonal submatrices are homogeneous.

The solution of (<ref>) has the following submatrix decomposition

\begin{align}
\widehat{P} = \begin{bmatrix} \pi_1 & \pi_2 & \cdots & \pi_2 \\
\pi_2 & \pi_1 & \cdots &\pi_2 \\
\vdots & \vdots & \ddots & \vdots \\
\pi_2 & \pi_2 & \cdots & \pi_1
\end{bmatrix} \in \mathbb{R}^{Np\times Np},
\quad \pi_1 \in \mathbb{R}^{p\times p}, \quad
\pi_2 \in \mathbb{R}^{p\times p} ,
\label{hatPpi12}
\end{align}

and the submatrices $\pi_1$ and $\pi_2$ are uniquely determined by the system

\begin{align}
\begin{cases}
\pi_1(t) =  \beta I_p - \beta^2 \gamma_1(t+1)  ,
\label{eqnpi1pi2}  \\
\pi_2(t) =  - \beta^2 \gamma_2(t+1) ,  \quad 1\leq t \leq T-1 , \\
\pi_1(T) = \pi_2(T) = (1/N^3)\sum_{i=1}^N \sum_{j=1}^{|\mathcal{D}_i|} u^i_j u^{i\top}_j ,
\end{cases}
\end{align}

where $\gamma_1(\cdot)$ and $\gamma_2(\cdot)$ are defined as
(<ref>) and (<ref>).

We argue analogously to <cit.> in deriving the following submatrix decomposition of $\widehat{P}$.

We decompose the $Np\times Np$ identity matrix into $N\times N$ submatrices
$I=(I_{ij})_{1\leq i, j \leq N}$ with each
$I_{ij}\in \mathbb{R}^{p\times p}$.
For each $1\leq i, j \leq N$, by $E_{ij} $we denote the $Np\times Np$ elementary matrix by exchanging the $i$th and $j$th rows of submatrices of the $Np\times Np$ identity matrix $I=(I_{ij})_{1\leq i, j \leq N}$. Note that $E_{ij}=E_{ij}^{-1}=E_{ij}^T$.
Multiplying both sides of (<ref>) from the left by $E_{ij}$ and from the right by $E_{ij}$, we obtain

\begin{align}
& \begin{cases}
E_{ij} \widehat{P}(t) E_{ij}
=  \beta I_{Np} - \beta^2 [(\lambda+\beta ) I_{Np} + E_{ij} \widehat{P}(t+1) E_{ij} ]^{-1} ,  \\
E_{ij} \widehat{P}(T) E_{ij} =  [ (1/N) I_p ,\cdots, (1/N) I_p ]^\top
\Big( \sum_{i=1}^N \frac{1}{N} \sum_{j=1}^{|\mathcal{D}_i|}  u^i_j u^{i\top}_j  \Big)
[ (1/N) I_p , \cdots, (1/N) I_p ] .
\end{cases}   \label{eqnEijtildePEij}
\end{align}

Comparing (<ref>) and (<ref>) reveals that
$\widehat{P}(t)$ and $E_{ij} \widehat{P}(t) E_{ij}$ satisfy the same ODE for all $1\leq i, j \leq N$. This observation implies that

\begin{align}
\widehat{P}_{ii} = \widehat{P}_{jj}, \quad \widehat{P}_{ij} = \widehat{P}_{ji} , \quad \widehat{P}_{ik}= \widehat{P}_{jk}, \quad
\widehat{P}_{ki} = \widehat{P}_{kj}, \quad \forall 1\leq i, j \leq N, \quad \forall k \neq i, j , \notag
\end{align}

and the first assertion of the proposition is proved.

Since $\widehat{P}$ takes the form (<ref>),
it is straight forward to verify that $[(\lambda+\beta)I_{Np} + \widehat{P}]^{-1}$ takes the form

\begin{align}
[(\lambda+\beta) I_{Np} + \widehat{P}]^{-1} = \begin{bmatrix} \gamma_1 & \gamma_2 & \cdots & \gamma_2 \\
\gamma_2 & \gamma_1 & \cdots &\gamma_2 \\
\vdots & \vdots & \ddots & \vdots \\
\gamma_2 & \gamma_2 & \cdots & \gamma_1
\end{bmatrix} , \label{[(lambda+1)I+P]inv}
\end{align}

with $\gamma_1$ and $\gamma_2$ given by (<ref>) and (<ref>).

We substitute (<ref>) and (<ref>) into (<ref>) to obtain the equations (<ref>).

Upon substituting $\widehat{P}$  into (<ref>), we find that the $Np\times 1$ matrix $\widehat{S}$ can be decomposed into homogeneous submatrices of dimensions $p\times 1$ each.

The solution of (<ref>) can be decomposed into submatrices

\begin{align}
\widehat{S}=(\pi_3^\top, \cdots, \pi_3^\top )^\top \in \mathbb{R}^{Np\times 1},
\quad \pi_3 \in \mathbb{R}^{p\times 1} ,
\label{hatSpi3}
\end{align}

and $\pi_3$ satisfies

\begin{align}
\begin{cases}
\pi_3(t) = \beta \big[ \gamma_1(t+1) + (N-1) \gamma_2(t+1)  \big]
( \pi_3(t+1) - \lambda \theta^\star_{(N)} )   , \\
\pi_3(T) = - (1/N^2) \sum_{i=1}^N \sum_{j=1}^{|\mathcal{D}_i|}  u^i_j y^i_j .
\end{cases}   \label{eqnpi3}
\end{align}

We multiply both sides of (<ref>) from the left by $E_{ij}$ defined in the proof of Proposition <ref>,

\begin{align}
E_{ij} \widehat{S}(t) = &  E_{ij} \beta [(\lambda + \beta )I_{Np} + \widehat{P}(t+1)]^{-1} (\widehat{S}(t+1) - \lambda \Theta^\star_{(N)})
\notag \\
= &    E_{ij} \beta [(\lambda + \beta )I_{Np} + \widehat{P}(t+1)]^{-1} E_{ij} E_{ij}(\widehat{S}(t+1) - \lambda \Theta^\star_{(N)}) \notag \\
= &    \beta [(\lambda + \beta )I_{Np} + E_{ij} \widehat{P}(t+1)E_{ij}]^{-1}  ( E_{ij}\widehat{S}(t+1) - \lambda \Theta^\star_{(N)})
\label{EijtildeS1/N(t)}
\end{align}

\begin{align}
E_{ij}\widehat{S}(T) = &  - E_{ij}[ (1/N) I_p, \cdots, (1/N) I_p ]^\top \sum_{i=1}^N \frac{1}{N} \sum_{j=1}^{|\mathcal{D}_i|}  u^i_j y^i_j \notag \\
= &  - [ (1/N) I_p, \cdots, (1/N) I_p ]^\top \sum_{i=1}^N \frac{1}{N} \sum_{j=1}^{|\mathcal{D}_i|}  u^i_j y^i_j .
\label{EijtildeS1/N(T)}
\end{align}

From (<ref>) and (<ref>), we have that $E_{ij}\widehat{S}$ also satisfies (<ref>) for all
$1\leq i, j \leq N$. This proves that all submatrices of $\widehat{S}=(\widehat{S}_i)_{1\leq i \leq N}$ are equal on $0\leq t \leq T$.
We further substitute (<ref>), (<ref>) and
$\widehat{S} = [\pi_3^\top, \cdots, \pi_3^\top]^\top$ into (<ref>) to obtain (<ref>).

Fix a data set $\mathcal{D}$ and assume that (<ref>) holds. Then the computational complexity of computing the sequence $\big( \theta(t) \big)_{t=0}^T$ by (<ref>) is
$\mathcal{O}(Tp^2 \max\{N, p^{0.373}\})$.

Complexity of computing $\pi_1(T)$, $\pi_2(T)$, and $\pi_3(T)$ is $O(N^2 p^2)$

Computing $u^i_j u^{i\top}_j$ has complexity $O(p^2)$ by Lemma <ref>-(iii) and computing the sum

$\sum_{i=1}^N \sum_{j=1}^{|\mathcal{D}_i|} u^i_j u^{i\top}_j$ has a complexity of $O( N^2 p^2)$ by Lemma <ref>-(i).
Moreover, multiplying the $p\times p$ matrix $\sum_{i=1}^N \sum_{j=1}^{|\mathcal{D}_i|} u^i_j u^{i\top}_j$ by the scalar $1/N^3$ has complexity $O(p^2)$. Hence the computing $\pi_1(T)$ and $\pi_2(T)$ has complexity $\mathcal{O}(N^2 p^2)$.
Computing the product $u^i_j y^i_j$ has a complexity of $O(p)$ by Lemma <ref>-(iii), and summing $\sum_{i=1}^N \sum_{j=1}^{|\mathcal{D}_i|} u^i_j y^i_j$ has complexity $O(N^2 p)$ by Lemma <ref>-(i). Multiplying the $p\times 1$ vector $\sum_{i=1}^N \sum_{j=1}^{|\mathcal{D}_i|} u^i_j y^i_j$
by the scalar $1/N^2$ has a complexity of $O(p)$.
Therefore computing $\pi_3(T)$ has complexity $O(N^2 p)$, and the complexity of computing $\pi_1(T)$, $\pi_2(T)$, and $\pi_3(T)$ is $\mathcal{O}(N^2 p)$.

Complexity of Computing $\gamma_1(T)$ and $\gamma_2(T)$ is $O(p^{2.373})$

With $\pi_1(T)$ and $\pi_2(T)$ obtained, we can compute $\gamma_1(T)$ and $\gamma_2(T)$ by (<ref>) and (<ref>).
From (<ref>) and (<ref>), computing $\gamma_1(\cdot)$ and $\gamma_2(\cdot)$ from $\pi_1(\cdot)$ and $\pi_2(\cdot)$ involves multiplication and addition of $p \times p$ matrices, scalar multiplication of $p\times p$-dimensional matrices, multiplication of a $p\times p$ matrix and a $p\times 1$ vector, and inversion of a $p \times p$ matrix.
By Lemma <ref>, multiplication of two $p\times p$ matrices has the dominant complexity of $\mathcal{O}(p^{2.373})$ among the above matrix operations.
Moreover, inverting a $p\times p$ matrix has complexity $\mathcal{O}(p^{2,373})$.
Hence, computing $\gamma_1(T)$ and $\gamma_2(T)$ has a complexity of $O(p^{2.373})$.

Complexity of computing $\pi_1(t)$, $\pi_2(t)$, $\pi_3(t)$, $\gamma_1(t)$ and $\gamma_2(t)$ for $t=T-1$, $T-2$, ..., $1$ has complexity $\mathcal{O}(T p^{2.373})$.

Similar to computing $\gamma_1(T)$ and $\gamma_2(T)$, computing $\gamma_1(t)$ and $\gamma_2(t)$ from $\pi_1(t+1)$ and $\pi_2(t+1)$ has complexity $\mathcal{O}(p^{2.373})$.
According to (<ref>), computing $\pi_1(t)$ and $\pi_2(t)$ from $\gamma_1(t+1)$ and $\gamma_2(t+1)$ involves scalar multiplication and addition along diagonal of $p\times p$ matrices, and therefore has complexity $O(p^2)$ by Lemma <ref>-(i) and (ii),
According to (<ref>), computing $\pi_3(t)$ from $\gamma_1(t+1)$, $\gamma_2(t+1)$, and $\pi_3(t+1)$ involves scalar multiplication and addition of $p\times p$ matrices, scalar multiplication and addition of $p\times 1$ matrices,
and multiplication of a $p\times p$ matrix with a $p\times 1$ matrix. By Lemma <ref>, the dominant complexity of these operations is $\mathcal{O}(p^2)$.
Summing up the above argument, computing $\pi_1(t)$, $\pi_2(t)$, $\pi_3(t)$, $\gamma_1(t)$ and $\gamma_2(t)$ for each $t$ has a complexity of $\mathcal{O}(p^{2.373})$, and therefore has a complexity of $\mathcal{O}(T p^{2.373})$ for all $t=T-1$, $T-2$,..., $1$.

The Cost of Computing Each $\Theta(t)$ is $O(Tp^2 \max\{N, p^{0.373}\})$.

By (<ref>), the cost of updating from $\Theta(t)$ to $\Theta(t+1)$ is equal to the complexity of computing $\widehat{\boldsymbol{\alpha}}(t)=(\widehat{\alpha}_1^\top(t), \cdots \widehat{\alpha}_N^\top(t))^\top$ for $t=0, 1, ..., T-1$.

By (<ref>), $\widehat\alpha_i(t)$ for all $i=1$, ..., $N$ share the common term

\begin{align}
& - \big\{ \gamma_1(t+1) \pi_2(t+1) + \gamma_2(t+1) [ \lambda I_p + \pi_1(t+1) + (N-2)\pi_2(t+1) ] \big\} \sum_{k=1}^N \theta_k(t)
\notag \\
& - \big[ \gamma_1(t+1) + (N-1) \gamma_2(t+1) \big] (\pi_3(t+1) - \lambda \theta^\star_{(N)}) ,  \notag
\end{align}

and computing the common term involves matrix multiplication, addition, and scalar multiplication of $p\times p$ matrices,
matrix addition and scalar multiplication of $p\times 1$ matrices,
and multiplication of a $p\times p$ matrix and a $p\times 1$ matrix.
By Lemma <ref>, these operations have complexity $O(Np + p^{2.373})$, where $Np$ is due to adding the $N$ $p$-dimensional vectors $\sum_{k=1}^N \theta_k(t)$, and $p^{2.373}$ is due to multiplication of two $p\times p$ matrices by a CW-like algorithm.

Computing the individual terms

\begin{align}
- (\gamma_1(t+1) - \gamma_2(t+1) ) (\lambda I_p + \pi_1(t+1) - \pi_2(t+1) ) \theta_i(t) \notag
\end{align}

for $\widehat\alpha_i(t)$, $i=1$, ..., $N$ involves addition, scalar multiplication, and matrix multiplication of $p\times p$ matrices, and multiplication of a $p\times p$ matrix and a $p\times 1$ matrix.
By Lemma <ref>, these operations have complexity of $\mathcal{O}(p^{2.373} + Np)$, where $p^{2.373}$ is due to multiplication of two $p\times p$ matrices by a CW-like algorithm and $Np$ is due to multiplying a $p\times p$ matrix by the $p$-dimensional vector $\theta_i(t)$ for $i=1$, ..., $N$.
Hence the complexity of computing $\widehat{\boldsymbol{\alpha}}(t)$ for $t=0, 1, ..., T-1$ is $\mathcal{O}(T p^2\max\{N, p^{0.373} \} )$.

The complexity of computing $(\Theta(t))_{t=0}^T$ is $\mathcal{O}(T p^2 \max\{N,p^{0.373}\})$

Looking over all computations involved, we deduce that the complexity of computing the sequence
$(\Theta(t))_{t=1}^T$ starting from $\Theta(0)=\Theta^\star$ has a complexity of $\mathcal{O}(T p^2 \max\{N,p^{0.373}\})$.

We may now deduce Theorem <ref> and Theorem <ref>.

The result directly follows from Theorem <ref> and Corollary <ref>.

Direct consequence of Propositions <ref> and <ref>.

§ BACKGROUND

In this paper, we consider regret-optimal memoryless training dynamics for finite-rank kernel ridge regressors (fKRR) trained from $N$ finite datasets drawn from $N$ (possibly) different data-generating distributions.
We are considering a scenario in which these datasets can originate from $N$ distinct tasks or be adversarially generated perturbations of the initial dataset, and we aim for our fKRR to exhibit robustness towards them.

Any continuous feature map $\phi:\mathbb{R}^d\rightarrow \mathbb{R}^p$, induces a hypothesis of fKRR $f_{\theta}:\mathbb{R}^d\rightarrow \mathbb{R}$ each of which is uniquely determined by a trainable parameter $\theta\in \mathbb{R}^p$ via

\begin{equation}
\label{eq:FRKR 1}
\end{equation}

where all vectors are represented as column-vectors and not row vectors.

The hypothesis class $\mathcal{H}$ possesses a natural reproducing kernel Hilbert space (RKHS) structure with inner-product given for $f_{\theta},f_{\tilde{\theta}}\in \mathcal{H}$ by $\langle f_{\theta},f_{\tilde{\theta}}\rangle_{\phi}\eqdef \sum_{k=1}^p\, \theta_k\tilde{\theta}_k$.  This RKHS structure suggests an optimal selection criterion to decide which hypothesis in $\mathcal{H}$ best describes a single training set $\mathcal{D}_1\eqdef \{(x^1_j,y^1_j)\}_{j=1}^{S^1}$ of $S^1\in \mathbb{N}_+$, by solving the penalized least-squares problem

\begin{align}
\label{eq:FRKR 2}
\theta^\star_1 \in \argmin_{\theta \in \mathbb{R}^p } \big\| \Phi(x^1) \theta  - y^1  \big\|_2^2
+ \kappa \big\| \theta \big\|_2^2 ,
\end{align}

\begin{align}
\Phi(x^1) \eqdef
\big( \phi(x^1_1), \
\phi(x^1_2), \ \cdots , \
\phi(x^1_{S^1}) \big)^\top \in \mathbb{R}^{S^1 \times p} , \
y^1 \eqdef (y^1_1, y^1_2, \cdots, y^1_{S^1})^\top
\in \mathbb{R}^{S^1} , \notag
\end{align}

and $\kappa>0$ is a fixed hyperparameter.  In this classical case, the Representer Theorem <cit.> states that the optimal choice of $f_{\theta}$ to the convex optimization problem (<ref>) is parameterized by

\begin{equation}
\label{eq:loss_one_dataset}
\theta^\star_1 =
( \Phi^\top(x^1) \Phi(x^1)
+ \kappa I_p )^{-1}
\Phi^\top(x^1) y^1 ,
\end{equation}

Alternatively, the optimal parameter choice $\theta^\star_1$ can be arrived at via gradient descent since (<ref>) has a strictly convex loss with a Lipschitz gradient.
The training of fKRR on a single dataset is very-well understood.  Likewise, other aspects of fKRR are well understood; namely, their statistical properties <cit.>, their in-sample behaviour in <cit.>, and even the approximation power and risk of randomly generated fKRR are respectively known <cit.> and <cit.>.

Using the fKRR (<ref>), the joint terminal time objective (<ref>) simplifies to

\begin{align}
\label{eq:terminal_time_objective__fKRR}
\begin{aligned}
l(\theta_1,\dots,\theta_N, w;\,\mathcal{D} )
\eqdef &
\sum_{i=1}^N
\biggl(
\sum_{j=1}^{S_i}
\big|
\langle
\theta^{w}
\rangle - y^i_j  \big|^2
\biggr)
\\
% \,\,
\mbox{ s.t. }
\,%\,
\theta^w\eqdef & \sum_{i=1}^N \theta_i
\end{aligned}
\end{align}

where $\langle\cdot,\cdot\rangle$ denotes the Euclidean inner-product, $u^i_j\eqdef \phi(x^i_j)$ and, as in (<ref>), $w = (w_1, \cdots, w_N) \in [0,1]^N$ with $\sum_{i=1}^N\,w_i=1$.