# DIAMOND: Taming Sample and Communication Complexities in Decentralized
Bilevel Optimization

Peiwen Qiu1 Yining Li1 Zhuqing Liu1 Prashant Khanduri2 Jia Liu1
Ness B. Shroff1 Elizabeth Serena Bentley3 Kurt Turck3
1Dept. of ECE, The Ohio State University 2Dept. of CS, Wayne State University
3Air Force Research Laboratory, Information Directorate  This work has been
supported in part by NSF grants CAREER CNS-2110259, CNS-2112471, CNS-2102233,
CCF-2110252, and AFRL grant FA8750-20-3-1003. The views and conclusions
contained herein are those of the authors and should not be interpreted as
necessarily representing the official policies or endorsements, either
expressed or implied, of the Air Force Research Laboratory or the U.S.
Government. Distribution A. Approved for public release: Distribution
unlimited AFRL-2023-0273 on 18 Jan 2023.

###### Abstract

Decentralized bilevel optimization has received increasing attention recently
due to its foundational role in many emerging multi-agent learning paradigms
(e.g., multi-agent meta-learning and multi-agent reinforcement learning) over
peer-to-peer edge networks. However, to work with the limited computation and
communication capabilities of edge networks, a major challenge in developing
decentralized bilevel optimization techniques is to lower sample and
communication complexities. This motivates us to develop a new decentralized
bilevel optimization called $\mathsf{DIAMOND}~{}$(decentralized single-
timescale stochastic approximation with momentum and gradient-tracking). The
contributions of this paper are as follows: i) our
$\mathsf{DIAMOND}~{}$algorithm adopts a single-loop structure rather than
following the natural double-loop structure of bilevel optimization, which
offers low computation and implementation complexity; ii) compared to existing
approaches, the $\mathsf{DIAMOND}~{}$algorithm does not require any full
gradient evaluations, which further reduces both sample and computational
complexities; iii) through a careful integration of momentum information and
gradient tracking techniques, we show that the $\mathsf{DIAMOND}~{}$algorithm
enjoys $\mathcal{O}(\epsilon^{-3/2})$ in sample and communication complexities
for achieving an $\epsilon$-stationary solution, both of which are independent
of the dataset sizes and significantly outperform existing works. Extensive
experiments also verify our theoretical findings.

##  I Introduction

In recent years, the problem of performing decentralized bilevel optimization
over networks has attracted increasing attention. For a peer-to-peer
communication network represented by a graph $\mathcal{G}=(\mathcal{N,L})$,
where $\mathcal{N}$ and $\mathcal{L}$ denote the sets of agents and edges with
$|\mathcal{N}|=m$, a decentralized bilevel optimization problem can be
generally written as follows:

$\displaystyle\min_{\mathbf{x}\in\mathbb{R}^{d_{\mathrm{up}}}}l\left(\mathbf{x}\right)=\frac{1}{m}\sum_{i=1}^{m}\left\\{l_{i}\left(\mathbf{x}\right)\triangleq\mathbb{E}_{\xi_{i}}\left[f_{i}\left(\mathbf{x},\mathbf{y}_{i}^{*}\left(\mathbf{x}\right);\xi_{i}\right)\right]\right\\}\text{,}$
$\displaystyle\text{s.t.
}\mathbf{y}_{i}^{*}\left(\mathbf{x}\right)=\arg\\!\\!\\!\\!\min_{\\!\\!\\!\\!\\!\\!\\!\mathbf{y}_{i}\in\mathbb{R}^{d_{\mathrm{low}}}}\\!\\!\left\\{g_{i}\left(\mathbf{x},\mathbf{y}_{i}\right)\triangleq\mathbb{E}_{\zeta_{i}}\left[g_{i}\left(\mathbf{x}_{i},\mathbf{y}_{i};\zeta_{i}\right)\right]\right\\},\\!\\!\\!$
(1)

where $l_{i}\left(\mathbf{x}\right)$ is the local objective function at agent
$i$, $\mathbf{x}\in\mathbb{R}^{d_{\mathrm{up}}}$ and
$\mathbf{y}_{i}\in\mathbb{R}^{d_{\mathrm{low}}}$ are the global upper-level
variables and the local lower-level variables at agent
$i\in\left\\{1,\ldots,m\right\\}$, and $\xi_{i}$ and $\zeta_{i}$ represent the
random samples of the upper-level and the lower-level subproblems,
respectively.

Problem (I) plays a foundational role for various fundamental multi-agent
learning paradigms over decentralized or multi-hop wireless edge networks. For
instance, in the well-known actor-critic framework for cooperative multi-agent
reinforcement learning (MARL, e.g., [1, 2]), the shared global policy
improvement (the actor component) corresponds to the upper-level subproblem in
Problem (I), which depends on the optimal solution of a policy evaluation
subproblem ( the critic component), which corresponds to the lower-level
subproblem in Problem (I). Another example can be found in multi-agent meta-
learning (also referred to as “learning-to-learn”, see, e.g., [3, 4]), where
the training of task-specific parameters at each agent can be represented by
the lower-level subproblem in Problem (I). The task-specific parameter
training is coupled with the shared parameters’ optimization, which
corresponds to the upper-level subproblem in Problem (I).

It is evident from Problem (I) that the most prominent features of
decentralized bilevel optimization are i) “bilevel” and ii)
“decentralization.” Same as the single-agent bilevel counterpart[5], Problem
(I) has a hierarchical structure, where the upper-level subproblem objective
value is determined by both the upper-level variable $\mathbf{x}$ and the
optimal variables $\\{\mathbf{y}_{i}^{*}(\mathbf{x})\\}_{i=1}^{m}$ obtained by
solving the lower-level subproblems. Due to this bilevel structure, the
solution approach for Problem (I) is fundamentally different from the
traditional loss minimization in conventional learning problems with a single-
level structure. Thus, new algorithm design and analysis techniques are
necessary for solving Problem (I). Moreover, instead of only having a single
task as in single-agent bilevel optimization problems, one needs to cope with
multiple lower-level tasks in a decentralized fashion in Problem (I). This key
difference necessitates new algorithm designs. Thus, solving decentralized
bilevel optimization problems over wireless networks needs to address the
following technical challenges:

  * •

Single-Loop or Double-Loop Architecture? In Problem (I), it is often
impractical to asymptotically solve the lower-level problem to optimality.
Rather, one typically resorts to using an approximaion of
$\mathbf{y}^{*}(\mathbf{x})$, which is obtained by solving the lower-level
problems with finite iterations[6, 7, 8, 9, 10, 1, 11]. However, due to the
coordination complexity among agents and training accuracy concerns, the
algorithmic architecture choice between “double-loop” [6, 7, 8] or “single-
loop” [9, 10, 1, 11], both of which are widely used in single-agent bilevel
optimization, suddenly becomes critical. On one hand, the double-loop
architecture naturally follows the bilevel problem structure and executes
multiple inner-loop iterations within each outer iteration, which typically
yields a more accurate estimation of the lower-level minimizer. However, in a
decentralized network setting, this requires a two-timescale implementation
with high coordination complexity, as well as high computation and sample
complexities in the inner loop. On the other hand, the single-loop
architecture iteratively solves the upper- and lower-level subproblems and
updates corresponding parameters simultaneously, which is much easier to
implement in the decentralized setting. However, it is unclear whether the
less accurate inner subproblem solutions could also result in high
communication and sample complexities in the overall training process.

  * •

Achieving Low Communication and Sample Complexities: Since there is no
dedicated centralized server in decentralized bilevel optimization over edge
networks, it is infeasible to aggregate the local datasets at the
geographically dispersed agents. Hence, it is necessary for the agents to
communicate and exchange information with each other to reach a “consensus
solution” [12, 13, 14, 15]. In such scenarios, how to design efficient
algorithms to reduce the required rounds of communications (i.e.,
communication complexity) to reach consensus is one of the most important
questions in algorithm design. This is particularly true for deploying
decentralized bilevel optimization over wireless edge networks that may have
low-speed and unreliable links. Also, due to the fact that the agents (i.e.,
computing nodes) in many wireless edge networks are fundamentally constrained
by computation capabilities (e.g., sensors or smart phones with limited
computation speed, energy, and memory), it is important to design efficient
algorithms to reduce the required number of samples (i.e., sample complexity).
However, achieving low sample and communication complexities are two
fundamentally conflicting goals. On one hand, the variance of a stochastic
gradient highly depends on the number of samples in each mini-batch. The more
samples in each mini-batch (i.e., potentially higher sample complexity), the
larger the variance, which may imply fewer communication rounds for
convergence (i.e., lower communication complexity). On the other hand, if one
prefers to use fewer samples per iteration to lower per-iteration sample
complexity, the stochastic gradient information is noisier, which could result
in more communication rounds to reach certain training accuracy (i.e., higher
communication complexity).

In addition to the above challenges, the coupled structure and the inherent
non-convexity of the decentralized bilevel optimization problems make it
challenging to design algorithms and theoretically analyze their performance.
So far, results on designing decentralized bilevel optimization algorithms
with low sample, communication, and implementation complexities remains rather
limited in the literature (see Section II for more detailed discussions). The
main contribution of this paper is that we propose a series of new algorithm
design techniques, which overcome the aforementioned challenges and achieve
low sample and communication complexities with a single-loop structure for
decentralized bilevel optimization problems. The key results of this paper are
summarized as follows:

  * •

We propose an algorithm called $\mathsf{DIAMOND}~{}$(decentralized single-loop
stochastic approximation with momentum and gradient-tracking) for solving
decentralized bilevel optimization problems over networks. Our proposed
$\mathsf{DIAMOND}~{}$algorithm integrates consensus-based updates with
gradient tracking and momentum-based stochastic gradient estimators, which is
a carefully designed triple-hybrid approach. We show that this triple-hyrid
approach enables the use of a single-loop algorithmic architecture, which
significantly reduces the implementation complexity over peer-to-peer edge
networks.

  * •

We show that $\mathsf{DIAMOND}~{}$achieves a sample complexity of
$\mathcal{O}(\epsilon^{-3/2})$ to find an $\epsilon$-stationary solution for
non-convex upper-level optimization objectives. Interestingly, this result
matches the state-of-the-art sample complexity of stochastic first-order
algorithms for solving single-agent bilevel optimization problems. Meanwhile,
the communication complexity of $\mathsf{DIAMOND}~{}$is
$\mathcal{O}(\epsilon^{-3/2})$. These results show that
$\mathsf{DIAMOND}~{}$strikes a good balance between sample and communication
complexities.

  * •

We conduct extensive experiments to validate the theoretical results of the
proposed $\mathsf{DIAMOND}~{}$algorithm. Our experimental results show that
$\mathsf{DIAMOND}~{}$outperforms other stochastic first-order baseline
algorithms in terms of sample complexities in various communication network
settings.

The rest of the paper is organized as follows. In Section II, we review
related work to provide the necessary background on decentralized and bilevel
optimization, and put our work in comparative perspectives. In Section III, we
present the system model and the consensus reformulation of decentralized
bilevel optimization. In Section IV, we propose the
$\mathsf{DIAMOND}~{}$algorithm. We then provide the theoretical convergence
analysis of $\mathsf{DIAMOND}~{}$in Section V. Section VI provides numerical
results to verify our theoretical findings, and Section VII concludes this
paper.

##  II Related Work

To facilitate our discussions in subsequent sections, we organize the related
work in three parts. First, we survey the approaches for solving single-agent
bilevel optimization to provide a contrasting view for decentralized bilevel
optimization. Then, we review the literature on decentralized optimization for
single-level loss minimization to familiarize readers with the basics of
decentralized optimization over networks. Lastly, we provide an in-depth
comparison with the most related work on decentralized bilevel optimization.

1) Single-Agent Bilevel Optimization: 1-a) Gradient-Based Approaches: To our
knowledge, single-agent bilevel optimization was first studied in [16]. Since
then, several solution approaches have been proposed, such as 1) penalizing
the outer function with the optimality conditions of the inner problem [17,
18]; 2) reformulating the bilevel problem as a single-level problem by
replacing the lower-level problem with its optimality conditions [19, 20]; and
3) utilizing gradient-based techniques to iteratively approximate the
(stochastic) gradient of the upper-level problem. Gradient-based algorithms
for bilevel optimization have gained the most attention due to their ease of
analysis. Many gradient-based bilevel optimization algorithms have been
proposed, including but not limited to: i) AID-based [21, 4, 22], ii) ITD-
based [6, 23, 24], and iii) SGD-based [7, 1, 11, 8]. However, these algorithms
were designed for single-agent bilevel optimization problems and not
applicable for the decentralized settings.

