# Novel Chapter Abstractive Summarization using Spinal Tree Aware Sub-
Sentential Content Selection

Hardy* Miguel Ballesteros Faisal Ladhak* Muhammad Khalifa*
Vittorio Castelli Kathleen McKeown

###### Abstract

††*Work done while at Amazon AWS AI Labs

Summarizing novel chapters is a difficult task due to the input length and the
fact that sentences that appear in the desired summaries draw content from
multiple places throughout the chapter. We present a pipelined extractive-
abstractive approach where the extractive step filters the content that is
passed to the abstractive component. Extremely lengthy input also results in a
highly skewed dataset towards negative instances for extractive summarization;
we thus adopt a margin ranking loss for extraction to encourage separation
between positive and negative examples. Our extraction component operates at
the constituent level; our approach to this problem enriches the text with
spinal tree information which provides syntactic context (in the form of
constituents) to the extraction model. We show an improvement of 3.71 Rouge-1
points over best results reported in prior work on an existing novel chapter
dataset.

##  1 Introduction

Research on summarizing novels (Mihalcea and Ceylan, 2007; Wu et al., 2017;
Ladhak et al., 2020; Kryściński et al., 2021; Wu et al., 2021) has recently
gained popularity following advancements in sequence-to-sequence pre-trained
models (Zhang et al., 2019a; Lewis et al., 2019; Raffel et al., 2019) and in
summarization of newswire datasets (Narayan et al., 2018; Hermann et al.,
2015; Grusky et al., 2018). Novel chapters present challenges not commonly
encountered when summarizing news articles. Phrases from multiple, non-
contiguous sentences within the chapter are often fused to form new sentences
for the summary. One would be inclined to use an abstractive approach, but the
length of chapters (on average, seven times longer than news articles (Ladhak
et al., 2020)) makes it unfeasible to use state of the art generative models,
such as BART (Lewis et al., 2019) and even Longformer (Beltagy et al., 2020).
Chapter length causes the additional problem of an imbalanced dataset, as a
much higher percentage of the input will not be selected for the summary than
is typical in domains such as news.

To address these challenges, we adopt an extractive-abstractive architecture,
where content is first selected by extracting units from the input and then an
abstractive model is used on the filtered input to produce fluent text.
Kryściński et al. (2021) benchmarked the extractive-abstractive architecture,
first proposed by Chen and Bansal (2018), for novel summarization, but did not
extend it. In this work, we propose several novel extensions to improve its
performance on the novel chapter summarization task.

First, we address the issue of imbalanced dataset where the large amount of
compression in novel chapter summarization (372 summary words per 5,165
chapter words on average) creates an extreme imbalance in the training data; a
successful extractive summarization algorithm would have to discard most of
the text. The standard practice of using Cross-Entropy loss (Good, 1992) when
training a neural network model backfires in our case: a network that opts to
discard everything will achieve near-perfect performance. We alleviate the
issue by improving the margin structure of the minority class boundary using
the Margin Ranking loss (Rosasco et al., 2004), which encourages separation
between the two classes. Other studies, such as Cruz et al. (2016), also shows
that a pairwise ranking improves model performances on imbalanced data.

Second, in order to model the fusion of chapter phrases into summary
sentences, we carry out extraction at the constituent level. Ladhak et al.
(2020) also tried this approach, but with mixed results. They noted that
sometimes the sub-sentential unit can be too small and, therefore, lack
meaningful content (e.g., phrases such as “what has?” in the extractive
summary, Table 1). These small unintelligible pieces can negatively affect the
performance of the extractive model and, more importantly, the subsequent
abstractive model. We hypothesize that we can improve the performance of the
extractive model—and, consequently, that of the downstream abstractive
model—by augmenting the meaning of the extracted sub-sentential units using
additional information from the sentence. To that end, we propose an
enrichment process, during model training, where we augment the sub-sentential
units with linguistic information. For this purpose, we use a spinal tree
(Carreras et al., 2008; Ballesteros and Carreras, 2015) which carries
information about both the dependency and the constituent structure of the
segment. We encode the spine’s information using a recurrent network and
concatenate its output to the embedding of the token, as illustrated in Figure
1. We choose spinal tree since it

Figure 1: The encoding part of the model for spinal tree encoding. Each token
is represented by its corresponding spine from the spinal tree and is encoded
by bidirectional-GRU networks (Cho et al., 2014) before being concatenated
with its token embedding. We don’t show the CLS and SEP tokens here for space-
saving purposes, but they are treated as in BertSumm (Liu and Lapata, 2019).

Our contributions are threefold: (1) we adopt an extractive-abstractive
architecture, improving the decision boundary of the content selection by
using a Margin Ranking loss, (2) we perform extraction at the constituent
level, introducing an enrichment process that uses spinal tree information and
(3) we show that our approach improves over the state-of-the-art with a 3.71
gain in Rouge-1 points.

Extracts from our best performance Extractive Model
---
tess went down the hill to trantridge cross , and inattentively waited to take
her seat in the van returning from chaseborough to shaston .<q>her mother had
advised her to stay here for the night , at the house of a cottage-
woman<q>what has ? ”<q>“ they say – mrs d’urberville says –<q>that she wants
you to look after a little fowl-farm which is her hobby .<q>cried joan to her
husband .
Abstracts from our best performance Abstractive Model
tess goes down the hill to trantridge cross and waits to take her seat in the
van returning from chaseborough to shaston . her mother has advised her to
stay for the night at the house of a cottage-woman who has a fowl-farm . joan
tells her husband that mrs. d’urberville has written a letter asking her
daughter to look after her poultry-farm
Reference
when tess returns home the following day. a letter from mrs. d’urberville
offering her a job tending fowl awaits her . despite her mother ’s ecstatic
eagerness , tess is displeased and looks instead for local jobs to earn money
to replace the family ’s horse .alec d’urberville stops by and prompts her
mother for an answer about the job . her efforts to find alternative work
prove fruitless and so tess accepts d’urberville ’s offer . she remarks that
mrs. d’urberville ’s handwriting looks masculine .
Table 1: The outputs from two different models. The extract is obtained
through a content selection model while the abstract is obtained by passing
the extract into BART (Lewis et al., 2019) language generation model. The <q>
tokens in the extract are the delimiters for constituents.

##  2 Related Work

Several previous works on novel chapter summarization, such as Mihalcea and
Ceylan (2007), Wu et al. (2017), Ladhak et al. (2020), Kryściński et al.
(2021) and Wu et al. (2021), are closely related to ours. Mihalcea and Ceylan
(2007) uses MEAD, an unsupervised extractive summarization described in Radev
et al. (2004); this approach includes features focusing on terms weighting
that take into account the different topics in the text. In this work, topic
boundaries are determined using a graph-based segmentation algorithm that uses
normalized cuts (Malioutov, 2006). A similar line of work, including Mihalcea
and Ceylan (2007) and Wu et al. (2017), also performs topic modelling with
Latent Dirichlet Allocation (Blei et al., 2003) followed by greedy
unsupervised extraction.

Conversely, Ladhak et al. (2020) experiment with extracting information at the
sentence and at the syntactic constituent level, via a supervised learning
approach. To train their model, they use an aligning process based on the
weighted ROUGE scores between the reference and novel text to assign proxy
extract labels, in the absence of manually annotated ground truth. Their
results at the constituent level are mixed; human evaluation shows a lower
performance of constituent extraction models presumably because the summaries
are not very readable. Kryściński et al. (2021) construct a novel chapter
dataset that is slightly larger than that of Ladhak et al. (2020) and
benchmark existing summarization algorithms on the dataset.

Wu et al. (2021), on the other hand, use a human-in-the-loop approach to
obtain summaries via behaviour cloning and reward modelling.

##  3 Novel Chapter Summarization

We use a two-step process where we first run an _extractive_ model (Mihalcea
and Ceylan, 2007; Wu et al., 2017; Ladhak et al., 2020) to select informative
content and then run a separate _abstractive_ model (Lewis et al., 2019; Zhang
et al., 2019a; Raffel et al., 2019) to produce a coherent and readable version
of this content.

###  3.1 Dataset and Pre-processing

For our novel dataset, we use summary-chapter pairs collected by Ladhak et al.
(2020) from Project Gutenberg and various study guide sources. The size of the
dataset is 8,088 chapter/summary pairs 111Train/dev/test splits are
6,288/938/862. The average length of the chapters is 5,165 words with the
longest being 33,167 words222We are aware that there is a larger dataset
called BookSum (Kryściński et al., 2021), which uses similar sources; however,
due to licensing issues, we are unable to use it in our work..

In order to prepare the data for the experiments, we follow the same pre-
processing steps as Ladhak et al. (2020) to obtain the sub-sentential units
and their alignment to reference summaries. In addition, we truncate chapters
to 30k tokens to fit into the GPU memory333We use Amazon AWS EC2 P4dn 40GB GPU
memory; as a result, a single chapter of the dataset is actually truncated.

###  3.2 Extractive Model

The extractive summarization task can be posed as a classic regression and
ranking problem where the model produces a score for each of a given set of
units and then ranks them based on that score. The top $k$ units are then used
as an extract. The input of our model is the sub-sentential units of the novel
chapter text. We train the model with the oracle labels which we obtain from
the alignment between sub-sentential units and reference summaries.

#### Baseline

Our baseline is BertSummExt model (Liu and Lapata, 2019) modified as follows.
First, we replaced the underlying Transformer models (Vaswani et al., 2017)
with Longformers, which can better capture long context and requires less
computing memory than BERT (Devlin et al., 2019). Second, we removed the
inter-sentence Transformer layers stacked on top of the BERT output, to
further reduce memory usage. To avoid confusion with Liu and Lapata (2019)’s
model, we named this baseline as Longformer Ext.

#### Spinal Tree

A spinal tree is a dependency structure of a sentence that is augmented with
constituent information (Carreras et al., 2008; Ballesteros and Carreras,
2015). For each sub-sentential unit, we retrieve the spinal tree parse by
first using the constituency parser (Manning et al., 2014) and then apply
Collins Head-Word Finder (Collins, 1997) to calculate the spines. We then
encode444We use the hidden size of 512 the spinal tree using bidirectional-GRU
networks (Cho et al., 2014)555We experimented with other architectures
including bi-LSTM and found that bidirectional-GRU were the best..

We construct the input of the Longformer by concatenating the embeddings of
the tokens666We use the embedding size of 768, the corresponding positional
embeddings per token, and the encoding of the spines for each token via the
bidirectional-GRU encoders, as illustrated in Figure 1.

#### Ranking Loss

The baseline model uses the Cross-Entropy (CE) loss function and minimizes the
loss via gradient descent. However, the CE loss function focuses on optimizing
both the negative and positive labels at the same time. To compensate for the
imbalance in our dataset, we add a Margin Ranking (MR) loss that gives the
positive labels higher ranks than the negative labels 777We also have tried
the weighted CE loss function but we get worse results. We also found that
training our model first with the CE loss function until convergence and then
continuing using the MR loss gives the best result..

#### Re-ordering Scheme

The default baseline of Liu and Lapata (2019) produces extracts with sub-
sentential units that are ordered based on their score. This scheme, however,
destroys the plot of the story. Hence, we re-order the units according to the
original positional order in the source text, thus preserving the correct plot
order in the story.

###  3.3 Abstractive Model

Since the extractive model outputs are sometimes incoherent and hard to read,
we forward them to an abstractive model, with the goal to produce a more
fluent and coherent result.

We use BART (Lewis et al., 2019) as our engine for abstractive summarization.
To train BART, we use the oracle extracts as the input source and the
reference summaries as the target. During prediction, we use the output of our
content selection model as the input source.

