# JECL: Joint Embedding and Cluster
Learning for Image-Text Pairs

Sean T. Yang  University of Washington
<EMAIL_ADDRESS>Kuan-Hao Huang  University of California, Los Angeles
<EMAIL_ADDRESS>Bill Howe  University of Washington
<EMAIL_ADDRESS>
###### Abstract

We propose JECL, a method for clustering image-caption pairs by training
parallel encoders with regularized clustering and alignment objectives,
simultaneously learning both representations and cluster assignments. These
image-caption pairs arise frequently in high-value applications where
structured training data is expensive to produce, but free-text descriptions
are common. JECL trains by minimizing the Kullback-Leibler divergence between
the distribution of the images and text to that of a combined joint target
distribution and optimizing the Jensen-Shannon divergence between the soft
cluster assignments of the images and text. Regularizers are also applied to
JECL to prevent trivial solutions. Experiments show that JECL outperforms both
single-view and multi-view methods on large benchmark image-caption datasets,
and is remarkably robust to missing captions and varying data sizes.

##  I Introduction

We consider multi-modal unsupervised learning for image-text pairs. In many
science and engineering applications, images are equipped with free-text
descriptions, but structured training labels are difficult to acquire. For
example, the figures in the scientific literature are an important source of
information [1], but training labels require specialized knowledge and may
evolve frequently. These figures are, however, equipped with a caption
describing the content or purpose of the figure, and these captions can be
used as a source of (noisy) supervision. Other examples include medical
imagery (paired with unstructured physician’s notes), art (paired with the
artist’s or curator’s description), or archaeological artifacts (paired with
researcher’s notes).

A simple approach is to ignore the text and cluster the images alone.
Unsupervised image clustering has received significant research attention in
computer vision [2]. However, as we will show, these single-view approaches
fail to differentiate semantically different but visually similar subjects on
benchmark datasets. On the other hand, using the captions alone (ignoring the
image) is rarely considered viable, since captions do not fully describe the
content of the image. Current multi-modal image-text models focus on matching
images and corresponding captions for information retrieval tasks [3, 4]
rather than unsupervised learning for image-text pairs. Jin et al. [5]
characterize correlations between image and text using Canonical Correlation
Analysis (CCA). However, the textual information for the model comprised semi-
structured tags rather than unstructured free-text descriptions. Free-text
descriptions can capture more information to improve a model’s performance,
but unstructured text is often considered prohibitively noisy in practice: it
can contain irrelevant or inconsistent information, and may even be associated
with the wrong image. We find that these challenges have limited the uptake of
machine learning in complex, human-intensive domains in science and the
humanities.

We propose JECL, a clustering algorithm for image-text pairs that considers
both visual features and text features, learning both a vector representation
for the pair as well as a clustering. JECL extends prior work on Deep Embedded
Clustering (DEC) [2]. DEC learns a mapping function from the data space to a
lower-dimensional feature space and produces soft cluster assignments in which
it iteratively optimizes Kullback-Leibler (KL) divergence between soft
assignments and computed target distributions. DEC has shown success on
clustering several benchmark datasets including both images and text
(separately). Despite its utility, we find DEC may often generate empty
clusters or singleton clusters containing an obvious outlier, a common problem
in clustering tasks [6].

JECL learns cluster assignments by iteratively optimizing a clustering
objective while learning to align a text distribution $\mathbf{r}$ and an
image distribution $\mathbf{q}$. We address the problem of empty and singleton
clusters by introducing regularization terms to force the model to find a
solution with a more balanced assignment for each track. We design a target
distribution $\mathbf{p}$, such that the model learns by minimizing the KL
divergence between $\mathbf{q}$ and $\mathbf{p}$, the KL divergence between
$\mathbf{r}$ and $\mathbf{p}$, and the Jensen-Shannon Divergence between
$\mathbf{r}$ and $\mathbf{q}$, penalizing the model when these distributions
become dissimilar. The final cluster assignments are derived via softmax over
the joint distribution (Figure 1). These combined objectives help JECL define
clear boundaries between clusters in the embedding space while retaining
semantically meaningful results. In contrast, DEC can fail to differentiate
between visually similar but semantically distinct examples, as we will show.

We make the following contributions:

  * •

We propose JECL, a model that simultaneously learns feature representations
and cluster assignments for multi-view data (typically image-text pairs) by
penalizing divergence from a shared joint distribution and rewarding coherence
across views.

  * •

We evaluate JECL on four datasets and compare with multiple single-view and
multi-view algorithms, finding that JECL achieves better performance on
multiple metrics for all but the smallest dataset due to little data for each
cluster.

  * •

We show that JECL’s performance is robust across many settings, including
those with missing text, semantically and visually ambiguous images, sub-
optimal hyperparameter settings, and varying data sizes.

##  II Related Work

We consider related work in both image-text representation learning and multi-
view clustering methods.

#### Multi-View Image-Text Representation

DeVise [7] generates visual-semantic embeddings by linearly transforming a
visual embedding from a pre-trained deep neural network into the embedding
space of the text representation. After DeVise, several visual semantic models
have been developed by optimizing bi-directional pairwise ranking loss [8, 9]
and maximum mean discrepancy loss [10]. Maximizing CCA (Canonical Correlation
Analysis) [11] is also a common way to acquire cross-modal representation. Yan
et al. [12] address the problem of matching images and text in a joint latent
space learned with deep canonical correlation analysis. Dorfer et al. [4]
develop a canonical correlation analysis layer and then apply pairwise ranking
loss to learn a common representation of image and text for information
retrieval tasks. However, most image-text multi-modal studies focus on
matching image and text. Few methods study the problem of unsupervised
clustering of image-text pairs.

Jin et al. considered clustering images by integrating the multimodal feature
generation with a Locality Linear Coding (LLC) and co-occurrence association
network, multimodal feature fusion with CCA, and accelerated hierarchical
k-means clustering [5]. However, the text data they handled are tags instead
of the long, noisy, and unreliable free-text descriptions we are interested
in. Grechkin et al. proposed EZLearn [13], a co-training framework which takes
image-text data and an ontology to classify images using labels from the
ontology. This model requires prior knowledge of the data in order to derive
an ontology. This prior knowledge is not always available, and can
significantly bias the results toward the clusters implied by the ontology.

#### Multi-View Clustering

JECL can be considered as a form of multi-view clustering, except that multi-
view methods often only consider only one data type, typically multiple images
of the same object. Matrix factorization is a common approach to address
multi-view clustering problem. Liu et al. [14] used a joint matrix
factorization with restraints to progressively find the consensus between
different views. Zhao et al. [15] developed a deep matrix factorization
framework which imposes the non-negative representation of all views to be the
same in final layer to maximize the mutual information and is graph
regularized to preserve the local geometric structure in each view. BMVC,
binary multi-view clustering, is presented by Zhang et al [16] to easily scale
to large data by collective encoding views into a compact common binary code
space and simultaneously clustering the collaborative binary representations
using a matrix factorization model. Spectral clustering has shown significant
performance in single view tasks and it also has been explored in multi-view
scenario. Brbić et al. [17] proposes a multi-view spectral clsutering
framework that encourages sparsity and low-rank solution and balances the
agreement across views. However, most spectral clustering methods are not
scalable due to its quadratic complexity.

JECL is also robust to incomplete multi-view tasks, which have received
increasing attention in recent years. DAIMC [18] is a method built on weighted
semi-nonnegative matrix factorization. It learns a shared feature matrix for
all views and prevents the effect from missing view with $L_{2,1}$-Norm
regularized regression. Wang et al. [19] build a bridge between perturbation
risk bounds and missing view problems and propose PIC which reduces
perturbation risk among all views and learns a consensus Laplacian matrix.

##  III Method

Figure 1: Overview of JECL. The initialization phase initializes DNN
parameters and centroids using a stacked denoising autoencoder and K-means on
the embedded data points. During clustering phase, parameters and centroids
are updated by minimizing the regularized KL divergence between a joint
distribution $\mathbf{p}$ and the image distribution $\mathbf{q}$ (similarly,
text distribution $\mathbf{r}$) and the alignment loss between soft cluster
assignments of text and images. This figure is best viewed in color.

Figure 1 shows an overview of our method. JECL clusters data by simultaneously
learning 1) DNN parameters $\theta_{X}$ and $\theta_{T}$ that map each data
point with image feature $x_{i}$ to an embedding $z_{i}\in Z$ and each text
feature $t_{i}$ to an embedding $z_{i}^{\prime}\in Z^{\prime}$, and 2) set of
image cluster centroids $\mu_{j}$ in $Z$ and a set of text cluster centroids
$\mu^{\prime}_{j}$ in $Z^{\prime}$.

#### Parameter Initialization

We initialize DNN parameters $\theta_{X}$ and $\theta_{T}$ with two stacked
denoising autoencoders. Stacked denoising autoencoders have shown success in
generating semantically meaningful representations for both text and images in
several studies (c.f., [20, 21, 2]). We train the stacked denoising
autoencoders to learn the initial DNN parameters for each view by minimizing
mean square error reconstruction loss. After training the autoencoders, we
discard the decoders, pass data $x_{i}$ and $t_{i}$ through the trained
encoders to obtain the initialized embeddings $z_{i}$ and $z_{i}^{\prime}$.
Then, we apply K-means to the embeddings $z_{i}$ and $z_{i}^{\prime}$ to
obtain initialized centroid sets $\mu_{j}$ and $\mu^{\prime}_{j}$.

#### Soft Assignment

Following Xie et al. [2], we model the probability of data point $i$ being
assigned to cluster $j$ using the Student’s t-distribution [22], producing a
distribution ($q_{ij}$ for images and $r_{ij}$ for text).

$q_{ij}=\frac{(1+\mathinner{\\!\left\lVert
z_{i}-\mu_{j}\right\rVert}^{2}/\alpha)^{-\frac{\alpha+1}{2}}}{\sum_{j^{\prime}}(1+\mathinner{\\!\left\lVert
z_{i}-\mu_{j^{\prime}}\right\rVert}^{2}/\alpha)^{\frac{\alpha+1}{2}}}$ (1)
$r_{ij}=\frac{(1+\mathinner{\\!\left\lVert
z^{\prime}_{i}-\mu^{\prime}_{j}\right\rVert}^{2}/\alpha)^{-\frac{\alpha+1}{2}}}{\sum_{j^{\prime}}(1+\mathinner{\\!\left\lVert
z^{\prime}_{i}-\mu^{\prime}_{j^{\prime}}\right\rVert}^{2}/\alpha)^{\frac{\alpha+1}{2}}}$
(2)

where $q_{ij}$ and $r_{ij}$ are the soft assignments for images and text,
respectively, and $\alpha$ is the number of degrees of freedom of the
Student’s t-distribution.

#### Cluster Alignment

After calculating the soft assignments for both views, we must align the two
sets of $k$ clusters, since the $j$-th image cluster does not necessarily
correspond to the $j$-th text cluster. To achieve this, we use the popular
Hungarian algorithm [23] to obtain the alignment between image clusters and
text clusters. Hungarian algorithm is an optimization algorithm to solve the
assignment problem by minimizing the assignment cost. We create a $k\times k$
confusion matrix where an entry $(m,n)$ represents the number of data points
being assigned to $m$-th image cluster and $n$-th text cluster. We then
subtract the maximum value of the matrix from the value of each cell to obtain
the “cost.“ The Hungarian algorithm is then applied to the cost matrix to find
a clustering assignment with the minimum cost.

#### Clustering with KL Divergence Minimization

Similar to Xie et al., we refine the cluster centroids by leveraging high-
confidence assignments using an auxiliary joint target distribution. However,
JECL is trained by matching both the image soft assignments $\mathbf{q}$ and
the text soft assignments $\mathbf{r}$ to a _single_ target distribution
$\mathbf{p}$, which allows information passing between the two models.
Specifically, JECL minimizes the KL divergence between $\mathbf{p}$ and
$\mathbf{q}$ and the KL divergence between $\mathbf{p}$ and $\mathbf{r}$. The
joint loss is as follows:

$\displaystyle L_{cluster}$
$\displaystyle=\underbrace{KL(\mathbf{p}||\mathbf{q})}_{\text{image
loss}}+\underbrace{KL(\mathbf{p}||\mathbf{r})}_{\text{text loss}}$ (3)
$\displaystyle=\frac{1}{N}\sum^{N}_{i}\sum^{k}_{j}\Big{\\{}p_{ij}\log\frac{p_{ij}}{q_{ij}}+p_{ij}\log\frac{p_{ij}}{r_{ij}}\Big{\\}}$
(4)

Dataset | # Points | # Categories | average # words | % of largest Class | % of smallest Class
---|---|---|---|---|---
Coco-cross | 7429 | 10 | 50.5 | 23.2 % | 1.6%
Coco-all | 23189 | 43 | 50.4 | 7.4% | 0.4%
Pascal | 1000 | 20 | 48.9 | 5.0% | 5.0%
RGB-D | 1449 | 13 | 38.5 | 26.4% | 1.7%

TABLE I: Dataset statistics.

#### Choice of Joint Target Distribution

The target distribution $\mathbf{p}$ aims to improve cluster purity and to
emphasize data points with high assignment confidence [2]. Our preliminary
design adapted this idea to the multi-view problem setting by using a separate
target distribution for text and images sub-models separately. But we found
that aligning both images and text to the same joint target distribution
simplified the model, improved performance, and was more robust to noise. The
JECL target distribution is as follows.

$p_{ij}=\lambda\times\frac{\nicefrac{{q^{2}_{ij}}}{{\sum_{i}q_{ij}}}}{\sum_{j^{\prime}}\nicefrac{{q^{2}_{ij^{\prime}}}}{{\sum_{i}q_{ij^{\prime}}}}}+(1-\lambda)\times\frac{\nicefrac{{r^{2}_{ij}}}{{\sum_{i}r_{ij}}}}{\sum_{j^{\prime}}\nicefrac{{r^{2}_{ij^{\prime}}}}{{\sum_{i}r_{ij^{\prime}}}}}$
(5)