1-b) Momentum-Based Approaches: Momentum-based approaches enhance the
gradient-based algorithms for single-agent bilevel optimization. It has been
shown that momentum improves the computation efficiency of stochastic gradient
updates both in theory and in practice. Several bilevel optimization
algorithms that exploit momentum have been proposed, such as STABLE [9], RSVRB
[10], MRBO [8], and SUSTAIN [11]. All of them share a similar single-loop
algorithmic architecture. To reach an $\epsilon$-stationary point, STABLE
requires an order of $\mathcal{O}\left(\epsilon^{-2}\right)$ samples, while
RSVRB, MRBO and SUSTAIN require $\mathcal{O}\left(\epsilon^{-3/2}\right)$
samples. Compared to STABLE, which only uses a momentum-based stochastic
gradient estimator for the upper-level subproblems, RSVRB, MRBO, and SUSTAIN
all utilize momentum-based stochastic gradient estimators for both the upper-
and lower-level subproblems. However, all these momentum-based algorithms are
designed for the single-agent bilevel optimization setting. In comparison, we
focus on decentralized multi-agent bilevel optimization, and propose the
$\mathsf{DIAMOND}~{}$algorithm, which uses momentum-based stochastic gradient
estimators in both upper- and lower-levels. Our theoretical result shows that
$\mathsf{DIAMOND}~{}$has the sample complexity of
$\mathcal{O}\left(\epsilon^{-3/2}\right)$, matching the state-of-the-art
result achieved by RSVRB, MRBO and SUSTAIN, but for the more challenging
decentralized setting.

2) Decentralized Optimization for Single-Level Loss Minimization over
Networks: Decentralized optimization for single-level loss minimization over
networks traces its roots to the seminal work[25], and has found important
applications in many engineering fields, e.g., network resource allocation
[26], power networks [27], and robotic networks [28]. One of the most popular
methods to solve decentralized optimization problems is the distributed
stochastic gradient descent (DSGD) [14], which established the well-known
$O(1/\sqrt{T})$ convergence rate with $T$ iterations. Subsequently, [29]
showed that DSGD can outperform the centralized SGD counterpart. Recently,
various sample- and communication-efficient variants of DSGD have been
proposed, e.g., leveraging compression[30], momentum [31], gradient tracking
[32, 33], and variance reduction techniques [12, 34, 35]. However, results on
solving general decentralized bilevel optimization problems are still limited.

3) Decentralized Bilevel Optimization over Networks: So far, the research on
decentralized bilevel optimization remains in its infancy. As mentioned
earlier, due to the lack of a centralized server in the decentralized setting,
it is natural for us to consider the network-consensus approach[12, 13, 14,
15] as the solution strategy in this paper. To our knowledge, the most related
and the only work that also adopts a consensus-based approach for solving
decentralized bilevel optimization problems is reported in [13], which
contains two algorithmic variants called INTERACT and SVR-INTERACT.
Specifically, INTERACT is a local-full-gradient-based algorithm with gradient
tracking and achieves
$\left[\mathcal{O}\left(n\epsilon^{-1}\right),\mathcal{O}\left(\epsilon^{-1}\right)\right]$
sample-communication complexity, where $n$ is the size of the dataset at each
agent. Recall that the sample and communication complexities of our
$\mathsf{DIAMOND}~{}$are both $\mathcal{O}\left(\epsilon^{-3/2}\right)$, which
is independent of data size. This implies that in the large dataset regime
$\Theta(\epsilon^{-1/2})$, which is not uncommon in the era of “big data,”
INTERACT suffers a higher sample complexity than that of our
$\mathsf{DIAMOND}~{}$algorithm.

To lower the sample complexity of INTERACT, SVR-INTERACT leverages variance
reduction techniques to retain the same communication complexity as INTERACT,
while achieving a lower but still dataset-dependent sample complexity.Thus, in
the large dataset regime $\Omega(\epsilon^{-1})$, the sample complexity of
SVR-INTERACT will be higher than that of $\mathsf{DIAMOND}$. Also, SVR-
INTERACT still requires periodic full gradients, while
$\mathsf{DIAMOND}~{}$only needs stochastic gradient evaluations. Moreover, due
to the variance reduction techniques, SVR-INTERACT has a double-loop
algorithmic architecture. By contrast, $\mathsf{DIAMOND}~{}$is single-loop
structure, which has a lower computational cost and is easier to implement.
Apart from these, SVR-INTERACT was designed to solve deterministic bilevel
optimization problems, rather than stochastic bilevel optimization problems
that has wider applications when the sample size of training data is large
(e.g., hyperparameter optimization [36]) or the fresh data is sampled for
algorithm iterations (e.g., reinforcement learning [1]).

##  III System Model and Problem Formulation

In this section, we will present the network-consensus-based problem
reformulation that paves the way for our subsequent algorithm design and
analysis. Recall from Problem (I) that we consider a peer-to-peer
communication network represented by a graph. Suppose that each agent $i$ can
communicate with its set of neighbors denoted by
$\mathcal{N}_{i}\triangleq\left\\{j\in\mathcal{N},:\left(i,j\right)\in\mathcal{L}\right\\}$.
To solve Problem (I) in a decentralized fashion, one can rewrite Problem (I)
as follows:

$\displaystyle\min_{\mathbf{x}_{i}\in\mathbb{R}^{d_{\mathrm{up}}}}l\left(\mathbf{x}\right)=\frac{1}{m}\sum_{i=1}^{m}\left\\{l_{i}\left(\mathbf{x}_{i}\right)\triangleq\mathbb{E}_{\xi_{i}}\left[f_{i}\left(\mathbf{x}_{i},\mathbf{y}_{i}^{*}\left(\mathbf{x}_{i}\right);\xi_{i}\right)\right]\right\\}\text{,}$
$\displaystyle\text{s.t.
}\mathbf{y}_{i}^{*}\left(\mathbf{x}_{i}\right)=\arg\\!\\!\\!\\!\min_{\mathbf{y}_{i}\in\mathbb{R}^{d_{\mathrm{low}}}}\left\\{g_{i}\left(\mathbf{x}_{i},\mathbf{y}_{i}\right)\triangleq\mathbb{E}_{\zeta_{i}}\left[g_{i}\left(\mathbf{x}_{i},\mathbf{y}_{i};\zeta_{i}\right)\right]\right\\}\text{,}$
$\displaystyle\qquad\mathbf{x}_{i}=\mathbf{x}_{j}\text{, if
}(i,j)\in\mathcal{L},$ (2)

where $\mathbf{x}_{i}\in\mathbb{R}^{d_{\mathrm{up}}}$, $\forall i$, are the
local copies of the global upper-level variables at agent
$i\in\left\\{1,\ldots,m\right\\}$ and $g_{i}(\mathbf{x}_{i},\mathbf{y}_{i})$
is the local lower-level loss at agent $i$. For notation simplicity, we denote
$f_{i}\left(\mathbf{x}_{i},\mathbf{y}_{i}^{*}\left(\mathbf{x}_{i}\right)\right)\\!\triangleq\\!\mathbb{E}_{\xi_{i}}\left[f_{i}\left(\mathbf{x}_{i},\mathbf{y}_{i}^{*}\left(\mathbf{x}_{i}\right);\xi_{i}\right)\right]$.
The equality constraint in Problem (III) ensures that all agents share the
same global $\mathbf{x}$-value to achieve the minimization of the upper-level
function, hence the name “consensus form” [14, 15, 12, 13]. We assume that
$f_{i}(\mathbf{x}_{i},\mathbf{y}_{i}^{*}(\mathbf{x}_{i}))$ is non-convex in
$\mathbf{x}_{i}$, $\forall i$, in general, and
$g_{i}(\mathbf{x}_{i},\mathbf{y}_{i})$ is strongly-convex in $\mathbf{y}_{i}$,
$\forall i$, which typically holds in meta-learning, hyper-parameter
optimization (see Section VI), and MARL with quadratically-regularized linear
critics. Now, we define the notion of $\epsilon$-stationarity that serves as
the convergence metric.

######  Definition 1 ($\epsilon$-Stationary Point).

A stochastic algorithm reaches an $\epsilon$-stationary point
$\left\\{\mathbf{x}_{i},\mathbf{y}_{i},\forall i\in\left[m\right]\right\\}$ if

$\mathbb{E}\Big{[}\underbrace{\|\nabla
l(\bar{\mathbf{x}})\|^{2}}_{\begin{subarray}{c}\mathrm{Stationarity}\\\
\mathrm{Error}\end{subarray}}+\underbrace{\left\|\mathbf{y}^{*}-\mathbf{y}\right\|^{2}}_{\begin{subarray}{c}\mathrm{Lower-
Level}\\\
\mathrm{Error}\end{subarray}}+\underbrace{\frac{1}{m}\sum\nolimits_{i=1}^{m}\left\|\mathbf{x}_{i}-\bar{\mathbf{x}}\right\|^{2}}_{\begin{subarray}{c}\mathrm{Consensus}~{}\mathrm{Error}\end{subarray}}\Big{]}\leq\epsilon\text{,}$

where $\bar{\mathbf{x}}\triangleq\frac{1}{m}\sum_{i=1}^{m}\mathbf{x}_{i}$,
$\mathbf{y}\triangleq\left[\mathbf{y}_{1}^{\top},\ldots,\mathbf{y}_{m}^{\top}\right]^{\top}$,
and
$\mathbf{y}^{*}\triangleq\left[\mathbf{y}_{1}^{*\top},\ldots,\mathbf{y}_{m}^{*\top}\right]^{\top}$.
The expectation is taken over the randomness of the algorithm.

Next, we formally define the sample complexity and communication complexity of
a decentralized algorithm, which are also used in the literature (e.g., [13,
12]).

######  Definition 2 (Sample Complexity).

The sample complexity is defined as the total number of incremental first-
order oracle (IFO) calls required per node for an algorithm to reach an
$\epsilon$-stationary point defined in Definition 1, where one IFO call is
defined as the evaluation of the stochastic gradient of upper- and lower-level
problems at agent $i\in\left[m\right]$.

######  Definition 3 (Communication Complexity).

The communication complexity is defined as the total rounds of communications
required to find an $\epsilon$-stationary point defined in Definition 1, where
each node can send and receive local parameters with its neighbors in one
communication round.

##  IV The $\mathsf{DIAMOND}~{}$Algorithm

In this section, we present our $\mathsf{DIAMOND}~{}$algorithm for solving
Problem (III). Since the agents can communicate with their neighbors through
the network to send and receive information (model parameters) and aggregate
the received information, we define the consensus weight matrix
$\mathrm{\mathbf{M}}\in\mathbb{R}^{m\times m}$, where
$\left[\mathrm{\mathbf{M}}\right]_{ij}$ represents the consensus weight over
edge $(i,j)\in\mathcal{L}$. We assume that $\mathbf{M}$ satisfies the
following:

  * 1)

Doubly stochastic:
$\sum_{i=1}^{m}\left[\mathrm{\mathbf{M}}\right]_{ij}=\sum_{j=1}^{m}\left[\mathrm{\mathbf{M}}\right]_{ij}=1,\forall
i,j$;

  * 2)

Symmetric:
$\left[\mathrm{\mathbf{M}}\right]_{ij}=\left[\mathrm{\mathbf{M}}\right]_{ji},\forall
i,j\in\mathcal{N}$;

  * 3)

Network-defined sparsity: $\left[\mathrm{\mathbf{M}}\right]_{ij}>0$ if
$\left(i,j\right)\\!\in\\!\mathcal{L}$; otherwise,
$\left[\mathrm{\mathbf{M}}\right]_{ij}=0,\forall i,j\in\mathcal{N}$.

The above conditions imply that the eigenvalues of $\mathrm{\mathbf{M}}$ are
real and thus could be sorted as:
$-1<\lambda_{m}\left(\mathrm{\mathbf{M}}\right)\leq\cdots\leq\lambda_{2}\left(\mathrm{\mathbf{M}}\right)<\lambda_{1}\left(\mathrm{\mathbf{M}}\right)=1$.
We denote the second largest eigenvalue in magnitude of $\mathbf{M}$ as
$\lambda\triangleq\max\left\\{\left|\lambda_{2}\left(\mathrm{\mathbf{M}}\right)\right|,\left|\lambda_{m}\left(\mathrm{\mathbf{M}}\right)\right|\right\\}$,
which will play an important role in the step-size selection for our proposed
algorithm. Note that the choice of $\mathbf{M}$ is not unique. For example,
one possible choice of $\mathrm{\mathbf{M}}$ that only relies on local
information is the Metropolis weights [37]:

$\displaystyle[\mathrm{\mathbf{M}}]_{ij}=\left\\{1+\max\left[d(i),d(j)\right]\right\\}^{-1},\forall(i,j)\in\mathcal{L},$
$\displaystyle[\mathrm{\mathbf{M}}]_{ii}=1-\sum_{j\neq
i}[\mathrm{\mathbf{M}}]_{ij},\forall i\in\mathcal{N},$

where $d(i)=|\mathcal{N}_{i}|$ is the degree of agent $i$.

Using the implicit function theorem, the hypergradient of
$l_{i}\left(\mathbf{x}_{i}\right)$ for a given
$\mathbf{x}_{i}\in\mathbb{R}^{d_{\mathrm{up}}}$ can be evaluated as [6]:

