11institutetext: Universitat Politècnica de Catalunya, Barcelona, Spain
11email<EMAIL_ADDRESS><EMAIL_ADDRESS>
# Monte-Carlo Sampling applied to Multiple Instance Learning for Histological
Image Classification

Marc Combalia  0000-0001-5237-4256 Verónica Vilaplana  0000-0001-6924-9961

###### Abstract

We propose a patch sampling strategy based on a sequential Monte-Carlo method
for high resolution image classification in the context of Multiple Instance
Learning. When compared with grid sampling and uniform sampling techniques, it
achieves higher generalization performance. We validate the strategy on two
artificial datasets and two histological datasets for breast cancer and sun
exposure classification.

###### Keywords:

histological image classification deep learning multiple instance learning
patch sampling Monte-Carlo methods.

##  1 Introduction

Deep learning is widely used for image classification with great success [4]
[9]. However, neural networks can not be directly applied to very high
resolution images, such as Whole Slide Tissue images, due to the high
computational cost involved. A common solution consists in dividing the image
into patches and using patch-level annotations to train a supervised
classifier. However, patch-level annotations are not usually available,
especially when working with medical datasets. On the contrary, image-level
annotations are much easier to obtain so practitioners have used Multiple
Instance Learning (MIL) to train patch-level classifiers in a weakly
supervised manner, aggregating patch-level predictions into image-level scores
[10] [5] [7] [6].

When the input images are small enough, the MIL formulation can be implemented
using a global Max Pooling layer at the output of a Fully Convolutional
Network [8]. However, in the case of high resolution images, this
implementation is not possible due to memory constraints. This is why patches
are usually sampled using a regular grid (with or without overlap) [5] [2]
before being fed to the neural network. Grid sampling may skip some zones in
the image which might be relevant for classification, and concentrate too much
effort in zones which are not. In this work we propose a novel patch sampling
strategy which extracts knowledge from the network to focus attention on the
most discriminative regions in an image for a given instant in the training
process, permitting better convergence and higher generalization performance.
We compare this approach to uniform sampling and conventional grid sampling on
two artificial and two histological datasets.

##  2 Materials and methods

###  2.1 Multiple Instance Learning

The Multiple Instance Learning formulation permits training a patch-based
classifier with only image-level annotations, aggregating patch level
predictions into image-level scores.

Multiple Instance Learning is a type of weakly supervised learning algorithm
where training data is arranged in bags, where each bag contains a set of
instances $X=\\{x_{1},x_{2},...,x_{M}\\}$, and there is one single label $Y$
per bag, $Y\in\\{0,1\\}$ in the case of a binary classification problem. It is
assumed that individual labels $y_{1},y_{2},...,y_{M}$ exist for the instances
within a bag, but they are unknown during training. In the standard Multiple
Instance assumption (SMI), a bag is considered negative if all its instances
are negative. On the other hand, a bag is positive, if at least one instance
in the bag is positive [11].

The MIL formulation has been often used to solve the problem of high
resolution image classification. An image (bag) is divided into $M$ patches
(instances), and the patches pertaining to the same image are treated jointly
in the classifier. If an image is positive ($Y=1$), it will contain at least
one positive patch ($y_{m}=1$ at least for one m). On the contrary, if the
image is negative ($Y=0$), all its patches will be negative ($y_{m}=0$ for all
m). Then, the $max$ operator can be used to aggregate patch predictions to
obtain an image-wise score: $\hat{Y}=max_{m}(\hat{y}_{m})$, where
$\hat{y}_{m}$ is the prediction for patch $m$. When using this aggregating
function, the weights of the network will be updated with the information of
only one patch per image. Other less strict aggregating functions have been
proposed in the literature [10] [6] [11], which use not only the highest
scoring patch but an aggregation of more than one patch prediction per image.

###  2.2 Patch sampling

Since the neural network will use a small subset of patches to update its
weights at every iteration, it is important to select an adequate sampling
strategy. The traditional grid-sampling strategy, a sampling strategy based on
a uniform random variable, and a novel sampling strategy based on sequential
Monte Carlo methods are reviewed in this section.

####  2.2.1 Grid sampling:

The extraction of patches is performed in a grid-like manner; the image is
divided into a regular grid of patches, with or without overlap. Given that
the sampling is performed only once in the whole training process, grid
sampling is the fastest sampling strategy. However, the subset of patches to
train will be the same throughout the epochs. Also, this strategy will sample
patches from not discriminative regions in the image even after the network
has learned that they are not relevant for classification.

####  2.2.2 Uniform sampling:

A uniform distribution is applied to select the patches used to train the
neural network at every epoch. This means that the neural network will see a
different subset of patches every time the image goes through the training
loop. As the number of training epochs increases, the network will tend to see
all possible patches from every image. Nevertheless, this approach will sample
patches from irrelevant regions in the image even after they have been learned
to be non-discriminative.

####  2.2.3 Monte-Carlo sampling:

The objective of this sampling strategy is to concentrate the effort on the
most relevant regions of a high resolution image. When a new image is fed into
the network, its output probability map is estimated using a variation of a
sequential Monte-Carlo method. New patches are obtained from regions around
high activations in the output probability map.

  1. 1.

Initialization: $n$ image points are sampled following a uniform distribution.

  2. 2.

Evaluation: a patch centered on each point is sampled and forwarded through
the network. The output produced by the patch is used to represent the point.

  3. 3.

Normalization: the point scores are re-scaled between 0 to 1. The points whose
value is closer to 1 will be the ones corresponding to patches which have
obtained the highest output from the neural network.

  4. 4.

Re-sampling: the lowest scoring points are removed, and (the same number of)
new points are re-sampled on top of the ones which have a higher score. This
re-sampling step can be done deterministically (re-sampling the $l$ lowest
scoring points) or stochastically (using a random uniform distribution).

  5. 5.

Displacement: the new points are slightly displaced according to a random 2D
Gaussian distribution.

  6. 6.

Go to step 2 for k iterations

The proposed method relocates patches which have not been relevant for
classification into more discriminative regions in the image, that is, around
the patches with higher activations. This process is performed at every batch,
since the discriminative regions in the image will vary as the network learns
during the training process.

##  3 Experiments

###  3.1 Datasets

####  3.1.1 Artificial datasets:

Two binary artificial datasets named MNIST-Sparse and MNIST-Clustered have
been created to test the performance of the various sampling algorithms. Each
image of 1024x1024 pixels consists of an aggregation of 28x28 images from the
MNIST dataset. A positive image contains at least one MNIST digit
corresponding to the class ’9’, while a negative image contains only digits
corresponding to the other classes (’0’ to ’8’). Digit ’9’ has been chosen
because it can be mistaken for ’4’ or ’5’ [6].

The purpose of these datasets is to imitate two different distributions found
in histological images. The MNIST-Sparse dataset has the relevant regions
(where the target number is localized) spread through the image. On the
contrary, the MNIST-Clustered dataset has the target patches concentrated in
space. The training and test subsets contain 1000 and 400 images,
respectively. Figure 2 shows examples extracted from the two datasets, where
the target digits ’9’ have been highlighted using red squares.

(a)

(b)

Figure 1: Images extracted from MNIST-Sparse dataset (a) and MNIST-Clustered
dataset (b). Target numbers (9) are marked with red squares in both images

####  3.1.2 Histological datasets:

The sampling strategies are also evaluated on two histological datasets: the
ICIAR Grand Challenge 2018 dataset Part A [1], and the Skin subset of the GTEx
dataset [3].

The ICIAR dataset is formed by 400 breast microscopy tissue images divided in
4 different classes: normal, benign, invasive and in-situ carcinoma. For each
class, there are 100 different Hematoxylin & Eosin stained images with a
dimension of 2048 x 1536 pixels. The images are in RGB color space. We use
benign and invasive classes to create a binary problem on which to test the
algorithms, which results in 160 images for training and 40 for test. The
images have already been pre-cropped from labeled Whole Slide Tissue images,
and hence, from a MIL perspective, a large number of patches (instances) that
we extract from an image (a bag) are expected to be consistent with the image
label.

The Skin subset of the GTEx dataset is composed of approximately 10000 pieces
of skin, which correspond to sun-exposed and not sun-exposed tissues. The
smallest slide available (8 microns per pixel) is used to train the neural
networks. The training and test splits contain 8000 and 2000 images,
respectively.

(a)

(b)

(c)

(d)

Figure 2: Images extracted from the ICIAR Part A Dataset for benign (a) and
invasive (b) classes; and the GTEx Skin dataset for the sun-exposed (c) and
not-sun-exposed (d) classes.

###  3.2 Results

A VGG-like architecture [9] with a receptive field of 40x40 pixels is trained
to evaluate the performance of the sampling algorithms on the MNIST-Sparse and
MNIST-Clustered datasets. A higher capacity neural network based on the ResNet
[4] architecture is used in the ICIAR Part A and GTEx Skin datasets with a
receptive field of 224x224, since these datasets are more challenging than the
MNIST toy example.

Patches are extracted without overlap for the grid sampling strategy, and the
same number of patches/points is used for the uniform and Monte-Carlo training
strategies. This results in a total of 625 patches per image for the MNIST
dataset and 54 patches per image for the ICIAR dataset. The number of patches
in the case of the GTEx dataset is variable since images have different sizes.
One iteration is used on the Monte-Carlo algorithm every time the images go
through the training loop, as it was found to be enough to perform a correct
estimation of the output probability map of an image.

Patch scores are aggregated using the $max$ operator into an image-level score
for the MNIST and the GTEx Skin datasets, since relevant information is
expected to be very localized in space. On the other hand, the Top-K (with K =
10) aggregating function is used in the ICIAR Part A dataset, since patches
are expected to be consistent with the label of the image. The Top-K function
will use the top K scoring instances in a bag to obtain the bag-level
prediction.

The neural networks are trained with Adam optimization. Grid sampling with 50
% overlap is used to sample patches from the images at test time, and the max
function is used to aggregate patch scores into image-wise predictions. The
accuracy results on the test set for each sampling strategy are shown in Table
1 and the train and validation accuracy curves for the MNIST-Sparse and MNIST-
Clustered datasets are presented in Figures 3 and 4, respectively.

Table 1: Test accuracies for the various sampling strategies on the MNIST-Sparse, MNIST-Clustered, ICIAR Part A and GTEx Skin datasets Test accuracy | MNIST Sparse | MNIST Clust | ICIAR PartA | GTEx Skin
---|---|---|---|---
Grid sampling | 0.520 $\pm$ 0.01 | 0.523 $\pm$ 0.01 | 0.776 | 0.826
Uniform sampling | 0.759 $\pm$ 0.03 | 0.83 $\pm$ 0.01 | 0.790 | 0.920
Monte-Carlo sampling | 0.825 $\pm$ 0.02 | 0.852 $\pm$ 0.03 | 0.847 | 0.942

Figure 3: Train and validation accuracy on the MNIST-Sparse dataset for the
proposed sampling strategies: grid (left), uniform (center), Monte-Carlo
(right).

Figure 4: Train and validation accuracy on the MNIST-Clustered dataset for the
proposed sampling strategies: grid (left), uniform (center), Monte-Carlo
(right).

##  4 Discussion

Figures 3 and 4 illustrate how the sampling strategy used for training can
have a very large impact on the final performance of the neural network. This
is especially true in cases where the receptive field of the network is small
compared to the spatial extension of the discriminative features, as it is on
the MNIST-Sparse and MNIST-Clustered datasets, where target digits are patches
of 28x28 pixels and clusters of 40x40 pixels, respectively. In these cases,
the grid sampling technique would need a very large overlap between patches to
provide a good subset of patches to the network, which would result in a
substantial increase in training time. While the neural network trained with
the grid sampling strategy is unable to learn the true distribution of the
data, the stochastic nature of the uniform and Monte-Carlo sampling strategies
permits seeing a different subset of patches at every epoch. This allows the
network to correctly find the discriminative regions on the image. In
addition, once the network has learned which regions in the image are the
relevant ones, the Monte-Carlo strategy samples only from these regions. This
results in a higher validation accuracy, especially in the MNIST-Clustered
dataset.

Figure 5 shows the output probability maps of one positive image from the
MNIST-Clustered database for each sampling strategy. The neural network
trained with the grid sampling strategy fails to localize the target digit;
the patch with the maximum score contains a ’4’. On the other hand, the neural
networks trained with the stochastic sampling strategies succeed activating on
the regions containing the target digit ’9’. The Monte-Carlo sampling strategy
produces a more accurate map.

The stochastic sampling approaches outperform the grid sampling also on the
histological datasets. This time, however, the neural networks trained with
the grid sampling strategy perform correctly. In this case the neural networks
have a larger receptive field, and the discriminative image regions are
smaller compared to the receptive field. However, the neural networks still
benefit from the Monte-Carlo training strategy, which focuses on the relevant
regions, improving accuracy. Figure 6 shows how the distribution of samples in
the Monte-Carlo approach changes as the neural network learns. In the first
epochs, the Monte-Carlo strategy behaves very similarly to the uniform
sampling strategy. However, as the network keeps learning, the Monte-Carlo
sampling strategy further concentrates its effort on the discriminative
regions.