where $\lambda$ is a hyperparameter controlling the relative influence of the
images and texts, which we set to 0.5 for all experiments but may be optimized
or selected for specialized domains. We found that tuning $\lambda$ had only a
mild effect on performance on our datasets in Section IV-E. This model is
naturally robust to missing text or missing images: Missing text causes the
second term in equation (5) to be 0, such that the data points _with_ text
have a higher value of $p_{ij}$ and therefore contribute a larger gradient to
the model. We will show this effect experimentally in Section IV-E.

#### Cross-Modality Alignment Loss

To better exploit the paired features of our data, we apply cross-modality
alignment loss to force the soft assignments of every image-caption pair to be
similar. The idea is that the text and image from the same pair should be
assigned to the same cluster (and, more generally, should have similar soft
assignment distributions). We use Jensen–Shannon divergence (JSD) [24] to
capture the similarity between the cluster assignment distributions:

$\displaystyle L_{align}$ $\displaystyle=JSD(\mathbf{q}||\mathbf{r})$ (6)
$\displaystyle=\frac{1}{2}KL(\mathbf{r}||\mathbf{s})+\frac{1}{2}KL(\mathbf{q}||\mathbf{s})$
(7)

where $\mathbf{s}=\frac{1}{2}(\mathbf{q}+\mathbf{r})$. JSD is preferred in
this setting over KL divergence because it is symmetric and always has a
finite value.

#### Distribution Regularizer

Many clustering algorithms are prone to producing trivial solutions and empty
clusters [6, 25]. Distribution regularizers can significantly improve
clustering performance [6, 26] in these situations. Dizaji et al. used a
regularization term to penalize non-uniform cluster assignments. In our case,
the overall distribution of the data is unknown and we can not assume that the
distribution should be uniform. Instead, we apply a regularizer on each view
to avoid empty clusters and maintain freedom for the overall distribution. We
define a target label distribution by averaging the soft frequencies for every
view.

$\displaystyle m_{j}=q(y=j)$ $\displaystyle=\frac{1}{N}\sum^{N}_{i}r_{ij}$ (8)
$\displaystyle n_{j}=r(y=j)$ $\displaystyle=\frac{1}{N}\sum^{N}_{i}q_{ij}$ (9)

where $m_{j}$ and $n_{j}$ can be interpreted as the prior frequency of
clusters for image and text, respectively. To impose the preference of a
balanced assignment, we add a term representing the KL divergence from a
uniform distribution $\mathbf{u}$. The regularized KL divergence is computed
as

$\displaystyle L_{\text{reg-img}}$ $\displaystyle=KL(\mathbf{m}||\mathbf{u})$
(10) $\displaystyle L_{\text{reg-txt}}$
$\displaystyle=KL(\mathbf{n}||\mathbf{u})$ (11)

and the overall regularized term can be summarized as:

$L_{reg}=L_{reg-img}+L_{reg-txt}$ (12)

The overall loss function is as follows.

$L_{JECL}=L_{cluster}+\gamma L_{align}+\beta L_{reg}$ (13)

where the first term aims to minimize the dissimilarity between the soft
assignment distribution and the joint target distribution as a clustering
objective, the second term is to penalize dissimilar soft assignments from the
image and text of the same pair, and the last term is to force the model to
prefer a balanced assignment for each view to prohibit empty clusters. We have
$\gamma$ and $\beta$ as hyperparameters to adjust the weightings of the
alignment term and regularized term. We will show that JECL is stable to our
hyperparameters in Section IV-E.

#### Optimization

During the training process, we alternate between two steps. In the first
step, we compute the target distribution $p_{ij}$ from $q_{ij}$ and $r_{ij}$.
In the second step, we fix $p_{ij}$ to update $q_{ij}$ and $r_{ij}$ by
refining the parameters ($\theta_{X}$ and $\theta_{T}$) and cluster centroids
($\mu_{j}$ and $\mu_{j}^{\prime}$) via gradient descent. The process continues
until convergence.

#### Final Cluster Assignment

After convergence is met, JECL learns a pair of representations
$(z_{i},z^{\prime}_{i})$ for each image-text pair $(x_{i},t_{i})$. The final
cluster assignment $y_{i}$ can be obtained by

$y_{i}=\operatorname*{arg\,max}_{j}{p_{ij}}$ (14)

| Coco-cross | Coco-all | Pascal | RGB-D
---|---|---|---|---
| ACC | NMI | ARI | ACC | NMI | ARI | ACC | NMI | ARI | ACC | NMI | ARI
Single-View (Image)
ResNet-50 + KM | 0.647 | 0.712 | 0.558 | 0.519 | 0.614 | 0.442 | 0.486 | 0.516 | 0.307 | 0.353 | 0.289 | 0.161
ResNet-50 + DEC | 0.649 | 0.629 | 0.670 | 0.472 | 0.701 | 0.429 | 0.418 | 0.564 | 0.311 | 0.421 | 0.352 | 0.236
Single-View (Text)
Doc2Vec + KM | 0.720 | 0.852 | 0.737 | 0.613 | 0.807 | 0.589 | 0.544 | 0.602 | 0.398 | 0.438 | 0.384 | 0.279
Doc2Vec + DEC | 0.720 | 0.843 | 0.729 | 0.557 | 0.738 | 0.501 | 0.295 | 0.294 | 0.120 | 0.429 | 0.383 | 0.287
Concatenation of Both Views + Single-View Models
Concat(ResNet50+Doc2Vec) + KM | 0.636 | 0.711 | 0.550 | 0.517 | 0.617 | 0.439 | 0.478 | 0.517 | 0.302 | 0.355 | 0.290 | 0.211
Concat(ResNet50+Doc2Vec) + DEC | 0.737 | 0.758 | 0.677 | 0.419 | 0.550 | 0.275 | 0.225 | 0.326 | 0.121 | 0.344 | 0.255 | 0.172
Multi-View Representation Learning
VSE + KM | 0.665 | 0.736 | 0.607 | 0.520 | 0.628 | 0.430 | 0.479 | 0.508 | 0.300 | 0.388 | 0.318 | 0.194
DCCA + KM | 0.712 | 0.822 | 0.703 | 0.645 | 0.817 | 0.603 | 0.442 | 0.485 | 0.238 | 0.388 | 0.310 | 0.186
CCAL-$L_{rank}$ \+ KM | 0.699 | 0.806 | 0.689 | 0.641 | 0.812 | 0.587 | 0.446 | 0.489 | 0.224 | 0.404 | 0.316 | 0.196
Multi-View Clustering
BMVC | 0.365 | 0.227 | 0.200 | 0.410 | 0.441 | 0.316 | 0.392 | 0.378 | 0.214 | 0.207 | 0.088 | 0.047
MultiViewLRSSC | 0.726 | 0.781 | 0.706 | 0.569 | 0.747 | 0.530 | 0.534 | 0.574 | 0.371 | 0.474 | 0.400 | 0.277
DMF-MVC | 0.829 | 0.805 | 0.774 | 0.632 | 0.776 | 0.608 | 0.512 | 0.573 | 0.380 | 0.441 | 0.330 | 0.257
JECL | 0.929 | 0.908 | 0.934 | 0.675 | 0.801 | 0.685 | 0.512 | 0.625 | 0.403 | 0.543 | 0.472 | 0.367
w/o alignment | 0.922 | 0.906 | 0.931 | 0.634 | 0.784 | 0.643 | 0.502 | 0.613 | 0.332 | 0.513 | 0.423 | 0.277
w/o regularizer | 0.894 | 0.890 | 0.889 | 0.624 | 0.777 | 0.610 | 0.513 | 0.620 | 0.376 | 0.520 | 0.433 | 0.327
w/o alignment & regularizers | 0.863 | 0.878 | 0.852 | 0.611 | 0.757 | 0.607 | 0.487 | 0.579 | 0.352 | 0.502 | 0.413 | 0.367

TABLE II: Clustering performance of several single-view and multi-view
algorithms on four datasets. The results reported are the average of five
iterations. JECL outperforms competitive methods on three datasets by a large
margin. We also conduct an ablation study on the regularization term and
alignment loss. The experimental results show that both additions improve the
model significantly.

##  IV Experiments

We evaluate JECL with four benchmark datasets and compare to both single-view
and multi-view algorithms.

###  IV-A Datasets

To evaluate our method, we choose benchmark datasets that have images with
corresponding captions as well as ground-truth labels to define the clusters.
We summarize the datasets in Table I. (1) Coco-cross: MSCOCO [27] is a large-
scale object detection, segmentation, and captioning dataset. There are five
sentences of captions per image. We discard images containing multiple objects
and only consider the largest category from ten supercategories. Finally, we
have 7,429 data points from these ten categories in total. (2) Coco-all: For
this subset of MSCOCO, similar to Coco-cross, we remove images with more than
one object, and we remove all categories that include less than 100 images.
The result is a dataset with 23,189 images from 43 categories. (3) Pascal
[28]: This dataset contains 1,000 images with 20 categories, 50 images each
category. Every image is associated with five sentences. (4) RGB-D [29]: This
dataset includes 1,449 images with 13 indoor scenes. Every image is captioned
with a paragraph which describes the content of the image. Compared to Coco
and Pascal datasets, the captions in this dataset are less specific to the
categories and significantly less reliable as a source of information.

Figure 2: Clustering behavior of JECL, DCCA and DMF-MVC. Color indicates
ground-truth labels. Cluster shape and position is not meaningful. JECL
successfully separates semantically distinct clusters with clear boundaries
between clusters. While DCCA and DMF-MVC are able to gather semantic similar
images, the boundaries between clusters are unclear, which is reflected in the
quantitative performance.

###  IV-B Competitive Methods

We compare our method to a variety of single-view and multi-view methods.

#### Single-View Methods

We run two single-view methods to serve as baseline comparisons: K-means (KM)
[30] and Deep Embedded Clustering (DEC) [2].

#### Multi-View Methods

We evaluate six state-of-the-art multi-view methods, including three multi-
view representation learning models and three multi-view clustering models. We
also evaluate a naive baseline for multi-view methods that simply concatenates
the ResNet-50 features and the Doc2Vec features before applying K-means and
DEC as in the single-view case. (1) VSE [8]: Unifying Visual-Semantic
Embeddings unifies joint image-text embedding models by minimizing pairwise
ranking loss. K-means is implemented to acquire the cluster centroids. (2)
DCCA [31]: Deep Canonical Correlation Analysis learns complex nonlinear
transformations of two views of data by maximizing the regularized total
correlation. The cluster assignments are obtained with K-means on the joint
representations. (3) CCAL-$L_{rank}$: This method learns a joint
representation by maximizing Canonical Correlation with a pairwise ranking
loss. K-means is applied to the learned embeddings. (4) DMF-MVC [15]: Multi-
View Clustering via Deep Matrix Factorization is a deep matrix factorization
framework to learn the semantic information of all views in a layer-wise
fashion. (5) BMVC [16]: Binary Multi-view Clustering is a joint learning
framework simultaneously compressing inputs into collaborative binary
representations and clustering the collaborative representations using a
binary matrix factorization model. (6) MLRSSC [17]: Multi-view Low-rank Sparse
Subspace Clustering is a multi-view spectral clustering framework that learns
a joint subspace representation by building affinity matrix among all views
with the constraints of low-rank and sparsity.

###  IV-C Evaluation Metrics

All experiments are evaluated by three standard clustering metrics: clustering
accuracy (ACC), normalized mutual information (NMI), and adjusted rand index
(ARI). For all metrics, higher numbers indicates better performance.

Figure 3: The 5 highest-confidence images in each cluster from JECL and DEC.
JECL clusters appear qualitatively better. For example, airplanes and kites,
two visually and semantically similar concepts, are clearly distinguished,
while DEC appears to struggle to distinguish giraffes and pizza. Figure 4: The
experimental results of hyperparameter sensitivity. The dash lines are the
best performing competitive algorithms listed in Table II. JECL is generally
robust to hyperparameter settings, while is the most stable and produces top
results with $\lambda=0.5$, $\beta=0.1$ and $\gamma=0.1$ among all datasets.

(a)

(b)

Figure 5: JECL performance as data size decreases. The performance degrades
when size ratio is below 0.5 (500 data points in each class), while JECL still
outperforms the state-of-the-art multi-view clustering methods, DMF-MVC and
MLRSSC on varying data sizes.  Figure 6: Experimental results on missing view
scenarios. JECL is competitive with the state-of-the-art method, PIC, and
outperforms DAIMC by a large margin on both datasets. Figure 7: JECL’s
robustness to missing data is attributable to the model of the joint
distribution: the images with text (orange) contribute more to the gradient
than the images with missing text (blue).

###  IV-D Implementation

We use a ResNet-50 model [32], pretrained on the 1.2M images from ImageNet
[33], to extract 2048-dimensional images features and Doc2vec [34], pretrained
on Wikipedia via skip-gram, to obtain 300-dimensional text features. All
methods are fed with these pre-trained features except for VSE, which has raw
text as input. We use hyperparameter settings following Xie et al. [2] for DEC
components. $\lambda$, $\gamma$, and $\beta$ are set to 0.5, 0.1, and 0.1 in
all experiments, respectively. We will show that the model remains stable to
different hyperparameter settings within reasonable range in next section. For
baseline algorithms, we use the same setting in their corresponding paper. All
the results are the average of 5 trials .

###  IV-E Experimental Results

Table II displays the quantitative results for different methods on various
datasets. JECL outperforms other tools on almost every dataset by a
significant margin. The table also contains the results of an ablation study
of the distribution regularizer and distribution alignment loss. We can see
that both additions improve the overall performance.

#### Qualitative Comparison