$\displaystyle\nabla l_{i}(\mathbf{x}_{i})=$
$\displaystyle\nabla_{\mathbf{x}}f_{i}\left(\mathbf{x}_{i},\mathbf{y}_{i}^{*}(\mathbf{x}_{i})\right)-\nabla_{\mathbf{x}\mathbf{y}}^{2}g_{i}\left(\mathbf{x}_{i},\mathbf{y}_{i}^{*}(\mathbf{x}_{i})\right)\times$
$\displaystyle\quad\left[\nabla_{\mathbf{y}\mathbf{y}}^{2}g_{i}\left(\mathbf{x}_{i},\mathbf{y}_{i}^{*}(\mathbf{x}_{i})\right)\right]^{-1}\nabla_{\mathbf{y}}f_{i}\left(\mathbf{x}_{i},\mathbf{y}_{i}^{*}(\mathbf{x}_{i})\right)\text{.}$
(3)

Since obtaining $\mathbf{y}_{i}^{*}(\mathbf{x}_{i})$ in closed-form is
difficult, $\bar{\nabla}f_{i}\left(\mathbf{x}_{i},\mathbf{y}_{i}\right)$ is
used as a surrogate of $\nabla l_{i}\left(\mathbf{x}_{i}\right)$ at any
$\left(\mathbf{x}_{i},\mathbf{y}_{i}\right)\in\mathbb{R}^{d_{\mathrm{up}}\times
d_{\mathrm{low}}}$, which is defined as follows [6]:

$\displaystyle\bar{\nabla}f_{i}\left(\mathbf{x}_{i},\mathbf{y}_{i}\right)=$
$\displaystyle\nabla_{\mathbf{x}}f_{i}\left(\mathbf{x}_{i},\mathbf{y}_{i}\right)-\nabla_{\mathbf{x}\mathbf{y}}^{2}g_{i}\left(\mathbf{x}_{i},\mathbf{y}_{i}\right)\times$
$\displaystyle\left[\nabla_{\mathbf{y}\mathbf{y}}^{2}g_{i}\left(\mathbf{x}_{i},\mathbf{y}_{i}\right)\right]^{-1}\nabla_{\mathbf{y}}f_{i}\left(\mathbf{x}_{i},\mathbf{y}_{i}\right)\text{.}$
(4)

Note that the computation of
$\bar{\nabla}f_{i}\left(\mathbf{x}_{i},\mathbf{y}_{i}\right)$ involves exact
Hessian matrix inverse and gradient, which is cumbersome. To avoid this
expensive computation, we adopt the biased stochastic gradient estimation of
$\bar{\nabla}f_{i}\left(\mathbf{x}_{i},\mathbf{y}_{i}\right)$ defined as [11]:

$\displaystyle\hat{\nabla}f_{i}\left(\mathbf{x}_{i},\mathbf{y}_{i};\bar{\xi}_{i}\right)=\nabla_{\mathbf{x}}f_{i}\left(\mathbf{x}_{i},\mathbf{y}_{i};\xi_{i}\right)-\frac{K}{L_{g}}\nabla_{\mathbf{x}\mathbf{y}}^{2}g_{i}\left(\mathbf{x}_{i},\mathbf{y}_{i};\zeta_{i}^{0}\right)$
$\displaystyle\quad\times\prod_{j=1}^{k\left(K\right)}\left(I-\frac{\nabla_{\mathbf{y}\mathbf{y}}^{2}g_{i}\left(\mathbf{x}_{i},\mathbf{y}_{i};\zeta_{i}^{j}\right)}{L_{g}}\right)\nabla_{\mathbf{y}}f_{i}\left(\mathbf{x}_{i},\mathbf{y}_{i};\xi_{i}\right),\\!\\!\\!\\!\\!$
(5)

where $k\left(K\right)\sim\mathcal{U}\\{0,\cdots,K-1\\}$ is a uniform random
variable chosen from $\left\\{0,\cdots,K-1\right\\}$. A total of $K+2$
independent samples are collected from the upper- and lower-level
distributions $\pi_{f}$ and $\pi_{g}$, respectively. We denote all random
variables needed in (IV) as a $(K\\!+\\!3)$-tuple:
$\bar{\xi}_{i}\triangleq\left\\{\xi_{i},\zeta_{i}^{0},\cdots,\zeta_{i}^{K},k\left(K\right)\right\\}$,
where $\xi_{i}\sim\pi_{f}$, $\zeta_{i}^{j}\sim\pi_{g}\text{, }j=0,\cdots,K$.

The overall framework of the proposed $\mathsf{DIAMOND}~{}$algorithm for
solving the decentralized bilevel optimization problem in (III) is summarized
in Algorithm 1.

Algorithm 1 The $\mathsf{DIAMOND}~{}$Algorithm.

1:Input: Step-sizes $\alpha_{t}$, $\beta_{t}$. Momentum coefficients
$\eta_{t}$, $\gamma_{t}$.

2:Initialization: Let
$\left\\{\mathbf{x}_{i,-1},\mathbf{y}_{i,-1}\right\\}_{i=1}^{m}=\left\\{\mathbf{x}_{-1},\mathbf{y}_{-1}\right\\}$.
Let $\left\\{\mathbf{p}_{i,-1}\right\\}_{i=1}^{m}=\mathbf{0}$, and
$\left\\{\mathbf{v}_{i,-1}\right\\}_{i=1}^{m}=\mathbf{0}$

3:for $t=0$ to $T-1$ do

4: for each agent $i\in\left[m\right]$ do

5: Estimate the stochastic gradients $\mathbf{p}_{i,t}$ and $\mathbf{v}_{i,t}$

6: using (IV) and (IV);

7: Track the global gradient $\mathbf{u}_{i,t}$ using (8);

8: Update the local model parameters $\mathbf{x}_{i,t+1}$ and

9: $\mathbf{y}_{i,t+1}$ using (9) and (10);

10: end for

11:end for

Note that $\mathsf{DIAMOND}~{}$adopts a single-loop structure, which reduces
the computation and implementation complexities compared with the double-loop
structure. Meanwhile, $\mathsf{DIAMOND}~{}$relies on consensus updates along
with gradient tracking and uses momentum-based stochastic gradient estimators,
so that it matches state-of-the-art convergence guarantees. Thus,
$\mathsf{DIAMOND}~{}$consists of three parts: i) local stochastic gradient
estimation, ii) global gradient tracking, and iii) consensus update with
stochastic gradient descent (SGD). The details of each part are described as
follows:

1) Local Stochastic Gradient Estimation: Each agent estimates the momentum-
based upper- and lower-level update directions $\mathbf{p}_{i,t}$ and
$\mathbf{v}_{i,t}$ of the upper-level and lower-level functions, respectively,
with its local stochastic gradients:

$\displaystyle\mathbf{p}_{i,t}=$
$\displaystyle\hat{\nabla}f_{i}\left(\mathbf{x}_{i,t},\mathbf{y}_{i,t};\bar{\xi}_{i}\right)$
$\displaystyle+\left(1-\eta_{t}\right)\left(\mathbf{p}_{i,t-1}-\hat{\nabla}f_{i}\left(\mathbf{x}_{i,t-1},\mathbf{y}_{i,t-1};\bar{\xi}_{i}\right)\right),$
(6) $\displaystyle\mathbf{v}_{i,t}=$
$\displaystyle\nabla_{\mathbf{y}}g_{i}\left(\mathbf{x}_{i,t},\mathbf{y}_{i,t};\zeta_{i}\right)$
$\displaystyle+\left(1-\gamma_{t}\right)\left(\mathbf{v}_{i,t-1}-\nabla_{\mathbf{y}}\mathbf{g}_{i}\left(\mathbf{x}_{i,t-1},\mathbf{y}_{i,t-1};\zeta_{i}\right)\right),$
(7)

where $\eta_{t}\in\left[0,1\right]$ and $\gamma_{t}\in\left[0,1\right]$ are
the momentum coefficients. Note that the avoidance of the full gradient
computation implies a noisy gradient estimation. $\mathsf{DIAMOND}~{}$utilizes
momentum-based stochastic gradient estimations to improve the accuracy of the
current gradient estimation, which is similar to [38, 39] for single-level
stochastic optimization and [11, 8] for single-agent bilevel optimization.

2) Global Gradient Tracking: Each agent updates the global gradient
$\mathbf{u}_{i,t}$ by averaging all its neighbors’ gradient estimates
$\mathbf{u}_{j,t-1}$, $j\in\mathcal{N}_{i}$, which is defined as:

$\mathbf{u}_{i,t}=\sum_{j\in\mathcal{N}_{i}}[\mathbf{M}]_{ij}\mathbf{u}_{j,t-1}+\mathbf{p}_{i,t}-\mathbf{p}_{i,t-1}.$
(8)

We do not perform gradient tracking for $\mathbf{v}_{i,t}$ since the lower-
level $\mathbf{y}$-variables do not require consensus (cf. Problem (III)).

3) Consensus Update with Decentralized SGD: Each agent $i$ updates the upper-
level parameters by computing a weighted average of its neighbors’ local
copies $\mathbf{x}_{j,t}$, $j\in\mathcal{N}_{i}$ and using the tracked global
gradient $\mathbf{u}_{i,t}$ computed in 2):

$\mathbf{x}_{i,t+1}=\sum_{j\in\mathcal{N}_{i}}[\mathbf{M}]_{ij}\mathbf{x}_{j,t}-\alpha_{t}\mathbf{u}_{i,t},$
(9)

where $\alpha_{t}$ is the upper-level step-size. The lower-level model
parameters $\mathbf{y}_{i,t+1}$ are updated locally by using
$\mathbf{v}_{i,t}$:

$\mathbf{y}_{i,t+1}=\mathbf{y}_{i,t}-\beta_{t}\mathbf{v}_{i,t},$ (10)

where $\beta_{t}$ is the lower-level step-size. Again, note that consensus is
only required for the upper-level $\mathbf{x}_{i}$-parameters.

##  V Theoretical Performance Analysis

In this section, we establish the theoretical convergence guarantees for the
$\mathsf{DIAMOND}~{}$algorithm for solving the decentralized bilevel
optimization problem in (III). Before describing the proof details, we first
highlight three major challenges in the convergence analysis in our
$\mathsf{DIAMOND}~{}$algorithm:

a) Momentum-Based Stochastic Gradient Estimation Error of the Lower-Level
Subproblem: Although the stochastic gradient estimation
$\nabla_{\mathbf{y}}g_{i}(\mathbf{x}_{i,t},\mathbf{y}_{i,t},\zeta_{i})$ of the
lower-level objective function is unbiased, there exists a bias between
$\mathbf{v}_{i,t}$ and the full gradient due to the randomness and the added
momentum, which can be written as
$\mathbf{e}_{i,t}^{g}\triangleq\mathbf{v}_{i,t}-\nabla_{\mathbf{y}}g_{i}\left(\mathbf{x}_{i,t},\mathbf{y}_{i,t}\right)$.

b) Momentum-Based Stochastic Gradient Estimation Error of the Upper-Level
Subproblem: The momentum-based stochastic gradient estimation error of the
upper-level subproblem is caused by: i) the randomness of the gradient
estimation $\mathbf{p}_{i,t}$, ii) the added momentum, and iii) the
approximation
$\mathbf{y}_{i,t}\approx\mathbf{y}_{i,t}^{*}\left(\mathbf{x}_{i,t}\right)$. We
denote this error as:
$\mathbf{e}_{i,t}^{f}\triangleq\mathbf{p}_{i,t}-\bar{\nabla}f_{i}\left(\mathbf{x}_{i,t},\mathbf{y}_{i,t}\right)-\mathbf{b}_{i,t}$.
where
$\mathbf{b}_{i,t}\triangleq\mathbb{E}_{\bar{\xi}_{i}}[\hat{\nabla}f_{i}\left(\mathbf{x}_{i,t},\mathbf{y}_{i,t};\bar{\xi}_{i}\right)]-\bar{\nabla}f_{i}\left(\mathbf{x}_{i,t},\mathbf{y}_{i,t}\right)$
is the bias.

c) Consensus Error: $\mathsf{DIAMOND}~{}$utilizes a decentralized consensus
update for the upper-level model parameters as shown in (8), which inevitably
introduces consensus errors.

###  V-A Main Convergence Results

To quantify the convergence rate performance of $\mathsf{DIAMOND}$, we first
define a new convergence metric specifically for the decentralized bilevel
problem in (III):

$\mathfrak{M}_{t}\triangleq\left\|\nabla
l\left(\bar{\mathbf{x}}_{t}\right)\right\|^{2}+\left\|\mathbf{x}_{t}-1\otimes\bar{\mathbf{x}}_{t}\right\|^{2}+\left\|\mathbf{y}_{t}^{*}-\mathbf{y}_{t}\right\|^{2}\text{,}$
(11)