(a)

(b)

(c)

(d)

(e)

(f)

(g)

Figure 5: Input image (a), output probability map for grid sampling (b),
uniform sampling (c) and Monte-Carlo sampling (d). Figures (e), (f) and (g)
show the maximally activated patch for grid, uniform and Monte-Carlo sampling,
respectively. Figure 6: Black points correspond to points sampled with Monte-
Carlo at epochs 2, 6, 8 and 37 during the training process of the neural
network for the sun-exposure classification problem.

##  5 Conclusions

In this paper we have shown that a simple grid sampling technique can
compromise the performance of a network, especially when its receptive field
is small compared to the size of the relevant features in the image. We have
proposed a sampling strategy based on a sequential Monte-Carlo method for high
resolution images which samples from the most relevant regions during the
training process, overcoming the problems of grid sampling. We have
illustrated its capabilities on two artificial and two histological datasets
for breast cancer and sun exposure classification.

####  5.0.1 Acknowledgments:

This work has been partially supported by the project MALEGRA TEC2016-75976-R
financed by the Spanish Ministerio de Economía y Competitividad and the
European Regional Development Fund.

## References

  * [1] BACH: Iciar 2018 (2018), https://iciar2018-challenge.grand-challenge.org/
  * [2] Campanella, G., Werneck Krauss Silva, V., J. Fuchs, T.: Terabyte-scale deep multiple instance learning for classification and localization in pathology (05 2018)
  * [3] Carithers, L.J., Ardlie, K., Barcus, M., Branton, P.A., Britton, A., Buia, S.A., Compton, C.C., DeLuca, D.S., Peter-Demchok, J., Gelfand, E.T., et al.: A novel approach to high-quality postmortem tissue procurement: the gtex project. Biopreservation and biobanking 13(5), 311–319 (2015)
  * [4] He, K., Zhang, X., Ren, S., Sun, J.: Deep residual learning for image recognition. CoRR abs/1512.03385 (2015), http://arxiv.org/abs/1512.03385
  * [5] Hou, L., Samaras, D., Kurc, T.M., Gao, Y., Davis, J.E., Saltz, J.H.: Patch-based convolutional neural network for whole slide tissue image classification. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. pp. 2424–2433 (2016)
  * [6] Ilse, M., Tomczak, J.M., Welling, M.: Attention-based deep multiple instance learning. CoRR abs/1802.04712 (2018), http://arxiv.org/abs/1802.04712
  * [7] Mercan, C., Mercan, E., Aksoy, S., Shapiro, L.G., Weaver, D.L., Elmore, J.G.: Multi-instance multi-label learning for whole slide breast histopathology. In: Medical Imaging 2016: Digital Pathology. vol. 9791, p. 979108. International Society for Optics and Photonics (2016)
  * [8] Pathak, D., Shelhamer, E., Long, J., Darrell, T.: Fully convolutional multi-class multiple instance learning. CoRR abs/1412.7144 (2014), http://arxiv.org/abs/1412.7144
  * [9] Simonyan, K., Zisserman, A.: Very deep convolutional networks for large-scale image recognition. CoRR abs/1409.1556 (2014), http://arxiv.org/abs/1409.1556
  * [10] Tomczak, J.M., Ilse, M., Welling, M.: Deep Learning with Permutation-invariant Operator for Multi-instance Histopathology Classification. ArXiv e-prints (Dec 2017)
  * [11] Wang, X., Yan, Y., Tang, P., Bai, X., Liu, W.: Revisiting multiple instance neural networks. Pattern Recognition 74, 15–24 (2018)


# Enhancing Inertial Hand based HAR through Joint Representation of Language,
Pose and Synthetic IMUs

Vitor Fortes Rey  DFKI KaiserslauternGermany ,  Lala Shakti Swarup Ray  RPTU
KL, DFKIKaiserslauternGermany ,  Dr. Xia Qingxin  HKUSTHong KongChina ,  Prof.
Dr. Kaishun Wu  Shenzhen UniversityShenzhenChina and  Prof. Dr. Paul Lukowicz
RPTU KL, DFKIKaiserslauternGermany

(2024)

###### Abstract.

Due to the scarcity of labeled sensor data in HAR, prior research has turned
to video data to synthesize Inertial Measurement Units (IMU) data,
capitalizing on its rich activity annotations. However, generating IMU data
from videos presents challenges for HAR in real-world settings, attributed to
the poor quality of synthetic IMU data and its limited efficacy in subtle,
fine-grained motions. In this paper, we propose Multi3Net, our novel multi-
modal, multitask, and contrastive-based framework approach to address the
issue of limited data. Our pretraining procedure uses videos from online
repositories, aiming to learn joint representations of text, pose, and IMU
simultaneously. By employing video data and contrastive learning, our method
seeks to enhance wearable HAR performance, especially in recognizing subtle
activities. Our experimental findings validate the effectiveness of our
approach in improving HAR performance with IMU data. We demonstrate that
models trained with synthetic IMU data generated from videos using our method
surpass existing approaches in recognizing fine-grained activities.

HAR, Sensor simulation, Multi-modal contrastive learning, Pretraining

††copyright: acmlicensed††journalyear: 2024††doi: XXXXXXX.XXXXXXX††conference:
Proceedings of the 2024 International Symposium on Wearable Computers; October
5–9, 2023; Melbourne, Austrailia††booktitle: Proceedings of the 2024
International Symposium on Wearable Computers (ISWC ’24), October 5–9, 2024,
Melbourne, Australia††submissionid: 8562††ccs: Computing methodologies
Learning latent representations††ccs: Computing methodologies Modeling and
simulation††ccs: Human-centered computing Ubiquitous and mobile computing
design and evaluation methods

##  1\. Introduction

Figure 1. Example of Ground truth IMU data and synthetic IMU data generated by
Kinect-based (IMUTube and Vi2IMU) and SMPL-based (Multi3Net) methods.

Human Activity Recognition (HAR) using wearable devices has garnered
increasing attention in real domains in recent years, such as healthcare
(Inoue et al., 2019), manufacturing (Xia et al., 2020), and fitness (Zhou et
al., 2022; Ray et al., 2024). However, HAR using wearable sensors has
benefited much less from recent advances in Deep Learning than fields such as
computer vision and natural language processing. This is, to a large extent,
due to the lack of large-scale (as compared to computer vision) repositories
of labeled training data for sensor-based HAR tasks. Existing studies have
utilized video data to synthesize Inertial Measurement Units (IMU) data to
mitigate the labeled data sparsity problem due to its abundance of activity-
related annotations, and its effectiveness has been substantiated in (Kwon et
al., 2020; Santhalingam et al., 2023; Rey et al., 2019), but those methods
cannot address fine-grained, subtle movements (Leng et al., 2024, 2023a) that
are often present in real activities in complex domains, such as sticking a
label in manufacturing or playing an instrument.

To utilize the monocular video data and synthesized IMU data for HAR in
complex domains faces two challenges: (1) Low-quality synthetic IMU data.
Existing approaches for generating synthetic IMU data from videos, which
require kinetic detection and motion capture, may introduce errors due to
lighting, body shapes, and occlusion, thus limiting IMU generation for complex
activities. Subtle motions, especially on the wrist, can be challenging to
simulate from monocular video due to the wrist’s degrees of freedom and its
relatively small size in pixels. For instance, as depicted in Figure 1, the
synthetic IMU data for the “pick-up paper” activity exhibits considerable
fluctuations and errors. While simulated data can capture part of the signal
characteristics, there is clearly a simulation gap. (2) Directly training on
synthetic IMU for HAR results in poor performance for fine-grained activities.
Due to inherent errors mentioned in (1), synthetic IMU data shows heightened
sensitivity to activities with smaller amplitudes or greater complexity. Thus
models trained with synthetic IMU data may not demonstrate superior
performance in HAR.

While shifts between real and simulated data can harm classification, pose
estimation for generating synthetic IMU can provide rich information about the
overall body motion and how it is perceived by wearable sensors. In this
study, we show how this relationship can be used for generating better IMU-
only representations by leveraging online videos and simulations. By learning
to match complex gestures (sign language) to their simulated IMU counterparts,
our method can obtain representations with fine-grained activity information
that can later be fine-tuned for IMU-only HAR, improving the overall
classifier and outperforming other approaches that directly train on simulated
data.

In this paper, we propose $\text{Multi}^{3}$Net, a multi-modal (text
description, Pose, IMU), multi-task (contrastive learning, Pose2IMU generation
IMU reconstruction), and multi-sensor(Left wrist IMU, Right wrist IMU) joint
representation framework to enhance the HAR performance in downstream tasks.
Firstly, we employ the Skinned Multi-Person Linear model (SMPL) (Loper et al.,
2023) to capture complex human poses with high fidelity and conduct pose
calibration to acquire highly accurate synthetic IMU data. Then, we leverage
contrastive learning for video descriptions$\leftrightarrow$pose, video
descriptions$\leftrightarrow$synthetic IMU, and pose$\leftrightarrow$synthetic
IMU to learn joint representations across modalities, facilitating the soft
adaptation of the pretrained model to target IMU-based HAR tasks. Finally, we
fine-tune the pretrained model using a small amount of target IMU data for
downstream HAR. The key contributions of this paper are as follows:

(1) $\text{Multi}^{3}$Net: A multi-modal, multi-task approach to train IMU-
only representations using videos, which can learn useful representations for
real data training only on simulated ones.

(2) A novel IMU simulation strategy based on SMPL to get better quality IMU
data though utilizing fixed bone lengths.

(3) Through extensive experimentation to demonstrate the effectiveness of the
proposed approach over other state-of-the-art IMU simulation pipelines through
IMU-based HAR.

##  2\. Related work

The main bottleneck in developing IMU-based HAR is the lack of rich datasets.
Labeled data collection is a cumbersome process due to the time needed for
annotation and the variability in sensor setups (position, sampling rate,
etc). Recent works have tried to ameliorate this problem either by data
simulation or better representation learning.

###  2.1. IMU Simulation

Various approaches have used other widely available modalities like text and
videos to generate the inertial data using 3D simulation and generative models
to generate IMU data and use it along with some real data to train HAR models.

Video to IMU models. In (Rey et al., 2019), virtual IMU data was generated
from video data, initially extracting 2D poses via OpenPose (Cao et al.,
2017), followed by the application of a regression model to translate
sequences of poses into IMU data. However, training the regression model
requires pre-collected pairs of pose and IMU data. Kwon et al. introduced
IMUSim (Young et al., 2011) to directly obtain IMU data from sequences of
poses. Nevertheless, the IMU data produced by the above methods often contain
considerable errors compared to actual IMU data, thus limiting the utility of
using generated data for complex HAR (Leng et al., 2023a, 2024). Santhalingam
et al. (Santhalingam et al., 2023) proposed a bi-directional LSTM-based model
to calibrate anomalous poses with the assistance of surrounding poses, aiming
to reduce the amount of incorrectly generated IMU data. However, it does not
entirely prevent errors in the translation from pose to generated IMU data.
Liu et al. (Liu et al., 2021) proposed a CNN-based model to automatically
calibrate errors between generated and real IMU data. However, the performance
of this approach is influenced by the characteristics of the training data.

Text to IMU models. Many studies (Leng et al., 2023b, 2024) have proposed the
utilization of textual descriptions converted into human poses for generating
IMU data. Various pretrained pose syntheses models, such as MotionGPT (Jiang
et al., 2024), T2M-GPT (Zhang et al., 2023), and MotionDiffuse (Zhang et al.,
2022), have been introduced into synthetic human poses, which are then
integrated with IMU generation models to obtain synthesized IMU data. However,
obtaining the pose is infeasible if the type of pose has never been
encountered during the training of the pose synthesis models. Thus, generating
IMU data from video has become the primary approach, especially in
professional domains.

###  2.2. Representation Learning

Contrastive learning has garnered attention in recent years due to its
efficacy in learning representations from data originating from diverse
domains. For instance, CLIP (Radford et al., 2021) learns visual and text
representations using paired images and text, achieving outstanding
generalization performance for downstream tasks. Moon et al. (Moon et al.,
2023) proposed a multi-modal contrastive framework and a pretraining approach
to align IMU data with text and video data, thereby projecting multi-modal
data representations into a joint space. Yang et al. (Yang et al., 2024)
further enhanced the contrastive framework between text and IMU data by
introducing a hierarchical temporal transformer to align important
representations. Different from the aforementioned multi-modal contrastive
approaches, our method exclusively utilizes video as input and generates both
human pose and highly accurate synthesized IMU data as inputs for the
contrastive model. This enables the creation of improved representation spaces
for video and IMU data.

##  3\. Approach

Figure 2. Overview of $\text{Multi}^{3}$Net architecture showcasing three
steps (1) Sensor simulation (2) Multitask pretraining (3) Downstream training
and evaluation.