The cluster metrics are difficult to interpret, so we are interested in
exploring a qualitative comparison between JECL and the best single-view
(DEC), image-text representation learning (DCCA), and multi-view (DMF-MVC)
competitors. Figure 2 is a visualization of the latent space of JECL to
illustrate its effectiveness in producing coherent clusters. We use t-SNE to
visualize the embeddings from the latent space. The positions and shapes of
the clusters are not meaningful due to the operation of t-SNE. JECL is able to
generate semantically distinct clusters with clear boundaries between
clusters. While DCCA and DMF-MVC are able to associate semantically similar
images, the cluster boundaries are less distinct. We further compare JECL to
DEC to examine the effect of additional view and our alignment loss by
inspecting examples of the clusters. Figure 3 shows the top five images with
highest confidence from each cluster from the Coco-cross dataset. The figure
shows that DEC clusters are not always coherent. For example, cluster #1 and
cluster #7 seem to include mostly airplane images and cluster #0 and cluster
#4 are clock clusters. Cluster #9 from DEC is a fusion of giraffe and pizza,
which are not at all similar semantically. Our guess is that both giraffe and
pizza share similar colors (yellow) and patterns (spots on the giraffe body
and toppings on the pizza). JECL, on the other hand, is easily able to
distinguish these objects, because the text descriptions expose their semantic
differences. Surprisingly, JECL is also able to distinguish airplane and kite,
which are not only visually similar, but are also semantically related.
However, we are still able to observe some errors from JECL, such as examples
of suitcase and cellphone, which are visually similar, assigned into the same
cluster (cluster #1) and clock examples separated into two clusters: clocks on
towers (cluster #2) and indoors clocks (cluster #9). _To summarize, JECL
appears to tolerate ambiguity better than other methods._

#### Model Sensitivity to Parameters

We have three hyperparameters, $\lambda$, $\beta$, and $\gamma$, to control
the weighting of text and image, distribution regularizer, and alignment loss,
respectively. JECL is designed for unsupervised learning scenarios, where the
training data is limited and hyperparameters tuning is unachievable. In this
section, we will show that JECL is robust to different hyper-parameters
settings within reasonable range. Figure 4 shows the model performance on
various hyperparameter settings. On the weighting between text and image
$\lambda$, we discover that the model is stable with $\lambda$ between 0.3 and
0.7 and performs the highest or close to the highest when $\lambda=0.5$, which
means JECL has equal weighting on text and images. This is not surprising. As
we mention in Section III, JECL naturally learns from high confidence data
points. In DEC, data points close to cluster centroids are those with high
confidence which contribute more to the gradients. In multi-view setting, JECL
learns from data points with consistent soft assignments of the text and image
pairs with the aid of high confidence data points from all views. With this
mechanism, tuning $\lambda$ is trivial and we will demonstrate it in missing
view experiment. Then, we study the effect of hyperparameter for distribution
regularizer term, $\beta$. From Figure 4, we can observe that the model
performance remains stable but slowly deteriorates when $\beta$ is close to 1.
The number of empty clusters decreases by 23% when the regularizer is applied.
Finally, we investigate the influence on the hyperparameter $\gamma$, which is
used to adjust the text-image alignment loss. We use a wider range to test the
$\gamma$, because we wonder whether a stronger image-text bond would help
overall clustering performance. We can see that the overall model performance
remains steady with $\gamma<1$ and it drops dramatically with $\gamma>1$. The
reason for this deterioration is that the alignment loss dominates overall
loss and causes the clustering to perform poorly. _To summarize, JECL is
robust when $\beta$ and $\gamma$ are smaller than 1._

#### Sensitivity to Data Size

We consider JECL performance with varying data size. In order to evaluate the
performance of JECL on varying data size, we produce a subset of Coco-all
(labeled all-sub in the figures and tables) with 8000 image-text pairs: 8
classes with 1000 image-text pairs each. We then sample this subset to vary
the data size. We compare against the two state-of-the-art multi-view
clustering methods, DMF-MVC and MLRSSC. Figure 5 shows that JECL’s performance
is robust until only 500 data points in each class remain and drops
dramatically when only 100 data points in each class remain. Despite this drop
in performance, _JECL continues to outperform competitive models, DMF-MVC and
MLRSSC on these smaller data sizes._

#### Robustness to Missing Text

Incomplete views are a common problem in multi-view clustering [35]; we cannot
expect all images to be equipped with text descriptions. To analyze the
robustness of JECL when text descriptions are missing, we remove text from a
random set of images at varying rates on Coco-cross and all-sub dataset. We
compare our method against two state-of-the-art incomplete multi-view
clustering model, PIC [19] and DAIMC [18]. The missing view experimental
results appear in Figure 6. JECL is competitive with PIC on both datasets and
outperforms DAIMC by a large margin. Figure 7 demonstrates that images with
captions (orange dots) have larger value of $p_{ij}$ and contribute a larger
gradient to the training process. Images with missing text have a smaller
associated value of $p_{ij}$ because the second term in equation (5) vanishes.

##  V Conclusion

We present JECL, a method that learns representations from multi-modal image-
text pairs for clustering analysis. JECL trains two parallel encoders with
clustering layers, one for images and one for text, alternating between
computing a proposed joint target distribution and minimizing KL divergence
between the embedded data distribution to the computed joint target
distribution. At the same time, JECL also learns to align the soft cluster
assignments between images and text. JECL exhibits superior performance on
various datasets, outperforming both single-view and state-of-the-art multi-
view models. We further examine the robustness of JECL to sources of problems,
including hyperparameter sensitivity, missing text and small data sizes. Our
results suggest that JECL is broadly effective for multi-modal clustering.

## References

  * [1] P.-s. Lee, S. T. Yang, J. D. West, and B. Howe, “Phyloparser: A hybrid algorithm for extracting phylogenies from dendrograms,” in _ICDAR_ , 2017\.
  * [2] J. Xie, R. Girshick, and A. Farhadi, “Unsupervised deep embedding for clustering analysis,” in _ICML_ , 2016.
  * [3] A. Karpathy and L. Fei-Fei, “Deep visual-semantic alignments for generating image descriptions,” in _CVPR_ , 2015.
  * [4] M. Dorfer, J. Schlüter, A. Vall, F. Korzeniowski, and G. Widmer, “End-to-end cross-modality retrieval with cca projections and pairwise ranking loss,” _International Journal of Multimedia Information Retrieval_ , vol. 7, no. 2, pp. 117–128, 2018.
  * [5] C. Jin, W. Mao, R. Zhang, Y. Zhang, and X. Xue, “Cross-modal image clustering via canonical correlation analysis,” in _AAAI_ , 2015.
  * [6] K. G. Dizaji, A. Herandi, C. Deng, W. Cai, and H. Huang, “Deep clustering via joint convolutional autoencoder embedding and relative entropy minimization,” in _ICCV_ , 2017.
  * [7] A. Frome, G. S. Corrado, J. Shlens, S. Bengio, J. Dean, T. Mikolov _et al._ , “Devise: A deep visual-semantic embedding model,” in _NIPS_ , 2013.
  * [8] R. Kiros, R. Salakhutdinov, and R. S. Zemel, “Unifying visual-semantic embeddings with multimodal neural language models,” _Transactions of the Association for Computational Linguistics_ , 2014.
  * [9] L. Wang, Y. Li, and S. Lazebnik, “Learning deep structure-preserving image-text embeddings,” in _CVPR_ , 2016.
  * [10] Y.-H. H. Tsai, L.-K. Huang, and R. Salakhutdinov, “Learning robust visual-semantic embeddings,” in _ICCV_ , 2017.
  * [11] D. R. Hardoon, S. Szedmak, and J. Shawe-Taylor, “Canonical correlation analysis: An overview with application to learning methods,” _Neural computation_ , vol. 16, no. 12, pp. 2639–2664, 2004.
  * [12] F. Yan and K. Mikolajczyk, “Deep correlation for matching images and text,” in _CVPR_ , 2015.
  * [13] M. Grechkin, H. Poon, and B. Howe, “Ezlearn: Exploiting organic supervision in large-scale data annotation,” in _IJCAI_ , 2018.
  * [14] J. Liu, C. Wang, J. Gao, and J. Han, “Multi-view clustering via joint nonnegative matrix factorization,” in _SDM_ , 2013.
  * [15] H. Zhao, Z. Ding, and Y. Fu, “Multi-view clustering via deep matrix factorization,” in _AAAI_ , 2017.
  * [16] Z. Zhang, L. Liu, F. Shen, H. T. Shen, and L. Shao, “Binary multi-view clustering,” _IEEE transactions on pattern analysis and machine intelligence_ , 2018.
  * [17] M. Brbić and I. Kopriva, “Multi-view low-rank sparse subspace clustering,” _Pattern Recognition_ , vol. 73, pp. 247–258, 2018.
  * [18] M. Hu and S. Chen, “Doubly aligned incomplete multi-view clustering,” in _IJCAI_ , 2018.
  * [19] H. Wang, L. Zong, B. Liu, Y. Yang, and W. Zhou, “Spectral perturbation meets incomplete multi-view data,” in _IJCAI_ , 2018.
  * [20] P. Vincent, H. Larochelle, I. Lajoie, Y. Bengio, and P.-A. Manzagol, “Stacked denoising autoencoders: Learning useful representations in a deep network with a local denoising criterion,” _Journal of machine learning research_ , vol. 11, no. Dec, pp. 3371–3408, 2010.
  * [21] Q. V. Le, “Building high-level features using large scale unsupervised learning,” in _ICASSP_ , 2013.
  * [22] L. v. d. Maaten and G. Hinton, “Visualizing data using t-sne,” _Journal of machine learning research_ , vol. 9, no. Nov, pp. 2579–2605, 2008.
  * [23] H. W. Kuhn, “The hungarian method for the assignment problem,” _Naval research logistics quarterly_ , vol. 2, no. 1-2, pp. 83–97, 1955.
  * [24] C. E. Shannon and W. Weaver, _The mathematical theory of communication_. University of Illinois press, 1998.
  * [25] M. Caron, P. Bojanowski, A. Joulin, and M. Douze, “Deep clustering for unsupervised learning of visual features,” in _ECCV_ , 2018.
  * [26] Y. Lin, X. Dong, L. Zheng, Y. Yan, and Y. Yang, “A bottom-up clustering approach to unsupervised person re-identification,” in _AAAI_ , vol. 2, 2019, pp. 1–8.
  * [27] T.-Y. Lin, M. Maire, S. Belongie, J. Hays, P. Perona, D. Ramanan, P. Dollár, and C. L. Zitnick, “Microsoft coco: Common objects in context,” in _ECCV_ , 2014.
  * [28] C. Rashtchian, P. Young, M. Hodosh, and J. Hockenmaier, “Collecting image annotations using amazon’s mechanical turk,” in _NAACL_ , 2010.
  * [29] C. Kong, D. Lin, M. Bansal, R. Urtasun, and S. Fidler, “What are you talking about? text-to-image coreference,” in _CVPR_ , 2014.
  * [30] S. Lloyd, “Least squares quantization in pcm,” _IEEE transactions on information theory_ , vol. 28, no. 2, pp. 129–137, 1982.
  * [31] G. Andrew, R. Arora, J. Bilmes, and K. Livescu, “Deep canonical correlation analysis,” in _ICML_ , 2013.
  * [32] K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” in _CVPR_ , 2016.
  * [33] J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei, “Imagenet: A large-scale hierarchical image database,” in _CVPR_ , 2009.
  * [34] Q. Le and T. Mikolov, “Distributed representations of sentences and documents,” in _ICML_ , 2014.
  * [35] C. Xu, D. Tao, and C. Xu, “Multi-view learning with incomplete views,” _IEEE Transactions on Image Processing_ , vol. 24, no. 12, pp. 5812–5825, 2015.


$\widehat{\mathrm{M}}_{\alpha,\beta}\geq
C_{\alpha,\beta}\frac{\widehat{C}^{cb}_{S_{A\otimes E}}\left(\left(E_{\rm
fix}^{A^{n}}\right)^{*}\right)}{\widehat{D}},\quad
C_{\alpha,\beta}:=\min\left\\{\alpha^{-\frac{1}{\beta-1}}\left(\frac{1-\varepsilon}{3t_{\rm
mix}^{S_{A\otimes
E}}(\varepsilon)}\right)^{\frac{\beta}{\beta-1}},\frac{1-\varepsilon}{2}\right\\}.$
(5.43) Finally, we provide estimates of $\widehat{C}^{cb}_{S_{A\otimes
E}}\left(\left(E_{\rm fix}^{A^{n}}\right)^{*}\right)$ and $t_{\rm
mix}^{S_{A\otimes E}}(\varepsilon)$. In fact, we choose the certificate
operator $\sum_{j=1}^{n}X_{j}\otimes I_{E}$ and recall the definition of
$\widehat{C}_{S_{A\otimes E}}$: $\displaystyle\widehat{C}_{S_{A\otimes
E}}\left(\left(E_{\rm fix}^{A^{n}}\right)^{*}\right)$
$\displaystyle=\sup_{X_{AE}\in\mathbb{B}(AE),\||X_{AE}|\|_{S_{A\otimes E}}\neq
0}\frac{\|(\mathcal{E}((E_{\rm
fix}^{A^{n}})^{*}-id_{A^{n}})\mathcal{D})^{*}(X_{AE})\|_{\infty}}{\||X_{AE}|\|_{S_{A\otimes
E}}}$ $\displaystyle=\sup_{X_{AE}\in\mathbb{B}(AE),\||X_{AE}|\|_{S_{A\otimes
E}}\neq 0}\frac{\|\mathcal{D}^{*}(E_{\rm
fix}^{A^{n}}-id_{A^{n}})\mathcal{E}^{*}(X_{AE})\|_{\infty}}{\||X_{AE}|\|_{S_{A\otimes
E}}}$ $\displaystyle\geq\frac{\|\mathcal{D}^{*}(E_{\rm
fix}^{A^{n}}-id_{A^{n}})(\sum_{j=1}^{n}X_{j})\|}{\||\sum_{j=1}^{n}X_{j}\otimes
I_{E}|\|_{S_{A\otimes
E}}}=\frac{\|\sum_{j=1}^{n}X_{j}\|_{\infty}}{\sup_{k}\|[Y_{k},\sum_{j=1}^{n}X_{j}]\otimes
X_{E}\|_{\infty}}=\frac{n}{2}.$ This directly implies
$\widehat{C}^{cb}_{S_{A\otimes E}}\left(\left(E_{\rm
fix}^{A^{n}}\right)^{*}\right)\geq\widehat{C}_{S_{A\otimes
E}}\left(\left(E_{\rm fix}^{A^{n}}\right)^{*}\right)\geq\frac{n}{2}$.
Similarly, we can check that $\displaystyle\widehat{C}^{cb}_{S_{A\otimes
E}}(T_{t})$ $\displaystyle\geq\widehat{C}_{S_{A\otimes
E}}(T_{t})=\sup_{X_{AE}\in\mathbb{B}(AE),\||X_{AE}|\|_{S_{A\otimes E}}\neq
0}\frac{\|(\mathcal{E}(T_{t}-id_{A^{n}})\mathcal{D})^{*}(X_{AE})\|_{\infty}}{\||X_{AE}|\|_{S_{A\otimes
E}}}$
$\displaystyle\geq\frac{\|\mathcal{D}^{*}(T_{t}^{*}-id_{A^{n}})(\sum_{j=1}^{n}X_{j})\|}{\||\sum_{j=1}^{n}X_{j}\otimes
I_{E}|\|_{S_{A\otimes
E}}}=(1-e^{-t})\frac{\|\sum_{j=1}^{n}X_{j}\|}{\||\sum_{j=1}^{n}X_{j}\otimes
I_{E}|\|_{S_{A\otimes E}}}=\frac{(1-e^{-t})n}{2},$ thus we can show that
$t_{\rm mix}^{S_{A\otimes E}}$ is bounded by a universal constant. Using
Theorem 5.11, we find a tight lower bound for
$\widehat{\mathrm{M}}_{\alpha,\beta}$ in terms of the number of qubits $n$:
$C_{\alpha,\beta}\frac{n}{\tau+6}\leq\widehat{\mathrm{M}}_{\alpha,\beta}\leq\frac{\pi
n}{\tau}.$ (5.44)

######  Remark 5.19.

Using Theorem 5.13, we can get the desirable behavior of linear dependency
$\widehat{l}_{\delta}^{\mathcal{U}_{A\otimes E}}(T_{t})=\Theta(nt).$

##  6 Conclusion

Our technique for the lower bound of simulation cost of open quantum systems
is based on the convex cost function defined in Section 4. The linear in time
behavior of the lower bounds that already have been observed in [7, 29] is
captured in our Theorem 4.15. Moreover, our dimension factor
$\frac{\kappa^{cb}(S)}{t_{\rm{mix}}^{S}}$ exhibits a new phenomenon, which
works for a more general class of generators than presented in previous works.
Explicit estimates of the dimension factor are given for $n$ qubit Pauli-type
and amplitude damping noise and the tightness of our lower bound is
illustrated by showing that the upper and lower bounds coincide in those two
examples. We leave the concrete analysis for more complicated generators for
future research.

##  7 Acknowledgements

The authors thank Tyler Kharazi for helpful discussions. Z.D., M.J. and P.S.
thank the Institute for Pure and Applied Mathematics (IPAM) for its
hospitality in hosting them as long-term visitors during the semester-long
program “Mathematical and Computational Challenges in Quantum Computing” in
Fall 2023.

##  Appendix A Hamiltonian simulation for amplitude damping noise

In this section, we present the missing calculation about the amplitude
damping channel $\mathcal{N}_{t}$ in (5.37). To be more specific, We need to
find the explicit expression of $U_{t}$ such that
$\mathcal{N}_{t}(\rho)=\Tr_{E}(U_{t}(\rho\otimes\outerproduct{0}{0}_{E})U_{t}^{*})$,
where the amplitude damping noise is given by
$\mathcal{N}_{t}\begin{pmatrix}\rho_{00}&\rho_{01}\\\
\rho_{10}&\rho_{11}\end{pmatrix}=\begin{pmatrix}\rho_{00}+(1-e^{-2t})\rho_{11}&e^{-t}\rho_{01}\\\
e^{-t}\rho_{10}&e^{-2t}\rho_{11}\end{pmatrix}.$ (A.1) In terms of Stinespring
dilation, $\mathcal{N}_{t}$ can be viewed as a coupling with a zero-
temperature external bath $\ket{0}_{E}$, i.e.,
$\mathcal{N}_{t}(\rho)=\Tr_{E}(V_{t}(\rho\otimes\outerproduct{0}{0}_{E})V_{t}^{*}),$
with the partial isometry $V_{t}$ so that $\displaystyle V_{t}:$
$\displaystyle\ket{0}_{A}\otimes\ket{0}_{E}\mapsto\ket{0}_{A}\otimes\ket{0}_{E},$
(A.2)
$\displaystyle\ket{1}_{A}\otimes\ket{0}_{E}\mapsto\sqrt{1-e^{-2t}}\ket{0}_{A}\otimes\ket{1}_{E}+e^{-t}\ket{1}_{A}\otimes\ket{0}_{E}.$
To find a suitable Hamiltonian to simulate $V_{t}$, we properly extend $V_{t}$
to a full unitary $U_{t}$ acting on the joint system $A\otimes E$. A specific
choice is given as $\displaystyle U_{t}:$
$\displaystyle\ket{0}_{A}\otimes\ket{0}_{E}\mapsto\ket{0}_{A}\otimes\ket{0}_{E},$
(A.3)
$\displaystyle\ket{1}_{A}\otimes\ket{0}_{E}\mapsto\sqrt{1-e^{-2t}}\ket{0}_{A}\otimes\ket{1}_{E}+e^{-t}\ket{1}_{A}\otimes\ket{0}_{E},$
$\displaystyle\ket{0}_{A}\otimes\ket{1}_{E}\mapsto
e^{-t}\ket{0}_{A}\otimes\ket{1}_{E}-\sqrt{1-e^{-2t}}\ket{1}_{A}\otimes\ket{0}_{E},$
$\displaystyle\ket{1}_{A}\otimes\ket{1}_{E}\mapsto\ket{1}_{A}\otimes\ket{1}_{E}.$
We claim that we have $U_{t}=\exp(-i\arccos(e^{-t})H),\quad
H=\frac{1}{2}(X_{A}\otimes Y_{E}-Y_{A}\otimes X_{E}),$ (A.4) where
$X_{A},Y_{A},X_{E},Y_{E}$ are the Pauli-$X,Y$ operators on the corresponding
system. One can check directly that for any real number $\theta$,
$\displaystyle i\theta
H(\ket{1}_{A}\otimes\ket{0}_{E})=\theta\ket{0}_{A}\otimes\ket{1}_{E},\quad
i\theta H(\ket{0}_{A}\otimes\ket{1}_{E})=-\theta\ket{1}_{A}\otimes\ket{0}_{E}$
Then by induction, we get for any $k\geq 0$ and real number $\theta$,
$\displaystyle(i\theta H)^{2k}:$
$\displaystyle\ket{1}_{A}\otimes\ket{0}_{E}\mapsto\theta^{2k}(-1)^{k}\ket{1}_{A}\otimes\ket{0}_{E},$
(A.5)
$\displaystyle\ket{0}_{A}\otimes\ket{1}_{E}\mapsto\theta^{2k}(-1)^{k}\ket{0}_{A}\otimes\ket{1}_{E}.$
$\displaystyle(i\theta H)^{2k+1}:$
$\displaystyle\ket{1}_{A}\otimes\ket{0}_{E}\mapsto\theta^{2k+1}(-1)^{k+1}\ket{0}_{A}\otimes\ket{1}_{E},$
$\displaystyle\ket{0}_{A}\otimes\ket{1}_{E}\mapsto\theta^{2k+1}(-1)^{k}\ket{1}_{A}\otimes\ket{0}_{E}.$
Also note that $(i\theta H)^{k}(\ket{0}_{A}\otimes\ket{0}_{E})=(i\theta
H)^{k}(\ket{1}_{A}\otimes\ket{1}_{E})=\textbf{0}$(zero vector) for $k\geq 1$.
By Taylor expansion, we have $\displaystyle\exp(i\theta H):$
$\displaystyle\ket{0}_{A}\otimes\ket{0}_{E}\mapsto\ket{0}_{A}\otimes\ket{0}_{E},$
(A.6) $\displaystyle\ket{1}_{A}\otimes\ket{0}_{E}\mapsto\sum_{k\geq
0}\frac{\theta^{2k+1}(-1)^{k+1}}{(2k+1)!}\ket{0}_{A}\otimes\ket{1}_{E}+\sum_{k\geq
0}\frac{\theta^{2k}(-1)^{k}}{(2k)!}\ket{1}_{A}\otimes\ket{0}_{E},$
$\displaystyle\ket{0}_{A}\otimes\ket{1}_{E}\mapsto\sum_{k\geq
0}\frac{\theta^{2k}(-1)^{k}}{(2k)!}\ket{0}_{A}\otimes\ket{1}_{E}+\sum_{k\geq
0}\frac{\theta^{2k+1}(-1)^{k}}{(2k+1)!}\ket{1}_{A}\otimes\ket{0}_{E},$
$\displaystyle\ket{1}_{A}\otimes\ket{1}_{E}\mapsto\ket{1}_{A}\otimes\ket{1}_{E}.$
Recall that $\cos\theta=\sum_{k\geq
0}\frac{\theta^{2k}(-1)^{k}}{(2k)!},\quad\sin\theta=\sum_{k\geq
0}\frac{\theta^{2k+1}(-1)^{k}}{(2k+1)!},$ (A.7) we have
$\displaystyle\exp(i\theta
H)(\ket{1}_{A}\otimes\ket{0}_{E})=-\sin\theta\ket{0}_{A}\otimes\ket{1}_{E}+\cos\theta\ket{1}_{A}\otimes\ket{0}_{E},$
$\displaystyle\exp(i\theta
H)(\ket{0}_{A}\otimes\ket{1}_{E})=\cos\theta\ket{0}_{A}\otimes\ket{1}_{E}+\sin\theta\ket{1}_{A}\otimes\ket{0}_{E}.$
Comparing the expression in (A.3), we choose
$\theta=-\arccos(e^{-t})\in[-\frac{\pi}{2},0]$, and we get
$U_{t}=\exp(-i\arccos(e^{-t})H).$ (A.8) Finally note that $[X_{A}\otimes
Y_{E},Y_{A}\otimes X_{E}]=0$, we have
${\mathrm{ad}}_{U_{t}}={\mathrm{ad}}_{\exp(\frac{i\arccos(e^{-t})}{2}Y_{A}\otimes
X_{E})}{\mathrm{ad}}_{\exp(\frac{-i\arccos(e^{-t})}{2}X_{A}\otimes Y_{E})}.$
(A.9)

##  Appendix B Perfect simulation of Pauli noise using one ancilla qubit

In this section, we show that using the calculation of the previous section,
we can construction a perfect simulation of the Pauli-noise on the qubit
system $A=\mathcal{H}_{2}$:
$\mathcal{T}_{t}=\exp(t(L_{X}+L_{Y})),\quad(L_{X}+L_{Y})(\rho):=X\rho X+Y\rho
Y-2\rho.$ (B.1) In fact, denote $\rho=\begin{pmatrix}\rho_{00}&\rho_{01}\\\
\rho_{10}&\rho_{11}\end{pmatrix}$, a calculation based on Taylor expansion
shows that $\displaystyle\mathcal{T}_{t}\begin{pmatrix}\rho_{00}&\rho_{01}\\\
\rho_{10}&\rho_{11}\end{pmatrix}$
$\displaystyle=\begin{pmatrix}\frac{1+e^{-4t}}{2}\rho_{00}+\frac{1-e^{-4t}}{2}\rho_{11}&e^{-2t}\rho_{01}\\\
e^{-2t}\rho_{10}&\frac{1-e^{-4t}}{2}\rho_{00}+\frac{1+e^{-4t}}{2}\rho_{11}\end{pmatrix}$
(B.2)
$\displaystyle=\frac{1}{2}\begin{pmatrix}\rho_{00}+(1-e^{-4t})\rho_{11}&e^{-2t}\rho_{01}\\\
e^{-2t}\rho_{10}&e^{-4t}\rho_{11}\end{pmatrix}+\frac{1}{2}\begin{pmatrix}e^{-4t}\rho_{00}&e^{-2t}\rho_{01}\\\
e^{-2t}\rho_{10}&(1-e^{-4t})\rho_{00}+\rho_{11}\end{pmatrix}$
$\displaystyle=\frac{1}{2}(\mathcal{N}_{2t}(\rho)+\widehat{\mathcal{N}}_{2t}(\rho)),$
where $\mathcal{N}_{t}$ is the amplitude damping noise defined in (A.1) and
$\widehat{\mathcal{N}}_{t}$ is defined by
$\widehat{\mathcal{N}}_{t}\begin{pmatrix}\rho_{00}&\rho_{01}\\\
\rho_{10}&\rho_{11}\end{pmatrix}=\begin{pmatrix}e^{-2t}\rho_{00}&e^{-t}\rho_{01}\\\
e^{-t}\rho_{10}&(1-e^{-2t})\rho_{00}+\rho_{11}\end{pmatrix}.$ (B.3) Using
exactly the same argument as the previous section, we have
$\widehat{\mathcal{N}}_{t}(\rho)=\Tr_{E}(\widehat{U}_{t}(\rho\otimes\outerproduct{0}{0}_{E})\widehat{U}_{t}^{*}),\quad\widehat{U}_{t}=\exp(-i\frac{\arccos(e^{-t})}{2}(X_{A}\otimes
Y_{E}+Y_{A}\otimes X_{E})).$ (B.4) Therefore, for the encoding
$\mathcal{E}:\rho\mapsto\rho\otimes\outerproduct{0}{0}_{E}$ and decoding
$\mathcal{D}:\rho_{AE}\mapsto\rho_{A}$, we have
$\mathcal{T}_{t}=\mathcal{D}\circ\frac{1}{2}\left({\mathrm{ad}}_{U_{1}(2t)}{\mathrm{ad}}_{U_{2}^{*}(2t)}+{\mathrm{ad}}_{U_{1}^{*}(2t)}{\mathrm{ad}}_{U_{2}^{*}(2t)}\right)\circ\mathcal{E},$
(B.5) where $U_{1}(t)=\exp(\frac{i\arccos(e^{-t})}{2}Y_{A}\otimes X_{E}),\quad
U_{2}(t)=\exp(\frac{i\arccos(e^{-t})}{2}X_{A}\otimes Y_{E}).$ (B.6)

## References

  *   * Manin [1980] Manin, Y.: Computable and uncomputable. Sovetskoye Radio, Moscow 128, 28 (1980)
  * Benioff [1980] Benioff, P.: The computer as a physical system: A microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machines. Journal of Statistical Physics 22(5), 563–591 (1980) https://doi.org/10.1007/BF01011339 . Accessed 2023-09-11
  * Feynman [1982] Feynman, R.P.: Simulating physics with computers. International Journal of Theoretical Physics 21(6-7), 467–488 (1982) https://doi.org/10.1007/BF02650179
  * Deutsch [1985] Deutsch, D.: Quantum theory, the church–turing principle and the universal quantum computer. Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences 400(1818), 97–117 (1985)
  * Berry et al. [2007] Berry, D.W., Ahokas, G., Cleve, R., Sanders, B.C.: Efficient quantum algorithms for simulating sparse Hamiltonians. Commun. Math. Phys. 270, 359–371 (2007)
  * Berry et al. [2014] Berry, D.W., Childs, A.M., Cleve, R., Kothari, R., Somma, R.D.: Exponential improvement in precision for simulating sparse Hamiltonians. In: STOC 2014 (2014)
  * Berry et al. [2015] Berry, D.W., Childs, A.M., Kothari, R.: Hamiltonian simulation with nearly optimal dependence on all parameters. In: 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pp. 792–809 (2015). IEEE
  * Low and Chuang [2019] Low, G.H., Chuang, I.L.: Hamiltonian Simulation by Qubitization. Quantum 3, 163 (2019) https://doi.org/10.22331/q-2019-07-12-163
  * Gilyén et al. [2019] Gilyén, A., Su, Y., Low, G.H., Wiebe, N.: Quantum singular value transformation and beyond: Exponential improvements for quantum matrix arithmetics. In: STOC 2019 (2019)
  * Childs et al. [2021] Childs, A.M., Su, Y., Tran, M.C., Wiebe, N., Zhu, S.: Theory of trotter error with commutator scaling. Phys. Rev. X 11, 011020 (2021) https://doi.org/10.1103/PhysRevX.11.011020
  * Childs and Wiebe [2012] Childs, A.M., Wiebe, N.: Hamiltonian simulation using linear combinations of unitary operations. arXiv preprint arXiv:1202.5822 (2012)
  * Rall et al. [2023] Rall, P., Wang, C., Wocjan, P.: Thermal State Preparation via Rounding Promises. Quantum 7, 1132 (2023)
  * Chen et al. [2023] Chen, C.-F., Kastoryano, M.J., Brandão, F.G.S.L., Gilyén, A.: Quantum thermal state preparation. arXiv:2303.18224 (2023)
  * Ding et al. [2024] Ding, Z., Li, B., Lin, L.: Efficient quantum gibbs samplers with kubo–martin–schwinger detailed balance condition. arXiv/2404.05998 (2024)
  * Ding et al. [2023] Ding, Z., Chen, C.-F., Lin, L.: Single-ancilla ground state preparation via Lindbladians. arXiv:2308.15676 (2023)
  * Kliesch et al. [2011] Kliesch, M., Barthel, T., Gogolin, C., Kastoryano, M., Eisert, J.: Dissipative quantum church-turing theorem. Physical Review Letters 107(12) (2011) https://doi.org/10.1103/physrevlett.107.120501
  * Cleve and Wang [2017] Cleve, R., Wang, C.: Efficient Quantum Algorithms for Simulating Lindblad Evolution. In: ICALP 2017, vol. 80, pp. 17–11714 (2017)
  * Li and Wang [2022] Li, X., Wang, C.: Simulating markovian open quantum systems using higher-order series expansion. arXiv preprint arXiv:2212.02051 (2022)
  * Chen et al. [2023] Chen, C.-F., Kastoryano, M.J., Brandão, F.G.S.L., Gilyén, A.: Quantum thermal state preparation (2023) arXiv:2303.18224
  * Ding et al. [2024] Ding, Z., Li, X., Lin, L.: Simulating open quantum systems using hamiltonian simulations. PRX Quantum 5, 020332 (2024) https://doi.org/10.1103/PRXQuantum.5.020332
  * Pocrnic et al. [2024] Pocrnic, M., Segal, D., Wiebe, N.: Quantum simulation of lindbladian dynamics via repeated interactions. arXiv/2312.05371 (2024)
  * Lindblad [1976] Lindblad, G.: On the generators of quantum dynamical semigroups. Communications in Mathematical Physics 48, 119–130 (1976)
  * Li et al. [2022] Li, L., Bu, K., Koh, D.E., Jaffe, A., Lloyd, S.: Wasserstein complexity of quantum circuits. arXiv preprint arXiv:2208.06306 (2022)
  * Araiza et al. [2023] Araiza, R., Chen, Y., Junge, M., Wu, P.: Resource-dependent complexity of quantum channels. arXiv preprint arXiv:2303.11304 (2023)
  * Campbell [2019] Campbell, E.: Random compiler for fast hamiltonian simulation. Physical review letters 123(7), 070503 (2019)
  * Berry et al. [2015] Berry, D.W., Childs, A.M., Cleve, R., Kothari, R., Somma, R.D.: Simulating hamiltonian dynamics with a truncated taylor series. Physical Review Letters 114(9) (2015) https://doi.org/%****␣Lower_bound_for_simulation_cost_of_open_quantum_systems.bbl␣Line␣400␣****10.1103/physrevlett.114.090502
  * Borras and Marvian [2024] Borras, E., Marvian, M.: A quantum algorithm to simulate lindblad master equations. arXiv preprint arXiv:2406.12748 (2024)
  * Chen et al. [2024] Chen, H., Li, B., Lu, J., Ying, L.: A randomized method for simulating lindblad equations and thermal state preparation. arXiv preprint arXiv:2407.06594 (2024)
  * Childs and Li [2016] Childs, A.M., Li, T.: Efficient simulation of sparse markovian quantum dynamics. arXiv preprint arXiv:1611.05543 (2016)
  * Bu et al. [2024] Bu, K., Garcia, R.J., Jaffe, A., Koh, D.E., Li, L.: Complexity of quantum circuits via sensitivity, magic, and coherence. Communications in Mathematical Physics 405(7), 161 (2024)
  * Haferkamp et al. [2022] Haferkamp, J., Faist, P., Kothakonda, N.B., Eisert, J., Yunger Halpern, N.: Linear growth of quantum circuit complexity. Nature Physics 18(5), 528–532 (2022)
  * Haferkamp [2023] Haferkamp, J.: On the moments of random quantum circuits and robust quantum complexity. arXiv preprint arXiv:2303.16944 (2023)
  * Childs et al. [2021] Childs, A.M., Su, Y., Tran, M.C., Wiebe, N., Zhu, S.: Theory of trotter error with commutator scaling. Physical Review X 11(1), 011020 (2021)
  * Suzuki [1976] Suzuki, M.: Generalized trotter’s formula and systematic approximants of exponential operators and inner derivations with applications to many-body problems. Communications in Mathematical Physics 51(2), 183–190 (1976)
  * Junge and Wu [2022] Junge, M., Wu, P.: Stability property for the quantum jump operators of an open system. arXiv preprint arXiv:2211.07527 (2022)
  * De Palma et al. [2021] De Palma, G., Marvian, M., Trevisan, D., Lloyd, S.: The quantum wasserstein distance of order 1. IEEE Transactions on Information Theory 67(10), 6627–6643 (2021)
  * Kadison [2004] Kadison, R.V.: Non-commutative conditional expectations and their applications. Contemporary Mathematics 365, 143–180 (2004)
  * Burgarth et al. [2013] Burgarth, D., Chiribella, G., Giovannetti, V., Perinotti, P., Yuasa, K.: Ergodic and mixing quantum channels in finite dimensions. New Journal of Physics 15(7), 073045 (2013)
  * Deschamps et al. [2016] Deschamps, J., Fagnola, F., Sasso, E., Umanita, V.: Structure of uniformly continuous quantum markov semigroups. Reviews in Mathematical Physics 28(01), 1650003 (2016)


# Multi-Player Multi-Armed Bandits with non-zero rewards on collisions for
uncoordinated spectrum access

###### Abstract

In this paper, we study the uncoordinated spectrum access problem using the
multi-player multi-armed bandits framework. We consider a model where there is
no central control and the users cannot communicate with each other. The
environment may appear differently to different users, i.e., the mean rewards
as seen by different users for a particular channel may be different.
Additionally, in case of a collision, we allow for the colliding users to
receive non-zero rewards. With this setup, we present a policy that achieves
expected regret of order $O(\log^{2+\delta}{T})$ for some $\delta>0$.

Index Terms—  multi-armed bandits, uncoordinated spectrum access

##  1 Introduction

Multi-player multi-armed bandit models have been widely used to study the
spectrum access problem [1, 2, 3, 4, 5, 6, 7, 8, 9], where there are multiple
users vying for a set of channels. The users follow a common protocol that is
designed to maximise the system performance. While [6, 8, 9] focus on the
primary/secondary user paradigm for spectrum sharing, we consider a different
system model where there is no such distinction between the users.

In most of the previous work in this area [1, 4, 6], it is assumed that the
reward distribution for each channel is the same across all users. Given that
in a practical scenario, users are not colocated in a wireless network,
assuming that users have different reward distributions for the channels
results in a more realistic model. There has been some prior work covering
varying reward distributions across users [5, 3, 2]. The algorithm presented
in [5] considers such a case with an assumption that each player can observe
what happens on a channel, i.e., if the channel is free or if there is a
collision on it. However such an assumption is unrealistic for the
uncoordinated spectrum access problem. In our work, we consider a fully
distributed scenario where players have access only to their previous actions
and rewards. The work in [3] considers such a setup and uses the method of
forced collisions as a way to communicate the estimated mean rewards between
users in order for them to compute the optimal matching. The work in [2] also
considers such a distributed setting where they use a game-theoretic approach
to solve this problem.

Another assumption prevalent in most previous works is that in the case of a
collision, all the colliding users get zero reward. However, in the case of a
collision in a practical scenario, the colliding users would get a reduced
reward. For instance, if the rate of the channel is the quantity represented
by the rewards, when two users use the same channel they would get reduced,
but not necessarily zero rewards. In [1], a model is studied which allows for
more than one user to access a channel simultaneously and receive non-zero
rewards. However, [1] assumes that the reward distributions for each channel
is the same across all users. In this paper, we consider the case where the
channels may appear differently to the users and the colliding users can
receive non-zero rewards. We present an algorithm that achieves expected
regret of order $O(\log^{2}T)$. To the best of our knowledge, this is the
first work that has considered the case of non-zero rewards on collisions when
the users can see the channels differently. Our work is closest to [2] where
they use a game theoretic approach to maximise the sum of expected rewards of
the users.

##  2 System Model

Consider the set of users $[K]$ to be players in a stochastic game. The action
space of each player $j$ is the set of $M$ channels or arms
$\mathcal{A}_{j}=[M]$. Let the time horizon be denoted by $T$, and the action
taken by player $j$ at time $t\leq T$ be $a_{t,j}$. The strategy
$\mathbf{a}_{t}$ is defined as the vector of the actions taken by the players,
i.e., $\mathbf{a}_{t}=[a_{t,1},...,a_{t,K}]$. At any given time, players can
observe only their own rewards and cannot observe the actions taken by other
players.

In this model, we allow the number of players to be more than the number of
channels and the reward for each arm is bounded in $[0,1]$. Thus, in the event
that more than one user access the same arm $m$, they would get non-zero
rewards. Let the reward obtained by player $j$ at time $t$ where the strategy
is $\mathbf{a}_{t}$ be denoted by $r_{j}({a}_{t,j},k_{t}(a_{t,j}))$, where
$k_{t}(a_{t,j})$ denotes the number of users on the arm $a_{t,j}$. The mean
reward for player $j$ for arm $m$ with $k(m)$ players on the arm is denoted by
$\mu_{j}(m,k(m))$. The mean rewards are inversely proportional to the number
of users on that arm. We assume that $\mu_{j}(m,k(m))$ becomes negligible for
some $k(m)\geq N+1$ where $N$ depends on the system, i.e., $\mu_{j}(m,k(m))=0$
for $k(m)\geq N+1$. Thus the maximum number of players allowed is $MN$

The action space for the players $\mathcal{A}$ is simply the product space of
the individual action spaces, i.e.,
$\mathcal{A}=\Pi_{j=1}^{K}\mathcal{A}_{j}$. Let $\mathbf{a^{*}}\in\mathcal{A}$
be such that

$\mathbf{a^{*}}\in\mathop{\arg\max}_{\mathbf{a}\in\mathcal{A}}\sum_{j=1}^{K}\mu_{j}(a_{j},k(a_{j}))$

In this work, we consider the case where there is a unique optimal matching.
Let $J_{1}=\sum_{j=1}^{K}\mu_{j}(a^{*}_{j},k(a^{*}_{j}))$ be the system reward
for the optimal matching and $J_{2}$ the system reward for the second optimal
matching. In our algorithm we assume that we have access to a lower bound on
the value

$\Delta=\frac{J_{1}-J_{2}}{2MN}$

The expected regret during a time horizon $T$ is defined as:

$R(T)=T\sum_{j=1}^{K}\mu_{j}(a^{*}_{j},k(a^{*}_{j}))-\mathbb{E}\left[\sum_{t=1}^{T}\sum_{j=1}^{K}\mu_{j}(a_{t,j},k_{t}(a_{t,j}))\right]$

where the expectation is over the action profiles of the players.

We assume we have a lower bound on the parameter

$\nu_{min}=\min_{j,m,n_{1},n_{2}}|\mu_{j}(m,n_{1})-\mu_{j}(m,n_{2})|$

where $n_{1},n_{2}\in[N]$, $\mu_{j}(m,n_{1}),\mu_{j}(m,n_{2})\neq 0$,
$j\in[K]$ and $m\in[M]$. Since in our model we allow for more than one user to
occupy a channel with non-zero rewards, such a parameter is needed for a user
to learn with high probability the number of users occupying the channel along
with him based on the reward he gets.

In addition, to estimate the means on each channel as a function of the number
of users, we need to impose some separability condition. We use the following
separability condition considered in [1]:

$|\mu_{j}(m,n_{1})-\mu_{j}(m,n_{2})\geq
4Mc\exp({\frac{K-1}{M-1}})\sqrt{\sigma^{2}+\epsilon_{2}}$

where $j\in[K]$, $m\in[M]$, $n_{1},n_{2}\in[N]$, $\epsilon_{2}\in(0,1)$,
$\sigma^{2}$ is the maximum variance of the reward distributions and $c$ is a
constant.

##  3 Algorithm

In most models for uncoordinated spectrum access, one of the main assumptions
is that on collision, i.e., more than one user accessing the same channel, the
reward received by all the users is zero. However this assumption is not a
very realistic assumption since in such a situation, the colliding users would
get a reduced reward. Since there is no communication possible between
players, on receiving a lower reward than expected, it is necessary to
distinguish whether it is because of other users accessing the same channel or
because of the stochastic nature of the rewards. Previous works such as [3]
and [10], use the method of forced collisions as a way for the users to
communicate their mean rewards to other players. However, the method of forced
collisions is not applicable in this scenario due to the above mentioned
reason. This work is closest to [2] where they use a game-theoretic approach
for the users to take actions (choose arms) to maximise the sum of utilities
(mean rewards) of the players.

Our algorithm, summarized in Algorithm 1, proceeds in epochs with each epoch
having three phases. The first is the exploration phase in which the players
access the channels uniformly in order to estimate the mean rewards of each
channel as a function of the number of users occupying that channel via a
clustering algorithm. In each epoch $\ell$, the exploration phase proceeds for
$T_{0}$ time units.

The second phase of the algorithm, summarized in Algorithm 1, is a strategic
form game where the goal is to maximize the utilities of the players. The
dynamics in this phase are adapted from [11], where they guarantee that the
action profile maximising the sum of utilities is played for a majority of the
time. Each player $j$ is associated with a state
$[\bar{a}_{j},\bar{u}_{j},S_{j}]$ where $\bar{a}_{j}\in[M]$ is the baseline
action of the player, $\bar{u}_{j}\in[0,1]$ is the baseline utility of the
player and $S_{j}\in\\{C,D\\}$ is the mood of the player ($C$ denotes content
and $D$ denotes discontent). The utility of the player denotes the mean reward
of the user for the arm chosen as a function of the number of users on the
channel. This phase proceeds in ’plays’, where each play lasts $c_{\epsilon}$
time units. In each play, every player chooses an action depending on the mood
and baseline action and the arm chosen is played for $c_{\epsilon}$ time
units. The utility of the player for this play is determined according to the
mean of the rewards received in the play. The state of the player is updated
according to the action and utility in the current play. In epoch $\ell$, this
phase proceeds for $c_{2}\ell^{1+\delta}$ plays
($c_{2}c_{\epsilon}\ell^{1+\delta}$ time units). Starting from $d=\lceil\rho
c_{2}\ell^{1+\delta}\rceil$-th play of Algorithm 1, the number of times each
action was played that resulted in being content is counted by each user as

$F_{j}^{\ell}(m)=\sum_{p=d}^{c_{2}c_{\epsilon}\ell^{1+\delta}}\mathbf{1}_{\\{(a_{p,j}=m,S_{j}=C)\\}}$

This maximising action profile is played for $c_{3}2^{\ell}$ time units in the
exploitation phase.

######  Theorem 1.

Given the system model specified in Section 2, the regret of the proposed
algorithm for a time horizon $T$ and some $0<\delta<1$ is
$R(T)=O(\log^{2+\delta}T)$.

###### Proof.

Let $L_{T}$ be the last epoch with time horizon $T$. The regret incurred
during the $L_{T}$ epochs can be analysed as the sum of the regret incurred in
the three stages of the algorithm. From the structure of the algorithm, we
have that $L_{T}<\log{T}$. Let $R_{1}$, $R_{2}$ and $R_{3}$ denote the regret
incurred during the exploration phase, matching phase and exploitation phase
during $L_{T}$ epochs respectively.

  1. 1.

Exploration phase: Since the exploration phase in each epoch $\ell$ proceeds
for $T_{0}$ units

$R_{1}\leq T_{0}L_{T}\leq T_{0}\log T$ (1)

  2. 2.

Matching phase: In epoch $\ell$, the matching phase runs for
$c_{2}c_{\epsilon}\ell^{1+\delta}$ time units. Thus

$\begin{split}R_{2}&=\sum_{\ell=1}^{L_{T}}c_{2}c_{\epsilon}\ell^{1+\delta}\leq
c_{2}c_{\epsilon}L_{T}^{2+\delta}\leq
c_{2}c_{\epsilon}\log^{2+\delta}{T}\end{split}$ (2)

  3. 3.

Exploitation phase: In the exploitation phase, regret is incurred in the
following two events:

    1. (a)

Let $E_{1}$ denote the event that for some user $j$ and channel $m$ and some
$k(m)\in[N]$, we have that
$|\mu_{j}(m,k(m))-\hat{\mu}_{j}(m,k(m))|\geq\Delta$. Let probability of this
event be $P(E_{1})$

    2. (b)

Let $E_{2}$ denote the event that given that all users have
$|\mu_{j}(m,k(m))-\hat{\mu}_{j}(m,k(m))|\leq\Delta$, the action profile chosen
in the matching phase of epoch $\ell$ is not optimal. Let probability of this
event for some epoch $\ell$ be $P^{\ell}(E_{2})$

We have from Theorem 2 of [1] that by choosing an appropriate $T_{0}$, we have
that $P(E_{1})\leq e^{-\ell}$ and from Lemma 3 that $P^{\ell}(E_{2})\leq
C_{\rho}\exp{(-\ell^{1+\delta})}$.

Therefore

$\begin{split}R_{3}&=\sum_{\ell=1}^{L_{T}}c_{3}2^{\ell}(e^{-\ell}+C_{\rho}e^{-\ell^{1+\delta}})\\\
&\leq\sum_{\ell=1}^{L_{T}}c_{3}(1+C_{\rho})(\frac{2}{e})^{\ell}\\\
&\leq\frac{2c_{3}(1+C_{\rho})}{2+e}\end{split}$ (3)

Thus

$\begin{split}R(T)&=R_{1}+R_{2}+R_{3}\\\ &\leq
T_{0}\log{T}+c_{2}c_{\epsilon}\log^{2+\delta}T+\frac{2c_{3}(1+C_{\rho})}{2+e}\\\
&=O(\log^{2+\delta}T)\end{split}$ (4)

∎

Initialization: Set $\hat{\mu}_{j}(m,n)=0$ for all $j\in[K]$, $m\in[M]$ and
$n\in[N]$ and $L_{T}$ as the last epoch with time horizon $T$

for  _$\ell=1,...,L_{T}$_ do

Exploration phase: for  _$t=0$ to $T_{0}$_ do

Choose a channel $m$ uniformly

Append reward to $x(m)$

$\hat{\mu}_{j}(m,1:\beta)$ $\leftarrow$ Cluster $x(m)$ for all $m$

end for

Matching phase: Run Algorithm 2

Starting from $d=\lceil\rho c_{2}\ell^{1+\delta}\rceil$-th turn of Algorithm
2, count the number of times each action was played that resulted in being
content
$F_{j}^{\ell}(m)=\sum_{p=d}^{c_{2}c_{\epsilon}\ell^{1+\delta}}\mathbf{1}_{\\{(a_{p,j}=m,S_{j}=C)\\}}$
Exploitation phase: for $c_{3}2^{\ell}$ time units play
$a_{j}=\mathop{\arg\max}_{m}F_{j}^{\ell}(m)$

end for

Algorithm 1

Initialization: Let $c>MN$.

for  _$t_{1}=1,...,c_{2}\ell^{1+\delta}$_ do

If $S_{j}=C$, action is chosen according to:

$p_{j}^{a_{j}}=\begin{cases}\frac{\epsilon^{c}}{M-1},&\text{if}\
a_{j}\neq\bar{a}_{j}\\\ 1-\epsilon^{c},&\text{if}\
a_{j}=\bar{a}_{j}\end{cases}$ (5) If $S_{j}=D$, action is chosen according to:

$p_{j}^{a_{j}}=\frac{1}{M}\;\;\forall\;a_{j}$

Upon choosing an action $a_{j}$, this arm is sampled for $c_{\epsilon}$ time
units and the average reward received is $\bar{r}_{j}$.

Let

$n^{*}=\mathop{\arg\min}_{n\in[\beta],\hat{\mu}_{j}(a_{j},n)\neq
0}|\bar{r}_{j}-\hat{\mu}_{j}(a_{j},n)|$

The utility of the user is calculated as:

$u_{j}=\hat{\mu}_{j}(a_{j},n^{*})$ The state of the user is updated as
follows:

If $S_{j}=C$ and $[a_{j},u_{j}]=[\bar{a}_{j},\bar{u}_{j}]$, the new state is
the same as the previous

If $S_{j}=C$ and $[a_{j},u_{j}]\neq[\bar{a}_{j},\bar{u}_{j}]$ or $S_{j}=D$,

$[\bar{a}_{j},\bar{u}_{j},C]=\begin{cases}[{a}_{j},{u}_{j},C]&\text{w.p. }\
\epsilon^{1-u_{j}}\\\ [{a}_{j},{u}_{j},D]&\text{w.p. }\
1-\epsilon^{1-u_{j}}\end{cases}$ (6)

end for

Algorithm 2

Run an $\alpha$-approximation for the k-means problem on input $X$, obtain
$\beta$ means $\nu_{1},...,\nu_{\beta}$

$S_{r}\leftarrow\\{i:|x_{i}-\nu_{r}|\leq|x_{i}-\nu_{s}|\text{for every}s\\}$

Return $g(S_{r})=\frac{1}{|S_{r}|}\sum_{i\in S_{r}}x_{i}$

Algorithm 3 Cluster

##  4 Estimation Phase

The exploration phase is required for each player to get estimates of the mean
rewards of each channel as a function of number of users on the channel. This
phase is derived from the estimation phase of [1]. While in [1], the
clustering algorithm is done to estimate the means of each channel when there
is more than one user on the channel, Theorem 2 from [1] holds even if the
clustering algorithm is carried out to estimate the means from $\mu_{j}(m,1)$
to $\mu_{j}(m,N)$. Thus by selecting an appropriate $T_{0}$, we have from
Theorem 2 of [1] that with probability $1-e^{-\ell}$, we have

$|\hat{\mu}_{j}(m,k(m))-{\mu}_{j}(m,k(m))|\leq\Delta$

for epoch $\ell$. This allows us to find the optimal action profile for the
users using the estimates of the mean rewards, as we have from Lemma 1 of [2]
that if the above condition holds, then the optimal action profile chosen
according to the estimates is the same as the optimal action profile chosen
according to the actual mean rewards. While Lemma 1 of [2] represents $J_{2}$
in terms of the mean rewards and collision indicators, it can be seen that the
proof holds even when there aren’t collision indicators present.

##  5 Matching Phase

The aim of Algorithm 2 is for the players to settle on an action profile that
maximises the system reward. The utility of a player $j$ occupying channel
$a_{j}$ with $k(a_{j})$ players on it during some play is defined as

$u^{\prime}_{j}(\mathbf{a})=\hat{\mu}_{j}(a_{j},k(a_{j}))$

However, the player receives only the instantaneous reward and do not know
$k_{t}(a_{t,j})$ in order to determine the utility. Thus, in the matching
phase algorithm, once the users have chosen an action profile, they sample
their chosen arms for $c_{\epsilon}$ time units and the utility is calculated
as the nearest $\hat{\mu}_{j}(m,n),n\in[\beta]$ to the sample mean.

######  Lemma 1.

If
$c_{\epsilon}\geq\lceil\frac{2\ln({\frac{2}{\epsilon^{c}}})}{(\Delta+\nu_{min})^{2}}\rceil$,
we have that

$p_{\epsilon}=P(u_{j}\neq u^{\prime}_{j})\leq\epsilon^{c}$

The proof follows directly from Hoeffding’s inequality.

The dynamics in the Matching Phase are adapted from [11]. The dynamics induce
a Markov chain over the state space
$\mathcal{Z}=\Pi_{j=1}^{K}([M]\times[0,1]\times\mathcal{M})$ where
$\mathcal{M}=\\{C,D\\}$. [11] guarantees that during the matching phase, the
action profile achieving the optimal sum of utilities is played for a majority
of the time. The analysis of [11] relies on the theory of resistance trees for
regular perturbed Markov decision processes [12]. The matching phase of our
algorithm differs in two aspects from [11]. The first is that our strategic
form game is not interdependent. This property is used in [11] only to
characterize the recurrence classes of the unperturbed process ($\epsilon=0$).
However, using the structure of our utilities, we have the following lemma
giving the same recurrence classes as in [11].

######  Lemma 2.

Let $D^{0}$ represent the set of states in which everyone is discontent. Let
$C^{0}$ represent the set of states in which each agent is content and the
benchmark action and utility are aligned. Then the recurrence classes of the
unperturbed process are $D^{0}$ and all singletons $z\in C^{0}$ .

###### Proof.

In the unperturbed process, if all the users are discontent, they remain
discontent with probability $1$. Thus we have that $D^{0}$ represents a single
recurrence class. In each state $z\in C^{0}$, each player chooses the same
action and since the baseline utility and utility are aligned, each user stays
content with probability $1$. Thus we have that $D^{0}$ and singletons $z\in
C^{0}$ are recurrence classes.

To see that the above are the only recurrence classes, look at any state that
has atleast one discontent user and atleast one content user. We have that the
baseline actions and utilities of the content users are aligned (since this is
the unperturbed process). Consider one of the discontent users. This user
chooses an action at random and there is a positive probability (bounded away
from 0) of choosing the action of a content user. This would cause the utility
of the content user to become misaligned thus leading to that player becoming
discontent. This continues until all players become discontent. Thus any such
state cannot be a recurrent state.

Now consider a state where all agents are content, but there is atleast one
user $i$ whose benchmark action and utility are not aligned. for the
unperturbed process, in the following step, the same action profile would be
played but this would cause user $i$ to become discontent and it follows from
the previous argument that this leads to all players becoming discontent.

Thus we have that $D^{0}$ and all singletons in $C^{0}$ are the only recurrent
states of the unperturbed process. ∎

The second way in which our algorithm differs from [11] is that there is a
probability of error $p_{\epsilon}$ in calculating a user’s utility. However,
this can be represented as an $\epsilon$ perturbation by rewriting the state
update step as follows:

If the player is content:

If $[a_{j},u^{\prime}_{j}]=[\bar{a}_{j},\bar{u}_{j}]$, the new state is

$[\bar{a}_{j},\bar{u}_{j},C]\to\begin{cases}[\bar{a}_{j},\bar{u}_{j},C]&\text{w.p.}\
1-p_{\epsilon}\\\ [\bar{a}_{j},{u}_{j},C],&\text{w.p.}\
p_{\epsilon}(\epsilon^{1-u_{j}})\\\ [\bar{a}_{j},{u}_{j},D],&\text{w.p.}\
p_{\epsilon}(1-\epsilon^{1-u_{j}})\end{cases}$ (7)

If $[a_{j},u^{\prime}_{j}]\neq[\bar{a}_{j},\bar{u}_{j}]$, with $q<1$

$[\bar{a}_{j},\bar{u}_{j},C]\to\begin{cases}[\bar{a}_{j},\bar{u}_{j},C]&\text{w.p.}\
qp_{\epsilon}\\\ [{a}_{j},{u}_{j},C],&\text{w.p.}\
(1-qp_{\epsilon})(\epsilon^{1-u_{j}})\\\ [{a}_{j},{u}_{j},D],&\text{w.p.}\
(1-qp_{\epsilon})(1-\epsilon^{1-u_{j}})\end{cases}$ (8)

If player is discontent:

$[\bar{a}_{j},\bar{u}_{j},D]\to\begin{cases}[{a}_{j},{u}_{j},C]&\text{w.p.}\
(1-p_{\epsilon})\epsilon^{1-u_{j}}\\\ [{a}_{j},{u}_{j},D],&\text{w.p.}\
(1-p_{\epsilon})(1-\epsilon^{1-u_{j}})\\\
[{a}_{j},{u}_{j}^{\prime},C],&\text{w.p.}\
p_{\epsilon}\epsilon^{1-u_{j}^{\prime}}\\\
[{a}_{j},{u}_{j}^{\prime},D],&\text{w.p.}\
p_{\epsilon}(1-\epsilon^{1-u_{j}^{\prime}})\end{cases}$ (9)

where we have from Lemma 1 that $p_{\epsilon}\leq\epsilon^{c}$. The second and
third transitions when a player is content and
$[a_{j},u^{\prime}_{j}]=[\bar{a}_{j},\bar{u}_{j}]$ correspond to the case when
$u_{j}\neq u^{\prime}_{j}$. Similarly when the player is content,
$a_{j}=\bar{a}_{j}$ and $u^{\prime}_{j}\neq\bar{u}_{j}$, there is a
possibility where $u^{\prime}_{j}=\bar{u}_{j}$ and the probability of this is
less than $p_{\epsilon}$. The transitions when the player is discontent can be
interpreted similarly. Thus we can see that the unperturbed process, i.e. when
$\epsilon=0$, is the same as the unperturbed process in [11]. And it can be
verified that these dynamics satisfy the conditions for a regular perturbed
markov chain specified in [12].

Let $D$ be any state in $D^{0}$ and $z,z^{\prime}\in c^{0}$. It can be seen
that the resistances for the paths $z\to D$, $D\to z$ amd $z\to z^{\prime}$
are the same as in [11]. For instance, the transition from $z\to D$ occurs
only when a user experiments or the utility is miscalculated. Since we have
$p_{\epsilon}\leq\epsilon^{c}$, the probability of this event is
$O(\epsilon^{c})$ and hence the resistance of the transition is $c$. Similarly
it can be seen that the resistances for the path $D\to z$ is
$(k-\sum_{j\in[K]}\bar{u}_{j})$ and $z\to z^{\prime}$ is bounded in $[c.2c)$.

We have from the Lemma 2 that the recurrent classes of the unperturbed process
are the same as in [11] and the resistances for the paths the same as in [11].
Thus from Theorem 1 of [11], we have that the stochastically stable state is
the one that maximises the sum of utilities of the players and by the
definition of a stochastically stable state, it is the one played a majority
of times in the matching phase. This is utilized by the counting process done
in the matching phase and the action profile played the maximum number of
times is played in the exploitation phase. Thus with high probability, the
action profile maximising the sum of utilities is played in the exploitation
phase.

We bound the probability of the optimal action profile not being played in the
exploitation phase in the following lemma.

######  Lemma 3.

Let
$\mathbf{a}^{*}=\mathop{\arg\max}_{\mathbf{a}\in\mathcal{A}}\sum_{j=1}^{K}\mu_{j}(a_{j},k({a_{j}}))$
and let $\mathbf{a^{\prime}}=[a^{\prime}_{1},...,a^{\prime}_{K}]$ where
$a^{\prime}_{j}=\mathop{\arg\max}_{m\in[M]}F_{j}^{\ell}(m)$ at some epoch
$\ell$. For small enough $\epsilon$, in some epoch $\ell$,
$P(\mathbf{a^{*}}\neq\mathbf{a^{\prime}})\leq
C_{\rho}\exp{(-\ell^{1+\delta})}$ for some $C_{\rho}>0$.

###### Proof.

Let $\mathbf{\bar{u}}$ denote the utilities of the players for the optimal
action profile $\mathbf{a^{*}}$. The optimal state of the markov chain is then
$\mathbf{z^{*}}=[\mathbf{a^{*}},\mathbf{\bar{u}},C^{K}]$. Let the distribution
of the markov chain after the first $d=\lceil\rho c_{2}\ell^{1+\delta}\rceil$
plays be $\phi$. When the system is in state $z$, let the observed state as
seen by the users be $z^{\prime}$. The observed state would differ from the
true state only in the utilities, due to the possibility that some users may
calculate their utility functions incorrectly. The counting process in the
matching phase of some epoch $\ell$ is done for $L=\lfloor
c_{2}(1-\rho)\ell^{(1+\delta)}\rfloor$. In order to bound the probability of
the event $\\{\mathbf{a^{*}}\neq\mathbf{a^{\prime}}\\}$, we use the Chernoff
Hoeffding bounds for markov chains from [13], which is also used in [2]. The
function $f(z)$ considered here is

$f(z)=\mathbf{1}_{\\{z=z^{*},z^{\prime}=z\\}}$

This is the event when the state is in the optimal state and the state is also
observed correctly (i.e. the utilities are observed correctly by all users).
If the optimal state is played for more than $L/2$ plays and the utilities are
calculated correctly by all the users for these plays, then the optimal action
profile would be played in the exploitation phase. Thus we have that

$\begin{split}P(\mathbf{a^{*}}\neq\mathbf{a^{\prime}})&\leq
P(\sum_{\tau=1}^{L}f(z(\tau)))\leq L/2)\\\
&=P(\sum_{\tau=1}^{L}\mathbf{1}_{\\{z(\tau)=z^{*}(\tau),z^{\prime}(\tau)=z(\tau)\\}}\leq
L/2)\end{split}$ (10)

In order to use the bounds in [13], we need $\mathbb{E}\left[f(z)\right]$.
Thus

$\begin{split}\mathbb{E}\left[f(z)\right]&=P({z=z^{*},z^{\prime}=z})\\\
&=P(z=z^{*})P(z^{\prime}=z|z=z^{*})\end{split}$ (11)

We also have that

$\begin{split}P(z^{\prime}\neq
z|z=z^{*})&=P(\cup_{j\in[M]}u_{j}\neq\bar{u}_{j})\\\
&\leq\sum_{j\in[M]}P(u_{j}\neq\bar{u}_{j})\\\ &\leq K\epsilon^{c}\end{split}$
(12)

This gives $\mathbb{E}\left[f(z)\right]=\mu_{f}\geq
P(z=z^{*})(1-K\epsilon^{c})$. And from the definition of a stochastically
stable state, we can choose an $\epsilon$ small enough such that
$P(z=z^{*})(1-K\epsilon^{c})>p>1/2$. Define $\eta=1-\frac{1}{2\mu_{f}}$ so
that $0<\eta<1$ when $\mu_{f}>1/2$. Let $T$ be the $1/8$ mixing time of the
markov chain. Thus from Theorem 3 of [13] we have that

$\begin{split}&P(\sum_{\tau=1}^{L}f(z(\tau))\leq L/2)\\\
&=P(\sum_{\tau=1}^{L}f(z(\tau))\leq(1-\eta)\mu_{f}L)\\\ &\leq
c_{0}||\phi||_{\pi}\exp(-\frac{(1-\frac{1}{2\mu_{f}})^{2}\mu_{f}c_{2}(1-\rho)\ell^{1+\delta}}{72T})\\\
&\leq C_{\rho}\exp{(-\ell^{1+\delta})}\end{split}$ (13)

where $\frac{(1-\frac{1}{2\mu_{f}})^{2}\mu_{f}c_{2}(1-\rho)}{72T}>0$ .

∎

## References

  * [1] M. Bande and V. V. Veeravalli,  “Multi-user multi-armed bandits for uncoordinated spectrum access,”  in 2019 International Conference on Computing, Networking and Communications (ICNC), Feb 2019, pp. 653–657.
  * [2] I. Bistritz and A. Leshem,  “Distributed multi-player bandits - a game of thrones approach,”  in Advances in Neural Information Processing Systems 31, pp. 7222–7232. Curran Associates, Inc., 2018.
  * [3] E. Boursier, V. Perchet, E. Kaufmann, and A. Mehrabian,  “A Practical Algorithm for Multiplayer Bandits when Arm Means Vary Among Players,”  arXiv e-prints, p. arXiv:1902.01239, Feb 2019.
  * [4] J. Rosenski, O. Shamir, and L. Szlak,  “Multi-player bandits: A musical chairs approach,”  in Proceedings of the 33rd International Conference on International Conference on Machine Learning - Volume 48, 2016, pp. 155–163.
  * [5] D. Kalathil, N. Nayyar, and R. Jain,  “Decentralized learning for multi-player multi-armed bandits,”  in 2012 IEEE 51st IEEE Conference on Decision and Control (CDC), Dec 2012, pp. 3960–3965.
  * [6] O. Avner and S. Mannor,  “Concurrent bandits and cognitive radio networks,”  in Proceedings of the 2014th European Conference on Machine Learning and Knowledge Discovery in Databases - Volume Part I, 2014, pp. 66–81.
  * [7] M. Bande and V. V. Veeravalli,  “Adversarial multi-user bandits for uncoordinated spectrum access,”  in ICASSP 2019 - 2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), May 2019, pp. 4514–4518.
  * [8] H. Liu, B. Krishnamachari, and Q. Zhao,  “Cooperation and learning in multiuser opportunistic spectrum access,”  in ICC Workshops - 2008 IEEE International Conference on Communications Workshops, May 2008, pp. 487–492.
  * [9] K. Liu and Q. Zhao,  “Distributed learning in multi-armed bandit with multiple players,”  IEEE Transactions on Signal Processing, vol. 58, no. 11, pp. 5667–5681, Nov 2010.
  * [10] E. Boursier and V. Perchet,  “SIC-MMAB: Synchronisation Involves Communication in Multiplayer Multi-Armed Bandits,”  arXiv e-prints, p. arXiv:1809.08151, Sep 2018.
  * [11] J.R. Marden, H.P.. Young, and L. Y. Pao,  “Achieving pareto optimality through distributed learning,”  SIAM Journal on Control and Optimization, vol. 52, no. 5, pp. 2753–2770, 2014.
  * [12] H. P. Young,  “The evolution of conventions,”  Econometrica, vol. 61, no. 1, pp. 57–84, 1993.
  * [13] K. Chung, H. Lam, Z. Liu, and M. Mitzenmacher,  “Chernoff-Hoeffding Bounds for Markov Chains: Generalized and Simplified,”  in STACS’12 (29th Symposium on Theoretical Aspects of Computer Science), Feb. 2012, vol. 14, pp. 124–135.


