remarkRemark assumptionAssumption defnDefinition hypothesisHypothesis Graph
Continual LearningR. Krishnan, and P. Balaprakash

# Learning Continually on a Sequence of Graphs – The Dynamical System
Way††thanks: Submitted to the editors 5/14/2023.

Krishnan Raghavan Mathematics and Computer Science, Argonne National
Laboratory<EMAIL_ADDRESS>Prasanna Balaprakash Oak Ridge National
Laboratory<EMAIL_ADDRESS>
###### Abstract

Continual learning (CL) is a field concerned with learning a series of inter-
related task with the tasks typically defined in the sense of either
regression or classification. In recent years, CL has been studied extensively
when these tasks are defined using Euclidean data– data, such as images, that
can be described by a set of vectors in an n-dimensional real space. However,
the literature is quite sparse, when the data corresponding to a CL task is
nonEuclidean– data , such as graphs, point clouds or manifold, where the
notion of similarity in the sense of Euclidean metric does not hold. For
instance, a graph is described by a tuple of vertices and edges and
similarities between two graphs is not well defined through a Euclidean
metric. Due to this fundamental nature of the data, developing CL for
nonEuclidean data presents several theoretical and methodological challenges.
In particular, CL for graphs requires explicit modelling of nonstationary
behavior of vertices and edges and their effects on the learning problem.
Therefore, in this work, we develop a adaptive dynamic programming viewpoint
for CL with graphs. In this work, we formulate a two-player sequential game
between the act of learning new tasks (generalization) and remembering
previously learned tasks (forgetting). We prove mathematically the existence
of a solution to the game and demonstrate convergence to the solution of the
game. Finally, we demonstrate the efficacy of our method on a number of graph
benchmarks with a comprehensive ablation study while establishing state-of-
the-art performance.

###### keywords:

Continual learning, dynamic programming, vertex edge random graph, optimal
control, Stackelberg Equillibrium

68T05, 37N35, 91A99

##  1 Introduction

The problem of Continual learning (CL) when the tasks are made up of a
collection of graphs is referred as graph continual learning (GCL). GCL is
illustrated on the left of Fig. 1 where the complete interval is divided into
three tasks. Each task is signified by a learning problem (graph
classification, node classification, regression of graphs or link prediction)
on a collection of a graphs. The goal at the onset of the first task is train
a graph neural network (a neural network that takes graphs as input) to
achieve perfect performance on the first task.

Figure 1: Illustration of the GCL problem. At the end of each task interval, a
collection of graphs is obtained. These tasks associated with a cost function
forms a task. The illustration provides three tasks, the first task is
obtained at $\Delta~{}t$, the second at $t_{1}$ and the third task at $t_{2}.$
Each subsequent task may have new edges or new vertices. The notation,
$\mathbf{t}_{2}$ indicates the collection of all tasks in the interval
$[0,t_{2}].$

After the first tasks is finished, another task is observed and we seek to
perform the second task well while remembering the first task. However, as
this second task may present new vertices and/or edges along with new edge
features and/or vertex features, updating the model naively using the second
task will reduce the models’ effectiveness on the first task (previous task)
due to a phenomenon known as catastrophic forgetting [16]. This behaviour
highlights an unusual dilemma in the CL domain, known as the stability-
plasticity dilemma [4], where a model in pursuit of learning new experiences
(generalize to new tasks) loses long-term memory (remember previous tasks).
This dilemma provides a natural objective for GCL: balance forgetting and
generalization. To facilitate this balance and achieve improved CL performance
on graph tasks one must model the dynamics between forgetting and
generalization – something the literature does not do, more on this in section
Section 1.1

The first work to formalize these notion of balance in CL was presented in
meta-experience replay (MER) [22], where the balance between forgetting and
generalization is enforced with hyperparameters. Our prior work in [14, 21]
attempted to take an alternative adaptive dynamic programming viewpoint of CL
to model the this balance and its dynamics with changing tasks. However, both
[22] and our prior work in [14, 21] does not naturally extend to _graph neural
network_ (neural networks that are specifically designed to take graphs as
inputs [23]). In recent years, graph neural networks (GNNs) have facilitated
unprecedented efficiency [2, 31, 23] for datasets with graph inputs. However,
much of this research involves cases when all the training graphs are
available upfront. In many applications, however, graphs are observed in
sequence, and the distribution of the graphs is nonstationary [25]. Thus, we
must train the GNN to adapt to the sequential nature of graph generation.
While the GCL literature is sparse, several methods [34, 17, 8, 35, 28] have
been proposed in recent years. There are two key issues with the current GCL
literature, first, none of the methods in the GCL literature model the
dynamics introduced into the GCL problem by the non-stationarity in graphs.
Furthermore, the balance between generalization and forgetting and these
methods are not modeled in any prior work and despite promising initial
advances, the current GCL methods [34, 17, 8, 35, 28] do not provide any
theoretical characterization of GCL.

###  1.1 Prior work on GCL

A rather complete and recent survey of continual learning when graphs are
chosen as inputs is provided in [33, 7]. It can be seen from the survey that
the prior work in GCL methods is sparse and the existing GCL methods can be
grouped into three classes, representation learning strategies [34, 8, 28,
24], regularization strategies [17], and Replay-based strategies [35].

Representation learning strategies [34, 8, 28, 24], focus on learning
representations across tasks to enable CL. For instance, Galke et al. [8]
incrementally learn unseen classes by estimating the change in the graph
distribution characterized by the node features. Wang et al. [28] translate a
GNN to a feature graph network and apply CL method developed for convolutional
neural network (CNN). The work in [24] seeks to build a context graph to model
connections and consolidate information across tasks and demonstrates
performance on image classification problems. The method in [24] does not
provide any evidence for being directly relevant to GCL since all their
experiments is on image data. Zhang et al. [34] propose a hierarchical
prototype network and provide certain theoretical insights. In particular,
Theorem 1 provides an upper bound on the number of prototypes, and Theorem 2
quantifies the prototype changes due to new tasks. Furthermore, other recent
works that utilize representation learning strategies includes SGNN-GR [29]
that identifies nodes in the network that are perturbed by the repeated
training and retrains them; and MSCGL [3] that seeks to obtain an optimal
network architecture for each task through automated neural architecture
search.

Regularization strategies [17]: The key idea behind regularization strategies
is to introduce constraints to the weights/output of the network such that the
forgetting that is incurred because a new task is minimized. The idea of
regularization alleviates the need to construct different architectures for
each problem. However, such a process is governed by preascertained
hyperparameters that are more often than not blindly selected without the
presence of past experiences (previous tasks). For example, without the
information from previous tasks, methods such as [17] solely focus on
increasing plasticity (resistance to change due to the presence of a new task)
in the network.

Replay-based strategies [35]: The plasticity imposed by regularization
strategies in [17] is obviated by ER-GNN [35], where five pooling mechanisms
are specifically developed to aggregate information with careful attention to
the previous task through the use of an experience replay mechanism. ER-GNN
[35] empirically studied the effectiveness of these pooling techniques and
demonstrated superior performance on vertex classification in the CL setting.
However, no attempt was made to ascertain balance required for efficient CL,
nor does ER-GNN provide any theoretical insights. In summary, a key gap in the
literature is the lack of theoretical foundations that enable the study and
analysis of GCL for a variety of graph tasks involving dynamic graphs without
the need for building specific architectures for different applications [17,
35] or blindly setting hyper-parameters [17].

It is important to note from the the summary of prior work on GCL and the
recent surveys [33, 7] that; while rudimentary investigations have been
performed and several methods have been proposed, there are two fundamental
oversights in the field of continual learning with Graphs. First, there is no
characterization of the dynamics of learning, that is, how does the solution
to the CL problem change when new tasks are introduced. Second, there is no
study, theoretical or empirical, that proves the feasibility of a new balance
point between forgetting and generalization whenever a shift in the input
distribution is observed.

To obviate these shortcomings, we develop the theoretical foundations of GCL
where we model the progression of value function (the best CL cost over all
possible tasks) with respect to tasks in the GCL setting as a dynamical
system. To this end, we extend our prior work in [14, 21] to dynamic graphs
and present our insights both when tasks are observed continuously and when
the tasks are observed discretely. Towards this pursuit, we model the non-
stationarity in graphs through continuous (CT) and discrete (DT) stochastic
processes leveraging the vertex edge random graphs (VERGs) [1] formalism.
Subsequently, we define the GCL task as a realization of VERG with the
corresponding loss function. We utilize an adaptive dynamic programming
viewpoint to formulate GCL, wherein the GCL cost ($L$) over all the possible
tasks (domain of the CL problem) is given by an integral of the generalization
(cost on the new task) and forgetting cost (cost on all previous tasks) over
the domain. The solution to the GCL problem is then be obtained by minimizing
$L$ to get the value function $L^{*}.$ However, obtaining this solution is not
straightforward because much of the domain is unknown. To circumvent this
issue, we utilize Bellman’s principle of optimality and derive an ordinary
differential equation (ODE) which models the progression of value function as
a function of tasks. That is, models, how each new task affects the value
function. To solve the ODE, we discretize the domain and formulate a
sequential two player min-max game with the goal of achieving balance between
generalization and forgetting—one player maximizes generalization, and another
minimizes forgetting. We solve this game utilizing mini-batch stochastic
gradient ascent-descent.

We present a comprehensive theoretical analysis that proves the existence of
at least one balance point between these two players for each new task
(Section 4.1). We also show convergence of our algorithm (Section 4.2). We
demonstrate these results while considering the effect of dynamic graph with
assumptions of Lipschitz continuity. To substantiate our approach empirically,
we demonstrate a 44% improvement over the state of the art on vertex
classification in a CL setting. Furthermore, we use large-scale hyperparameter
search experiments to demonstrate the robustness of our method to different
hyperparameters and initialization of weights on the graph classification. We
also present an ablation study and demonstrate a 21% improvement over the
naive experience replay method.

###  1.2 Summary of Contributions

In summary, we build on [14, 21] to initiate the investigation into, how tasks
impact the graph continual learning problem when the input is provided by
graphs. Our work provides the first theoretical characterization and analysis
of the balance between forgetting and generalization in the GCL setting where
we model the non-Euclidean nature of the graphs including the stochasticity
presented by the dynamic nodes, the edge attributes and edge connectivity
(including dynamic connectivity) and introduce a theoretical framework to
study this. Furthermore, utilizing this framework, we develop a simple
methodology that can be shown theoretically to converge and provides empirical
advantages. Finally, we provide a comprehensive ablation study where we
illustrate the effect of changes in hyperparameter configurations, which is
quite unique in the ML setting.

###  1.3 Notations

We denote scalars by lowercase letters, i.e., $x,$ vectors by lowercase bold
letters, i.e., $\mathbf{x}.$ A matrix is denoted by uppercase bold alphabets,
i.e., $\mathbf{X}$ and use $\mathbf{w}$ to collectively denote a column vector
of all parameters. Let the interval $\mathbf{\Omega}=[0,\Omega]$ for
$\Omega>0$ represent the sample space for all tasks instances (the total
interval in which tasks may be observed) and $\mathbb{R}^{+}$ referring to the
set of real positive numbers. Task intervals in $\Omega$ are given by
$\mathbf{t}\subseteq\mathbf{\Omega}\;|\;\mathbf{t}=[0,t].$ In a special case,
when $\mathbf{\Omega}\subset\mathbb{N},$ with $\mathbb{N}$ denoting the set of
natural numbers, we will use $k$ to denote discrete task instances in
$\mathbf{\Omega}$. Any partial derivatives are given by $\partial_{y}(x)$—the
partial derivative of $x$ with respect to $y.$ An asymptotic value is
indicated by a superscript $N$, optimal value by a superscript $*$ and
iterations are indicated by a superscript in parenthesis. For instance,
$L^{*}_{t}$ refers to the optimal value of $L$ with respect to the task $t$
and $\mathbf{w}^{(n)}$ provides the value of $\mathbf{w}$ after $n$
iterations.

###  1.4 Outline

There are two major goals in this paper. First, we seek to derive the dynamics
of the GCL value function. Next, we derive our two player min-max game to
provide updates to a neural network to find the balance between generalization
and forgetting. We begin with preliminaries from [1] in and describe a task in
GCL in Section 2. Next, we describe the dynamical system modelling of GCL in
Section 2.4 and Section 2.5 and formulate the two player game and provide the
algorithm in Section 3. The theoretical analysis presented in Section 4 and we
substantiate our contributions empirically in Section 5.

##  2 Graph Continual Learning

GCL is the problem of learning a sequence of tasks, where each task is defined
as a collection of graphs associated with a loss function according to a GNN.
Therefore, we must first define a collection of graphs that captures the non-
stationarity in vertices and edges within a graph. In typical literature, a
collection of graphs $G\in\mathcal{G}(k)$ for $k\in\mathbf{\Omega}$ is a tuple
of vertices $\mathbf{V}\subset\boldsymbol{\mathcal{V}}$, edges $\mathbf{E}$,
and features $\mathbf{F}.$ This collection of graphs is typically considered
as samples from random graphs – in particular, a probability space
$(\mathbf{\Omega},\sigma(\mathbf{\Omega}),\mathbb{P}).$ Here,
$\mathbf{\Omega}$ is a sample space equipped with a sigma algebra
$\sigma(\mathbf{\Omega})$ and $\mathbb{P}$ is a probability space.
Furthermore, $\mathbf{V}\subset\mathbb{N}$ is the vertex set,
$\mathbf{E}\in\mathbb{R}^{|\mathbf{V}|\times|\mathbf{V}|}$ is the edge set
with $\mathbf{\mathcal{X}}\subset\mathbb{R}^{n}$ being the sample space for
the features $\mathbf{F}.$ In the context of GCL, graphs within the collection
$\mathcal{G}(k)$ can be dynamic for different tasks: they can have different
vertices, edges, and corresponding features. We formalize this dynamic
behavior using vertex-edge random graph (VERG) [1] where both the vertices and
edges of a random graph are formalized as stochastic processes.

###  2.1 VERG for GCL

According to [1], a vertex edge random graph (VERG) is a probability space
over $(\mathbf{x},\phi)$ graphs. Subsequently, an $(\mathbf{x},\phi)$ graph is
a tuple of vertex features, represented by $\mathbf{x}$ and edge features,
represented by $\phi.$ The stochastic processes $\mathbf{x}$ and
$\mathbf{\phi}$ can be thought as measurable functions the assign real values
to vertex and an edge. Consequently, a VERG is of the form
$(\mathcal{G}_{\mathbf{V}},P)$, where $\mathcal{G}_{V}$ is a collection of
$(\mathbf{x},\phi)$ graphs with a probability measure $P.$

To adapt this generic notion of VERG must be adapted to GCL we let
$\boldsymbol{\mathcal{V}}$ be the set of all vertices over which the graph
data can be collected and that $\boldsymbol{\mathcal{V}}$ is endowed with a
compact neighborhood topology. Then, for each interval $[t,t+\Delta
t]\subset\mathbf{\Omega}|t,\Delta t\in\mathbf{\Omega},$ the collection of
graphs is defined over a particular task dependent vertex set
$\mathbf{V}(t)\subset\boldsymbol{\mathcal{V}}$ such that VERG for GCL is
formally given as a probability space over dynamic graphs.

######  Definition 1 (VERG for GCL).

For any $t\in\mathbf{\Omega},v\in\boldsymbol{\mathcal{V}}$ define
$\mathbf{x}(v,t):\boldsymbol{\mathcal{V}}\times\mathbf{\Omega}\rightarrow\mathbb{R}^{n}$
and
$\phi:\boldsymbol{\mathcal{V}}\times\boldsymbol{\mathcal{V}}\times\mathbf{\Omega}\rightarrow\mathbb{R}.$
Then, $\mathbf{x}_{\mathbf{V}}(t)=\\{\mathbf{{x}}(v,t),\quad\forall
v\in\mathbf{N}_{v},\forall\mathbf{N}_{v}\subset\mathbf{V}(t)\\}_{\mathbf{V}(t)}$
is the vertex stochastic process with
$\phi_{\mathbf{V}}(t)=\\{\phi(i,j,t),\forall
i,j\in\mathbf{N}_{v},\mathbf{N}_{v}\subset\mathbf{V}(t)\\}_{\mathbf{V}(t)}$
being the edge stochastic process. Then, VERG is a probability space of the
form $(\mathcal{G}_{\mathbf{V}}(t),P_{\mathbf{x}\times\phi})$ where
$\mathcal{G}_{\mathbf{V}}(t)$ is a collection of a graphs
$\left(\mathbf{x}_{\mathbf{V}}(t),\phi_{\mathbf{V}}(t)\right)$ with
probability measure $P_{\mathbf{x}\times\phi}.$

###  2.2 Learning Objective:

When dynamic graphs are generated, the associated problem is to learn an
unknown function
$g(.):\mathbb{R}^{n}\times\mathbb{R}\rightarrow\mathbb{R}^{p}$ such that
$y(t)=\rho(\mathbf{x}(t),\phi(t))$ with $y(t)=\partial_{t}(.)$ for regression
and $y(t)$ representing probabilities in the context of classification (node
and edge classification as well as link prediction). We seek to approximate
this unknown function using a graph neural network (GNN) parameterized by some
weight parameters. Therefore, we define a compact parameter space
$\mathcal{W}\subset\mathbb{R}^{m}$ and a vector-valued function that provides
an $\mathbb{R}^{m}$ weight vector for each $t\in\mathbf{\Omega}$ where
$\mathbf{w}(t):\mathbf{\Omega}\rightarrow\mathcal{W}.$ The vector-valued
function can be essentially thought as a policy that defines the set of rules
according to which a weight vector may be obtained corresponding to each $t$
such that $y(t)=g(.,.,\mathbf{w}(t))$ represents the GNN. Then, we define a
loss function $\ell:\mathbb{R}^{n}\rightarrow\mathbb{R},$ which provides the
learning objective.

###  2.3 GCL task

The GCL task is given as

######  Definition 2 (GCL task in the continuous sense).

For $t,\Delta t\in\mathbf{\Omega}$, define the interval $[t,t+\Delta t]$ and
let $(\mathcal{G}_{V}(t),P_{\mathbf{x}(t)\times\phi(t)})$ represent a VERG
associated with GCL. Denote the GNN model as
$g(.,.,\mathbf{w}(t)):\mathbf{\Omega}\rightarrow\mathbb{R}^{n}$ with a loss
function given as $\ell:\mathbb{R}^{p}\rightarrow\mathbb{R}.$ Let
$J(\mathbf{x}([t,t+\Delta t]),\phi([t,t+\Delta t]),\mathbf{w}([t,t+\Delta
t]))=\int_{\tau=t}^{t+\Delta
t}\ell(\mathbf{x}_{\mathbf{V}}(\tau),\phi_{\mathbf{V}}(\tau),\mathbf{w}(\tau))]$
be the forgetting and generalization cost over the interval $[t,t+\Delta t].$
Then, a GCL task $\mathcal{T}([t,t+\Delta t])$ is described by the tuple

(1) $\Big{(}\mathbf{x}([t,t+\Delta t]),\phi([t,t+\Delta
t]),J(\mathbf{x}([t,t+\Delta t]),\phi([t,t+\Delta t]),\mathbf{w}([t,t+\Delta
t]))\Big{)}$

with $\mathbf{x}([t,t+\Delta
t])=\\{\mathbf{x}_{\mathbf{V}}(\tau)\forall\tau\in[t,t+\Delta
t]\\}_{\mathbf{V}(t)}$ and $\phi([t,t+\Delta
t])=\\{\mathbf{\phi}_{\mathbf{V}}(\tau)\forall\tau\in[t,t+\Delta
t]\\}_{\mathbf{V}(t)}$

A GCL task has been defined as a stochastic process over $\mathbf{V}(t)$ of
$\boldsymbol{\mathcal{V}}.$ As a GNN operates by performing operations in a
neighborhood and the vertex set need not be fixed and the loss function
corresponding to a GNN is simply an integral across all neighborhoods in the
vertex set $\mathbf{V}(t)$. As $\boldsymbol{\mathcal{V}}$ is endowed with a
compact neighborhood topology, the vertex set is decomposable into overlapping
neighborhood and the cost $J(\mathbf{x}([t,t+\Delta t]),\phi([t,t+\Delta
t]),\mathbf{w}([t,t+\Delta t]))$ can be defined as an integral over all vertex
sets in the interval $[t,t+\Delta t]$. This key feature in the formulation of
a task allows the flexibility to consider distinct vertex sets for distinct
graphs is not present in other GCL methods in the literature. The only
restriction in this setting is that the total number of vertices in a graph
may not exceed the cardinality of $\boldsymbol{\mathcal{V}}.$