Figure 2 depicts the overview of the proposed approach, comprising three
primary components: (1) IMU simulation, which generates human poses and high-
quality IMU data from video for pretraining; (2) $\text{Multi}^{3}\text{Net}$,
which pretrains the joint text, pose, and IMU representations; and (3)
downstream task that involves training to finetune the IMU encoder with real
IMU data from the target dataset and evaluating with the target IMU data.

###  3.1. IMU Simulation from Videos

By leveraging human motion capture files, we can precisely calculate both
linear acceleration and angular velocity of objects in motion. By tracking the
positions and orientations of markers attached to the body over time, we can
generate highly accurate data regarding their movement. The goal of this
section is to generate high-quality IMU data from video frames using IMUSim
(Young et al., 2011), a tool extensively utilized in synthetic IMU generation
(e.g., applications such as IMUTube (Kwon et al., 2020), IMUGPT (Leng et al.,
2023b, 2024), and etc). By leveraging human motion capture files calculated
from video frames, we can calculate both linear acceleration and angular
velocity of objects in motion. Tracking the positions and orientations of
markers attached to the human body over time enables us to generate IMU data
regarding the movement. To generate synthetic IMU, our approach draws partial
inspiration from the Orient3IMU model available in IMUSim removing the noise
parameters. We begin with MoCap Motions formatted in SMPL, leveraging Blender
to convert the underlying skeleton into an identical shape approximation of
specific measurements like height 1.7 meters of average human height for all
mocaps. Subsequently, we relocate the skeleton’s origin (Center of Feet) to
the (0,0,0) position and orientation. Transforming linear acceleration to
local coordinates considering Gravity can be done using:

(1)
$\mathbf{a}_{\text{local}}(t)=\mathbf{R}_{\text{local}}(t)\cdot\left(\frac{d^{2}\mathbf{r}_{\text{global}}(t)}{dt^{2}}-\mathbf{g}_{\text{global}}\right)$

where: $\mathbf{a}_{\text{local}}(t)$ is the linear acceleration of the rigid
body in the local coordinate system $\mathbf{R}_{\text{local}}(t)$ is the
rotation matrix describing the orientation of the local coordinate system
relative to the global coordinates. $\mathbf{a}_{\text{global}}(t)$ is the
linear acceleration of the rigid body in the global coordinate system
$\mathbf{r}_{\text{global}}(t)=[x(t),y(t),z(t)]^{T}$ is the position vector of
the rigid body in global coordinates $\mathbf{g}_{\text{global}}$ is the
acceleration due to gravity in the global coordinate system expressed as
$\mathbf{g}_{\text{global}}=[0,-9.8,0]^{T}$ where $g$ is the magnitude of
acceleration due to gravity. Transforming linear acceleration to local
coordinates considering Gravity:

Similarly, after calculating global angular velocity from orientation, we
transform it to local coordinates:

(2)
$\bm{\omega}_{\text{local}}(t)=\mathbf{R}_{\text{local}}(t)^{T}\cdot\bm{\omega}_{\text{global}}(t)$

where: $\bm{\omega}_{\text{local}}(t)$ is the angular velocity of the rigid
body in the local coordinate system.

The primary motivation behind adopting our own model over IMUSim lies in the
absence of IMU calibration signals necessary for generating good IMU data in
IMUSim. Without these signals, the generated data tends to be significantly
inferior and out of range of the original signal. Utilizing our model also
affords us greater uniformity and control over our dataset. We can ensure
consistent starting positions and orientations, as well as uniform human size
across all mocap files, simplifying the neural network’s task of establishing
correlations within this dataset.  Additionally, employing SMPL bodies for
pose generation offers advantages to Kinematic 3D pose estimations, as the
bone lengths of SMPL bodies remain constant, and the model provides 3D angles
rather than identical positions. Furthermore, Kinematic 3D pose estimations
require the use of Inverse Kinematics afterward to convert the 3D pose into a
Motion Capture file, potentially leading to the loss of information during
this process as discussed in the Vi2IMU paper.

###  3.2. $\text{Multi}^{3}$Net for Pretraining

After getting the pose and IMU data generated from video data, we then
pretrain joint representations of text, pose, and IMU data via
$\text{Multi}^{3}$Net, which consists of 3 tasks (1) multi-modal contrastive
learning, (2) Pose2IMU regression, and (3) IMU reconstruction.

#### Multi-modal Contrastive learning

As illustrated in Figure 2 (2), the pretraining model comprises three
encoders, each mapping text, pose, and IMU data to a respective latent space.
Regarding the Text encoder, the input consists of the embedding of the text
description of the corresponding video, derived from the output of the last
hidden layer of a large pretrained model Instructor (Large) (Su et al., 2022).
The output of the Text encoder is denoted as $e_{t}$. The encoder architecture
is based on ResNet architecture with three residual blocks each containing a
1D CNN layer, followed by a batch normalization layer, and a Residual layer.
In contrast to IMU2CLIP, where the text encoder is frozen to facilitate
modality transitivity, in our approach, the text encoder is trainable during
pretraining to acquire joint representations for multi-modality data. Similar
to the Text encoder, the Pose encoder takes the SMPL pose parameters of the
body with (22, 3) tensor except for the two hand parameters, and both left and
right hand as Mano parameters (30, 3) tensors to generate the output embedding
of $e_{p}$. The pose encoder is based on the spatial-temporal transformer
architecture of PoseFormer (Zheng et al., 2021) where each module is passed to
a spatial attention block followed by a temporal attention block to generate
intermediate embedding. For the IMU encoder, to facilitate adaptable
processing across diverse scenarios, we utilize identical multi-headed
attention blocks with positional embedding for data collected from both the
left and right wrists. The input to the IMU encoder consists of synthetic data
segments for each wrist, and the output comprises embedding for the left and
right wrists, denoted as $e_{sl}$ and $e_{sr}$, respectively. Although both
encoders share identical architecture the learnable weights are different.

#### Pose2IMU Regression

The Pose2IMU regression block consists of a Pose encoder and a Pose2IMU
decoder, which has a CNN architecture with three ConvTranspose and Unpooling
layers along with Batch normalization and Dropout blocks. Since activities in
real scenarios typically involve fine-grained motions, the Pose2IMU decoder is
designed to guarantee that the input pose encoder encompasses the requisite
features by reconstructing the IMU data from the encoder. For the Pose2IMU
decoder, the input is $e_{p}$, and the output is the predicted result of the
corresponding synthetic IMU data, denoted as $X_{p}$. The decoder architecture
is based on PSN from PresSim (Ray et al., 2023).

#### IMU Reconstruction

Similar to the Pose2IMU regression block, the IMU reconstruction block
comprises two IMU encoders and an IMU reconstructor. This IMU reconstructor
features an identical CNN architecture with Section 3.2 that takes the
concatenation of $[e_{sl},e_{sr}]$ and uses one linear layer to map it back
from (256, 2) to 256 vectors to reconstruct one frame input IMU instance. The
predicted IMU data is denoted as $X_{s}$.

#### Loss function

To acquire joint representations for text, pose, and IMU from the encoders, we
propose using instance discrimination by minimizing the InfoNCE loss (Oord et
al., 2018) for each pair of encoders, which encourages similar representations
for positive pairs closer and pushes representations of negative pairs apart,
leading to meaningful feature representations, the InfoNCE loss is defined as
follows:

(3)
$\text{InfoNCE}(q,k)=-\frac{1}{N}\sum_{i=1}^{N}\log\left(\frac{e^{s(q_{i},k_{i})}}{e^{s(q_{i},k_{i})}+\sum_{j=1,j\neq
i}^{N}e^{s(q_{i},k_{j})}}\right)$

where $N$ is the batch size, $q_{i}$ and $k_{i}$ are the representations of
the $i$-th data sample under two different augmentations, $s(q_{i},k_{i})$ is
the cosine similarity score between $q_{i}$ and $k_{i}$, normalized by the
temperature, and $e$ denotes the exponential function.

The cosine similarity score $s(q_{i},k_{i})$ is computed as:

(4) $s(q_{i},k_{i})=\frac{q_{i}\cdot k_{i}}{\lVert q_{i}\rVert\cdot\lVert
k_{i}\rVert}$

where $\cdot$ denotes the dot product and $\lVert\cdot\rVert$ denotes the L2
norm.

Thus, the overall InfoNCE loss of the pairs of encoders is formulated as
follows:

(5)
$\displaystyle\textbf{L}_{Contrastive}=\text{InfoNCE}(e_{t},e_{p})+\text{InfoNCE}(e_{t},e_{sl})$
$\displaystyle+\text{InfoNCE}(e_{t},e_{sr})+\text{InfoNCE}(e_{p},e_{sl})$
$\displaystyle+\text{InfoNCE}(e_{p},e_{sr})+\text{InfoNCE}(e_{sl},e_{sr})$

To ensure that the pose and IMU encoders preserve the necessary features to
represent activities, MSE loss is applied for Pose2IMU regression and IMU
reconstruction. Taking $X_{v}$ as the synthetic IMU data, the MSE loss is
defined as follows:

(6) $\displaystyle\textbf{L}_{MSE}$ $\displaystyle=\textbf{L}_{MSE\
Pose2IMU}+\textbf{L}_{MSE\ IMURec}$
$\displaystyle=\frac{1}{N}\sum_{j=1}^{N}\frac{1}{l}\sum_{i=t}^{t+l}(X^{i}_{v}-X^{i}_{p})^{2}+(X^{i}_{v}-X^{i}_{s})^{2}$

where $X^{i}_{v}$ represents the $i$-th synthetic IMU data point, $X^{i}_{p}$
and $X^{i}_{s}$ denote the prediction values of the pose2IMU and IMU2IMU
decoders, respectively. $l$ represents the segment length.

The overall loss for pertaining is
$\textbf{L}_{Contrastive}+\textbf{L}_{MSE}$.

###  3.3. Downstream Task

After pretraining the model using video resources containing rich hand
movements, we can subsequently finetune the IMU encoder with a small amount of
target IMU data. This process enables us to achieve robust HAR performance
even with limited data. The model structure consists of the pretrained IMU
encoder and a classifier. To prevent the bottleneck problem we take the
intermediate output $(6,256)$ of the pretrained encoder instead of the 1D
feature $256$ the final output during pretraining.

We used a hybrid decoder where the classifier processes input feature
$(6,256)$ through a sequence of neural network layers, starting with a CNN
layer followed by normalization and ReLU activation. The features are then
reshaped and passed through two stages of multi-head attention mechanisms,
each followed by normalization and activation, to enable the model to focus on
different parts of the input. After each attention stage, the features are
further transformed linearly and re-normalized. Finally, the processed
features are reshaped, and the classes are obtained by averaging across a
specific dimension.

Given a window of sensor data $\bm{X}^{[t:t+l]}$ as the input and
$\bm{Y}^{[t:t+l]}=[\bm{y}_{t},\bm{y}_{t+1},...,\bm{y}_{t+l}]$ as the ground
truth label, the classifier is trained to output estimates that have minimum
errors to $\bm{Y}^{[t:t+l]}$. We train the downstream model using the cross-
entropy loss using the Adam optimizer. The objective function is formulated as
follows:

(7) $\textbf{L}_{Cross\
Entropy}=-{\textstyle{\sum_{i=t}^{t+l}}\sum_{c=1}^{C}}\bm{y}_{ic}\text{log}(p_{ic}),$

where $\bm{y}_{ic}$ is a one-hot vector corresponding to the $i$-th prediction
of class $c$, and $p_{ic}$ shows the prediction of $x_{l}^{i}$ belonging to
class $c$.

##  4\. Evaluation

###  4.1. Dataset and Training Details

We utilized two types of datasets (1) Large video datasets with rich hand
activity representations for pertaining, and (2) Target inertial HAR datasets
with wrist IMUs. To maintain consistency, all video data were resampled to 60
frames per second.

How2Sign Dataset (Duarte et al., 2021). This dataset contains more than 80
hours of sign language videos and corresponding transcripts, which provide
rich information on hand and wrist movements. This dataset is applied only for
pre-training.

GRAB Dataset (Taheri et al., 2020). This dataset contains approximately 4
hours of MoCap of the entire body of subjects grabbing everyday objects. It
comprises data from 10 subjects engaging with 51 different everyday objects.
This dataset is applied only for pre-training.

OpenPack Dataset(Yoshimura et al., 2024). Acceleration data from both the left
and right wrists of 5 workers were collected using an Empatica E4 wristband
with a sampling rate of 30Hz while they performed a packaging task comprising
11 classes of activities. The workers’ activities were also recorded on video
to serve as ground truth.

MM-Fit Dataset(Strömbäck et al., 2020). This dataset comprises data from 10
subjects engaging in 10 gym exercises. IMU data from Mobvoi TicWatch Pro
devices, sampled at 100Hz, capture detailed movement information from the
participants’ wrists. Additionally, RGB data captured at 30Hz offers visual
context for the performed exercises.

