# A Review on Generative Adversarial Networks for Data Augmentation in Person
Re-Identification Systems

Víctor Uc-Cetina1, Laura Álvarez-González2, Anabel Martin-Gonzalez1,
1 Universidad Autónoma de Yucatán - {uccetina<EMAIL_ADDRESS>
2 Universidad Autónoma de Yucatán -<EMAIL_ADDRESS>

(February 2023)

###### Abstract

Interest in automatic people re-identification systems has significantly grown
in recent years, mainly for developing surveillance and smart shops software.
Due to the variability in person posture, different lighting conditions, and
occluded scenarios, together with the poor quality of the images obtained by
different cameras, it is currently an unsolved problem. In machine learning-
based computer vision applications with reduced data sets, one possibility to
improve the performance of re-identification system is through the
augmentation of the set of images or videos available for training the neural
models. Currently, one of the most robust ways to generate synthetic
information for data augmentation, whether it is video, images or text, are
the generative adversarial networks. This article reviews the most relevant
recent approaches to improve the performance of person re-identification
models through data augmentation, using generative adversarial networks. We
focus on three categories of data augmentation approaches: style transfer,
pose transfer, and random generation.

##  1 Introduction

Re-identification of a person consists of the recognition of the same person
through videos obtained from different cameras with a non-overlapping range of
vision, captured at different moments in time. If we focus on the security
domain, every year the installation of security cameras in cities around the
world increases. The amount of images generated by these cameras every second
translates into the need for manually, semi-automatically or automatically
analysis of hundreds of hours of surveillance cameras by security forces.

Figure 1: Example of Market-1501 [15] images obtained by security cameras.
Images corresponding to the same person are marked with green borders. The low
resolution of the images prevent us from using automatic facial recognition
information.

In recent years, interest in the problem of re-identification has increased,
due to the fact that it is not possible to use biometric data for the
identification of a person, since the quality of the images does not allow a
clear definition of the facial data. Therefore, other image features must be
used, such as the structure of the body and clothing. Currently, different
neural network models have been proposed to improve the re-identification
performance, but to make these models work more efficiently, they need to be
trained with very diverse data. One way to artificially generate diverse data
is by means of generative adversarial networks (GANs) [6] which are capable of
generating synthetic data that can help to improve the performance of the re-
identification neural networks.

Training a basic GAN model involves two main steps:

  1. 1.

In the first step, we train a neural network to receive as input a vector of
randomly generated numbers, and produce as output the pixel values for a
synthetic image. This neural network is called the generator network. At the
same time, during this step, we train a second neural network, in this case,
the so-called discriminator network. The discriminator receives an image as
input and produce a classification as output, indicating whether the input
images is a real one or a fake one.

  2. 2.

In the second steps, we use the generator network to produce some fake images,
but we label them as real images, and we pass them to the discriminator
network. The discriminator network will produce an error signal, given that
the image is fake, but it is labelled as real one. This error signal is used
to further train the generator network, making it to produce more realistic
fake images.

These two steps are intertwined during several iterations until both networks
improve their performance to discriminate and generate fake images. In
general, It is not a trivial task to train GANs, especially considering the
large amounts of data and computational power needed. However, as we describe
in this article, there has been already some successful approaches.

On the other hand, due to the current increase in the amount of information
from video surveillance systems that has to be analyzed, the implementation of
an intelligent automatic analysis system is extremely important. In some
countries, such as China, advanced cameras with sufficient resolution to
extract unique face features are currently being used. However, since most
surveillance cameras generate low-resolution images, the option of generating
an automatic facial recognition system for re-identification is ruled out.

As it can be seen in Fig. 1, images are low-resolution, with variations in
lighting and contrast, in addition to other factors that make the re-
identification of people in images more complex, such as: the change of
clothing, whether or not the person is wearing a backpack or sweater, the
presence of obstacles or people in the background that limits the visibility
of the person of interest in an open space.

In order to support the development of re-identification neural networks,
different deep training libraries have been developed, such as Torchreid [19].
However, to achieve effective training of these models, a large amount of
correctly labeled data is needed. This constitutes one of the greatest
challenges for training efficient re-identification models. Currently, the
largest datasets are very limited because they do not contain a large number
of images. For example, two of the most important datasets, Market1501 and
DukeMTMC-reID have 1501 persons recorded on 6 different cameras and 702
persons recorded on 8 different cameras, respectively.

The purpose of this article is to review the most relevant data augmentation
methods based on the use of generative adversarial networks for people re-
identification, in such a way that it provides a reference guide to
researchers and engineers interested in this field.

##  2 MOST COMMON APPROACHES

Generative adversarial networks, proposed in 2014 by Ian Goodfellow et al.
[6], are capable of artificially generating images with great diversity. Over
time, new architectures have been generated that improve the quality of the
data generated, such as the CycleGan architecture, proposed in 2017 by Zhu et
al. [20]. Apart from improving the quality of the generated images, it manages
to transfer the style or domain of a group of images to another group, using
two generative adversarial networks.

The performance of adversarial generative networks has been improving year
after year, as new models have been proposed. This improvement has motivated
several researchers to start investigating the use of GANs for data
augmentation tasks. An important increase in the study of GANs for data
augmentation in the training of re-identification models can be noted since
2018. The most relevant approaches have been grouped into three categories,
corresponding to different methods used to generate new artificial images.

  1. 1.

Style transfer. New images are artificially generated from an input image,
using different styles, known also as domains. The styles are imposed on the
new images at the moment they are generated by neural networks previously
trained for that purpose. In the new generated images, you can see
modifications with respect to the input image, such as color, tone, and
lighting.

  2. 2.

Pose transfer. In this approach the inputs are one image of a real person and
the target posture that we want to impose on that person. The posture can be
specified whether as a heat map or by the joints that correspond to the
skeleton of the desired posture. The model is capable of generating the image
of the input person with the determined posture.

  3. 3.

Random generation. As its name suggests, methods in this category are less
constrained and they are focused on randomly generating synthetic images with
the only condition that the generated images should have similar
characteristics of those images in the dataset that we want to augment.

##  3 STYLE TRANSFER

Images obtained by cameras usually have different resolutions or are in
different positions. This can cause the lighting and tonality to vary, among
other aspects. One way to generate new data is by transferring from one domain
to another or adapting the domain, which is based on the idea of transferring
the style of one or more images to others without changing the structure nor
the background of the original images. Which means that there is no change in
the positions of the pixels, leaving the images exactly the same.

There are several ways of dealing with style transfer. CycleGAN [20] is a GAN
introduced in 2017. It is capable of learning the style of some images and
transferring it to other different images, that is, transferring the style
from one domain to another. This was a milestone within the generative
adversarial networks and as of 2018 a large number of works based on this
architecture began to appear. For instance in 2019, Zhong et al. [18] proposed
CamStyle for transferring the style of a security camera to that of another
camera. The newly proposed method based on CycleGAN can transfer the style
only between two domains, limiting the architecture in such a way that it is
necessary to generate a model for each pair of security cameras.

Following the same philosophy of transferring one style from another, Dai et
al. [4] proposed the cmGAN model focused on style transfer to convert RGB and
infrared camera images. It is the first method using a RGB-Infrared Cross-
Modality Re-ID Dataset which includes images from four infrared and two RGB
cameras. In this case, the generative adversarial network’s discriminator is
part of the feature extractor of the re-identification model. The input to the
re-identification model is an infrared image and the target person needs to be
searched within the RGB images.

All these methods mentioned so far have the limitation of only transferring a
style from one domain A to another domain B, which results in the need to
duplicate the project for each different style. Furthermore, one of the
biggest challenges faced by the models of re-identification is the poor
performance obtained when images from one database are used during the testing
of a re-identification model trained with images from another database.
Therefore, some works propose the transfer of domains between different
databases and/or multiple domains.

In 2018, as an improvement to the Camstyle architecture and seeking better
performance using the model in different databases, the M2M-GAN [9]
architecture is proposed, which classifies the images of each database into
subdomains, that is, for each of the cameras. Being able to transfer the sub-
domain of domain A to a sub-domain of domain B, the training being carried out
in a supervised manner and requiring that all the data from the different
databases have been labeled by hand.

As of 2019, different more sophisticated architectures began to appear, such
as the one proposed by Zheng et al. [16], DG-NET, which uses two encoders that
are capable of extracting the colors of the image, appearance, and transfer
those colors to another image where the structure of the person has been
extracted . This model also uses the adversarial generative network’s own
architecture as a re-identification model (see Fig. 2).

Figure 2: Style transfer. In this example of DE-GAN [16], the algorithm
transfers the appearance of the image on the left to all images on the right,
combining appearance and structure.

Some architectures can be trained to differentiate between different colors of
clothing and preserves the coherence of identity of the same person with the
color of clothing. Such color-aware architectures are capable of
differentiating and modifying the different colors of upper clothing
(sweatshirts/t-shirts) or lower clothing (pants).

Zhiqi Pang et al. [11] in the year 2021 proposed a hybrid method, supervised
and unsupervised. This method uses a novel architecture TC-GAN to generate
labelled artificial images, transferring the person from the input image to
the background of the target style image. They also proposed the use of the
DFE-Net re-identification model that uses a modified version of the ResNet-50
network, pretrained with the ImageNet database that has as input the real
images without tag and artificially generated ones. It uses the network as an
image feature extractor for later comparison.

##  4 POSE TRANSFER

One of the biggest challenges within the re-identification problem is the
great variation in the posture of a person that can be seen in different
cameras. To mitigate this problem, the generation of new data of the same
person is proposed, modifying the posture using different architectures. In
this approach, the data augmentation process is based on the generation of new
data through the extraction of the person in the original image, which can be
done by obtaining joints or heat maps. The pose transfer is obtained with the
help of the original image and those generated maps encapsulating the posture
information.

In 2018, Qian et al. [12] proposed the PN-GAN architecture. It is capable of
generating artificial images by means of the image of a person in eight
different postures. The eight canonical postures are obtained using the
k-means algorithm on the distribution of all the images in the database. To
generate the template, the open pose [3] estimator tool is used, which is
capable of detecting 18 joints of the human body and their joints. Through the
articulation map of both images it is able to transfer the posture of each one
of the eight canonical postures to the input images, as illustrated in Fig. 3.

Figure 3: Pose transfer. A new image of the person is generated from an input
image and the skeleton and the heat map of the desired posture.

In 2019, Borgia et al. [2] following the same line as the previous
architecture and extracting the joints using also the open pose method, they
propose an architecture which, instead of evaluating a single image, it
evaluates video footage of a person’s movement. Eight canonical postures are
predefined: three looking forward, three from behind, one in profile looking
to the right side and another to the left side. In the first place, the video
sequences of a person are obtained and the corresponding images with the
canonical postures are searched by means of the Euclidean distance, if any of
those eight postures does not exist, the artificial image will be generated.
The same happens with all the people that are in the video, their sequences
are obtained and if there is no canonical position it generates it, by means
of the cosine distance they compare the eight corresponding images with the
eight canonical postures of the input person with all the other sequence of
images of people. A classification is made and the one with the smallest
cosine distance is assigned as if it were the same person in the re-
identification model.

In 2020, Zhang et al. [14] proposed PAC-GAN. It consists of two models, the
first is CPG-Net, through the use of a conditional GAN, it is capable of
generating artificial images of a person from a camera A, and converting it to
the point of view of another camera B. The data is increased by generating new
images with postures from different points of view of different cameras. It
trains with the joints generated with Open Pose and the image itself.

More recently, in 2021, Ziyang et al. [10] proposed a new architecture which
is capable of correcting images in such a way that the images of people are
centered and straight. For this, the database was trained in such a way that
the images with the correct positions were indicated.

##  5 RANDOM GENERATION

The third major approach consists in generating random images of persons, with
different postures, lighting, colors and backgrounds (see Fig. 4). After the
images has been generated, different methods are used to automatically label
them. Finally the labelled images are used for training the re-identification
model.

Figure 4: Random generation. On the left, real images taken from the
Market-1501 [15] database. On the right, artificial images randomly generated
with StyleGAN3 [8].

One of the main algorithms for the automatic labeling of the random images is
called Label Smooth Regularization (LSR) and it was proposed in 2015 by
Szegedy et al. [13]. This algorithm was originally used in an image
classification problem.

Later on, in 2017, Zheng et al. [17] used a Deep Convolutional GAN (DCGAN)
together with the LSR algorithm to generate images and label them. They called
this method Label Smooth Regularization for Outliers (LSRO) and it assigns the
artificially generated images the same value in all classes, that is, it is
uniformly distributed throughout all classes. The same year, Ainam et al. [1]
proposed the use of the k-means algorithm to group the images for the training
set of a DCGAN. They also introduced the Sparse Label Smoothing Regularization
(SLSR) , which is based on the LSRO labeling method. It labels the
artificially generated images using the groups generated by k-means.

Interpolation of images has been also successfully tried. Eom et al. [5]
proposed a new GAN architecture called Identity Shuffle GAN (IS-GAN). In this
method, the generation of artificial images is through of the interpolation
between two real images, being able to distinguish between the upper and the
lower part. The labels of the artificial image will be the same as the images
that have generated the interpolation.

More recently, in 2021, Hussin et al. 2021 [7] proposed the use of the
StyleGAN [8] for the generation of new data. First, StyleGAN is trained with
some of the most popular datasets for people re-identification. Once StyleGAN
has been trained, a set of new artificial images is generated. Finally, the
generated images are labelled using the LSRO method.

##  6 DISCUSSION

Data augmentation is a difficult task in any domain and the re-identification
domain is not the exception. In this article we have reviewed the most
relevant approaches for data augmentation in person re-identification systems
which employ generative adversarial networks. We have categorized all the
reviewed methods in three groups: style transfer, pose transfer, and random
generation of images.

Neither of these approaches can be regarded as the best one. The kind of
application may indicate the use of one approach over the other. For example,
a re-identification system operating inside a shop with controlled light
conditions might require a data augmentation based on pose transfer, meanwhile
an re-id application for outdoors surveillance might benefit more from style
transfer models. In Table 1 we provide the summary of all the methods here
reviewed.

GAN Model | Approach
---|---
CycleGAN [20] | Style transfer
CamStyle [18] | Style transfer
cmGAN [4] | Style transfer
M2M-GAN [9] | Style transfer
DG-NET [16] | Style transfer
TC-GAN + DFE-Net [11] | Style transfer
PN-GAN [12] | Pose transfer
WF+WPR [2] | Pose transfer
PAC-GAN [14] | Pose transfer
GAN + CNN + STN [10] | Pose transfer
LSR [13] | Random generation
DCGAN + LSR [17] | Random generation
k-means + DCGAN SLSR [1] | Random generation
IS-GAN [5] | Random generation
StyleGAN [8] [7] | Random generation
Table 1: Summary of GAN approaches to data augmentation in person re-
identification.

Moreover, even though good advances have been achieved so far with these
approaches to data augmentation, we must keep in mind that generative
adversarial networks are not trivial models to train and fine-tune. Common
problems that researchers generally encounter when training GANs, such as mode
collapse and training instability, are also very likely to appear when
learning to augment a re-identification dataset.

Mode collapse occurs when the generator network becomes less and less diverse
as the number training iterations increases. Basically, the generator improves
the quality of one specific category of fake images that it produces, for
example, women images, and begins to produce almost exclusively women images.
Consequently, the discriminator network begins to experience only fake images
of women and it also starts to forget to discriminate other category of
images, for example, men images. With time, when the discriminator manages to
discriminate images of women, the generator is forced to start producing
another category of images, for example children images. This problem causes
the GAN to cycle around a few number of categories, never becoming good in all
the required categories.

The training instability problem has to do with the mere fact of training two
neural networks at the same time, in a way that the good performance of one
network depends on the good performance of the other. In such training
dependency, it is very easy for the whole system to get trapped into an
unstable phase, in which all network’s parameters oscillate. Very often, the
training process might seem to be going very well and then, from one iteration
to the other, the performance drops unexpectedly, without no clear reason.
Under these circumstances, a lot of fine-tuning is necessary, in order to find
an optimal set of hyperparameters.

Regarding the quality of each approach, rather than saying that one method is
better that the other, we provide a list of advantages and disadvantages in
Tables 2, 3 and 4, for style transfer, pose transfer and random generation,
respectively. The selection of one approach over the other depends on several
factors. Some of the main factors include: the specific application of the re-
identification system, the size of the dataset, the resolution of the images,
and the computational power available for training the models (see Fig. 5).

Figure 5: The selection of the best approach depends on several conditions
such as the application of the Re-ID system, the size of the dataset, the
quality of the images and the computational resources available.

GAN Model | Advantage | Disadvantage
---|---|---
CycleGAN [20] |  Image paired examples are not needed. |  Results are not uniformly positive. It works better for translations involving color and texture than geometric changes.
CamStyle [18] |  It reduces the risk of deep network overfitting and that smooths the CamStyle disparities. |  It cannot directly handle multi-domain image-to-image translation methods.
cmGAN [4] |  It focuses on Re-ID between infrared and RGB images and it can be trained in an end-to-end manner. |  It was tested only for infrared-RGB translations.
M2M-GAN [9] |  It solves the many-to-many cross-domain transfer learning with less training time, fewer parameters and a better performance. |  For every training example image, it needs the source and target sub-domain labels. This could represent a problem if we do not have those labels.
DG-NET [16] |  It separately encodes each person into an appearance code and a structure code. |  The generative module tends to learn regular textures such as stripes and dots, but it ignores some rare patterns such as logos on shirts.
TC-GAN \+ DFE-Net [11] |  It effectively combines supervised and unsupervised learning. |  Training this model can take longer than some of the methods studied in their comparative work.

Table 2: Summary of advantages and disadvantages of style transfer approaches.

GAN Model | Advantage | Disadvantage
---|---|---
PN-GAN [12] |  It can generalize to re-id datasets collected from new cameras without model fine-tuning. |  In a transfer learning setting, the reported results are lower than those in a supervised setting, which is expected due to the complexity of the task.
WF+WPR [2] |  It mitigates the effects of the inter-camera viewpoint problem. |  It relies on a network with a depth of around 1/3 of ResNet50, which could reduce its performance.
PAC-GAN [14] |  It does not require labeled data for training. |  The computation needed for generating a larger number of authentic samples is very expensive.
GAN + CNN \+ STN [10] |  It learns features containing global information as well as local detailed properties. |  The least performance improvement occurs with the region of the legs and feet of a person.

Table 3: Summary of advantages and disadvantages of pose transfer approaches.

GAN Model | Advantage | Disadvantage
---|---|---
LSR [13] |  It prevents the largest logit in convolutional networks from becoming much larger than all others. |  It is a general-purpose method for training convolutional networks and it was not specifically designed for data augmentation.
DCGAN + LSR [17] |  It is complementary to previous methods due to the regularization of the GAN data. |  This method is more focused on the regularization ability of the GAN than on producing a state-of-the-art result.
k-means + DCGAN SLSR [1] |  It exploits the clustering property of person re-id datasets and creates groups of similar objects in order to model cross-view variations. |  It needs thousands of labels to better handle a practical environment scenario.
IS-GAN [5] |  It disentangles identity-related and indentity-unrelated features from person images. |  This method does not have a particular reported disadvantage, other than ignoring features related to the persons’ identities.
StyleGAN [8] [7] |  With high-resolution images, the success rate increases. |  StyleGAN requires huge computational resources for training.

Table 4: Summary of advantages and disadvantages of random generation
approaches.

##  7 CONCLUSION

In this article we have reviewed three of the most common approaches for data
augmentation in person re-identification systems which employ generative
adversarial networks for style transfer, pose transfer, and random generation
of images. We have included in this review, what we consider to be the most
relevant and successful ways to augment image datasets for the task of re-
identifying people. This is of course not a exhaustive survey, but a reference
guide to researchers or engineers interested in this field.

Finally, although data augmentation for re-identification systems is nowadays
possible through the use of generative adversarial networks, using the
approaches above mentioned, it is important to consider that this task may
require an important amount of expertise in implementating, training and fine-
tuning generative adversarial models.

## References

  * [1] J. P. Ainam, K. Qin, G. Liu, and G. Luo.  Sparse Label Smoothing Regularization for Person Re-Identification.  IEEE Access, 7:27899–27910, 2019.
  * [2] A. Borgia, Y. Hua, E. Kodirov, and N. M. Robertson.  GAN-based Pose-aware Regulation for Video-based Person Re-identification.  2019\.
  * [3] Z. Cao, T. Simon, S. E. Wei, and Y. Sheikh.  Realtime multi-person 2D pose estimation using part affinity fields.  Proceedings - 30th IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2017, 2017-Janua:1302–1310, 2017.
  * [4] P. Dai, R. Ji, H. Wang, Q. Wu, and Y. Huang.  Cross-modality person re-identification with generative adversarial training.  IJCAI International Joint Conference on Artificial Intelligence, 2018-July:677–683, 2018.
  * [5] C. Eom and B. Ham.  Learning disentangled representation for robust person re-identification.  Advances in Neural Information Processing Systems, 32, 2019.
  * [6] I. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio.  Generative adversarial nets.  In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K. Weinberger, editors, Advances in Neural Information Processing Systems, volume 27. Curran Associates, Inc., 2014.
  * [7] S. H. S. Hussin and R. Yildirim.  StyleGAN-LSRO Method for Person Re-identification.  IEEE Access, pages 13857–13869, 2021.
  * [8] T. Karras, M. Aittala, S. Laine, E. Härkönen, J. Hellsten, J. Lehtinen, and T. Aila.  Alias-Free Generative Adversarial Networks.  (NeurIPS), 2021.
  * [9] W. Liang, G. Wang, J. Lai, and J. Zhu.  M2M-GAN: Many-to-Many Generative Adversarial Transfer Learning for Person Re-Identification.  2018\.
  * [10] Z. Ni, J. Pei, and Y. Zhao.  Affine transform for skew correction based on generative adversarial network method for multi-camera person re-identification.  ACM International Conference Proceeding Series, PartF16898:89–95, 2021.
  * [11] Z. Pang, J. Guo, W. Sun, Y. Xiao, and M. Yu.  Cross-domain person re-identification by hybrid supervised and unsupervised learning.  Applied Intelligence, 2021.
  * [12] X. Qian, Y. Fu, T. Xiang, W. Wang, J. Qiu, Y. Wu, Y.-G. Jiang, and X. Xue.  Pose-Normalized Image Generation for Person Re-identification.  The European Conference on Computer Vision (ECCV), pages 650–667, 2018.
  * [13] C. Szegedy, V. Vanhoucke, S. Ioffe, J. Shlens, and Z. Wojna.  Rethinking the Inception Architecture for Computer Vision.  Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2016-Decem:2818–2826, 2016.
  * [14] C. Zhang, L. Zhu, S. C. Zhang, and W. Yu.  PAC-GAN: An effective pose augmentation scheme for unsupervised cross-view person re-identification.  Neurocomputing, 387:22–39, 2020.
  * [15] L. Zheng, L. Shen, L. Tian, S. Wang, J. Wang, and Q. Tian.  Scalable Person Re-identification : A Benchmark University of Texas at San Antonio.  Iccv, pages 1116–1124, 2015.
  * [16] Z. Zheng, X. Yang, Z. Yu, L. Zheng, Y. Yang, and J. Kautz.  Joint discriminative and generative learning for person re-identification.  Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2019-June:2133–2142, 2019.
  * [17] Z. Zheng, L. Zheng, and Y. Yang.  Unlabeled Samples Generated by GAN Improve the Person Re-identification Baseline in Vitro.  Proceedings of the IEEE International Conference on Computer Vision, 2017-Octob:3774–3782, 2017.
  * [18] Z. Zhong, L. Zheng, Z. Zheng, S. Li, and Y. Yang.  CamStyle: A Novel Data Augmentation Method for Person Re-Identification.  IEEE Transactions on Image Processing, 28(3):1176–1190, 2019.
  * [19] K. Zhou and T. Xiang.  Torchreid: A library for deep learning person re-identification in pytorch, 2019.
  * [20] J. Y. Zhu, T. Park, P. Isola, and A. A. Efros.  Unpaired Image-to-Image Translation Using Cycle-Consistent Adversarial Networks.  Proceedings of the IEEE International Conference on Computer Vision, 2017-Octob:2242–2251, 2017.


# Resource Allocation with Subcarrier Pairing in OFDMA Two-Way Relay Networks

Hao Zhang, Yuan Liu, , and Meixia Tao Manuscript received November 16, 2011.
The associate editor approving it for publication was Dr. Harish
Viswanathan.The authors are with the Department of Electronic Engineering at
Shanghai Jiao Tong University, Shanghai, 200240, P. R. China (e-mail:
{gavinzhanghao, yuanliu, mxtao}@sjtu.edu.cn).This work was supported by the
NSF of China (60902019) and the Innovation Program of Shanghai Municipal
Education Commission (11ZZ19).

###### Abstract

This study considers an orthogonal frequency-division multiple-access
(OFDMA)-based multi-user two-way relay network where multiple mobile stations
(MSs) communicate with a common base station (BS) via multiple relay stations
(RSs). We study the joint optimization problem of subcarrier-pairing based
relay-power allocation, relay selection, and subcarrier assignment. The
problem is formulated as a mixed integer programming problem. By using the
dual method, we propose an efficient algorithm to solve the problem in an
_asymptotically_ optimal manner. Simulation results show that the proposed
method can improve system performance significantly over the conventional
methods.

###### Index Terms:

Two-way relaying, subcarrier pairing, resource allocation, orthogonal
frequency-division multiple-access.

##  I Introduction

An important property of orthogonal frequency-division multiplexing
(OFDM)-based relaying is that the frequency diversity can be exploited by
_subcarrier pairing_ , which matches the incoming and outgoing subcarriers at
the relay based on channel dynamics and hence improves system performance. In
multi-user environments with orthogonal frequency-division multiple-access
(OFDMA), subcarriers should not only be carefully paired at the relay but also
be assigned adaptively for different users. If with multiple relays, it
further complicates the problem because relay selection tightly couples with
subcarrier pairing and assignment. Thus, subcarrier-pairing based resource
allocation in multi-user multi-relay OFDMA networks is highly challenging.

Subcarrier-pairing based resource allocation has been originally investigated
for single-user single-relay one-way communications (e.g., [1, 2]). In
particular, it is proved in [1] that the _ordered pairing_ is optimal for
amplify-and-forward (AF) protocol. Authors in [3] investigated _separated_
power allocation and subcarrier pairing in two-way communication using single
relay, where the power allocation is first employed by water-filling and then
subcarriers are paired at the relay by a heuristic method. In [4], the
subcarrier-pairing based joint optimization of power allocation, relay
selection and subcarrier assignment for single-user multi-relay systems was
studied. The subcarrier-pairing based joint optimization of power allocation
and subcarrier-user assignment for multi-user single-relay scenario was
studied in [5]. In [6], the authors studied relay-assisted bidirectional OFDMA
cellular networks, wherein the subcarrier-pairing based joint optimization of
bidirectional transmission mode selection, relay selection, and subcarrier
assignment was investigated by a graph approach. Authors in [7] investigated
the jointly optimal channel and relay assignment for multi-user multi-relay
two-way relay networks. These works [6, 7], however, did not consider power
allocation.

In this work, we consider an OFDMA two-way relay network with a common base
station (BS), multiple mobile stations (MSs) and multiple relay stations
(RSs). The downlink and uplink traffic for each MS is multiplexed through
analog network coding at the RSs. We formulate a joint optimization problem of
subcarrier-pairing based relay-power allocation, relay selection, and
subcarrier assignment. The problem is a mixed integer programming problem and
we solve it efficiently in dual domain with polynomial complexity.

Figure 1: System model.

##  II System Model and Problem formulation

We consider a single-cell OFDMA two-way relay network, as shown in Fig. 1,
with one BS, multiple MSs and RSs. All the MSs are assumed to be cell-edge
users so that both the downlink and uplink traffic of each user needs to be
relayed through one or more RSs. This assumption is commonly used for cellular
relay networks in the literature (e.g., [5, 8, 9]). Each RS operates in a
half-duplex mode and relays the bi-directional traffic using AF protocol,
known as analog network coding. In specific, the AF two-way relay protocol
takes place in two phases [10]. In the first phase, also known as multiple-
access (MAC) phase, all the MSs and the BS concurrently transmit signals while
al the RSs listen. In the second phase, known as broadcast (BC) phase, the RSs
amplify the received signals and then forward them to the MSs and the BS. To
avoid multi-user interference, each MS and RS operate in non-overlapping
subcarriers in the first and second phases, respectively. The downlink-uplink
interference within each user is eliminated by self-interference cancelation.
Furthermore, the channel is assumed to be slowly time-varying and all the
channel state information can be perfectly estimated and known at the BS for
centralized processing.

Let $\mathcal{N}=\\{1,2,\cdot\cdot\cdot,N\\}$ denote the set of subcarriers,
$\mathcal{K}=\\{1,2,\cdot\cdot\cdot,K\\}$ denote the set of RSs, and
$\mathcal{U}=\\{1,2,\cdot\cdot\cdot,M\\}$ denote the set of MSs. The channel
coefficients from BS $b$ and MS $u$ to RS $k$ on subcarrier $i$ in the MAC
phase are denoted as $h_{b,k,i}$ and $f_{u,k,i}$, respectively, $\forall
u\in\mathcal{U},k\in\mathcal{K},i\in\mathcal{N}$. In the BC phase, the channel
coefficients from RS $k$ to BS $b$ and MS $u$ on subcarrier $j$ are denoted as
$h_{k,b,j}$ and $f_{k,u,j}$, respectively, $\forall
u\in\mathcal{U},k\in\mathcal{K},j\in\mathcal{N}$. Here channel reciprocity is
used, which is valid in TDD (time-division duplex) mode. Along with the paths,
we further denote $p_{b,k,i}$ and $p_{u,k,i}$ as the transmitted power of BS
$b$ and MS $u$ respectively, and $p_{k,u,j}$ as the transmitted power of RS
$k$. Then, the sum-rate of uplink-downlink transmission of MS $u$ over
subcarrier pair $(i,j)$ with the assistance of RS $k$ can be expressed as [10,
3]

$\begin{split}R_{u,k,i,j}=&\frac{1}{2}\log_{2}\left(1+\frac{p_{u,k,i}|f_{u,k,i}|^{2}p_{k,u,j}|h_{k,b,j}|^{2}}{p_{k,u,j}|h_{k,b,j}|^{2}+m_{u,k,i}}\right)\\\
+&\frac{1}{2}\log_{2}\left(1+\frac{p_{b,k,i}|h_{b,k,i}|^{2}p_{k,u,j}|f_{k,u,j}|^{2}}{p_{k,u,j}|f_{k,u,j}|^{2}+m_{u,k,i}}\right),\end{split}$
(1)

in which $m_{u,k,i}=1+p_{b,k,i}|h_{b,k,i}|^{2}+p_{u,k,i}|f_{u,k,i}|^{2}$. It
can be proved that the sum-rate $R_{u,k,i,j}$ is concave in the relay power
$p_{k,u,j}$.

We then introduce a set of binary variables $\rho_{u,k,i,j}\in\\{0,1\\}$ for
all $u$, $k$, $i$, $j$. When $\rho_{u,k,i,j}=1$, it means that subcarrier $i$
in the MAC phase is paired with subcarrier $j$ in the BC phase and they are
used by RS $k$ to relay the signals of MS $u$. Otherwise, we have
$\rho_{u,k,i,j}=0$. These binary variables must satisfy the following
constraints, due to the exclusive subcarrier assignment,

$\displaystyle\sum_{u=1}^{M}\sum_{k=1}^{K}\sum_{j=1}^{N}\rho_{u,k,i,j}$
$\displaystyle\leq$ $\displaystyle 1,~{}\forall i,$ (2)
$\displaystyle\sum_{u=1}^{M}\sum_{k=1}^{K}\sum_{i=1}^{N}\rho_{u,k,i,j}$
$\displaystyle\leq$ $\displaystyle 1,~{}\forall j.$ (3)

For simplicity, we study relay-power allocation and let the transmit power of
the BS and MSs be fixed. Each RS is subject to its own peak power constraint.
This can be expressed as:

$\displaystyle\sum_{u=1}^{M}\sum_{j=1}^{N}p_{k,u,j}\leq P_{k},~{}\forall k,$
(4)

where $P_{k}$ is the peak power constraint of RS $k$.

Our objective is to maximize the system total weighted throughput by jointly
optimizing the assignment variables $\\{\rho_{u,k,i,j}\\}$ and the relay power
variables $\\{p_{k,u,j}\\}$. Mathematically, this can be formulated as:

$\displaystyle\max_{\\{\boldsymbol{p},\boldsymbol{\rho}\\}}\sum_{u=1}^{M}w_{u}\sum_{k=1}^{K}\sum_{i=1}^{N}\sum_{j=1}^{N}\rho_{u,k,i,j}R_{u,k,i,j}(p_{k,u,j})$
(5)
$\displaystyle\textit{s.t.}~{}~{}(\ref{eqn:t1}),(\ref{eqn:t2}),(\ref{eqn:p}),$

where $w_{u}$ is the weight that represents the priority of MS $u$,
$\boldsymbol{p}\in\mathbb{R}_{+}^{K\times M\times N}$ and
$\boldsymbol{\rho}\in\\{0,1\\}^{M\times K\times N\times N}$ are matrices with
entries $p_{k,u,j}$ and $\rho_{u,k,i,j}$, respectively.

##  III Dual Based Algorithm

We first define $\mathcal{T}$ as the set of all possible $\boldsymbol{\rho}$
satisfying (2) and (3), $\mathcal{P}$ as the set of all possible power
allocations $\boldsymbol{p}$ for the given $\boldsymbol{\rho}$ that satisfy
$p_{k,u,j}\geq 0$ for $\rho_{u,k,i,j}=1$ and $p_{k,u,j}=0$ for
$\rho_{u,k,i,j}=0$. Denote
$\boldsymbol{\lambda}=(\lambda_{1},\lambda_{2},...,\lambda_{K})\succeq 0$ as
the dual variables associated with the peak power constraints of the RSs. Then
the dual function of the problem in (5) can be defined as

$\displaystyle
g(\boldsymbol{\lambda})\triangleq\max_{\begin{subarray}{\boldsymbol{missing}}{p}\in\mathcal{P}(\boldsymbol{\rho})\\\
\boldsymbol{\rho}\in\mathcal{T}\end{subarray}}L(\boldsymbol{p},\boldsymbol{\rho},\boldsymbol{\lambda}),$
(6)

where the Lagrangian is

$\displaystyle L(\boldsymbol{p},\boldsymbol{\rho},\boldsymbol{\lambda})$
$\displaystyle=$
$\displaystyle\sum_{u=1}^{M}w_{u}\sum_{k=1}^{K}\sum_{i=1}^{N}\sum_{j=1}^{N}R_{u,k,i,j}(p_{k,u,j})$
(7)
$\displaystyle+\sum_{k=1}^{K}\lambda_{k}\left(P_{k}-\sum_{u=1}^{M}\sum_{j=1}^{N}p_{k,u,j}\right).$

Computing the dual function $g(\boldsymbol{\lambda})$ requires us to determine
the optimal $({\boldsymbol{p},\boldsymbol{\rho}})$ at the given dual vector
$\boldsymbol{\lambda}$. In the following we present the derivations in detail.

###  III-A Optimizing the Primal Variables
$(\boldsymbol{p},\boldsymbol{\rho})$ for Given $\boldsymbol{\lambda}$

We first find the optimal power variables $\boldsymbol{p}$ by fixing the
binary assignment variables $\boldsymbol{\rho}$. Then we search the optimal
$\boldsymbol{\rho}$ by eliminating $\boldsymbol{p}$ in the objective function.
Such a method has been commonly used in the literature (e.g., [2, 4, 5, 11]).

Let us rewrite $L(\boldsymbol{p},\boldsymbol{\rho},\boldsymbol{\lambda})$ as

$L(\boldsymbol{p},\boldsymbol{\rho},\boldsymbol{\lambda})=\sum_{k=1}^{K}\sum_{u=1}^{U}\sum_{j=1}^{N}L_{k,u,j}(p_{k,u,j})+\sum_{k=1}^{K}\lambda_{k}P_{k},$
(8)

where

$\begin{split}L_{u,k,j}(p_{u,k,j})=w_{u}\sum_{i=1}^{N}R_{u,k,i,j}(p_{k,u,j})-\lambda_{k}p_{k,u,j}.\end{split}$
(9)

Suppose $\rho_{u,k,i,j}=1$ for a certain $(u,k,i,j)$. It is easy to verify
that $L_{u,k,j}(p_{u,k,j})$ is concave in $p_{k,u,j}$ and thus the optimal
$p_{k,u,j}^{*}(\lambda_{k})$ can be obtained by applying the Karush-Kuhn-
Tucker (KKT) conditions. More specifically, $p_{k,u,j}^{*}(\lambda_{k})$ is
the non-negative real root of the following quartic function

$\displaystyle ap_{k,u,j}^{4}+bp_{k,u,j}^{3}+cp_{k,u,j}^{2}+dp_{k,u,j}+e=0,$
(10)

where $a,b,c,d,e$ are coefficients determined by the dual variables, MSs’
weights, and channel gains as defined at the top of the next page.

$\displaystyle a$ $\displaystyle=2\ln
2\lambda_{k}|h_{b,k,j}|^{4}|f_{u,k,j}|^{4}/m_{u,k,i},$ $\displaystyle b$
$\displaystyle=4\ln
2\lambda_{k}|h_{b,k,j}|^{2}|f_{u,k,j}|^{2}(|f_{u,k,j}|^{2}+|h_{b,k,j}|^{2}),$
$\displaystyle c$ $\displaystyle=2m_{u,k,i}\ln
2\lambda_{k}(|h_{b,k,j}|^{4}+|f_{u,k,j}|^{4}+4|h_{b,k,j}|^{2}|f_{u,k,j}|^{2})$
$\displaystyle-
w_{u}|h_{b,k,j}|^{2}|f_{u,k,j}|^{2}(p_{u,k,i}|f_{u,k,i}|^{2}|f_{u,k,j}|^{2}+p_{b,k,i}|h_{b,k,i}|^{2}|h_{b,k,j}|^{2}),$
$\displaystyle d$ $\displaystyle=4m_{u,k,i}^{2}\ln
2\lambda_{k}(|f_{u,k,j}|^{2}+|h_{b,k,j}|^{2})-2w_{u}m_{u,k,i}|h_{b,k,j}|^{2}|f_{u,k,j}|^{2}((p_{u,k,i}|f_{u,k,i}|^{2}+p_{b,k,i}|h_{b,k,i}|^{2}),$
$\displaystyle e$ $\displaystyle=2m_{u,k,i}^{3}\ln
2\lambda_{k}-w_{u}m_{u,k,i}^{2}(p_{u,k,i}|f_{u,k,i}|^{2}|h_{b,k,j}|^{2}+p_{b,k,i}|h_{b,k,i}|^{2}|f_{u,k,j}|^{2}).$

Substituting the optimal power allocations
$\boldsymbol{p}^{*}(\boldsymbol{\lambda})$ into (6) to eliminate the power
variables, the dual function can be rewritten as

$\displaystyle
g(\boldsymbol{\lambda})=\max_{\boldsymbol{\rho}\in\mathcal{T}}\sum_{u=1}^{M}\sum_{k=1}^{K}\sum_{i=1}^{N}\sum_{j=1}^{N}\rho_{u,k,i,j}X_{u,k,i,j}+\sum_{k=1}^{K}\lambda_{k}P_{k},$

where

$X_{u,k,i,j}=w_{u}R_{u,k,i,j}(p_{k,u,j}^{*}(\lambda_{k}))-\lambda_{k}p_{k,u,j}^{*}(\lambda_{k}).$
(11)

Now we are ready to find the optimal $\boldsymbol{\rho}$. In the following, we
show that $X_{u,k,i,j}$ defined in (11) plays an important role in user and
relay selection for occupying a subcarrier pair $(i,j)$.

Noting the constraints (2) and (3), we conclude that there is at most one non-
zero element for a given subcarrier pair $(i,j)$. This suggests that at most
one MS and one RS can occupy the subcarrier pair $(i,j)$. Based on the
observation, we define

$\mathcal{X}_{i,j}=\max_{k\in\mathcal{K},u\in\mathcal{U}}X_{u,k,i,j},$ (12)
$(u^{*},k^{*})_{i,j}=\arg\max_{k\in\mathcal{K},u\in\mathcal{U}}X_{u,k,i,j}.$
(13)

Then the dual function can be further written as

$\displaystyle
g(\boldsymbol{\lambda})=\max_{\boldsymbol{\rho}\in\mathcal{T}}\sum_{i=1}^{N}\sum_{j=1}^{N}\rho_{u*^{,}k^{*},i,j}\mathcal{X}_{i,j}+\sum_{k=1}^{K}\lambda_{k}P_{k}.$
(14)

From (14) it can be seen that if subcarrier $i$ in the MAC phase is paired
with subcarrier $j$ in the BC phase, then the pair should be used by MS
$u^{*}$ with the help of RS $k^{*}$, i.e., the MS and RS with the maximum
$X_{u,k,i,j}$ as defined in (11). This can be interpreted from an economic
perspective. Suppose each dual variable $\lambda_{k}$ represents the power
price of RS $k$. Then $X_{u,k,i,j}$ can be regarded as the profit of letting
MS $u$ transmitting over the subcarrier pair $(i,j)$ with the help of RS $k$,
where the profit is defined as the throughput revenue $w_{u}R_{u,k,i,j}$ minus
the power cost $\lambda_{k}p^{*}_{k,u,j}$. Clearly, to maximize the system
total profit, each potential subcarrier pair $(i,j)$ should be assigned to the
MS and RS that can generate the maximum sub-profit.

The remaining problem is then to identify the optimal subcarrier pairings
$\rho_{u^{*},k^{*},i,j}$. This is a standard _two-dimensional assignment
problem_. The classical Hungarian method can be applied to find the optimal
$\boldsymbol{\rho}^{*}(\boldsymbol{\lambda})$ in polynomial time.

###  III-B Optimizing the Dual Vector $\boldsymbol{\lambda}$

After computing $g(\boldsymbol{\lambda})$, we now solve the standard dual
optimization problem which is

$\displaystyle\min_{\boldsymbol{\lambda}}~{}g(\boldsymbol{\lambda})$ (15)
$\displaystyle s.t.~{}~{}\boldsymbol{\lambda}\succeq 0.$

Since a dual function is always convex, subgradient-based methods can be used
to minimize $g(\boldsymbol{\lambda})$ with global convergence with the fact
that

$\Delta\lambda_{k}=P_{k}-\sum_{u=1}^{M}\sum_{j=1}^{N}p_{k,u,j}^{*}(\lambda_{k})$
(16)

is the subgradient at $\lambda_{k},\forall k$. In specific, denote
$\Delta\boldsymbol{\lambda}^{(l)}=(\Delta\lambda_{1}^{(l)},\Delta\lambda_{2}^{(l)},...,\Delta\lambda_{K}^{(l)})$,
then we can update the dual variables as
$\boldsymbol{\lambda}^{(l+1)}=\boldsymbol{\lambda}^{(l)}+\omega^{(l)}\Delta\boldsymbol{\lambda}^{(l)}$.
Here, $\omega^{(l)}$ is the diminishing step size at the $l$th iteration to
guarantee the convergence of the subgradient method.

###  III-C Refinement of Power Allocation

Having the dual point $\boldsymbol{\lambda}^{*}$, we now need to determine the
optimal solution to the primal problem (5). Due to the non-zero duality gap,
the optimal $\boldsymbol{\rho}^{*}(\boldsymbol{\lambda}^{*})$ and
$\boldsymbol{p}^{*}(\boldsymbol{\lambda}^{*})$ may not satisfy all the
constraints (2), (3), and (4) in the original problem. To overcome this
problem, we first determine the optimal assignment $\boldsymbol{\rho}^{*}$ in
dual domain, and then make a refinement of the power allocation to meet the
power constraints in the primal problem. More specifically, denote
$\mathcal{A}_{u,k}$ as the set of active subcarrier pairs assigned to MS $u$
and RS $k$ obtained from the dual problem. The problem can be written as:

$\displaystyle\max_{\boldsymbol{p}}\sum_{u=1}^{M}w_{u}\sum_{k=1}^{K}\sum_{(i,j)\in\mathcal{A}_{u,k}}R_{u,k,i,j}(p_{k,u,j})$
(17) $\displaystyle
s.t.~{}~{}\sum_{u=1}^{M}\sum_{(i,j)\in\mathcal{A}_{u,k}}p_{k,u,j}\leq
P_{k},~{}\forall k.$ (18)

Clearly, this is a convex problem. By applying KKT conditions, we can obtain
the optimal $p_{k,u,j}^{*}$ which has the same expression as that in the dual
domain.

Finally we summarize the overall procedure of the proposed dual-based solution
in Algorithm 1. This algorithm is asymptotically optimal when $N$ is
sufficiently large [12].

Algorithm 1 Proposed algorithm for problem (5)

1: initialize $\boldsymbol{\lambda}^{(0)}$ as a random non-negative vector,
$l=0$.

2: repeat

3: Compute $X_{u,k,i,j}$ using (11) for all $(u,k,i,j)$ with $p^{*}_{k,u,j}$
being the non-negative real root of (10).

4: Obtain $\mathcal{X}_{i,j}$ and $(u^{*},k^{*})$ using (12) and (13)
respectively for all $(i,j)$, then obtain optimal
$\boldsymbol{\rho}^{*}(\boldsymbol{\lambda}^{(l)})$ by solving (14).

5: Update $\boldsymbol{\lambda}^{(l)}$ using the subgradients
$\Delta\boldsymbol{\lambda}^{(l)}$ in (16); Let $l\leftarrow l+1$.

6: until $\boldsymbol{\lambda}$ converges.

7: Set the final $\boldsymbol{\rho}$ as $\boldsymbol{\rho}^{*}$ obtained in
the dual domain and refine the power parameter $\boldsymbol{p}^{*}$ by solving
(17) at the given $\boldsymbol{\rho}^{*}$.

###  III-D Discussion on Complexity and Proportional Fairness

The complexity of updating the dual variables $\boldsymbol{\lambda}$ is
$\mathcal{O}(K^{q})$ (e.g., if the ellipsoid method is used, $q=2$). The
complexity in (12) and the Hungarian method are $\mathcal{O}(MK)$ and
$\mathcal{O}(N^{3})$, respectively. Combining all, the total complexity of the
proposed method is $\mathcal{O}((MK+N^{3})K^{q})$, which is polynomial.

If consider long-term fairness among the MSs, the weight of MS $u$ at time $t$
can be updated by $w_{u}^{(t)}=1/T_{u}^{(t)}$, $\forall u\in\mathcal{U}$,
where $T_{u}^{(t)}$ as the accumulated rate of MS $u$ at time $t$. Note that
we can let $w_{u}=1$ for every MS for pure throughput maximization.

##  IV Simulation Results

We consider a cell with 2 km radius. The RSs are uniformly located on a circle
centered at the BS and with radius of 1 km. The MSs are randomly but uniformly
distributed in the outer circle as in Fig. 1. The path loss exponent is $4$
and the standard deviation of log-normal shadowing is $5.8$ dB. The small-
scale fading is modeled by multi-path Rayleigh fading process. A total of
$3000$ independent channel realizations were used. Each channel realization is
associated with a different set of node locations. We set $M=4$, $K=3$, and
$N=32$. All MS and the BS have the same maximum power constraints, so do all
RSs. We set the BS and MS power to be $10$ dB per-node and uniformly
distributed among all subcarriers.

As the benchmarks, the performance of Equal Power Assignment (EPA) based
resource allocation and Random Resource Allocation (RRA) schemes are also
presented. Specifically, EPA lets $\boldsymbol{p}$ be uniformly distributed
among all the subcarriers on each relay station and finds optimal
$\boldsymbol{\rho}^{*}$ as in Section III-A proposed algorithm. In RRA, the
power is uniformly distributed and the subcarrier pairs and relays are
randomly assigned. The complexity of the EPA and RRA schemes are
$\mathcal{O}(MK+N^{3})$ and $\mathcal{O}(N)$, respectively, which are lower
than that of the proposed algorithm.

Figure 2: Average sum-rate versus RS-power per-node.

Fig. 2 compares the average sum-rate achieved by different schemes. We first
observe that the proposed dual-based algorithm approaches the upper bound (the
optimal dual) closely. This verifies the effectiveness of the dual method at
large number of subcarriers. One also observes that the proposed algorithm
outperforms the two benchmarks by a significant margin. In particular, the
proposed algorithm obtains more than $30\%$ and $200\%$ throughput
improvements over the EPA and RRA schemes, respectively. This tremendous
improvement demonstrates the superiority of our proposed algorithm.

##  V Conclusion

In this work, we have studied the subcarrier-pairing based resource allocation
in OFDMA-based two-way relay networks. By using the dual method, an efficient
algorithm for joint optimization of subcarrier-pairing based relay-power
allocation, relay selection, and subcarrier assignment was proposed.
Simulation results show that the proposed algorithm can significantly improve
the system performance compared with the conventional schemes.

## References

  * [1] A. Hottinen and T. Heikkinen, “Optimal subchannel assignment in a two-hop OFDM relay,” in _Proc. IEEE SPAWC_ , Jun. 2007.
  * [2] C.-N. Hsu, H.-J. Su, and P.-H. Lin, “Joint subcarrier pairing and power allocation for OFDM transmission with decode-and-forward relaying,” _IEEE Trans. Signal Proc._ , vol. 59, no. 99, pp. 399–414, Jan. 2011.
  * [3] C. K. Ho, R. Zhang, and Y. C. Liang, “Two-way relaying over OFDM: optimized tone permutation and power allocation,” in _Proc. IEEE ICC_ , May 2008, pp. 3908–3912.
  * [4] W. Dang, M. Tao, H. Mu, and J. Huang, “Subcarrier-pair based resource allocation for cooperative multi-relay OFDM systems,” _IEEE Trans. Wireless Commun._ , vol. 9, no. 5, pp. 1640–1649, May 2010.
  * [5] M. Hajiaghayi, M. Dong, and B. Liang, “Optimal channel assignment and power allocation for dual-hop multi-channel multi-user relaying,” in _Proc. IEEE INFOCOM_ , Apr. 2011.
  * [6] Y. Liu, M. Tao, B. Li, and H. Shen, “Optimization framework and graph-based approach for relay-assisted bidirectional OFDMA cellular networks,” _IEEE Trans. Wireless Commun._ , vol. 9, no. 11, pp. 3490–3500, Nov. 2010\.
  * [7] Y. Liu and M. Tao, “Optimal channel and relay assignment in OFDM-based multi-relay multi-pair two-way communication networks,” _IEEE Trans. Commun._ , to appear.
  * [8] S. Ren and M. van der Schaar, “Distributed power allocation in multi-user multi-channel cellular relay networks,” _IEEE Trans. Wireless Commun._ , vol. 9, no. 6, pp. 1952–1964, Jun. 2010.
  * [9] D. W. K. Ng and R. Schober, “Resource allocation and scheduling in multi-cell OFDMA systems with decode-and-forward relaying,” _IEEE Trans. Wireless Commun._ , vol. 10, no. 7, pp. 2246–2258, Jul. 2011.
  * [10] B. Rankov and A. Wittneben, “Spectral efficient protocols for half-duplex fading relay channels,” _IEEE J. Sel. Areas Commun._ , vol. 25, no. 2, pp. 379–389, Feb. 2007.
  * [11] J. Louveaux, R. Duran, and L. Vandendorpe, “Efficient algorithm for optimal power allocation in OFDM transmission with relaying,” in _Proc. IEEE ICASSP_ , 2008, pp. 3257–3260.
  * [12] W. Yu and R. Lui, “Dual methods for nonconvex spectrum optimization of multicarrier systems,” _IEEE Trans. Commun._ , vol. 54, no. 7, pp. 1310–1322, Jul. 2006.


80 2017 ACML 2017

# Accumulated Gradient Normalization

Joeri R<EMAIL_ADDRESS>
Gerasimos Spanakis<EMAIL_ADDRESS>
Rico Möckel<EMAIL_ADDRESS>
Department of Electrical Engineering and Computer Science  Liège University
Belgium
Department of Data Science & Knowledge Engineering  Maastricht University  The
Netherlands

###### Abstract

This work addresses the instability in asynchronous data parallel
optimization. It does so by introducing a novel distributed optimizer which is
able to efficiently optimize a centralized model under communication
constraints. The optimizer achieves this by pushing a normalized sequence of
first-order gradients to a parameter server. This implies that the magnitude
of a worker delta is smaller compared to an accumulated gradient, and provides
a better direction towards a minimum compared to first-order gradients, which
in turn also forces possible implicit momentum fluctuations to be more aligned
since we make the assumption that all workers contribute towards a single
minima. As a result, our approach mitigates the parameter staleness problem
more effectively since staleness in asynchrony induces (implicit) momentum,
and achieves a better convergence rate compared to other optimizers such as
asynchronous easgd and dynsgd, which we show empirically.

###### keywords:

Distributed Optimization, Neural Networks, Gradient Descent

##  1 Introduction

Speeding up gradient based methods has been a subject of interest over the
past years with many practical applications, especially with respect to Deep
Learning. Despite the fact that many optimizations have been done on a
hardware level, the convergence rate of very large models remains problematic.
Therefore, data parallel methods next to mini-batch parallelism have been
suggested Dean et al. (2012); Ho et al. (2013); Hadjis et al. (2016); Recht et
al. (2011); Louppe and Geurts (2010); Jiang et al. (2017); Zhang et al. (2015)
to further decrease the training time of parameterized models using gradient
based methods. Nevertheless, asynchronous optimization was considered too
unstable for practical purposes due to a lacking understanding of the
underlying mechanisms, which is an issue this work addresses.

Data Parallelism is an inherently different methodology of optimizing
parameters. As stated above, it is a technique to reduce the overall training
time of a model. In essence, data parallelism achieves this by having $n$
workers optimizing a central model, and at the same time, processing $n$
different shards (partitions) of the dataset in parallel over multiple
workers111A worker in this work is a process on a single machine. However, it
is possible that multiple workers share the same machine. Nevertheless, one
could construct the distribution mechanism (even manually) in such a way every
worker will be placed on a different machine.. The workers are coordinated in
such a way that they optimize the parameterization of a central model or
central variable, which we denote by $\tilde{\theta}_{t}$. The coordination
mechanism of the workers can be implemented in many different ways. A popular
approach to coordinate workers is to employ a centralized _Parameter Server_
(PS). The sole responsibility of the parameter server is to aggregate model
updates coming from the workers (_worker commits_), and to handle parameter
requests (_worker pulls_).

Recently, a theoretical contribution has been made Mitliagkas et al. (2016)
which defines asynchronous optimization in terms of (implicit) _momentum_ due
to the presence of a queuing model of gradients based on past
parameterizations. This paper mainly builds upon this work, and Zhang et al.
(2015) to construct a better understanding why asynchronous optimization shows
proportionally more divergent behavior when the number of parallel workers
increases, and how this affects existing distributed optimization algorithms.

$t$$w_{1}$$w_{2}$$\tilde{\theta}_{t}$$\nabla_{\theta}\mathcal{L}_{1}(\tilde{\theta}_{t})$$w_{1}$$\tilde{\theta}_{t+1}=\tilde{\theta}_{t}-\eta_{t}\odot\nabla_{\theta}\mathcal{L}_{1}(\tilde{\theta}_{t})$$\nabla_{\theta}\mathcal{L}_{2}(\tilde{\theta}_{t})$$w_{2}$$\tilde{\theta}_{t+2}=\tilde{\theta}_{t+1}-\eta_{t}\odot\nabla_{\theta}\mathcal{L}_{2}(\tilde{\theta}_{t})$Updating
$\tilde{\theta}_{t+1}$ with gradient
$\nabla_{\theta}\mathcal{L}_{2}(\tilde{\theta}_{t})$ based on
$\tilde{\theta}_{t}$ Figure 1: In Asynchronous Data Parallelism workers
compute and commit gradients to the PS asynchronously. This has as a side-
effect that some workers are computing, and thus committing, gradients based
on old values. These gradients are called _stale gradients_ in literature. In
this particular example there are 2 workers $w_{1}$, and $w_{2}$. At the start
of the optimization process, both workers pull the most recent
parameterization, $\tilde{\theta}_{t}$, from the PS. Now all workers start
computing gradients asynchronously based on the pulled parameterization.
However, since the PS incorporates gradients into the center variable
asynchronously as a simple queuing (FIFO) model, other workers will update the
center variable with gradients based on a stale parameterization, as shown
above. Finally, assuming that the computing cluster is homogeneous, we can
derive from this figure that the expected staleness of a gradient update is
$\mathbf{E}[\tau]=(n-1)$, as mentioned in Mitliagkas et al. (2016).

The rest of the paper is organized as follows. In Section 2 we present the
intuition for our method. Section 3 describes the proposed method in full,
followed by an experimental validation in Section 4. Finally, Section 5
concludes the paper by giving an overview of the contributions presented in
this work.

##  2 Concept & Intuition

The main issue with downpour Dean et al. (2012) is the requirement of constant
communication with the parameter server after every gradient computation.
Furthermore, as the number of parallel workers increases, downpour fails to
converge due to the amount of _implicit momentum_ , as shown in Figure
LABEL:fig:downpour_convergence. To reduce the amount of communication with the
parameter server, one could take ideas from easgd, and perform several
iterations of local exploration before committing the gradients to the
parameter server. However, in the case of algorithms like downpour, that is,
where gradients are committed to the parameter server in an asynchronous
fashion with no mechanisms in place to ensure convergence, more local
exploration results in proportionally larger gradients and as a result,
complicate the staleness and the implicit momentum problem even further. To
intuitively show why this is an issue, let us consider Figure
LABEL:fig:agn_intuition. In a downpour setting, first-order gradients such as
in Subfigure (a) are committed to the parameter server. However, when an
algorithm allows for a certain amount of local exploration, the gradient that
is committed to the parameter server is typically an _accumulated gradient_ as
shown in Subfigure (b).

Now, imagine two asynchronous environments where respectively no gradient
accumulation takes place, and one where does. In the environment where no
gradient accumulation is performed, as in regular downpour, first-order
gradients are committed to the parameter server. However, we know that
downpour diverges when the number of asynchronous workers is too high due to
the amount of implicit momentum Mitliagkas et al. (2016). As a result, careful
tuning is required when no adaptive methods are applied in order to guarantee
convergence. Nevertheless, given the fact that downpour converges with $n=10$
workers in Figure LABEL:fig:downpour_convergence, and our knowledge about
gradient accumulation, i.e., _accumulated gradients that are committed are
proportional to the number of exploration steps for every worker, and provide
better directions to a minimum_ , we would expect that for some amount of
local exploration while using the same hyperparameterization (with the
exception of local exploration steps $\lambda$) downpour would diverge again
due to the magnitude of the accumulated gradients. This behaviour is
illustrated in Figure LABEL:fig:downpour_accumulated_divergence, and confirms
our hypothesis.

To reduce the magnitude of the accumulated gradients, and thereby reducing the
amount of implicit momentum, while at the same time preserving the better
direction that has been provided due to the amount of local exploration, we
propose to normalize (average) the accumulated gradient with the amount of
local steps that have been performed by the workers ($\lambda$), shown in
Equation 1222Note if $\lambda=1$, agn generalizes to downpour.. We call this
technique of normalizing the accumulated gradient _Accumulated Gradient
Normalization_ or agn. An initial critique of this technique would be that by
normalizing the accumulated gradient, agn would in effect be undoing the work
that has been done by a single worker. This seems at first a valid criticism,
however, one needs to take into account that agn is actually using the worker
exploration steps to compute a better gradient based on first-order gradients.

Figure 3: After pulling the most recent parameterization of the central
variable from the parameter server, the worker starts accumulating $\lambda$
first order gradients, and applies those gradients locally to explore the
surrounding error space. Finally, after $\lambda$ exploration steps have been
performed, the accumulated is normalized w.r.t. $\lambda$ and send to the
parameter server.

##  3 Method

The agn update rule for a worker and the parameter are described in Equation 1
and Equation 2 respectively. Since agn is using local steps ($\lambda$) to
compute a better gradient based on a _sequence_ of first-order gradients, it
can also be used under communication constraints like easgd since less
communication with the parameter server is required due to computation of a
local sequence of first-order gradients. Figure 3 shows how an agn gradient is
obtained and computed using Equation 1 by following Algorithm 1. In this
setting $\eta_{t}$ denotes the learning rate of a worker at time $t$, and $m$
denotes the size of the mini-batch which is identical across all workers.

$\Delta\theta^{k}=-\frac{1}{\lambda}\sum_{i=0}^{\lambda}\eta_{t}\frac{1}{m}\sum_{j=0}^{m-1}\nabla_{\theta}\mathcal{L}(\theta_{i};x_{ij};y_{ij})$
(1)

$\tilde{\theta}_{t+1}=\tilde{\theta}_{t}+\Delta\theta^{k}$ (2)

Algorithm 1 Worker procedure of agn.

1:procedure AGNWorker($k$)

2: $\theta^{k}_{0}\leftarrow\tilde{\theta}\leftarrow\textsc{Pull}($)

3: $t\leftarrow 0$

4: while not converged do

5: $i\leftarrow 0$

6: $a\leftarrow 0$

7: while $i<\lambda$ do

8: $\textbf{x},~{}\textbf{y}\leftarrow\textsc{FetchNextMiniBatch()}$

9:
$g\leftarrow-\eta_{t}\odot\nabla_{\theta}\mathcal{L}(\theta^{k}_{t};\textbf{x};\textbf{y})$
$\triangleright$ Gradient from, e.g., Adam Kingma and Ba (2014)

10: $a\leftarrow a+g$

11: $\theta^{k}_{t+1}=\theta^{k}_{t}+g$

12: $i\leftarrow i+1$

13: $t\leftarrow t+1$

14: end

15: $a\leftarrow\frac{a}{\lambda}$ $\triangleright$ Normalization step.

16: $\textsc{Commit}(a)$

17: $\theta^{k}_{t}\leftarrow\textsc{Pull}($)

18: end

19:end procedure

An interesting thought-experiment would be to explore what would happen if the
workers would communicate with the parameter server after a very large number
of steps, that is, when $\lambda$ approaches $\infty$. How would the
normalized accumulated gradients look like in such a situation, described by
Equation 3?

$\lim_{\lambda\to\infty}-\frac{\sum_{i=0}^{\lambda}\eta_{t}\frac{1}{m}\sum_{j=0}^{m-1}\nabla_{\theta}\mathcal{L}(\theta_{i};x_{ij};y_{ij})}{\lambda}$
(3)

In order to completely understand how the worker deltas would look like after
$\lambda=\infty$ steps, one first needs to understand the individual
components of Equation 3. The most inner component,
$\eta_{t}\frac{1}{m}\sum_{j=0}^{m-1}\nabla_{\theta}\mathcal{L}(\theta_{i};x_{ij};y_{ij})$,
is just the computation of a mini-batch using $m-1$ samples, where index $i$
denotes the current step in the gradient accumulation. Please note that a
mini-batch can differ for different values of $i$ as training samples are
randomly retrieved from the dataset. After computing the gradient based on the
mini-batch, the local model will be updated as
$\theta_{i+1}=\theta_{i}-\eta_{t}\frac{1}{m}\sum_{j=0}^{m-1}\nabla_{\theta}\mathcal{L}(\theta_{i};x_{ij};y_{ij})$.
This process goes on for $\lambda$ steps, while at the end, the accumulated is
normalized with respect to $\lambda$.

Let us assume we have a smooth convex error space, or a smooth non-convex
error space with at least a single minima. Due to the existence of a minima in
both cases, first order gradients will eventually converge to, or in the
neighbourhood of said minima. Furthermore, we make the assumption that the
hyperparameterization during the training procedure will not change. For
instance, no learning rate decay after $x$ number of steps. Under these
assumptions, it is trivial to realize that applying gradient descent for
$\infty$ steps will cause the parameterization to converge in a minima. Of
course, given that the hyperparameterization, and the data allow for
convergence to occur. As a result, the term
$\sum_{i=0}^{\lambda}\eta_{t}\frac{1}{m}\sum_{j=0}^{m-1}\nabla_{\theta}\mathcal{L}(\theta_{i};x_{ij};y_{ij})$
is finite, even after applying $\infty$ steps of mini-batch updates. To
simplify our problem, let us denote $\vec{c}$ as the _finite_ result of the
top term in Equation 3 for $\lambda=\infty$. Furthermore, since $\vec{c}$ is
finite, the equation can be treated as an instance of $\frac{1}{\infty}$,
which approaches 0. This implies that for a very large $\lambda$, the
normalized accumulated gradients will basically be $\vec{0}$. However, what is
interesting is that the normalized accumulated gradients directly point
towards a minima due to the large amount of exploration steps that have been
performed. Subsequently, one can view a normalized accumulated gradient when
$\lambda$ approaches $\infty$ as a point, but with a direction. Therefore,
when convergence is obtained, the path the central variable traversed is a
straight line towards the minima, as shown in Figure
LABEL:fig:agn_straight_line.

The thought experiments described above help us in several ways if we make
several additional assumptions. The first assumes that normalized accumulated
gradients with $\lambda=\infty$ can be computed immediately, that is, without
a delay. This is of course an unrealistic assumption. However, one needs to
consider realistic communication constraints. Given a certain network
throughput, what is the amount of local communication that needs to be
performed in order for a parameter commit to be “worth it”? As mentioned
above, $\lambda=\infty$ is not a very good solution since the normalized
accumulated gradient will converge to $\vec{0}$ in the limit. Nevertheless, if
the normalized accumulated gradient could be computed immediately, as we
assumed, the central variable would traverse the shortest path to a minima, in
contrast to first order gradients. Of course, this is not a realistic
assumption. Furthermore, this issue is quite similar to _stochastic gradient
descent_ vs. _mini-batch gradient descent_ , since in agn we also have to make
the decision between more frequent parameter updates, and more “local”
iterations to compute a better gradient, where better in the case of mini-
batch gradient descent means less-noisy.

In most settings, the size of a mini-batch is determined empirically, and is
dependent on the noise of the gradients. Furthermore, when using mini-batch
gradient descent, a trade-off is made between more frequent parameter updates,
i.e., a smaller mini-batch, or more robust and consistent gradients by
increasing the size of a mini-batch which results in a more accurate
approximation of the first order curvature. This is similar to our situation.
Yet, in mini-batch gradient descent you are basically trying to estimate a
hyperparameter based on several unknowns, i.e., convergence based on error
space and noise of individual gradients. However, agn is balancing the amount
of local computation to produce a better gradient, with the throughput of the
network, which is a known variable. For instance, imagine a hypothetical
communication infrastructure which is able to apply the commits of the workers
directly into the workers with no delay. In this situation, one could apply
downpour. However, remember from Figure
LABEL:fig:downpour_accumulated_divergence that downpour does not handle an
increased amount of asynchronous parallelism ($n=20$). As a result, even in an
ideal situation downpour will not be able to converge due to the amount of
implicit momentum.

Nevertheless, the situation in agn is different as will become apparent in
Section 4. Contrary to downpour, agn does not commit first order gradients to
the parameter server, but rather a normalized sequence of first order
gradients which result in better directions towards a minima, as discussed
above. Therefore, agn worker deltas will point more or less in more optimal
direction and thereby reducing the negative effects of implicit momentum in
first order gradients.

##  4 Experimental Validation

This Section evaluates agn against different distributed optimization
algorithms. MNIST LeCun et al. (1998) is used as a benchmark dataset, and all
optimizers the same model with identical parameterization of the weights.
Furthermore, we will set the mini-batch size to $m=128$ in all optimizers, and
use _40 epochs_ worth of training data that will be equally distributed over
all $n$ workers. Our computing infrastructure consists a relatively small
cluster of _15 nodes_ with a _10Gbps interconnect_ , most of them in the same
rack, each having 2 Intel® Xeon® CPU E5-2650 v2 @ 2.60GHz CPU’s, where every
CPU has 8 cores and 2 threads. No GPU’s are used during training, and no
learning rate decay is applied. Our optimizer and experiments are implemented
and executed using _dist-keras_ 333github.com/cerndb/dist-keras, which are
available in the package.

Our initial experiment, shown in Figure LABEL:fig:agn_experiment_1, shows the
training accuracy of agn, aeasgd, and dynsgd over time. In this experiment, we
use a near-optimal hyperparameterization for all optimizers to ensure
convergence. Looking at Figure LABEL:fig:agn_experiment_1, we observe an
increase in training performance for agn, both in training accuracy, and in
training time when compared to current state-of-the-art algorithms such as
aeasgd and dynsgd. Furthermore, dynsgd scales the gradients down with respect
to staleness $\tau$, which in effect is $(n-1)^{-1}$ since
$\textbf{E}[\tau]=n-1$. As a result, dynsgd does not handle the parameter
staleness problem appropriately since it does not take the distance between
the parameterizations into account. This is validated in Figure
LABEL:fig:agn_experiment_1 because of the observed divergent behaviour of the
optimizer. Furthermore, due to the relatively high communication frequency
($\lambda=10$, $\lambda=3$), dynsgd will take longer to process all data since
more communication with the parameter server is required.

Figure 5: Decline of the training accuracy of both agn and aeasgd as the
number of asynchronous workers increases. From these experiments, we observe
that agn is more robust to an increased amount of asynchrony as the training
accuracy only starts to decrease from $n=25$ workers, while the validation
accuracy remains stable even with 40 workers.

Contrary to aeasgd, agn is able to cope more effectively with an increased
amount of parallelism, as its training accuracy only starts to decline from
$n=25$ asynchronous workers, while the validation accuracy is barely
fluctuating, as shown in Figure 5. An obvious follow-up question to this
result would be to question the fact whether increasing the amount of workers
really improves the temporal efficiency optimizer, i.e., the amount of time it
takes to reach a certain training accuracy. In fact, it does reduce the
training time to reach a certain training accuracy, as shown in Figure
LABEL:fig:agn_temporal_efficiency. However, several factors have to be taken
into account.

The first being an increased amount of staleness that is inserted into the
system as the number of asynchronous workers increase. This effect is
difficult to mitigate. Previous approaches Jiang et al. (2017) propose to
scale gradient commits down proportionally to the number of stale steps.
However, as previously shown, this is not an effective solution since
accumulating gradients locally, is in effect making the gradients larger, and
as a result, committing accumulated gradients increases the _distance_ between
the central variable and other workers. The second and final issue is the
balance between updating the central variable with a certain frequency, and
the amount of local work to effectively reduce the training time due to high
communication costs. In effect, this resembles the situation usually one has
when selecting a mini-batch size $m$, i.e., do we allow for more frequent
parameter updates (small $m$), or do we compute a less noisy first order
gradient by increasing $m$, thereby reducing the frequency of parameter
updates and the convergence of a model? In Figure
LABEL:fig:agn_experiments_workers, we evaluate varying values of $\lambda$ for
a specific number of asynchronous workers $n$ to show that similar manual
tuning is required. In all cases, we observe configurations with $\lambda=40$
usually have the slowest convergence rate with respect to other configurations
with higher communication frequencies.

Nevertheless, what is really interesting, is why configurations with low
communication frequencies actually do converge, in contrast to configurations
with high communication frequencies (with respect to the number of workers).
Since our definition of staleness relates to the distance between the
_current_ parameterization of a worker, and the _current_ parameterization of
the central variable. One can imagine that increasing the number of
asynchronous workers, effectively increases the _distance_ between the
parameterizations of the workers and the _current_ central variable due to the
queuing model discussed before, i.e., worker deltas are incorporated in the
central variable in a queuing fashion. Yet, parameter staleness still does not
explain why configurations with low communication frequencies converge, as
opposed to configurations with higher communication frequencies. The question
begs, is convergence guaranteed due to the amount of local exploration, thus
providing the parameter server with a better “direction”, as shown in Figure
3. Or, due to limit condition described above, which eventually scales the
worker deltas down to 0 as the communication frequency decreases ($\lambda$
increases)? This is a rather difficult question to answer, since there might
be a synergy since large gradients are usually considered a bad thing.
However, the normalization step takes the average gradient of all accumulated
gradients. As a result, the limit condition does not apply here. Summarized,
the stability property of agn arises from the fact that _implicit momentum_
fluctuations will mostly be in line with a minima due to the better directions
agn provides.

To compare agn against aeasgd (since this optimizer shows almost no divergent
behaviour for a wide range of hyperparameters), we introduce _temporal
efficiency_ in terms of the surface described by a training metric. This means
that for some optimizer $a$, we have a function $f_{a}(t)$ which describes the
performance of a model at time $t$, e.g., $f_{a}(t)$ describes the training
accuracy of the model at time $t$. If we integrate over $t$, we obtain a
surface representing the performance of a model over time. If we would do this
for an other optimizer $b$, and divide the surface of optimizer $a$ by the
performance surface of optimizer $b$, we get a ratio which describes how
optimizer $a$ is performing compared to optimizer $b$. If this ratio is larger
then 1, it means that optimizer $a$ is outperforming optimizer $b$, else, it
is the other way around (unless the surfaces are equal of course). However, in
order to compute a _fair_ surface area, we have to limit the computation to
the _minimal shared training time_ $m$. This is done to prevent that
optimizers with a longer training time have a significant advantage, since
they have more time to produce a better model. To summarize, we define the
temporal efficiency $\mathcal{E}$ of two optimizers $a$ and $b$ as the ratio
of their performance surface, as stated in Equation 4. Using _temporal
efficiency_ , we can make a more qualitative judgment which optimizer is
performing better in different scenarios _since it also incorporates the
stability of the optimizer_.

$\mathcal{E}(a,b)=\frac{\displaystyle\int_{0}^{m}f_{a}(t)\,dt}{\displaystyle\int_{0}^{m}f_{b}(t)\,dt}$
(4)

Finally, we apply _temporal efficiency_ to compare agn against aeasgd and
summarize the results in Table 1. We make the observation that increasing the
amount of asynchrony results in a deterioration of the training accuracy
(which is expected since more staleness, and thereby, implicit momentum is
induced). However, the rather unexpected property is that increasing the
amount of asynchronous workers results in an early _flattening_ of the
training accuracy in aeasgd. This is due to an equilibrium condition which is
present in easgd Hermans (2017). Since we increase the amount of asynchrony in
the optimization procedure, workers will reach the equilibrium condition
faster because the elastic difference is computed based on the most recent
parameterization of the central variable. Meaning, as soon as aeasgd is done
computing $\lambda$ iterations, the central variable is pulled to the worker
where the elastic difference is computed based on the recently pulled central
variable, which is very stale due to the low communication frequency and high
number of asynchronous workers. As a result, aeasgd is rather slow reaching a
better training accuracy in the presence of small gradients compared to other
optimization algorithms.

$n$ | $\lambda$ |  AGN $t$ |  AGN Acc. |  AEASGD $t$ |  AEASGD Acc. | $\mathcal{E}(\textsc{agn},\textsc{aeasgd})$
---|---|---|---|---|---|---
10 | 10 | 1066.08s | 100.00% | 953.61s | 99.22% | 1.009
10 | 15 | 864.01s | 99.53% | 846.86s | 99.38% | 1.012
10 | 20 | 886.34s | 99.38% | 804.07s | 98.91% | 1.003
10 | 25 | 855.51s | 98.75% | 784.46s | 98.91% | 0.999
10 | 30 | 886.01s | 99.22% | 930.73s | 98.91% | 0.988
10 | 35 | 850.87s | 98.44% | 798.74s | 99.22% | 0.990
10 | 40 | 845.21s | 98.75% | 791.04s | 97.66% | 0.990
20 | 10 | 839.94s | 99.26% | 821.12s | 97.90% | 0.983
20 | 15 | 571.17s | 100.00% | 610.88s | 98.52% | 1.018
20 | 20 | 432.93s | 99.38% | 510.72s | 97.78% | 1.022
20 | 25 | 479.72s | 99.63% | 421.50s | 97.86% | 1.009
20 | 30 | 433.36s | 99.42% | 429.16s | 98.36% | 1.007
20 | 35 | 418.83s | 98.52% | 409.86s | 98.19% | 1.002
20 | 40 | 434.86s | 98.44% | 420.46s | 97.66% | 0.997
40 | 10 | 748.94s | 94.17% | 1256.09s | 96.57% | 1.044
40 | 15 | 506.25s | 95.99% | 534.42s | 96.88% | 0.964
40 | 20 | 383.51s | 99.24% | 412.37s | 96.65% | 1.027
40 | 25 | 308.15s | 98.86% | 347.50s | 96.65% | 1.025
40 | 30 | 351.54s | 98.66% | 305.50s | 96.47% | 0.997
40 | 35 | 279.30s | 98.73% | 252.70s | 96.32% | 1.009
40 | 40 | 257.62s | 97.88% | 250.74s | 96.65% | 1.009
Table 1: Summary of agn and aeasgd experiments using different distributed
hyperparameters ($n$ and $\lambda$). From these experiments we find that agn
performs better in terms of training and validation accuracy in the presence
of a higher number of asynchronous workers, and a reduced communication
frequency. We also include the temporal efficiency of agn and aeasgd compared
to different distributed hyperparameters. Using this information, we can
deduce that agn is outperforming aeasgd in 69.73% of the cases, which is
significantly better. Furthermore, this statistic includes cases which are
known where agn is performing badly, i.e., small amount of asynchrony, low
communication frequency, and high amount of asynchrony, and high communication
frequency.

##  5 Conclusion

This work introduces a novel distributed optimization procedure. We make
identical _practical_ assumptions with respect to constraints as easgd, i.e.,
high communication costs. However, agn is not effected by equilibrium
conditions which incapacitate the converge rate of the optimization process,
which are present in easgd Hermans (2017). As a result, we turned to downpour,
and allowed for more local exploration by sending _accumulated gradients_ to
the parameter server. However, this approach diverged even faster than regular
downpour, with the difference that data was processed significantly faster due
to the reduced waits.

Therefore, downpour was adapted to use the time between parameter updates more
efficiently by computing a _better_ gradient based on a normalized sequence of
first-order gradients, thus obtaining Accumulated Gradient Normalization.
Furthermore, we show that agn outperforms existing distributed optimizers in
terms of convergence rate in the presence of a large amount of concurrency and
communication constraints. Since _stability_ is also important in distributed
optimization, we introduce a new metric called _temporal efficiency_ which is
defined as the ratio between the integrated area of training metrics of two
different optimizers. As a result, not only the final training accuracy is
considered, but also the stability, and time required to reach an accuracy
level.

To conclude, agn achieves this result by computing a better _direction_ of the
gradient based on a sequence of first order gradients which can be computed
locally without any communication with the centralized model. This direction
also reduces the negative effects of implicit momentum in highly concurrent
environment as most workers will point in the general direction of a minimum,
thereby making agn more robust to distributed hyperparameterization such as
the number of workers and communication frequency. Although, as the number of
workers increases, a decline in training and validation accuracy is still
observed due to the amount of implicit momentum. A natural response would be
to lower the communication frequency (increase $\lambda$). However, this would
increase the amount of local exploration with the possibility that a subset of
workers might end up in different minima.

For possible future work, it would be of interest to explore if adaptive
communication frequencies might benefit the optimization process. In fact, in
small gradient environments (e.g., close to a minima) it might be beneficial
to _not_ normalize the accumulated gradients since the first-order gradient
updates are relatively small anyway.

##  6 Acknowledgements

We would like the team members of CERN IT-DB for supporting this work,
especially Zbigniew Baranowski and Luca Canali. We also thank Vlodimir Begy
for the insightful discussions. Finally, we thank the Dutch National Science
Foundation NWO for financial support through the project SWARMPORT (NWO
project number 439.16.108).

## References

  * Dean et al. (2012) Jeffrey Dean, Greg Corrado, Rajat Monga, Kai Chen, Matthieu Devin, Mark Mao, Andrew Senior, Paul Tucker, Ke Yang, Quoc V Le, et al.  Large scale distributed deep networks.  In _Advances in neural information processing systems_ , pages 1223–1231, 2012.
  * Hadjis et al. (2016) Stefan Hadjis, Ce Zhang, Ioannis Mitliagkas, Dan Iter, and Christopher Ré.  Omnivore: An optimizer for multi-device deep learning on CPUs and GPUs.  _arXiv preprint arXiv:1606.04487_ , 2016.
  * Hermans (2017) Joeri Hermans.  On Scalable Deep Learning and Parallelizing Gradient Descent.  Master’s thesis, Maastricht University, Jul 2017.  URL http://cds.cern.ch/record/2276711.  Presented 06 Jul 2017.
  * Ho et al. (2013) Qirong Ho, James Cipar, Henggang Cui, Seunghak Lee, Jin Kyu Kim, Phillip B Gibbons, Garth A Gibson, Greg Ganger, and Eric P Xing.  More effective distributed ML via a stale synchronous parallel parameter server.  In _Advances in neural information processing systems_ , pages 1223–1231, 2013.
  * Jiang et al. (2017) Jiawei Jiang, Bin Cui, Ce Zhang, and Lele Yu.  Heterogeneity-aware distributed parameter servers.  In _Proceedings of the 2017 ACM International Conference on Management of Data_ , pages 463–478. ACM, 2017.
  * Kingma and Ba (2014) Diederik Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_ , 2014.
  * LeCun et al. (1998) Yann LeCun, Corinna Cortes, and Christopher JC Burges.  The MNIST database of handwritten digits, 1998.
  * Louppe and Geurts (2010) Gilles Louppe and Pierre Geurts.  A zealous parallel gradient descent algorithm.  _Learning on Cores, Clusters and Clouds workshop, NIPS, 2010_ , 2010\.
  * Mitliagkas et al. (2016) Ioannis Mitliagkas, Ce Zhang, Stefan Hadjis, and Christopher Ré.  Asynchrony begets momentum, with an application to deep learning.  In _Communication, Control, and Computing (Allerton), 2016 54th Annual Allerton Conference on_ , pages 997–1004. IEEE, 2016.
  * Recht et al. (2011) Benjamin Recht, Christopher Re, Stephen Wright, and Feng Niu.  Hogwild: A lock-free approach to parallelizing stochastic gradient descent.  In _Advances in Neural Information Processing Systems_ , pages 693–701, 2011.
  * Zhang et al. (2015) Sixin Zhang, Anna E Choromanska, and Yann LeCun.  Deep learning with elastic averaging SGD.  In _Advances in Neural Information Processing Systems_ , pages 685–693, 2015.