For simplicity of notations, we will denote the task as
$\mathcal{T}_{[t,t+\Delta t]}$ which is described by the tuple
$\left((\mathbf{x},\phi)_{[t,t+\Delta t]},J_{[t,t+\Delta
t]}(\mathbf{x},\phi,\mathbf{w})\right)$ where the subscript indicates the
interval over which the task is defined. This notation, easily extends to a
collection of tasks. For instance, all the tasks in the interval $[0,t]$ are
collectively provided by $\mathcal{T}_{[0,t]}.$ As we use $\mathbf{t}$ to
represent the interval $[0,t],$ it follows that $\mathcal{T}_{[0,t]}$ is
rewritten as $\mathcal{T}_{\mathbf{t}}$ which represents all tasks in the
interval $[0,t]$ where
$\mathcal{T}_{\mathbf{t}}=\left((\mathbf{x},\phi)_{\mathbf{t}},J_{\mathbf{t}}(\mathbf{x},\phi,\mathbf{w})\right)$
with
$J_{\mathbf{t}}(\mathbf{x},\phi,\mathbf{w})=\int_{\tau=0}^{t}\ell(\mathbf{x}(\tau),\phi(\tau),\mathbf{w}(\tau)).$
This notation naturally extends to the case when $\mathbf{\Omega}$ is
comprised of discrete instance as well. In this case, we will set $\Delta t=1$
and replace $t$ by $k$ such that $[0,t]=[0,k]=[0,1,2,3,\cdots,k]=\mathbf{k}$
Furthermore, the collection of all tasks in the interval $[0,k]$ is given by
$\mathcal{T}_{\mathbf{k}}$ with
$J_{\mathbf{k}}(\mathbf{x},\phi,\mathbf{w})=\sum_{\tau=0}^{k}\ell(\mathbf{x}(\tau),\phi(\tau),\mathbf{w}(\tau))$
where $g(\mathbf{x}(k),\phi(k))$ is the parametric map and
$\ell(\mathbf{x}(k),\phi(k),\mathbf{w}(k))$ is the corresponding loss with the
VERG defined by the probability space
$(\mathcal{G}(k),P_{\mathbf{x}(k)\times\phi(k)})),k\in\mathbf{\Omega}.$

###  2.4 Dynamical Systems Modelling

Consider now an example for GCL, where at time $t_{i},$ the goal is to perform
well on all tasks in the interval $[0,t_{i}],$ the collection of which is
provided by $\mathcal{T}_{\mathbf{t}_{i}}.$ The conventional CL approach
involves constructing a cost function as
$J_{\mathbf{t}_{1}}(\mathbf{x},\phi,\mathbf{w})=\int_{\tau=0}^{t_{i}}\ell(\mathbf{x}(\tau),\phi(\tau),\mathbf{w}(\tau))$
with all the available tasks and minimizing it. Therefore, the GNN parameter
set $\mathbf{w}(\mathbf{t}_{1})$ is sought such that

$\underset{\mathbf{w}(\mathbf{t}_{1})}{min}J_{\mathbf{t}_{1}}(\mathbf{x},\phi,\mathbf{w}).$

Next, when at $\mathbf{t}_{2}$, new set of tasks are observed and the GNN must
be updated such that the GNN parameter set $\mathbf{w}(\mathbf{t}_{2})$
minimizes $J_{\mathbf{t}_{2}}(\mathbf{x},\phi,\mathbf{w})$ where

$J_{\mathbf{t}_{2}}(\mathbf{x},\phi,\mathbf{w})=J_{\mathbf{t}_{1}}(\mathbf{x},\phi,\mathbf{w})+J_{[\mathbf{t}_{1},\mathbf{t}_{2}]}(\mathbf{x},\phi,\mathbf{w}).$

That is, we seek to solve for both $J_{\mathbf{t}_{1}}$ and
$J_{[\mathbf{t}_{1},\mathbf{t}_{2}]}.$ This naive method of solving GCL leads
to two challenges. First, the number of tasks that must be performed increase
with each subsequent tasks and the increase in the number of tasks leads to a
shrinkage in the feasible region of the solution space. Second, whenever the
new set of tasks are observed, $\mathbf{w}$ obtained for the previous tasks is
the starting point and this starting point biases the GNN towards the future
tasks.

To elaborate on these challenges, let there be three graph learning tasks and
let the solution space of the be $\mathcal{W}_{1},\mathcal{W}_{2}$ and
$\mathcal{W}_{3}$ with $\mathbf{w}_{1}^{*},\mathbf{w}_{1}^{*}$ and
$\mathbf{w}_{3}^{*}$ being the ideal solutions (centers of these feasible
regions). Say, the first task is solved perfectly (solution $w_{1}^{*}$ is
attained). Therefore, the search for second task begins from
$\mathbf{w}_{1}^{*}.$ This process would move the solution from the feasible
region $\mathcal{W}_{1}$ to $\mathcal{W}_{1}\cap\mathcal{W}_{2}$ because the
solution that is optimal for both task 1 and 2 can only be found on this
intersection. If the two tasks are identical or very similar, then
$\mathcal{W}_{1}\cap\mathcal{W}_{2}$ is similar to
$\mathcal{W}_{1}\cup\mathcal{W}_{2}.$ However, if the two tasks are not
identical, the intersection space is smaller.

With this behavior, three scenarios may arise. First, with more and more
dissimilar tasks, the solution space (intersection of the feasible regions)
will shrink and it is possible that a solution that will perform all tasks
equally well may not exist. Second, if the new task pulls the solution
unreasonably towards its own solution space, we will incur large forgetting.
Third, if the new task does not influence the solution at all, we will not
learn the new task at all, no generalization. Due to these reasons, we cannot
naively minimize a cost as done by traditional CL methods and it is imperative
to update the GNN in such a way that a solution from the previous tasks is
neither unreasonably influenced by the new task (which will reduce
forgetting), nor ignore the new task completely (no generalization). That is –
it is necessary to achieve balance forgetting and generalization.

Even if it was possible to achieve a balance point, a bias exists. For
example, say the first task has been learned and we search for the solution of
the second task beginning from $\mathbf{w}_{1}^{*}.$ Due to this,
$\mathbf{w}_{1}^{*}$ biases the solution for the second task and even the
tasks in the future because, the distance between $\mathbf{w}_{1}^{*}$ and
$\mathcal{W}_{1}\cap\mathcal{W}_{2}$ determines how likely we will be able to
attain an optimal solution for both task one and two and the quality of this
solution. As each subsequent new task accumulates this bias, a multi-stage
decision making stochastic process must be considered where the weight
parameter at each stage influences the subsequent stages.

Therefore, we need to find a solution that is not only a saddle point between
generalization and forgetting but also converges to an optimal solution that
is optimal irrespective of the bias. To model the bias, we must characterize
“How does the solution to the GCL problem behave when each new task is
observed?” To find the balance, we seek to answer the question “Can we force
this solution to achieve a saddle point that enforces balance between
generalization and forgetting?” We will begin by modelling the behaviour
(dynamics) of the solution as a function of each new task.

In this pursuit, we will take an adaptive dynamic programming viewpoint and
leverage tools for optimal control literature [15]. Give a collection of
tasks, the generalization and catastrophic forgetting cost is

(2) $\displaystyle
J_{\mathbf{t}}(\mathbf{x},\phi,\mathbf{w})=\int_{\tau=0}^{t}\ell_{\tau}(\mathbf{x},\phi,\mathbf{w})d\tau.$

Consider the example in Fig. 1 where the forgetting and generalization cost at
$\mathbf{t}_{1}$ is given as $J_{\mathbf{t}_{1}}(\mathbf{x},\phi,\mathbf{w})$
with the weights of the GNN initialized at $\mathbf{w}(\mathbf{t}_{1}).$ As we
go through the updates, we obtain obtain $\mathbf{w}^{*}(\mathbf{t}_{1})$ by
minimizing $J_{\mathbf{t}_{1}}(\mathbf{x},\phi,\mathbf{w}).$ However, when the
next set of previous and new tasks are observed, the quality of
$\mathbf{w}^{*}(\mathbf{t}_{2})$ is biased by
$\mathbf{w}^{*}(\mathbf{t}_{1}).$ This bias can be removed if
$\mathbf{w}^{*}(\mathbf{t}_{1})$ is obtained considering its effect of
$\mathbf{w}^{*}(\mathbf{t}_{2}).$ At $\mathbf{t}_{1},$ if the total cost
$L(\mathbf{t})_{1}$ is
$J_{\mathbf{t}_{1}}(\mathbf{x},\phi,\mathbf{w})+J_{\mathbf{t}_{2}}(\mathbf{x},\phi,\mathbf{w})+J_{\mathbf{t}_{3}}(\mathbf{x},\phi,\mathbf{w})$
is minimized, then, we have considered the complete effect of
$\mathbf{w}(\mathbf{t}^{1})$ on ever task in the future. Generalizing this
idea over the interval $\mathbf{\Omega},$ we obtain the GCL problem
considering the effect of GNN over all tasks is given as

(3) $\displaystyle
L^{*}_{\mathbf{t}}=\underset{\mathbf{w}(\mathbf{t})}{min}\int_{\tau=t}^{\Omega}J_{\boldsymbol{\tau}}(\mathbf{x},\phi,\mathbf{w}),$

where the outer integral summarizes the cumulative effect of $\mathbf{w}(t)$
on all future tasks and the effect of $\mathbf{w}(t)$ on all the previous and
the new task is considered through
$J_{\boldsymbol{\tau}}(\mathbf{x},\phi,\mathbf{w}).$ Solving
LABEL:{eq:problem_GCL} results in $L^{*}(\mathbf{t})$ as the minimum which is
obtained considering the effects of the GCL solution over all the tasks in the
past, present and the future – a holistic unbiased solution of GCL. Therefore,
our goal of GCL is to find a holistic unbiased policy $\mathbf{w}(\mathbf{t})$
which results in $L^{*}(\mathbf{t}).$

###  2.5 GCL Ordinary Differential Equation (ODE)

It is intractable to calculate the integral in Eq. 3 as the large part of the
domain is unknown since future tasks are not available. We will therefore
simplify this problem using Bellman’s principal of optimality [14, 21] where
we will approximate the information regarding future tasks using what
information is available right now. With this setup we will now derive the
dynamics of the graph continual learning problem through the following
proposition.

######  Proposition 2.1.

For $t\in\mathbf{\Omega}$ and a vertex set
$\mathbf{V}(t):\mathbf{\Omega}\rightarrow\boldsymbol{\mathcal{V}}|\mathbf{V}(t)\subset\boldsymbol{\mathcal{V}},$
define the CL task as in 2. For each $\mathbf{t}\subset\mathbf{\Omega}$ let

(4) $\displaystyle
L^{*}_{\mathbf{t}}=\underset{\mathbf{w}(\mathbf{t})}{min}\int_{\tau=t}^{\Omega}J_{\boldsymbol{\tau}}(\mathbf{x},\phi,\mathbf{w})$

as the GCL problem. Assume $J_{\mathbf{t}}(\mathbf{x},\phi,\mathbf{w})$ to be
smooth with respect to all its arguments. Under the assumption that
$R(\mathbf{t})$ denotes all the higher order terms in a Taylor series
expansion, the following is true

(5)
$\displaystyle-\left(\partial_{\mathbf{t}}L^{*}_{\mathbf{t}}\right)^{T}\Delta_{\mathbf{t}}$
$\displaystyle=\underset{\mathbf{w}(\mathbf{t})}{min}\Big{[}J_{\mathbf{t}}(\mathbf{x},\phi,\mathbf{w})+\left(\partial_{\mathbf{x}_{\mathbf{t}}}L^{*}_{\mathbf{t}}\right)^{T}\Delta_{\mathbf{x}}$
$\displaystyle+\left(\partial_{\phi_{\mathbf{t}}}L^{*}_{\mathbf{t}}\right)^{T}\Delta_{\phi}+\left(\partial_{\mathbf{w}_{\mathbf{t}}}L^{*}_{\mathbf{t}}\right)^{T}\Delta_{\mathbf{w}}+R_{\mathbf{t}},\Big{]}$

where $\Delta{x}$ refers to tiny perturbation.

######  Proof 2.2.

The proof is provided in the supplementary files.

Proposition 2.1 summarizes the dynamics of GCL as a function of tasks. The
partial derivative of the value function on the left-hand side of the equation
describes the change in value function introduced by a change in $\mathbf{t}$–
the introduction of a new task. The terms in the right-hand side describe
which different element quantify this change in the value function. The first
term summarizes the cost of generalization and forgetting. The second term
characterizes the change due to $\mathbf{x}$—“how change in the vertex
features modifies the value function.” The third term describes “ how the
change in the edge features impacts the value function”. The fourth term
summarizes the impact of model parameters on the value function and the fifth
term summarize all the higher-order terms. One of the key features of this ODE
is that the change in connectivity of the graphs is modelled by the last two
terms of this ODE. The second and the third term are defined on
$\mathbf{V}(t)$ which describes the change in the vertex set. As the vertex
set may change as a function of task, both the edge feature and vertex
features may change. This ability to theoretically model edge-connectivity
provides a unique approach to GCL.

To verify whether the equation GCL ODE is correct or not, we will derive the
ODE for when the vertex set has cardinality one, with unit neighborhood size
and the edge properties being non-existant. Intuitively, this equation should
be equivalent to [14].

######  Lemma 2.3.

Let the graph ODE be given as

(6)
$\displaystyle-\left(\partial_{\mathbf{t}}L^{*}(\mathbf{t})\right)^{T}\Delta_{\mathbf{t}}$
$\displaystyle=\underset{\mathbf{w}(\mathbf{t})}{min}\Big{[}J_{\mathbf{t}}(\mathbf{x},\phi,\mathbf{w})+\left(\partial_{\mathbf{x}_{\mathbf{t}}}L^{*}_{\mathbf{t}}\right)^{T}\Delta_{\mathbf{x}}$
$\displaystyle+\left(\partial_{\phi_{\mathbf{t}}}L^{*}_{\mathbf{t}}\right)^{T}\Delta_{\phi}+\left(\partial_{\mathbf{w}_{\mathbf{t}}}L^{*}_{\mathbf{t}}\right)^{T}\Delta_{\mathbf{w}}+R_{\mathbf{t}},\Big{]}$