The model is written in Pytorch and trained on an Ubuntu system with Nvidia
A6000 ada GPU and AMD Ryzen 7900X CPU. We used Adam optimizer for training.
Both pretraining and downstream training are done for 300 epochs with the
early stopping of patience 20 and a learning rate scheduler of patience 10
starting with 0.001.

###  4.2. Quantitative Results

Table 1. Weighted Macro F1-score for OpenPack dataset Model | Left wrist | Both wrists
---|---|---
DCL (Real) | 45.80 $\pm$ 1.97 | 49.48 $\pm$ 2.23
DCL (Real + Synthetic Vi2IMU) |  35.41 $\pm$ 1.12 |  37.86 $\pm$ 1.06
DCL (Real + Synthetic IMUTube) |  36.98 $\pm$ 2.23 |  48.66 $\pm$ 0.63
Base (Real) |  31.43 $\pm$ 0.25 | 53.84 $\pm$ 0.15
Base (Real + Synthetic Vi2IMU) | 40.03 $\pm$ 0.47 |  32.60 $\pm$ 0.54
Base (Real + Synthetic IMUTube) |  24.96 $\pm$ 0.87 |  31.88 $\pm$ 1.69
IMU Reconstruction (how2sign:frozen) |  19.99 $\pm$ 0.32 |  30.53 $\pm$ 0.27
IMU Reconstruction (how2sign:not frozen) |  31.79 $\pm$ 0.41 | 53.44 $\pm$ 0.36
Contrastive pretrain (how2sign:frozen) |  20.64 $\pm$ 0.22 |  30.18 $\pm$ 0.29
Contrastive pretrain (how2sign:not frozen) |  39.86 $\pm$ 0.34 | 59.11 $\pm$ 0.40
IMU Reconstruction (GRAB:frozen) |  20.48 $\pm$ 0.18 |  30.22 $\pm$ 0.26
IMU Reconstruction (GRAB:not frozen) |  31.41 $\pm$ 0.19 | 54.00 $\pm$ 0.30
Contrastive pretrain (GRAB:frozen) |  21.19 $\pm$ 0.20 |  32.82 $\pm$ 0.33
Contrastive pretrain (GRAB:not frozen) |  33.10 $\pm$ 0.28 | 54.91 $\pm$ 0.37
$\text{Multi}^{3}$Net (how2sign:frozen) |  20.53 $\pm$ 0.23 |  30.88 $\pm$ 0.31
$\text{Multi}^{3}$Net (how2sign:not frozen) |  42.32 $\pm$ 0.13 | 61.74 $\pm$ 0.22
$\text{Multi}^{3}$Net (GRAB:frozen) |  20.77 $\pm$ 0.21 |  32.96 $\pm$ 0.35
$\text{Multi}^{3}$Net (GRAB:not frozen) |  34.08 $\pm$ 0.38 | 55.12 $\pm$ 0.41
$\text{Multi}^{3}$Net (Both: frozen) |  25.13 $\pm$ 0.24 |  38.29 $\pm$ 0.39
$\text{Multi}^{3}$Net (Both:not frozen) |  39.38 $\pm$ 0.37 | 60.23 $\pm$ 0.35
Table 2. Weighted Macro F1-score for MM-Fit dataset Model | Left wrist | Both wrists
---|---|---
DCL (Real) | 90.66 $\pm$ 0.41 | 90.59 $\pm$ 0.53
DCL (Real + Synthetic Vi2IMU) |  90.39 $\pm$ 1.06 |  89.73$\pm$ 0.49
DCL (Real + Synthetic IMUTube) |  89.73 $\pm$ 0.81 |  89.95 $\pm$ 0.68
Base (Real) |  80.86 $\pm$ 0.35 | 90.11 $\pm$ 0.55
Base (Real + Synthetic Vi2IMU) | 89.00 $\pm$ 0.10 |  86.39 $\pm$ 0.15
Base (Real + Synthetic IMUTube) |  87.24 $\pm$ 0.17 |  89.19 $\pm$ 0.92
IMU reconstruction (how2sign:frozen) |  28.76 $\pm$ 0.62 |  35.48 $\pm$ 0.41
IMU reconstruction (how2sign:not frozen) |  80.91 $\pm$ 0.52 |  90.08 $\pm$ 0.33
Contrastive pretrain (how2sign:frozen) |  35.78 $\pm$ 0.47 |  40.01 $\pm$ 0.37
Contrastive pretrain (how2sign:not frozen) |  87.23 $\pm$ 0.59 | 91.85 $\pm$ 0.69
IMU reconstruction (GRAB:frozen) |  28.89 $\pm$ 0.29 |  35.66 $\pm$ 0.51
IMU reconstruction (GRAB:not frozen) |  80.89 $\pm$ 0.48 |  90.17 $\pm$ 0.66
Contrastive pretrain (GRAB:frozen) |  37.18 $\pm$ 0.40 |  44.32 $\pm$ 0.60
Contrastive pretrain (GRAB:not frozen) |  85.03 $\pm$ 0.57 |  90.17 $\pm$ 0.42
$\text{Multi}^{3}$Net (how2sign:frozen) |  37.03 $\pm$ 0.31 |  41.86 $\pm$ 0.55
$\text{Multi}^{3}$Net (how2sign:not frozen) |  89.49 $\pm$ 0.67 | 93.02 $\pm$ 0.71
$\text{Multi}^{3}$Net (GRAB:frozen) |  38.41 $\pm$ 0.38 |  45.93 $\pm$ 0.53
$\text{Multi}^{3}$Net (GRAB:not frozen) |  87.71 $\pm$ 0.46 | 90.98 $\pm$ 0.61
$\text{Multi}^{3}$Net (Both:frozen) |  40.33 $\pm$ 0.49 |  46.57 $\pm$ 0.70
$\text{Multi}^{3}$Net (Both:not frozen) |  88.18 $\pm$ 0.63 | 92.19 $\pm$ 0.68
Figure 3. TSNE Latent representations of the proposed approach for OpenPack
test set(U0201) where each point depicts a data point in the dataset and each
color represents a unique class present in the data.

In this section, we compare the proposed approach with synthetic IMU generated
by different approaches and directly used for HAR. 5 times leave-one-user-out
experiments were conducted with different random seeds.

DCL (Real): Only real IMU data of the target dataset is used for training, the
HAR model is DeepConvLSTM (DCL) (Ordóñez and Roggen, 2016), which is widely
used for IMU-based HAR tasks.

DCL (Real+Synthetic Vi2IMU): Both synthetic and real IMU data from the target
dataset are used for training. The synthetic IMU is generated by Vi2IMU
(Santhalingam et al., 2023), which takes 2D and 3D pose and orientation series
as input, and an LSTM-based model is used to predict the virtual IMU. Note
that as the orientation is not available in the paper, we utilize OSX (Lin et
al., 2023) to output the approximate orientations.

DCL (Real+Synthetic IMUTube): Both synthetic and real IMU data from the target
dataset are used for training. The synthetic IMU is created using IMUTube
(Kwon et al., 2020), starting with extracting 2D skeletal poses from videos
using AlphaPose (Fang et al., 2022), then mapping the 2D poses to 3D using
VideoPose3D (Pavllo et al., 2019), and using IMUSim to generate synthetic IMU
data for specific body joints. Finally the simulated IMU is calibrated using
some real IMU data from the target set to have similar range of variability.

Base (Real), (Real+Synthetic Vi2IMU), and (Real+Synthetic IMUTube): We do the
downstream training without any pretraining. The IMU encoder weights are
initialized randomly. We use real IMU data, real and synthetic IMU data
generated by Vi2IMU and IMUTube, to train the model.

IMU reconstruction (frozen) and (not frozen): Only the IMU reconstruction
model is applied for pretraining. ”Frozen” indicates that the learned weights
of the IMU encoder are frozen, and only the classifier parameters are
optimized. ”Not frozen” means that the IMU encoder is frozen for N epochs
until the loss stops decreasing and reaches the patience P for the first time,
after which it is unfrozen while the classifier is learning.

Contrastive pretrain: Only the multi-modal contrastive model is applied for
pretraining.

Multi3Net: The proposed approach utilizes multi-task pretraining to create a
better joint representation for downstream classification.

Tables 1 and 2 display the HAR performance for the OpenPack and MM-Fit
datasets, respectively. Overall, the proposed approach outperforms the methods
that utilize real IMU or real and synthetic IMU data directly for HAR on both
wrists. Specifically, the proposed method demonstrates an 7.90 % improvement
for OpenPack with both wrists and 2.43 % improvement for MM-Fit with both
wrists. This indicates that useful information can be extracted from extensive
datasets with activities not present in the target dataset, effectively
addressing the lack of data issue. However, the performance of the proposed
approach with the left wrist is poorer than DCL (Real), this may be due to the
fact that information obtained from a single body part using the proposed
method may not be as accurate, whereas obtaining data from multiple body parts
can enhance the HAR performance. Besides, the macro F1-score exhibited poorer
performance in many scenarios when utilizing synthetic IMU generated by
Vi2IMU. This discrepancy may be attributed to errors in calculating the joint
orientation, indicating that the quality of synthetic IMU data significantly
impacts HAR performance for complex activities.

###  4.3. Discussion and Limitations

To investigate the impact of different components on performance, we conduct
experiments with varied settings.

Effect of Pretraining. Pretraining with simulated data in fact helps in
creating better clustering of different latent representations. As we can see
in Figure 3, the combination of pretraining followed by fine-tuning yields the
highest discriminability of latent representations in IMU data. While some
clustering is observable in Figures 3 (2) and (4), these representations
appear less structured compared to Figure 3 (5). In contrast, Figure 3 (1)
illustrates scattered clusters, suggesting that raw IMU data without
pretraining and fine-tuning lacks clear patterns in latent representation.
Even if we are pretraining on a rich dataset that is not of the target it
still improves the overall results. Also, our method, not frozen, consistently
improves on our baseline, which is not always true for other simulation
methods. Additionally based on the results we can clearly see that single-task
pretrainings like Contrastive pretrain and IMU reconstruction are outperformed
by multi-task pretraing used in $\text{Multi}^{3}$Net regardless of the type
of pretraining or downstream dataset. Hence proving our hypothesis multi-task
pretraining is superior.

Effect of Freezing Encoder Weights Based on the results presented in the
tables, the ”not frozen” approach outperforms the ”frozen” approach on both
datasets. This indicates that optimizing the encoders pretrained from a
different data modality (i.e., video) is necessary for IMU-based HAR tasks. As
the pretraining dataset share non standard activity types and does not really
contains both the specific activities present in the target dataset as well as
the calibrated imu signals that falls in same range as target IMU signal it is
expected to have poorer result when the encoder is not learning anything from
the target dataset. Nevertheless this method help us in improving the overall
HAR when we don’t freeze it as it has acquired some knowledge during pretraing
process and when that mixed with knowledge acquired during downstream training
making it better than other methods.

Effect of Real Data Amount.

Figure 4. F1-score on different amount of real IMU used for downstream task
(left wrist at top and both wrists at bottom).

We conduct experiments on OpenPack dataset to investigate how the size of the
training set influences the macro F1-score of our approach. As depicted in
Figure 4, as the amount of real IMU data increases, the macro F1-score of the
proposed approach also increases. However, while the result of utilizing
synthetic IMU data directly with only 25% real IMU data is the highest, the
synthetic IMU data is generated from the video of the target dataset. This is
in contrast to the proposed method, where the activities in the video are
completely different from the target dataset.

Limitations. As shown in the tables, different datasets for pretraining have
an impact on the downstream HAR performance, highlighting the importance of
selecting appropriate datasets for pretraining. Furthermore, it is observed
that the performance on relatively simple activities does not show a
significant increase. This lack of enhancement can likely be attributed to the
fact that the pretraining datasets predominantly consist of non-standard
activity types, which may not effectively generalize to more straightforward
activities. This discrepancy suggests that the pretraining process might not
be adequately capturing the nuances required for these simpler tasks.
Additionally, as illustrated in Figure 1, the simulated IMU data exhibits
notable imperfections, whose severity correlates with the accuracy of the
estimated pose. This dependence underscores the critical role of pose
estimation quality in shaping the fidelity of simulated IMU data.
Consequently, the downstream performance of HAR models may be affected by the
fidelity of the simulated IMU data, necessitating careful consideration and
refinement of pose estimation techniques in conjunction with HAR model
development.

Our model performs comparatively worse than other approaches for single wrist-
based IMU detection. This discrepancy may be due to the data interpretation
during pretraining, which utilized both wrists, whereas downstream training
involved only one wrist. To address this issue, a more comprehensive study and
additional experiments are needed.

##  5\. Conclusion

This paper presents $\text{Multi}^{3}$Net, an extensive framework that
leverages multi-modal contrastive learning to enhance IMU-based HAR
performance using video data (sign language), with activity classes distinct
from the target datasets. The IMU simulation approach is utilized to
effectively extract fine-grained activity features from the video, and the
learned features enhance downstream HAR tasks, particularly in recognizing
complex activities with limited data availability. Experimentation conducted
for fine-tuning across various settings demonstrates that the ”no frozen”
setting consistently outperforms the others, exhibiting an 8 % improvement
compared to baseline methods. In the future, we plan to investigate the impact
of pretraining data selection, the performance on single wrist IMUs, and the
challenge of accurately estimating poses for high-fidelity IMU simulation.