where
$\bar{\mathbf{x}}_{t}\triangleq\frac{1}{m}\sum_{i=1}^{m}\mathbf{x}_{i,t}$,
$\mathbf{x}_{t}\triangleq\left[\mathbf{x}_{1,t}^{\top},\ldots,\mathbf{x}_{m,t}^{\top}\right]^{\top}$,
$\mathbf{y}_{t}\triangleq\left[\mathbf{y}_{1,t}^{\top},\ldots,\mathbf{y}_{m,t}^{\top}\right]^{\top}$,
and
$\mathbf{y}_{t}^{*}\triangleq\left[\mathbf{y}_{1,t}^{*\top},\ldots,\mathbf{y}_{m,t}^{*\top}\right]^{\top}$.
The first term in (11) measures the convergence of the agent-average
$\bar{\mathbf{x}}_{t}$ to a stationary point. The second term in (11)
quantifies the consensus error among local copies of the upper-level
$\mathbf{x}_{t}$-parameters. The third term in (11) measures the approximation
error caused by the finite iterations of the lower-level optimization across
all agents. Clearly, if $\mathfrak{M}_{t}\to 0$, we can conclude that the
algorithm achieves three goals simultaneously: 1) achieving a stationary
solution of the decentralized bilevel optimization problem in (III), 2)
reaching consensus of upper-level model parameters across all agents, and 3)
obtaining optimal solutions to the lower-level subproblem.

Next, we state the following assumptions that are useful for our convergence
performance analysis:

######  Assumption 1 (Upper-Level Objective).

$f_{i}\left(\mathbf{x}_{i},\mathbf{y}_{i}\right)$ satisfies:

  * 1)

For any $i\in\left\\{1,\ldots,m\right\\}$ and
$\left(\mathbf{x}_{i},\mathbf{y}_{i}\right)\in\mathbb{R}^{d_{\mathrm{up}}}\times\mathbb{R}^{d_{\mathrm{low}}}$,
$\nabla_{\mathbf{x}}f_{i}\left(\mathbf{x}_{i},\mathbf{y}_{i}\right)$ and
$\nabla_{\mathbf{y}}f_{i}\left(\mathbf{x}_{i},\mathbf{y}_{i}\right)$ are
Lipschitz continuous with constants $L_{f_{x}}\geq 0$ and $L_{f_{y}}\geq 0$,
respectively.

  * 2)

For any $i\in\left\\{1,\ldots,m\right\\}$ and
$\left(\mathbf{x}_{i},\mathbf{y}_{i}\right)\in\mathbb{R}^{d_{\mathrm{up}}}\times\mathbb{R}^{d_{\mathrm{low}}}$,
we have
$\left\|\nabla_{\mathbf{y}}f_{i}\left(\mathbf{x}_{i},\mathbf{y}_{i}\right)\right\|\leq
C_{f_{y}}$ for some constants $C_{f_{y}}\geq 0$.

######  Assumption 2 (Lower-Level Objective).

$g_{i}\left(\mathbf{x}_{i},\mathbf{y}_{i}\right)$ satisfies:

  * 1)

For any $\mathbf{x}_{i}\in\mathbb{R}^{d_{\mathrm{up}}}$ and
$\mathbf{y}_{i}\in\mathbb{R}^{d_{\mathrm{low}}}$,
$g_{i}\left(\mathbf{x}_{i},\mathbf{y}_{i}\right)$ is twice continuously
differentiable with respect to $\left(\mathbf{x}_{i},\mathbf{y}_{i}\right)$.

  * 2)

For any $i\in\left\\{1,\ldots,m\right\\}$ and
$\left(\mathbf{x}_{i},\mathbf{y}_{i}\right)\in\mathbb{R}^{d_{\mathrm{up}}}\times\mathbb{R}^{d_{\mathrm{low}}}$,
$\nabla_{\mathbf{y}}g_{i}\left(\mathbf{x}_{i},\mathbf{y}_{i}\right)$ is
Lipschitz continuous with constant $L_{g}\geq 0$.

  * 3)

For any $i\in\left\\{1,\ldots,m\right\\}$ and
$\mathbf{x}_{i}\in\mathbb{R}^{d_{\mathrm{up}}}$,
$g_{i}\left(\mathbf{x}_{i},\cdot\right)$ is $\mu_{g}$-strongly convex with
respect to $\mathbf{y}_{i}$ for some $\mu_{g}>0$.

  * 4)

For any $i\in\left\\{1,\ldots,m\right\\}$ and
$\left(\mathbf{x}_{i},\mathbf{y}_{i}\right)\in\mathbb{R}^{d_{\mathrm{up}}}\times\mathbb{R}^{d_{\mathrm{low}}}$,
$\nabla_{\mathbf{x}\mathbf{y}}^{2}g_{i}\left(\mathbf{x}_{i},\mathbf{y}_{i}\right)$
and
$\nabla_{\mathbf{y}\mathbf{y}}^{2}g_{i}\left(\mathbf{x}_{i},\mathbf{y}_{i}\right)$
are Lipschitz continuous with constants $L_{g_{xy}}\geq 0$ and $L_{g_{yy}}\geq
0$, respectively.

  * 5)

For any $i\in\left\\{1,\ldots,m\right\\}$ and
$\left(\mathbf{x}_{i},\mathbf{y}_{i}\right)\in\mathbb{R}^{d_{\mathrm{up}}}\times\mathbb{R}^{d_{\mathrm{low}}}$,
we have
$\left\|\nabla_{\mathbf{x}\mathbf{y}}^{2}g_{i}\left(\mathbf{x}_{i},\mathbf{y}_{i}\right)\right\|^{2}\leq
C_{g_{xy}}$ for some $C_{g_{xy}}>0$.

######  Assumption 3 (Stochastic Objectives).

Assumptions 1 and 2 hold for
$f_{i}\left(\mathbf{x}_{i},\mathbf{y}_{i};\xi_{i}\right)$ and
$g_{i}\left(\mathbf{x}_{i},\mathbf{y}_{i};\zeta_{i}\right)$, for all
$\xi_{i}\in\mathrm{supp}\left(\pi_{f}\right)$ and
$\zeta_{i}\in\mathrm{supp}\left(\pi_{g}\right)$ where
$\mathrm{supp}\left(\pi\right)$ denotes the support of distribution $\pi$.

######  Assumption 4 (Stochastic Gradients).

For any $i\\!\in\\!\left\\{1,\ldots,m\right\\}$ and
$\left(\mathbf{x}_{i},\mathbf{y}_{i}\right)\\!\in\\!\mathbb{R}^{d_{\mathrm{up}}}\\!\times\\!\mathbb{R}^{d_{\mathrm{low}}}$,
the gradient estimators
$\hat{\nabla}f_{i}\left(\mathbf{x}_{i},\mathbf{y}_{i};\bar{\xi}_{i}\right)$
and
$\nabla_{\mathbf{y}}g_{i}\left(\mathbf{x}_{i},\mathbf{y}_{i};\zeta_{i}\right)$
satisfy:

  * 1)

There exists a constant $\sigma_{f}\geq 0$ such that
$\mathbb{E}_{\bar{\xi}_{i}}[\|\hat{\nabla}f_{i}(\mathbf{x}_{i},\mathbf{y}_{i};\bar{\xi}_{i})-\bar{\nabla}f_{i}(\mathbf{x}_{i},\mathbf{y}_{i})-\mathbf{b}_{i}(\mathbf{x}_{i},\mathbf{y}_{i})\|^{2}]\leq\sigma_{f}^{2}$,
where
$\mathbf{b}_{i}(\mathbf{x}_{i},\mathbf{y}_{i})\triangleq\mathbb{E}_{\bar{\xi}_{i}}[\hat{\nabla}f_{i}(\mathbf{x}_{i},\mathbf{y}_{i};\bar{\xi}_{i})]-\bar{\nabla}f_{i}(\mathbf{x}_{i},\mathbf{y}_{i})$
is the bias in estimating $\bar{\nabla}f_{i}(\mathbf{x}_{i},\mathbf{y}_{i})$.

  * 2)

There exists a constant $\sigma_{g}\geq 0$ such that
$\mathbb{E}_{\zeta_{i}}[\|\nabla_{\mathbf{y}}g_{i}(\mathbf{x}_{i},\mathbf{y}_{i};\zeta_{i})-\nabla_{\mathbf{y}}g_{i}(\mathbf{x}_{i},\mathbf{y}_{i})\|^{2}]\leq\sigma_{g}^{2}$.

We note that all these assumptions are standard in the bilevel optimization
literature (see, e.g., [13, 11, 6]). Next, we state two lemmas on
characterizing the Lipschitz constants of the hypergradient $\nabla
l_{i}(\mathbf{x}_{i})$ in (IV), the approximate gradient
$\bar{\nabla}f_{i}(\mathbf{x}_{i},\mathbf{y}_{i})$ in (IV), the optimal
solution $\mathbf{y}_{i}^{*}$ of the lower-level problem, and the stochastic
gradient estimator
$\hat{\nabla}f_{i}\left(\mathbf{x}_{i},\mathbf{y}_{i};\bar{\xi}_{i}\right)$ in
(IV). These lemmas will be useful in our main convergence results.

######  Lemma 1 (Ref. [6]).

Under Assumptions 1 and 2, we have

$\displaystyle\|\bar{\nabla}f_{i}(\mathbf{x},\mathbf{y})-\nabla
l_{i}(\mathbf{x})\|\leq
L_{f}\left\|\mathbf{y}^{*}(\mathbf{x})-\mathbf{y}\right\|,$
$\displaystyle\left\|\mathbf{y}_{i}^{*}\left(\mathbf{x}_{1}\right)-\mathbf{y}_{i}^{*}\left(\mathbf{x}_{2}\right)\right\|\leq
L_{y}\left\|\mathbf{x}_{1}-\mathbf{x}_{2}\right\|,$
$\displaystyle\left\|\nabla l_{i}\left(\mathbf{x}_{1}\right)-\nabla
l_{i}\left(\mathbf{x}_{2}\right)\right\|\leq
L_{l}\left\|\mathbf{x}_{1}-\mathbf{x}_{2}\right\|,$

for all $i\in\left\\{1,\ldots,m\right\\}$,
$\mathbf{x},\mathbf{x}_{1},\mathbf{x}_{2}\in\mathbb{R}^{d_{\mathrm{up}}}$ and
$\mathbf{y}\in\mathbb{R}^{d_{\mathrm{low}}}$, where the Lipschitz constants
above are defined as:

$\displaystyle
L_{f}=L_{f_{x}}+\frac{L_{f_{y}}C_{g_{xy}}}{\mu_{g}}+C_{f_{y}}\left(\frac{L_{g_{xy}}}{\mu_{g}}+\frac{L_{g_{yy}}C_{g_{xy}}}{\mu_{g}^{2}}\right),$
$\displaystyle L_{l}=L_{f}+\frac{L_{f}C_{g_{xy}}}{\mu_{g}},\quad\text{ and
}\quad L_{y}=\frac{C_{g_{xy}}}{\mu_{g}}.$

######  Lemma 2 (Ref. [11]).

Under Assumptions 1, 2 and 3, for any
$\left(\mathbf{x}_{1},\mathbf{y}_{1}\right)\text{,
}\left(\mathbf{x}_{2},\mathbf{y}_{2}\right)\in\mathbb{R}^{d_{\mathrm{up}}}\times\mathbb{R}^{d_{\mathrm{low}}}$,
we have

$\mathbb{E}_{\bar{\xi}}\left\|\hat{\nabla}f_{i}\left(\mathbf{x}_{1},\mathbf{y}_{1};\bar{\xi}\right)-\hat{\nabla}f_{i}\left(\mathbf{x}_{2},\mathbf{y}_{2};\bar{\xi}\right)\right\|\\\
\leq
L_{K}(\left\|\mathbf{x}_{1}-\mathbf{x}_{2}\right\|+\left\|\mathbf{y}_{1}-\mathbf{y}_{2}\right\|),$

where $L_{K}=$

$2L_{f_{x}}^{2}+\frac{6C_{g_{xy}}^{2}L_{f_{y}}^{2}K}{2\mu_{g}L_{g}-\mu_{g}^{2}}+\frac{6C_{f_{y}}^{2}L_{g_{xy}}^{2}K}{2\mu_{g}L_{g}-\mu_{g}^{2}}+\frac{6C_{g_{xy}}^{2}C_{f_{y}}^{2}L_{g_{yy}}^{2}K^{3}}{\left(L_{g}-\mu_{g}\right)^{2}\left(2\mu_{g}L_{g}-\mu_{g}^{2}\right)}\text{,}$

and $K$ is the number of samples required to construct the stochastic gradient
estimate in (IV).

The following lemma says that the bias of the stochastic gradient estimator
for the upper-level objective defined in (IV) decays exponentially fast with
respect to the number of samples $K$ that is chosen to approximate the Hessian
inverse.

######  Lemma 3 (Ref. [1]).

Under Assumptions 1–3, for any $i\in\left\\{1,\ldots,m\right\\}$ and
$\left(\mathbf{x},\mathbf{y}\right)\in\mathbb{R}^{d_{\mathrm{up}}}\times\mathbb{R}^{d_{\mathrm{low}}}$,
the bias of the stochastic gradient estimator in (IV) satisfies:

$\|\bar{\nabla}f_{i}(\mathbf{x}_{i},\mathbf{y}_{i})-\mathbb{E}[\hat{\nabla}f_{i}(\mathbf{x}_{i},\mathbf{y}_{i};\bar{\xi}_{i})]\|\leq\frac{C_{g_{xy}}C_{f_{y}}}{\mu_{g}}\left(1-\frac{\mu_{g}}{L_{g}}\right)^{K},$

where $K$ is the number of samples required to construct the stochastic
gradient estimate in (IV).

Now, based on the convergence metric defined in (11), we state the main
convergence result of $\mathsf{DIAMOND}~{}$in Theorem 1:

######  Theorem 1 (Convergence Rate of $\mathsf{DIAMOND}$).

Under Assumptions 1–4, choose
$K=\left(L_{g}/\mu_{g}\right)\log\left(C_{g_{xy}}C_{f_{y}}T/\mu_{g}\right)$.
Define $\alpha_{t}\triangleq\left(\omega+t\right)^{-1/3}$ for $\omega\geq 2$,
$\beta_{t}\triangleq c_{\beta}\alpha_{t}$, $\eta_{t+1}\triangleq
c_{\eta}\alpha_{t}^{2}$, and $\gamma_{t+1}\triangleq
c_{\gamma}\alpha_{t}^{2}$, where

$\displaystyle c_{\beta}=\frac{8L_{f}}{mL_{\mu_{g}}\bar{c}_{y}},\quad
c_{\eta}=\frac{6L_{f}\bar{c}_{\eta}+m}{3L_{f}m\left(1-3\bar{c}_{u}\bar{c}_{\eta}\right)},$
$\displaystyle
c_{\gamma}=\frac{1}{3L_{f}}+8L_{g}^{2}c_{\beta}^{2}+\bar{c}_{r}\left(\frac{2c_{\beta}\bar{c}_{y}}{L_{\mu_{g}}}+\frac{8L_{K}^{2}c_{\beta}^{2}}{\bar{c}_{\eta}}+12L_{K}^{2}\bar{c}_{u}c_{\beta}^{2}\right),$

and where

$\displaystyle\bar{c}_{y}\\!=\\!\min\bigg{\\{}\sqrt{\frac{L_{f}}{2L_{y}^{2}m}},\sqrt{\frac{L_{f}}{10L_{y}^{2}m^{2}}}\bigg{\\}},\,\,\bar{c}_{u}\\!=\\!\min\bigg{\\{}\frac{1}{48L_{K}^{2}},\frac{1}{3\bar{c}_{\eta}}\bigg{\\}},$
$\displaystyle\bar{c}_{\eta}=\max\bigg{\\{}32L_{K}^{2},160L_{K}^{2}m,\frac{24\left(\mu_{g}+L_{g}\right)L_{K}^{2}c_{\beta}}{\bar{c}_{y}}\bigg{\\}},$
$\displaystyle\bar{c}_{\gamma}=\max\bigg{\\{}32L_{g}^{2},160L_{g}^{2}m,\frac{24\left(\mu_{g}+L_{g}\right)L_{g}^{2}c_{\beta}}{\bar{c}_{y}}\bigg{\\}}.$

Let $\mathfrak{B}_{t}\triangleq
l\left(\bar{\mathbf{x}}_{t}\right)+\bar{c}_{y}\left\|\mathbf{y}_{t}-\mathbf{y}_{t}^{*}\right\|^{2}+\bar{c}_{x}\left\|\mathbf{x}_{t}-\mathbf{1}\otimes\bar{\mathbf{x}}_{t}\right\|^{2}+\bar{c}_{u}\left\|\mathbf{u}_{t}-\mathbf{1}\otimes\bar{\mathbf{u}}_{t}\right\|^{2}$
with $\bar{c}_{x}=\frac{6}{(1-\lambda)\alpha_{t}}$,
$\bar{\mathbf{u}}_{t}\triangleq\frac{1}{m}\sum_{i=1}^{m}\mathbf{u}_{i,t}$ and
$\mathbf{u}_{t}\triangleq\left[\mathbf{u}_{1,t}^{\top},\ldots,\mathbf{u}_{m,t}^{\top}\right]^{\top}$.
If $\alpha_{t}\leq\min\\{\sqrt{\frac{m}{2L_{l}^{2}}},$
$\frac{\bar{c}_{u}\left(1-\lambda\right)^{2}}{30},$
$\frac{\bar{c}_{u}(1-\lambda)L_{\mu_{g}}c_{\beta}}{40L_{y}^{2}\bar{c}_{y}},$
$\frac{\bar{c}_{u}(1-\lambda)\bar{c}_{\eta}}{80L_{K}^{2}},$
$\frac{\bar{c}_{u}(1-\lambda)\bar{c}_{\gamma}}{80L_{g}^{2}},$
$\frac{1}{5L_{l}},$ $\frac{1}{3L_{f}},$
$\sqrt{\frac{(1-\lambda)^{2}}{120L_{K}^{2}}},$
$\frac{1-\lambda}{240\bar{c}_{u}L_{K}^{2}m},$
$\frac{\bar{c}_{y}(1-\lambda)}{36\left(\mu_{g}+L_{g}\right)\bar{c}_{u}L_{K}^{2}c_{\beta}},$
$1-\lambda\\}$ and $\beta_{t}\leq\frac{1}{\mu_{g}+L_{g}}$, then the sequence
$\left\\{\mathbf{x}_{t},\mathbf{y}_{t}\right\\}$ generated by Algorithm 1
satisfies:

$\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}\left[\mathfrak{M}_{t}\right]=\mathcal{O}\left(\frac{\mathfrak{B}_{0}-l^{*}}{T^{2/3}}\right)+\mathcal{O}\left(\frac{\log\left(T\right)\sigma_{f}^{2}}{T^{2/3}}\right)\\\
+\mathcal{O}\left(\frac{\log\left(T\right)\sigma_{g}^{2}}{T^{2/3}}\right)=\tilde{\mathcal{O}}\left(\frac{1}{T^{2/3}}\right).$

Theorem 1 indicates that the decreasing step-sizes
$\\{\alpha_{t},\beta_{t}\\}$ depend on the Lipschitz constants, the number of
agents, and the network topology. Note also that the choice of step-size
$\alpha_{t}$ is directly affected by $\lambda$, the second largest eigenvalue
in magnitude of the weight matrix $\mathrm{\mathbf{M}}$. Further, Theorem 1
immediately implies the following sample complexity and communication
complexity of $\mathsf{DIAMOND}$:

######  Corollary 1 (Sample and Communication Complexities of
$\mathsf{DIAMOND}$).

Under the conditions stated in Theorem 1, $\mathsf{DIAMOND}~{}$requires
$\mathcal{O}(\epsilon^{-3/2})$ in sample complexity and communication
complexity to reach an $\epsilon$-stationary point.

###  V-B Proofs of the Main Theoretical Results

Due to space limitation, we provide a proof sketch of Theorem 1, which is
organized into several key steps:

Step 1) Per-iterate descent of the upper-level objective function: We first
bound the per-iterate descent of the upper-level objective function as
follows:

######  Lemma 4.

Under Assumptions 1–2, the following inequality holds for the consecutive
iterates of Algorithm 1:

$\displaystyle\mathbb{E}\left[l\left(\bar{\mathbf{x}}_{t+1}\right)\right.$
$\displaystyle\left.-l\left(\bar{\mathbf{x}}_{t}\right)\right]\leq\mathbb{E}\left[-\frac{\alpha_{t}}{2}\left\|\nabla
l\left(\bar{\mathbf{x}}_{t}\right)\right\|^{2}+\frac{2\alpha_{t}}{m}\sum_{i=1}^{m}\left\|\mathbf{e}_{i,t}^{f}\right\|^{2}\right.$
$\displaystyle\left.-\left(\frac{\alpha_{t}}{2}-\frac{L_{l}\alpha_{t}^{2}}{2}\right)\left\|\bar{\mathbf{u}}_{t}\right\|^{2}+\frac{2L_{l}^{2}\alpha_{t}}{m}\sum_{i=1}^{m}\left\|\bar{\mathbf{x}}_{t}-\mathbf{x}_{i,t}\right\|^{2}\right.$
$\displaystyle\left.+\frac{2L_{f}^{2}\alpha_{t}}{m}\sum_{i=1}^{m}\left\|\mathbf{y}_{i,t}^{*}-\mathbf{y}_{i,t}\right\|^{2}+\frac{2\alpha_{t}}{m}\sum_{i=1}^{m}\left\|\mathbf{b}_{i,t}\right\|^{2}\right],$

for all $t\in\left\\{0,1,\ldots,T-1\right\\}$, where the expectation is taken
over all randomness of the algorithm.

Lemma 4 bounds the expected per-iterate descent of the upper-level objective
value, which depends on i) the consensus error of the upper-level parameters
$\mathbb{E}[\left\|\bar{\mathbf{x}}_{t}-\mathbf{x}_{i,t}\right\|^{2}]$, ii)
the momentum-based gradient estimation error of the upper-level objective
function $\mathbb{E}[\|\mathbf{e}_{i,t}^{f}\|^{2}]$ including the bias
$\|\mathbf{b}_{i,t}\|^{2}$, and iii) the approximation gap of the lower-level
optimal parameter $\mathbb{E}[\|\mathbf{y}_{i,t}^{*}-\mathbf{y}_{i,t}\|^{2}]$,
which will be bounded in Step 2).

Step 2) Error bound on $\mathbf{y}^{*}(\mathbf{x})$: We show that the
approximation error of $\mathbf{y}^{*}(\mathbf{x})$ can be bounded as:

######  Lemma 5.

Under Assumptions 1 and 2, the following approximation gap of
$\mathbf{y}^{*}(\mathbf{x})$ holds for Algorithm 1:

$\displaystyle\mathbb{E}\left[\left\|\mathbf{y}_{i,t+1}-\mathbf{y}_{i,t+1}^{*}\right\|^{2}\right]\leq\mathbb{E}\left[\left(1+\frac{1}{c_{1}}\right)L_{y}^{2}\left\|\mathbf{x}_{i,t+1}-\mathbf{x}_{i,t}\right\|^{2}\right.$
$\displaystyle\left.+\left(1+c_{1}\right)\left(1+c_{0}\right)\left(1-\frac{2\beta_{t}\mu_{g}L_{g}}{\mu_{g}+L_{g}}\right)\left\|\mathbf{y}_{i,t}-\mathbf{y}_{i,t}^{*}\right\|^{2}\right.$
$\displaystyle\left.+\left(1+c_{1}\right)\left(1+c_{0}\right)\left(\beta_{t}^{2}-\frac{2\beta_{t}}{\mu_{g}+L_{g}}\right)\left\|\nabla_{\mathbf{y}}g_{i}\left(\mathbf{x}_{i,t},\mathbf{y}_{i,t}\right)\right\|^{2}\right.$
$\displaystyle\left.+\left(1+c_{1}\right)\left(1+\frac{1}{c_{0}}\right)\beta_{t}^{2}\left\|\mathbf{e}_{i,t}^{g}\right\|^{2}\right],$

for all $i\in\\{1,\ldots,m\\}$ and $t\in\left\\{0,1,\ldots,T-1\right\\}$ with
some positive constants $c_{0},c_{1}>0$, where the expectation is taken over
all randomness of the algorithm.

Lemma 5 indicates that the approximation error $\mathbf{y}^{*}(\mathbf{x})$
shrinks if $(1+c_{1})(1+c_{0})(1-2\beta_{t}\mu_{g}L_{g}/(\mu_{g}+L_{g}))<1$,
and is influenced by the momentum-based stochastic gradient estimation error
of the lower-level objective function
$\mathbb{E}[\|\mathbf{e}_{i,t}^{g}\|^{2}]$. Because of the tightly coupled
structure of the bilevel problem,
$\mathbb{E}[\|\mathbf{y}_{i,t+1}-\mathbf{y}_{i,t+1}^{*}\|^{2}]$ is also
affected by the upper-level parameters
$\mathbb{E}[\|\mathbf{x}_{i,t+1}-\mathbf{x}_{i,t}\|^{2}]$, which is in turn
affected by the consensus error in decentralized optimization.

Step 3) Shrinking rate of $\mathbf{e}_{i,t}^{f}$: Next, we bound the
stochastic gradient estimation error $\mathbf{e}_{i,t}^{f}$ of the upper-level
objective function as follows:

######  Lemma 6.

Under Assumptions 1-4, the stochastic gradient estimation error of the upper-
level objective function $\mathbf{e}_{i,t}^{f}$ satisfies the following
relationship:

$\displaystyle\mathbb{E}[\|\mathbf{e}_{i,t+1}^{f}\|^{2}]\leqslant$
$\displaystyle\mathbb{E}[(1-\eta_{t+1})^{2}\|\mathbf{e}_{i,t}^{f}\|^{2}+2\eta_{t+1}^{2}\sigma_{f}^{2}$
$\displaystyle+4(1-\eta_{t+1})^{2}L_{K}^{2}\|\mathbf{x}_{i,t+1}-\mathbf{x}_{i,t}\|^{2}$
$\displaystyle+8(1-\eta_{t+1})^{2}L_{K}^{2}\beta_{t}^{2}\|\mathbf{e}_{i,t}^{g}\|^{2}$
$\displaystyle+8(1-\eta_{t+1})^{2}L_{K}^{2}\beta_{t}^{2}\|\nabla_{\mathbf{y}}g_{i}(\mathbf{x}_{i,t},\mathbf{y}_{i,t})\|^{2}],$