Model | R1 | R2 | RL | WMD | BERTScore
---|---|---|---|---|---
Extractive
Oracle Ext |  46.75 |  14.27 |  45.64 |  0.633 |  0.823
CB const R-wtd (Ladhak, 2020) |  36.62 |  6.9 |  35.4 | N/A | N/A
Longformer Ext |  39.24 |  7.61 |  38.29 |  0.712 |  0.803
(Modified Liu and Lapata (2019)) |  |  |  |  |
\+ Spinal Information |  39.35 |  7.62 |  38.45 |  0.711 |  0.802
\+ Ranking Loss |  39.48 |  7.63 |  38.58 |  0.708 |  0.802
\+ Re-ordering |  39.48 |  7.70 |  38.58 |  0.708 |  0.806
Abstractive
Oracle Abs |  45.82 |  14.14 |  42.74 |  0.641 |  0.828
BART Abs |  39.77 |  9.28 |  37.56 |  0.693 |  0.807
\+ Spinal Information |  39.83 |  9.33 |  37.61 |  0.691 |  0.807
\+ Ranking Loss |  39.88 |  9.35 |  37.68 |  0.691 |  0.807
\+ Re-ordering |  40.33 |  9.10 |  37.95 |  0.690 |  0.810
Table 2: ROUGE, Word Mover Distance and BERTScore for extractive and
abstractive models

##  4 Results

Examples of outputs from our best abstractive and extractive models are shown
in Table 1. Here we report results from an automatic and a manual evaluation.
We compare our approach with and without the different extensions to the prior
best model from Ladhak et al. (2020) We also included the oracle for both the
extractive and abstractive models.

###  4.1 Automatic Evaluation

We use three different metrics for automatic evaluation: ROUGE (Lin, 2004),
BERTScore (Zhang et al., 2019b) and Word Mover Distance (WMD) (Kusner et al.,
2015). ROUGE measures syntactic similarities between system and reference
summaries and BERTScore and WMD measure semantic similarities. BERTScore
measures similarities at the sentence level while WMD does at the token level.
We run each experiment three times using different random seeds and we report
the mean score.

Table 2 shows our models performance against the baseline and previous works.
Our best extractive model (Longformer Ext+spinal+Ranking+Re-ordering)
outperforms previous work (CB const R-wtd) by 2.86 ROUGE-1, 0.8 ROUGE-2, and
3.18 ROUGE-L points. Meanwhile, the abstractive model (BART
Abs+spinal+Ranking+Re-ordering) outperforms previous work (CB const R-wtd) by
3.71 ROUGE-1, 2.2 ROUGE-2, and 2.55 ROUGE-L points. We have also shown that
both the best abstractive and extractive models exceed their corresponding
baselines (Longformer Ext and BART Abs) in all metrics. Our models still have
room to grow as shown by the oracle results.

###  4.2 Human Evaluation

For human evaluation, we use the lightweight Pyramid (Shapira et al., 2019).
We randomly selected 99 samples 888We prepared 100 samples, but one sample got
corrupted during the evaluation. from the test dataset for human evaluation.
We also re-run Ladhak et al. (2020)’s output’s using the same samples in order
to compare ours with their work.

Model | Pyramid
---|---
CB Const R-wtd (Ladhak, 2020) | 17.91
BART Abs | 22.03
BART Abs+Spinal+Rank+Re-ordering | 22.86
Table 3: Pyramid score for our best abstractive performance model compared to
previous works

Table 3 shows that our models outperform previous work by at least 2 points.
We also show that the application of spinal tree enrichment, ranking loss and
re-ordering show an improvement of 0.83 points in the human evaluation.

##  5 Conclusion and Future Work

We have built a novel chapter summarization that produces abstract summaries
using a spinal tree aware sub-sentential content selection method. Our results
show that we have improved over the state-of-the-art of an existing novel
chapter dataset in both automatic and human evaluations.

For future work, we propose an approach where the segmentation of sub-
sentential units is jointly trained with the content selection instead of pre-
processed before the training process. We hypothesize that this could improve
the alignment with reference summaries, therefore, increasing the performance
of the overall models.

## Limitation

The limitation of our work is that the dataset is small. It is also difficult
to show significance using a small dataset. Investigation on larger datasets
would be necessary to further validate our conclusions.

## Ethical Impact

We don’t foresee any ethical issues with our approach. One could argue that
our system might ultimately take jobs away from the people who currently write
such summaries. However, given the number of books being written, it is more
likely that some summaries would never be written and a good system for novel
chapter summarization might help to increase the amount of summaries that are
available online.

## References

  * Ballesteros and Carreras (2015) Miguel Ballesteros and Xavier Carreras. 2015.  Transition-based spinal parsing.  In _Proceedings of the 19th Conference on Computational Language Learning (CoNLL 2015). 2015 July 30-31; Beijing, China.[Stroudsburg]: ACL, 2015. p. 289-99._ repositori.upf.edu.
  * Beltagy et al. (2020) Iz Beltagy, Matthew E Peters, and Arman Cohan. 2020.  Longformer: The Long-Document transformer.
  * Blei et al. (2003) David M Blei, Andrew Y Ng, and Michael I Jordan. 2003.  Latent dirichlet allocation.  _the Journal of machine Learning research_ , 3:993–1022.
  * Carreras et al. (2008) Xavier Carreras, Michael Collins, and Terry Koo. 2008.  Tag, dynamic programming, and the perceptron for efficient, feature-rich parsing.  In _CoNLL 2008: Proceedings of the Twelfth Conference on Computational Natural Language Learning_ , pages 9–16.
  * Chen and Bansal (2018) Yen-Chun Chen and Mohit Bansal. 2018.  Fast abstractive summarization with Reinforce-Selected sentence rewriting.
  * Cho et al. (2014) Kyunghyun Cho, Bart van Merriënboer, Caglar Gulcehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. 2014.  Learning phrase representations using rnn encoder–decoder for statistical machine translation.  In _Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 1724–1734.
  * Collins (1997) Michael Collins. 1997.  Three generative, lexicalised models for statistical parsing.  _arXiv preprint cmp-lg/9706022_.
  * Cruz et al. (2016) Ricardo Cruz, Kelwin Fernandes, Jaime S Cardoso, and Joaquim F Pinto Costa. 2016\.  Tackling class imbalance with ranking.  In _2016 International joint conference on neural networks (IJCNN)_ , pages 2182–2187. IEEE.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  Bert: Pre-training of deep bidirectional transformers for language understanding.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 4171–4186.
  * Good (1992) Irving John Good. 1992.  Rational decisions.  In _Breakthroughs in statistics_ , pages 365–377. Springer.
  * Grusky et al. (2018) Max Grusky, Mor Naaman, and Yoav Artzi. 2018.  Newsroom: A Dataset of 1.3 Million Summaries with Diverse Extractive Strategies.  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers)_ , volume 1, pages 708–719, Stroudsburg, PA, USA. Association for Computational Linguistics.
  * Hermann et al. (2015) Karl Moritz Hermann, Tomáš Kočiský, Edward Grefenstette, Lasse Espeholt, Will Kay, Mustafa Suleyman, and Phil Blunsom. 2015\.  Teaching Machines to Read and Comprehend.  In _Neural Information Processing Systems_ , pages 1–14.
  * Kryściński et al. (2021) Wojciech Kryściński, Nazneen Rajani, Divyansh Agarwal, Caiming Xiong, and Dragomir Radev. 2021.  Booksum: A collection of datasets for long-form narrative summarization.
  * Kusner et al. (2015) Matt Kusner, Yu Sun, Nicholas Kolkin, and Kilian Weinberger. 2015.  From word embeddings to document distances.  In _International conference on machine learning_ , pages 957–966. PMLR.
  * Ladhak et al. (2020) Faisal Ladhak, Bryan Li, Yaser Al-Onaizan, and Kathleen McKeown. 2020.  Exploring content selection in summarization of novel chapters.
  * Lewis et al. (2019) Mike Lewis, Yinhan Liu, Naman Goyal, Marjan Ghazvininejad, Abdelrahman Mohamed, Omer Levy, Ves Stoyanov, and Luke Zettlemoyer. 2019.  BART: Denoising Sequence-to-Sequence pre-training for natural language generation, translation, and comprehension.
  * Lin (2004) Chin-Yew Lin. 2004.  ROUGE: A package for automatic evaluation of summaries.  In _Text Summarization Branches Out_ , pages 74–81, Barcelona, Spain. Association for Computational Linguistics.
  * Liu and Lapata (2019) Yang Liu and Mirella Lapata. 2019.  Text summarization with pretrained encoders.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 3730–3740.
  * Malioutov (2006) Igor Igor Mikhailovich Malioutov. 2006.  _Minimum cut model for spoken lecture segmentation_.  Ph.D. thesis, Massachusetts Institute of Technology.
  * Manning et al. (2014) Christopher D. Manning, Mihai Surdeanu, John Bauer, Jenny Finkel, Steven J. Bethard, and David McClosky. 2014.  The Stanford CoreNLP natural language processing toolkit.  In _Association for Computational Linguistics (ACL) System Demonstrations_ , pages 55–60.
  * Mihalcea and Ceylan (2007) Rada Mihalcea and Hakan Ceylan. 2007.  Explorations in automatic book summarization.  In _Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning (EMNLP-CoNLL)_ , pages 380–389, Prague, Czech Republic. Association for Computational Linguistics.
  * Narayan et al. (2018) Shashi Narayan, Shay B Cohen, and Mirella Lapata. 2018.  Don’t give me the details, just the summary! Topic-Aware convolutional neural networks for extreme summarization.
  * Radev et al. (2004) Dragomir R Radev, Hongyan Jing, Małgorzata Styś, and Daniel Tam. 2004.  Centroid-based summarization of multiple documents.  _Information Processing & Management_, 40(6):919–938.
  * Raffel et al. (2019) Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. 2019.  Exploring the limits of transfer learning with a unified Text-to-Text transformer.
  * Rosasco et al. (2004) Lorenzo Rosasco, Ernesto De Vito, Andrea Caponnetto, Michele Piana, and Alessandro Verri. 2004.  Are loss functions all the same?  _Neural computation_ , 16(5):1063–1076.
  * Shapira et al. (2019) Ori Shapira, David Gabay, Yang Gao, Hadar Ronen, Ramakanth Pasunuru, Mohit Bansal, Yael Amsterdamer, and Ido Dagan. 2019.  Crowdsourcing lightweight pyramids for manual summary evaluation.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 682–687, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017.  Attention is all you need.  In _Advances in neural information processing systems_ , pages 5998–6008.
  * Wu et al. (2021) Jeff Wu, Long Ouyang, Daniel M Ziegler, Nisan Stiennon, Ryan Lowe, Jan Leike, and Paul Christiano. 2021.  Recursively summarizing books with human feedback.  _arXiv preprint arXiv:2109.10862_.
  * Wu et al. (2017) Zongda Wu, Li Lei, Guiling Li, Hui Huang, Chengren Zheng, Enhong Chen, and Guandong Xu. 2017.  A topic modeling based approach to novel document automatic summarization.  _Expert Systems with Applications_ , 84:12–23.
  * Zhang et al. (2019a) Jingqing Zhang, Yao Zhao, Mohammad Saleh, and Peter J Liu. 2019a.  PEGASUS: Pre-training with extracted gap-sentences for abstractive summarization.
  * Zhang et al. (2019b) Tianyi Zhang, Varsha Kishore, Felix Wu, Kilian Q Weinberger, and Yoav Artzi. 2019b.  Bertscore: Evaluating text generation with bert.  _arXiv preprint arXiv:1904.09675_.

##  Appendix A Human Evaluation

For performing Human Evaluation, we use crowdsourcing service provided by
Appen.999https://appen.com/solutions/crowd-management/ We follow Ladhak et al.
(2020)’s approach including the instructions and number of crowdworkers. For
each crowdworker, we calculate the payment based on the minimum wage in the US
($ 15 per hour).


# A tight bound on the stepsize of the Decentralized gradient descent

Woocheol Choi  Department of Mathematics, Sungkyunkwan University, Suwon
440-746, Republic of Korea<EMAIL_ADDRESS>
###### Abstract.

In this paper, we consider the decentralized gradinet descent (DGD) given by