* van Nieuwkerk  _et al._ [2021] Y. D. van Nieuwkerk, J. Schmiedmayer, and F. H. L. Essler, Josephson oscillations in split one-dimensional Bose gases, SciPost Phys. 10, 090 (2021).
  * Mennemann  _et al._ [2021] J.-F. Mennemann, I. E. Mazets, M. Pigneur, H. P. Stimming, N. J. Mauser, J. Schmiedmayer, and S. Erne, Relaxation in an extended bosonic Josephson junction, Phys. Rev. Res. 3, 023197 (2021).
  * Berry [1983] M. Berry, Semiclassical mechanics of regular and irregular motion, in  _Chaotic behaviour of deterministic systems (Les Houches Session XXXVI)_, edited by G. Iooss, R. H. G. Helleman, and R. Stora (North-Holland Publishing, Amsterdam, 1983).
  * Miller [2007] R. B. P. D. Miller, Exact solutions of semiclassical non-characteristic Cauchy problems for the sine-Gordon equation,  (2007), arXiv:0705.3159 [nlin.SI] .
  * Paredes  _et al._ [2004] B. Paredes, A. Widera, V. Murg, O. Mandel, S. Fölling, I. Cirac, G. V. Shlyapnikov, T. W. Hänsch, and I. Bloch, Tonks–Girardeau gas of ultracold atoms in an optical lattice, Nature 429, 277 (2004).
  * Kinoshita  _et al._ [2004] T. Kinoshita, T. Wenger, and D. S. Weiss, Observation of a one-dimensional Tonks-Girardeau gas, Science 305, 1125 (2004).
  * Esteve  _et al._ [2006] J. Esteve, J.-B. Trebbia, T. Schumm, A. Aspect, C. I. Westbrook, and I. Bouchoule, Observations of density fluctuations in an elongated Bose gas: Ideal gas and quasicondensate regimes, Phys. Rev. Lett. 96, 130403 (2006).
  * Hofferberth  _et al._ [2008] S. Hofferberth, I. Lesanovsky, T. Schumm, A. Imambekov, V. Gritsev, E. Demler, and J. Schmiedmayer, Probing quantum and thermal noise in an interacting many-body system, Nature Phys. 4, 489 (2008).
  * Schley  _et al._ [2013] R. Schley, A. Berkovitz, S. Rinott, I. Shammass, A. Blumkin, and J. Steinhauer, Planck distribution of phonons in a Bose-Einstein condensate, Phys. Rev. Lett. 111, 055301 (2013).
  * fan [2016] Momentum-space correlations of a one-dimensional Bose gas, Phys. Rev. Lett. 116, 050402 (2016).
  * Jacqmin  _et al._ [2011] T. Jacqmin, J. Armijo, T. Berrada, K. V. Kheruntsyan, and I. Bouchoule, Sub-Poissonian fluctuations in a 1D Bose gas: From the quantum quasicondensate to the strongly interacting regime, Phys. Rev. Lett. 106, 230405 (2011).
  * Schemmer  _et al._ [2019] M. Schemmer, I. Bouchoule, B. Doyon, and J. Dubail, Generalized hydrodynamics on an atom chip, Phys. Rev. Lett. 122, 090601 (2019).
  * Mermin and Wagner [1966] N. D. Mermin and H. Wagner, Absence of ferromagnetism or antiferromagnetism in one- or two-dimensional isotropic Heisenberg models, Phys. Rev. Lett. 17, 1133 (1966).
  * Petrov  _et al._ [2000] D. S. Petrov, G. V. Shlyapnikov, and J. T. M. Walraven, Regimes of quantum degeneracy in trapped 1d gases, Phys. Rev. Lett. 85, 3745–3749 (2000).
  * Kheruntsyan  _et al._ [2003] K. Kheruntsyan, D. Gangardt, P. Drummond, and G. Shlyapnikov, Pair correlations in a finite-temperature 1D Bose gas, Phys. Rev. Lett. 91, 040403 (2003).
  * Betz  _et al._ [2011] T. Betz, S. Manz, R. Bücker, T. Berrada, C. Koller, G. Kazakov, I. E. Mazets, H.-P. Stimming, A. Perrin, T. Schumm, and J. Schmiedmayer, Two-point phase correlations of a one-dimensional bosonic Josephson junction, Phys. Rev. Lett. 106, 020407 (2011).
  * Gring  _et al._ [2012] M. Gring, M. Kuhnert, T. Langen, T. Kitagawa, B. Rauer, M. Schreitl, I. Mazets, D. A. Smith, E. Demler, and J. Schmiedmayer, Relaxation and prethermalization in an isolated quantum system, Science 337, 1318–1322 (2012).
  * Langen  _et al._ [2013] T. Langen, R. Geiger, M. Kuhnert, B. Rauer, and J. Schmiedmayer, Local emergence of thermal correlations in an isolated quantum many-body system, Nature Physics 9, 640–643 (2013).
  * Schweigler  _et al._ [2017] T. Schweigler, V. Kasper, S. Erne, I. Mazets, B. Rauer, F. Cataldini, T. Langen, T. Gasenzer, J. Berges, and J. Schmiedmayer, Experimental characterization of a quantum many-body system via higher-order correlations, Nature 545, 323–326 (2017).
  * Langen  _et al._ [2018] T. Langen, T. Schweigler, E. Demler, and J. Schmiedmayer, Double light-cone dynamics establish thermal states in integrable 1D Bose gases, New Journal of Physics 20, 023034 (2018).
  * Rauer  _et al._ [2018] B. Rauer, S. Erne, T. Schweigler, F. Cataldini, M. Tajik, and J. Schmiedmayer, Recurrences in an isolated quantum many-body system, Science 360, 307 (2018).
  * Pigneur  _et al._ [2018] M. Pigneur, T. Berrada, M. Bonneau, T. Schumm, E. Demler, and J. Schmiedmayer, Relaxation to a phase-locked equilibrium state in a one-dimensional bosonic Josephson junction, Phys. Rev. Lett. 120, 173601 (2018).
  * Estève  _et al._ [2008] J. Estève, C. Gross, A. Weller, S. Giovanazzi, and M. K. Oberthaler, Squeezing and entanglement in a Bose–Einstein condensate, Nature 455, 1216 (2008).
  * Berrada  _et al._ [2013] T. Berrada, S. V. Frank, R. Bücker, T. Schumm, J.-F. Schaff, and J. Schmiedmayer, Integrated Mach–Zehnder interferometer for Bose–Einstein condensates, Nat. Comm. 4 (2013).
  * Andrews  _et al._ [1997] M. R. Andrews, C. G. Townsend, H.-J. Miesner, D. M. Durfee, D. S. Kurn, and W. Ketterle, Observation of interference between two Bose condensates, Science 275, 637 (1997).
  * Castin and Dalibard [1997] Y. Castin and J. Dalibard, Relative phase of two Bose-Einstein condensates, Phys. Rev. A 55, 4330 (1997).
  * Pethick and Smith [2002] C. J. Pethick and H. Smith, Bose-Einstein condensation in dilute gases (Cambridge University Press, Cambridge, UK, 2002) pp. 343–348.
  * Zapata  _et al._ [2003] I. Zapata, F. Sols, and A. J. Leggett, Phase dynamics after connection of two separate Bose-Einstein condensates, Phys. Rev. A 67, 021603(R) (2003).
  * Milburn  _et al._ [1997] G. J. Milburn, J. Corney, E. M. Wright, and D. F. Walls, Quantum dynamics of an atomic Bose-Einstein condensate in a double-well potential, Phys. Rev. A 55, 4318 (1997).
  * Tuchman  _et al._ [2006] A. K. Tuchman, C. Orzel, A. Polkovnikov, and M. A. Kasevich, Nonequilibrium coherence dynamics of a soft boson lattice, Phys. Rev. A 74, 051601(R) (2006).
  * Chuchem  _et al._ [2010] M. Chuchem, K. Smith-Mannschott, M. Hiller, T. Kottos, A. Vardi, and D. Cohen, Quantum dynamics in the bosonic Josephson junction, Phys. Rev. A 82, 053617 (2010).
  * Drummond and Hardman [1993] P. D. Drummond and A. D. Hardman, Simulation of quantum effects in Raman-active waveguides, Europhys. Lett. 21, 279 (1993).
  * Sinatra  _et al._ [2002] A. Sinatra, C. Lobo, and Y. Castin, The truncated Wigner method for Bose-condensed gases: limits of validity and applications, J. Phys. B 35, 3599 (2002).
  * Blakie  _et al._ [2008] P. B. Blakie, A. S. Bradley, M. J. Davis, R. J. Ballagh, and C. W. Gardiner, Dynamics and statistical mechanics of ultra-cold Bose gases using c-field techniques, Adv. Phys. 57, 363 (2008).
  * Polkovnikov [2010] A. Polkovnikov, Phase space representation of quantum dynamics, Ann. Phys. 325, 1790 (2010).
  * Ruostekoski and Isella [2005] J. Ruostekoski and L. Isella, Dissipative quantum dynamics of bosonic atoms in a shallow 1d optical lattice, Phys. Rev. Lett. 95, 110403 (2005).
  * Javanainen and Ruostekoski [2013] J. Javanainen and J. Ruostekoski, Emergent classicality in continuous quantum measurements, New J. Phys. 15, 013005 (2013).
  * Martin and Ruostekoski [2010a] A. D. Martin and J. Ruostekoski, Quantum and thermal effects of dark solitons in a one-dimensional Bose gas, Phys. Rev. Lett. 104, 194102 (2010a).
  * Martin and Ruostekoski [2010b] A. D. Martin and J. Ruostekoski, Nonequilibrium quantum dynamics of atomic dark solitons, New J. Phys. 12, 055018 (2010b).
  * Horváth  _et al._ [2019] D. X. Horváth, I. Lovas, M. Kormos, G. Takács, and G. Zaránd, Nonequilibrium time evolution and rephasing in the quantum sine-Gordon model, Phys. Rev. A 100, 013613 (2019).
  * Rigol  _et al._ [2008] M. Rigol, V. Dunjko, and M. Olshanii, Thermalization and its mechanism for generic isolated quantum systems, Nature 452, 854 (2008).
  * D’Alessio  _et al._ [2016] L. D’Alessio, Y. Kafri, A. Polkovnikov, and M. Rigol, From quantum chaos and eigenstate thermalization to statistical mechanics and thermodynamics, Adv.Phys. 65, 239 (2016).
  * Žnidarič  _et al._ [2010] M. Žnidarič, T. Prosen, G. Benenti, G. Casati, and D. Rossini, Thermalization and ergodicity in one-dimensional many-body open quantum systems, Physical Review E 81, 051135 (2010).
  * Purkayastha  _et al._ [2016] A. Purkayastha, A. Dhar, and M. Kulkarni, Out-of-equilibrium open quantum systems: A comparison of approximate quantum master equation approaches with exact results, Physical Review A 93, 062114 (2016).
  * Reichental  _et al._ [2018] I. Reichental, A. Klempner, Y. Kafri, and D. Podolsky, Thermalization in open quantum systems, Physical Review B 97, 134301 (2018).
  * Tupkary  _et al._ [2022] D. Tupkary, A. Dhar, M. Kulkarni, and A. Purkayastha, Fundamental limitations in lindblad descriptions of systems weakly coupled to baths, Physical Review A 105, 032208 (2022).
  * Nathan and Rudner [2020] F. Nathan and M. S. Rudner, Universal lindblad equation for open quantum systems, Physical Review B 102, 115109 (2020).
  * Tupkary  _et al._ [2023] D. Tupkary, A. Dhar, M. Kulkarni, and A. Purkayastha, Searching for lindbladians obeying local conservation laws and showing thermalization, arXiv preprint arXiv:2301.02146 (2023).
  * Navon  _et al._ [2021] N. Navon, R. P. Smith, and Z. Hadzibabic, Quantum gases in optical boxes, Nat. Phys. 17, 1334 (2021).
  * Olshanii [1998] M. Olshanii, Atomic scattering in the presence of an external confinement and a gas of impenetrable bosons, Phys. Rev. Lett. 81, 938 (1998).
  * Sadler  _et al._ [2006] L. E. Sadler, J. M. Higbie, S. R. Leslie, M. Vengalattore, and D. M. Stamper-Kurn, Spontaneous symmetry breaking in a quenched ferromagnetic spinor Bose–Einstein condensate,  443, 312 (2006).
  * Zibold  _et al._ [2010] T. Zibold, E. Nicklas, C. Gross, and M. K. Oberthaler, Classicial bifurcation at the transition from Rabi to Josephson dynamics, Phys. Rev. Lett. 105, 204101 (2010).
  * Dalfovo  _et al._ [1999] F. Dalfovo, S. Giorgini, L. P. Pitaevskii, and S. Stringari, Theory of Bose-Einstein condensation in trapped gases, Rev. Mod. Phys. 71, 463 (1999).
  * Sinatra  _et al._ [2001] A. Sinatra, C. Lobo, and Y. Castin, Classical-field method for time dependent Bose-Einstein condensed gases, Phys. Rev. Lett. 87, 210404 (2001).
  * Mora and Castin [2003] C. Mora and Y. Castin, Extension of Bogoliubov theory to quasicondensates, Phys. Rev. A 67, 053615 (2003).
  * Smerzi  _et al._ [1997] A. Smerzi, S. Fantoni, S. Giovanazzi, and S. R. Shenoy, Quantum coherent atomic tunneling between two trapped Bose-Einstein condensates, Phys. Rev. Lett. 79, 4950 (1997).
  * Fermi  _et al._ [1955] E. Fermi, J. Pasta, S. Ulam, and M. Tsingou, Studies of nonlinear problems (1955), Document LA-1940, Los Alamos National Laboratory.
  * Egorov  _et al._ [2013] M. Egorov, B. Opanchuk, P. Drummond, B. V. Hall, P. Hannaford, and A. I. Sidorov, Measurement of $s$-wave scattering lengths in a two-component Bose-Einstein condensate, Phys. Rev. A 87, 053614 (2013).
  * Rackauckas and Nie [2017] C. Rackauckas and Q. Nie, Differentialequations.jl–a performant and feature-rich ecosystem for solving differential equations in julia, Journal of Open Research Software 5 (2017).
  * Pitaevskii and Stringari [2003] L. P. Pitaevskii and S. Stringari,  _Bose-Einstein Condensation_ (Oxford University, New York, 2003).
  * Cheneau  _et al._ [2012] M. Cheneau, P. Barmettler, D. Poletti, M. Endres, P. Schauß, T. Fukuhara, C. Gross, I. Bloch, C. Kollath, and S. Kuhr, Light-cone-like spreading of correlations in a quantum many-body system, Nature 481, 484 (2012).
  * Karl  _et al._ [2017] M. Karl, H. Cakir, J. C. Halimeh, M. K. Oberthaler, M. Kastner, and T. Gasenzer, Universal equilibrium scaling functions at short times after a quench, Phys. Rev. E 96, 022110 (2017).
  * de Nova  _et al._ [2019] J. R. M. de Nova, K. Golubkov, V. I. Kolobov, and J. Steinhauer, Observation of thermal Hawking radiation and its temperature in an analogue black hole, Nature 569, 688 (2019).
  * Arnold [1997] V. I. Arnold,  _Mathematical Methods of Classical Mechanics_ (Springer, New York, 1997).
  * Wittmann W.  _et al._ [2022] K. Wittmann W., E. R. Castro, A. Foerster, and L. F. Santos, Interacting bosons in a triple well: Preface of many-body quantum chaos, Phys. Rev. E 105, 034204 (2022).
  * Brandino  _et al._ [2015] G. P. Brandino, J.-S. Caux, and R. M. Konik, Glimmers of a quantum kam theorem: Insights from quantum quenches in one-dimensional bose gases, Phys. Rev. X 5, 041043 (2015).
  * Olver et al. [2010] Olver et al., ed.,  _NIST Handbook of Mathematical Functions_ (Cambridge University Press, New York, 2010) available online at dlmf.nist.gov.
  * O’Dell [1999] D. H. J. O’Dell,  _The diffraction of atoms by light_ , Ph.D. thesis, University of Bristol (1999).
  * Berry and O’Dell [1999] M. V. Berry and D. H. J. O’Dell, Ergodicity in wave-wave diffraction, J. Phys. A: Math. 32, 3571 (1999).