Let $\mathbf{t}=t$ and therefore $\Delta t=t.$ Assuming $G=\mathbf{x}$, where
the edge properties have been removed. Define a task in this context as
$\mathcal{T}(t)=(\mathbf{x}(t),\ell(\mathbf{w}(t))$ and assume that $R_{t}=0,$
Then the dynamics of continual learning are governed by

(7) $\displaystyle\partial_{\mathbf{t}}L^{*}(t)^{T}\Delta_{t}$
$\displaystyle=-\underset{\mathbf{w}(t)}{min}\Big{[}J_{\mathbf{t}}(\mathbf{x},\mathbf{w})+\left(\partial_{\mathbf{x}_{\mathbf{t}}}L^{*}_{\mathbf{t}}\right)^{T}\Delta_{\mathbf{x}}+\left(\partial_{\mathbf{w}_{\mathbf{t}}}L^{*}_{\mathbf{t}}\right)^{T}\Delta_{\mathbf{w}}\Big{]}.$

where $\partial_{y}x$ refers to the partial derivative of $x$ with respect to
$y$ and $\Delta_{x}$ refers to the first difference in $x.$

######  Proof 2.4.

The end result is obtained by simply substituting $\Delta t=t,\mathbf{t}=t$
and
$\left(\partial_{\phi_{\mathbf{t}}}L^{*}_{\mathbf{t}}\right)^{T}\Delta_{\phi}=0.$

The preceding lemma proves that the work in [14] is a special case of the
dynamics provided here. This reinforces the fact that the present work is the
most general form of continual learning that can work for both Euclidean and
nonEuclidean data. The ODE in Proposition 2.1 models the behavior of the GCL
solution $L^{*}(\mathbf{t})$ as a function of the tasks. Next, we seek
solution to the GCL problem where we formulate a saddle point problem to
balance generalization and forgetting.

##  3 Balancing Forgetting and Generalization

In the preceding section, we formulated the problem of GCL where we obtained
ODE that models the behavior of $L^{*}$– the optimal solution of the GCL
problem, as a function of the tasks. We now seek to update to the policy using
the differential equation in Proposition 2.1. An update to our policy can be
directly obtained by solving the ODE in Eq. (2). However, solving the ODE
fully may be quite tedious. Fortunately, it is not necessary to solve the ODE
explicitly. The important thing is that when any new task is revealed, we must
find an update to the policy such that the new task induces minimum change
(zero change in an ideal case) to the value function. This will allow us to
find a stable balance point which is not biased by the tasks. This insight
provide the following optimization problem that need to be solved:

(8)
$\displaystyle\underset{\mathbf{w}(\mathbf{t})}{min}\Big{[}J_{\mathbf{t}}(\mathbf{x},\phi,\mathbf{w})+\left(\partial_{\mathbf{x}_{\mathbf{t}}}L^{*}_{\mathbf{t}}\right)^{T}\Delta_{\mathbf{x}}+\left(\partial_{\phi_{\mathbf{t}}}L^{*}_{\mathbf{t}}\right)^{T}\Delta_{\phi}+\left(\partial_{\mathbf{w}_{\mathbf{t}}}L^{*}_{\mathbf{t}}\right)^{T}\Delta_{\mathbf{w}},\Big{]}$
$\displaystyle\text{ subject to
}-\left(\partial_{\mathbf{t}}L^{*}(\mathbf{t})\right)^{T}\Delta_{\mathbf{t}}+R_{\mathbf{t}}\leq\kappa,\forall\kappa\in[0,1].$

In many GCL settings, the tasks may arrive at discrete time instances.
Therefore, for each $k\in\mathbf{\Omega},\Delta_{\mathbf{t}}=1$ the
optimization problem is given as

(9)
$\displaystyle\underset{\mathbf{w}(\mathbf{k})}{min}\Big{[}J_{\mathbf{k}}(\mathbf{x},\phi,\mathbf{w})+\left(\partial_{\mathbf{x}_{\mathbf{k}}}L^{*}_{\mathbf{t}}\right)^{T}\Delta_{\mathbf{x}}+\left(\partial_{\phi_{\mathbf{k}}}L^{*}_{\mathbf{k}}\right)^{T}\Delta_{\phi}+\left(\partial_{\mathbf{w}_{\mathbf{k}}}L^{*}_{\mathbf{t}}\right)^{T}\Delta_{\mathbf{w}},\Big{]}$
$\displaystyle\text{ subject to
}-\partial_{\mathbf{t}}L^{*}(\mathbf{k})+R_{\mathbf{k}}\leq\kappa,\forall\kappa\in[0,1].$

With the assumption that
$R(\mathbf{k})\leq\kappa\quad\forall\kappa\in\mathbb{R}$, we write the
optimization problem as

(10)
$\displaystyle\underset{\mathbf{w}_{\mathbf{k}}}{min}\quad\mathcal{H}_{\mathbf{k}}(\Delta_{\phi},\Delta_{\mathbf{x}},\Delta_{\mathbf{w}},\mathbf{x},\phi,\mathbf{w}),$

where we have gathered all terms in the bracket. In summary, the GCL problem
is that of finding a policy ($\mathbf{w}$) that minimizes
$\mathcal{H}_{\mathbf{k}}(\Delta_{\phi},\Delta_{\mathbf{x}},\Delta_{\mathbf{w}},\mathbf{x},\phi,\mathbf{w})$
whenever a new task is introduced. Typically, at the onset of each new task,
there is a change in the graph indicated by $\Delta_{\phi}$ and
$\Delta_{\mathbf{x}}.$ Subsequently, corresponding to this change in the
graph, there is a particular $\Delta_{\mathbf{w}}$ that provides a change in
the policy just due to the new task. This change due to the new task
experienced by the policy is the process of generalization. Therefore, the
larger the value of the delta’s, the larger the shift in policy, the larger
the generalization. As a large shift in policy will erase the knowledge of
previous tasks (as the policy moves away from the previous tasks), large
forgetting follows large generalization. Since, large forgetting due to a new
task is not desirable, this shift in policy must be regularized. However, such
a regularizing in only possible, if the exact value of $\Delta_{\mathbf{w}}$
corresponding to a given value of $\Delta_{\phi},\Delta_{\mathbf{x}}$ is
known. In the absence of such information, which is the case in most GCL/CL
applications, we must first ascertain the delta’s
($\Delta_{\phi},\Delta_{\mathbf{x}},\Delta_{\mathbf{w}}$) to estimate
generalization and then, update $\mathbf{w}$ to guarantee minimum forgetting.
In this work, we simulate generalization by updating delta’s to introduce
maximum change in the value function and update the policy to reduce the
effect of worst case generalization. Thus, we formulate a two player min-max
game where the worst case generalization and the corresponding forgetting is
implicitly determined through iterative updates [5] with $\Delta$’s updated
through gradient ascent and $\mathbf{w}$ is updated through gradient descent.

To indicate these iterative updates, we will introduce two iteration indices
$i$ and $j$, respectively. We use $i=1,2,3,\cdots,\zeta$ to indicate updates
for the $\Delta$’s and $j=1,2,3,\cdots,\rho$ to indicate updates on
$\mathbf{w}.$ Then, we rewrite the optimization problem as
$\underset{\mathbf{w}^{(j)}_{\mathbf{k}}}{min}\quad
H_{\mathbf{k}}(\Delta^{(i)}_{\phi},\Delta^{(i)}_{\mathbf{x}},\Delta^{(i)}_{\mathbf{w}},\mathbf{x},\phi,\mathbf{w}^{(j)}),$
where we denote the task with the subscript $\mathbf{k}$ with the min and max
iteration at each task denoted by superscript $i$ and $j$, respectively. Next,
we define three compact sets $\mathcal{W},\mathbf{\mathcal{X}},\mathbf{\Phi}$
such that the search space for the optimization problem is described by the
triplet
$\Delta_{\mathbf{w}}^{(i)}\times\Delta^{(i)}_{\phi}\times\Delta^{(i)}_{\mathbf{x}}\in\mathcal{W}\times\mathbf{\Phi}\times\mathbf{\mathcal{X}},\quad\mathbf{w}^{(i)}\in\mathcal{W}.$
We approximate the value function using $J_{\mathbf{k}},$ as given by the
following proposition

######  Proposition 3.1.

Let $\mathbf{k}\in\mathbf{\Omega}$ and define
$\mathcal{W},\mathbf{\mathcal{X}},\mathbf{\Phi}$ such that
$\Delta_{\mathbf{w}}^{(i)}\times\Delta^{(i)}_{\phi}\times\Delta^{(i)}_{\mathbf{x}}\in\mathcal{W}\times\mathbf{\Phi}\times\mathbf{\mathcal{X}}$
and assume that

(11a) $\displaystyle sup_{\mathbf{\mathcal{X}}}L^{*}_{\mathbf{k}}$
$\displaystyle\leq
inf_{\mathbf{\mathcal{X}}}J_{\mathbf{k}}(\mathbf{x},\phi,\mathbf{w}^{(j)})\leq
max_{\mathbf{\Delta}^{(i)}_{\mathbf{x}_{\mathbf{k}}}\in\mathbf{\mathcal{X}}}J_{\mathbf{k}}(\mathbf{x}+\mathbf{\Delta}_{\mathbf{x}}^{(i)},\phi,\mathbf{w}^{(j)})$
(11b) $\displaystyle sup_{\mathbf{\Phi}}L^{*}_{\mathbf{k}}$ $\displaystyle\leq
inf_{\mathbf{\Phi}}J_{\mathbf{k}}(\mathbf{x},\phi,\mathbf{w}^{(j)})\leq
max_{\Delta^{(i)}_{\phi_{\mathbf{k}}}\in\mathbf{\Phi}}J_{\mathbf{k}}(\mathbf{x},\phi+\Delta^{(i)}_{\phi},\mathbf{w}^{(j)})$
(11c) $\displaystyle sup_{\mathcal{W}}L^{*}_{\mathbf{k}}$ $\displaystyle\leq
inf_{\mathcal{W}}J_{\mathbf{k}}(\mathbf{x},\phi,\mathbf{w}^{(j)})\leq
max_{\Delta^{(i)}_{\mathbf{w}}\in\mathcal{W}}J_{\mathbf{k}}(\mathbf{x},\phi,\mathbf{w}^{(j)}+\Delta^{(i)}_{\mathbf{w}})$
(11d) $\displaystyle Inf_{\mathbf{\mathcal{X}}}L^{*}_{\mathbf{k}}\geq
0,Inf_{\mathbf{\Phi}}L^{*}_{\mathbf{k}}$ $\displaystyle\geq
0,Inf_{\mathcal{W}}L^{*}_{\mathbf{k}}\geq 0.$

Then, define
$\mathcal{H}(\Delta^{(i)}_{\phi},\Delta^{(i)}_{\mathbf{x}},\mathbf{x},\phi,\mathbf{w}^{(j)})=J_{\mathbf{k}}(\mathbf{x},\phi,\mathbf{w}^{(j)})+\left(\partial_{\mathbf{x}_{\mathbf{k}}}L^{*}_{\mathbf{k}}\right)^{T}\Delta^{(i)}_{\mathbf{x}_{\mathbf{k}}}\\\
+\left(\partial_{\phi_{\mathbf{k}}}L^{*}_{\mathbf{k}}\right)^{T}\Delta_{\phi_{\mathbf{k}}}+\left(\partial_{\mathbf{w}^{(j)}_{\mathbf{k}}}L^{*}_{\mathbf{k}}\right)^{T}\Delta^{(i)}_{\mathbf{w}_{\mathbf{k}}}$
and the following approximation is true

(12) $\displaystyle
H_{\mathbf{k}}(\Delta^{(i)}_{\phi},\Delta^{(i)}_{\mathbf{x}},\Delta^{(i)}_{\mathbf{w}},\mathbf{x},\phi,\mathbf{w}^{(j)})\leq
max_{\Delta_{\mathbf{w}_{\mathbf{k}}}^{(i)}\times\Delta^{(i)}_{\phi_{\mathbf{k}}}\times\Delta^{(i)}_{\mathbf{x}_{\mathbf{k}}}\in\mathcal{W}\times\mathbf{\Phi}\times\mathbf{\mathcal{X}}}$
$\displaystyle\Big{[}J_{\mathbf{k}}(\mathbf{x},\phi,\mathbf{w}^{(j)})+\beta_{1}J_{\mathbf{k}}(\mathbf{x}+\mathbf{\Delta}_{\mathbf{x}}^{(i)},\phi,\mathbf{w}^{(j)})+\beta_{2}J_{\mathbf{k}}(\mathbf{x},\phi+\Delta^{(i)}_{\phi},\mathbf{w}^{(j)})$
$\displaystyle+\beta_{3}J_{\mathbf{k}}(\mathbf{x},\phi,\mathbf{w}^{(j)}+\Delta^{(i)}_{\mathbf{w}}),\Big{]}$

where $\beta_{k}\in\mathbb{R}\cup[0,1],\forall k$ and $\zeta\in\mathbb{N}$
indicates finite difference updates.

######  Proof 3.2.

The proof can be found in the supplementary material.

Using Proposition 3.1, the upper bound to our optimization problem is

$\displaystyle\underset{\mathbf{w}^{(j)}_{\mathbf{k}}}{min}\;H_{\mathbf{k}}(\Delta^{(i)}_{\phi},\Delta^{(i)}_{\mathbf{x}},\Delta^{(i)}_{\mathbf{w}},\mathbf{x},\phi,\mathbf{w}^{(j)})\leq\underset{\mathbf{w}^{(j)}_{\mathbf{k}}}{min}\underset{\Delta_{\mathbf{w}_{\mathbf{k}}}^{(i)}\times\Delta^{(i)}_{\phi_{\mathbf{k}}}\times\Delta^{(i)}_{\mathbf{x}_{\mathbf{k}}}\in\mathcal{W}\times\mathbf{\Phi}\times\mathbf{\mathcal{X}}}{max}$
(13)
$\displaystyle\Big{[}J_{\mathbf{k}}(\mathbf{x},\phi,\mathbf{w}^{(j)})+\beta_{1}J_{\mathbf{k}}(\mathbf{x}+\mathbf{\Delta}_{\mathbf{x}}^{(i)},\phi,\mathbf{w}^{(j)})+\beta_{2}J_{\mathbf{k}}(\mathbf{x},\phi+\Delta^{(i)}_{\phi},\mathbf{w}^{(j)})+\beta_{3}$
$\displaystyle
J_{\mathbf{k}}(\mathbf{x},\phi,\mathbf{w}^{(j)}+\Delta^{(i)}_{\mathbf{w}})\Big{]}\leq\underset{\mathbf{w}^{(j)}_{\mathbf{k}}}{min}\underset{\Delta_{\mathbf{w}_{\mathbf{k}}}^{(i)}\times\Delta^{(i)}_{\phi_{\mathbf{k}}}\times\Delta^{(i)}_{\mathbf{x}_{\mathbf{k}}}}{max}\mathcal{H}_{\mathbf{k}}(\Delta^{(i)}_{\phi},\Delta^{(i)}_{\mathbf{x}},\Delta^{(i)}_{\mathbf{w}},\mathbf{x},\phi,\mathbf{w}^{(j)}).$

For notational simplification, we will pool all the maximizing parameters
using a block column vector $\mathbf{u}$ and write

(14) $\displaystyle min_{\mathbf{w}^{(j)}_{\mathbf{k}}}\quad
max_{\mathbf{u}_{\mathbf{k}}^{(i)}}\quad\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{(i)},\mathbf{w}^{(j)}),$

with
$\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{(i)},\mathbf{w}^{(j)})=J_{\mathbf{k}}(\mathbf{w}^{(j)})+\beta_{1}J_{\mathbf{k}}(\mathbf{u}_{0}^{(i)},\mathbf{w}^{(j)})+\beta_{2}J_{\mathbf{k}}(\mathbf{u}_{1}^{(i)},\mathbf{w}^{(j)})+\beta_{3}J_{\mathbf{k}}(\mathbf{u}_{2}^{(i)},\mathbf{w}^{(j)}),$
where $\mathbf{u}_{l}$ denotes the $l^{th}$ element in the block-column vector
$\mathbf{u}.$ Generalization is simulated through $\mathbf{u},$ (the delta’s
and the first player) and the forgetting through the policy $\mathbf{w}$ (the
second player). The two players, $\mathbf{u}$ and $\mathbf{w}$ chose
adversarial strategies and introduce dynamics by increasing and decreasing
$\mathcal{H}_{\mathbf{k}}.$ Many different strategies are possible but, in
this work, we choose stochastic gradient ascent-descent. Over different
iterations, the two players introduce the dynamics of a game using the
gradient of the $\mathcal{H}_{\mathbf{k}}$ to either perform ascent updates as
in the case of $\mathbf{u}$ or descent update as in the case of $\mathbf{w}.$
This push-pull play will converge when the gradient of
$\mathcal{H}_{\mathbf{k}}$ will approach zero at which point, the two players
have no incentive to move and an equilibrium point (saddle point between two
players) will be achieved. In the context of GCL, this equilibrium state is
known as the balance between forgetting and generalization. Thus, two
theoretical questions arise, “Is there such a balance point?,” and “Can this
balance be achieved?” Later in the theoretical analysis section, we
demonstrate that the answer to these questions is indeed yes. However, first,
we detail an algorithm through which this two player game will be played.

Specifically, we define two datasets: $D^{P}_{k}$, the previous tasks dataset,
and $D^{N}_{k}$, the new task dataset. With this setup, we define
$\mathcal{W}\times\mathbf{\mathcal{X}}\times\mathbf{\Phi}$ as $\mathcal{U}$ to
be the compact search space for $\mathbf{u}^{(i)}$ and $\mathcal{W}$ as the
search space for $\mathbf{w}^{(j)}.$ The learning problem is

(15)
$\displaystyle\underset{\mathbf{w}^{(j)}\in\mathcal{W}}{min}\quad\underset{\mathbf{u}^{(i)}\in\mathcal{U}}{max}\quad\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{(i)},\mathbf{w}^{(j)}).$

This algorithm follows a two-step strategy and is detailed in Algorithm 1.

Algorithm 1 Graph Continual Learning

1: Initialize ${\mathbf{w}^{(j)}},D^{N}_{k},D^{P}_{k}.$

2: while $k=1,2,3,.K$ do

3: j = 0

4: while $j<\rho$ do

5: Fix $\mathbf{w}^{(j)}$

6: while $i+1<=\zeta$ do

7: Sample $\mathbf{b}_{N}\in D^{N}_{k},\mathbf{b}_{P}\in D^{P}_{k}$ and get
$\mathbf{b}_{PN}=\mathbf{b}_{P}\cup\mathbf{b}_{N}.$ i = 0.

8: Update $\mathbf{u}^{(i)}$ through gradient ascent on
$\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{(i)},\mathbf{w}^{(j)}).$

9: i = i+1.

10: end while

11: Fix $\mathbf{u}^{(\zeta)}$

12: Sample $\mathbf{b}_{N}\in D^{N}_{k},\mathbf{b}_{P}\in D^{P}_{k}$ and get
$\mathbf{b}_{PN}=\mathbf{b}_{P}\cup\mathbf{b}_{N}.$

13: Update $\mathbf{w}^{(j)}$ using gradient descent on
$\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{(\zeta)},\mathbf{w}^{(j)}).$

14: j= j+1.

15: end while

16: Update ${D_{P}}$ with ${D_{N}}$

17: end while

We first update $\mathbf{u}^{(i)}$ and attain $\mathbf{u}^{*}$ in
$\mathcal{U}.$ With a fixed solution in $\mathcal{U}$, we find
$\mathbf{w}^{*}$ in $\mathcal{W}$ by updating $\mathbf{w}^{(j)}.$ With
repeated iterations, we converge to the equillibrium point
$(\mathbf{u}^{*},\mathbf{w}^{*}).$ The existence and the convergence is
guaranteed through theoretical analysis in the following section.

##  4 Theoretical Analysis

In this section, we will define all the expected values respect to the joint
probability measure $P_{\mathbf{x}\times\phi}$ as described in 2. To perform
continual learning according to Algorithm 1, we define $\mathcal{U}$ to be the
search space for $\mathbf{u}^{(i)}$ and $\mathcal{W}$ is the search space for
$\mathbf{w}^{(j)}.$ Then, the learning problem is provided as

(16)
$\displaystyle\underset{\mathbf{w}^{(j)}\in\mathcal{W}}{min}\quad\underset{\mathbf{u}^{(i)}\in\mathcal{U}}{max}\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{(i)},\mathbf{w}^{(j)}).$

We will denote $\mathbf{g}^{(j)}_{\mathbf{w}}$ and
$\mathbf{g}^{(i)}_{\mathbf{u}}$ as the derivative of
$H_{\mathbf{k}}(\mathbf{u}^{(i)},\mathbf{w}^{(j)})$ with respect to
$\mathbf{w}$ and $\mathbf{u}$ respectively. For a minibatch sampled according
to the distribution $P_{\mathbf{x}\times\phi}$, we will define a minibatch
estimate of the gradients as $\hat{\mathbf{g}}_{\mathbf{u}}^{(i)}$ and
$\hat{\mathbf{g}}_{\mathbf{w}}^{(j)}$ respectively. We will use
$\mathbf{g}^{(j)}_{\mathbf{w}}(m)$ indicating gradients with respect to the
$m^{th}$ datapoint in the mini-batch. At this point, we make the following
assumptions The function $J_{\mathbf{k}}$ is Lipschitz continuous, that is

(17a)
$\displaystyle\|\nabla_{\mathbf{u}^{(i+1)}}J_{\mathbf{k}}-\nabla_{\mathbf{u}^{(i)}}J_{\mathbf{k}}\|$
$\displaystyle\leq M\|\mathbf{u}^{(i+1)}-\mathbf{u}^{(i)}\|$ (17b)
$\displaystyle\|\nabla_{\mathbf{w}^{(i+1)}}J_{\mathbf{k}}-\nabla_{\mathbf{w}^{(i)}}J_{\mathbf{k}}\|$
$\displaystyle\leq L_{w}\|\mathbf{w}^{(i+1)}-\mathbf{w}^{(i)}\|$
$\displaystyle\forall\mathbf{u}^{(i+1)},\mathbf{u}^{(i)}\in\mathcal{U},$
$\displaystyle\forall\mathbf{w}^{(i+1)},\mathbf{w}^{(i)}\in\mathcal{W}.$

Furthermore, the gradient is bounded with respect to all its arguments.

(18) $\displaystyle\|\nabla_{\mathbf{u}_{0}^{(i)}}J_{\mathbf{k}}\|\leq
G_{\mathbf{x}}$
$\displaystyle,\|\nabla_{\mathbf{u}_{1}^{(i)}}J_{\mathbf{k}}\|\leq
G_{\phi}\|\nabla_{\mathbf{u}_{2}^{(i)}}J_{\mathbf{k}}\|\leq G_{\mathbf{w}}$
$\displaystyle,\|\nabla_{\mathbf{w}^{(i)}}J_{\mathbf{k}}\|\leq G$
$\displaystyle\forall\mathbf{u}^{(i)}\in\mathcal{U},$
$\displaystyle\forall\mathbf{w}^{(i)}\in\mathcal{W}.$

Before presenting our results, we will bound the expected value of gradients
($\hat{\mathbf{g}}_{\mathbf{u}}^{(i)},\hat{\mathbf{g}}_{\mathbf{w}}^{(i)}$)
based on the assumptions described here.

######  Lemma 4.1.

Let Eq. 16 be true and let the size of $D^{P}_{k}\cup D^{N}_{k}$, be described
by $N$ with the batch size given by $b.$ Assume that a minibatch is obtained
by sampling uniformly from the dataset and define
$H_{\mathbf{k}}(\mathbf{u}^{(i)},\mathbf{w}^{(j)})=[J_{\mathbf{k}}(\mathbf{w}^{(j)})+\beta_{1}J_{\mathbf{k}}(\mathbf{u}_{0}^{(i)},\mathbf{w}^{(j)})+\beta_{2}J_{\mathbf{k}}(\mathbf{u}_{1}^{(i)},\mathbf{w}^{(j)})+\beta_{3}J_{\mathbf{k}}(\mathbf{u}_{2}^{(i)},\mathbf{w}^{(j)})]$
with $\bar{G}=[G_{\phi}+G_{\mathbf{x}}+G_{\mathbf{w}}].$ Then, the following
inequalities are true.

$\displaystyle\|\mathbf{g}^{(i)}_{\mathbf{u}}\|$
$\displaystyle\leq\beta\bar{G}$
$\displaystyle\|\mathbf{g}^{(j)}_{\mathbf{w}}\|$
$\displaystyle\leq\Big{[}(1+3\beta)G\Big{]}$ (19)
$\displaystyle\mathbb{E}\left[\|\mathbf{g}^{(i)}_{\mathbf{u}}\|\right]$
$\displaystyle\leq\beta\frac{b\bar{G}}{N}$
$\displaystyle\mathbb{E}\left[\|\mathbf{g}^{(i)}_{\mathbf{w}}\|\right]$
$\displaystyle\leq\beta\frac{b(1+3\beta)G}{N}$ $\displaystyle
Var(\mathbf{g}^{(i)}_{\mathbf{u}})$
$\displaystyle\leq\frac{2b\beta^{2}\left(N^{2}+b^{2}\right)}{N^{3}}\bar{G}^{2}$
$\displaystyle Var(\mathbf{g}^{(j)}_{\mathbf{w}})$
$\displaystyle\leq\left[\frac{bN^{2}+b^{3}}{N^{3}}\right]\left[G^{2}(1+3\beta)^{2}\right].$

where $\|.\|$ refers to the $\ell_{2}$ norm.

In this work, the goal is to prove that a equillibrium point for the two
player game exists and can be reached. Since, the two player game is
sequential, we seek a local min-max point or Stackleberg equillibrium. The
following definitions are adapted from [12] which provides approximate
conditions for sequential minmax games as

######  Definition 3.

. Let there be two compact sets $\mathcal{U}$ and $\mathcal{W}$ and assume
$\mathcal{H}_{\mathbf{k}}$ to be twice differentiable, then
$(\mathbf{u}^{*},\mathbf{w}^{*})\in\mathcal{U}\times\mathcal{W}$ is said to be
a local minimax point or at Stackleberg equillibrium for
$\mathcal{H}_{\mathbf{k}}$, if the following is true

(20)
$\displaystyle\left\lVert\mathbb{E}[\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{*},\mathbf{w}^{*})-\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{(i)},\mathbf{w}^{*})]\right\rVert$
$\displaystyle\leq\epsilon(\delta_{u}),$
$\displaystyle\left\lVert\mathbb{E}\left[\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{*},\mathbf{w}^{*})-\underset{\mathbf{u}^{(i)}\in\mathcal{\mathbf{U}}}{max}\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{(i)},\mathbf{w}^{(j)})\right]\right\rVert$
$\displaystyle\leq\epsilon(\delta_{w},\delta_{u}).$

for every $(\mathbf{u}^{(i)},\mathbf{w}^{(j)})\in\mathcal{U}\times\mathcal{W}$
such that for any $\delta_{u},\delta_{w}\in\mathbb{R}^{+}$ with
$\mathbb{E}[\|\mathbf{w}^{(j)}-\mathbf{w}^{*}]\|\leq\delta_{w},\quad\mathbb{E}[\|\mathbf{u}^{(i)}-\mathbf{u}^{*}]\|\leq\delta_{u},$
with $\epsilon(\delta_{u},\delta_{w}),\epsilon(\delta_{u})\in\mathbb{R^{+}}.$

In what follows, we will show that a local min-max point (which is equivalent
to the Stackleberg equilibrium in a two-player setting [12]) exists (
definition 3) and that the algorithm converges.

###  4.1 Theorem 1, Existence of the minmax point

We will first show the existence of Stackleberg equillibrium. It suffices to
show that there exists a $(\mathbf{u}^{*},\mathbf{w}^{*})$ such that the
conditions from definition 3 are satisfied. This is given as follows.

######  Theorem 4.2 (Existence of an Equilibrium Point).