$x_{i}(t+1)=\sum_{j=1}^{m}w_{ij}x_{j}(t)-\alpha(t)\nabla f_{i}(x_{i}(t)).$

We find a sharp range of the stepsize $\alpha(t)>0$ such that the sequence
$\\{x_{i}(t)\\}$ is uniformly bounded when the aggregate cost $f$ is assumed
be strongly convex with smooth local costs which might be non-convex.
Precisely, we find a tight bound $\alpha_{0}>0$ such that the states of the
DGD algorithm is unfiromly bounded for non-increasing sequence $\alpha(t)$
satisfying $\alpha(0)\leq\alpha_{0}$. The theoretical results are also
verified by numerical experiments.

###### Key words and phrases:

Distributed optimization, Gradient descent, Sharp range

###### 2010 Mathematics Subject Classification:

Primary 65K10, 90C26

##  1\. Introduction

In this work, we consider the distributed optimization

$\min_{x}~{}f(x):=\frac{1}{m}\sum_{k=1}^{m}f_{k}(x),$ (1.1)

where $m$ denotes the number of agents and
$f_{k}:\mathbb{R}^{n}\rightarrow\mathbb{R}$ is a differentiable local cost
only known to agent $k$ for each $1\leq k\leq m$. The decetralized gradient
descent is given as

$x_{k}(t+1)=\sum_{j=1}^{m}w_{kj}x_{j}(t)-\alpha(t)\nabla f_{k}(x_{k}(t)).$
(1.2)

Here $\alpha(t)>0$ is a stepsize and $x_{k}(t)$ denotes the variable of agent
$k$ at time instant $t\geq 0$. The communication pattern among agents in (1.1)
is determined by an undirected graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$,
where each node in $\mathcal{V}$ represents each agent, and each edge
$\\{i,j\\}\in\mathcal{E}$ means $i$ can send messages to $j$ and vice versa.
The value $w_{ij}$ is a nonnegative weight value such that $w_{ij}>0$ if and
only if $\\{i,j\\}\in\mathcal{E}$ and the matrix $W=\\{w_{ij}\\}_{1\leq
i,j\leq m}$ is doubly stochastic.

This algorithm has recieved a lot of attentions from researchers in various
fields. In particular, the algorithm has been a pivotal role in the
development of several methods, containing online distributed gradient descent
method [13, 3], the stochastic decentralized gradient descent [11], and multi-
agent Reinforcement Learning [7, 15]. It was also extended to nested
communication-local computation algorithms [1, 5].

For the fast convergence of the algorithm (1.2), it is important to choose a
suitable sequence of the stepsize $\alpha(t)$. It is often advantageous to
choose a possibly large stepsize as the convergence may become faster as the
stepsize gets larger in a stable regime.

When it comes to the cases $m=1$, the algorithm is reduced to the gradient
descent algorithm given as

$x(t+1)=x(t)-\alpha(t)\nabla f(x(t)),$ (1.3)

and we recall a well-known convergence result in the following theorem.

######  Theorem 1.1.

Assume that $f$ is $\mu$-strongly convex and $L$-smooth. Suppose that the
stepsize of (1.3) satisfies $\alpha(t)\leq\frac{2}{\mu+L}$. Then the sequence
$\\{x(t)\\}_{t\geq 0}$ is bounded. Moreover,

$\|x(t+1)-x_{*}\|^{2}\leq\Big{(}1-\frac{2L\mu\alpha(t)}{L+\mu}\Big{)}\|x(t)-x_{*}\|^{2}.$

Although the convergence property of the algorithm (1.2) has been studied
extensively ([8, 9, 12, 14, 6]), the sharp range of $\alpha(t)$ for the
convergence of the algorithm (1.2) has not been completely understood, even
when each cost $f_{k}$ is a quadratic form.

In the early stage, the convergene of the algorithm (1.2) was studied with
assuming that $\|\nabla f_{i}\|_{\infty}<\infty$ and each function $f_{i}$ is
convex for $1\leq i\leq m$. Nedić-Ozdaglar [8] showed that for the algorithm
(1.2) with the stepsize $\alpha(t)\equiv\alpha$, the cost value $f(\cdot)$ at
an average of the iterations converges to an $O(\alpha)$-neighborhood of an
optimal value of $f$. Nedić-Ozdaglar [9] proved that the algorithm (1.2)
converges to an optimal point if the stepsize satisfies
$\sum_{t=1}^{\infty}\alpha(t)=\infty$ and
$\sum_{t=1}^{\infty}\alpha(t)^{2}<\infty$. In the work of Chen [4], the
algorithm (1.2) with stepsize $\alpha(t)=c/t^{p}$ with $0<p<1$ was considered
and the convergene rate was achieved as $O(1/t^{p})$ for $0<p<1/2$, $O(\log
t/\sqrt{t})$ for $p=1/2$, and $O(1/t^{1-p})$ for $1/2<p<1$.

Recently, Yuan-Ling-Yin [14] established the convergence property of the
algorithm (1.2) without the gradient bound assumption. Assuming that each
local cost function is convex and the total cost is strongly convex, they
showed that the algorithm (1.2) with constant stepsize $\alpha(t)\equiv\alpha$
converges exponentially to an $O(\alpha)$-neighborhood of an optimizer $x_{*}$
of (1.1). Recently, the work [6] obtained the convergence property of the
algorithm (1.2) for a general class of non-increasing stepsize
$\\{\alpha(t)\\}_{t\in\mathbb{N}_{0}}$ given as $\alpha(t)=a/(t+w)^{p}$ for
$a>0$, $w\geq 1$ and $0<p\leq 1$ assuming the strong convexity on the total
cost function $f$, with cost functions $f_{i}$ not necessarily being convex.

To discuss the convergence property of (1.2), it is convenient to state the
following definition.

######  Definition 1.2.

The sequence $\\{x_{k}(t)\\}$ of (1.2) is said to be uniformly bounded if
there exists a value $R>0$ such that

$\|x_{i}(t)\|\leq R$

for all $t\geq 0$ and $1\leq i\leq m$.

We state the following convergence results established in the works [14, 6].

######  Theorem 1.3 ([14, 6]).

Assume that each cost $f_{k}$ is $L$-smooth and the aggregate cost $f$ is
$\mu$-strongly convex. Suppose also that the sequence $\\{x_{k}(t)\\}_{t\geq
0}$ of (1.2) is uniformly bounded and $\alpha(0)\leq\frac{2}{\mu+L}$. Then we
have the following results:

  1. (1)

If $\alpha(t)\equiv\alpha$, then the sequence $x_{k}(t)$ converges
exponentially to an $O\Big{(}\frac{\alpha}{1-\beta}\Big{)}$ neighborhood of
$x_{*}$.

  2. (2)

If $\alpha(t)=\frac{a}{(t+w)^{p}}$ for some $a>0,w\geq 0$ and $p\in(0,1]$,
then the sequence $x_{k}(t)$ converges to $x_{*}$ with the following rate

$\|x_{i}(t)-x_{*}\|=O\Big{(}\frac{1}{t^{p}}\Big{)}.$

We remark that a uniform bound assumption for the sequence
$\\{x_{k}(t)\\}_{t\geq 0}$ is required in the above result, which is contrast
to the result of Theorem 1.1. In fact, the boundedness property of (1.2) has
been obtained under an additional restriction on the stepsize as in the
following results.

######  Theorem 1.4 ([14]).

Assume that $f_{j}$ is convex and $L$-smooth. Suppose that the stepsize is
constant $\alpha(t)=\alpha$ and $\alpha\leq\frac{(1+\lambda_{m}(W))}{L}$, then
the sequence $\\{x(t)\\}$ is uniformly bounded. Here $\lambda_{m}(W)$ denotes
the smallest eigenvalue of the matrix $W$.

######  Theorem 1.5 ([6]).

Assume that $f_{j}$ is $L$-smooth and $f$ is $\mu$-strongly convex. Let
$\eta=\frac{\mu L}{\mu+L}$ and suppose that
$\alpha(t)\leq\frac{\eta(1-\beta)}{L(\eta+L)}$. Then the sequence
$\\{x_{i}(t)\\}$ is uniformly bounded.

In the above results, we note the following inequality

$\frac{\eta(1-\beta)}{L(\eta+L)}<\frac{1+\lambda_{m}(W)}{L}.$

Therefore, the result of Theorem 1.4 establishes the boundedness property for
a broader range of the constant stepsize with assuming the convexity for each
local cost. Meanwhile, the result of Theorem 1.5 establishes the boundedness
property for time varying stepsize without assuming the convexity on each
local cost, but the range of the stepsize is more restrictive. Having said
this, it is natural to consider the following questions:

Question 1: _Does the result of Theorem 1.4 hold for time-varying stepsize?
and can we moderate the convexity assumption on each cost?_

Question 2: _Can we extend the range of $\alpha(t)$ in the result of Theorem
1.5 with an additional information of the cost functions?_

We may figure out the importance of these questions by considering an example:
Consider $m=3$ and the functions
$f_{1},f_{2},f_{3}:\mathbb{R}^{2}\rightarrow\mathbb{R}$ defined as

$f_{1}(x,y)=f_{2}(x,y)=\frac{L}{2}x^{2}+\frac{\mu}{2}y^{2}\quad\textrm{and}\quad
f_{3}(x,y)=-\frac{\epsilon}{2}x^{2}+\frac{\mu}{2}y^{2},$ (1.4)

where $L\gg\mu_{0}>0$ and $\epsilon\geq 0$ is small enough. Then $f_{k}$ is
$L$-smooth for $1\leq k\leq 3$ and the aggregate cost $f$ is $\mu$-strongly
convex. If we apply the above results, we have the following results:

If $\epsilon=0$, then the boundedness property holds by Theorem 1.4 for
constant stepsize $\alpha(t)\equiv\alpha$ satisfying

$\alpha\leq\frac{1+\lambda_{m}(W)}{L}.$

If $\epsilon>0$, then the boundedness property holds by Theorem 1.5 for the
stepsize $\alpha(t)$ satisfying

$\alpha(t)\leq\frac{\eta(1-\beta)}{L(\eta+L)}.$

Here we see that the range guaranteed by the above theorems drastically
changes as the value $\epsilon$ becomes positive from zero.

The purpose of this paper is to provide reasonable answers to the above-
mentioned questions. For this we consider the function
$G_{\alpha}:\mathbb{R}^{nm}\rightarrow\mathbb{R}$ for $\alpha>0$ defined by

$\begin{split}G_{\alpha}(\mathbf{x})&=\frac{\alpha}{m}\sum_{k=1}^{m}f_{k}(x_{k})+\frac{1}{2}\mathbf{x}^{T}(I-W\otimes
1_{n})\mathbf{x}\\\
&=:\alpha\mathbf{F}(\mathbf{x})+\frac{1}{2}\mathbf{x}^{T}(I-W\otimes
1_{n})\mathbf{x}.\end{split}$

As well-known, the algorithm (1.2) is then written as

$\mathbf{x}(t+1)=\mathbf{x}(t)-\nabla G_{\alpha(t)}(\mathbf{x}(t)).$ (1.5)

For each $\alpha>0$ we define the following function class

$\mathbf{G}_{\alpha}=\Big{\\{}(f_{1},\cdots,f_{m})\in(C_{1}(\mathbb{R}^{n}))^{m}~{}\Big{|}~{}\textrm{the
function $G_{\alpha}$ is strongly convex }\Big{\\}}.$ (1.6)

The following is the main result of this paper.

######  Theorem 1.6.

Suppose that $F=(f_{1},\cdots,f_{m})\in A_{\alpha_{0}}$ for some
$\alpha_{0}>0$ and $f_{k}$ is $L$-smooth for each $1\leq k\leq m$. Assume that
the sequence of stepsize $\\{\alpha(t)\\}_{t\in\mathbb{N}}$ is a non-
increasing sequence satisfying

$\alpha(0)\leq\min\Big{\\{}\frac{1+\lambda_{m}(W)}{L},~{}\alpha_{0}\Big{\\}}.$
(1.7)