## References

  * (1)
  * Cao et al. (2017) Zhe Cao, Tomas Simon, Shih-En Wei, and Yaser Sheikh. 2017.  Realtime Multi-Person 2D Pose Estimation Using Part Affinity Fields. In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_.
  * Duarte et al. (2021) Amanda Duarte, Shruti Palaskar, Lucas Ventura, Deepti Ghadiyaram, Kenneth DeHaan, Florian Metze, Jordi Torres, and Xavier Giro-i Nieto. 2021.  How2Sign: A Large-scale Multimodal Dataset for Continuous American Sign Language. In _Conference on Computer Vision and Pattern Recognition (CVPR)_.
  * Fang et al. (2022) Hao-Shu Fang, Jiefeng Li, Hongyang Tang, Chao Xu, Haoyi Zhu, Yuliang Xiu, Yong-Lu Li, and Cewu Lu. 2022.  Alphapose: Whole-body regional multi-person pose estimation and tracking in real-time.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ (2022).
  * Inoue et al. (2019) Sozo Inoue, Paula Lago, Tahera Hossain, Tittaya Mairittha, and Nattaya Mairittha. 2019.  Integrating Activity Recognition and Nursing Care Records: The System, Deployment, and a Verification Study.  _Proc. ACM Interact. Mob. Wearable Ubiquitous Technol._ 3, 3, Article 86 (sep 2019), 24 pages.  https://doi.org/10.1145/3351244
  * Jiang et al. (2024) Biao Jiang, Xin Chen, Wen Liu, Jingyi Yu, Gang Yu, and Tao Chen. 2024.  MotionGPT: Human Motion as a Foreign Language.  _Advances in Neural Information Processing Systems_ 36 (2024).
  * Kwon et al. (2020) Hyeokhyen Kwon, Catherine Tong, Harish Haresamudram, Yan Gao, Gregory D. Abowd, Nicholas D. Lane, and Thomas Plötz. 2020.  IMUTube: Automatic Extraction of Virtual on-body Accelerometry from Video for Human Activity Recognition.  _Proc. ACM Interact. Mob. Wearable Ubiquitous Technol._ 4, 3, Article 87 (sep 2020), 29 pages.  https://doi.org/10.1145/3411841
  * Leng et al. (2024) Zikang Leng, Amitrajit Bhattacharjee, Hrudhai Rajasekhar, Lizhe Zhang, Elizabeth Bruda, Hyeokhyen Kwon, and Thomas Plötz. 2024.  IMUGPT 2.0: Language-Based Cross Modality Transfer for Sensor-Based Human Activity Recognition.  _arXiv preprint arXiv:2402.01049_ (2024).
  * Leng et al. (2023a) Zikang Leng, Yash Jain, Hyeokhyen Kwon, and Thomas Ploetz. 2023a.  On the Utility of Virtual On-body Acceleration Data for Fine-grained Human Activity Recognition. In _Proceedings of the 2023 ACM International Symposium on Wearable Computers_ (Cancun, Quintana Roo, Mexico) _(ISWC ’23)_. Association for Computing Machinery, New York, NY, USA, 55–59.  https://doi.org/10.1145/3594738.3611364
  * Leng et al. (2023b) Zikang Leng, Hyeokhyen Kwon, and Thomas Ploetz. 2023b.  Generating Virtual On-Body Accelerometer Data from Virtual Textual Descriptions for Human Activity Recognition. In _Proceedings of the 2023 ACM International Symposium on Wearable Computers_ _(ISWC ’23)_.  https://doi.org/10.1145/3594738.3611361
  * Lin et al. (2023) Jing Lin, Ailing Zeng, Haoqian Wang, Lei Zhang, and Yu Li. 2023.  One-Stage 3D Whole-Body Mesh Recovery with Component Aware Transformer. In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_.
  * Liu et al. (2021) Yilin Liu, Shijia Zhang, and Mahanth Gowda. 2021.  When Video meets Inertial Sensors: Zero-shot Domain Adaptation for Finger Motion Analytics with Inertial Sensors. In _Proceedings of the International Conference on Internet-of-Things Design and Implementation_ (Charlottesvle, VA, USA) _(IoTDI ’21)_. Association for Computing Machinery, New York, NY, USA, 182–194.  https://doi.org/10.1145/3450268.3453537
  * Loper et al. (2023) Matthew Loper, Naureen Mahmood, Javier Romero, Gerard Pons-Moll, and Michael J. Black. 2023.  _SMPL: A Skinned Multi-Person Linear Model_ (1 ed.).  Association for Computing Machinery, New York, NY, USA.
  * Moon et al. (2023) Seungwhan Moon, Andrea Madotto, Zhaojiang Lin, Aparajita Saraf, Amy Bearman, and Babak Damavandi. 2023.  IMU2CLIP: Language-grounded Motion Sensor Translation with Multimodal Contrastive Learning. In _Findings of the Association for Computational Linguistics: EMNLP 2023_ , Houda Bouamor, Juan Pino, and Kalika Bali (Eds.). Association for Computational Linguistics, Singapore, 13246–13253.  https://doi.org/10.18653/v1/2023.findings-emnlp.883
  * Oord et al. (2018) Aaron van den Oord, Yazhe Li, and Oriol Vinyals. 2018.  Representation learning with contrastive predictive coding.  _arXiv preprint arXiv:1807.03748_ (2018).
  * Ordóñez and Roggen (2016) Francisco Javier Ordóñez and Daniel Roggen. 2016.  Deep convolutional and lstm recurrent neural networks for multimodal wearable activity recognition.  _Sensors_ 16, 1 (2016), 115.
  * Pavllo et al. (2019) Dario Pavllo, Christoph Feichtenhofer, David Grangier, and Michael Auli. 2019.  3d human pose estimation in video with temporal convolutions and semi-supervised training. In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_. 7753–7762.
  * Radford et al. (2021) Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, Gretchen Krueger, and Ilya Sutskever. 2021.  Learning Transferable Visual Models From Natural Language Supervision. In _Proceedings of the 38th International Conference on Machine Learning_ _(Proceedings of Machine Learning Research, Vol. 139)_ , Marina Meila and Tong Zhang (Eds.). PMLR, 8748–8763.
  * Ray et al. (2024) Lala Shakti Swarup Ray, Bo Zhou, Sungho Suh, Lars Krupp, Vitor Fortes Rey, and Paul Lukowicz. 2024.  Text me the data: Generating Ground Pressure Sequence from Textual Descriptions for HAR. In _2024 IEEE International Conference on Pervasive Computing and Communications Workshops and other Affiliated Events (PerCom Workshops)_. 461–464.  https://doi.org/10.1109/PerComWorkshops59983.2024.10503379
  * Ray et al. (2023) Lala Shakti Swarup Ray, Bo Zhou, Sungho Suh, and Paul Lukowicz. 2023.  Pressim: An end-to-end framework for dynamic ground pressure profile generation from monocular videos using physics-based 3d simulation. In _2023 IEEE International Conference on Pervasive Computing and Communications Workshops and other Affiliated Events (PerCom Workshops)_.
  * Rey et al. (2019) Vitor Fortes Rey, Peter Hevesi, Onorina Kovalenko, and Paul Lukowicz. 2019.  Let there be IMU data: generating training data for wearable, motion sensor based activity recognition from monocular RGB videos. In _Adjunct Proceedings of the 2019 ACM International Joint Conference on Pervasive and Ubiquitous Computing and Proceedings of the 2019 ACM International Symposium on Wearable Computers_ (London, United Kingdom) _(UbiComp/ISWC ’19 Adjunct)_. Association for Computing Machinery, New York, NY, USA, 699–708.  https://doi.org/10.1145/3341162.3345590
  * Santhalingam et al. (2023) Panneer Selvam Santhalingam, Parth Pathak, Huzefa Rangwala, and Jana Kosecka. 2023.  Synthetic Smartwatch IMU Data Generation from In-the-wild ASL Videos.  _Proc. ACM Interact. Mob. Wearable Ubiquitous Technol._ 7, 2, Article 74 (jun 2023), 34 pages.  https://doi.org/10.1145/3596261
  * Strömbäck et al. (2020) David Strömbäck, Sangxia Huang, and Valentin Radu. 2020.  MM-Fit: Multimodal Deep Learning for Automatic Exercise Logging across Sensing Devices.  4, 4 (2020).  https://doi.org/10.1145/3432701
  * Su et al. (2022) Hongjin Su, Weijia Shi, Jungo Kasai, Yizhong Wang, Yushi Hu, Mari Ostendorf, Wen-tau Yih, Noah A Smith, Luke Zettlemoyer, and Tao Yu. 2022.  One embedder, any task: Instruction-finetuned text embeddings.  _arXiv preprint arXiv:2212.09741_ (2022).
  * Taheri et al. (2020) Omid Taheri, Nima Ghorbani, Michael J. Black, and Dimitrios Tzionas. 2020.  GRAB: A Dataset of Whole-Body Human Grasping of Objects. In _European Conference on Computer Vision (ECCV)_.
  * Xia et al. (2020) Qingxin Xia, Joseph Korpela, Yasuo Namioka, and Takuya Maekawa. 2020.  Robust Unsupervised Factory Activity Recognition with Body-worn Accelerometer Using Temporal Structure of Multiple Sensor Data Motifs.  _Proc. ACM Interact. Mob. Wearable Ubiquitous Technol._ 4, Article 97 (sep 2020), 30 pages.  https://doi.org/10.1145/3411836
  * Yang et al. (2024) Xueyuan Yang, Chao Yao, and Xiaojuan Ban. 2024.  Spatial-Related Sensors Matters: 3D Human Motion Reconstruction Assisted with Textual Semantics.  _Proceedings of the AAAI Conference on Artificial Intelligence_ 38, 9 (Mar. 2024), 10225–10233.  https://doi.org/10.1609/aaai.v38i9.28888
  * Yoshimura et al. (2024) Naoya Yoshimura, Jaime Morales, Takuya Maekawa, and Takahiro Hara. 2024.  OpenPack: A Large-Scale Dataset for Recognizing Packaging Works in IoT-Enabled Logistic Environments. In _2024 IEEE International Conference on Pervasive Computing and Communications (PerCom)_. 90–97.  https://doi.org/10.1109/PerCom59722.2024.10494448
  * Young et al. (2011) A. D. Young, M. J. Ling, and D. K. Arvind. 2011.  IMUSim: A simulation environment for inertial sensing algorithm design and evaluation. In _Proceedings of the 10th ACM/IEEE International Conference on Information Processing in Sensor Networks_. 199–210.
  * Zhang et al. (2023) Jianrong Zhang, Yangsong Zhang, Xiaodong Cun, Shaoli Huang, Yong Zhang, Hongwei Zhao, Hongtao Lu, and Xi Shen. 2023.  T2M-GPT: Generating Human Motion from Textual Descriptions with Discrete Representations. In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_.
  * Zhang et al. (2022) Mingyuan Zhang, Zhongang Cai, Liang Pan, Fangzhou Hong, Xinying Guo, Lei Yang, and Ziwei Liu. 2022.  MotionDiffuse: Text-Driven Human Motion Generation with Diffusion Model.  _arXiv preprint arXiv:2208.15001_ (2022).
  * Zheng et al. (2021) Ce Zheng, Sijie Zhu, Matias Mendieta, Taojiannan Yang, Chen Chen, and Zhengming Ding. 2021.  3D Human Pose Estimation with Spatial and Temporal Transformers.  _Proceedings of the IEEE International Conference on Computer Vision (ICCV)_ (2021).
  * Zhou et al. (2022) Bo Zhou, Sungho Suh, Vitor Fortes Rey, Carlos Andres Velez Altamirano, and Paul Lukowicz. 2022.  Quali-Mat: Evaluating the Quality of Execution in Body-Weight Exercises with a Pressure Sensitive Sports Mat.  _Proc. ACM Interact. Mob. Wearable Ubiquitous Technol._ 6, 2, Article 89 (jul 2022), 45 pages.  https://doi.org/10.1145/3534610


# A note on the network coloring game: A randomized distributed
$(\Delta+1)$-coloring algorithm††thanks: This research was supported by the
Hellenic Foundation for Research and Innovation (H.F.R.I.) under the “1st Call
for H.F.R.I. Research Projects to support Faculty members and Researchers and
the procurement of high-cost research equipment grant” (Project Number: HFRI-
FM17-2436).

Nikolaos Fryganiotis School of Electrical and Computer Engineering, National
Technical University of Athens, Zografou, Greece, 15780, e-mail:
<EMAIL_ADDRESS>Symeon Papavassiliou School of Electrical and
Computer Engineering, National Technical University of Athens, Zografou,
Greece, 15780, e-mail<EMAIL_ADDRESS>Christos Pelekis School of
Electrical and Computer Engineering, National Technical University of Athens,
Zografou, Greece, 15780, e-mail<EMAIL_ADDRESS>
###### Abstract