for all $i\in\\{1,\ldots,m\\}$ and $t\in\\{0,1,\ldots,T-1\\}$, where the
expectation is taken over all randomness of the algorithm.

Lemma 6 indicates that the momentum-based stochastic gradient estimation error
of the upper-level function $\mathbb{E}[\|\mathbf{e}_{i,t+1}^{f}\|^{2}]$ is
affected by the consensus error of the upper-level parameters, which is
contained in
$\mathbb{E}[\left\|\mathbf{x}_{i,t+1}-\mathbf{x}_{i,t}\right\|^{2}]$, the
lower-level momentum-based stochastic gradient estimation error
$\mathbb{E}[\|\mathbf{e}_{i,t}^{g}\|^{2}]$, and the full gradient norm
$\mathbb{E}[\|\nabla_{\mathbf{y}}g_{i}(\mathbf{x}_{i,t},\mathbf{y}_{i,t})\|^{2}]$.

Step 4) Shrinking rate of $\mathbf{e}_{i,t}^{g}$: Next, we bound the
stochastic gradient estimation error $\mathbf{e}_{i,t}^{g}$ of the lower-level
objective function as follows:

######  Lemma 7.

Under Assumptions 1-4, the stochastic gradient estimation error of the lower-
level function satisfies the following relationship:

$\displaystyle\mathbb{E}[\|\mathbf{e}_{i,t+1}^{g}\|^{2}]$
$\displaystyle\leq\mathbb{E}[(1-\gamma_{t+1})^{2}(1+8L_{g}^{2}\beta_{t}^{2})\|\mathbf{e}_{i,t}^{g}\|^{2}$
$\displaystyle+4(1-\gamma_{t+1})^{2}L_{g}^{2}\|\mathbf{x}_{i,t+1}-\mathbf{x}_{i,t}\|^{2}+2r_{t+1}^{2}\sigma_{g}^{2}$
$\displaystyle+8(1-\gamma_{t+1})^{2}L_{g}^{2}\beta_{t}^{2}\|\nabla_{\mathbf{y}}g_{i}(\mathbf{x}_{i,t},\mathbf{y}_{i,t})\|^{2}],$

for all $i\in\\{1,\ldots,m\\}$ and $t\in\\{0,1,\ldots,T-1\\}$, where the
expectation is taken over all randomness of the algorithm.

Lemma 7 shows that, since decentralized bilevel optimization is a composition
of a lower-level problem and an upper-level problem, the momentum-based
stochastic gradient estimation error of the lower-level function
$\mathbb{E}[\|\mathbf{e}_{i,t+1}^{g}\|^{2}]$ is influenced by the consensus
error of the upper-level parameters, which is contained in
$\mathbb{E}[\|\mathbf{x}_{i,t+1}-\mathbf{x}_{i,t}\|^{2}]$.

Step 5) Iterate contractions: Next, we establish the following iterate
contraction results of the $\mathsf{DIAMOND}~{}$algorithm:

######  Lemma 8.

The following contraction properties of the iterates in Algorithm 1 hold:

$\displaystyle\left\|\mathbf{x}_{t+1}-\mathbf{1}\otimes\bar{\mathbf{x}}_{t+1}\right\|^{2}\leq\left(1+c_{2}\right)\lambda^{2}\left\|\mathbf{x}_{t}-\mathbf{1}\otimes\bar{\mathbf{x}}_{t}\right\|^{2}$
$\displaystyle\qquad\qquad\qquad\qquad\qquad+\left(1+\frac{1}{c_{2}}\right)\alpha_{t}^{2}\left\|\mathbf{u}_{t}-\mathbf{1}\otimes\bar{\mathbf{u}}_{t}\right\|^{2},$
$\displaystyle\left\|\mathbf{u}_{t+1}-\mathbf{1}\otimes\bar{\mathbf{u}}_{t+1}\right\|^{2}\leq\left(1+c_{3}\right)\lambda^{2}\left\|\mathbf{u}_{t}-\mathbf{1}\otimes\bar{\mathbf{u}}_{t}\right\|^{2}$
$\displaystyle\qquad\qquad\qquad\qquad\qquad+\left(1+\frac{1}{c_{3}}\right)\left\|\mathbf{p}_{t+1}-\mathbf{p}_{t}\right\|^{2},$

where $c_{2},c_{3}>0$ are constants, and
$\mathbf{p}_{t}\triangleq\left[\mathbf{p}_{1,t}^{\top},\cdots,\mathbf{p}_{m,t}^{\top}\right]^{\top}$.
In addition, we have

$\displaystyle\left\|\mathbf{x}_{t+1}-\mathbf{x}_{t}\right\|^{2}\leqslant
8\left\|\mathbf{x}_{t}-\mathbf{1}\otimes\bar{\mathbf{x}}_{t}\right\|^{2}$
$\displaystyle\qquad\qquad\qquad\quad+4\alpha_{t}^{2}\left\|\mathbf{u}_{t}-\mathbf{1}\otimes\bar{\mathbf{u}}_{t}\right\|^{2}+4\alpha_{t}^{2}m\left\|\bar{\mathbf{u}}_{t}\right\|^{2},$
$\displaystyle\mathbb{E}[\|\mathbf{p}_{t+1}-\mathbf{p}_{t}\|^{2}]\leq\mathbb{E}\left[3\eta_{t+1}^{2}\sum_{i=1}^{m}\|\mathbf{e}_{i,t}^{f}\|^{2}+24L_{K}^{2}m\alpha_{t}^{2}\|\bar{\mathbf{u}}_{t}\|^{2}\right.$
$\displaystyle\left.+12L_{K}^{2}\beta_{t}^{2}\sum_{i=1}^{m}\|\nabla_{\mathbf{y}}g_{i}(\mathbf{x}_{i,t},\mathbf{y}_{i,t})\|^{2}+48L_{K}^{2}\|\mathbf{x}_{t}-\mathbf{1}\otimes\bar{\mathbf{x}}_{t}\|^{2}+\right.$
$\displaystyle\left.24L_{K}^{2}\alpha_{t}^{2}\|\mathbf{u}_{t}\\!-\\!\mathbf{1}\otimes\bar{\mathbf{u}}_{t}\|^{2}\\!+\\!12L_{K}^{2}\beta_{t}^{2}\sum_{i=1}^{m}\|\mathbf{e}_{i,t}^{g}\|^{2}\\!+\\!3\eta_{t+1}^{2}\sigma_{f}^{2}m\right],$

where $\mathbb{E}[\cdot]$ is taken over all randomness of the algorithm.

Note that we only attempt to reach consensus in the upper-level
$\mathbf{x}$-variables. Step 5 quantifies the impacts of the consensus error
in the iterates of the upper-level $\mathbf{x}$-variables, which is important
to analyze the convergence of $\mathsf{DIAMOND}$. Our key idea is to first
define
$\tilde{\mathrm{\mathbf{M}}}=\mathrm{\mathbf{M}}\otimes\mathrm{\mathbf{I}}_{m}$.
Since $\mathbf{x}_{t}-\mathbf{1}\otimes\mathbf{x}_{t}$ is orthogonal to
$\mathbf{1}$, which is the eigenvector corresponding to the largest eigenvalue
of $\tilde{\mathrm{\mathbf{M}}}$, and
$\lambda=\max\left\\{\left|\lambda_{2}\right|,\left|\lambda_{m}\right|\right\\}$,
we have
$\|\tilde{\mathrm{\mathbf{M}}}\mathbf{x}_{t}-\mathbf{1}\otimes\bar{\mathbf{x}}_{t}\|^{2}=\|\tilde{\mathrm{\mathbf{M}}}(\mathbf{x}_{t}-\mathbf{1}\otimes\bar{\mathbf{x}}_{t})\|^{2}\leq\lambda^{2}\|\mathbf{x}_{t}-\mathbf{1}\otimes\bar{\mathbf{x}}_{t}\|^{2}$.

Step 6) Decrement of a constructed potential function: Next, we define a
potential function $W_{t}$ as follows:

$W_{t}=l(\bar{\mathbf{x}}_{t})+\bar{c}_{y}\|\mathbf{y}_{t}-\mathbf{y}_{t}^{*}\|^{2}+\bar{c}_{x}\|\mathbf{x}_{t}-\mathbf{1}\otimes\bar{\mathbf{x}}_{t}\|^{2}\\\
+\bar{c}_{u}\|\mathbf{u}_{t}-\mathbf{1}\otimes\bar{\mathbf{u}}_{t}\|^{2}+\frac{\|\mathbf{e}_{t}^{f}\|^{2}}{\bar{c}_{\eta}\alpha_{t-1}}+\frac{\|\mathbf{e}_{t}^{g}\|^{2}}{\bar{c}_{\gamma}\alpha_{t-1}}.$
(12)

Then, we can show the following decrement results for $\\{W_{t}\\}$:

######  Lemma 9.

Choose $c_{0}=\frac{\beta_{t}L_{\mu_{g}}}{1-2\beta_{t}L_{\mu_{g}}}$,
$c_{1}=\frac{\beta_{t}L_{\mu_{g}}}{2(1-\beta_{t}L_{\mu_{g}})}$ and
$c_{2}=c_{3}=\frac{1}{\lambda}-1$. Under the same conditions as in Theorem 1
and using the results in Lemmas 4–8, the iterates generated by Algorithm 1
satisfy:

$\displaystyle\mathbb{E}\left[W_{t+1}\right.$
$\displaystyle\left.-W_{t}\right]\leq\mathbb{E}\left[-\frac{\alpha_{t}}{2}\left\|\nabla
l\left(\bar{\mathbf{x}}_{t}\right)\right\|^{2}-\frac{2L_{f}^{2}}{m}\alpha_{t}\left\|\mathbf{y}_{t}^{*}-\mathbf{y}_{t}\right\|^{2}\right.$
$\displaystyle\left.-\frac{1}{1-\lambda}\left\|\mathbf{x}_{t}-\mathbf{1}\otimes\bar{\mathbf{x}}_{t}\right\|^{2}+\frac{2\alpha_{t}}{m}\sum_{i=1}^{m}\left\|\mathbf{b}_{i,t}\right\|^{2}\right.$
$\displaystyle\left.+\frac{2m\eta_{t+1}^{2}}{\bar{c}_{\eta}\alpha_{t}}\sigma_{f}^{2}+\frac{2m\gamma_{t+1}^{2}}{\bar{c}_{\gamma}\alpha_{t}}\sigma_{g}^{2}+\frac{3\bar{c}_{u}m\eta_{t+1}^{2}}{\alpha_{t}}\sigma_{f}^{2}\right].$

With the proposed potential function and setting the parameters properly, we
can make the coefficients of
$\mathbb{E}[\|\mathbf{u}_{t}-\mathbf{1}\otimes\bar{\mathbf{u}}_{t}\|^{2}]$,
$\mathbb{E}[\|\bar{\mathbf{u}}_{t}\|^{2}]$,
$\mathbb{E}[\sum_{i=1}^{m}\|\mathbf{e}_{,t}^{f}\|^{2}]$,
$\mathbb{E}[\sum_{i=1}^{m}\|\mathbf{e}_{,t}^{g}\|^{2}]$ and
$\mathbb{E}[\sum_{i=1}^{m}\|\nabla_{\mathbf{y}}g_{i}(\mathbf{x}_{i,t},\mathbf{y}_{i,t})\|^{2}]$
to be non-positive in the range of $\alpha_{t}$ and $\beta_{t}$, which leads
to the stated result in Lemma 9.

Step 7) Proof of Theorem 1: Note that
$\sum_{t=0}^{T-1}\alpha_{t}^{3}\leq\log\left(T+1\right)$ with $\omega\geq 1$.
Telescoping the result in Lemma 9 from $0$ to $T-1$, and multiplying by
$2/\alpha_{T}$ on both sides yields:

$\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}\left[\mathfrak{M}_{t}\right]\leqslant{\left[\frac{2\left(\mathfrak{B}_{0}-l^{*}\right)}{\alpha_{T}T}+\frac{4}{m\alpha_{T}T}\sum_{t=0}^{T-1}\alpha_{t}E\left[\sum_{i=1}^{m}\left\|\mathbf{b}_{i,t}\right\|^{2}\right]\right.}$
$\displaystyle+\frac{4c_{\eta}^{2}m\sigma_{f}^{2}}{\bar{c}_{\eta}}\frac{\log(T+1)}{\alpha_{T}T}+\frac{4c_{\gamma}^{2}m\sigma_{g}^{2}}{\bar{c}_{\gamma}}\frac{\log(T+1)}{\alpha_{T}T}+\frac{2\sigma_{f}^{2}}{\bar{c}_{\eta}\alpha_{-1}\alpha_{T}T}$
$\displaystyle\left.+6\bar{c}_{u}c_{\eta}^{2}m\sigma_{f}^{2}\frac{\log(T+1)}{\alpha_{T}T}+\frac{2\sigma_{g}^{2}}{\bar{c}_{\gamma}\alpha_{-1}\alpha_{T}T}\right]/\min\left\\{\frac{4L_{f}^{2}}{m},\frac{2}{1-\lambda}\right\\}.$