For each task $k,$ fix $\mathbf{w}^{*}\in\mathcal{W}$ and construct
$\mathcal{M}=\\{\mathbf{\mathcal{U}},\mathbf{w}^{*}\\}.$ Let assumption Eq. 16
be true, define a dataset $D_{P}\cup D_{N}$ of size $N>0$ and sample uniformly
a mini-batch of size $b.$ Next, define
$\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{(i)},\mathbf{w}^{(j)})=J_{\mathbf{k}}(\mathbf{w}^{(j)})+\beta_{1}J_{\mathbf{k}}(\mathbf{u}_{0}^{(i)},\mathbf{w}^{(j)})+\beta_{2}J_{\mathbf{k}}(\mathbf{u}_{1}^{(i)},\mathbf{w}^{(j)})+\beta_{3}J_{\mathbf{k}}(\mathbf{u}_{2}^{(i)},\mathbf{w}^{(j)})$
with $\beta_{1},\beta_{2},\beta_{3}\leq\beta>0.$ Let the inequalities from
Lemma 4.1 be true. Under assumption that $\alpha^{(i)}_{u}>0,b>0,\beta>0,N>0,$
then, there conditions in Eq. 20 are satisfied with

(21a) $\displaystyle\epsilon(\delta_{u})$
$\displaystyle=\frac{M+1}{2}\delta_{u}^{2}+\bar{G}^{2}\left(\frac{1}{2}\left(\frac{b\bar{G}}{N}\right)^{2}+\frac{2b\beta^{2}\left(N^{2}+b^{2}\right)}{N^{3}}\right),$
(21b) $\displaystyle\epsilon(\delta_{u},\delta_{w})$
$\displaystyle=(\frac{L_{w}+1}{2})\delta_{w}^{2}+G^{2}\left(\frac{\left[(1+3\beta)^{2}\right]}{2}+\left[\frac{bN^{2}+b^{3}}{N^{3}}\right]\left[(1+3\beta)^{2}\right]\right)$
$\displaystyle+\frac{M+1}{2}\delta_{u}^{2}+\bar{G}^{2}\left(\frac{1}{2}\left(\frac{b}{N}\right)^{2}+\frac{2b\beta^{2}\left(N^{2}+b^{2}\right)}{N^{3}}\right).$

Here $\|\mathbf{u}^{(i)}-\mathbf{u}^{*}\|\leq\delta_{u},\forall i$ and
$\|\mathbf{w}^{(j)}-\mathbf{w}^{*}\|\leq\delta_{w},\forall j.$ Furthermore,
there exists a $(\mathbf{u}^{*},\mathbf{w}^{*})\in\mathcal{M}\cup\mathcal{N}$
such that $(\mathbf{u}^{*},\mathbf{w}^{*})$ is a local minimax point or a
Stackleberg equillibrium point according to 3.

To show a local min-max point, we make the assumption that the two players are
initialized close to the equilibrium point. This assumption is due to the lack
of convexity in the learning problem. Since there is no unique equilibrium
point in the nonconvex case, the best we can claim is that one converges to a
local minimum. We note, however, that local minima are typically good in the
sense of performance for neural networks and that any initialization strategy
such as the one in [9] can facilitate this local minimum. Next, we show that
our algorithm converges.

###  4.2 Theorem 2, Convergence to the equillibrium point

The proof of this theorem requires us to first prove that the maximizing
player converges. Next, we show that, provided the maximizing player provides
a strategy, the minimizing player converges. In our algorithm, we perform
$\zeta$ gradient ascent updates for each $\mathbf{w}^{(j)}.$ Therefore, we
will first show that the with many gradient ascent steps, our gradient goes to
zero.

######  Theorem 4.3 (Gradient of $\mathcal{H}_{\mathbf{k}}$ with respect to
$\mathbf{u}^{(i)}$ converges to zero).

For each task $k,$ fix $\mathbf{w}^{(j)}\in\mathcal{W}$ and construct
$\mathcal{M}=\\{\mathbf{w}^{(j)},\mathbf{\mathcal{U}}\\}.$ Let Eq. 16 be true
and sample uniformly a minibatch of size $b$ from the dataset $D$ of size $N$.
Define
$\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{(i)},\mathbf{w}^{(j)})=J_{\mathbf{k}}(\mathbf{w}^{(j)})+\beta_{1}J_{\mathbf{k}}(\mathbf{u}_{0}^{(i)},\mathbf{w}^{(j)})+\beta_{2}J_{\mathbf{k}}(\mathbf{u}_{1}^{(i)},\mathbf{w}^{(j)})+\beta_{3}J_{\mathbf{k}}(\mathbf{u}_{2}^{(i)},\mathbf{w}^{(j)})$
with $\beta_{1},\beta_{2},\beta_{3}\leq\beta>0.$ Let the inequalities from
Lemma 4.1 be true. Choose $\alpha^{(i)}_{u}=\frac{\alpha_{u}}{\sqrt{\zeta}},$
then
$\sum_{i}\alpha^{(i)}_{u}=\sum_{i}\frac{\alpha_{u}}{\sqrt{\zeta}}=\alpha_{u}\sqrt{\zeta}.$
Similarly, $\sum_{i}(\alpha^{(i)}_{u})^{2}=\alpha^{2}_{u}$ such that
$\sum_{i}(\alpha^{(i)}_{u}-\frac{M(\alpha^{(i)}_{u})^{2}}{2})=\frac{2\alpha_{u}\sqrt{\zeta}-M\alpha^{2}_{u}}{2}=S_{n}$.
Now, denote
$\Delta_{(i)}=\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{(i+1)},\mathbf{w}^{(j)})-\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{*},\mathbf{w}^{(j)}),$
then the following is true

$\underset{i=0,\cdots,\zeta}{min}E\left[\|\mathbf{g}^{(i)}_{\mathbf{u}}\|^{2}\right]\leq\frac{2\mathbb{E}[\|\mathbf{u}^{(\zeta)}-\mathbf{u}^{*}\|]}{2\alpha_{u}\sqrt{\zeta}-M\alpha^{2}_{u}}+\frac{2M(\alpha_{u})^{2}b\beta^{2}\bar{G}^{2})}{N\left(2\alpha_{u}\sqrt{\zeta}-M\alpha^{2}_{u}\right)}+\frac{2M(\alpha_{u})^{2}(b^{3}\beta^{2}\bar{G}^{2})}{N^{3}\left(2\alpha_{u}\sqrt{\zeta}-M\alpha^{2}_{u}\right)}.$

Provided $M\alpha^{2}_{u}<<\alpha_{u}\sqrt{\zeta}$, we have
$\lim_{\zeta\rightarrow\infty}\underset{i=0,\cdots,\zeta}{min}E\left[\|\mathbf{g}^{(i)}_{\mathbf{u}}\|^{2}\right]\rightarrow
0$ with the rate $\frac{1}{\sqrt{\zeta}}.$

With the result that the gradient will converge to zero for the maximizing
player, we are now ready to show the convergence of our algorithm in the sense
of gradients approaching zero. At which point, the two players will have no
incentive to change. Therefore, the Stackleberg equillibrium is attained. For
the following result, we will assume that, for each $j$ the maximizing player
has already played and provides with a $\mathbf{u}^{(\zeta)}$ as given by the
preceeding theorem.

######  Theorem 4.4 (Convergence in gradients).

For each task $k,$ construct
$\mathcal{N}=\\{\mathbf{\mathcal{U}},\mathbf{\mathcal{W}}\\}.$ Let Eq. 16 be
true and define a dataset $D$ of size $N>0.$ Assume that a minibatch of size
$b$ is obtained by uniformly sampling from $D$ and define
$\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{(i)},\mathbf{w}^{(j)})=J_{\mathbf{k}}(\mathbf{w}^{(j)})+\beta_{1}J_{\mathbf{k}}(\mathbf{u}_{0}^{(i)},\mathbf{w}^{(j)})+\beta_{2}J_{\mathbf{k}}(\mathbf{u}_{1}^{(i)},\mathbf{w}^{(j)})+\beta_{3}J_{\mathbf{k}}(\mathbf{u}_{2}^{(i)},\mathbf{w}^{(j)})$
with $\beta_{1},\beta_{2},\beta_{3}\leq\beta>0$ Consider the updates for
$\mathbf{u}^{(i)}$ as $\alpha^{(i)}_{u}\mathbf{\hat{g}}^{(i)}_{\mathbf{u}}$
and the updates for updates for $\mathbf{w}^{(j)}$ as
$\alpha^{(j)}_{w}\mathbf{\hat{g}}^{(i)}_{\mathbf{w}}$ and let the inequalities
from Lemma 4.1 provides the bounds on the variance and expected values of
these gradients. By Theorem 4.4, we obtain that the maximizing player
$\mathbf{u}^{(i)}$ converges to $\mathbf{u}^{(\zeta)}$ Furthermore, assume
that
$\alpha^{(i)}_{u}>0,b>0,\beta>0,N>0,\left\lVert\mathbf{u}^{(\zeta)}-\mathbf{u}^{*}\right\rVert^{2}\leq\delta_{w}^{2},$
and that
$\underset{j=1,2,3,\cdots\rho}{max}Var(\mathbf{g}^{(j)}_{\mathbf{w}})$ and
$\underset{j=1,2,3,\cdots\rho}{max}Var(\mathbf{g}^{(j)}_{\mathbf{w}})$ are
upper bounded by the bound provided by Lemma 4.1. Furthermore, choose,
$\alpha^{(i)}_{w}=\frac{\alpha_{w}}{\sqrt{\rho}},$ then
$\sum_{i}(\alpha^{(i)}_{w}=\sum_{i}\frac{\alpha_{w}}{\sqrt{\rho}}=\alpha_{w}\sqrt{\rho}.$
Similarly, $\sum_{i}(\alpha^{(i)}_{w})^{2}=\alpha^{2}_{w}.$ Then the minimum
value of the gradient is bounded as

(22)
$\displaystyle\underset{j=1,2,3,\cdots\rho}{min}\mathbb{E}\left[\|\mathbf{g}^{(j)}_{\mathbf{w}}\|^{2}\right]$
$\displaystyle\leq\frac{2\rho\mathbb{E}\left[\delta_{u}^{2}\right](M+1)+2(1+3\beta)G\delta_{w}2}{2\alpha_{w}\sqrt{\rho}-L_{w}\alpha^{2}_{w}}+\frac{L(\alpha_{\mathbf{w}})^{2}b}{N(2\alpha_{w}\sqrt{\rho}-L\alpha^{2}_{w})}$
$\displaystyle+\frac{\beta\rho
b^{2}\bar{G}^{2}}{N^{2}(2\alpha_{w}\sqrt{\rho}-L_{w}\alpha^{2}_{w})}+\frac{G^{2}(1+3\beta)^{2}L_{w}(\alpha_{\mathbf{w}})^{2}b^{3}}{(N^{3}2\alpha_{w}\sqrt{\rho}-L_{w}\alpha^{2}_{w})}.$

where $G$ and $\bar{G}$ are provided by Lemma 4.1 with and the gradient
converges asymptotically to zero with the rate $\frac{1}{\sqrt{\rho}}$ under
the assumption that $2\alpha_{w}\sqrt{\rho}>>L_{w}\alpha^{2}_{w}$ .

Note that the convergence again depends on how effectively the parameters are
initialized. Moreover, the equilibrium is not exact but approximate; that is,
the pair $(\mathbf{u}^{(i)},\mathbf{w}^{(j)})$ reaches within a ball around a
local equilibrium point $(\mathbf{u}^{*},\mathbf{w}^{*}).$ The size of this
ball is dependent on the batch size, learning rate $\alpha_{w}$, size of
$D^{P}_{k}$, and number of updates $\zeta$ and $\rho$. These ideas cater to
the usual intuition that the larger the dataset, the better the convergence.
Similarly, a large number of updates lead to convergence, and better
initialization always allows a network to approach a better minimum. The
theorems and proofs presented in this section are the first convergence
results for using stochastic gradient ascent-descent strategies in the GCL
literature.

##  5 Experiments

We consider the Cora, CiteSeer, and Reddit datasets [35] for vertex
classification problems and consider Mutag and Proteins [18] for graph
classification. We compare our method with the state-of-the-art experience
replay-driven method in the GCL literature [35]. Note that [35] reports
results only on vertex classification problems. We adopted the experimental
setting and datasets from the current state-of-the-art papers [35] and [17].
In this way we can ensure a fair comparison between two experience-replay-
based methods. Furthermore, we fix the size of the memory buffer to be 500.
Given the lack of large CL benchmarks for graphs, we conducted a unique large-
scale hyperparameter search (with 1,000 high-performing hyperparameter
configurations) to confirm the robustness of our approach. Moreover, we
conducted ablation studies to establish the effectiveness of different
components of our method. With all these experimental results, we seek to
mitigate the dearth of large standard GCL benchmarks for empirical comparison.
We compared our method with other methods on vertex classification datasets.
We utilized graph classification datasets to study and analyze the stability
of our approach to different hyperparameters. All experiments were conducted
in Python 3.4 using the pytorch $1.7.1$ library with the NVIDIA-A100 GPU.

Table 1: Vertex classification problem

| Cora | CiteSeer | Reddit
---|---|---|---
|  PM$\uparrow$ |  PM$\uparrow$. |  PM$\uparrow$
DeepWalk | 85.63 | 64.79 | 76.93
node2Vec | 85.99 | 65.18 | 78.24
GraphSage | 94.15 | 81.26 | 95.01
GIN | 90.17 | 74.92 | 93.75
GCN | 93.62 | 80.63 | 94.43
SGC | 93.06 | 78.18 | 94.01
GAT | 94.19 | 81.48 | 93.84
ER-GAT-MF | 94.15 | 80.03 | 94.18
ER-GAT-MF* | 94.23 | 81.83 | 94.63
ER-GAT-CM | 93.98 | 78.78 | 93.33
ER-GAT-CM* | 94.25 | 80.86 | 94.23
ER-GAT-IM | $\mathbf{95.66}$ | 80.85 | $\mathbf{95.36}$
Ours | $91.51$ | $\mathbf{90.34}$ | $94.32$
(a) Performance mean (PM)

Cora | CiteSeer | Reddit
---|---|---
FM$\downarrow$ |  FM$\downarrow$ |  FM$\downarrow$
34.51 | 25.92 | 33.24
35.46 | 24.87 | 34.66
37.73 | 28.06 | 40.06
33.81 | 27.42 | 36.28
31.90 | 25.47 | 35.17
33.93 | 28.31 | 38.59
30.84 | 23.73 | 32.79
22.49 | 17.96 | 26.44
21.88 | 17.83 | 23.54
22.14 | 18.03 | 26.17
21.03 | 17.86 | 23.15
21.14 | 17.08 | 23.09
$\mathbf{7.58}$ | $\mathbf{3.64}$ | $\mathbf{14.21}$
(b) Forgetting metric (FM)

Metrics: We used the same metrics as in [35] for comparison: performance mean
(PM) and forgetting mean (FM). These metrics use either accuracy ($acc$) or
micro-F1 score ($f_{1}$) based on the dataset. Whenever a new task was
observed, we recorded two quantities: (i) task $acc$ or $f_{1}$ of the model
on the new task and (ii) forgetting $acc$ or $f_{1}$—the difference in the
$acc$ or $f_{1}$ of the model before and after the new task was observed. Once
all the tasks are observed, FM is observed as the average forgetting $acc$ or
$f_{1}$, and PM is observed as the average task $acc$ or $f_{1}$. For PM, the
higher score is better; for FM, the lower score is better. Note, however, note
that the value of PM is not upper bounded by the FM value since the PM values
are the measure of pure generalization, whereas FM is the metric of both
generalization and forgetting. A methodology is high performing if it achieves
low FM and high PM.

Vertex classification: The baselines for the vertex classification problem are
directly taken from [35]. They are Deepwalk [20], node2Vec [10], graph
convolutional networks [13] (GCNs), GraphSAGE [11], Graph Attention [27]
(GAT), Simple Graph Convolutions [30] (SGC), and Graph Isomorphism Network
[32] (GIN). Furthermore, the work in [35] introduces five new models: ER-GAT-
MF, ER-GAT-MF*, ER-GAT-CM, ER-GAT-CM*, and ER-GAT-IM, where MF is the mean of
the attributes, MF* is the mean of embeddings, CM is the attribute space
coverage maximization, CM is the embedding space maximization, and IM is the
influence maximization. As in [35] we constructed three 2-way tasks, namely,
two classes per task for the Cora and CiteSeer datasets. For Reddit, we
constructed eight 5-way tasks. For the network, we utilized two layers of GAT
with two layers of dropouts, similar to what is used in [35]. We used the Adam
optimizer learning rate of $10^{-03}$ for gradient descent and $10^{-07}$ for
gradient ascent with $\rho=1000$ and $\zeta=10$; and we utilized the 80-20
training-testing split. We use double precision for all our simulations and
therefore, even $10^{-07}$ introduces changes in the weights. We summarize
these results in Table 1b and Table 1a. We evaluate FM and PM on $acc$ for
Cora while evaluating these metrics on $f_{1}$ score for Reddit and CiteSeer,
as in [35]. We report the mean and standard deviation of these metrics over
100 runs, where a distinct random seed was utilized for each run, and mark the
best scores in bold.

Except for our results, all other numbers are taken directly from [35] where
no standard deviation numbers or results on PubMed were reported. The results
show that our approach achieves superior performance in the FM when compared
with all methods discussed in [35]. To quantify, for Cora, our method obtains
an FM of $7.58$, which is 67% improvement over ER-GAT-IM with $21.14$:
$\left((21.14-7.58)/21.14)\times 100\right)$. Similarly, 78% and 44%
improvements are observed in CiteSeer and Reddit datasets, respectively.

Our method also does well on the PM scale: the PM values achieved by our
method are either comparable to or better than all the others. These results
are reflected in the last two rows of Table 1a. Earlier, we claimed that a
good GCL methodology must achieve a balance between generalization and
forgetting. A low FM value coupled with a high PM value supports this claim
and supports the narrative of Theorem 1, where it was shown that such a
balance point exists.

Stability analysis: Next we demonstrate the stability of our approach to
supporting the claims of Theorem 2. We utilized the graph classification
datasets Mutag and Protein for this study. In both these cases, we used the
60-20-20 split for training-testing and validation. We are able to report
scores only for our method in Table 2 since the only method available for
comparison [35] does not report any $acc/f_{1}$ on graph classification
problems. In the first row of Table 2, we report the performance using 1-FM
that is achieved by training a model on all the tasks together (assuming all
the data from these tasks is available); we call this joint training. For any
continual learning approach, the accuracy achieved by joint training is an
absolute upper bound. In what follows we study the impact of hyperparameters
on the effectiveness of our proposed GCL method. To that end, we utilized
DeepHyper (DH) [6]—a scalable software package for hyperparameter tuning.
Leveraging DH, we ran a hyperparameter search where we selected hyperparameter
configurations ($nlays$–number of layers, $drop$– dropout rate, $hc$– number
of hidden channels in graph attention layers with $\alpha,\rho$ and $\zeta$)
that improve the objective $(FM).$ Once DH has run for a sufficient number of
iterations, we selected the hyperparameters that provide top 30% quantile of
objective values (FM) distribution.

Figure 2: (left) Histograms of different hyperparameter configurations found
by DeepHyper and (right) the corresponding FM distribution.

To observe the variance of the objective values corresponding to these
hyperparemters selected by DH, we seek to understand what are the different
sets of hyperparameters that provide good FM for these datasets. Typically, if
DH has been executed for a large number of iterations, the hyperparameters
providing the top 30% quantile FM value would be high performing (will provide
extremely high values of FM). However, running DH for such a long number of
iterations requires considerable high-performance computing resources. To
alleviate this need, we fit a Gaussian copula [19] (GC) to mimic the
distribution of these hyperparameters (those providing the top 30% quantile in
FM) and sample 1,000 new high-performing hyperparameters. We then evaluated
all of them in the CL setting in parallel with a distinct random seed.

In Table Table 2 we record the best, worst, and $mean\pm std$ values obtained
by these 1,000 models. Furthermore we jointly trained a model using the
hyperparameter configuration that provided the best FM values according to DH;
the score is recorded in the first row in Table 2. Note that for both
datasets, the best accuracy is close to the upper bound achieved by jointly
training a model, while the worst $acc$ are farther away from the mean.

In Fig. 2 (right), we record the histogram of different FM values obtained by
our approach when DH is utilized to find appropriate hyperparameters. Note
that for both datasets, the FM values are skewed toward the mean (the mean is
coinciding with the mode). In the left and middle of Fig. 2, we plot the
histograms of different hyperparameter values found by DH. In addition to
indicating to the practitioner which hyperparameters are good for using our
methodology, they illustrate several other insights. The histogram of
hyperparameters for each dataset is distinct, and the histograms for these
hyperparameters are broad. For instance, the values of $\rho$ range for Mutag
vary between 1 and 4000. Theses observations, together with the fact that the
mean FM is skewed toward the mode, indicate that our approach is very stable
to different hyperparameter configurations and different initializations of
weights. In other words, even with varying hyperparameters and initial values
of weights, our approach provides reasonable FMs.

| Mutag | Proteins
---|---|---
|  (1-FM)$\uparrow$ |  (1-FM)$\uparrow$
Joint training | $93$ | $66$
Best | $94$ | $66$
Worst | $68$ | $40$
Mean(std) | $83\pm 6.1$ | $56\pm 7$
Table 2: Scores on graph classification. The best, minimum, and mean(std) are
evaluated based on DeepHyper’s hyperparameter search. Joint training refers to
the process of training a model on all the tasks together.