The network coloring game has been proposed in the literature of social
sciences as a model for conflict-resolution circumstances. The players of the
game are the vertices of a graph with $n$ vertices and maximum degree
$\Delta$. The game is played over rounds, and in each round all players
simultaneously choose a color from a set of available colors. Players have
local information of the graph: they only observe the colors chosen by their
neighbors and do not communicate or cooperate with one another. A player is
happy when she has chosen a color that is different from the colors chosen by
her neighbors, otherwise she is unhappy, and a configuration of colors for
which all players are happy is a proper coloring of the graph. It has been
shown in the literature that, when the players adopt a particular greedy
randomized strategy, the game reaches a proper coloring of the graph within
$O(\log(n))$ rounds, with high probability, provided the number of colors
available to each player is at least $\Delta+2$. In this note we show that a
modification of the aforementioned greedy strategy yields likewise a proper
coloring of the graph, provided the number of colors available to each player
is at least $\Delta+1$, and results in a simple randomized distributed
algorithm for the $(\Delta+1)$-coloring problem.

_Keywords_ : graph coloring; games on graphs; symmetric strategies; greedy
algorithms; distributed algorithms

_MSC (2010)_ : 05C15; 05C57

##  1 Related work and main result

###  1.1 Notation

Throughout the text, given a positive integer $n$, we denote by $[n]$ the set
$\\{1,\ldots,n\\}$ and, given a finite set $F$, we denote by $|F|$ its
cardinality. Given a graph $G=(V,E)$ and a vertex $v\in V$, we denote the
_neighborhood_ of $v$ by $\mathcal{N}(v)=\\{u\in V:(u,v)\in E\\}$. The
cardinality of $\mathcal{N}(v)$ is the _degree_ of $v$. All graphs considered
in this note are finite, without loops, undirected and simple. A _coloring_ of
a graph $G=(V,E)$ is an assignment of colors to the elements of $V$. A
coloring which uses at most $k$ colors is called a _$k$ -coloring_. A
$k$-coloring is _proper_ when no two adjacent vertices receive the same color.

###  1.2 Related work

The problem of determining the smallest possible value of $k$ for which a
graph admits a proper $k$-coloring is classical. It is well known to be NP-
hard, and has attracted an immense attention both from a theoretical as well
as a practical perspective. A particular line of research focuses on games /
algorithms for graph coloring (see, for example, [7, 11, 14] for textbooks
devoting whole chapters to the topic). It is well-known that one can properly
color a graph using $\Delta+1$ colors in linear time via a centralized
algorithm. However the problem becomes more delicate when the algorithm is
required to be distributed, a fact that gives rise to the so-called
distributed coloring problem.

Let $G$ be a graph on $n$ vertices and maximum degree $\Delta$. The
_distributed $k$-coloring problem_ on $G$ is the problem of properly coloring
the vertices of $G$, in a distributed manner, using a given set of $k$
available colors. The problem originates in a rather influential paper of
Linial [12] and has attracted a great deal of attention. The above-mentioned
centralized algorithm implies that at most $\Delta+1$ colors are enough to
properly color $G$, and therefore most of the work on distributed coloring
naturally focuses on the $(\Delta+1)$-coloring problem. The corresponding
literature is vast and is roughly divided in two lines of research: randomized
distributed algorithms and deterministic distributed algorithms. In this
article we shall be concerned with the former setting, and we refer the reader
to [6] for a recent account on the history and state of the art of the latter.

Perhaps the first, simple, randomized distributed algorithm for the
$(\Delta+1)$-coloring problem is due to Luby [13] (see also [1, Section
10.1]), which finds a proper coloring of $G$ within $O(\log(n))$ rounds.
Comparably simple randomized distributed algorithms, with $O(\log(n))$ running
time, for the $(\Delta+1)$-coloring problem have been reported by Collet,
Fraigniaud and Penna [4], Finocchi, Pasconesi and Silvestri [5] and Johansson
[8]. Let us remark that all of the aforementioned algorithms rely on a
standing assumption of the distributed coloring problem which states that the
graph $G$ is at the same time a communication network; an assumption which
allows the vertices to exchange messages over the edges of $G$. In particular,
the randomized algorithms in [4, 5, 8, 13] require that at each round each
vertex knows that status of her neighbours, which means that each vertex
communicates to her neighbours whether she has any conflicts or not. The so-
called Local model allows for adjacent vertices to exchange messages of
arbitrarily large size, while the Congest model allows for adjacent vertices
to exchange messages of $O(\log(n))$ bits per round. Given that there are
several simple $O(\log(n))$-rounds randomized distributed algorithms for the
$(\Delta+1)$-coloring problem, much of the current research focuses on
minimizing the number of rounds until convergence, with the current best
randomized $(\Delta+1)$-coloring algorithm in the Local model being due to
Chang, Li, and Pettie [2], which runs in $O(\log^{3}(\log(n)))$ rounds.

A basic idea in several of the above-mentioned distributed randomized
algorithms is that vertices with conflicts should utilize the set of colors
that are not chosen by their neighbours. A bit more concretely, suppose that
$v$ is a vertex having a conflict after a certain round, say $t$. This means
that there is some other vertex, say $w$, that has chosen the same color as
$v$. Now, for every vertex in $u\in G$ having a conflict, one can associate
the set of “available” colors, say $\mathcal{A}_{t}(u)$, consisting of the
colors that are not chosen by her neighbours after round $t$. Observe that,
when $k\geq\Delta+1$, it holds $|\mathcal{A}_{t}(u)|\geq 1$, for every vertex
$u\in G$ having a conflict. Now, when $k=\Delta+1$, it could happen that
$|\mathcal{A}_{t}(v)|=|\mathcal{A}_{t}(w)|=1$ and
$\mathcal{A}_{t}(v)=\mathcal{A}_{t}(w)$. A worst-case scenario is an instance
for which all vertices in $\mathcal{N}(v)\setminus\\{w\\}$ have no conflict,
and have taken all remaining colors. In such an instance, the vertices $v,w$
have to decide about how to choose their colors in the next round. The “greedy
approach” will result in an infinite loop, and one approach for handling such
instances is to allow cooperation / communication among vertices. To the best
of our knowledge, the first purely game-theoretic distributed randomized
algorithm that requires no communication or cooperation among vertices is due
to Chaudhuri, Chung and Jamall [3]. The main idea behind the algorithm in [3]
is that when $k\geq\Delta+2$, then it holds $|\mathcal{A}_{t}(u)|\geq 2$, for
every vertex $u\in G$ having a conflict, and such a player can choose, in the
next round, a color uniformly at random from the set $\mathcal{A}_{t}(u)$. A
vertex with no conflict just sticks to her choice in all subsequent rounds.
The main result from [3] states that this algorithm converges in $O(\log(n))$
rounds to a proper coloring of the graph. In this article we extend the idea
from [3]. Our observation is that if we include the color chosen by vertex $u$
after round $t$ to the set $\mathcal{A}_{t}(u)$, then vertex $u$ has at least
two available colors to choose from in the next round; a fact that holds true
even in the case $k=\Delta+1$. This allows to resolve potential conflicts
among vertices and results in a distributed randomized algorithm for the
$(\Delta+1)$-coloring problem that requires no exchange of information among
vertices. Our algorithm is stated in terms of a symmetric strategy among
players (i.e., the Frugal strategy defined below) of a particular game played
on a graph, which we now formally define.

###  1.3 A network coloring game: Main result

We shall be concerned with a particular game for graph coloring, which is
referred to as the _network coloring game_. The network coloring game is
introduced and studied empirically in [9] as a model for conflict-resolution
circumstances. The game is played on a graph $G=(V,E)$ with $|V|=n$ vertices
and maximum degree $\Delta$. Each vertex of $G$ is a player, having a set of
$k$ available colors, and participates in a game that is played over a number
of rounds. In each round all players simultaneously choose a color from their
set of available colors, which is assumed to be the set $[k]$. Players have
local information on the graph: they can only observe the colors of their
neighbors, and cannot communicate or cooperate with one another. A player is
_happy_ if she has chosen a color that is different from the colors chosen by
her neighbors. Otherwise, the player is _unhappy_. In game-theoretic language,
the payoff to a player is $1$, if she is happy, and is $0$ if she is unhappy,
and a configuration of colors for which every player receives payoff $1$ is a
_Nash equilibrium_ of the game, in the sense that no player has the incentive
to change strategy under such a configuration.

The problem is to find a symmetric strategy for the players (i.e., a strategy
that is the same for all players) that achieves convergence to a Nash
equilibrium after a finite number of rounds, using the smallest possible value
for $k$. Proving that a particular symmetric strategy is optimal (i.e., it
minimizes the (expected) time to equilibrium) is probably an elusive problem,
and a more realistic line of research is to propose “reasonable” symmetric
strategies and estimate their time to Nash equilibrium.

Such a strategy has been proposed in [3], and will be referred to as the
_Greedy strategy_. In order to formally define the Greedy strategy, let us
introduce some notation. Let $c_{t}(v)$ be the color chosen by player $v$
after round $t$. Notice that a player is unhappy after round $t$ if there
exists $u\in\mathcal{N}(v)$ such that $c_{t}(u)=c_{t}(v)$. Moreover, let
$\mathcal{C}_{t}(v)$ be the set consisting of the colors chosen by the
neighbors of $v$ after round $t$, i.e.,
$\mathcal{C}_{t}(v)=\bigcup_{u\in\mathcal{N}(v)}\\{c_{t}(u)\\}$.

Greedy strategy. Suppose that $k\geq\Delta+2$ and that each player adopts the
following strategy: if a player, say $v$, is happy after a certain round, say
$t$, then she sticks to her color for all subsequent rounds, i.e.,
$c_{s}(v)=c_{t}(v)$ for all $s>t$. If she is unhappy after round $t$, then in
the next round she _changes_ color, and chooses the color $c_{t+1}(v)$
uniformly at random from the set $[k]\setminus\mathcal{C}_{t}(v)$, consisting
of those colors which are not chosen by any of her neighbors after round $t$.

######  Remark 1.

Notice that, when all players in the network coloring game adopt the Greedy
strategy, a happy player remains happy in all subsequent rounds. Notice also
that, since $k\geq\Delta+2$, it holds $|[k]\setminus\mathcal{C}_{t}(v)|\geq 2$
for all $v\in V$ and all rounds $t\geq 1$. In particular, this implies that
for every unhappy player, there are always at least two colors that are not
chosen by her neighbors. Let us also remark that the assumption
$k\geq\Delta+2$ is crucial in the Greedy strategy. Indeed, if $k=\Delta+1$
then the Greedy strategy may result in a game that never reaches a Nash
equilibrium, as can be easily seen by employing the strategy to a triangle-
graph (see also [3, Theorem 2]).

It is shown in [3] that, when all players adopt the Greedy strategy, the
expected number of unhappy players decays exponentially in each round. More
concretely, for every player $v\in V$, let $\tau_{v}$ denote the first round
after which player $v$ becomes happy. Then $\tau=\max_{v}\tau_{v}$ is the
first round after which all players are happy. Notice that at round $\tau$ the
graph is properly $k$-colored and the payoff to every player equals $1$. In
other words, after time $\tau$ the game reaches a Nash equilibrium. The
following statement is the main result in [3].

######  Theorem 1 (Chaudhuri, Chung-Graham, Jamall [3]).

Let $G$ be a graph on $n$ vertices and maximum degree $\Delta$. Suppose that
the number of available colors to each player is $k\geq\Delta+2$ and that each
player in the network coloring game adopts the Greedy strategy. Let $\tau$ be
the first round after which all players are happy. Then, for any starting
assignment of colors to the vertices, it holds

$\mathbb{P}\left(\tau\leq C\cdot\log\left(\frac{n}{\delta}\right)\right)\geq
1-\delta\,,$

where $C=1050e^{9}$ and $\delta>0$ is arbitrarily small.

In other words, when the players in the network coloring game adopt the Greedy
strategy, the game converges to a Nash equilibrium in
$O\left(\log\left(\frac{n}{\delta}\right)\right)$ rounds with probability at
least $1-\delta$. Improved estimates on the expected value of $\tau$ can be
found in [15, Theorem 3]. In this note we combine some ideas from the
approaches in [3] and [15] and deduce a refinement of Theorem 1. A bit more
concretely, we show that a modification of the above-mentioned Greedy strategy
allows to deduce the same conclusion as in Theorem 1, subject to the
assumption that the number of colors available to each player is at least
$\Delta+1$. We refer to this modified Greedy strategy as a _Frugal strategy_ ,
which is formally defined as follows.

Frugal strategy. Suppose that $k\geq\Delta+1$ and that each player in the
network coloring game first chooses, independently of all other choices, a
color uniformly at random from the set $[k]$, and then adopts the following
strategy: if a player, say $v$, is happy after round $t\geq 1$, then she
sticks to her color for all subsequent rounds, i.e., $c_{s}(v)=c_{t}(v)$ for
all $s>t$. If she is unhappy after round $t$, then in the next round she
chooses uniformly at random a color from the set
$\\{c_{t}(v)\\}\cup([k]\setminus\mathcal{C}_{t}(v))$.