Then the sequence $\\{\mathbf{x}(t)\\}$ is uniformly bounded.

This result naturally extends the previous works [14, 6]. We mention that the
result [14] was obtained for constant stepsize
$\alpha(t)\equiv\alpha\leq\frac{1+\lambda_{m}(W)}{L}$ under the assumption
that each cost $f_{k}$ is convex. Meanwhile, the result [6] was obtained only
assuming that the aggregate cost $f$ is strongly convex but the stepsize range
is more conservative. We summarize the results of [14, 6] and this work in
Table 1.

| Convexity condition | Type of stepsize | Bound on stepsize
---|---|---|---
[14] | Each $f_{j}$ is convex |  constant $\alpha(t)\equiv\alpha$ | $\alpha\leq\frac{(1+\lambda_{m}(W))}{L}$
[6] |  $f$ is $\mu$-strongly convex | any sequence | $\alpha(t)\leq\frac{\eta(1-\beta)}{L(\eta+L)}$
This work |  $G_{\alpha_{0}}$ is strongly convex |  non-increasing sequence | $\alpha(t)\leq\min\Big{\\{}\frac{1+\lambda_{m}(W)}{L},~{}\alpha_{0}\Big{\\}}.$
Table 1. This table summarizes the conditions for the uniform boundedness of
the sequence $\mathbf{x}(t)$ of DGD algorithm (1.5).

For the example (1.4), we set $L=10$, $\mu=1$, and

$W=\begin{pmatrix}0.4&0.3&0.3\\\ 0.3&0.3&0.4\\\ 0.3&0.4&0.3\end{pmatrix}.$

Then for $0\leq\epsilon\leq 10$ we have

$\alpha_{S}:=\frac{\eta(1-\beta)}{L(\eta+L)}=0.0075,\quad\frac{1+\lambda_{m}(W)}{L}=0.2.$

Finally the value $\alpha_{0}$ of Theorem 1.6 is computed for each
$\epsilon\in(0,10]$. The graph of Figure 1 shows that the value $\alpha_{0}$
is larger than $(1+\lambda_{m}(W))/L$ for small $\epsilon>0$, but it becomes
smllaer than the latter value $\epsilon>0$ is larger than $3$. For the detail
computing these values, we refer to Section 5.

Figure 1. The figure corresponds to the graph of values $\alpha_{0}$,
$\alpha_{S}$ and $\frac{1+\lambda_{m}(W)}{L}$ with respect to $\epsilon\geq
0$.

The function class $\mathbf{G}_{\alpha}$ is closely related to the function
class that the aggregate cost $f$ is strongly convex. To explain the relation,
for each $\alpha>0$ we let