Since the histogram of a particular hyperparameter for the two datasets is
very distinct, hyperparameter configurations cannot be commonly set for
different datasets. Furthermore, our results follow several commonly held
notions with respect to setting hyperparameters. A larger number of layers
appear to favor the top 30% quantile of FM. Furthermore, larger $\rho$ and
large $\zeta$ are favored (mean around $3000$ in both cases). The intuition is
that within the two-player game, more updates for both the outer loop and the
inner loop lead to better convergence (supports the validity of Theorem 2
result where asymptotic convergence is guaranteed). Peculiarly, larger dropout
values are also favored. More investigation is required to analyze this
behavior. A larger number of layers also appear to provide better performance,
which also adheres to the intuition that better performance for deeper
architectures.

Ablation study: Our cost function
$\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{(i)},\mathbf{w}^{(j)})$, which
summarizes the game of two players $\mathbf{u}^{(i)}$ and $\mathbf{w}^{(j)}$,
comprises four terms as in Eq. 12. Here, the first term summarizes the
forgetting and generalization cost. The second and third terms quantify the
impact of simulated change in graphs. The fourth term quantifies the impact of
simulated change in the parameters of the model. In this study we provide
insight into the contribution of these different terms on the performance of a
model (a GAT with two dropout layers) for the Mutag dataset. Specifically, we
initialize a model using high-performing hyperparameters (chosen through DH)
and perform three experiments. We perform CL on Mutag and record the FM score
over 10 runs (each run is executed with distinct random seed) when (1) all
terms in $\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{(i)},\mathbf{w}^{(j)})$ are
utilized; (2) first, second, and third terms in
$\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{(i)},\mathbf{w}^{(j)})$ are utilized;
and (3) just the first term in
$\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{(i)},\mathbf{w}^{(j)})$ is utilized.

While the second scenario is equivalent to the case when we switch off the
game, the third scenario is equivalent to regular experience replay strategy.
We observe that the best performance on the Mutag dataset is observed when all
the terms in the cost are utilized and the two-player game is played. We
attain a performance of 89%. When the game is switched off, we suffer a 14%
deterioration, and the deterioration further increases by switching off the
regularization term where a 21% deterioration in performance is observed. The
study proves that the game actually does contribute to improved performance in
the graph continual learning scenario.

##  6 Conclusion

We presented a new theoretical framework for graph continual learning. We
modeled the stochastic process underlying the GCL problem as a vertex edge
random graph. We formulated the GCL problem from an adaptive dynamic
programming viewpoint and derived a partial differential equation to model the
dynamics of GCL. We developed a theoretically sound two-player game-driven
methodology for the GCL setting. We demonstrated that our proposed method
achieved 44% improvement compared with the state of the art on vertex
classification benchmarks. We presented an ablation study, wherein we showed
that the game performance improves by 21%. With a large-scale analysis we
confirmed that our approach is stable to a variety of hyperparameters.

Our future work will include (1) GCL for spatial-temporal data, (2) GCL for
other classes of non-Euclidean data, (3) development of problem-agnostic
representation learning for GCL, and (4) applications to molecule property
prediction tasks.

##  7 Acknowledgement

This work is funded by the Department of Energy under the Integrated
Computational and Data Infrastructure (ICDI) for Scientific Discovery, grant
DE-SC0022328. We also acknowledge the support by the U.S. Department of Energy
for the SCIDAC5-RAPIDS institute and the DOE Early Career Research Program
award. This research used resources of the Argonne Leadership Computing
Facility, which is a DOE Office of Science User Facility supported under
Contract DE-AC02- 06CH11357.

##  8 Preliminaries

The GCL task is given as

######  Definition 4 (GCL task in the continuous sense).

For $t,\Delta t\in\mathbf{\Omega}$, define the interval $[t,t+\Delta t]$ and
let $(\mathcal{G}_{V}(t),P_{\mathbf{x}(t)\times\phi(t)})$ represent a VERG
associated with GCL. Denote the GNN model as
$g(.,.,\mathbf{w}(t)):\mathbf{\Omega}\rightarrow\mathbb{R}^{n}$ with a loss
function given as $\ell:\mathbb{R}^{n}\rightarrow\mathbb{R}.$ Let
$J(\mathbf{x}([t,t+\Delta t]),\phi([t,t+\Delta t]),\mathbf{w}([t,t+\Delta
t]))=\int_{\tau=t}^{t+\Delta
t}\ell(\mathbf{x}_{\mathbf{V}}(\tau),\phi_{\mathbf{V}}(\tau),\mathbf{w}(\tau))]$
be the forgetting and generalization cost over the interval $[t,t+\Delta t].$
Then, a GCL task $\mathcal{T}([t,t+\Delta t])$ is described by the tuple

(23) $\Big{(}\mathbf{x}([t,t+\Delta t]),\phi([t,t+\Delta
t]),J(\mathbf{x}([t,t+\Delta t]),\phi([t,t+\Delta t]),\mathbf{w}([t,t+\Delta
t]))\Big{)}$

with $\mathbf{x}([t,t+\Delta
t])=\\{\mathbf{x}_{\mathbf{V}}(\tau)\forall\tau\in[t,t+\Delta
t]\\}_{\mathbf{V}(t)}$ and $\phi([t,t+\Delta
t])=\\{\mathbf{\phi}_{\mathbf{V}}(\tau)\forall\tau\in[t,t+\Delta
t]\\}_{\mathbf{V}(t)}$

For simplicity of notations, we will denote the task as
$\mathcal{T}_{[t,t+\Delta t]}$ which is described by the tuple
$\left((\mathbf{x},\phi)_{[t,t+\Delta t]},J_{[t,t+\Delta
t]}(\mathbf{x},\phi,\mathbf{w})\right)$ where the subscript indicates the
interval over which the task is defined. This notation, easily extends to a
collection of tasks. For instance, all the tasks in the interval $[0,t]$ are
collectively provided by $\mathcal{T}_{[0,t]}.$ As we use $\mathbf{t}$ to
represent the interval $[0,t],$ it follows that $\mathcal{T}_{[0,t]}$ is
rewritten as $\mathcal{T}_{\mathbf{t}}$ which represents all tasks in the
interval $[0,t]$ where
$\mathcal{T}_{\mathbf{t}}=\left((\mathbf{x},\phi)_{\mathbf{t}},J_{\mathbf{t}}(\mathbf{x},\phi,\mathbf{w})\right)$
with
$J_{\mathbf{t}}(\mathbf{x},\phi,\mathbf{w})=\int_{\tau=0}^{t}\ell(\mathbf{x}(\tau),\phi(\tau),\mathbf{w}(\tau)).$
This notation naturally extends to the case when $\mathbf{\Omega}$ is
comprised of discrete instance as well. In this case, we will set $\Delta t=1$
and replace $t$ by $k$ such that $[0,t]=[0,k]=[0,1,2,3,\cdots,k]=\mathbf{k}$
Furthermore, the collection of all tasks in the interval $[0,k]$ is given by
$\mathcal{T}_{\mathbf{k}}=\left((\mathbf{x},\phi)_{\mathbf{k}},\ell_{\mathbf{k}}(\mathbf{x}_{\mathbf{V}},\phi_{\mathbf{V}},\mathbf{w})\right)$
with
$J_{\mathbf{k}}(\mathbf{x},\phi,\mathbf{w})=\sum_{\tau=0}^{k}\ell(\mathbf{x}(\tau),\phi(\tau),\mathbf{w}(\tau))$
where $g(\mathbf{x}(k),\phi(k))$ is the parametric map and
$\ell(\mathbf{x}(k),\phi(k),\mathbf{w}(k))$ is the corresponding loss with the
VERG defined by the probability space
$(\mathcal{G}(k),P_{\mathbf{x}(k)\times\phi(k)})),k\in\mathbf{\Omega}.$

##  9 Dynamical System Modelling

######  Proposition 9.1 (Dynamics of the GCL problem).

Define a domain $\mathbf{\Omega}$ with $t\in\mathbf{\Omega}$ and a vertex set
$\mathbf{V}(t):\mathbf{\Omega}\rightarrow\boldsymbol{\mathcal{V}}|\mathbf{V}(t)\subset\boldsymbol{\mathcal{V}}$
Then, define the CL task as in 4. For each $\mathbf{t}\subset\mathbf{\Omega}$
let

(24) $\displaystyle
L^{*}_{\mathbf{t}}=\underset{\mathbf{w}(\mathbf{t})}{min}\int_{\tau=t}^{\Omega}J_{\boldsymbol{\tau}}(\mathbf{x},\phi,\mathbf{w})$

as the GCL problem. Assume $J_{\mathbf{t}}(\mathbf{x},\phi,\mathbf{w})$ to be
smooth with respect to all its arguments. Under the assumption that
$R(\mathbf{t})$ denotes all the higher order terms in a Taylor series
expansion, the following is true

(25)
$\displaystyle-\left(\partial_{\mathbf{t}}L^{*}_{\mathbf{t}}\right)^{T}\Delta_{\mathbf{t}}$
$\displaystyle=\underset{\mathbf{w}(\mathbf{t})}{min}\Big{[}J_{\mathbf{t}}(\mathbf{x},\phi,\mathbf{w})+\left(\partial_{\mathbf{x}_{\mathbf{t}}}L^{*}_{\mathbf{t}}\right)^{T}\Delta_{\mathbf{x}}$
$\displaystyle+\left(\partial_{\phi_{\mathbf{t}}}L^{*}_{\mathbf{t}}\right)^{T}\Delta_{\phi}+\left(\partial_{\mathbf{w}_{\mathbf{t}}}L^{*}_{\mathbf{t}}\right)^{T}\Delta_{\mathbf{w}}+R_{\mathbf{t}},\Big{]}$

where $\Delta{x}$ refers to the first derivative of $x$ with respect to
$\mathbf{t}.$

######  Proof 9.2.

Let the GCL problem be given as

(26) $\displaystyle
L^{*}_{\mathbf{t}}=\underset{\mathbf{w}_{\mathbf{t}}}{min}\int_{\tau=t}^{\Omega}J_{\tau}(\mathbf{x},\phi,\mathbf{w}).$

Split the integral with the time interval $,t$rewrite the optimization problem
as

(27) $\displaystyle L_{\mathbf{t}}^{*}$ $\displaystyle=$
$\displaystyle\Big{[}\underset{\mathbf{w}_{\mathbf{t}}}{min}\quad
J_{\mathbf{t}}(\mathbf{x},\phi,\mathbf{w})+\int_{\tau=t+\Delta
t}^{\Omega}\underset{\mathbf{w}_{\tau}}{min}\quad
J_{\mathbf{\tau}}(\mathbf{x},\phi,\mathbf{w})\Big{]}$

Using the policy $\mathbf{w}_{\mathbf{t}}$ if we begin at $\mathbf{t},$
$L_{\mathbf{t}}^{*}$ provides the optimal cost over the complete interval.
Since, $\underset{\mathbf{w}_{\mathbf{t}}}{min}\int_{t}^{\Omega}$
$J_{\mathbf{t}}(\mathbf{x},\phi,\mathbf{w}).$ is $L_{\mathbf{t}}^{*}$, then it
stands to reason that $\underset{\mathbf{w}_{\mathbf{t}}}{min}$
$\int_{\tau=t+\Delta t}^{\Omega}J_{\mathbf{t}}(\mathbf{x},\phi,\mathbf{w}).$
is the optimal cost after $\mathbf{t}.$ That is, it is the optimal cost for
the interval $\mathbf{\Omega}^{C}$ while following policy
$\mathbf{w}(\mathbf{t}),$ which we denote as $L^{*}_{\mathbf{t}^{+}}$ This
provides

(28) $\displaystyle
L^{*}_{\mathbf{t}}=\underset{\mathbf{w}_{\mathbf{t}}}{min}\Big{[}J_{\mathbf{t}}(\mathbf{x},\phi,\mathbf{w})+L^{*}_{\mathbf{t}^{+}}\Big{]}.$

Now, all the information about the future must be approximated using
$\mathbf{t}.$ To do this approximation, we will write the Taylor series
expansion of $L^{*}_{\mathbf{t}^{+}}$ around $\mathbf{t}.$ Since

$V^{*}:\mathbf{\Omega}\rightarrow(\mathcal{X},\Phi)\rightarrow\mathbf{G}\xrightarrow[]{\mathbf{w}}\mathbb{R}.$

Taylor series expression is expanded around

$(\mathbf{t},\mathbf{w}(\mathbf{t}),\mathbf{x}(\mathbf{t}),\phi(\mathbf{t})).$

to obtain

(29)
$L^{*}_{\mathbf{t}^{+}}=L^{*}_{\mathbf{t}}+\left(\partial_{\mathbf{t}}L^{*}_{\mathbf{t}}\right)^{T}\Delta_{\mathbf{t}}+\left(\partial_{\mathbf{x}_{\mathbf{t}}}L^{*}_{\mathbf{t}}\right)^{T}\Delta_{\mathbf{x}}\\\
+\left(\partial_{\phi_{\mathbf{t}}}L^{*}_{\mathbf{t}}\right)^{T}\Delta_{\phi}\
+\left(\partial_{\mathbf{w}_{\mathbf{t}}}L^{*}_{\mathbf{t}}\right)^{T}\Delta_{\mathbf{w}}+\cdots,$

Substitution into (28) reveals

(30)
$L^{*}_{\mathbf{t}}=\underset{\mathbf{w}_{\mathbf{t}}}{min}\Big{[}J_{\mathbf{t}}(\mathbf{x},\phi,\mathbf{w})+L^{*}(\mathbf{t})+\left(\partial_{\mathbf{t}}L^{*}(\mathbf{t})\right)^{T}\Delta_{\mathbf{t}}+\left(\partial_{\mathbf{x}_{\mathbf{t}}}L^{*}_{\mathbf{t}}\right)^{T}\Delta_{\mathbf{x}}\\\
+\left(\partial_{\phi_{\mathbf{t}}}L^{*}_{\mathbf{t}}\right)^{T}\Delta_{\phi}+\left(\partial_{\mathbf{w}_{\mathbf{t}}}L^{*}_{\mathbf{t}}\right)^{T}\Delta_{\mathbf{w}}+\cdots,\Big{]}$

We will now cancel the common terms and write

$\displaystyle 0$
$\displaystyle=\underset{\mathbf{w}_{\mathbf{t}}}{min}\Big{[}J_{\mathbf{t}}(\mathbf{x},\phi,\mathbf{w})+\left(\partial_{\mathbf{t}}L^{*}_{\mathbf{t}}\right)^{T}\Delta_{\mathbf{t}}+\left(\partial_{\mathbf{x}_{\mathbf{t}}}L^{*}_{\mathbf{t}}\right)^{T}\Delta_{\mathbf{x}}$
(31)
$\displaystyle+\left(\partial_{\phi_{\mathbf{t}}}L^{*}_{\mathbf{t}}\right)^{T}\Delta_{\phi}+\left(\partial_{\mathbf{w}_{\mathbf{t}}}L^{*}_{\mathbf{t}}\right)^{T}\Delta_{\mathbf{w}}+R_{\mathbf{t}},\Big{]}$

where $R(\mathbf{t})$ summarizes all the terms in the $\cdots$, i.e, the
higher order terms from the Taylor series. Moving terms in the equation
provides graph PDE as

$\displaystyle-\left(\partial_{\mathbf{t}}L^{*}(\mathbf{t})\right)^{T}\Delta_{\mathbf{t}}$
$\displaystyle=\underset{\mathbf{w}(\mathbf{t})}{min}\Big{[}J_{\mathbf{t}}(\mathbf{x},\phi,\mathbf{w})+\left(\partial_{\mathbf{x}_{\mathbf{t}}}L^{*}_{\mathbf{t}}\right)^{T}\Delta_{\mathbf{x}}$
(32)
$\displaystyle+\left(\partial_{\phi_{\mathbf{t}}}L^{*}_{\mathbf{t}}\right)^{T}\Delta_{\phi}+\left(\partial_{\mathbf{w}_{\mathbf{t}}}L^{*}_{\mathbf{t}}\right)^{T}\Delta_{\mathbf{w}}+R_{\mathbf{t}},\Big{]}$

##  10 Discrete Time Approximation

######  Proposition 10.1.

Let $\mathbf{k}\in\mathbf{\Omega}$ and define
$\mathcal{W},\mathbf{\mathcal{X}},\mathbf{\Phi}$ such that
$\Delta_{\mathbf{w}}^{(i)}\times\Delta^{(i)}_{\phi}\times\Delta^{(i)}_{\mathbf{x}}\in\mathcal{W}\times\mathbf{\Phi}\times\mathbf{\mathcal{X}}$
and assume that

(33a) $\displaystyle sup_{\mathbf{\mathcal{X}}}L^{*}_{\mathbf{k}}$
$\displaystyle\leq
inf_{\mathbf{\mathcal{X}}}J_{\mathbf{k}}(\mathbf{x},\phi,\mathbf{w}^{(j)})\leq
max_{\mathbf{\Delta}^{(i)}_{\mathbf{x}_{\mathbf{k}}}\in\mathbf{\mathcal{X}}}J_{\mathbf{k}}(\mathbf{x}+\mathbf{\Delta}_{\mathbf{x}}^{(i)},\phi,\mathbf{w}^{(j)})$
(33b) $\displaystyle sup_{\mathbf{\Phi}}L^{*}_{\mathbf{k}}$ $\displaystyle\leq
inf_{\mathbf{\Phi}}J_{\mathbf{k}}(\mathbf{x},\phi,\mathbf{w}^{(j)})\leq
max_{\Delta^{(i)}_{\phi_{\mathbf{k}}}\in\mathbf{\Phi}}J_{\mathbf{k}}(\mathbf{x},\phi+\Delta^{(i)}_{\phi},\mathbf{w}^{(j)})$
(33c) $\displaystyle sup_{\mathcal{W}}L^{*}_{\mathbf{k}}$ $\displaystyle\leq
inf_{\mathcal{W}}J_{\mathbf{k}}(\mathbf{x},\phi,\mathbf{w}^{(j)})\leq
max_{\Delta^{(i)}_{\mathbf{w}}\in\mathcal{W}}J_{\mathbf{k}}(\mathbf{x},\phi,\mathbf{w}^{(j)}+\Delta^{(i)}_{\mathbf{w}})$
(33d) $\displaystyle inf_{\mathbf{\mathcal{X}}}L^{*}_{\mathbf{k}}$
$\displaystyle\geq 0,inf_{\mathbf{\Phi}}L^{*}_{\mathbf{k}}\geq
0,inf_{\mathcal{W}}L^{*}_{\mathbf{k}}\geq 0.$

Then, define
$\mathcal{H}(\Delta^{(i)}_{\phi},\Delta^{(i)}_{\mathbf{x}},\mathbf{x},\phi,\mathbf{w}^{(j)})=J_{\mathbf{k}}(\mathbf{x},\phi,\mathbf{w}^{(j)})+\left(\partial_{\mathbf{x}_{\mathbf{k}}}L^{*}_{\mathbf{k}}\right)^{T}\Delta^{(i)}_{\mathbf{x}_{\mathbf{k}}}\\\
+\left(\partial_{\phi_{\mathbf{k}}}L^{*}_{\mathbf{k}}\right)^{T}\Delta_{\phi_{\mathbf{k}}}+\left(\partial_{\mathbf{w}^{(j)}_{\mathbf{k}}}L^{*}_{\mathbf{k}}\right)^{T}\Delta^{(i)}_{\mathbf{w}_{\mathbf{k}}}$
and the following approximation is true

(34) $\displaystyle
H_{\mathbf{k}}(\Delta^{(i)}_{\phi},\Delta^{(i)}_{\mathbf{x}},\Delta^{(i)}_{\mathbf{w}},\mathbf{x},\phi,\mathbf{w}^{(j)})\leq
max_{\Delta_{\mathbf{w}_{\mathbf{k}}}^{(i)}\times\Delta^{(i)}_{\phi_{\mathbf{k}}}\times\Delta^{(i)}_{\mathbf{x}_{\mathbf{k}}}\in\mathcal{W}\times\mathbf{\Phi}\times\mathbf{\mathcal{X}}}$
$\displaystyle\Big{[}J_{\mathbf{k}}(\mathbf{x},\phi,\mathbf{w}^{(j)})+\beta_{1}J_{\mathbf{k}}(\mathbf{x}+\mathbf{\Delta}_{\mathbf{x}}^{(i)},\phi,\mathbf{w}^{(j)})+\beta_{2}J_{\mathbf{k}}(\mathbf{x},\phi+\Delta^{(i)}_{\phi},\mathbf{w}^{(j)})$
$\displaystyle+\beta_{3}J_{\mathbf{k}}(\mathbf{x},\phi,\mathbf{w}^{(j)}+\Delta^{(i)}_{\mathbf{w}}),\Big{]}$

where $\beta_{k}\in\mathbb{R}\cup[0,1],\forall k$ and $\zeta\in\mathbb{N}$
indicates finite difference updates.