Using the fact that $\left\|\mathbf{b}_{i,t}\right\|=1/T$ when
$K=\left(\mu_{g}/L_{g}\right)\log\left(C_{g_{xy}}C_{f_{y}}T/\mu_{g}\right)$,
we have:

$\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}\left[\mathfrak{M}_{t}\right]=\mathcal{O}\left(\frac{\mathfrak{B}_{0}-l^{*}}{T^{2/3}}\right)+\widetilde{\mathcal{O}}\left(\frac{\sigma_{f}^{2}}{T^{2/3}}\right)+\widetilde{\mathcal{O}}\left(\frac{\sigma_{9}^{2}}{T^{2/3}}\right),$

where $\mathfrak{B}_{t}\triangleq
l(\bar{\mathbf{x}}_{t})+\bar{c}_{y}\|\mathbf{y}_{t}-\mathbf{y}_{t}^{*}\|^{2}+\bar{c}_{x}\|\mathbf{x}_{t}-\mathbf{1}\otimes\bar{\mathbf{x}}_{t}\|^{2}+\bar{c}_{u}\|\mathbf{u}_{t}-\mathbf{1}\otimes\bar{\mathbf{u}}_{t}\|^{2}$.
This completes the proof of Theorem 1.

##  VI Numerical Results

(a) MNIST dataset.

(b) CIFAR-10 dataset.

Figure 1: Convergence performance on the meta-learning problem with 9-agent
network.

(c) MNIST dataset.

(d) CIFAR-10 dataset.

Figure 2: Convergence performance on the meta-learning problem with 15-agent
network.

(a) 9-agent network.

(b) 15-agent network.

Figure 3: Convergence performance with different edge connectivity
probabilities $p_{c}$ on the meta-learning problem.

Figure 4: Comparison between D-SGD and $\mathsf{DIAMOND}~{}$on the hyper-
parameter optimization problem.

In this section, we conduct numerical experiments to verify the theoretical
results of the proposed $\mathsf{DIAMOND}~{}$algorithm using decentralized
meta-learning problems and hyper-parameter optimization problems.

1) Decentralized Meta-Learning: The formulation of the decentralized meta-
learning problem is the same as (I), where $\mathbf{x}$ is the common
parameters across all agents and $\mathbf{y}_{i}$ is the task-specific
parameters of $\mathcal{T}_{i}$. The upper-level optimization objective
function $f_{i}(\mathbf{x},\mathbf{y}_{i}^{*}(\mathbf{x}))$ is the loss
function related to task $\mathcal{T}_{i}$ and is non-convex in $\mathbf{x}$.
The lower-level optimization objective function
$g_{i}(\mathbf{x},\mathbf{y}_{i})$ satisfies the strongly convex requirements
in $\mathbf{y}_{i}$ by using a strongly convex regularizor
$\mathcal{R}(\mathbf{y}_{i})=\frac{1}{2}\|\mathbf{y}_{i}\|_{2}^{2}$. The
decentralized meta-learning problem aims to learn the common parameters that
can be adapted to specific tasks. The classifier is based on a two-hidden-
layer fully connected neural network for the decentralized meta-learning
problem. The network topology is generated based on Erdös-Rényi random graph
by NetworkX [40]. We choose the consensus matrix as
$\mathbf{M}=\mathbf{I}-\frac{2\mathbf{V}}{3\rho_{\max}(\mathbf{V})}$, where
$\mathbf{V}$ is the Laplacian matrix and $\rho_{\max}$ is the largest
eigenvalue of $\mathbf{V}$.

1-a) Comparison between Decentralized Stochastic Algorithms: We conduct
decentralized meta-learning on MNIST [41] and CIFAR-10 [42] datasets with 9-
and 15-agent networks. The edge connectivity probability is $p_{c}=0.3$. We
compare the proposed $\mathsf{DIAMOND}~{}$algorithm with three decentralized
stochastic bilevel optimization methods:

  * •

Decentralized Stochastic Gradient Descent (D-SGD)[14]: Each agent directly
updates its local copy of the upper-level parameters $\mathbf{x}_{i,t}$ with
the stochastic gradient of the upper-level objective function, i.e.,
$\mathbf{x}_{i,t}=\sum_{j\in\mathcal{N}_{i}}[\mathbf{M}]_{ij}\mathbf{x}_{j,t-1}-\alpha_{t}\hat{\nabla}f_{i}\left(\mathbf{x}_{i,t},\mathbf{y}_{i,t};\bar{\xi}_{i,t}\right)$
and
$\mathbf{y}_{i,t}=\mathbf{y}_{i,t-1}-\beta_{t}\nabla_{\mathbf{y}}g_{i}\left(\mathbf{x}_{i,t},\mathbf{y}_{i,t};\zeta_{i,t}\right)$.

  * •

Gradient-Tracking Stochastic Gradient Descent (GT-SGD): In addition to the
DSGD update, GT-SGD performs gradient tracking over
$\mathbf{x}_{i,t}$-variables. Specifically, GT-SGD updates the upper-level
variables as:
$\mathbf{x}_{i,t+1}\\!=\\!\sum_{j\in\mathcal{N}_{i}}[\mathbf{M}]_{ij}\mathbf{x}_{j,t}\\!-\\!\alpha_{t}\mathbf{u}_{i,t}$,
where
$\mathbf{u}_{i,t}\\!=\\!\sum_{j\in\mathcal{N}_{i}}[\mathbf{M}]_{ij}\mathbf{u}_{j,t-1}\\!+\\!\hat{\nabla}f_{i}(\mathbf{x}_{i,t},\mathbf{y}_{i,t};\bar{\xi}_{i,t})\\!-\\!\hat{\nabla}f_{i}(\mathbf{x}_{i,t-1},\mathbf{y}_{i,t-1};\bar{\xi}_{i,t-1})$.

  * •

Momentum Stochastic Gradient Descent (M-SGD): This algorithm can be viewed as
a simplified version of $\mathsf{DIAMOND}~{}$by neglecting gradient tracking.
Specifically, we replace the update step (9) by
$\mathbf{x}_{i,t+1}=\sum_{j\in\mathcal{N}_{i}}[\mathrm{\mathbf{M}}]_{ij}\mathbf{x}_{j,t}-\alpha_{t}\mathbf{p}_{i,t}$.

We set the learning rates $\alpha_{t}\\!=\\!c_{\alpha}(\omega\\!+\\!t)^{-1/3}$
and $\beta_{t}\\!=\\!c_{\beta}\alpha_{t}$ following Theorem 1, where
$c_{\alpha}\\!=\\!10$, $\omega\\!=\\!2$ and $c_{\beta}\\!=\\!10$. The momentum
coefficients are chosen as $\eta_{t+1}\\!=\\!c_{\eta}\alpha_{t}^{2}$ and
$\gamma_{t+1}\\!=\\!c_{\gamma}\alpha_{t}^{2}$ for M-SGD and
$\mathsf{DIAMOND}$, respectively, where $c_{\eta}\\!=\\!c_{\gamma}\\!=\\!0.1$.
Figs. 2 and 2 illustrate that the $\mathsf{DIAMOND}~{}$algorithm outperforms
other algorithms for solving decentralized bilevel optimization problems in
terms of the convergence metric in both 9-agent and 15-agent networks, which
implies lower sample and communication complexity.

1-b) Impact of connectivity probability: We evaluate the impact of edge
connection probability $p_{c}$ on the performance of $\mathsf{DIAMOND}~{}$with
the nine-agent network. We choose $p_{c}$ from $\\{0.3,0.5,0.8\\}$, and the
parameters of learning rate and momentum coefficient are the same as those in
the previous setting. As shown in Fig. 4, there is only a slight increase in
convergence rate with a higher $p_{c}$-value, which reflects that the
performance of $\mathsf{DIAMOND}~{}$is not sensitive to the edge connection
probability, and the proposed $\mathsf{DIAMOND}~{}$algorithm can adapt to
various network settings.

2) Hyper-parameter optimization. Next, we compare $\mathsf{DIAMOND}~{}$with
D-SGD using the logistic regression problem [43, 7] with the same formulation
as in (I), where
$f_{i}(\mathbf{x},\mathbf{y}_{i}^{*}(\mathbf{x}))\\!=\\!\frac{1}{|\mathcal{D}_{\text{val},i}|}\sum_{(\mathbf{a}_{j},\mathbf{c}_{j})\in\mathcal{D}_{\text{val},i}}Q(\mathbf{a}_{j}^{T}\mathbf{y}_{i}^{*},\mathbf{c}_{j})$,
$g_{i}(\mathbf{x},\mathbf{y}_{i})\\!=\\!\frac{1}{|\mathcal{D}_{\text{tr},i}|}\sum_{(\mathbf{a}_{j},\mathbf{c}_{j})\in\mathcal{D}_{\text{tr},i}}Q(\mathbf{a}_{j}^{T}\mathbf{y}_{i},\mathbf{c}_{j})\\!+\\!\frac{1}{qp}\sum_{k=1}^{q}$
$\sum_{r=1}^{p}\exp(\mathbf{x}_{r})\mathbf{y}_{irk}^{2}$. Here,
$\mathcal{D}_{\text{tr},i}$ and $\mathcal{D}_{\text{val},i}$ are the training
and validation datasets for agent $i$, respectively, $Q$ is the cross-entropy
loss, $q$ is the number of classes, and $p$ is the number of features. We use
the a9a dataset [44], where $q\\!=\\!2$ and $p\\!=\\!123$, and divide the a9a
dataset into training, validation, and testing sets, which contain 40%, 40%,
and 20% samples, respectively.

We compare the proposed $\mathsf{DIAMOND}~{}$algorithm with D-SGD in terms of
test accuracy and test error, using five-agent communication networks. For
both $\mathsf{DIAMOND}~{}$and D-SGD, the learning rates are set as
$\alpha_{t}\\!=\\!c_{\alpha}{(\omega\\!+\\!t)}^{-1/3}$ and
$\beta_{t}\\!=\\!c_{\beta}\alpha_{t}$, where $c_{\alpha}\\!=\\!5$,
$\omega\\!=\\!2$, and $c_{\beta}\\!=\\!1.5$. Moreover, the momentum related
parameters in $\mathsf{DIAMOND}~{}$are chosen as
$\eta_{t+1}\\!=\\!c_{\eta}\alpha_{t}^{2}$ and
$\gamma_{t+1}\\!=\\!c_{\gamma}\alpha_{t}^{2}$, where
$c_{\eta}\\!=\\!c_{\gamma}\\!=\\!0.1$. As shown in Fig. 4,
$\mathsf{DIAMOND}~{}$has a faster convergence rate than that of D-SGD over
various networks with different edge connection probabilities. This validates
the superiority of the proposed $\mathsf{DIAMOND}~{}$algorithm.

##  VII Conclusion

In this paper, we proposed the $\mathsf{DIAMOND}~{}$algorithm for
decentralized bilevel optimization with non-convex upper-level subproblems and
strongly-convex lower-level subproblems. $\mathsf{DIAMOND}~{}$utilizes a
network-consensus approach and adopts a single-loop algorithmic architecture
along with momentum-based stochastic gradient estimations and gradient
tracking techniques. This is contrast to existing related works that use a
double-loop architecture, full gradient estimations, or large-batch gradients.
We showed that $\mathsf{DIAMOND}~{}$achieves
$\mathcal{O}\left(\epsilon^{-3/2}\right)$ in both sample and communication
complexities to reach an $\epsilon$-stationary point, outperforming existing
works. We also conducted numerical experiments using meta-learning and hyper-
parameter optimization problems to verify our theoretical findings. Future
directions include i) to consider Hessian approximation to further reduce
computation costs of the Hessian matrix and ii) to extend the proposed
algorithm to wireless networks with channel noise and fading.