$S_{\alpha}=\\{(f_{1},\cdots,f_{m})\in(C_{1}(\mathbb{R}^{n})^{m}~{}\mid~{}\textrm{the
function $f$ is $\alpha$-strongly convex}\\}.$

Then, for given $F=(f_{1},\cdots,f_{m})\in(C_{1}(\mathbb{R}^{n})^{m}$, we will
prove that the following relation between the class $\mathbf{G}_{\alpha}$ and
$S_{\alpha}$ in Section 2:

  1. (1)

If $f_{k}$ is quadratic and convex for each $1\leq k\leq m$, then

$F\in S_{\mu}\textrm{~{}for some~{}}\mu>0\Longrightarrow
F\in\mathbf{G}_{\alpha}\textrm{~{}for all~{}}\alpha>0.$

  2. (2)

If $f_{k}$ is quadratic for each $1\leq k\leq m$, then

$F\in S_{\mu}\textrm{~{}for some~{}}\mu>0\Longrightarrow
F\in\mathbf{G}_{\alpha}\textrm{~{}for some~{}}\alpha>0.$

  3. (3)

It always holds that

$F\in\mathbf{G}_{\alpha}\textrm{~{}for
some~{}}\alpha>0~{}\Longrightarrow~{}F\in S_{\mu}~{}\textrm{ for
some}~{}\mu>0.$

For given $F\in\mathbf{G}_{\alpha}$, let us denote the optimal point of
$G_{\alpha}$ by $\mathbf{x}_{*}^{\alpha}$. In order to prove the above result,
we exploit the fact that the algorithm (1.2) at step $t$ is interpreted as the
gradient descent of $G_{{\alpha}(t)}$ as in (1.5). Using this fact, it is not
difficult to derive the result of Theorem 1.6 if the stepsize is given by a
constant $\alpha(t)\equiv\alpha>0$ since the gradient descent descent (1.5)
converges to the minimizer $\mathbf{x}_{*}^{\alpha}$. However, when the
stepsize is varying, then we may not interprete (1.5) as a gradient descent
algorithm of a single objective function. In order to handle this case, we
prove the continuity and boundedness property of $x_{\alpha}$ with respect to
$\alpha$. Precisely, we obtain the following result.

######  Theorem 1.7.

Assume that $G_{\alpha_{0}}$ is $\mu$-strongly convex for some $\alpha_{0}>0$
and $\mu>0$. Then the following results hold:

  1. (1)

For $\alpha\in(0,\alpha_{0}]$ we have

$\|\mathbf{x}_{*}^{\alpha}\|^{2}\leq\frac{2\alpha_{0}}{\mu}f(0).$

  2. (2)

For all $\alpha,\beta\in(0,\alpha_{0}]$ we have

$\|\mathbf{x}_{*}^{\alpha}-\mathbf{x}_{*}^{\beta}\|\leq\frac{2\alpha_{0}C_{1}|\beta-\alpha|}{\mu\beta},$

where

$C_{1}=\sup_{s\in[0,1]}\sup_{\alpha,\beta\in(0,\alpha_{0}]}\Big{\|}\nabla\mathbf{F}(\mathbf{x}_{*}^{\beta}+s(\mathbf{x}_{*}^{\alpha}-\mathbf{x}_{*}^{\beta}))\Big{\|}.$

In the above result, we remark that the constant $C_{1}$ is bounded since
$\mathbf{F}$ is smooth and $\mathbf{x}_{*}^{\alpha}$ are uniformly bounded for
$\alpha\in(0,\alpha_{0}]$. We will make use of this result to prove Theorem
1.6.

The rest of this paper is organized as follows. Section 2 is devoted to study
the function class $\mathbf{G}_{\alpha}$. In Section 3 we exploit the
boundedness and continuity property of the optimizer of $G_{\alpha}$ with
respect to $\alpha$. Based on the property, we prove the main result in
Section 4. Section 5 provides some numerical experiments supporting the result
of this paper.

##  2\. Properties of the class $\mathbf{G}_{\alpha}$

In this section, we study the function classe $\mathbf{G}_{\alpha}$ defined in
(1.6). Before this, we introduce two standard assumptions on the graph
$\mathcal{G}$ ans its associated weight $W=\\{w_{ij}\\}_{1\leq i,j\leq m}$.

######  Assumption 1.

The communication graph $\mathcal{G}$ is undirected and connected, i.e., there
exists a path between any two agents.

We define the mixing matrix $W=\\{w_{ij}\\}_{1\leq i,j\leq m}$ as follows. The
nonnegative weight $w_{ij}$ is given for each communication link
$\\{i,j\\}\in\mathcal{E},$ where $w_{ij}\neq 0$ if $\\{i,j\\}\in\mathcal{E}$
and $w_{ij}=0$ if $\\{i,j\\}\notin\mathcal{E}$. In this paper, we make the
following assumption on the mixing matrix $W$.

######  Assumption 2.

The mixing matrix $W=\\{w_{ij}\\}_{1\leq i,j\leq m}$ is doubly stochastic,
i.e., $W\mathbf{1}=\mathbf{1}$ and $\mathbf{1}^{T}W=\mathbf{1}^{T}$. In
addition, $w_{ii}>0$ for all $i\in\mathcal{V}$.

In the following theorem, we study the function class $\mathbf{G}_{\alpha}$
when each local cost is a quadratic form.

######  Theorem 2.1.

Assume that each cost is a quadratic form
$f_{k}(x)=\frac{1}{2}x_{k}^{T}A_{k}x_{k}$.

  1. (1)

Assume that each $f_{k}$ is convex and $f$ is $\mu$-strongly convex. Then
$G_{\alpha}$ is strongly convex for any $\alpha>0$.

  2. (2)

Assume that $f$ is $\mu$-strongly convex. Then there exists a value
$\alpha_{0}>0$ such that for $\alpha>\alpha_{0}$, $G_{\alpha}$ is strongly
convex.

###### Proof.

Then $G_{\alpha}$ is given as

$G_{\alpha}(\mathbf{x})=\frac{\alpha}{2m}\sum_{k=1}^{m}x_{k}^{T}A_{k}x_{k}+\frac{1}{2}\mathbf{x}^{T}(I-W\otimes
1_{n})\mathbf{x}.$

Choose a constant $Q>0$ and $\bar{Q}>0$ such that

$\Big{\|}\sum_{k=1}^{n}A_{k}u_{k}\Big{\|}\leq
Q\|u\|\quad\forall~{}u\in\mathbb{R}^{mn}$ (2.1)

and

$\Big{\|}(A_{1}u_{1},\cdots,A_{m}u_{m})\Big{\|}\leq\bar{Q}\|u\|\quad\forall~{}u\in\mathbb{R}^{nm}.$
(2.2)

Let $\mathbf{x}=1\otimes\bar{x}+u$ with $u=\mathbf{x}-1\otimes\bar{x}$ and
$\bar{x}=\frac{1}{n}\sum_{k=1}^{n}x_{k}$. Using that $W1_{m}=1_{m}$, we find

$G_{\alpha}(\mathbf{x})=\frac{\alpha}{2m}\sum_{k=1}^{n}(\bar{x}+u_{k})^{T}A_{k}(\bar{x}+u_{k})+\frac{1}{2}u^{T}(I-W\otimes
1_{n})u.$ (2.3)

Take a constant $c>0$ and consider

$Y_{c}=\\{\mathbf{x}=1\bar{x}+u~{}:~{}\|u\|\leq
c\|\bar{x}\|\\}\quad\textrm{and}\quad
Z_{c}=\\{\mathbf{x}=1\bar{x}+u~{}:~{}\|u\|\geq c\|\bar{x}\|\\}.$

If $\mathbf{x}\in Y_{c}$, then we have

$\|\mathbf{x}\|^{2}=n\|\bar{x}\|^{2}+\|u\|^{2}\leq(n+c^{2})\|\bar{x}\|^{2}.$
(2.4)

For $\mathbf{x}\in Z_{c}$, it holds that

$\|\mathbf{x}\|^{2}=n\|\bar{x}\|^{2}+\|u\|^{2}\leq\frac{(n+c^{2})}{c^{2}}\|u\|^{2}.$
(2.5)

Now we proceed to prove (1). For $\mathbf{x}\in Y_{c}$ we use (2.1) to
estimate (2.3) as

$\begin{split}G_{\alpha}(\mathbf{x})&=\frac{\alpha}{2m}\Big{[}\bar{x}^{T}\Big{(}\sum_{k=1}^{m}A_{k}\Big{)}\bar{x}+2\bar{x}\Big{(}\sum_{k=1}^{m}A_{k}u_{k}\Big{)}+\sum_{k=1}^{m}u_{k}^{T}A_{k}u_{k}\Big{]}+\frac{1}{2}u^{T}(I-W\otimes
I_{n})u\\\
&\geq\frac{\alpha}{2}\Big{[}\mu\|\bar{x}\|^{2}-2Q\|\bar{x}\|\|u\|\Big{]}\\\
&\geq\frac{\alpha}{2}[\mu-2Qc]\|\bar{x}\|^{2}.\end{split}$

Using (2.4) here, we find

$G_{\alpha}(\mathbf{x})\geq\frac{\alpha(\mu-2Qc)}{2(n+c^{2})}\|\mathbf{x}\|^{2}.$

For $\mathbf{x}\in Z_{c}$ we have

$G_{\alpha}(\mathbf{x})\geq(1-\beta)\|u\|^{2}\geq\frac{(1-\beta)c^{2}}{n+c^{2}}\|\mathbf{x}\|^{2}.$

Here we used the fact that

$y^{T}(I-W)y\geq(1-\beta)\|y\|^{2}$

for any $y\in\mathbb{R}^{m}$ satisfying $\langle y,1_{m}\rangle=0$, where
$\beta\in(0,1)$ is the second largest eigenvalue of $W$.

Combining the above two estimates, we find

$G_{\alpha}(\mathbf{x})\geq\min\Big{\\{}\frac{(1-\beta)c^{2}}{n+c^{2}},\frac{\alpha(\mu-2Qc)}{2(n+c^{2})}\Big{\\}}\|\mathbf{x}\|^{2},$

which provesthe first assertion (1).

Next we prove (2). For $\mathbf{x}\in Y_{c}$ we have

$\begin{split}G_{\alpha}(\mathbf{x})&\geq\frac{\alpha}{2}\Big{[}\mu\|\bar{x}\|^{2}-2\|\bar{x}\|\Big{\|}\sum_{k=1}^{m}A_{k}u_{k}\Big{\|}-\|u\|\Big{\|}\sum_{k=1}^{n}A_{k}u_{k}\Big{\|}\Big{]}\\\
&\geq\frac{\alpha}{2}\Big{[}\mu\|\bar{x}\|^{2}-2Q\|\bar{x}\|\|u\|-\bar{Q}\|u\|^{2}\Big{]}\\\
&\geq\frac{\alpha}{2}\Big{[}\mu\|\bar{x}\|^{2}-(2cQ+c^{2}\bar{Q})\|\bar{x}\|^{2}\Big{]}.\end{split}$

For $\mathbf{x}\in Z_{c}$ we estimate

$\begin{split}G_{\alpha}(\mathbf{x})&\geq\frac{\alpha}{2}\sum_{k=1}^{m}\bar{x}^{T}A_{k}\bar{x}+\alpha\sum_{k=1}^{m}\bar{x}(A_{k}u_{k})+\frac{\alpha}{2}\sum_{k=1}^{m}u_{k}^{T}A_{k}u_{k}+(1-\beta)\|u\|^{2}\\\
&\geq\frac{\alpha\mu}{2}\|\bar{x}\|^{2}-\alpha
Q\|\bar{x}\|\|u\|-\frac{\alpha\bar{Q}}{2}\|u\|^{2}+(1-\beta)\|u\|^{2}\\\
&\geq\frac{\alpha\mu}{2}\|\bar{x}\|^{2}-\Big{(}\frac{\alpha
Q}{c}+\frac{\alpha\bar{Q}}{2}\Big{)}\|u\|^{2}+(1-\beta)\|u\|^{2}.\end{split}$

This gives the following estimate

$G_{\alpha}(\mathbf{x})\geq\frac{c^{2}}{n+c^{2}}\Big{[}(1-\beta)-\Big{(}\frac{\alpha
Q}{c}+\frac{\alpha\bar{Q}}{2}\Big{)}\Big{]}\|\mathbf{x}\|^{2}.$

This completes the proof of the second assertion (2). ∎

We also have the following result.

######  Theorem 2.2.

If $G_{\alpha}$ is $\mu$-stronlgy convex for some $\alpha>0$, then $f$ is
$\frac{\mu}{\alpha}$-stronlgy convex.

###### Proof.

Let $\mathbf{x}=(x,\cdots,x)$ and $\mathbf{y}=(y,\cdots,y)$. The strongly
convexity of $G_{\alpha}$ yields that

$G_{\alpha}(\mathbf{y})\geq
G_{\alpha}(\mathbf{x})+(\mathbf{y}-\mathbf{x})\nabla
G_{\alpha}(x)+\frac{\mu}{2}\|\mathbf{y}-\mathbf{x}\|^{2}.$ (2.6)

We have

$G_{\alpha}(\mathbf{x})=\frac{\alpha}{m}\sum_{k=1}^{m}f_{k}(x),\quad
G_{\alpha}(\mathbf{y})=\frac{\alpha}{m}\sum_{k=1}^{m}f_{k}(y).$

Also,

$\begin{split}\nabla G_{\alpha}(\mathbf{x})&=\frac{\alpha}{m}(\nabla
f_{1}(x),\cdots,\nabla f_{m}(x))+(I-W)\mathbf{x}\\\ &=\frac{\alpha}{m}(\nabla
f_{1}(x),\cdots,\nabla f_{m}(x)).\end{split}$

Using these equalities in (2.6) we find

$f(y)\geq f(x)+(y-x)\nabla f(x)+\frac{\mu}{2\alpha}\|y-x\|^{2},$

and so the function $f$ is $\frac{\mu}{2\alpha}$-strongly convex. The proof is
done. ∎

##  3\. Uniform bound and smoothness property of $x_{*}^{\alpha}$ with respect
to $\alpha>0$

In this section, we exploit the property of the minimizer
$\mathbf{x}_{\alpha}$ of the function $G_{\alpha}$. Under the strongly
convexity assumption on $G_{\alpha_{0}}$ for some $\alpha_{0}$, we will show
that the optimizers $\mathbf{x}_{*}^{\alpha}\in\mathbb{R}^{n}$ is uniformly
bounded for $\alpha\in(0,\alpha_{0}]$ and also locally Lipschitz continuous
with respect to $\alpha$.

######  Lemma 3.1.

We assume that $G_{\alpha}$ is $\mu$-strongly convex for some $\alpha>0$.
Then, the function $G_{\beta}$ is $\frac{\beta\mu}{\alpha}$-strongly convex
for any $\beta\in(0,\alpha]$.

###### Proof.

For $\beta\in(0,\alpha]$, we express the function $G_{\beta}$ as

$\begin{split}G_{\beta}(\mathbf{x})&=\beta\sum_{k=1}^{n}f_{k}(x_{k})+\frac{1}{2}\mathbf{x}^{T}(I-W\otimes
1_{n})\mathbf{x}\\\
&=\frac{\beta}{\alpha}\Big{[}\alpha\sum_{k=1}^{n}f_{k}(x_{k})+\frac{1}{2}\mathbf{x}^{T}(I-W\otimes
1_{n})\mathbf{x}\Big{]}+\frac{(\alpha-\beta)}{2\alpha}\mathbf{x}^{T}(I-W\otimes
1_{n})\mathbf{x}.\end{split}$

Since the last term is convex, and $G_{\alpha}$ is $\mu$-strongly convex, the
above formula yields that $G_{\beta}$ is $\frac{\beta\mu}{\alpha}$-strongly
convex. The proof is done. ∎

We now prove Theorem 1.7.

###### Proof of Theorem 1.7.

For $0<\alpha\leq\alpha_{0}$ we know that $G_{\alpha}$ is
$\Big{(}\frac{\alpha}{\alpha_{0}}\Big{)}\mu$-strongly convex by Lemma 3.1.
Therefore

$G_{\alpha}(\mathbf{x})\geq\frac{\alpha\mu}{2\alpha_{0}}\|\mathbf{x}-\mathbf{x}_{*}^{\alpha}\|^{2}$

for all $\mathbf{x}\in\mathbb{R}^{nm}$. Taking $\mathbf{x}=0$ here, we get

$\frac{\alpha\mu}{2\alpha_{0}}\|\mathbf{x}_{*}^{\alpha}\|^{2}\leq
G_{\alpha}(0)=\alpha f(0),$

which gives

$\|\mathbf{x}_{*}^{\alpha}\|^{2}\leq\frac{2\alpha_{0}}{\mu}f(0).$

This proves the first assertion.

Next we are concerned with the smoothness property of
$\mathbf{x}_{*}^{\alpha}\in\mathbb{R}^{d}$ with respect to the parameter
$\alpha>0$. The function $G_{\beta}$ is $\frac{\mu\beta}{\alpha_{0}}$-strongly
convex by Lemma 3.1. Using this fact and that $\mathbf{x}_{*}^{\beta}$ is a
minimizer of $F_{\beta}$, we find

$\begin{split}&\beta\mathbf{F}(\mathbf{x})+\frac{1}{2}\mathbf{x}^{T}(I-W)\mathbf{x}\\\
&\geq\frac{\mu\beta}{2\alpha_{0}}\|\mathbf{x}-\mathbf{x}_{*}^{\beta}\|^{2}+\beta\mathbf{F}(\mathbf{x}_{*}^{\beta})+\frac{1}{2}(\mathbf{x}_{*}^{\beta})^{T}(I-W)\mathbf{x}_{*}^{\beta}\\\
&=\frac{\mu\beta}{2\alpha_{0}}\|\mathbf{x}-\mathbf{x}_{*}^{\beta}\|^{2}+(\beta-\alpha)\mathbf{F}(\mathbf{x}_{*}^{\beta})+\Big{[}\alpha\mathbf{F}(\mathbf{x}_{*}^{\beta})+\frac{1}{2}(\mathbf{x}_{*}^{\beta})^{T}(I-W)\mathbf{x}_{*}^{\beta}\Big{]}.\end{split}$

Using the minimality of $\mathbf{x}_{*}^{\alpha}$ for $G_{\alpha}$ in the
right hand side, we find

$\begin{split}&\beta\mathbf{F}(\mathbf{x})+\frac{1}{2}\mathbf{x}^{T}(I-W)\mathbf{x}\\\
&\geq\frac{\mu\beta}{2\alpha_{0}}\|\mathbf{x}-\mathbf{x}_{*}^{\beta}\|^{2}+(\beta-\alpha)\mathbf{F}(\mathbf{x}_{*}^{\beta})+\Big{[}\alpha\mathbf{F}(\mathbf{x}_{*}^{\alpha})+\frac{1}{2}({\mathbf{x}_{*}^{\alpha}})^{T}(I-W)\mathbf{x}_{*}^{\alpha}\Big{]}.\end{split}$

Taking $\mathbf{x}=\mathbf{x}_{*}^{\alpha}$, we find

$\begin{split}&\beta\mathbf{F}(\mathbf{x}_{*}^{\alpha})+\frac{1}{2}(\mathbf{x}_{*}^{\alpha})^{T}(I-W)\mathbf{x}_{*}^{\alpha}\\\
&\geq\frac{\mu\beta}{2\alpha_{0}}\|\mathbf{x}_{*}^{\alpha}-\mathbf{x}_{*}^{\beta}\|^{2}+(\beta-\alpha)\mathbf{F}(\mathbf{x}_{*}^{\beta})+\alpha\mathbf{F}(\mathbf{x}_{*}^{\alpha})+\frac{1}{2}(\mathbf{x}_{*}^{\alpha})^{T}(I-W)\mathbf{x}_{*}^{\alpha},\end{split}$

which gives

$(\beta-\alpha)(\mathbf{F}(\mathbf{x}_{*}^{\alpha})-\mathbf{F}(\mathbf{x}_{*}^{\beta}))\geq\frac{\mu\beta}{2\alpha_{0}}\|\mathbf{x}_{*}^{\alpha}-\mathbf{x}_{*}^{\beta}\|^{2}.$
(3.1)

Notice that

$\mathbf{F}(\mathbf{x}_{*}^{\alpha})-\mathbf{F}(\mathbf{x}_{*}^{\beta})=(\mathbf{x}_{*}^{\alpha}-\mathbf{x}_{*}^{\beta})\cdot\int_{0}^{1}\nabla\mathbf{F}(\mathbf{x}_{*}^{\beta}+s(\mathbf{x}_{*}^{\alpha}-\mathbf{x}_{*}^{\beta}))ds.$

Therefore we have

$|\mathbf{F}(\mathbf{x}_{*}^{\alpha})-\mathbf{F}(\mathbf{x}_{*}^{\beta})|\leq
C_{1}\|\mathbf{x}_{*}^{\alpha}-\mathbf{x}_{*}^{\beta}\|.$

This together with (3.1) gives

$\frac{\mu\beta}{2\alpha_{0}}\|\mathbf{x}_{*}^{\alpha}-\mathbf{x}_{*}^{\beta}\|^{2}\leq
C_{1}|\beta-\alpha|\|\mathbf{x}_{*}^{\alpha}-\mathbf{x}_{*}^{\beta}\|.$

The proof is done. ∎

##  4\. Boundedness property

In this section, we make use of the properties of $\mathbf{x}_{*}^{\alpha}$
obtained in the previous section to study the sequence
$\\{\mathbf{x}(t)\\}_{t\geq 0}$ of the decentralized gradient descent (1.5).

######  Lemma 4.1.

Suppose that $G_{\alpha_{0}}$ is $\mu$-strongly convex for some
$\alpha_{0}>0$. Assume that
$\alpha(t)\leq\min\Big{\\{}\frac{1+\sigma_{n}(W)}{L},~{}\alpha_{0}\Big{\\}}$.
Then we have

$\|\mathbf{x}_{t+1}-\mathbf{x}_{*}^{\alpha(t+1)}\|\leq\|\mathbf{x}_{t}-\mathbf{x}_{*}^{\alpha(t)}\|+\frac{2\alpha_{0}C_{1}}{\mu\alpha(t)}|\alpha(t+1)-\alpha(t)|.$

###### Proof.

Note that $G_{\alpha}$ is $L_{G}$-smooth with $L_{G}=\alpha
L+(1-\sigma_{n}(W))$. Thus, if $\alpha\leq\frac{1+\sigma_{n}(W)}{L}$, then we
have $L_{G}\leq 2$. Note that

$\begin{split}&\|\mathbf{x}_{t+1}-\mathbf{x}_{*}^{\alpha}\|^{2}\\\
&=\|\mathbf{x}_{t}-\nabla
G_{\alpha}(\mathbf{x}_{t})-\mathbf{x}_{*}^{\alpha}\|^{2}\\\
&=\|\mathbf{x}_{t}-\mathbf{x}_{*}^{\alpha}\|^{2}-2\Big{\langle}\mathbf{x}_{t}-\mathbf{x}_{*}^{\alpha},~{}\nabla
G_{\alpha}(\mathbf{x}_{t})-\nabla
G_{\alpha}(\mathbf{x}_{*}^{\alpha})\Big{\rangle}+\|\nabla
G_{\alpha}(\mathbf{x}_{t})-\nabla
G_{\alpha}(\mathbf{x}_{*}^{\alpha})\|^{2}.\end{split}$

Since $G_{\alpha}$ is convex and $L_{G}$-smooth, we have

$\langle\mathbf{x}_{t}-\mathbf{x}_{*}^{\alpha},~{}\nabla
G_{\alpha}(\mathbf{x}_{t})-\nabla
G_{\alpha}(\mathbf{x}_{*}^{\alpha})\rangle\geq\frac{1}{L_{G}}\|\nabla
G_{\alpha}(\mathbf{x}_{t})-\nabla G_{\alpha}(\mathbf{x}_{*}^{\alpha})\|^{2}.$

Combining the above two estimates, we get

$\begin{split}\|\mathbf{x}_{t+1}-\mathbf{x}_{*}^{\alpha}\|^{2}&\leq\|\mathbf{x}_{t}-\mathbf{x}_{*}^{\alpha}\|^{2}-\Big{(}\frac{2}{L_{G}}-1\Big{)}\|\nabla
G_{\alpha}(\mathbf{x}_{t})-\nabla G_{\alpha}(\mathbf{x}_{*}^{\alpha})\|^{2}\\\
&\leq\|\mathbf{x}_{t}-\mathbf{x}_{*}^{\alpha}\|^{2}.\end{split}$

Using this with the triangle inequality and Theorem 1.7, we deduce

$\begin{split}\|\mathbf{x}_{t+1}-\mathbf{x}_{*}^{\alpha(t+1)}\|&\leq\|\mathbf{x}_{t+1}-\mathbf{x}_{*}^{\alpha(t)}\|+\|\mathbf{x}_{*}^{\alpha(t)}-\mathbf{x}_{*}^{\alpha(t+1)}\|\\\
&\leq\|\mathbf{x}_{t+1}-\mathbf{x}_{*}^{\alpha(t)}\|+\frac{2\alpha_{0}C_{1}}{\mu\alpha(t)}|\alpha(t)-\alpha(t+1)|.\end{split}$

The proof is done.

∎

In order to prove Theorem 1.6, we recall the following result from [6].

######  Theorem 4.2 ([6]).

Suppose that the total cost function $f$ is $\mu$-strongly convex for some
$\mu>0$ and each $f_{i}$ is $L$-smooth for $1\leq i\leq m$. If
$\\{\alpha(t)\\}_{t\in\mathbb{N}_{0}}$ is non-increasing stepsize satisfying
$\alpha(0)<\frac{\eta(1-\beta)}{L(\eta+L)}$, then we have

$\|\bar{\mathbf{x}}(t)-\mathbf{x}_{*}\|\leq R\quad
and\quad\|\mathbf{x}(t)-\bar{\mathbf{x}}(t)\|\leq\frac{\eta
R}{L}<R,\quad\forall t\geq 0.$ (4.1)

Here $\eta=\frac{\mu L}{\mu+L}$ and a finite value $R>0$ is defined as

$R=\max\left\\{\|\bar{\mathbf{x}}(0)-\mathbf{x}_{*}\|,~{}\frac{L}{\eta}\|\mathbf{x}(0)-\bar{\mathbf{x}}(0)\|,~{}\frac{\sqrt{m}D\alpha(0)}{\eta(1-\beta)/L-(\eta+L)\alpha(0)}\right\\}.$

Using the above lemma, we give the proof of the main theorem on the
boundedness property of the sequence $\\{\mathbf{x}(t)\\}_{t\geq 0}$.

###### Proof of Theorem 1.6.

Scine $F\in\mathbf{G}_{\alpha}$, the function $G_{\alpha}$ is $\mu$-strongly
convex for some $\mu>0$. Then we know that $f$ is
$\frac{\mu}{\alpha_{0}}$-strongly convex by Theorem 2.2. We set the following
constants

$\eta=\frac{(\mu/\alpha_{0})L}{(\mu/\alpha_{0})+L}\quad\textrm{and}\quad\mathbf{a}_{c}=\frac{\frac{\mu}{\alpha_{0}}(1-\beta)}{2L\Big{(}\frac{\mu}{\alpha_{0}}+L\Big{)}}=\frac{\mu(1-\beta)}{4L(\mu+\alpha_{0}L)}.$

Take a number $t_{0}\in\mathbb{N}$ such that $\alpha(t_{0})\geq\mathbf{a}_{c}$
and $\alpha(t_{0}+1)<\mathbf{a}_{c}$.

For $t\leq t_{0}$ we apply Lemma 4.1 to find

$\begin{split}\|\mathbf{x}_{t+1}-\mathbf{x}_{*}^{\alpha(t+1)}\|&\leq\|\mathbf{x}_{t}-\mathbf{x}_{*}^{\alpha(t)}\|+\frac{2C_{1}}{\alpha(t)}|\alpha(t+1)-\alpha(t)|\\\
&\leq\|\mathbf{x}_{t}-\mathbf{x}_{*}^{\alpha(t)}\|+\frac{2C_{1}}{\mathbf{a}_{c}}|\alpha(t+1)-\alpha(t)|.\end{split}$

Thus,

$\begin{split}\|\mathbf{x}_{t_{0}+1}-\mathbf{x}_{*}^{\alpha(t)}\|&\leq\|\mathbf{x}_{0}-\mathbf{x}_{*}^{\alpha(1)}\|+\frac{2C_{1}}{\mathbf{a}_{c}}\sum_{s=0}^{t_{0}}|\alpha(s+1)-\alpha(s)|\\\
&=\|\mathbf{x}_{0}-\mathbf{x}_{*}^{\alpha(0)}\|+\frac{2C_{1}}{\mathbf{a}_{c}}(\alpha(0)-\alpha(t_{0}+1)).\end{split}$

Note that

$\|\mathbf{x}_{t_{0}+1}\|\leq\|\mathbf{x}_{0}-\mathbf{x}_{*}^{\alpha(0)}\|+\frac{2C_{1}}{\mathbf{a}_{c}}\alpha(0)+\|\mathbf{x}_{*}^{\alpha(t_{0}+1)}\|.$

Therefore

$\|\bar{\mathbf{x}}_{t_{0}+1}-\mathbf{x}_{t_{0}+1}\|\leq\|\mathbf{x}_{0}-\mathbf{x}_{*}^{\alpha(0)}\|+\frac{2C_{1}}{\mathbf{a}_{c}}\alpha(0)+\|\mathbf{x}_{*}^{\alpha(t_{0}+1)}\|$

and

$\begin{split}\|\bar{\mathbf{x}}_{t_{0}+1}-\mathbf{x}_{*}\|&\leq\|\bar{\mathbf{x}}_{t_{0}+1}\|+\|\mathbf{x}_{*}\|\\\
&\leq\|\mathbf{x}_{0}-\mathbf{x}_{*}^{\alpha(0)}\|+\frac{2C_{1}}{\mathbf{a}_{c}}\alpha(0)+\|\mathbf{x}_{*}^{\alpha(t_{0}+1)}\|+\|\mathbf{x}_{*}\|.\end{split}$

Now we use the result of Theorem 4.2 to deduce that

$R=\max\left\\{\|\bar{\mathbf{x}}_{t_{0}+1}-\mathbf{x}_{*}\|,~{}\frac{L}{\eta}\|\mathbf{x}_{t_{0}+1}-\bar{\mathbf{x}}_{t_{0}+1}\|,~{}\frac{\sqrt{m}D\alpha(t_{0}+1)}{\eta(1-\beta)/L-(\eta+L)\alpha(t_{0}+1)}\right\\},$

then we have

$\|\bar{\mathbf{x}}(t)-\mathbf{x}_{*}\|\leq R\quad
and\quad\|\mathbf{x}(t)-\bar{\mathbf{x}}(t)\|\leq\frac{\eta
R}{L}<R,\quad\forall t\geq t_{0}+1.$ (4.2)

Here $\eta=\frac{\mu L}{\mu+L}$. We also check that

$\begin{split}\frac{\sqrt{m}D\alpha(t_{0}+1)}{\eta(1-\beta)/L-(\eta+L)\alpha(t_{0}+1)}&=\frac{\sqrt{m}D}{\frac{\eta(1-\beta)}{L\alpha(t_{0}+1)}-(\eta+L)}\\\
&\leq\frac{\sqrt{m}D}{\frac{\eta(1-\beta)}{L\mathbf{a}_{c}}-(\eta+L)}=\frac{\sqrt{m}D}{2(\eta+L)}.\end{split}$

The proof is finished. ∎

##  5\. Numerical experiments

In this section, we provide numerical experiments supporting the theoretical
results of this paper.

First we set $m=3$ and $n=2$ for problem (1.1). For each $1\leq k\leq m$, we
choose the local cost $f_{k}$ as

$f_{k}(x)=\frac{1}{2}x^{T}A_{k}x+B_{k}^{T}x.$

Here the matrix $A_{k}$ is an $n\times n$ symmetrix matrix chosen as

$A_{k}=\epsilon I_{n\times n}+(R_{k}+R_{k}^{T}),$

where $\epsilon>0$ and each element of $R_{k}$ is chosen randomly from
$[-1,1]$ with uniform distribution. Also, each element of
$B_{k}\in\mathbb{R}^{n}$ is randomly chosen in $[-1,1]$ with uniform
distribution. We choose $W$ as

$W=\begin{pmatrix}1/2&1/4&1/4\\\ 1/4&1/2&1/4\\\ 1/4&1/4&1/2\end{pmatrix}.$

In order to verify the result of Theorem 1.6, we compute the following
constants:

$\begin{split}\alpha_{A}&=\textrm{a possibly large value $\alpha_{0}>0$ such
that $F\in\mathbf{G}_{\alpha_{0}}$}\\\
\alpha_{L}&=\frac{1+\lambda_{m}(W)}{L}.\end{split}$

The detail for computing the above values are explained below:

  * •

To compute $\alpha_{A}$ we choose a large $N\in\mathbb{N}$ and set

$\alpha_{A}=\sup_{k\in\mathbb{N}}\Big{\\{}\frac{k}{N}>0~{}|~{}F\in\mathbf{G}_{(k/N)}\Big{\\}}.$

Since $G_{(k/N)}(x)$ is a quadratic function, we may check the positivity of
all eigenvalues of $\nabla^{2}G_{(k/N)}(x)$ to determine if the function
$G_{(k/N)}$ is strongly convex.

  * •

To find the smallest value of $L>0$, we compute $L_{k}=\|A_{k}\|_{\infty}$ by
using the eigenvalues of $A_{k}$. Then we set $L=\sup_{1\leq k\leq m}L_{k}$.

In our experiment, the constants are computed as

$\alpha_{A}\simeq 0.0799\quad\textrm{and}\quad\alpha_{L}\simeq 0.1721$

with $L\simeq 7.2615$ and $\lambda_{m}(W)=0.25$.

Since $\alpha_{A}<\alpha_{L}$, the range (1.7) of the stepsize $\alpha(t)$
guaranteed by Theorem 1.6 is given as

$\alpha(0)\leq\alpha_{A}.$

We take the constant stepsize $\alpha(t)\equiv\alpha>0$ with various choices
of $\alpha$ given as

$\\{0.5\alpha_{A},~{}0.95\alpha_{A},~{}0.99\alpha_{A},~{}1.01\alpha_{A},~{}1.01\\}.$

For each time step $t\geq 0$, we measure the following error

$R(t)=\sum_{k=1}^{m}\|x_{k}(t)-x_{*}\|,$

where $x_{k}(t)$ is the state of $k$ in (1.2) and $x_{*}$ is the optimizer of
(1.1).

Figure 2. The left (resp., right) figure corresponds to the graph of value
$\log R(t)$ (resp., $R(t)$) with respect to $t\geq 0$.

The result shows that the states $\\{x_{k}(t)\\}_{k=1}^{m}$ are uniformly
bounded for the three cases
$\alpha\in\\{0.5\alpha_{A},0.95\alpha_{A},0.99\alpha_{A}\\}$ as expected by
Theorem 1.6. Meanwhile, the states $\\{x_{k}(t)\\}$ diverges as
$t\rightarrow\infty$ for the choices
$\alpha\in\\{1.01\alpha_{A},1.02\alpha_{A}\\}$ which are larger than the value
$\alpha_{A}$. This shows the sharpness of the result of Theorem 1.6.

## References

  * [1] A. Berahas, R. Bollapragada, N. Keskar, E. Wei, E.: Balancing communication and computation in distributed optimization. IEEE Trans. Autom. Control 64, 3141–3155 (2019).
  * [2] S. Bubeck. Convex optimization: Algorithms and complexity. Foundations and Trends in Machine Learning, 8(3-4):231–357, 2015.
  * [3] X. Cao, T. Basar, Tamer Decentralized online convex optimization with feedback delays. IEEE Trans. Automat. Control 67 (2022), no. 6, 2889–2904.
  * [4] I.-A. Chen et al., Fast distributed first-order methods, Master’s thesis, Massachusetts Institute of Technology, 2012.
  * [5] W. Choi, D. Kim, S. Yun, Convergence results of a nested decentralized gradient method for non-strongly convex problems. J. Optim. Theory Appl. 195 (2022), no. 1, 172–204.
  * [6] W. Choi, J. Kim, On the convergence of decentralized gradient descent with diminishing stepsize, revisited, arXiv:2203.09079.
  * [7] T. T. Doan, S. T. Maguluri, and J. Romberg, Finite-time performance of distributed temporal difference learning with linear function approximation, SIAM J. Math. Data Sci., vol. 3, no. 1, pp. 298–320, 2021
  * [8] A. Nedić and A. Ozdaglar, Distributed subgradient methods for multi-agent optimization, IEEE Trans. Autom. Control 54 (2009), pp. 48–61.
  * [9] A. Nedić and A. Olshevsky, Distributed optimization over time-varying directed graphs, IEEE Trans. Autom. Control 60 (2015), pp. 601–615.
  * [10] S. Pu and A. Nedić, Distributed stochastic gradient tracking methods, Math. Program, pp. 1–49, 2018
  * [11] S. Pu, A. Olshevsky, I. Paschalidis, A sharp estimate on the transient time of distributed stochastic gradient descent. IEEE Trans. Automat. Control 67 (2022), no. 11, 5900–5915.
  * [12] S. S. Ram, A. Nedić, and V. V. Veeravalli, Distributed Stochastic Subgradient Projection Algorithms for Convex Optimization, Journal of Optimization Theory and Applications, 147, no. 3, pp. 516–545, 2010.
  * [13] K. Yuan, W. Xu, Q. Ling,Can primal methods outperform primal-dual methods in decentralized dynamic optimization? IEEE Trans. Signal Process. 68 (2020), 4466–4480.
  * [14] K. Yuan, Q. Ling, W. Yin, On the convergence of decentralized gradient descent. SIAM J. Optim., 26 (3), 1835–1854.
  * [15] S. Zeng, M. A. Anwar, T. T. Doan, A. Raychowdhury, and J. Romberg, “A decentralized policy gradient approach to multi-task reinforcement learning,” in Proc. Uncertainty Artif. Intell., 2021, pp. 1002–1012.


# A high sensitivity tool for geophysical applications: A geometrically locked
Ring Laser Gyroscope.

E. Maccioni  1,2 N. Beverini  1 G. Carelli  1,2,* G. Di Somma  1,2 A. Di
Virgilio  2 and P. Marsili1,2  1University of Pisa, Pisa, Italy, 2INFN Sezione
di Pisa, Pisa, Italy<EMAIL_ADDRESS>
###### Abstract

This work demonstrates that a middle size ring laser gyroscope (RLG) can be a
very sensitive and robust instrument for rotational seismology, even if it
operates in a quite noisy environment. The RLG has a square cavity,
$1.60\times 1.60$ m2, and it lies in a plane orthogonal to the Earth
rotational axis. The Fabry-Perot optical cavities along the diagonals of the
square were accessed and their lengths were locked to a reference laser.
Through a quite simple locking circuit, we were able to keep the sensor fully
operative for 14 days. The obtained long term stability is of the order of 3
nanorad/s and the short term sensitivity close is to 2 nanorad/s$\cdot$Hz-1/2.
These results are limited only by the noisy environment, our laboratory is
located in a building downtown.

††journal: osajournal††articletype: Research Article

##  1 Introduction

Large frame ring laser gyroscopes (RLG) are the most sensitive absolute
angular rotation sensors, they are able to combine the status of art
sensitivity with a bandwidth above 100 Hz, long term operation and very large
dynamic range. The same device can efficiently records extremely low amplitude
signals and large shocks. They are based on the Sagnac effect that appears as
a difference in the optical path between waves propagating in opposite
direction in a rotating closed loop. As a consequence, in a rotating RLG a
difference arises between the frequencies emitted by the laser in the two
opposite directions (Sagnac frequency). For a RLG rigidly connected to the
ground, the Earth rotation velocity is by far the dominant component of
$\Omega$.

Eq. (1) gives the general relation connecting the Sagnac frequency $f_{s}$,
and the modulus of the local angular rotation rate $\Omega$:

$f_{s}=4\frac{A}{P\lambda}\Omega\cdot\cos(\theta)$ (1)

where $A$ is the area enclosed by the optical path, $P$ is the ring perimeter
length, $\lambda$ the intracavity laser wavelength, and $\theta$ is the angle
between the area vector and the rotational axis.

Our prototype, GP2, is a square laser gyroscope with a perimeter of 6.40 m,
that is operative in a laboratory placed inside the basement of the Pisa INFN
building, see Fig.1.

Figure 1: GP2 gyroscope inside the building of the INFN Pisa section

It was built as a test bench to develop the optical and electronic
technologies that will be implemented in GINGER. The last is a very high
sensitivity three dimensional array of large frame RLGs, currently in the
design phase, which has the aim of verifying general relativity theories on a
laboratory scale [1]. Nevertheless, GP2 has also the aim of contributing to
the development of reduced scale RLGs (4 - 8 m in perimeter) with a bit lower
performance, devoted to geophysical and seismic applications.

The quality of the performances of a RLG are strictly related to the control
of the geometrical scale factor $S=4\frac{A}{P\lambda}\cos(\theta)$, and of
the laser kinematics. In a previous papers we addressed the complex problem of
the reduction of the non-linear laser dynamics perturbation [2, 3],
elaborating a procedure that was applied to the $3.60\times 3.60~{}$m2 RLG
"Gingerino", placed in the deep underground Gran Sasso laboratory.

In spite of its limitation, due to the reduced dimension and to the noisy
location, GP2 can give important information about the procedures for the
control of the scale factor, thanks to its peculiar properties. First of all,
the ring is oriented with its axis nearly parallel to the Earth axis, so that
the accuracy is improved and the disturbances induced on the Sagnac signal by
local tilting are minimized. Furthermore, the vacuum chamber includes also
additional pipes connecting the opposite mirrors along the two diagonals . In
this way, the four mirrors define, besides the square optical cavity, also two
Fabry-Pérot (FP) linear resonators along the diagonals, that can be used to
better define and control the ring geometry.

We already demonstrated in [4, 5] to be able to measure and to stabilize the
lengths of the diagonals of GP2 with a statistical accuracy of some tens of
nanometers. This results was obtained through an interferometric technique, by
using for each diagonal of a double Pound-Drever-Hall (PDH) control loop. In
this work we investigate the geometrical properties of GP2, by testing new
simplified procedures to measure and control the geometrical shape and the
scale factor that could be profitably applied to the reduced scale RLGs.

##  2 The apparatus

###  2.1 The mechanical structure

The optical cavity of GP2 is a square defined by four high-quality dielectric
mirrors. It is mounted inside a vacuum room composed by four corner chambers,
hosting the mirrors, connected, through bellows, by pipes along the sides and
the diagonals of the square. Each mirror is rigidly fixed to the chambers that
are mounted on a piezoelectric slide (PZT), screwed on a massive granite table
that warrants the stiffness of the apparatus. The PZTs can drive displacements
along the direction of the diagonals within an $80\ \mu$m range.

The whole vacuum volume is filled by a 6.4 millibar of He and 0.2 millibar of
a mixture of 20Ne and 22Ne, with a 1:1 ratio of the two isotopes. A pyrex
capillary, 5 mm inner diameter, is inserted halfway of one side where the gas
is excited by a capacitive rf discharge. In order to minimize the losses and
maximize the resonator quality factor, no windows are inserted inside the
laser optical paths. A getter-pump provides to keep clean from any
contamination the noble gas mixtures.

The granite slab is fixed on a concrete base, tilted in the N-S direction by
about $46.6^{\circ}$, which is the value of the local colatitude. Besides, in
order to have the ring axis oriented in the local meridian plane, it was taken
specific care of the positioning of the base .

###  2.2 The optics

We mounted very high quality mirrors 1" in diameter on GP2. Recently, we
changed the optics with respect to that reported in Ref. [4, 5], mounting a
more performing set of mirrors and realigning the optical cavity. The new
mirrors were tested, demonstrating at 45° s-polarized incidence a reflectivity
of 0.999995(1) and a transmission of 0.35(5) ppm, in accordance with the
supplier’s specifications. By means of ring-down measurements, the quality
factor of the ring cavity was obtained equal to approx$10^{12}$, corresponding
to overall losses of 100 ppm. Note that overall losses include also the losses
for diffraction in the capillary. The reflectivity of the mirrors at normal
incidence is quite lower, so that the Q factor of the FP optical cavities
along the diagonals is of the order of $10^{10}$. Also the reference
metrological laser (RfL) is presently a Winters Electro-Optics Helium-Neon
laser locked to a saturated absorption transition of molecular iodine.
Following the specification, the emission frequency is
$f_{Winter}=473~612~622.97\pm 0.01~$ MHz. By means of an optical hetherodyne
technique between the RLG emission beam and the reference laser on a fast
photo-diode we can measure the RLG frequency in the new alignment with an
accuracy of 1 MHz, limited by the RLG vibration noise.

###  2.3 Data acquisition and elaboration

The Sagnac interferometric signal is the beat note, obtained by a photo-diode,
between the clock-wise and counter-clock-wise beams. The two beams are
extracted by the same mirror, and the beat note is stored continuously at a
rate of 5 kSample/s. In parallel at the same rate, we also record the
intensity of the two counter-propagating beams ($monobeam~{}signals$) exiting
from a second mirror, see Fig.2. Data are elaborated off-line by a Matlab®
procedure in order to correct the interferometric signal for mirrors back-
scattering effects. Following the algorithms described in [2], we identify and
correct these effects by using the monobeam signals. The procedure can be
elaborated quickly, producing the reduced data quasi on-line, in a few
seconds, and includes the largest correction terms, usually referred as
backscatter noise. In a second step, [3] linear regression methods could be
applied to evaluate and correct the null-shift, related to the time evolution
of the losses of the laser optical resonator. This procedure requires the off-
line elaboration of extended sets of data, of the order of $10^{4}-10^{5}$ s.
However, in RLG equipped with high quality mirrors the effects are quite small
with a slow evolution time, and can be neglected at the Fourier frequencies of
interest in seismic applications, frequency window spanning from 0.01 to 100
Hz.

Figure 2: Operational setup for geometrical stabilization. AOM Acoustic
Optical Modulator; VCO Voltage Controlled Oscillator; PZT piezoelectric
device; PD photo diode; $I_{1t}$, $I_{2t}$ transmission signal of the diagonal
1 and 2 resonators; $V_{1}$, $V_{2}$ error signal of diagonal 1 and 2.

##  3 Stabilization of the RLG scale factor

In order to stabilize the scale factor $S$, the standard techniques are to
lock the ring perimeter length by comparing the RLG emission frequency with an
optical frequency standard or the RLG cavity FSR with a radio-frequency
standard. The presence of the two FP resonators along the square ring cavity
allows the implementation of a procedure that optimise the ring shape and
stabilize $S$ [6] by stabilizing the length of the two diagonals. Our
procedure acts symmetrically on the PZTs, moving the four mirrors along the
diagonal direction. It gives the advantage of keeping invariant the ring shape
and, as a consequence, the phase of the radiation back scattered by the
mirrors, which is the principal source of error due the non-linearity of the
laser kinematics.

The new simplified scheme is shown in Fig.2. The radiation coming from our RfL
is sent through two polarization maintaining single-mode fibers into the
Fabry-Pérot resonators build by the diagonal opposite mirrors to interrogate
the two diagonal FP. Into the fiber path is inserted an acousto-optics
modulator (AOM), operating around 200 MHz. Each FP transmission signal is
collected on a photodiode, then it’s amplified by a transimpendance modulus
and finally it’s sent to a data acquisition card National Instrument USB-6363.
A VCO sweeps the in-fiber AOM every 100 ms of some MHz. A LabVIEW program
visualises the two transmission signals. At the beginning of each run, the
PZTs that move the mirrors are manually driven by a DC voltage in order to
center the transmission peaks inside the AOM sweep. Eventually, the sweep is
reduced to about 1 MHz and the LabView program will calculate in two
independent parallel ways the voltage of the PZTs corresponding to the maxima
of the transmission signals, sending the error signal to the PZTs to close the
loop. The high frequency response of the servo loop is limited to a few tenths
of Hz, because each PZT slide must move the whole chamber mass, bigger than 2
kg.

We underline that the correction signal is sent symmetrically on the two PZTs
of each diagonal. This solution allows a correction of the temperature
dilation without deforming the geometry of the optical path, which would
affect the back-scattering phase.

Figure 3:  Allan plot of the Sagnac frequency relative to a run with active
locking condition 14 days long (blue points) and to a selected free running
3-hours recording (red circles)

##  4 Discussion of the experimental results

We compared Sagnac signal of two 2-days long runs, recorded respectively with
and without the active stabilization of the diagonals, in slightly different
environmental condition. The raw data were in both cases reduced for
backscattering. For the run without stabilization, we obtained a mean Sagnac
frequency value of 184.1593 Hz with a standard deviation of 0.0734 Hz, while
for the locked diagonals run, we find a mean Sagnac frequency value of
184.1327 Hz with a standard deviation of 0.0536 Hz. Moreover, in locked
condition no data point were lost in the whole run, while in the free running
case it was necessary to discard the 26% of the data.

The efficacy of the stabilization is further demonstrated in Fig. 3 that shows
the Allan plot of the Sagnac frequency relative to a 14 days long locked run.
No data were discarded and the Allan is certainly affected by the
environmental disturbances produced by the everyday activity. At high
frequency the signal is dominated by the environment vibration noise, while it
is achieved a long time stability better than $3\times 10^{-9}~{}$rad/s over
one day. By comparison, we superimpose the Allan plot of a selected time
interval (about two hours) in unlocked operation. Note that also in the best
condition of the free running mode it was possible to acquire a continuous set
of data without spikes or jumps for no more than two or three hours.

The location guesting GP2 is a building downtown and it’s quite noisy. An
evaluation of its instrumental sensitivity in locked configuration can be
deduced from the plots of Amplitude Spectral Density shown in Fig. 4,
calculated in selected lime interval with the lowest environment noise.

Figure 4: Amplitude Spectral Density calculated on two selected time intervals

A level of 2 nanorad/s/Hz-1/2 is achieved in 0.02-0.3 Hz range. Note that in
present configuration the high frequency locking efficiency is limited by the
PZT, as stated in section 3.

The technique described in the previous chapter allows the stabilization of
the ring geometry and of the scale factor of the RLG, but it does not give the
opportunity of optimizing the ring geometry following the procedure suggested
in [6]. For this purpose it is necessary to measure the absolute values of the
ring optical path and of the diagonals length. Knowing this quantities, it is
possible to evaluate an expected value of the scale factor $S$ and to compare
it with the measured one.

The perimeter of the optical path can be calculated as $p=nc/$FSR, where the
refraction index of the intracavity medium $n$ can be estimated as
$1+2.1\times 10^{-7}$ [7]. The ring laser FSR is measured by observing on a
fast photo-diode the frequency spectrum of the RLG emission while increasing a
bit the laser excitation up to the onset of a second longitudinal mode. We
find a ring $p=6.3963216$ m.

To measure the absolute diagonal length we described in Ref [4, 5] a complex
procedure requiring for each diagonal a double PDH locking circuit. Here we
used an alternative more simple method by eliminating the second PDH locking.
It is a less performing method, but it’s accurate enough for our purpose, . As
in [4], the diagonal are measured one at a time in sequence. The light beam
coming from the RfL is injected through polarization maintaining single-mode
fibers in the two diagonal resonators and the single diagonal resonance
frequency is locked to the RfL frequency through a PDH circuit. Then, through
an in-fiber EOM the laser radiation is frequency swept around a multiple of
the resonator FSR. A LabVIEW software analyzes the transmitted signal fitting
the data in order to find the central FSR resonance frequency. The diagonal
length is then given by $L=c/(2n$ FSR). We found a value of the lengths of
$2~261~341~\mu$m and $2~261~541~{}\mu$m, with an estimated error of the order
of 1 $\mu$m.

We can observe that the perimeter $p^{\prime}$ of a rhombus whose diagonals
are equal to the measured one, which is $p^{\prime}=6.396~{}320$ m,is almost
identical to the value $p=6.396~{}321~{}6$ found before.

By using the observed values of the diagonals and of the perimeter, we have
also calculated the expected value of the scale factor $S$ of the GP2,
assuming a perfect rhomboid shape, perfectly aligned to Earth rotation axis,
as: $S=4A/(\lambda p)$ where $A$ is the area enclose by the optical path. The
intracavity wavelength $\lambda$ is calculated as $c/f_{0}$, where
$f_{0}=473~612~683$ MHz is the frequency emitted by the RLG, measured beating
on a fast photodiode the RLG radiation against the RfL. Then, the scale factor
of the RLG is $S=4A/(\lambda p)=2.52768\times 10^{6}$, giving a theoretical
Sagnac frequency due to the Earth rotation rate $\Omega_{E}=7.29211586\times
10^{-5}$ rad/s : $f_{th}=S~\Omega_{E}=184.216Hz$.

This can be compared with an experimentally detected Sagnac frequency of
184.133 Hz. The difference could be consistent with a misalignment of the ring
resonator axis of $1.7^{\circ}$, but also with residual non compensation of
the laser non-linear dynamics.

##  5 Conclusions

Rotational seismology requires instrumentation able to provide long term
operation with sensitivity close to nrad/s and suitable response in the
frequency range from 0.01 to 100 Hz. Middle size RLGs, such as our GP2 RLG
prototype, have a simple and compact control apparatus and are suitable to be
installed in common geophysical observatories. This paper shows that they can
satisfy the listed requirements. The duty cycle of a RLG is limited in
principle by the dynamics of the laser, which is affected by mode jumps and
split mode operation. The duty cycle of our free running prototype is
effectively less than $80\%$. The control strategy, tested on GP2, allows to
recover the $100\%$ of the duty cycle in 14 days long continuous unattended
operation, without affecting the sensitivity response. Note that the present
work make use of an expensive metrological laser with an accuracy better then
$10^{-10}$ as reference length standard, but more simple commercially
available reference lasers with a stability of 1 part on $10^{7}$ can provide
a likewise efficient control for geophysical application.

##  6 Acknowledgments

Work funded by INFN

##  7 Disclosures

The authors declare no conflicts of interest.

## References

  * [1] A. D. V. Di Virgilio, J. Belfi, W.-T. Ni, N. Beverini, G. Carelli, E. Maccioni, and A. Porzio, “Ginger: A feasibility study,” The European Physical Journal Plus 132, 157 (2017).
  * [2] A. D. V. Di Virgilio, N. Beverini, G. Carelli, D. Ciampini, F. Fuso, and E. Maccioni, “Analysis of ring laser gyroscopes including laser dynamics,” The European Physical Journal C 79, 573 (2019).
  * [3] A. D. V. Di Virgilio, N. Beverini, G. Carelli, D. Ciampini, F. Fuso, U. Giacomelli, and E. Maccioni, “Identification and correction of sagnac frequency variations,” The European Physical Journal C 80 (2020).
  * [4] F. Stefani, N. Beverini, G. Carelli, D. Ciampini, A. Di Virgilio, F. Fuso, and E. Giacomelli, U.and Maccioni, “Long term stabilization of large frame laser gyroscopes,” in _3020nd European Frequency and Time Forum (EFTF),_ (IEEE, Torino, Italy, 2018), pp. 119–121.
  * [5] N. Beverini, G. Carelli, A. D. Virgilio, U. Giacomelli, E. Maccioni, F. Stefani, and J. Belfi, “Length measurement and stabilization of the diagonals of a square area laser gyroscope,” Classical and Quantum Gravity 37, 065025 (2020).
  * [6] R. Santagata, R. Beghi, J. Belfi, N. Beverini, D. Cuccato, A. Di Virgilio, A. Ortolan, A. Porzio, and S. Solimeno, “Optimization of the geometrical stability in square ring laser gyroscopes,” Classical and Quantum Gravity 32, 055013 (2015).
  * [7] R. B. Hurst, M. Mayerbacher, A. Gebauer, K. U. Schreiber, and J.-P. R. Wells, “High-accuracy absolute rotation rate measurements with a large ring laser gyro: establishing the scale factor,” Applied Optics 56, 1124 (2017).