In other words, under the Frugal strategy, a player who is unhappy after round
$t\geq 1$ chooses in the next round a color uniformly at random from the set
consisting of her color-choice after round $t$ and the set of colors that are
not chosen by her neighbors after round $t$.

######  Remark 2.

Notice that, since $k\geq\Delta+1$, it holds
$|\\{c_{t}(v)\\}\cup([k]\setminus\mathcal{C}_{t}(v))|\geq 2$ for all $v\in V$
and all rounds $t\geq 1$. In particular, every unhappy player has at least two
colors to choose from in the next round. Notice also that, in contrast to the
Greedy strategy, under the Frugal strategy an unhappy player may not change
color in the next round.

In this note we imitate the analysis of the proof of Theorem 1, from [3], and
show that the Frugal strategy converges to a Nash equilibrium in a finite
number of rounds. More precisely, we obtain the following refinement of
Theorem 1. Recall (see [17]) that a random variable $X$ is _stochastically
smaller_ than a random variable $Y$, denoted $X\leq_{st}Y$, if it holds
$\mathbb{P}(X>t)\leq\mathbb{P}(Y>t)$, for all $t$.

######  Theorem 2.

Let $G$ be a graph on $n$ vertices and maximum degree $\Delta$. Suppose that
the number of available colors to each player is $k\geq\Delta+1$ and that each
player in the network coloring game adopts the Frugal strategy. Let $\tau$ be
the first round after which all players are happy. Then $\tau$ is
stochastically smaller than a random variable $T$ such that

$\mathbb{E}(T)\leq\frac{2}{\mu}(1+\log(n))\quad\text{ and
}\quad\text{Var}(T)\leq\frac{4n}{\mu^{2}}\,,$

where $\mu=-\log\left(1-\frac{1}{2^{6}e^{5}}\right)\approx 0.000105$.

We prove Theorem 2 in the next section. The proof mimics the proof of Theorem
1, from [3], and proceeds in two steps. The first step concerns a lower
estimate on the probability that a player, who is unhappy after a certain
round, say $t$, has “enough” available colors after round $t+1$. The second
step concerns a lower estimate on the probability that the player becomes
happy after round $t+2$, given that she has “enough” available colors after
round $t+1$. Both estimates do not depend on $\Delta$ and, when combined,
yield a lower bound on the probability that an unhappy player becomes happy
after two rounds, which is also independent of $\Delta$. Let us remark that
the analysis over two rounds is crucial; over a single round it could happen
that an unhappy player becomes happy in the next round with probability
$\frac{1}{2^{\Delta}}$, an estimate which clearly depends on $\Delta$. The
proof of Theorem 2 is completed using ideas from the theory of maximally
dependent random variables.

##  2 Proof of main result

In this section we prove Theorem 2. We assume that each player in the network
coloring game adopts the Frugal strategy. We begin with a lower estimate on
the probability that a player, who is unhappy after a certain round, receives
“enough” available colors in the next round. In order to be more precise, we
need some extra piece of notation that will remain fixed throughout this
section.

Recall that $c_{t}(v)$ is the color chosen by player $v$ after round $t$ and
that $\mathcal{C}_{t}(v)$ is the set of colors chosen by its neighbors. For
every $t\geq 1$, let $H_{t}$ denote the set of happy players after round $t$,
and set $U_{t}=V\setminus H_{t}$ be the set of unhappy players after round
$t$. Given $v\in U_{t}$, let

$\mathcal{A}_{t}(v)=\\{c_{t}(v)\\}\cup([k]\setminus\mathcal{C}_{t}(v))$

be the set of colors _available_ to $v$ after round $t$; hence in the next
round player $v$ chooses the color $c_{t+1}(v)$ uniformly at random from the
set $\mathcal{A}_{t}(v)$. Let also $p_{t}(v)=\frac{1}{|\mathcal{A}_{t}(v)|}$
denote the probability with which the unhappy player $v$ chooses her color in
the next round. For $v\in H_{t}$, set $\mathcal{A}_{t}(v)=\\{c_{t}(v)\\}$ and
$p_{t}(v)=1$. Similarly, given a vertex $v\in V$, let $H_{t}(v)$ denote the
set of happy neighbors of $v$ after round $t$, and let

$F_{t}(v)=\bigcup_{u\in H_{t}(v)}\\{c_{t}(u)\\}$

be the set of colors chosen by the happy neighbors of $v$ after round $t$, and
$U_{t}(v)=\mathcal{N}(v)\setminus H_{t}(v)$ be the set of unhappy neighbors of
$v$. Notice that every color in the set $[k]\setminus F_{t}(v)$ has a non-zero
chance of not being chosen by any unhappy neighbour of $v$, and so has a non-
zero chance of belonging to the set $\mathcal{A}_{t+1}(v)$. Finally, let
$f_{t}(v)=|F_{t}(v)|$, and notice that, since happy players stick to their
choice, the sequence $\\{f_{t}(v)\\}_{t\geq 1}$ is non-decreasing. Thus the
number of colors available to $v$ after round $t+1$ as well as after round
$t+2$ is at most $k-f_{t}(v)$. We now establish a lower bound on the
probability that the number of colors available to player $v\in U_{t}$ after
round $t+1$ is at least $\frac{k-f_{t}(v)}{5}$.

######  Lemma 1.

For each $t\geq 1$ and each $v\in U_{t}$, it holds

$\mathbb{P}\left(|\mathcal{A}_{t+1}(v)|\geq\frac{k-f_{t}(v)}{5}\right)\geq\frac{1}{2^{4}}\,.$

###### Proof.

To simplify notation, let $f:=f_{t}(v)$. We first estimate
$\mathbb{E}(|\mathcal{A}_{t+1}(v)|)$ from below; the result then will follow
from Markov’s inequality. Recall that every color from the set $[k]\setminus
F_{t}(v)$ has a positive chance of being an element of $\mathcal{A}_{t+1}(v)$.
The probability that a fixed color $i\in[k]\setminus F_{t}(v)$ is not chosen
by any $u\in U_{t}(v)$ in the next round is equal to

$\prod_{\\{u\in U_{t}(v):i\in\mathcal{A}_{t}(u)\\}}(1-p_{t}(u))\,.$

Therefore, using the arithmetic-geometric means inequality, we have

$\displaystyle\mathbb{E}(|\mathcal{A}_{t+1}(v)|)$ $\displaystyle\geq$
$\displaystyle\sum_{i\in[k]\setminus F_{t}(v)}\,\prod_{\\{u\in
U_{t}(v):i\in\mathcal{A}_{t}(u)\\}}(1-p_{t}(u))$ $\displaystyle\geq$
$\displaystyle(k-f)\cdot\left(\prod_{i\in[k]\setminus F_{t}(v)}\prod_{\\{u\in
U_{t}(v):i\in\mathcal{A}_{t}(u)\\}}(1-p_{t}(u))\right)^{\frac{1}{k-f}}$
$\displaystyle\geq$ $\displaystyle(k-f)\cdot\left(\prod_{u\in
U_{t}(v)}\,\prod_{i\in\mathcal{A}_{t}(u)}(1-p_{t}(u))\right)^{\frac{1}{k-f}}$
$\displaystyle=$ $\displaystyle(k-f)\cdot\left(\prod_{u\in
U_{t}(v)}\,\,\left(1-\frac{1}{|\mathcal{A}_{t}(u)|}\right)^{|\mathcal{A}_{t}(u)|}\right)^{\frac{1}{k-f}}\,.$

Now notice that for every $u\in U_{t}(v)$ it holds $|\mathcal{A}_{t}(u)|\geq
2$; hence $1-\frac{1}{|\mathcal{A}_{t}(u)|}>0$. Since the sequence
$\\{(1-1/m)^{m}\\}_{m\geq 2}$ is non-decreasing and $|\mathcal{A}_{t}(u)|\geq
2$, it follows that
$\left(1-\frac{1}{|\mathcal{A}_{t}(u)|}\right)^{|\mathcal{A}_{t}(u)|}\geq\left(1-\frac{1}{2}\right)^{2}=\frac{1}{4}$.
Putting the above together, we conclude

$\mathbb{E}(|\mathcal{A}_{t+1}(v)|)\geq(k-f)\cdot\left(\frac{1}{4}\right)^{\frac{|U_{t}(v)|}{k-f}}\,.$

Now, since $k\geq\Delta+1$, it holds $|U_{t}(v)|\leq\Delta-f\leq k-1-f$, and
thus $\frac{|U_{t}(v)|}{k-f}\leq 1$. This implies that
$\left(\frac{1}{4}\right)^{\frac{|U_{t}(v)|}{k-f}}\geq\frac{1}{4}$ and
therefore

$\mathbb{E}(|\mathcal{A}_{t+1}(v)|)\geq\frac{k-f}{4}\,.$

To complete the proof, let $X=k-f-|\mathcal{A}_{t+1}(v)|$ and apply the lower
estimate on $\mathbb{E}(|\mathcal{A}_{t+1}(v)|)$, together with Markov’s
inequality, to deduce
$\mathbb{P}\left(|\mathcal{A}_{t+1}(v)|<\frac{k-f}{5}\right)=\mathbb{P}\left(X>\frac{4(k-f)}{5}\right)<\frac{5\cdot\mathbb{E}(X)}{4(k-f)}\leq\frac{15}{16}$,
as desired. ∎

In the next lemma we estimate from below the probability that a player, who is
unhappy after round $t$, becomes happy after two rounds. This will require
some additional notation.

Fix a player $v\in U_{t+1}$. Since $v$ is unhappy, it follows that there
exists $u\in\mathcal{N}(v)$ such that $c_{t+1}(u)=c_{t+1}(v)$. There are two
kinds of unhappy neighbors of $v$ participating in the game. Those that have
the same color as player $v$, and those that have different color. This
partitions the set $U_{t+1}(v)$ into the sets

$S_{t+1}(v)=\\{u\in U_{t+1}(v):c_{t+1}(u)=c_{t+1}(v)\\}\quad\text{ and }\quad
D_{t+1}(v)=\\{u\in U_{t+1}(v):c_{t+1}(u)\neq c_{t+1}(v)\\}\,.$

Observe that for every $u\in S_{t+1}(v)$ it holds
$c_{t+1}(v)\in\mathcal{A}_{t+1}(u)$, while for every $u\in D_{t+1}(v)$ it
holds $c_{t+1}(v)\notin\mathcal{A}_{t+1}(u)$. Moreover, since
$c_{t+1}(u)\in\mathcal{A}_{t+1}(u)$, it follows that for every $u\in
D_{t+1}(v)$ the set $\mathcal{A}_{t+1}(u)$ contains a color, namely, color
$c_{t+1}(u)$, that is _not_ contained in $\mathcal{A}_{t+1}(v)$.

######  Lemma 2.

It holds

$\mathbb{P}(v\in H_{t+2}\,|\,v\in U_{t})\geq\frac{1}{2^{6}e^{5}}\,.$

###### Proof.

Let $v\in U_{t}$. Then, conditional on $\mathcal{A}_{t+1}(v)$ and $v\in
U_{t+1}$, the probability that player $v$ is happy after round $t+2$ is the
average of the probabilities that a fixed color from $\mathcal{A}_{t+1}(v)$ is
not chosen by any unhappy neighbor $u\in U_{t+1}(v)$. To simplify notation,
let us define, for each color $i\in[k]$, the sets

$S_{t+1}^{(i)}:=\\{u\in S_{t+1}(v)\,:\,i\in\mathcal{A}_{t+1}(u)\\}\quad\text{
and }\quad D_{t+1}^{(i)}:=\\{u\in
D_{t+1}(v)\,:\,i\in\mathcal{A}_{t+1}(u)\\}\,.$

For $i\in\mathcal{A}_{t+1}(v)$ and $u\in U_{t+1}(v)$, let
$q(i;u):=\mathbb{P}(c_{t+2}(u)\neq i)$ be the probability that player $u$ does
not choose color $i$ in the next round. Then the probability that a fixed
color $i\in\mathcal{A}_{t+1}(v)$ is not chosen by any player $u\in U_{t+1}(v)$
in the next round is equal to

$\prod_{u\in S_{t+1}^{(i)}}q(i;u)\,\prod_{u\in D_{t+1}^{(i)}}q(i;u)\,.$

Hence, conditional on $\mathcal{A}_{t+1}(v)$ and $v\in U_{t+1}$, the
probability that player $v$ is happy after round $t+2$ equals