######  Proof 10.2.

######  Remark 10.3.

Note that the value function is a function of all the arguments in the ODE.
That is,
$\Delta^{(i)}_{\phi},\Delta^{(i)}_{\mathbf{x}},\Delta^{(i)}_{\mathbf{w}},\mathbf{x},\phi,\mathbf{w}^{(j)}$
but the arguments are not explicitly denoted for notational simplicity. Just
for this proposition, we shall indicate the arguments when required to
describe the dependence through which the first derivatives shall exist. After
the following proposition, we go back to the original notation of
$L_{\mathbf{k}}^{*}.$

By Euler’s approximation, we obtain

(35)
$\displaystyle\left(\partial_{\mathbf{x}_{\mathbf{k}}}L^{*}_{\mathbf{k}}\right)^{T}\Delta^{(i)}_{\mathbf{x}}$
$\displaystyle=\left(L^{*}_{\mathbf{k}}(\mathbf{x}+\Delta_{\mathbf{x}}^{(i)})-L^{*}_{\mathbf{k}}(\mathbf{x})\right)\frac{\left(\Delta_{\mathbf{x}}^{(i)}\right)}{\left(\Delta_{\mathbf{x}}^{(i)}\right)^{T}}$
$\displaystyle=\frac{L^{*}_{\mathbf{k}}(\mathbf{x}+\Delta_{\mathbf{x}}^{(i)})-L^{*}_{\mathbf{k}}}{\Delta_{\mathbf{k}}}$
$\displaystyle\leq\frac{sup_{\mathbf{\mathcal{X}}}L^{*}_{\mathbf{k}}-inf_{\mathbf{\mathcal{X}}}L^{*}_{\mathbf{k}}}{\Delta_{\mathbf{k}}}$
$\displaystyle\leq\frac{1}{\Delta_{\mathbf{k}}}max_{\mathbf{\Delta}_{\mathbf{x}}^{(i)}\in\mathbf{\mathcal{X}}}J_{\mathbf{k}}(\mathbf{x}+\mathbf{\Delta}_{\mathbf{x}}^{(i)},\phi,\mathbf{w}^{(j)})$
$\displaystyle\leq\beta_{1}max_{\mathbf{\Delta}_{\mathbf{x}}^{(i)}\in\mathbf{\mathcal{X}}}J_{\mathbf{k}}(\mathbf{x}+\mathbf{\Delta}_{\mathbf{x}}^{(i)},\phi,\mathbf{w}^{(j)}),\forall\beta_{1}\in\mathbb{R}^{+}$

Where the fourth and fifth inequality follows from assumption and † indicates
the psuedo inverse. Similarly, we may write

(36)
$\displaystyle\left(\partial_{\phi_{\mathbf{k}}}L^{*}_{\mathbf{k}}\right)^{T}\Delta_{\phi}$
$\displaystyle\leq\beta_{2}max_{\mathbf{\Delta}^{(i)}_{\phi_{\mathbf{k}}}\in\mathbf{\Phi}}J_{\mathbf{k}}(\mathbf{x},\phi+\Delta^{(i)}_{\phi},\mathbf{w}^{(j)})$
$\displaystyle\left(\partial_{\mathbf{w}^{(j)}_{\mathbf{k}}}L^{*}_{\mathbf{k}}\right)^{T}\Delta^{(i)}_{\mathbf{w}}$
$\displaystyle\leq\beta_{3}max_{\mathbf{\Delta}_{\mathbf{w}_{\mathbf{k}}}^{(i)}\in\mathcal{W}}J_{\mathbf{k}}(\mathbf{x},\phi,\mathbf{w}^{(j)}+\Delta^{(i)}_{\mathbf{w}})$

with $\beta_{2},\beta_{3}\in\mathbb{R}^{+},$ we obtain

$\displaystyle
H_{\mathbf{k}}(\Delta^{(i)}_{\phi},\Delta^{(i)}_{\mathbf{x}},\mathbf{x},\phi,\mathbf{w}^{(j)})$
$\displaystyle\leq J_{\mathbf{k}}(\mathbf{x},\phi,\mathbf{w}^{(j)})$
$\displaystyle+\beta_{1}max_{\mathbf{\Delta}_{\mathbf{x}}^{(i)}\in\mathbf{\mathcal{X}}}J_{\mathbf{k}}(\mathbf{x}+\mathbf{\Delta}_{\mathbf{x}}^{(i)},\phi,\mathbf{w}^{(j)})$
$\displaystyle+\beta_{2}max_{\mathbf{\Delta}_{\phi}^{(i)}\in\mathbf{\Phi}}J_{\mathbf{k}}(\mathbf{x},\phi+\Delta^{(i)}_{\phi},\mathbf{w}^{(j)})$
$\displaystyle+\beta_{3}max_{\mathbf{\Delta}_{\mathbf{w}}^{(i)}\in\mathcal{W}}J_{\mathbf{k}}(\mathbf{x},\phi,\mathbf{w}^{(j)}+\Delta^{(i)}_{\mathbf{w}})$

Pulling the maximization outside provides the result.

(37) $\displaystyle
H_{\mathbf{k}}(\Delta^{(i)}_{\phi},\Delta^{(i)}_{\mathbf{x}},\Delta^{(i)}_{\mathbf{w}},\mathbf{x},\phi,\mathbf{w}^{(j)})\leq
max_{\Delta_{\mathbf{w}_{\mathbf{k}}}^{(i)}\times\Delta^{(i)}_{\phi_{\mathbf{k}}}\times\Delta^{(i)}_{\mathbf{x}_{\mathbf{k}}}\in\mathcal{W}\times\mathbf{\Phi}\times\mathbf{\mathcal{X}}}$
$\displaystyle\Bigg{[}J_{\mathbf{k}}(\mathbf{x},\phi,\mathbf{w}^{(j)})+\beta_{1}J_{\mathbf{k}}(\mathbf{x}+\mathbf{\Delta}_{\mathbf{x}}^{(i)},\phi,\mathbf{w}^{(j)})$
$\displaystyle+\beta_{2}J_{\mathbf{k}}(\mathbf{x},\phi+\Delta^{(i)}_{\phi},\mathbf{w}^{(j)})+\beta_{3}J_{\mathbf{k}}(\mathbf{x},\phi,\mathbf{w}^{(j)}+\Delta^{(i)}_{\mathbf{w}})\Bigg{]}$

##  11 Theoretical Analysis

First, we will show that the gradients are bounded under the following
assumption The function $J_{\mathbf{k}}$ is Lipschitz continuous, that is

(38a)
$\displaystyle\|\nabla_{\mathbf{u}^{(i+1)}}J_{\mathbf{k}}-\nabla_{\mathbf{u}^{(i)}}J_{\mathbf{k}}\|$
$\displaystyle\leq M\|\mathbf{u}^{(i+1)}-\mathbf{u}^{(i)}\|$ (38b)
$\displaystyle\|\nabla_{\mathbf{w}^{(i+1)}}J_{\mathbf{k}}-\nabla_{\mathbf{w}^{(i)}}J_{\mathbf{k}}\|$
$\displaystyle\leq L_{w}\|\mathbf{w}^{(i+1)}-\mathbf{w}^{(i)}\|$
$\displaystyle\forall\mathbf{u}^{(i+1)},\mathbf{u}^{(i)}\in\mathcal{U},$
$\displaystyle\forall\mathbf{w}^{(i+1)},\mathbf{w}^{(i)}\in\mathcal{W}.$

Furthermore, the gradient is bounded with respect to all its arguments.

(39) $\displaystyle\|\nabla_{\mathbf{u}_{0}^{(i)}}J_{\mathbf{k}}\|\leq
G_{\mathbf{x}}$
$\displaystyle,\|\nabla_{\mathbf{u}_{1}^{(i)}}J_{\mathbf{k}}\|\leq
G_{\phi}\|\nabla_{\mathbf{u}_{2}^{(i)}}J_{\mathbf{k}}\|\leq G_{\mathbf{w}}$
$\displaystyle,\|\nabla_{\mathbf{w}^{(i)}}J_{\mathbf{k}}\|\leq G$
$\displaystyle\forall\mathbf{u}^{(i)}\in\mathcal{U},$
$\displaystyle\forall\mathbf{w}^{(i)}\in\mathcal{W}.$

Thus providing the following lemma

######  Lemma 11.1.

Let assumption 11 be true and let the size of $D^{P}_{k}\cup D^{N}_{k}$, be
described by $N$ with the batch size given by $b.$ Assume that a minibatch is
obtained by sampling uniformly from the dataset and define
$H_{\mathbf{k}}(\mathbf{u}^{(i)},\mathbf{w}^{(j)})=[J_{\mathbf{k}}(\mathbf{w}^{(j)})+\beta_{1}J_{\mathbf{k}}(\mathbf{u}_{0}^{(i)},\mathbf{w}^{(j)})+\beta_{2}J_{\mathbf{k}}(\mathbf{u}_{1}^{(i)},\mathbf{w}^{(j)})+\beta_{3}J_{\mathbf{k}}(\mathbf{u}_{2}^{(i)},\mathbf{w}^{(j)})]$
with $\bar{G}=[G_{\phi}+G_{\mathbf{x}}+G_{\mathbf{w}}].$ Then, the following
inequalities are true.

$\displaystyle\|\mathbf{g}^{(i)}_{\mathbf{u}}\|$
$\displaystyle\leq\beta\bar{G}$
$\displaystyle\|\mathbf{g}^{(j)}_{\mathbf{w}}\|$
$\displaystyle\leq\Big{[}(1+3\beta)G\Big{]}$ (40)
$\displaystyle\mathbb{E}\left[\|\mathbf{g}^{(i)}_{\mathbf{u}}\|\right]$
$\displaystyle\leq\beta\frac{b\bar{G}}{N}$
$\displaystyle\mathbb{E}\left[\|\mathbf{g}^{(i)}_{\mathbf{w}}\|\right]$
$\displaystyle\leq\beta\frac{b(1+3\beta)G}{N}$ $\displaystyle
Var(\mathbf{g}^{(i)}_{\mathbf{u}})$
$\displaystyle\leq\frac{2b\beta^{2}\left(N^{2}+b^{2}\right)}{N^{3}}\bar{G}^{2}$
$\displaystyle Var(\mathbf{g}^{(j)}_{\mathbf{w}})$
$\displaystyle\leq\left[\frac{bN^{2}+b^{3}}{N^{3}}\right]\left[G^{2}(1+3\beta)^{2}\right].$

######  Proof 11.2.

We begin by stating the cost function as

(41) $\displaystyle H_{\mathbf{k}}(\mathbf{u}^{(i)},\mathbf{w}^{(j)})$
$\displaystyle=\Big{[}J_{\mathbf{k}}(\mathbf{w}^{(j)})+\beta_{1}J_{\mathbf{k}}(\mathbf{u}_{0}^{(i)},\mathbf{w}^{(j)})$
$\displaystyle+\beta_{2}J_{\mathbf{k}}(\mathbf{u}_{1}^{(i)},\mathbf{w}^{(j)})+\beta_{3}J_{\mathbf{k}}(\mathbf{u}_{2}^{(i)},\mathbf{w}^{(j)})\Big{]}$

Taking derivative with respect to $\mathbf{u}$ both sides provides

(42a) $\displaystyle\mathbf{g}^{(i)}_{\mathbf{u}}$
$\displaystyle=\nabla_{\mathbf{u}^{(i)}}H_{\mathbf{k}}(\mathbf{u}^{(i)},\mathbf{w}^{(j)})$
(42b)
$\displaystyle=\nabla_{\mathbf{u}^{(i)}}\Big{[}J_{\mathbf{k}}(\mathbf{w}^{(j)})+\beta_{1}J_{\mathbf{k}}(\mathbf{u}_{0}^{(i)},\mathbf{w}^{(j)})+\beta_{2}J_{\mathbf{k}}(\mathbf{u}_{1}^{(i)},\mathbf{w}^{(j)})$
$\displaystyle+\beta_{3}J_{\mathbf{k}}(\mathbf{u}_{2}^{(i)},\mathbf{w}^{(j)})\Big{]},$

which leads to

(43a) $\displaystyle\mathbf{g}^{(i)}_{\mathbf{u}}$
$\displaystyle=\nabla_{\mathbf{u}^{(i)}}\Big{[}\beta_{1}J_{\mathbf{k}}(\mathbf{u}_{0}^{(i)},\mathbf{w}^{(j)})+\beta_{2}J_{\mathbf{k}}(\mathbf{u}_{1}^{(i)},\mathbf{w}^{(j)})$
$\displaystyle+\beta_{3}J_{\mathbf{k}}(\mathbf{u}_{2}^{(i)},\mathbf{w}^{(j)})\Big{]}$
(43b)
$\displaystyle=\Big{[}\beta_{1}\nabla_{\mathbf{u}^{(i)}}J_{\mathbf{k}}(\mathbf{u}_{0}^{(i)},\mathbf{w}^{(j)})+\beta_{2}\nabla_{\mathbf{u}^{(i)}}J_{\mathbf{k}}(\mathbf{u}_{1}^{(i)},\mathbf{w}^{(j)})$
$\displaystyle+\beta_{3}\nabla_{\mathbf{u}^{(i)}}J_{\mathbf{k}}(\mathbf{u}_{2}^{(i)},\mathbf{w}^{(j)})\Big{]}$

whence the boundedness assumption on the gradients along with the
$\beta_{1},\beta_{2},\beta_{3}\leq\beta$ provides

(44) $\displaystyle\|\mathbf{g}^{(i)}_{\mathbf{u}}\|$
$\displaystyle\leq\beta\bar{G}$
$\displaystyle\mathbb{E}\left[\|\mathbf{g}^{(i)}_{\mathbf{u}}\|\right]$
$\displaystyle\leq\beta\sum_{b}\frac{1}{N}\bar{G}\leq\beta\frac{b\bar{G}}{N}$

Similarly, we obtain

(45)
$\displaystyle\|\mathbf{g}^{(j)}_{\mathbf{w}}\|\leq\Big{[}(1+3\beta)G\Big{]}$

with

(46) $\displaystyle E\left[\|\mathbf{g}^{(j)}_{\mathbf{w}}\|\right]$
$\displaystyle\leq\sum_{b}\frac{1}{N}\left[(1+3\beta)G\right]$
$\displaystyle\leq\frac{b}{N}\left[(1+3\beta)G\right]$

where $b$ refers to the batch size and $N$ refers to the total number of
samples with $\mathbf{g}^{(j)}_{\mathbf{w}}(j)$ indicating gradient with
respect to the $j^{th}$ datapoint in the batch. The estimators of variance is
provided as

(47) $\displaystyle Var(\mathbf{g}^{(i)}_{\mathbf{u}})$
$\displaystyle=\sum_{b}\frac{1}{N}\|\mathbf{g}^{(i)}_{\mathbf{u}}-\hat{\mathbf{g}}^{(i)}_{\mathbf{u}}\|^{2}$
$\displaystyle\leq\sum_{b}\frac{1}{N}\left[\|\mathbf{g}^{(i)}_{\mathbf{u}}\|^{2}+\|\hat{\mathbf{g}}^{(i)}_{\mathbf{u}}\|^{2}+2\|\mathbf{g}^{(i)}_{\mathbf{u}}\|\|\hat{\mathbf{g}}^{(i)}_{\mathbf{u}}\|\right]$
$\displaystyle\leq\sum_{b}\frac{1}{N}\left[2\|\mathbf{g}^{(i)}_{\mathbf{u}}\|^{2}+2\|\hat{\mathbf{g}}^{(i)}_{\mathbf{u}}\|^{2}\right]$
$\displaystyle\leq\sum_{b}\frac{2}{N}\left[(\beta)^{2}+(\frac{b\beta}{N})^{2}\right]\bar{G}^{2}$
$\displaystyle\leq\sum_{b}\frac{2\beta^{2}}{N}\left(1+\frac{b^{2}}{N^{2}}\right)\bar{G}^{2}$
$\displaystyle\leq\frac{2b\beta^{2}\left(N^{2}+b^{2}\right)}{N^{3}}\bar{G}^{2},$

where the third inequality is obtained by applying the Young’s inequality.
Similarly, we obtain

(48) $\displaystyle Var(\mathbf{g}^{(j)}_{\mathbf{w}})$
$\displaystyle=\sum_{b}\frac{1}{N}\|\mathbf{g}^{(j)}_{\mathbf{w}}-\hat{\mathbf{g}}^{(i)}_{\mathbf{w}}\|^{2}$
$\displaystyle\leq\sum_{b}\frac{1}{N}\|\mathbf{g}^{(j)}_{\mathbf{w}}\|^{2}+\|\hat{\mathbf{g}}^{(i)}_{\mathbf{w}}\|^{2}+2\|\hat{\mathbf{g}}^{(i)}_{\mathbf{w}}\|\|\mathbf{g}^{(j)}_{\mathbf{w}}\|$
$\displaystyle\leq\sum_{b}\frac{1}{N}\left[2\|\mathbf{g}^{(j)}_{\mathbf{w}}\|^{2}+2\|\hat{\mathbf{g}}^{(i)}_{\mathbf{w}}\|^{2}\right]$
$\displaystyle\leq\sum_{b}\frac{1}{N}\left[G^{2}(1+3\beta)^{2}+\frac{b^{2}G^{2}(1+3\beta)^{2}}{N^{2}}\right]$
$\displaystyle\leq\left[\frac{bN^{2}+b^{3}}{N^{3}}\right]\left[G^{2}(1+3\beta)^{2}\right]$

In this work, the goal is to prove that a equillibrium point for the two
player game exists and can be reached. Since, the two player game is
sequential, we seek a local min-max point or Stackleberg equillibrium. The
following definitions are adapted from [12] which provides approximate
conditions for sequential minmax games as

######  Definition 5.

. Let there be two compact sets $\mathcal{U}$ and $\mathcal{W}$ and assume
$\mathcal{H}_{\mathbf{k}}$ to be twice differentiable, then
$(\mathbf{u}^{*},\mathbf{w}^{*})\in\mathcal{U}\times\mathcal{W}$ is said to be
a local minimax point or at Stackleberg equillibrium for
$\mathcal{H}_{\mathbf{k}}$, if the following is true

(49)
$\displaystyle\left\lVert\mathbb{E}[\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{*},\mathbf{w}^{*})-\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{(i)},\mathbf{w}^{*})]\right\rVert$
$\displaystyle\leq\epsilon(\delta_{u}),$
$\displaystyle\left\lVert\mathbb{E}\left[\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{*},\mathbf{w}^{*})-\underset{\mathbf{u}^{(i)}\in\mathcal{\mathbf{U}}}{max}\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{(i)},\mathbf{w}^{(j)})\right]\right\rVert$
$\displaystyle\leq\epsilon(\delta_{w},\delta_{u}).$

for every $(\mathbf{u}^{(i)},\mathbf{w}^{(j)})\in\mathcal{U}\times\mathcal{W}$
such that for any $\delta_{u},\delta_{w}\in\mathbb{R}^{+}$ with
$\mathbb{E}[\|\mathbf{w}^{(j)}-\mathbf{w}^{*}]\|\leq\delta_{w},\quad\mathbb{E}[\|\mathbf{u}^{(i)}-\mathbf{u}^{*}]\|\leq\delta_{u},$
with $\epsilon(\delta_{u},\delta_{w}),\epsilon(\delta_{u})\in\mathbb{R^{+}}.$

In what follows, we will show that a local min-max point (which is equivalent
to the Stackleberg equilibrium in a two-player setting [12]) exists (
definition 5) and that the algorithm converges.

##  12 Proof of Theorem 1, Existence of the minmax point

######  Theorem 12.1 (Existence of an Equilibrium Point).

For each task $k,$ fix $\mathbf{w}^{*}\in\mathcal{W}$ and construct
$\mathcal{M}=\\{\mathbf{\mathcal{U}},\mathbf{w}^{*}\\}.$ Let assumption
Section 11 be true, define a dataset $D_{P}\cup D_{N}$ of size $N>0$ and
sample uniformly a mini-batch of size $b.$ Next, define
$\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{(i)},\mathbf{w}^{(j)})=J_{\mathbf{k}}(\mathbf{w}^{(j)})+\beta_{1}J_{\mathbf{k}}(\mathbf{u}_{0}^{(i)},\mathbf{w}^{(j)})+\beta_{2}J_{\mathbf{k}}(\mathbf{u}_{1}^{(i)},\mathbf{w}^{(j)})+\beta_{3}J_{\mathbf{k}}(\mathbf{u}_{2}^{(i)},\mathbf{w}^{(j)})$
with $\beta_{1},\beta_{2},\beta_{3}\leq\beta>0.$ Let the inequalities from
Lemma 4.1 be true. Under assumption that $\alpha^{(i)}_{u}>0,b>0,\beta>0,N>0,$
then, there conditions in Eq. 49 are satisfied with