## References

  * [1] M. Hong, H.-T. Wai, Z. Wang, and Z. Yang, “A two-timescale framework for bilevel optimization: Complexity analysis and application to actor-critic,” _arXiv preprint arXiv:2007.05170_ , 2020.
  * [2] H. Zhang, W. Chen, Z. Huang, M. Li, Y. Yang, W. Zhang, and J. Wang, “Bi-level actor-critic for multi-agent coordination,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 34, no. 05, 2020, pp. 7325–7332.
  * [3] Y. Liu and R. Liu, “Boml: A modularized bilevel optimization library in python for meta learning,” in _2021 IEEE International Conference on Multimedia & Expo Workshops (ICMEW)_. IEEE, 2021, pp. 1–2.
  * [4] A. Rajeswaran, C. Finn, S. M. Kakade, and S. Levine, “Meta-learning with implicit gradients,” _Advances in neural information processing systems_ , vol. 32, 2019.
  * [5] S. Dempe, _Foundations of bilevel programming_. Springer Science & Business Media, 2002.
  * [6] S. Ghadimi and M. Wang, “Approximation methods for bilevel programming,” _arXiv preprint arXiv:1802.02246_ , 2018.
  * [7] K. Ji, J. Yang, and Y. Liang, “Bilevel optimization: Convergence analysis and enhanced design,” in _International Conference on Machine Learning_. PMLR, 2021, pp. 4882–4892.
  * [8] J. Yang, K. Ji, and Y. Liang, “Provably faster algorithms for bilevel optimization,” _Advances in Neural Information Processing Systems_ , vol. 34, pp. 13 670–13 682, 2021.
  * [9] T. Chen, Y. Sun, and W. Yin, “A single-timescale stochastic bilevel optimization method,” _arXiv preprint arXiv:2102.04671_ , 2021.
  * [10] Z. Guo and T. Yang, “Randomized stochastic variance-reduced methods for stochastic bilevel optimization,” _arXiv preprint arXiv:2105.02266_ , 2021\.
  * [11] P. Khanduri, S. Zeng, M. Hong, H.-T. Wai, Z. Wang, and Z. Yang, “A near-optimal algorithm for stochastic bilevel optimization via double-momentum,” _Advances in Neural Information Processing Systems_ , vol. 34, pp. 30 271–30 283, 2021.
  * [12] X. Zhang, J. Liu, Z. Zhu, and E. S. Bentley, “Low sample and communication complexities in decentralized learning: A triple hybrid approach,” in _IEEE INFOCOM 2021-IEEE Conference on Computer Communications_. IEEE, 2021, pp. 1–10.
  * [13] Z. Liu, X. Zhang, P. Khanduri, S. Lu, and J. Liu, “Interact: Achieving low sample and communication complexities in decentralized bilevel learning over networks,” _arXiv preprint arXiv:2207.13283_ , 2022.
  * [14] A. Nedic and A. Ozdaglar, “Distributed subgradient methods for multi-agent optimization,” _IEEE Transactions on Automatic Control_ , vol. 54, no. 1, pp. 48–61, 2009.
  * [15] A. Nedic, A. Ozdaglar, and P. A. Parrilo, “Constrained consensus and optimization in multi-agent networks,” _IEEE Transactions on Automatic Control_ , vol. 55, no. 4, pp. 922–938, 2010.
  * [16] J. Bracken and J. T. McGill, “Mathematical programs with optimization problems in the constraints,” _Operations Research_ , vol. 21, no. 1, pp. 37–44, 1973\.
  * [17] C. Shi, J. Lu, and G. Zhang, “An extended kuhn–tucker approach for linear bilevel programming,” _Applied Mathematics and Computation_ , vol. 162, no. 1, pp. 51–63, 2005.
  * [18] A. Mehra and J. Hamm, “Penalty method for inversion-free deep bilevel optimization,” in _Asian Conference on Machine Learning_. PMLR, 2021, pp. 347–362.
  * [19] B. Colson, P. Marcotte, and G. Savard, “An overview of bilevel optimization,” _Annals of operations research_ , vol. 153, no. 1, pp. 235–256, 2007.
  * [20] G. Kunapuli, K. P. Bennett, J. Hu, and J.-S. Pang, “Classification model selection via bilevel programming,” _Optimization Methods & Software_, vol. 23, no. 4, pp. 475–489, 2008.
  * [21] K. Ji and Y. Liang, “Lower bounds and accelerated algorithms for bilevel optimization,” _arXiv preprint arXiv:2102.03926_ , 2021.
  * [22] A. Shaban, C.-A. Cheng, N. Hatch, and B. Boots, “Truncated back-propagation for bilevel optimization,” in _The 22nd International Conference on Artificial Intelligence and Statistics_. PMLR, 2019, pp. 1723–1732.
  * [23] S. Gould, B. Fernando, A. Cherian, P. Anderson, R. S. Cruz, and E. Guo, “On differentiating parameterized argmin and argmax problems with application to bi-level optimization,” _arXiv preprint arXiv:1607.05447_ , 2016.
  * [24] F. Pedregosa, “Hyperparameter optimization with approximate gradient,” in _International conference on machine learning_. PMLR, 2016, pp. 737–746.
  * [25] J. N. Tsitsiklis, “Problems in decentralized decision making and computation.” Massachusetts Inst of Tech Cambridge Lab for Information and Decision Systems, Tech. Rep., 1984.
  * [26] Z. Jiang, K. Mukherjee, and S. Sarkar, “On consensus-disagreement tradeoff in distributed optimization,” in _2018 Annual American Control Conference (ACC)_. IEEE, 2018, pp. 571–576.
  * [27] D. S. Callaway and I. A. Hiskens, “Achieving controllability of electric loads,” _Proceedings of the IEEE_ , vol. 99, no. 1, pp. 184–199, 2010.
  * [28] J. Kober, J. A. Bagnell, and J. Peters, “Reinforcement learning in robotics: A survey,” _The International Journal of Robotics Research_ , vol. 32, no. 11, pp. 1238–1274, 2013.
  * [29] X. Lian, C. Zhang, H. Zhang, C.-J. Hsieh, W. Zhang, and J. Liu, “Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent,” _Advances in Neural Information Processing Systems_ , vol. 30, 2017.
  * [30] X. Zhang, J. Liu, Z. Zhu, and E. S. Bentley, “Compressed distributed gradient descent: Communication-efficient consensus over networks,” in _IEEE INFOCOM 2019-IEEE Conference on Computer Communications_. IEEE, 2019, pp. 2431–2439.
  * [31] H. Yu, R. Jin, and S. Yang, “On the linear speedup analysis of communication efficient momentum sgd for distributed non-convex optimization,” in _International Conference on Machine Learning_. PMLR, 2019, pp. 7184–7193.
  * [32] S. Lu, X. Zhang, H. Sun, and M. Hong, “Gnsd: A gradient-tracking based nonconvex stochastic algorithm for decentralized optimization,” in _2019 IEEE Data Science Workshop (DSW)_. IEEE, 2019, pp. 315–321.
  * [33] S. Pu and A. Nedić, “Distributed stochastic gradient tracking methods,” _Mathematical Programming_ , vol. 187, no. 1, pp. 409–457, 2021.
  * [34] R. Xin, U. Khan, and S. Kar, “A hybrid variance-reduced method for decentralized stochastic non-convex optimization,” in _International Conference on Machine Learning_. PMLR, 2021, pp. 11 459–11 469.
  * [35] P. Khanduri, P. Sharma, H. Yang, M. Hong, J. Liu, K. Rajawat, and P. Varshney, “Stem: A stochastic two-sided momentum algorithm achieving near-optimal sample and communication complexities for federated learning,” _Advances in Neural Information Processing Systems_ , vol. 34, pp. 6050–6061, 2021.
  * [36] L. Franceschi, P. Frasconi, S. Salzo, R. Grazzi, and M. Pontil, “Bilevel programming for hyperparameter optimization and meta-learning,” in _International Conference on Machine Learning_. PMLR, 2018, pp. 1568–1577.
  * [37] K. Zhang, Z. Yang, H. Liu, T. Zhang, and T. Basar, “Fully decentralized multi-agent reinforcement learning with networked agents,” in _International Conference on Machine Learning_. PMLR, 2018, pp. 5872–5881.
  * [38] A. Cutkosky and F. Orabona, “Momentum-based variance reduction in non-convex sgd,” _Advances in neural information processing systems_ , vol. 32, 2019\.
  * [39] Q. Tran-Dinh, N. H. Pham, D. T. Phan, and L. M. Nguyen, “Hybrid stochastic gradient descent algorithms for stochastic nonconvex optimization,” _arXiv preprint arXiv:1905.05920_ , 2019.
  * [40] A. Hagberg, P. Swart, and D. S Chult, “Exploring network structure, dynamics, and function using networkx,” Los Alamos National Lab (LANL), Los Alamos, NM (United States), Tech. Rep., 2008.
  * [41] Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner, “Gradient-based learning applied to document recognition,” _Proceedings of the IEEE_ , vol. 86, no. 11, pp. 2278–2324, 1998.
  * [42] A. Krizhevsky, G. Hinton _et al._ , “Learning multiple layers of features from tiny images,” 2009.
  * [43] R. Grazzi, L. Franceschi, M. Pontil, and S. Salzo, “On the iteration complexity of hypergradient computation,” in _International Conference on Machine Learning_. PMLR, 2020, pp. 3748–3758.
  * [44] D. Dheeru and E. K. Taniskidou. (2017) UCI machine learning repository. [Online]. Available: https://archive.ics.uci.edu/ml


2016 XV Latin American Regional IAU Meeting LARIM Data Repository Open Data
Data preservation

# LAGO distributed network of data repositories

H. Asorey11affiliation: Laboratorio Detección de Partículas y Radiación,
Centro Atómico Bariloche & Instituto Balseiro, Bariloche, Argentina A.
Martínez-Méndez22affiliation: Escuela de Ingeniería de Sistemas, Universidad
Industrial de Santander, Bucaramanga, Colombia. L.A. Núñez33affiliation:
Escuela de Física, Universidad Industrial de Santander, Bucaramanga, Colombia.
44affiliation: Departamento de Física, Universidad de Los Andes, Mérida,
Venezuela. and A. Valbuena-Delgado33affiliationmark:  for the LAGO
Collaboration55affiliation: The Latin American Giant Observatory (LAGO),
http://lagoproject.org, see the full list of members and institutions at
http://lagoproject.org/collab.html

We describe a set of tools, services and strategies of the Latin American
Giant Observatory (LAGO) data repository network, to implement Data
Accessibility, Reproducibility and Trustworthiness.

The Latin American Giant Observatory, (LAGO), is an extended continental
astroparticle observatory oriented to basic research on: the Extreme Universe,
Space Weather, and Atmospheric Radiation, with singles and small arrays
particle detectors, covering a huge range of geomagnetic rigidity cutoffs and
atmospheric absorption/reaction levels (Asorey et al., 2016).

Unlike other instruments where data flows from only one place to a network of
data repositories, in LAGO each site preserves, catalogs and generates data
locally which, referrers not only to raw data but also to data produced during
the analysis and/or simulation of cosmic rays phenomena. Dspace provides basic
functionality for storing and retrieving of digital content with a
straightforward adaptability for non-native types of contents and metadata
schemes, supporting two interoperability protocols: OAI-PMH (Open Archive
Initiatives Protocol for Metadata Harvesting) and SWORD (Simple Webservice
Offering Repository Deposit)(Smith et al., 2003; Lewis et al., 2012). We have
overcome one of the most important DSpace limitations: its inability to
upload/download multiple records, developing a script to ingest data profiting
from the some DSpace capabilities(Asorey et al., 2015). This data repository
network will also be useful for the solar physics and space climatology
communities.

Figure 1: Continental LAGO data repository network.

The Data Accessibility, Reproducibility and Trustworthiness (DART) initiative
was launched by CHAIN-REDS (Coordination and Harmonisation of Advanced
e-infrastructure for Research and Education Data Sharing), an European
Commission co-funded project focused on promoting and supporting technological
and scientific collaboration across different communities in various
continents. GRNET PID (European Persistent Identifiers Consortium) service
enables the allocation, management and resolution of PIDs and has been
employed to ensure the data persistence and reproducibility of the
experiments. Part identifiers can compute an unlimited number of handles on
the fly, without requiring registering each separately. (Barbera et al.,
2014).

This project has been partially funded by VIE Universidad Industrial de
Santander.

## References

  * Asorey et al. [2015] Asorey, H., Cazar-Ramírez, D., Mayo-García, R., Núñez, L., Rodríguez-Pascual, M., Torres-Niño, L., & the LAGO Collaboration. 2015, in The 34th International Cosmic Ray Conference, Vol. PoS(ICRC2015), 672
  * Asorey et al. [2016] Asorey, H., Núñez, L., Suárez-Durán, M., Torres-Niño, L., Rodríguez-Pascual, M., Rubio-Montero, A., & Mayo-García, R. 2016, in Cluster, Cloud and Grid Computing (CCGrid), 2016 16th IEEE/ACM International Symposium on, IEEE, 707–711
  * Barbera et al. [2014] Barbera, R., Becker, B., Carrubba, C., Inserra, G., Jalife-Villalón, S., Kanellopoulos, C., Koumantaros, K., Mayo-García, R., Núñez, L., Prnjate, O., Ricceri, R., Rodríguez-Pascual, M., Rubio-Montero, A., Ruggieri, F., & Project, C.-R. 2014, in ANAIS DAS SESSÕES TEMÁTICAS E PÔSTERS, 166
  * Lewis et al. [2012] Lewis, S., de Castro, P., & Jones, R. 2012, D-Lib Magazine, 18
  * Smith et al. [2003] Smith, M., Barton, M., Bass, M., Branschofsky, M., McClellan, G., Stuve, D., Tansley, R., & Walker, J. H. 2003, D-lib magazine, 9