$\displaystyle\pi_{t+2}$ $\displaystyle:=$
$\displaystyle\frac{1}{|\mathcal{A}_{t+1}(v)|}\,\sum_{i\in\mathcal{A}_{t+1}(v)}\,\prod_{u\in
S_{t+1}^{(i)}}q(i;u)\prod_{u\in D_{t+1}^{(i)}}q(i;u)$ $\displaystyle\geq$
$\displaystyle\left(\prod_{i\in\mathcal{A}_{t+1}(v)}\,\,\prod_{u\in
S_{t+1}^{(i)}}q(i;u)\prod_{u\in
D_{t+1}^{(i)}}q(i;u)\right)^{1/|\mathcal{A}_{t+1}(v)|}$ $\displaystyle=$
$\displaystyle\left(\prod_{i\in\mathcal{A}_{t+1}(v)}\,\,\prod_{u\in
S_{t+1}^{(i)}}q(i;u)\right)^{1/|\mathcal{A}_{t+1}(v)|}\left(\prod_{i\in\mathcal{A}_{t+1}(v)}\,\,\prod_{u\in
D_{t+1}^{(i)}}q(i;u)\right)^{1/|\mathcal{A}_{t+1}(v)|}$

where the estimate follows from the arithmetic-geometric means inequality. Now
observe that $c_{t+1}(v)\in\mathcal{A}_{t+1}(v)$, and therefore it holds
$q(c_{t+1}(v);u)=1$, for $u\in D_{t+1}(v)$. Moreover, for each $u\in
D_{t+1}(v)$, the set $\mathcal{A}_{t+1}(u)$ contains at least one color
(namely, $c_{t+1}(u)$) that does not belong to $\mathcal{A}_{t+1}(v)$. The
last two observations imply that

$\displaystyle\prod_{i\in\mathcal{A}_{t+1}(v)}\,\,\prod_{u\in
D_{t+1}^{(i)}}q(i;u)$ $\displaystyle=$
$\displaystyle\prod_{i\in\mathcal{A}_{t+1}(v)\setminus\\{c_{t+1}(v)\\}}\,\,\prod_{u\in
D_{t+1}^{(i)}}q(i;u)$ $\displaystyle\geq$ $\displaystyle\prod_{u\in
D_{t+1}(v)}\,\,\prod_{i\in\mathcal{A}_{t+1}(u)\setminus\\{c_{t+1}(u)\\}}\left(1-\frac{1}{|\mathcal{A}_{t+1}(u)|}\right)$
$\displaystyle=$ $\displaystyle\prod_{u\in
D_{t+1}(v)}\,\left(1-\frac{1}{|\mathcal{A}_{t+1}(u)|}\right)^{|\mathcal{A}_{t+1}(u)|-1}$
$\displaystyle\geq$ $\displaystyle\left(\frac{1}{e}\right)^{|D_{t+1}(v)|}\,,$

where the last estimate follows from the fact that
$\left(1-\frac{1}{m}\right)^{m-1}\geq\frac{1}{e}$, when $m\geq 2$. Similarly,
we have

$\displaystyle\prod_{i\in\mathcal{A}_{t+1}(v)}\,\,\prod_{u\in
S_{t+1}^{(i)}}q(i;u)$ $\displaystyle\geq$ $\displaystyle\prod_{u\in
S_{t+1}(v)}\,\prod_{i\in\mathcal{A}_{t+1}(u)}\left(1-\frac{1}{|\mathcal{A}_{t+1}(u)|}\right)$
$\displaystyle=$ $\displaystyle\prod_{u\in
S_{t+1}(v)}\left(1-\frac{1}{|\mathcal{A}_{t+1}(u)|}\right)^{|\mathcal{A}_{t+1}(u)|}$
$\displaystyle\geq$ $\displaystyle\left(\frac{1}{4}\right)^{|S_{t+1}(v)|}\,.$

Putting the above together, we conclude that

$\pi_{t+2}\geq\left(\frac{1}{4}\right)^{\frac{|S_{t+1}(v)|}{|\mathcal{A}_{t+1}(v)|}}\cdot\left(\frac{1}{e}\right)^{\frac{|D_{t+1}(v)|}{|\mathcal{A}_{t+1}(v)|}}\,.$

From Lemma 1 we know that with probability at least $1/2^{4}$ it holds
$|\mathcal{A}_{t+1}(v)|\geq\frac{k-f_{t}(v)}{5}\geq\frac{k-|H_{t}(v)|}{5}\geq\frac{k-|H_{t+1}(v)|}{5}$.
Furthermore, observe that $|D_{t+1}(v)|\geq
k-|H_{t+1}(v)|-|\mathcal{A}_{t+1}(v)|$. Since

$|S_{t+1}(v)|+|D_{t+1}(v)|=|U_{t+1}(v)|\leq\Delta-|H_{t+1}(v)|\leq
k-1-|H_{t+1}(v)|\leq k-|H_{t+1}(v)|\,,$

it follows that $|S_{t+1}|\leq|\mathcal{A}_{t+1}(v)|$; hence
$\pi_{t+2}\geq\frac{1}{4}\cdot\left(\frac{1}{e}\right)^{\frac{|D_{t+1}(v)|}{|\mathcal{A}_{t+1}(v)|}}$.
Since it clearly holds $|D_{t+1}(v)|\leq k-|H_{t+1}(v)|$ we conclude that,
conditional on the event that
$|\mathcal{A}_{t+1}(v)|\geq\frac{k-|H_{t+1}(v)|}{5}$, it holds
$\pi_{t+2}\geq\frac{1}{4e^{5}}$. The result follows. ∎

We now turn into the proof of our main result. Given $v\in V$, let $\tau_{v}$
be the first round after which player $v$ is happy and set
$\tau=\max_{v}\tau_{v}$. We want to upper bound the expected value of $\tau$.
Notice that the random variables $\tau_{v},v\in V$, are _not_ mutually
independent and our bound on $\tau$ will be a worst-case estimate. To this
end, we follow [15] and employ ideas from the theory of maximally dependent
random variables. Given a real number $\mu>0$, let $E_{\mu}$ denote an
exponential random variable of parameter $\mu$.

######  Lemma 3.

For every $v\in V$, it holds $\tau_{v}\leq_{st}2\cdot E_{\mu}$, where
$\mu=-\log\left(1-\frac{1}{2^{6}e^{5}}\right)$.

###### Proof.

We have to show that
$\mathbb{P}(\tau_{v}>t)\leq\mathbb{P}(E_{\mu}>\frac{t}{2})$, for all $t$.
Notice that

$\mathbb{P}(\tau_{v}>1)=1-\left(1-\frac{1}{k}\right)^{|\mathcal{N}(v)|}\leq
1-\left(1-\frac{1}{k}\right)^{k-1}\leq 1-\frac{1}{e}\leq
1-\frac{1}{2^{6}e^{5}}\,.$

From Lemma 2 we know that
$\mathbb{P}(\tau_{v}>t+2\,|\,\tau_{v}>t)=\mathbb{P}(v\in U_{t+2}\,|\,v\in
U_{t})\leq 1-\frac{1}{2^{6}e^{5}}$ holds true for every $t\geq 1$. Now notice
that when $t$ is odd, say $t=2m+1$, it holds

$\displaystyle\mathbb{P}(\tau_{v}>t)$ $\displaystyle=$
$\displaystyle\mathbb{P}(\tau_{v}>1)\cdot\prod_{i=1}^{m}\mathbb{P}(\tau_{v}>2i+1\,|\,\tau_{v}>2i-1)$
$\displaystyle\leq$ $\displaystyle\left(1-\frac{1}{2^{6}e^{5}}\right)^{m+1}$
$\displaystyle\leq$ $\displaystyle\left(1-\frac{1}{2^{6}e^{5}}\right)^{t/2}$
$\displaystyle=$ $\displaystyle\mathbb{P}\left(E_{\mu}>\frac{t}{2}\right)\,.$

If $t$ is even, the proof is similar, and the result follows. ∎

Now let $\tau$ be the first round after which all players are happy. Then
$\tau=\max_{v}\tau_{v}$. The proof of our main result is almost complete.
Given two random variables $X,Y$, let $X\sim Y$ denote that fact that they
have the same distribution.

###### Proof of Theorem 2.

Lemma 3 implies that, for all $v\in V$, it holds $\tau_{v}\leq_{st}Y_{v}$,
where $Y_{v}\sim 2\cdot E_{\mu}$. Since $\tau_{v}\leq_{st}Y_{v}$ it follows
(see [17, Theorem 1.A.1]) that there exist random variables
$\hat{\tau}_{v},\hat{Y}_{v}$ such that $\hat{\tau}_{v}\sim\tau_{v}$,
$\hat{Y}_{v}\sim Y_{v}$ and $\hat{\tau}_{v}\leq\hat{Y}_{v}$ with probability
$1$. Hence $\max_{v}\hat{\tau}_{v}\leq\max_{v}\hat{Y}_{v}$ with probability
$1$. Since $\tau\sim\max_{v}\hat{\tau}_{v}$, we conclude that
$\tau\leq_{st}2\cdot M$, where $M$ is the maximum of $n$ exponential random
variables, say $\\{X_{v}\\}_{v\in V}$, of parameter $\mu$. Hence
$\mathbb{E}(\tau)\leq 2\cdot\mathbb{E}(M)$ and it is therefore enough to
establish an upper bound on $\mathbb{E}(M)$. To this end, we borrow ideas from
[10]. Note that for every real number $a$ we have $M\leq
a+\sum_{v}\max\\{X_{v}-a,0\\}$; hence

$\mathbb{E}(M)\leq
a+\sum_{v}\mathbb{E}(\max\\{X_{v}-a,0\\})=a+n\int_{a}^{\infty}(1-F(x))\,dx\,,$

where $F(\cdot)$ is the distribution function of $X_{v}\sim E_{\mu}$. Let
$h(a)=a+n\int_{a}^{\infty}(1-F(x))\,dx$, defined for real $a$, and notice that
$h(\cdot)$ attains its minimum at $a_{n}:=F^{-1}(1-\frac{1}{n})$. Since
$F(x)=1-e^{\mu x}$, we deduce that

$\mathbb{E}(M)\leq a_{n}+n\int_{a_{n}}^{\infty}e^{-\mu
x}dx=\frac{1}{\mu}(1+\log(n))\,,$

as desired. Finally, the main result from [16] implies that $\text{Var}(M)\leq
n\cdot\text{Var}(E_{\mu})=\frac{n}{\mu^{2}}$. The result follows upon letting
$T\sim 2\cdot M$. ∎

## References

  * [1] L. Barenboim, M. Elkin, Distributed graph coloring: Fundamentals and recent developments, Synthesis Lectures on Distributed Computing Theory 4(1), pp.1–171, 2013.
  * [2] Y. J. Chang, W. Li, S. Pettie, An optimal distributed $(\Delta+1)$–coloring algorithm?, In Proceedings of the ACM Symposium on Theory of Computing (STOC), pages 445–456, 2018.
  * [3] K. Chaudhuri, F. Chung-Graham, M.S. Jamall, A network coloring game, International Workshop on Internet and Network Economics. Springer, Berlin, Heidelberg, 2008.
  * [4] S. Collet, P. Fraigniaud, P. Penna, Equilibria of Games in Networks for Local Tasks, OPODIS 2018 - 22nd International Conference on Principles of Distributed Systems, Dec 2018, HongKong, China.
  * [5] I. Finocchi, A. Panconesi, R. Silvestri, Experimental analysis of simple, distributed vertex coloring algorithms, In SODA, pages 606–615, 2002.
  * [6] M. M. Halldórsson, F. Kuhn, A. Nolin, T. Tonoyan, Near-Optimal Distributed Degree+1 Coloring, preprint, arXiv:2112.00604 [cs.DC].
  * [7] T.R. Jensen, B. Toft, Graph coloring problems, Vol. 39. John Wiley & Sons, 2011.
  * [8] Ö.-Johansson, Simple distributed $(\Delta+1)$-coloring of graphs, Information Processing Letters 70(5) (1999) 229–232.
  * [9] M. Kearns, S. Suri, N. Montfort, An Experimental Study of the Coloring Problem on Human Subject Networks, Science 313 (5788) (2006) 824–827.
  * [10] T.L. Lai, H. Robbins, Maximally Dependent Random Variables, Proceedings of the National Academy of Sciences of the United States of America 73(2) (1976) 286–288.
  * [11] R. Lewis, A guide to graph colouring: Algorithms and Applications, Vol. 7. Berlin: Springer, 2015.
  * [12] N. Linial, Locality in distributed graph algorithms, SIAM Journal on Computing 21(1) (1992) 193–201.
  * [13] M. Luby, A simple parallel algorithm for the maximal independent set problem, SIAM Journal on Computing 15 (1986) 1036–1053.
  * [14] Molloy, M. Molloy, B. Reed, Graph colouring and the probabilistic method, Vol. 23, Springer Science & Business Media, 2002.
  * [15] C. Pelekis, M. Schauer, Network coloring and colored coin games, Search Theory, Springer, New York, NY, 2013, p. 59–73.
  * [16] T. Rychlik, Extreme variances of order statistics in dependent samples, Statistics & Probability Letters 78 (2008) 1577–1582.
  * [17] M. Shaked, J.G. Shanthikumar, Stochastic Orders and their Applications, Springer, New York (2007).