(50a) $\displaystyle\epsilon(\delta_{u})$
$\displaystyle=\frac{M+1}{2}\delta_{u}^{2}+\bar{G}^{2}\left(\frac{1}{2}\left(\frac{b\bar{G}}{N}\right)^{2}+\frac{2b\beta^{2}\left(N^{2}+b^{2}\right)}{N^{3}}\right),$
(50b) $\displaystyle\epsilon(\delta_{u},\delta_{w})$
$\displaystyle=(\frac{L+1}{2})\delta_{w}^{2}+G^{2}\left(\frac{\left[(1+3\beta)^{2}\right]}{2}+\left[\frac{bN^{2}+b^{3}}{N^{3}}\right]\left[(1+3\beta)^{2}\right]\right)$
$\displaystyle+\frac{M+1}{2}\delta_{u}^{2}+\bar{G}^{2}\left(\frac{1}{2}\left(\frac{b}{N}\right)^{2}+\frac{2b\beta^{2}\left(N^{2}+b^{2}\right)}{N^{3}}\right).$

Here $\|\mathbf{u}^{(i)}-\mathbf{u}^{*}\|\leq\delta_{u},\forall i$ and
$\|\mathbf{w}^{(j)}-\mathbf{w}^{*}\|\leq\delta_{w},\forall j.$ Furthermore,
there exists a $(\mathbf{u}^{*},\mathbf{w}^{*})\in\mathcal{M}\cup\mathcal{N}$
such that $(\mathbf{u}^{*},\mathbf{w}^{*})$ is a local minimax point or a
Stackleberg equillibrium point according to definition 5

######  Proof 12.2.

The proof of this theorem has two specific inequalities to prove. These
inequilities make up the condition that guarantees Stackleberg equilibrium as
detailed in definition 5. We prove the first inequality, i.e.,
$\mathbb{E}\left[\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{(i)},\mathbf{w}^{*})-\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{*},\mathbf{w}^{*})\right]\leq\epsilon(\delta_{u})$
and determine the bound for $\epsilon(\delta_{u})$ through the next lemma.

######  Lemma 12.3.

For each task $k,$ fix $\mathbf{w}^{*}\in\mathcal{W}$ and construct
$\mathcal{M}=\\{\mathbf{\mathcal{U}},\mathbf{w}^{*}\\}.$ Let assumption
Section 11 be true and sample uniformly a minibatch of size $b$ from the
dataset $D=D_{P}\cup D_{N}$ of size $N$. Define
$\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{(i)},\mathbf{w}^{(j)})=J_{\mathbf{k}}(\mathbf{w}^{(j)})+\beta_{1}J_{\mathbf{k}}(\mathbf{u}_{0}^{(i)},\mathbf{w}^{(j)})+\beta_{2}J_{\mathbf{k}}(\mathbf{u}_{1}^{(i)},\mathbf{w}^{(j)})+\beta_{3}J_{\mathbf{k}}(\mathbf{u}_{2}^{(i)},\mathbf{w}^{(j)})$
with $\beta_{1},\beta_{2},\beta_{3}\leq\beta>0.$ Then,
$\left\lVert\mathbb{E}\left[\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{*},\mathbf{w}^{*})-\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{(i)},\mathbf{w}^{*})\right]\right\rVert\leq\epsilon(\delta_{u})$
with

(51)
$\displaystyle\epsilon(\delta_{u})=\frac{M+1}{2}\delta_{u}^{2}+\bar{G}^{2}\left(\frac{2b\beta^{2}}{N}+\frac{1b^{2}}{2N^{2}}++\frac{2b^{3}\beta^{2}}{N^{3}}\right).$

######  Proof 12.4.

For each task $k,$ fix $\mathbf{w}^{*}\in\mathcal{W}$ and construct
$\mathcal{M}=\\{\mathbf{\mathcal{U}},\mathbf{w}^{*}\\}.$ Therefore, for
$(\mathbf{u}^{(i+1)},\mathbf{w}^{*}),(\mathbf{u}^{(i)},\mathbf{w}^{*})\in\mathcal{M}$
assuming L-smoothness of
$\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{(i)},\mathbf{w}^{*})$ we write

(52a) $\displaystyle\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{*},\mathbf{w}^{*})$
$\displaystyle\leq\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{(i)},\mathbf{w}^{*})+\langle\mathbf{g}^{(i)}_{\mathbf{u}},\mathbf{u}^{*}-\mathbf{u}^{(i)}\rangle$
$\displaystyle+\frac{M}{2}\|\mathbf{u}^{(i)}-\mathbf{u}^{*}\|^{2},$ (52b)
$\displaystyle\leq\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{(i)},\mathbf{w}^{*})+\frac{1}{2}\|\mathbf{g}^{(i)}_{\mathbf{u}}\|^{2}$
$\displaystyle+\frac{M+1}{2}\|\mathbf{u}^{(i)}-\mathbf{u}^{*}\|^{2},\Bigg{|}\text{{By
Young's Inequality}}$

Take conditional expectation that conditioned on $\mathbf{u}^{(i)}$ to obtain

$\displaystyle\mathbb{E}\left[\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{*},\mathbf{w}^{*})|\mathbf{u}^{(i)}\right]$
$\displaystyle\leq\mathbb{E}\left[\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{(i)},\mathbf{w}^{*})|\mathbf{u}^{(i)}\right]$
(53a)
$\displaystyle+\mathbb{E}\left[\frac{1}{2}\|\mathbf{g}^{(i)}_{\mathbf{u}}\|^{2}|\mathbf{u}^{(i)}\right]$
$\displaystyle+\mathbb{E}\left[\frac{M+1}{2}\|\mathbf{u}^{(i)}-\mathbf{u}^{*}\|^{2}|\mathbf{u}^{(i)}\right],$
$\displaystyle\quad\quad\Bigg{|}\text{{$Var(x)=E[x^{2}]-E[x]^{2}$ }}$ (53b)
$\displaystyle\leq\mathbb{E}\left[\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{(i)},\mathbf{w}^{*})|\mathbf{u}^{(i)}\right]+\frac{1}{2}\|\mathbb{E}\left[\mathbf{g}^{(i)}_{\mathbf{u}}|\mathbf{u}^{(i)}\right]\|^{2}$
$\displaystyle+\frac{M+1}{2}\|\mathbf{u}^{(i)}-\mathbf{u}^{*}\|^{2}+Var\left(\mathbf{g}^{(i)}_{\mathbf{u}}|\mathbf{u}^{(i)}\right),$

Integrate out the $\mathbf{u}^{(i)}$ by law of total expectation, substitute
the bounds and rearrange to write

(54)
$\displaystyle\mathbb{E}\left[\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{*},\mathbf{w}^{*})-\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{(i)},\mathbf{w}^{*})\right]$
$\displaystyle\leq\frac{1}{2}\left(\frac{b\bar{G}}{N}\right)^{2}+\frac{M+1}{2}\|\mathbf{u}^{(i)}-\mathbf{u}^{*}\|^{2}$
$\displaystyle+\frac{2b\beta^{2}\left(N^{2}+b^{2}\right)}{N^{3}}\bar{G}^{2}.$

Under the assumption that $\|\mathbf{u}^{(i)}-\mathbf{u}^{*}\|\leq\delta_{u},$
we obtain

(55)
$\displaystyle\left\lVert\mathbb{E}\left[\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{*},\mathbf{w}^{*})-\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{(i)},\mathbf{w}^{*})\right]\right\rVert$
$\displaystyle\leq\epsilon(\delta_{u}),$

with

$\epsilon(\delta_{u})=\frac{M+1}{2}\delta_{u}^{2}+\bar{G}^{2}\left(\frac{2b\beta^{2}}{N}+\frac{1b^{2}}{2N^{2}}++\frac{2b^{3}\beta^{2}}{N^{3}}\right).$

Now, we prove the second inequality which is

$\left\lVert\mathbb{E}\left[\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{*},\mathbf{w}^{*})-\underset{\mathbf{u}^{(i)}\in\mathcal{\mathbf{U}}}{max}\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{(i)},\mathbf{w}^{(j)})\right]\right\rVert\leq\epsilon(\delta_{w},\delta_{u})$

######  Lemma 12.5.

For each task $k,$ fix $\mathbf{w}^{*}\in\mathcal{W}$ and construct
$\mathcal{M}=\\{\mathbf{\mathcal{U}},\mathbf{w}^{*}\\}.$ Let assumption 2 be
true and sample uniformly a minibatch of size $b$ from the dataset $D$ of size
$N$. Define
$\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{(i)},\mathbf{w}^{(j)})=J_{\mathbf{k}}(\mathbf{w}^{(j)})+\beta_{1}J_{\mathbf{k}}(\mathbf{u}_{0}^{(i)},\mathbf{w}^{(j)})+\beta_{2}J_{\mathbf{k}}(\mathbf{u}_{1}^{(i)},\mathbf{w}^{(j)})+\beta_{3}J_{\mathbf{k}}(\mathbf{u}_{2}^{(i)},\mathbf{w}^{(j)})$
with $\beta_{1},\beta_{2},\beta_{3}\leq\beta>0.$ Let the inequalities from
Lemma 4.1 be true. Under assumption that $\alpha^{(i)}_{u}>0,b>0,\beta>0,N>0$
and

(58)
$\displaystyle\underset{\begin{array}[]{c}\mathbf{u}^{(i)}\in\mathcal{U}\\\
\|\mathbf{u}^{(i)}-\mathbf{u}^{*}\|\leq\delta_{u}\forall
i\end{array}}{max}\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{(i)},\mathbf{w}^{(j)})=\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{(\zeta)},\mathbf{w}^{(j)}).$

Then, the second inequality is true with

(59) $\displaystyle\epsilon(\delta_{u},\delta_{w})$
$\displaystyle=(\frac{L+1}{2})\delta_{w}^{2}+(1+3\beta)^{2}G^{2}\left(\frac{1}{2}+\frac{b}{N}+\frac{b^{3}}{N^{3}}\right)+\frac{M+1}{2}\delta_{u}^{2}$
$\displaystyle+\bar{G}^{2}\left(\frac{2b\beta^{2}}{N}+\frac{1b^{2}}{2N^{2}}++\frac{2b^{3}\beta^{2}}{N^{3}}\right).$

######  Proof 12.6.

For each task $k,$ construct
$\mathcal{N}=\\{\mathcal{U},\mathbf{\mathcal{W}}\\}.$ Therefore, for
$(\mathbf{u}^{(\zeta)},\mathbf{w}^{(j)}),$
$(\mathbf{u}^{*},\mathbf{w}^{*})\in\mathcal{N}$ assuming L-smoothness of
$\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{*},\mathbf{w}^{(j)})$ and under the
assumption we write

(60) $\displaystyle\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{*},\mathbf{w}^{*})$
$\displaystyle\leq\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{(\zeta)},\mathbf{w}^{(j)})+\langle\mathbf{g}^{(j)}_{\mathbf{w}},\mathbf{w}^{*}-\mathbf{w}^{(j)}\rangle+\frac{L}{2}\|\mathbf{w}^{(j)}-\mathbf{w}^{*}\|^{2}$
$\displaystyle+\langle\mathbf{g}^{(\zeta)}_{\mathbf{u}},\mathbf{u}^{*}-\mathbf{u}^{(\zeta)}\rangle+\frac{M}{2}\|\mathbf{u}^{(\zeta)}-\mathbf{u}^{*}\|^{2},$
$\displaystyle\leq\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{*},\mathbf{w}^{*})+\frac{1}{2}\|\mathbf{g}^{(i)}_{\mathbf{w}}\|^{2}+\frac{L+1}{2}\|\mathbf{w}^{(i)}-\mathbf{w}^{*}\|^{2}$
$\displaystyle+\frac{1}{2}\|\mathbf{g}^{(\zeta)}_{\mathbf{u}}\|^{2}+\frac{M+1}{2}\|\mathbf{u}^{(\zeta)}-\mathbf{u}^{*}\|^{2},\Bigg{|}\text{{By
Young's Inequality}}$

where the second inequality is achieved through Young’s inequality. Take
conditional expectation that conditioned on $\mathbf{w}^{(j)}$ and
$\mathbf{u}^{(\zeta)}$ to obtain

(61) $\displaystyle\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{*},\mathbf{w}^{*})$
$\displaystyle\leq\mathbb{E}\left[\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{(\zeta)},\mathbf{w}^{(j)})|\mathbf{w}^{(j)},\mathbf{u}^{(\zeta)}\right]+\mathbb{E}\left[\frac{1}{2}\|\mathbf{g}^{(j)}_{\mathbf{w}}\|^{2}|\mathbf{w}^{(j)},\mathbf{u}^{(\zeta)}\right]$
$\displaystyle+\mathbb{E}\left[\frac{L+1}{2}\|\mathbf{w}^{(j)}-\mathbf{w}^{*}\|^{2}|\mathbf{w}^{(j)}\right]+\mathbb{E}\left[\frac{1}{2}\|\mathbf{g}^{(\zeta)}_{\mathbf{u}}\|^{2}|\mathbf{w}^{(j)},\mathbf{u}^{(\zeta)}\right]$
$\displaystyle+\mathbb{E}\left[\frac{M+1}{2}\|\mathbf{u}^{(\zeta)}-\mathbf{u}^{*}\|^{2}|\mathbf{u}^{(\zeta)}\right],$
$\displaystyle\leq\mathbb{E}\left[\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{(\zeta)},\mathbf{w}^{(j)})|\mathbf{w}^{(j)},\mathbf{u}^{(\zeta)}\right]$
$\displaystyle+\frac{1}{2}\|\mathbb{E}\left[\mathbf{g}^{(j)}_{\mathbf{w}}|\mathbf{w}^{(j)},\mathbf{u}^{(\zeta)}\right]\|^{2}$
$\displaystyle+\frac{1}{2}\|\mathbb{E}\left[\mathbf{g}^{(\zeta)}_{\mathbf{u}}|\mathbf{w}^{(j)},\mathbf{u}^{(\zeta)}\right]\|^{2}$
$\displaystyle+\mathbb{E}\left[\frac{L+1}{2}\|\mathbf{w}^{(j)}-\mathbf{w}^{*}\|^{2}|\mathbf{w}^{(j)}\right]$
$\displaystyle+\mathbb{E}\left[\frac{M+1}{2}\|\mathbf{u}^{(\zeta)}-\mathbf{u}^{*}\|^{2}|\mathbf{u}^{(\zeta)}\right]$
$\displaystyle+Var\left(\mathbf{g}^{(j)}_{\mathbf{w}}|\mathbf{w}^{(j)},\mathbf{u}^{(\zeta)}\right)$
$\displaystyle+Var\left(\mathbf{g}^{(\zeta)}_{\mathbf{u}}|\mathbf{w}^{(j)},\mathbf{u}^{(\zeta)}\right)\quad\Bigg{|}\text{
Since {$Var(x)=E[x^{2}]-E[x]^{2}$ }}$

Integrate out the $\mathbf{w}^{(j)}$ and $\mathbf{u}^{(\zeta)}$ to get by law
of total expectation,

(62)
$\displaystyle\mathbb{E}\left[\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{*},\mathbf{w}^{*})\right]-\mathbb{E}\left[\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{(\zeta)},\mathbf{w}^{(j)})\right]$
$\displaystyle\leq\frac{1}{2}\|\mathbb{E}\left[\mathbf{g}^{(j)}_{\mathbf{w}}\right]\|^{2}$
$\displaystyle+\frac{1}{2}\|\mathbb{E}\left[\mathbf{g}^{(\zeta)}_{\mathbf{u}}\right]\|^{2}$
$\displaystyle+\mathbb{E}\left[\frac{L+1}{2}\|\mathbf{w}^{(j)}-\mathbf{w}^{*}\|^{2}\right]$
$\displaystyle+\mathbb{E}\left[\frac{M+1}{2}\|\mathbf{u}^{(\zeta)}-\mathbf{u}^{*}\|^{2}\right]$
$\displaystyle+Var\left(\mathbf{g}^{(j)}_{\mathbf{w}}\right)+Var\left(\mathbf{g}^{(\zeta)}_{\mathbf{u}}\right)$

Since,
$\mathbb{E}\left[\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{(\zeta)},\mathbf{w}^{(j)})\right]=\underset{\begin{array}[]{c}\mathbf{u}^{(i)}\in\mathcal{U}\\\
\|\mathbf{u}^{(i)}-\mathbf{u}^{*}\|\leq\delta_{u}\end{array}}{max}\mathbb{E}\left[\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{(i)},\mathbf{w}^{(j)})\right].$
We obtain by substituting the bounds.

(63)
$\displaystyle\mathbb{E}\left[\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{*},\mathbf{w}^{*})\right]-\underset{\begin{array}[]{c}\mathbf{u}^{(i)}\in\mathcal{U}\\\
\|\mathbf{u}^{(i)}-\mathbf{u}^{*}\|\leq\delta_{u}\end{array}}{max}\mathbb{E}\left[\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{(i)},\mathbf{w}^{(j)})\right]$
$\displaystyle\leq(\frac{L+1}{2})\delta_{w}^{2}+G^{2}\left(\frac{\left[(1+3\beta)^{2}\right]}{2}+\left[\frac{bN^{2}+b^{3}}{N^{3}}\right]\left[(1+3\beta)^{2}\right]\right)$
$\displaystyle\frac{M+1}{2}\delta_{u}^{2}+\bar{G}^{2}\left(\frac{1}{2}\left(\frac{b}{N}\right)^{2}+\frac{2b\beta^{2}\left(N^{2}+b^{2}\right)}{N^{3}}\right)$

which leads into

(64)
$\displaystyle\left\lVert\mathbb{E}\left[\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{*},\mathbf{w}^{*})-\underset{\begin{array}[]{c}\mathbf{u}^{(i)}\in\mathcal{U}\\\
\|\mathbf{u}^{(i)}-\mathbf{u}^{*}\|\leq\delta_{u}\end{array}}{max}\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{(i)},\mathbf{w}^{(j)})\right]\right\rVert\leq\epsilon(\delta_{w},\delta_{u})$

with

$\displaystyle\epsilon(\delta_{u},\delta_{w})$
$\displaystyle=(\frac{L+1}{2})\delta_{w}^{2}+(1+3\beta)^{2}G^{2}\left(\frac{1}{2}+\frac{b}{N}+\frac{b^{3}}{N^{3}}\right)$
(65)
$\displaystyle+\frac{M+1}{2}\delta_{u}^{2}+\bar{G}^{2}\left(\frac{2b\beta^{2}}{N}+\frac{1b^{2}}{2N^{2}}++\frac{2b^{3}\beta^{2}}{N^{3}}\right).$

We have pulled the expected value outside the maximum under the assumption
that the function is smooth.

By the two inequalities proved in the preceeding lemmas, we obtain for
$(\mathbf{u}^{*},\mathbf{w}^{*})\in\mathcal{M}\cup\mathcal{N}.$

(66)
$\displaystyle\left\lVert\mathbb{E}\left[\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{*},\mathbf{w}^{*})-\underset{\begin{array}[]{c}\mathbf{u}^{(i)}\in\mathcal{U}\\\
\|\mathbf{u}^{(i)}-\mathbf{u}^{*}\|\leq\delta_{u}\end{array}}{max}\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{(i)},\mathbf{w}^{(j)})\right]\right\rVert$
$\displaystyle\leq\epsilon(\delta_{w},\delta_{u})$
$\displaystyle\left\lVert\mathbb{E}\left[\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{*},\mathbf{w}^{*})-\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{(i)},\mathbf{w}^{*})\right]\right\rVert$
$\displaystyle\leq\epsilon(\delta_{u}),$

Then, $(\mathbf{u}^{*},\mathbf{w}^{*})$ is a local minimax point according to
definition 5. Thus, we conclude the proof of Theorem 1.

##  13 Proof of Theorem 2, Convergence to the equilibrium point

The proof of this theorem requires us to first prove that the maximizing
player converges. Next, we show that, provided the maximizing player provides
a strategy, the minimizing player converges. In our algorithm, we perform
$\zeta$ gradient ascent updates for each $\mathbf{w}^{(j)}.$ Therefore, we
will first show that the with many gradient ascent steps, our gradient goes to
zero.

######  Theorem 13.1 (Gradient of $\mathcal{H}_{\mathbf{k}}$ with respect to
$\mathbf{u}^{(i)}$ converges to zero).

For each task $k,$ fix $\mathbf{w}^{(j)}\in\mathcal{W}$ and construct
$\mathcal{M}=\\{\mathbf{w}^{(j)},\mathbf{\mathcal{U}}\\}.$ Let assumption 2 be
true and sample uniformly a minibatch of size $b$ from the dataset $D$ of size
$N$. Define
$\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{(i)},\mathbf{w}^{(j)})=J_{\mathbf{k}}(\mathbf{w}^{(j)})+\beta_{1}J_{\mathbf{k}}(\mathbf{u}_{0}^{(i)},\mathbf{w}^{(j)})+\beta_{2}J_{\mathbf{k}}(\mathbf{u}_{1}^{(i)},\mathbf{w}^{(j)})+\beta_{3}J_{\mathbf{k}}(\mathbf{u}_{2}^{(i)},\mathbf{w}^{(j)})$
with $\beta_{1},\beta_{2},\beta_{3}\leq\beta>0.$ Let the inequalities from
Lemma 4.1 be true. Choose $\alpha^{(i)}_{u}=\frac{\alpha_{u}}{\sqrt{\zeta}},$
then
$\sum_{i}\alpha^{(i)}_{u}=\sum_{i}\frac{\alpha_{u}}{\sqrt{\zeta}}=\alpha_{u}\sqrt{\zeta}.$
Similarly, $\sum_{i}(\alpha^{(i)}_{u})^{2}=\alpha^{2}_{u}$ such that
$\sum_{i}(\alpha^{(i)}_{u}-\frac{M(\alpha^{(i)}_{u})^{2}}{2})=\frac{2\alpha_{u}\sqrt{\zeta}-M\alpha^{2}_{u}}{2}=S_{n}$.
Now, denote
$\Delta_{(i)}=\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{(i+1)},\mathbf{w}^{(j)})-\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{*},\mathbf{w}^{(j)}),$
then the following is true

$\underset{i=0,\cdots,\zeta}{min}E\left[\|\mathbf{g}^{(i)}_{\mathbf{u}}\|^{2}\right]\leq\frac{2\mathbb{E}[\|\mathbf{u}^{(\zeta)}-\mathbf{u}^{*}\|]}{2\alpha_{u}\sqrt{\zeta}-M\alpha^{2}_{u}}+\frac{2M(\alpha_{u})^{2}b\beta^{2}\bar{G}^{2})}{N\left(2\alpha_{u}\sqrt{\zeta}-M\alpha^{2}_{u}\right)}+\frac{2M(\alpha_{u})^{2}(b^{3}\beta^{2}\bar{G}^{2})}{N^{3}\left(2\alpha_{u}\sqrt{\zeta}-M\alpha^{2}_{u}\right)}..$

Provided $M\alpha^{2}_{u}<<\alpha_{u}\sqrt{\zeta}$, we have
$\lim_{\zeta\rightarrow\infty}\underset{i=0,\cdots,\zeta}{min}E\left[\|\mathbf{g}^{(i)}_{\mathbf{u}}\|^{2}\right]\rightarrow
0$ with the rate $\frac{1}{\sqrt{\zeta}}.$

######  Proof 13.2.

For each task $k,$ fix $\mathbf{w}^{(j)}\in\mathcal{W}$ and construct
$\mathcal{M}=\\{\mathbf{w}^{(j)},\mathbf{\mathcal{U}}\\}.$ Therefore, for
$(\mathbf{u}^{(i+1)},\mathbf{w}^{(j)}),(\mathbf{u}^{(i)},\mathbf{w}^{(j)})\in\mathcal{M}$
assuming L-smoothness of
$\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{(i)},\mathbf{w}^{(j)})$ we write

(67)
$\displaystyle\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{(i+1)},\mathbf{w}^{(j)})\geq\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{(i)},\mathbf{w}^{(j)})+\langle\mathbf{g}^{(i)}_{\mathbf{u}},\mathbf{u}^{(i+1)}-\mathbf{u}^{(i)}\rangle-\frac{M}{2}\|\mathbf{u}^{(i+1)}-\mathbf{u}^{(i)}\|^{2},$

where we get upon substitution of the update rule
$\alpha^{(i)}_{u}\mathbf{\hat{g}}^{(i)}_{\mathbf{u}}$

(68)
$\displaystyle\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{(i+1)},\mathbf{w}^{(j)})$
$\displaystyle\geq\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{(i)},\mathbf{w}^{(j)})+\alpha^{(i)}_{u}\langle\mathbf{g}^{(i)}_{\mathbf{u}},\mathbf{\hat{g}}^{(i)}_{\mathbf{u}}\rangle-\frac{M(\alpha^{(i)}_{u})^{2}}{2}\|\mathbf{\hat{g}}^{(i)}_{\mathbf{u}}\|^{2}.$

Take conditional expectation that is conditioned on $\mathbf{u}^{(i)}$

(69)
$\displaystyle\mathbb{E}[\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{(i+1)},\mathbf{w}^{(j)})|\mathbf{u}^{(i)}]$
$\displaystyle\geq\mathbb{E}[\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{(i)},\mathbf{w}^{(j)})|\mathbf{u}^{(i)}]$
$\displaystyle+\alpha^{(i)}_{u}\langle\mathbf{g}^{(i)}_{\mathbf{u}},\mathbb{E}[\mathbf{\hat{g}}^{(i)}_{\mathbf{u}}|\mathbf{u}^{(i)}]\rangle$
$\displaystyle-\frac{M(\alpha^{(i)}_{u})^{2}}{2}\mathbb{E}[\|\mathbf{\hat{g}}^{(i)}_{\mathbf{u}}\|^{2}|\mathbf{u}^{(i)}],$
$\displaystyle\Bigg{|}\text{ Since {$Var(x)=E[x^{2}]-E[x]^{2}$ }}$
$\displaystyle\geq\mathbb{E}[\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{(i)},\mathbf{w}^{(j)})|\mathbf{u}^{(i)}]$
$\displaystyle+\alpha^{(i)}_{u}\langle\mathbf{g}^{(i)}_{\mathbf{u}},\mathbb{E}[\mathbf{\hat{g}}^{(i)}_{\mathbf{u}}|\mathbf{u}^{(i)}]\rangle$
$\displaystyle-\frac{M(\alpha^{(i)}_{u})^{2}}{2}(\|\mathbb{E}[\mathbf{\hat{g}}^{(i)}_{\mathbf{u}}|\mathbf{u}^{(i)}]\|^{2}+Var(\mathbf{g}^{(i)}_{\mathbf{u}}))$

Assume
$\mathbb{E}[\mathbf{\hat{g}}^{(i)}_{\mathbf{u}}|\mathbf{u}^{(i)}]=\mathbf{g}^{(i)}_{\mathbf{u}}$
[26] to write

(70)
$\displaystyle\mathbb{E}[\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{(i+1)},\mathbf{w}^{(j)})|\mathbf{u}^{(i)}]$
$\displaystyle\geq\mathbb{E}[\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{(i)},\mathbf{w}^{(j)})|\mathbf{u}^{(i)}]+\alpha^{(i)}_{u}\|\mathbf{g}^{(i)}_{\mathbf{u}}\|^{2}$
$\displaystyle-\frac{M(\alpha^{(i)}_{u})^{2}}{2}\|\mathbf{g}^{(i)}_{\mathbf{u}}\|^{2}$
$\displaystyle-\frac{M(\alpha^{(i)}_{u})^{2}}{2}(Var(\mathbf{g}^{(i)}_{\mathbf{u}}))$
$\displaystyle\geq\mathbb{E}[\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{(i)},\mathbf{w}^{(j)})|\mathbf{u}^{(i)}]$
$\displaystyle+\alpha^{(i)}_{u}(1-\frac{M\alpha^{(i)}_{u}}{2})\|\mathbf{g}^{(i)}_{\mathbf{u}}\|^{2}$
$\displaystyle-\frac{M(\alpha^{(i)}_{u})^{2}}{2}(Var(\mathbf{g}^{(i)}_{\mathbf{u}})).$

Take expectation over all possible values of $\mathbf{u}^{(i)}$ and applying
Law of total expectation provides and substitute the bounds from Lemma 4.1 to
obtain

(71)
$\displaystyle\mathbb{E}[\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{(i+1)},\mathbf{w}^{(j)})]$
$\displaystyle\geq\mathbb{E}[\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{(i)},\mathbf{w}^{(j)})]$
$\displaystyle+\alpha^{(i)}_{u}(1-\frac{M\alpha^{(i)}_{u}}{2})\|\mathbf{g}^{(i)}_{\mathbf{u}}\|^{2}$
$\displaystyle-\frac{M(\alpha^{(i)}_{u})^{2}}{2}(Var(\mathbf{g}^{(i)}_{\mathbf{u}})),$
$\displaystyle\geq\mathbb{E}[\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{(i)},\mathbf{w}^{(j)})]$
$\displaystyle+\alpha^{(i)}_{u}(1-\frac{M\alpha^{(i)}_{u}}{2})E\left[\|\mathbf{g}^{(i)}_{\mathbf{u}}\|^{2}\right]$
$\displaystyle-\frac{M(\alpha^{(i)}_{u})^{2}}{2}(Var(\mathbf{g}^{(i)}_{\mathbf{u}})).$

Add and subtract $\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{*},\mathbf{w}^{(j)})$
from both sides to obtain

(72)
$\displaystyle\mathbb{E}[\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{(i+1)},\mathbf{w}^{(j)})-\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{*},\mathbf{w}^{(j)})]$
$\displaystyle\geq\mathbb{E}[\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{(i)},\mathbf{w}^{(j)})-\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{*},\mathbf{w}^{(j)})]$
$\displaystyle+\alpha^{(i)}_{u}(1+\frac{M\alpha^{(i)}_{u}}{2})E\left[\|\mathbf{g}^{(i)}_{\mathbf{u}}\|^{2}\right]$
$\displaystyle+\frac{M(\alpha^{(i)}_{u})^{2}}{2}(Var(\mathbf{g}^{(i)}_{\mathbf{u}})),$
$\displaystyle\Bigg{|}\text{ Denote
$\Delta_{(i)}=\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{(i+1)},\mathbf{w}^{(j)})-\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{*},\mathbf{w}^{(j)})$}$
$\displaystyle\mathbb{E}[\Delta^{i+1}]$
$\displaystyle\geq\mathbb{E}[\Delta^{i}]$
$\displaystyle+\alpha^{(i)}_{u}(1-\frac{M\alpha^{(i)}_{u}}{2})E\left[\|\mathbf{g}^{(i)}_{\mathbf{u}}\|^{2}\right]$
$\displaystyle-\frac{M(\alpha^{(i)}_{u})^{2}}{2}(Var(\mathbf{g}^{(i)}_{\mathbf{u}})).$

Thus, we obtain

(73)
$\displaystyle-\alpha^{(i)}_{u}(1-\frac{M\alpha^{(i)}_{u}}{2})E\left[\|\mathbf{g}^{(i)}_{\mathbf{u}}\|^{2}\right]$
$\displaystyle\geq\mathbb{E}[\Delta^{i}]-\mathbb{E}[\Delta^{i+1}]-\frac{M(\alpha^{(i)}_{u})^{2}}{2}(Var(\mathbf{g}^{(i)}_{\mathbf{u}})).$
$\displaystyle\alpha^{(i)}_{u}(1-\frac{M\alpha^{(i)}_{u}}{2})E\left[\|\mathbf{g}^{(i)}_{\mathbf{u}}\|^{2}\right]$
$\displaystyle\leq\mathbb{E}[\Delta^{i+1}]-\mathbb{E}[\Delta^{i}]+\frac{M(\alpha^{(i)}_{u})^{2}}{2}(Var(\mathbf{g}^{(i)}_{\mathbf{u}})).$

Since, we take $\zeta$ updates, let us sum both sides for $\zeta$ updates

(74)
$\displaystyle\sum_{i}\alpha^{(i)}_{u}(1-\frac{M\alpha^{(i)}_{u}}{2})E\left[\|\mathbf{g}^{(i)}_{\mathbf{u}}\|^{2}\right]$
$\displaystyle\leq\underset{\text{Telescopic
sum}}{\underbrace{\sum_{i}\left(\mathbb{E}[\Delta^{i+1}]-\mathbb{E}[\Delta^{i}]\right)}}$
$\displaystyle+\sum_{i}\frac{M(\alpha^{(i)}_{u})^{2}}{2}(\frac{2b\beta^{2}\left(N^{2}+b^{2}\right)}{N^{3}}\bar{G}^{2}),$
$\displaystyle\sum_{i}\alpha^{(i)}_{u}(1-\frac{M\alpha^{(i)}_{u}}{2})E\left[\|\mathbf{g}^{(i)}_{\mathbf{u}}\|^{2}\right]$
$\displaystyle\leq\mathbb{E}[\Delta^{\zeta}]-\mathbb{E}[\Delta^{0}]$
$\displaystyle+\sum_{i}\frac{M(\alpha^{(i)}_{u})^{2}}{2}(\frac{2b\beta^{2}\left(N^{2}+b^{2}\right)}{N^{3}}\bar{G}^{2}).$

Now choose, $\alpha^{(i)}_{u}=\frac{\alpha_{u}}{\sqrt{\zeta}},$ then
$\sum_{i}\alpha^{(i)}_{u}=\sum_{i}\frac{\alpha_{u}}{\sqrt{\zeta}}=\alpha_{u}\sqrt{\zeta}.$
Similarly, $\sum_{i}(\alpha^{(i)}_{u})^{2}=\alpha^{2}_{u}.$ Therefore, we
obtain

$\sum_{i}(\alpha^{(i)}_{u}-\frac{M(\alpha^{(i)}_{u})^{2}}{2})=\frac{2\alpha_{u}\sqrt{\zeta}-M\alpha^{2}_{u}}{2}=S_{n}.$

Use the idea that for a set of random variables $x_{1},\cdots,x_{m},$ we have
$\underset{i=0,\cdots,m}{min}\mathbb{E}[x]\leq\mathbb{E}[\underset{i=0,\cdots,m}{min}x]$
and the fact that the minimum value of $\mathbb{E}[\Delta^{0}]$ is zero.

(75)
$\displaystyle\sum_{i}(\alpha^{(i)}_{u}-\frac{M(\alpha^{(i)}_{u})^{2}}{2})\underset{i=0,\cdots,\zeta}{min}E\left[\|\mathbf{g}^{(i)}_{\mathbf{u}}\|^{2}\right]$
$\displaystyle\leq\mathbb{E}[\Delta^{K}]-\mathbb{E}[\Delta^{0}]$
$\displaystyle+\sum_{i}\frac{M(\alpha^{(i)}_{u})^{2}}{2}(\frac{2b\beta^{2}\left(N^{2}+b^{2}\right)}{N^{3}}\bar{G}^{2}).$
$\displaystyle\underset{i=0,\cdots,\zeta}{min}E\left[\|\mathbf{g}^{(i)}_{\mathbf{u}}\|^{2}\right]$
$\displaystyle\leq\frac{\mathbb{E}[\Delta^{K}]}{S_{n}}+\frac{M(\alpha_{u})^{2}}{2S_{n}}(\frac{2b\beta^{2}\left(N^{2}+b^{2}\right)}{N^{3}}\bar{G}^{2}).$

Thus providing the upperbound on the minimum value of the gradients over all
the update steps as

(76)
$\displaystyle\underset{i=0,\cdots,\zeta}{min}E\left[\|\mathbf{g}^{(i)}_{\mathbf{u}}\|^{2}\right]$
$\displaystyle\leq\frac{\mathbb{E}[\Delta^{K}]}{\left(\frac{2\alpha_{u}\sqrt{\zeta}-M\alpha^{2}_{u}}{2}\right)}+\frac{2M(\alpha_{u})^{2}b\beta^{2}\bar{G}^{2})}{2N\left(\frac{2\alpha_{u}\sqrt{\zeta}-M\alpha^{2}_{u}}{2}\right)}+\frac{2M(\alpha_{u})^{2}(b^{3}\beta^{2}\bar{G}^{2})}{2N^{3}\left(\frac{2\alpha_{u}\sqrt{\zeta}-M\alpha^{2}_{u}}{2}\right)}.$

As a consequence of lemma 4.1, we may write

(77)
$\displaystyle\underset{i=0,\cdots,\zeta}{min}E\left[\|\mathbf{g}^{(i)}_{\mathbf{u}}\|^{2}\right]$
$\displaystyle\leq\frac{2\mathbb{E}[\|\mathbf{u}^{(\zeta)}-\mathbf{u}^{*}\|]}{2\alpha_{u}\sqrt{\zeta}-M\alpha^{2}_{u}}+\frac{2M(\alpha_{u})^{2}b\beta^{2}\bar{G}^{2})}{N\left(2\alpha_{u}\sqrt{\zeta}-M\alpha^{2}_{u}\right)}+\frac{2M(\alpha_{u})^{2}(b^{3}\beta^{2}\bar{G}^{2})}{N^{3}\left(2\alpha_{u}\sqrt{\zeta}-M\alpha^{2}_{u}\right)}.$

Under the assumption that
$\|\mathbf{u}^{(\zeta)}-\mathbf{u}^{*}\|\leq\delta_{u}$ we obtain our result
as

(78)
$\displaystyle\underset{i=0,\cdots,\zeta}{min}E\left[\|\mathbf{g}^{(i)}_{\mathbf{u}}\|^{2}\right]$
$\displaystyle\leq\frac{2\mathbb{E}[\delta_{u}]}{2\alpha_{u}\sqrt{\zeta}-M\alpha^{2}_{u}}+\frac{4M(\alpha_{u})^{2}b\beta^{2}\bar{G}^{2})}{N\left(2\alpha_{u}\sqrt{\zeta}-M\alpha^{2}_{u}\right)}$
$\displaystyle+\frac{4M(\alpha_{u})^{2}(b^{3}\beta^{2}\bar{G}^{2})}{N^{3}\left(2\alpha_{u}\sqrt{\zeta}-M\alpha^{2}_{u}\right)}.$

Provided $\alpha^{2}_{u}<<\alpha_{u}\sqrt{\zeta}$,
$\underset{i=0,\cdots,\zeta}{min}E\left[\|\mathbf{g}^{(i)}_{\mathbf{u}}\|^{2}\right]$
we have
$\lim_{\zeta\rightarrow\infty}\mathbb{E}[\|\mathbf{g}^{(i)}_{\mathbf{u}}\|^{2}]\rightarrow
0.$ with the rate $\frac{1}{\sqrt{\zeta}}$

With the result that the gradient will converge to zero for the maximizing
player, we are now ready to show the convergence of our algoritheorem in the
sense of gradients. Thus, providing the result to our main theorem in the
paper–Theorem 2. For the following result, we will assume that, for each $j$
the maximizing player has already played and provides with a
$\mathbf{u}^{(\zeta)}.$

######  Theorem 13.3 (Convergence in gradients).

For each task $k,$ construct
$\mathcal{N}=\\{\mathbf{\mathcal{U}},\mathbf{\mathcal{W}}\\}.$ Let assumption
2 be true and define a dataset $D$ of size $N>0.$ Assume that a minibatch of
size $b$ is obtained by uniformly sampling from $D$ and define
$\mathcal{H}_{\mathbf{k}}(\mathbf{u}^{(i)},\mathbf{w}^{(j)})=J_{\mathbf{k}}(\mathbf{w}^{(j)})+\beta_{1}J_{\mathbf{k}}(\mathbf{u}_{0}^{(i)},\mathbf{w}^{(j)})+\beta_{2}J_{\mathbf{k}}(\mathbf{u}_{1}^{(i)},\mathbf{w}^{(j)})+\beta_{3}J_{\mathbf{k}}(\mathbf{u}_{2}^{(i)},\mathbf{w}^{(j)})$
with $\beta_{1},\beta_{2},\beta_{3}\leq\beta>0$ Consider the updates for
$\mathbf{u}^{(i)}$ as $\alpha^{(i)}_{u}\mathbf{\hat{g}}^{(i)}_{\mathbf{u}}$
and the updates for updates for $\mathbf{w}^{(j)}$ as
$\alpha^{(j)}_{w}\mathbf{\hat{g}}^{(i)}_{\mathbf{w}}$ and let the inequalities
from Lemma 4.1 provides the bounds on the variance and expected values of
these gradients. By theorem 13.1, we obtain that the maximizing player
$\mathbf{u}^{(i)}$ converges to $\mathbf{u}^{(\zeta)}$ Furthermore, assume
that
$\alpha^{(i)}_{u}>0,b>0,\beta>0,N>0,\left\lVert\mathbf{u}^{(\zeta)}-\mathbf{u}^{*}\right\rVert^{2}\leq\delta_{w}^{2},$
and that
$\underset{j=1,2,3,\cdots\rho}{max}Var(\mathbf{g}^{(j)}_{\mathbf{w}})$ and
$\underset{j=1,2,3,\cdots\rho}{max}Var(\mathbf{g}^{(j)}_{\mathbf{w}})$ are
upper bounded by the bound provided by lemma 4.1. Furthermore, choose,
$\alpha^{(i)}_{w}=\frac{\alpha_{w}}{\sqrt{\rho}},$ then
$\sum_{i}(\alpha^{(i)}_{w}=\sum_{i}\frac{\alpha_{w}}{\sqrt{\rho}}=\alpha_{w}\sqrt{\rho}.$
Similarly, $\sum_{i}(\alpha^{(i)}_{w})^{2}=\alpha^{2}_{w}.$ Then the minimum
value of the gradient is bounded as

(79)
$\displaystyle\underset{j=1,2,3,\cdots\rho}{min}\mathbb{E}\left[\|\mathbf{g}^{(j)}_{\mathbf{w}}\|^{2}\right]$
$\displaystyle\leq\frac{2\rho\mathbb{E}\left[\delta_{u}^{2}\right](M+1)+2(1+3\beta)G\delta_{w}2}{2\alpha_{w}\sqrt{\rho}-L_{w}\alpha^{2}_{w}}+\frac{L_{w}(\alpha_{\mathbf{w}})^{2}b}{N(2\alpha_{w}\sqrt{\rho}-L_{w}\alpha^{2}_{w})}$
$\displaystyle+\frac{\beta\rho