# Decision theoretic bootstrapping

Peyman Tavallali1,∗, Hamed Hamze Bajgiran2, Danial J. Esaid3, Houman Owhadi2,∗

###### Abstract.

The design and testing of supervised machine learning models combine two
fundamental distributions: (1) the training data distribution (2) the testing
data distribution. Although these two distributions are identical and
identifiable when the data set is infinite; they are imperfectly known (and
possibly distinct) when the data is finite (and possibly corrupted) and this
uncertainty must be taken into account for robust Uncertainty Quantification
(UQ). We present a general decision-theoretic bootstrapping solution to this
problem: (1) partition the available data into a training subset and a UQ
subset (2) take $m$ subsampled subsets of the training set and train $m$
models (3) partition the UQ set into $n$ sorted subsets and take a random
fraction of them to define $n$ corresponding empirical distributions $\mu_{j}$
(4) consider the adversarial game where Player I selects a model
$i\in\left\\{1,\ldots,m\right\\}$, Player II selects the UQ distribution
$\mu_{j}$ and Player I receives a loss defined by evaluating the model $i$
against data points sampled from $\mu_{j}$ (5) identify optimal mixed
strategies (probability distributions over models and UQ distributions) for
both players. These randomized optimal mixed strategies provide optimal model
mixtures and UQ estimates given the adversarial uncertainty of the training
and testing distributions represented by the game. The proposed approach
provides (1) some degree of robustness to distributional shift in both the
distribution of training data and that of the testing data (2) conditional
probability distributions on the output space forming aleatory representations
of the uncertainty on the output as a function of the input variable.

1Jet Propulsion Laboratory, California Institute of Technology, Pasadena, CA
91109

2California Institute of Technology, Pasadena, CA 91125

3Jet Propulsion Laboratory, California Institute of Technology, Pasadena, CA
91109; University of California, Riverside, 92521

∗Corresponding Author, E-mails<EMAIL_ADDRESS><EMAIL_ADDRESS>
© 2021\. California Institute of Technology. Government sponsorship
acknowledged.

##  1\. Introduction

Although traditional cross validation (CV) provides model UQ/error estimates
[64, 65, 2, 21, 67], these estimates are in general not robust to distribution
shifts. We propose to incorporate the impact of distributional uncertainty in
the adversarial setting of decision theory (DT) [47].

Figure 1. Train-UQ Partitioning of the Data. The _left plot_ shows the
schematic partitioning of the original empirical data into two exclusive train
and UQ sets. The _middle plot_ shows how the train set is used to train $m$ ML
estimators (randomly). Here, the training sets are found by subsampling the
train dataset $m$ times. The _right plot_ shows the procedure of breaking up
the UQ set into $n$ subsets, from which $n$ different empirical distributions
can be extracted.

###  1.1. Main Result:

Our proposed decision theoretic bootstrapping (DTB) solution is to:

  * •

randomly partition the available data
$\left\\{\left(X_{i},Y_{i}\right)\right\\}_{i\in\mathcal{I}}$ into a training
subset $\left\\{\left(X_{i},Y_{i}\right)\right\\}_{i\in\mathcal{T}}$ and a UQ
subset $\left\\{\left(X_{i},Y_{i}\right)\right\\}_{i\in\mathcal{U}}$ (see
Figure 1-a);

  * •

randomly subsample the training set $\mathcal{T}$ into $m$ subsets
$\left\\{\mathcal{T}_{i}\right\\}_{i=1}^{m}$, and train $m$ models
$\left\\{F_{i}\right\\}_{i=1}^{m}$ (see Figure 1-b);

  * •

For $k\in\\{1,\ldots,K\\}$ repeat the following steps.

  * •

Partition the UQ set into $n$ sorted subsets.

    * –

Randomly subsample from all the $n$ sorted subsets of $\mathcal{U}$ and define
$n$ corresponding empirical distributions $\left\\{\mu_{j}\right\\}_{j=1}^{n}$
(see Figure 1-b);

    * –

consider the zero-sum adversarial game where Player I selects a model $F_{i}$,
Player II selects the UQ distribution $\mu_{j}$, and Player I receives a
random loss defined as the empirical risk

$\mathcal{L}_{ij}=\mathbb{E}_{(X,Y)\sim\mu_{j}}\mathcal{E}\left(Y,F_{i}\left(X\right)\right),$
(1.1)

where $\mathcal{E}$ is an error function. The diagram of the proposed game is
as follows.

(Player
I)$\textstyle{F_{i}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\min}$$\textstyle{\mu_{j}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\max}$(Player
II)$\textstyle{\mathcal{L}_{ij}}$

    * –

identify and record the optimal mixed strategies (probability distributions)
$\boldsymbol{p}^{(k)}=\left(p_{1}^{(k)},\ldots,p_{m}^{(k)}\right)$ over models
$\left\\{F_{i}\right\\}_{i=1}^{m}$ and
$\boldsymbol{q}^{(k)}=\left(q_{1}^{(k)},\ldots,q_{n}^{(k)}\right)$ over UQ
distributions $\left\\{\mu_{j}\right\\}_{j=1}^{n}$, for both players by
solving the minimax problem

$\begin{array}[]{c}\underset{\boldsymbol{p}}{\min}\,\underset{\boldsymbol{q}}{\max}\sum_{i,j}p_{i}\mathcal{L}_{ij}q_{j}\end{array}.$
(1.2)

and record the value $v^{(k)}$ of the game (1.2).

  * •

Use the distribution of the $p^{(k)}$ and possibly $v^{(k)}$ for UQ analysis.

###  1.2. Structure of the paper:

The proposed methodology and algorithm is described in Section 2. In Section
3, we discuss the relevance of DTB to CV. We then present two detailed
examples in Section 4. We cover related works in 5 and compare the proposed
method with other UQ for ML methods in the literature.

##  2\. DTB Methodology and Algorithm

In any modeling endeavor, there are three major questions: “ _How can the
uncertainty be quantified?_ ”, “ _How robust is a given model if the
distribution of the testing data is distinct from that of training data?_ ”,
and finally, “ _How can we pick amongst many trained models?_ ”. This
manuscript presents a decision-theoretic (zero-sum game) framework answering
all three questions. We will now motivate these questions and illustrate DTB
with the following real-world problem.

######  Example 1.

Given the California housing dataset (that includes ZIP codes, square footage,
number of bedroom and bathrooms, sales prices, etc.) [52], and $20$ ML models
(e.g., regression trees) trained on distinct subsets of this dataset, (1)
predict sales prices for a new test set (that includes the previous features
but not sales prices), (2) provide confidence intervals for each prediction,
(3) establish the robustness of the predictions to distributional shift
between training and testing data. Although selecting the model with the
lowest error in the training set is a natural solution to (1), the
deterministic nature of this solution is in conflict with the requirements of
(2) providing confidence intervals and (3) ensuring robustness to
distributional shifts. Similarly, although using training errors to create a
weighted ranking of the $20$ models could be used to provide confidence
intervals, it does not ensure robustness to distribution shifts. With the
proposed approach, we estimate the error of one of these $20$ models (selected
at random by Player I) against an empirical distribution (selected at random
by player II). The randomization of the underlying game provides confidence
intervals, and its adversarial nature ensures robustness to distribution
shifts. Figure 2 illustrates DTB. For that figure, we trained $m=20$ different
regression tree models (each with a maximum depth of $15$) on a train set with
$|\mathcal{T}|=13759$ samples, then exposed those models to $n=100$ unseen
randomized realizations of a UQ set (with $|\mathcal{U}|=6777$ samples) to
find each model’s probability, and finally applied them to a left-out test set
with $104$ samples. We chose a small test set to accentuate uncertainties for
ease of presentation. Each model is trained on a random half of the training
set ($|F_{i}|\approx|\mathcal{T}|/2$). The sorted unseen randomized
realizations of the UQ set are divided into $n=100$ subsets. The combined
support of the $\mu_{j}$ in each randomization encompasses roughly $20\%$ of
the whole UQ set. The _prediction distribution_ $p_{i}$ over the $20$ models
is calculated based on material presented in Section 3.2. For each $104$
sample in the left-out test set, Figure 2 shows the mean prediction (obtained
by averaging the prediction of each model with respect to the distribution
$p_{i}$) and the standard deviation of that prediction (with respect to the
distribution $p_{i}$). As can be seen from this figure, almost all ground
truth values over the test set fall in between the confidence bounds of the
predictions (note that we used one standard deviation to define confidence
intervals).

###  2.1. Setup

The supervised ML setting is that of approximating an unknown function
$F^{\dagger}$ given $F^{\dagger}(X_{i})=Y_{i}$ for all $i$ where
$\left\\{\left(X_{i},Y_{i}\right)\right\\}_{i\in\mathcal{I}}$ represents the
available input/output training data. One major issue with solving this
problem as a regression/interpolation (curve fitting) problem is that the
interpolant does not carry an intrinsic measure of uncertainty (even if it has
been obtained as a conditional expectation by conditioning a Gaussian prior
[57], then the conditional covariance of the posterior distribution depends on
the covariance function of the Gaussian prior whose selection is to some
degree arbitrary). Furthermore, this approach is not stable to distribution
shifts, especially in deep neural networks case [46]. A partial remedy is to
use CV to ensure that the training and generalization errors are close [64,
65, 2, 21, 67]. However, CV does not address the distribution shift problem
and it does not provide a pointwise (input dependent) prediction confidence
intervals. Although there are methods that provide a stable linear regression
mitigating the effects of distribution shifts by a relaxed minimax approach
[4], yet these methods do not provide a pointwise prediction confidence
interval. Contrary to these, our proposed solution, based on decision theory
[47], is to formulate the underlying regression problem (linear or non-linear)
as a zero-sum adversarial game over the set of possible machine learning (ML)
models and empirical data distributions providing both robustness of
estimation and prediction confidence intervals. To do so, the modeler must
provide a set of fitting functions
$\left\\{F_{i}\left(X\right)\right\\}_{i=1}^{m}$ and play an adversarial zero-
sum game against some random empirical distributions of the data. In what
follows, we present a detailed description of each step.

Figure 2. Robust Prediction with Confidence Intervals. This plot shows that on
a random test set from the California Housing dataset [52], the predictions of
$20$ different regression trees are robust in the sense that their confidence
intervals include the ground truth. There are only a few large confidence
intervals, and the rest are relatively tight. This plot is showing the value
of double randomization, both over the empirical distributions and the models.
The latter is one of the main ideas of the adversarial game-theoretic setup of
DTB.

###  2.2. Partitioning the training data:

Our first step is to randomly partition the available (training) data
$\left\\{\left(X_{i},Y_{i}\right)\right\\}_{i\in\mathcal{I}}$ into two
mutually exclusive sets: a training set
$\left\\{\left(X_{i},Y_{i}\right)\right\\}_{i\in\mathcal{T}}$ and a UQ set
$\left\\{\left(X_{i},Y_{i}\right)\right\\}_{i\in\mathcal{U}}$.

###  2.3. Training models:

Next, we subsample $m$ subsets of the training set $\mathcal{T}$. We write
$\left\\{\mathcal{T}_{i}\right\\}_{i=1}^{m}$ for these subsets and train $m$
corresponding models $\left\\{F_{i}\right\\}_{i=1}^{m}$ ($F_{i}$ is the model
obtained by using $\mathcal{T}_{i}$ as training data). The training pipeline
can be arbitrary (e.g., the corresponding models could be deep neural networks
[22], random forests [7, 28], or any other ML model). Therefore, there is no
constraint in the selection of the model producing pipeline and any function
estimator, relevant to the problem at hand, and any training methodology could
be used. Even the class of these functions could be different across
$i\in\\{1,\ldots,m\\}$. For example, some could be linear regression models
(for some labels $i$), some decision trees [8] (for the other labels) and some
support vector machines [9] (for the remaining labels).

###  2.4. Bootstrapping a set of empirical distributions:

Next, we sort $\mathcal{U}$ with respect to the response variable $Y$ and then
partition this sorted set into $n$ subsets
$\left\\{\mathcal{U}_{j}\right\\}_{j=1}^{n}$. Then, we randomly subsample the
sorted set $\left\\{\left(X_{i},Y_{i}\right)\right\\}_{i\in\mathcal{U}}$ from
the $n$ subsets $\left\\{\mathcal{U}_{j}\right\\}_{j=1}^{n}$ and define $n$
corresponding empirical distributions

$\mu_{j}\coloneqq\frac{1}{\left|\mathcal{U}_{j}\right|}\sum_{j\in\mathcal{U}_{j}}\updelta\left(X_{j},Y_{j}\right).$
(2.1)

####  2.4.1. Deterministic Game:

Consider the game in which Player I selects an element from
$\left\\{F_{i}\right\\}_{i=1}^{m}$ and Player II selects an element from
$\left\\{\mu_{j}\right\\}_{j=1}^{n}$ (defined as in (2.1)). Let

$\mathcal{L}_{ij}=\mathbb{E}_{(X,Y)\sim\mu_{j}}\big{[}\mathcal{E}(Y,F_{i}(X))\big{]}$
(2.2)

be the loss function for this game. In that deterministic setting the optimal
mixed strategies of Player I and II tends to concentrate on single elements,
i.e., the worst distribution in $\left\\{\mu_{j}\right\\}_{j=1}^{n}$ and its
best response in $\left\\{F_{i}\right\\}_{i=1}^{m}$. This is due to the fact
that, although this game incorporates some degree of uncertainty in the
selection of the data generating distribution, it does not incorporate the
uncertainty associated with sampling from that distribution. To address this
issue, we repeat the proposed game over many random realizations of the
$\mu_{j}$ and use the resulting distribution over optimal mixed strategies for
our UQ analysis.

###  2.5. Randomized Game:

Consider the game described in Subsection 2.4.1 and observe that the
randomized sampling process generating the $\mu_{j}$ induces a randomization
of the loss metric $\mathcal{L}$ ($\mathcal{L}_{ij}$ a random function of
$(i,j)$). Assigning probabilities
$\boldsymbol{p}=\left(p_{1},\ldots,p_{m}\right)$ over models
$\left\\{F_{i}\right\\}_{i=1}^{m}$ and
$\boldsymbol{q}=\left(q_{1},\ldots,q_{n}\right)$ over a specific realization
of $\left\\{\mu_{j}\right\\}_{j=1}^{n}$, optimal mixed strategies
$(p^{\dagger},q^{\dagger})$ are identified as solutions of the minimax problem

$\begin{array}[]{c}\underset{\boldsymbol{p}}{\min}\,\underset{\boldsymbol{q}}{\max}\sum_{i,j}p_{i}\mathcal{L}_{ij}q_{j}\end{array},$
(2.3)

Note that the randomization of the loss $\mathcal{L}$ implies that
$(\boldsymbol{p}^{\dagger},\boldsymbol{q}^{\dagger})$ are random
distributions. We will now sample from these distributions by solving (2.3)
many times (with different random realizations of $\mathcal{L}$). This
approach is directly related to Harsanyi’s purification over repeated games
[26].

###  2.6. Probability distributions over models:

Given $K\geq 1$, let $(\boldsymbol{p}^{(k)},\boldsymbol{q}^{(k)})$ be $K$
i.i.d. samples from $(\boldsymbol{p}^{\dagger},\boldsymbol{q}^{\dagger})$ and
write $v^{(k)}$ for the corresponding random values of (2.3). Note that the
$(\boldsymbol{p}^{(k)},\boldsymbol{q}^{(k)})$ are obtained by solving (2.3)
over $K$ independent realizations of the loss $\mathcal{L}$. We record each
optimal $\boldsymbol{p}^{\left(k\right)}$, each value $v^{(k)}$, and use the
histogram defined by the $v^{(k)}$ and the empirical average

$\bar{\boldsymbol{p}}=\frac{1}{K}\sum_{k=1}^{K}\boldsymbol{p}^{\left(k\right)}\,,$
(2.4)

for UQ. From an ML perspective, this approach is robust to distribution
shifts. This procedure is presented in Algorithm 1.

  1. (1)

Randomly separate
$\left\\{\left(X_{i},Y_{i}\right)\right\\}_{i\in\mathcal{I}}$ into mutually
exclusive sets $\left\\{\left(X_{i},Y_{i}\right)\right\\}_{i\in\mathcal{T}}$
and $\left\\{\left(X_{i},Y_{i}\right)\right\\}_{i\in\mathcal{U}}$.

  2. (2)

Generate $m$ randomly subsampled subsets
$\left\\{\mathcal{T}_{i}\right\\}_{i=1}^{m}$ of the training set
$\mathcal{T}$.

    1. (a)

Train the models $F_{i}$ on the subsets $\mathcal{T}_{i}$.

  3. (3)

Sort $\mathcal{U}$ with respect to the response variable $Y$ and then
partition into $n$ subsets $\left\\{\mathcal{U}_{j}\right\\}_{j=1}^{n}$.

  4. (4)

For $k\in\left\\{1,\ldots,K\right\\}$

    1. (a)

Generate $n$ randomly subsampled subsets
$\left\\{\mathcal{U}_{j}^{(k)}\right\\}_{j=1}^{n}$ from
$\left\\{\mathcal{U}_{j}\right\\}_{j=1}^{n}$ write
$\left\\{\mathcal{\mu}_{j}^{(k)}\right\\}_{j=1}^{n}$ for the corresponding
empirical distributions.

    2. (b)

Solve the minimax problem
$\begin{array}[]{c}\underset{\boldsymbol{p}}{\min}\,\underset{\boldsymbol{q}}{\max}\sum_{i,j}p_{i}\mathcal{L}_{ij}q_{j}\end{array}$,
and record the optimal $\boldsymbol{p}^{\left(k\right)}$ and the value
$v^{(k)}$ of the game.

  5. (5)

Report
$\bar{\boldsymbol{p}}=\frac{1}{K}\sum_{k=1}^{K}\boldsymbol{p}^{\left(k\right)}$
as the distribution over models and the histogram of values $v^{(k)}$.

Algorithm 1 Decision Theoretic CV

###  2.7. How to Choose $K$, $n$ and the $\mathcal{U}_{j}$:

Choosing $K$ is relatively straightforward. Since (2.4) is a Monte Carlo (MC)
estimate, its accuracy improves with the number of sample points. The
$\mathcal{U}_{j}$ are obtained through random subs-sampling of $\mathcal{U}$
and are of chosen to be of equal size $s$ ($|\mathcal{U}_{j}|=s$). The
$\mathcal{U}_{j}$ do not overlap. We selected $s$ and $n$ so that the size of
the combined support of the $\mathcal{U}_{j}$ is about $20\%$ of the size of
$\mathcal{U}$ ($ns\approx 0.2|\mathcal{U}|$). Note that given $ns\approx
0.2|\mathcal{U}|$, the parameterization of our approach can be reduced to $s$
which can be interpreted as a trade-off parameter between robustness (small
$s$) and accuracy (large $s$). Recall that robustness and accuracy are
conflicting requirements [49].

##  3\. UQ analysis

###  3.1. CV and Bayesian inference

While CV provides an estimate of the generalization error, this estimate is
not pointwise in the sense that it does not depend on the particular input of
the model. Furthermore, CV does not produce any distribution over models.
Furthermore, while Bayesian inference could be employed to obtain a
distribution over models, doing so would not be robust with respect to the
selection of the prior [50, 51, 48, 49].

###  3.2. DTB

On the other hand, by inducing a probability distribution $\bar{p}$ over
models, DTB defines a robust point-wise distribution over the output space
where robustness in inherited from the adversarial nature of the game. This
distribution depends on the particular choice of the loss function and the
histogram of the $\left\\{v^{\left(k\right)}\right\\}_{k=1}^{K}$ provides a
robust quantification of generalization error. Given an input $X$, write

$\rho\left(X\right)=\sum_{i=1}^{m}F_{i}\left(X\right)\bar{p}_{i}\,,$ (3.1)

for the average model output and

$\sigma^{2}\left(X\right)=\sum_{i=1}^{m}\left(F_{i}\left(X\right)-\rho\left(X\right)\right)^{2}\bar{p}_{i}\,,$
(3.2)

for the standard deviation of the model outputs defined by
$\bar{\boldsymbol{p}}$. Note that $\bar{\boldsymbol{p}}$ may be distinct from
the uniform distribution employed in _ensemble modeling_.

##  4\. Examples

We will now illustrate the proposed approach (Algorithm 1) on synthetic and
real-world datasets.

######  Example 2.

Consider the univariate function $y=x\sin x$ for $x\in\left[0,10\right]$
(solid dark plots in Figure 3). The dataset is composed of $35$ pointwise
evaluations of this function. In the left plot of Figure 3 we regress each
training subset $\mathcal{T}_{i}$ with a polynomial of degree $4$ to produce
the corresponding model $F_{i}$ and use Algorithm 1 with $20$ regression
polynomials to obtain a probability distribution $\bar{\boldsymbol{p}}$ over
these models. As seen in this plot, the ground truth is close to the
prediction mean, defined by (3.1), and it falls between the confidence bounds,
defined by (3.2). Although low order polynomials do not lead to highly
accurate models, Algorithm 1 provides a robust quantification of
generalization errors. Replacing the $20$ regressions polynomials by
regression trees further improves this picture, as illustrated in the right
plot of Figure 3. In this case, we fixed the depth of each tree to $5$. Note
that the confidence intervals are now smaller near the boundaries. Generally,
this simple example illustrates the robustness of Algorithm 1 when the data is
sparse, non-uniformly distributed, and the models are weak.

Figure 3. Robust Prediction with Confidence Intervals. The _left plot_ shows
the application of Algorithm 1 when the ML estimators are $20$ regression
polynomials each with degree $4$. The ground truth is shown in solid dark
color. The sample points are the dots, and the prediction mean and confidence
intervals are shown in red and filled-blue, respectively. The _right plot_
uses the setting of the left plot, except that the $20$ regressors are
regression trees. Irrespective of the type of the regressors, both plots show
robust predictions and confidence intervals obtained from only a sparse set of
non-uniform samples.

######  Example 3.

With this example, illustrate the robustness of Algorithm 1 on the following
datasets: California Housing [52], Electrical Grid Stability [3],
Superconductor [25], and Bike Sharing [14]. For the sake of brevity, we call
them Housing, Grid, SC, and Bike, respectively. To normalize target ranges,
the target variables in Grid, SC and Bike were multiplied by $100.0$, $0.1$,
and $0.01$, respectively.

For contrast, we compare the model distribution obtained from Algorithm 1 (DT
models) with the uniform distribution. In all the cases, we take $10$
regression trees with a maximum depth of $10$. The original data is divided
into $80\%$ train-UQ and $20\%$ test sets. The train-UQ set is then fed into
Algorithm 1 once having separate $\mathcal{T}$ and $\mathcal{U}$ sets, and
once $\mathcal{T}=\mathcal{U}$. The latter is done for the sake of a fair
comparison with uniform ensembles. In the algorithm, we take $n=100$ and
$K=100$. Also, for each $k\in\left\\{1,\ldots,K\right\\}$, we take
$\frac{sn}{\left|\mathcal{U}\right|}\simeq 0.2$.

We introduce two modes of training: In the first mode, each tree is trained on
randomly selected $0.5\%$ of the train set $\mathcal{T}$. In the second mode,
each tree is trained on randomly selected $50\%$ of the train set. The first
and second modes are called “weak” and “strong”, respectively.

Furthermore, we introduce two comparison metrics: One is the overall mean
squared loss on the test set. The other is the maximum mean squared loss over
folds, where folds are determined by binning the sorted target variable. In
these experiments, we use $100$ folds. In fact, this second metric is an
indicator of the robustness of the final ensemble with respect to distribution
shifts.

We repeat each setup in this experiment $20$ times. The results are reported
in Tables 1 and 2. The values in parenthesis are the ones produced with
$\mathcal{T}=\mathcal{U}$. As seen from Table 2, the ensemble of estimators
generated by Algorithm 1 are showing lower maximum fold losses in nearly all
weak cases and most of the strong cases, compared to their uniform averaging
counterparts. The difference is more prominent when the models are weakly
trained. Having a lower maximum fold loss is an indication of the robustness
of Algorithm 1 with respect to distribution shifts, especially when the models
are not strong. In other words, Algorithm 1 shows its best applicability when
the epistemic uncertainties are notable. On the other hand, most of the times,
the overall loss is lower for uniform averaging of the models; see Table 1.

It is noteworthy to mention that the improvement in the maximum fold loss is
larger than the degradation in the overall loss when Algorithm 1 is used. In
other words, if Algorithm 1 is used, with a slight sacrifice of the overall
accuracy, the models become more stable and consistent, with higher precision,
in their predictions.

Overall | Weak Trees |  | Strong Trees |
---|---|---|---|---
| Uniform | DT | Uniform | DT
Housing |  0.54(0.51) | 0.59(0.66) |  0.31(0.31) | 0.32(0.31)
Grid | 7.54(7.23) |  7.27(7.58) |  1.95(1.92) | 1.98(1.95)
SC |  3.41(3.15) | 3.52(3.81) |  1.28(1.23) | 1.30(1.22)
Bike |  1.47(1.39) | 1.66(1.87) |  0.28(0.27) |  0.28(0.28)
Table 1. Overall Losses Comparison. This table shows the overall loss comparison of 10 regression tress when the ensemble mean is taken by the use of Algorithm 1 versus simple uniform averaging. These are called DT and Uniform, respectively, in the table. The values in parenthesis correspond to $\mathcal{T}=\mathcal{U}$. The bold fonts show better losses in each category; weak vs strong. Max Fold | Weak Trees |  | Strong Trees |
---|---|---|---|---
| Uniform | DT | Uniform | DT
Housing | 2.91(2.93) |  2.40(2.52) | 1.74(1.72) |  1.73(1.70)
Grid | 32.25(31.96) |  29.97(27.47) | 9.79(8.50) |  9.74(8.50)
SC | 21.96(19.22) |  15.61(12.56) | 5.40(5.23) |  5.39(5.12)
Bike | 19.43(17.60) |  11.98(10.10) |  1.31(1.38) | 1.34(1.36)
Table 2. Maximum Fold Losses Comparison. This table shows the maximum fold
loss comparison of 10 regression trees. DT uses the distribution over models
obtained from Algorithm 1. Uniform refers to the uniform distribution over
models. These are called DT and Uniform, respectively, in the table. The
values in parenthesis correspond to $\mathcal{T}=\mathcal{U}$. The bold fonts
show better losses in each category; weak vs. strong.

######  Example 4.

In this example, we investigate the effect of $ns/\left|\mathcal{U}\right|$.
Since this ratio is a part of the purification over repeated games [26], we
call it “purification ratio” for brevity. Our purpose is to illustrate the
maximum fold loss, and also the overall loss, as a function of the
purification whose values are between $0$ and $1$. We work with the California
Housing [52] dataset, and we take an ensemble of models produced by Algorithm
1 with $n=100$ . In all the cases, we take $10$ regression trees with a
maximum depth of $10$. The original data is divided into $80\%$ train-UQ and
$20\%$ test sets. Each tree is trained on randomly selected $50\%$ of the
train set. This time, to estimate the robustness of the algorithm using
maximum fold loss, we use only $20$ bins (folds) over the test set. For each
purification ratio, we conduct the experiment $100$ times, and we plot the
mean of each experiment. To make sure enough data points are seen by the
estimators, $K$ is taken to be $5$ over the purification ratio.

The results are shown in Figure 4. As can be seen from the plots, there is a
purification ratio close to $0.15$ that produces the minimal maximum fold loss
in all the tests. At the same time, the overall loss decreases uniformly with
a decrease in the purification ratio. This experiment shows that to capture
the best balance between the overall loss and maximum fold loss, the
purification ratio $ns/\left|\mathcal{U}\right|$ should be around $0.15$. This
also supports our choice in the previous example of 0.20.

Figure 4. Purification Ratio. The _top plot_ shows the maximum fold loss for
different purification ratios. The _bottom plot_ shows the overall loss for
different purification ratios. Both plots correspond to the test dataset. A
weighted local linear regression is used to provide a better picture in both
plots. These plots show that the purification ratio should be around $0.15$
for this particular dataset to achieve the best balance between the overall
loss and maximum fold loss.

######  Example 5.

In this example, we investigate the effect of data sparsity on Algorithm 1. As
in the previous example, we work with the California Housing [52] dataset. In
all the cases, we take $10$ regression trees with a maximum depth of $10$. The
original data is divided into $80\%$ train-UQ and $20\%$ test sets. The train-
UQ set is then fed into Algorithm 1 with $\mathcal{T}=\mathcal{U}$. The latter
is done for the sake of a fair comparison with uniform ensembles. We take $n$
and $K$ to be both $100$. Also, the purification ratio is taken to be $0.20$.
The maximum fold loss is calculated over $20$ bins of the test set. In this
experiment, we vary the data availability by allowing a fixed fraction of the
train set to each estimator. We call this variable the “data fraction”. Figure
5 shows that for sparse data availability, Algorithm 1’s error is unanimously
less than the uniform averaging method. At the same time, the overall loss is
always smaller for uniform averaging. This figure conveys the message that
Algorithm 1 is more robust than uniform averaging, specifically when only a
small amount of data is available.

Figure 5. Small vs Large Data Test. The _top plot_ shows that Algorithm 1 is
robust when the available data is sparse. The _bottom plot_ shows that uniform
averaging always provide a more accurate prediction. Both plots show that for
large datasets, both approaches converge in robustness and accuracy.

##  5\. Related Works

###  5.1. Sources of Uncertainty:

From a statistical perspective, uncertainty manifests itself in two general
forms.

####  5.1.1. Aleatoric Uncertainty (Irreducible Uncertainty):

This type of uncertainty is intrinsic to the randomness of the data generating
process and is not reducible [11]. It is also known as the _statistical
uncertainty_. Aleatoric uncertainty can be categorized into homoskedastic and
heteroskedastic categories [12]. The homoskedastic randomness stays constant
for all data points, however, the heteroskedastic uncertainty is variant with
respect to them.

####  5.1.2. Epistemic Uncertainty (Reducible Uncertainty):

This type of error is about the oversight on data and can be reduced with an
increase in data collection, incorporation of more features, and a better
selection of the model [11].

###  5.2. What does UQ mean in ML?

Based on the sources of uncertainty enumerated, we can define UQ as any method
that can quantify the individual or combined effects of the aleatoric and
epistemic uncertainties. Hence, UQ can have different interpretations in the
context of ML, and statistical learning theory [15]. In what follows, we
express a survey of some of these methods.

####  5.2.1. UQ as Expected Generalization (Prediction) Error:

In this form, UQ quantifies the expected generalization error of a machine
learning algorithm. There are two separate approaches here. One is analytical,
used for linear models, and based on the training dataset (in-sample) [40].
The other is based on efficient sample re-use (extra-sample) and can be used
for both linear and nonlinear models [15]. The first approach encompasses
methods like Mallows’ $C_{p}$ [36, 38, 35, 37], and Akaike information
criterion (AIC) [1]. The second approach uses techniques like cross-validation
(CV) [64, 65, 2, 21, 67] and bootstrapping [13, 6, 7, 56]. For small to
moderately large models, CV methods can be used readily. However,
computational costs may impede such approaches for larger models like deep
neural networks (DNN).

####  5.2.2. UQ as Posterior Distribution Variance:

In this form, the machine learning that is used must be probabilistic in a
Bayesian inference (BI) framework. The posterior distribution of the model
parameters can then be exploited to express prediction confidence intervals
[18, 41]. The major issue here is that the Bayesian approach needs priors that
are not necessarily found from observations. For linear models, this type of
UQ task is commonly done by the Bayesian information criterion (BIC) [62]. For
nonlinear models, it is done by approaches like the Monte Carlo (MC) and
Markov Chain Monte Carlo (MCMC) [19, 17, 20, 18]. Unfortunately, the MCMC
methods become computationally expensive for larger models. Using a
variational Bayesian inference (VBI) [23] has been proposed as a possible
solution. For example Bayesian neural networks (BNN) [34, 43, 23, 33, 5, 61]
are mainly using VBI. However, the computational costs are still prohibitive
[46], the MCMC comparisons show the low quality of posterior approximations
[68], and these approaches are sensitive to initial starting values [60].

####  5.2.3. UQ as Regression Quantiles:

There are methods in which data is used to provide quantile bounds as
prediction intervals over regressors in a frequentist sense [30, 29]. An
extension of this methodology is the method of quantile regression forests
(QRF) estimating the predictions of a regressor in terms of quantile values
[39]. Recently, conformal quantile regression (CQR) has combined conformal
prediction [54, 66, 53] with quantile regression (QR) methodology [39, 30, 29]
to provide confidence intervals by using a “pinball loss” [29] over a train
set and then applying a conformal prediction over a calibration set [59].
Although this method addresses heteroskedastic data with outliers, it requires
a specific loss function.

####  5.2.4. Deep Learning UQ (DLUQ ) Survey:

Deep learning (DL) has arisen as a particularly powerful technology due to its
ability to ingest raw data with less preprocessing than classical ML [22, 32].
However, DL models are costly at the training phase. Hence, the application of
the UQ views expressed in this section is not straightforward. Because of this
major issue, the deep neural networks (DNN) models become over-confident [44].
Ad hoc methods like confidence calibration [24], temperature scaling [27] (
using Platt scaling [55, 45]), histogram binning [69, 70], isotonic regression
[70], deep ensembles with Gaussian mixture [31], and Bayesian binning into
quantiles [42] are introduced to address deep learning UQ. Unfortunately, all
these methods are mainly post-processing steps to models. The only systematic
DLUQ is the dropout UQ approach [16, 63]. Although this method is closely
related to BI of deep Gaussian processes [58, 10], it is a limit case study
that could deviate from a Gaussian process for a finite width-depth DNN.

##  6\. Conclusion

In this article, we have furnished a systematic machine learning UQ approach
based on decision theory. DTB provides a rigorous UQ in a cross-validation
setting and produces ML algorithms that are more stable with respect to
distribution shifts. The algorithm presented in this paper can show its best
performance when there is significant epistemic uncertainty. At the same time,
DTB provides pointwise prediction confidence intervals for ML regressors. This
framework is not confined to regression problems in a classical setting and
can be readily extended to DNN and classification tasks as well. DTB slightly
sacrifices accuracy to achieve high stability for ML estimators.

## Acknowledgment

This research was carried out at the Jet Propulsion Laboratory, California
Institute of Technology, under a contract with the National Aeronautics and
Space Administration and support from Beyond Limits (Learning Optimal Models)
and AFOSR (Grant number FA9550-18-1-0271, Games for Computation and Learning).
The authors are thankful to Amy Braverman, Lukas Mandrake and Kiri Wagstaff,
for their insights.

© 2021\. California Institute of Technology. Government sponsorship
acknowledged.

## References

  * [1] Hirotogu Akaike.  Information theory and an extension of the maximum likelihood principle.  In Selected papers of hirotugu akaike, pages 199–213. Springer, 1998.
  * [2] David M Allen.  The relationship between variable selection and data agumentation and a method for prediction.  Technometrics, 16(1):125–127, 1974.
  * [3] Vadim Arzamasov, Klemens Böhm, and Patrick Jochem.  Towards concise models of grid stability.  In 2018 IEEE International Conference on Communications, Control, and Computing Technologies for Smart Grids (SmartGridComm), pages 1–6. IEEE, 2018.
  * [4] Dimitris Bertsimas and Ivan Paskov.  Stable regression: On the power of optimization over randomization in training regression problems.  Journal of Machine Learning Research, 21:1–25, 2020.
  * [5] Charles Blundell, Julien Cornebise, Koray Kavukcuoglu, and Daan Wierstra.  Weight uncertainty in neural networks.  arXiv preprint arXiv:1505.05424, 2015.
  * [6] Leo Breiman.  Bagging predictors.  Machine learning, 24(2):123–140, 1996.
  * [7] Leo Breiman.  Random forests.  Machine learning, 45(1):5–32, 2001.
  * [8] Leo Breiman, Jerome Friedman, Charles J Stone, and Richard A Olshen.  Classification and regression trees.  CRC press, 1984.
  * [9] Corinna Cortes and Vladimir Vapnik.  Support-vector networks.  Machine learning, 20(3):273–297, 1995.
  * [10] Andreas Damianou and Neil Lawrence.  Deep gaussian processes.  In Artificial Intelligence and Statistics, pages 207–215, 2013\.
  * [11] Armen Der Kiureghian and Ove Ditlevsen.  Aleatory or epistemic? does it matter?  Structural Safety, 31(2):105–112, 2009.
  * [12] Francis X Diebold.  Elements of forecasting.  Citeseer, 1998.
  * [13] Bradley Efron.  Estimating the error rate of a prediction rule: improvement on cross-validation.  Journal of the American statistical association, 78(382):316–331, 1983.
  * [14] Hadi Fanaee-T and Joao Gama.  Event labeling combining ensemble detectors and background knowledge.  Progress in Artificial Intelligence, 2(2-3):113–127, 2014.
  * [15] Jerome Friedman, Trevor Hastie, and Robert Tibshirani.  The elements of statistical learning, volume 1.  Springer series in statistics Springer, Berlin, 2001.
  * [16] Yarin Gal and Zoubin Ghahramani.  Dropout as a bayesian approximation: Representing model uncertainty in deep learning.  In international conference on machine learning, pages 1050–1059, 2016.
  * [17] Alan E Gelfand and Adrian FM Smith.  Sampling-based approaches to calculating marginal densities.  Journal of the American statistical association, 85(410):398–409, 1990.
  * [18] Andrew Gelman, John B Carlin, Hal S Stern, David B Dunson, Aki Vehtari, and Donald B Rubin.  Bayesian data analysis.  Chapman and Hall/CRC, 2013.
  * [19] Stuart Geman and Donald Geman.  Stochastic relaxation, gibbs distributions, and the bayesian restoration of images.  IEEE Transactions on pattern analysis and machine intelligence, (6):721–741, 1984.
  * [20] Walter R Gilks, Sylvia Richardson, and David Spiegelhalter.  Markov chain Monte Carlo in practice.  Chapman and Hall/CRC, 1995.
  * [21] Gene H Golub, Michael Heath, and Grace Wahba.  Generalized cross-validation as a method for choosing a good ridge parameter.  Technometrics, 21(2):215–223, 1979.
  * [22] Ian Goodfellow, Yoshua Bengio, Aaron Courville, and Yoshua Bengio.  Deep learning, volume 1.  MIT press Cambridge, 2016.
  * [23] Alex Graves.  Practical variational inference for neural networks.  In Advances in neural information processing systems, pages 2348–2356, 2011.
  * [24] Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q Weinberger.  On calibration of modern neural networks.  In Proceedings of the 34th International Conference on Machine Learning-Volume 70, pages 1321–1330. JMLR. org, 2017.
  * [25] Kam Hamidieh.  A data-driven statistical model for predicting the critical temperature of a superconductor.  Computational Materials Science, 154:346–354, 2018.
  * [26] John C Harsanyi.  Games with randomly disturbed payoffs: A new rationale for mixed-strategy equilibrium points.  International journal of game theory, 2(1):1–23, 1973.
  * [27] Geoffrey Hinton, Oriol Vinyals, and Jeff Dean.  Distilling the knowledge in a neural network.  arXiv preprint arXiv:1503.02531, 2015.
  * [28] Tin Kam Ho.  Random decision forests.  In Proceedings of 3rd international conference on document analysis and recognition, volume 1, pages 278–282. IEEE, 1995.
  * [29] Roger Koenker and Gilbert Bassett Jr.  Regression quantiles.  Econometrica: journal of the Econometric Society, pages 33–50, 1978\.
  * [30] Roger Koenker and Kevin F Hallock.  Quantile regression.  Journal of economic perspectives, 15(4):143–156, 2001.
  * [31] Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell.  Simple and scalable predictive uncertainty estimation using deep ensembles.  In Advances in Neural Information Processing Systems, pages 6402–6413, 2017.
  * [32] Yann LeCun, Yoshua Bengio, and Geoffrey Hinton.  Deep learning.  nature, 521(7553):436, 2015.
  * [33] Christos Louizos and Max Welling.  Multiplicative normalizing flows for variational bayesian neural networks.  In Proceedings of the 34th International Conference on Machine Learning-Volume 70, pages 2218–2227. JMLR. org, 2017.
  * [34] David JC MacKay.  A practical bayesian framework for backpropagation networks.  Neural computation, 4(3):448–472, 1992.
  * [35] CL Mallows.  Choosing variables in a linear regression: A graphical aid.  In Central Regional Meeting of the Institute of Mathematical Statistics, Manhattan, Kansas, volume 5, 1964.
  * [36] Cohn L Mallows.  More comments on cp.  Technometrics, 37(4):362–372, 1995.
  * [37] Colin L Mallows.  Choosing a subset regression.  In TECHNOMETRICS, volume 9, page 190. AMER STATISTICAL ASSOC 1429 DUKE ST, ALEXANDRIA, VA 22314, 1967.
  * [38] Colin L Mallows.  Some comments on c p.  Technometrics, 15(4):661–675, 1973.
  * [39] Nicolai Meinshausen.  Quantile regression forests.  Journal of Machine Learning Research, 7(Jun):983–999, 2006.
  * [40] Douglas C Montgomery, Elizabeth A Peck, and G Geoffrey Vining.  Introduction to linear regression analysis.  John Wiley & Sons, 2015.
  * [41] Kevin P Murphy.  Machine learning: a probabilistic perspective.  MIT press, 2012.
  * [42] Mahdi Pakdaman Naeini, Gregory Cooper, and Milos Hauskrecht.  Obtaining well calibrated probabilities using bayesian binning.  In Twenty-Ninth AAAI Conference on Artificial Intelligence, 2015\.
  * [43] Radford M Neal.  Bayesian learning for neural networks, volume 118.  Springer Science & Business Media, 2012.
  * [44] Anh Nguyen, Jason Yosinski, and Jeff Clune.  Deep neural networks are easily fooled: High confidence predictions for unrecognizable images.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 427–436, 2015.
  * [45] Alexandru Niculescu-Mizil and Rich Caruana.  Predicting good probabilities with supervised learning.  In Proceedings of the 22nd international conference on Machine learning, pages 625–632. ACM, 2005.
  * [46] Yaniv Ovadia, Emily Fertig, Jie Ren, Zachary Nado, D Sculley, Sebastian Nowozin, Joshua V Dillon, Balaji Lakshminarayanan, and Jasper Snoek.  Can you trust your model’s uncertainty? evaluating predictive uncertainty under dataset shift.  arXiv preprint arXiv:1906.02530, 2019.
  * [47] Houman Owhadi and Clint Scovel.  Towards machine wald.  Springer Handbook of Uncertainty Quantification, 2015.  arXiv preprint arXiv:1508.02449.
  * [48] Houman Owhadi and Clint Scovel.  Brittleness of bayesian inference and new selberg formulas.  Communications in Mathematical Sciences, 14(1):83–145, 2016.
  * [49] Houman Owhadi and Clint Scovel.  Qualitative robustness in bayesian inference.  ESAIM: Probability and Statistics, 21:251–274, 2017.
  * [50] Houman Owhadi, Clint Scovel, and Tim Sullivan.  On the brittleness of bayesian inference.  SIAM Review, 57(4):566–582, 2015.
  * [51] Houman Owhadi, Clint Scovel, Tim Sullivan, et al.  Brittleness of bayesian inference under finite information in a continuous world.  Electronic Journal of Statistics, 9(1):1–79, 2015.
  * [52] R Kelley Pace and Ronald Barry.  Sparse spatial autoregressions.  Statistics & Probability Letters, 33(3):291–297, 1997.
  * [53] Harris Papadopoulos.  Inductive conformal prediction: Theory and application to neural networks.  INTECH Open Access Publisher Rijeka, 2008.
  * [54] Harris Papadopoulos, Kostas Proedrou, Volodya Vovk, and Alex Gammerman.  Inductive confidence machines for regression.  In European Conference on Machine Learning, pages 345–356. Springer, 2002.
  * [55] John Platt et al.  Probabilistic outputs for support vector machines and comparisons to regularized likelihood methods.  Advances in large margin classifiers, 10(3):61–74, 1999.
  * [56] J Ross Quinlan.  C4. 5: programs for machine learning.  Elsevier, 2014.
  * [57] Carl Edward Rasmussen.  Gaussian processes in machine learning.  In Summer School on Machine Learning, pages 63–71. Springer, 2003\.
  * [58] Carl Edward Rasmussen and CKI Williams.  Gaussian processes for machine learning.  The MIT Press, 2006.
  * [59] Yaniv Romano, Evan Patterson, and Emmanuel Candes.  Conformalized quantile regression.  In Advances in Neural Information Processing Systems, pages 3538–3548, 2019.
  * [60] Simone Rossi, Pietro Michiardi, and Maurizio Filippone.  Good initializations of variational bayes for deep models.  arXiv preprint arXiv:1810.08083, 2018.
  * [61] Cynthia Rudin.  Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead.  Nature Machine Intelligence, 1(5):206, 2019.
  * [62] Gideon Schwarz et al.  Estimating the dimension of a model.  The annals of statistics, 6(2):461–464, 1978.
  * [63] Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov.  Dropout: a simple way to prevent neural networks from overfitting.  The journal of machine learning research, 15(1):1929–1958, 2014\.
  * [64] Mervyn Stone.  Cross-validatory choice and assessment of statistical predictions.  Journal of the Royal Statistical Society: Series B (Methodological), 36(2):111–133, 1974.
  * [65] Mervyn Stone.  An asymptotic equivalence of choice of model by cross-validation and akaike’s criterion.  Journal of the Royal Statistical Society: Series B (Methodological), 39(1):44–47, 1977.
  * [66] Vladimir Vovk, Alex Gammerman, and Glenn Shafer.  Algorithmic learning in a random world.  Springer Science & Business Media, 2005.
  * [67] Grace Wahba.  Spline bases, regularization, and generalized cross-validation for solving approximation problems with large quantities of noisy data.  Approximation theory III, 2, 1980.
  * [68] Jiayu Yao, Weiwei Pan, Soumya Ghosh, and Finale Doshi-Velez.  Quality of uncertainty quantification for bayesian neural network inference.  arXiv preprint arXiv:1906.09686, 2019.
  * [69] Bianca Zadrozny and Charles Elkan.  Obtaining calibrated probability estimates from decision trees and naive bayesian classifiers.  In Icml, volume 1, pages 609–616. Citeseer, 2001.
  * [70] Bianca Zadrozny and Charles Elkan.  Transforming classifier scores into accurate multiclass probability estimates.  In Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 694–699. ACM, 2002.


* Lämmerzahl [1995] C. Lämmerzahl, A Hamilton operator for quantum optics in gravitational fields, Phys. Lett. A 203, 12 (1995).
  * Okołów [2020] A. Okołów, Does time always slow down as gravity increases?, Eur. J. Phys. 41, 023001 (2020).
  * Møller [1956] C. Møller, The ideal standard clocks in the general theory of relativity, Helv. Phys. Acta 29 (1956), 54 (1956).
  * Giese  _et al._ [2019] E. Giese, A. Friedrich, F. Di Pumpo, A. Roura, W. P. Schleich, D. M. Greenberger, and E. M. Rasel, Proper time in atom interferometers: Diffractive versus specular mirrors, Phys. Rev. A 99, 013627 (2019).
  * Di Pumpo  _et al._ [2020] F. Di Pumpo, A. Friedrich, E. Giese, A. Roura, H. Lemmel, D. M. Greenberger, E. M. Rasel, and W. P. Schleich, Chapter six - Specular mirror interferometer, in  _A Tribute to Emil Wolf_, Prog. Opt., Vol. 65, edited by T. D. Visser (Elsevier, 2020) pp. 173 – 229\.
  * Note [3] Note that the ratio $\Delta m/m\ll 1$ corresponds to the ratio of transition frequency to mean Compton frequency.
  * Hughes  _et al._ [2009] K. J. Hughes, J. H. T. Burke, and C. A. Sackett, Suspension of atoms using optical pulses, and application to gravimetry, Phys. Rev. Lett. 102, 150403 (2009).
  * Abend  _et al._ [2016] S. Abend, M. Gebbe, M. Gersemann, H. Ahlers, H. Müntinga, E. Giese, N. Gaaloul, C. Schubert, C. Lämmerzahl, W. Ertmer, W. P. Schleich, and E. M. Rasel, Atom-chip fountain gravimeter, Phys. Rev. Lett. 117, 203003 (2016).
  * Katori  _et al._ [2003] H. Katori, M. Takamoto, V. G. Pal’chikov, and V. D. Ovsiannikov, Ultrastable optical clock with neutral atoms in an engineered light shift trap, Phys. Rev. Lett. 91, 173005 (2003).
  * Xu  _et al._ [2019] V. Xu, M. Jaffe, C. D. Panda, S. L. Kristensen, L. W. Clark, and H. Müller, Probing gravity by holding atoms for 20 seconds, Science 366, 745 (2019).
  * Paige  _et al._ [2020] A. J. Paige, A. D. K. Plato, and M. S. Kim, Classical and nonclassical time dilation for quantum clocks, Phys. Rev. Lett. 124, 160602 (2020).
  * Amit  _et al._ [2019] O. Amit, Y. Margalit, O. Dobkowski, Z. Zhou, Y. Japha, M. Zimmermann, M. A. Efremov, F. A. Narducci, E. M. Rasel, W. P. Schleich, and R. Folman, ${T}^{3}$ Stern-Gerlach matter-wave interferometer, Phys. Rev. Lett. 123, 083601 (2019).
  * Dumke  _et al._ [2002] R. Dumke, T. Müther, M. Volk, W. Ertmer, and G. Birkl, Interferometer-type structures for guided atoms, Phys. Rev. Lett. 89, 220402 (2002).
  * Berrada  _et al._ [2013] T. Berrada, S. van Frank, R. Bücker, T. Schumm, J.-F. Schaff, and J. Schmiedmayer, Integrated Mach–Zehnder interferometer for Bose–Einstein condensates, Nat. Commun. 4, 2077 (2013).
  * Ryu and Boshier [2015] C. Ryu and M. G. Boshier, Integrated coherent matter wave circuits, New J. Phys. 17, 092002 (2015).
  * Navez  _et al._ [2016] P. Navez, S. Pandey, H. Mas, K. Poulios, T. Fernholz, and W. von Klitzing, Matter-wave interferometers using TAAP rings, New J. Phys. 18, 075014 (2016).
  * Schumm  _et al._ [2005] T. Schumm, S. Hofferberth, L. M. Andersson, S. Wildermuth, S. Groth, I. Bar-Joseph, J. Schmiedmayer, and P. Krüger, Matter-wave interferometry in a double well on an atom chip, Nat. Phys. 1, 57 (2005).
  * Pagel  _et al._ [2020] Z. Pagel, W. Zhong, R. H. Parker, C. T. Olund, N. Y. Yao, and H. Müller, Symmetric Bloch oscillations of matter waves, Phys. Rev. A 102, 053312 (2020).
  * Gebbe  _et al._ [2021] M. Gebbe, J.-N. Siemß, M. Gersemann, H. Müntinga, S. Herrmann, C. Lämmerzahl, H. Ahlers, N. Gaaloul, C. Schubert, K. Hammerer, S. Abend, and E. M. Rasel, Twin-lattice atom interferometry, Nat. Commun. 12, 1 (2021).
  * Ke  _et al._ [2018] Y. Ke, J. Huang, M. Zhuang, B. Lu, and C. Lee, Compact gravimeter with an ensemble of ultracold atoms in spin-dependent optical lattices, Phys. Rev. A 98, 053826 (2018).
  * Zhang  _et al._ [2016] X. Zhang, R. P. del Aguila, T. Mazzoni, N. Poli, and G. M. Tino, Trapped-atom interferometer with ultracold Sr atoms, Phys. Rev. A 94, 043608 (2016).
  * Roura  _et al._ [2021] A. Roura, C. Schubert, D. Schlippert, and E. M. Rasel, Measuring gravitational time dilation with delocalized quantum superpositions, Phys. Rev. D 104, 084001 (2021).
  * Hartmann  _et al._ [2020] S. Hartmann, J. Jenewein, E. Giese, S. Abend, A. Roura, E. M. Rasel, and W. P. Schleich, Regimes of atomic diffraction: Raman versus Bragg diffraction in retroreflective geometries, Phys. Rev. A 101, 053610 (2020).
  * Lévèque  _et al._ [2009] T. Lévèque, A. Gauguet, F. Michaud, F. Pereira Dos Santos, and A. Landragin, Enhancing the area of a Raman atom interferometer using a versatile double-diffraction technique, Phys. Rev. Lett. 103, 080405 (2009).
  * Alden  _et al._ [2014] E. A. Alden, K. R. Moore, and A. E. Leanhardt, Two-photon $E1$-$M1$ optical clock, Phys. Rev. A 90, 012523 (2014).
  * Ahlers  _et al._ [2016] H. Ahlers, H. Müntinga, A. Wenzlawski, M. Krutzik, G. Tackmann, S. Abend, N. Gaaloul, E. Giese, A. Roura, R. Kuhl, C. Lämmerzahl, A. Peters, P. Windpassinger, K. Sengstock, W. P. Schleich, W. Ertmer, and E. M. Rasel, Double Bragg interferometry, Phys. Rev. Lett. 116, 173601 (2016).
  * Note [4] If the focus lies for example on the optical transition spectrum in hydrogen-like atoms and by that on a specific energy scale, one can build a simpler effective theory by integrating out the energy scale associated with the nucleus. This way, the problem reduces to an effective QED interaction between a positively charged atomic nucleus and a single shell electron. In this new theory all dependence on the high energy scale is again absorbed into the coupling constants.
  * Caswell and Lepage [1986] W. Caswell and G. Lepage, Effective Lagrangians for bound state problems in QED, QCD, and other field theories, Phys. Lett. B 167, 437 (1986).
  * Paz [2015] G. Paz, An introduction to NRQED, Mod. Phys. Lett. A 30, 1550128 (2015).
  * Pineda and Soto [1998] A. Pineda and J. Soto, Potential NRQED: The positronium case, Phys. Rev. D 59, 016005 (1998).
  * Kleinert  _et al._ [2015] S. Kleinert, E. Kajari, A. Roura, and W. P. Schleich, Representation-free description of light-pulse atom interferometry including non-inertial effects, Phys. Rep. 605, 1 (2015).


# Polygonal equalities and $p$-negative type

Ian Doust  School of Mathematics and Statistics, University of New South
Wales, Sydney, New South Wales 2052, Australia<EMAIL_ADDRESS>and
Anthony Weston  Arts and Sciences, Carnegie Mellon University in Qatar,
Education City, PO Box 24866, Doha, Qatar<EMAIL_ADDRESS>
###### Abstract.

Nontrivial $p$-polygonal equalities impose certain conditions on the geometry
of a metric space $(X,d)$ and so it is of interest to be able to identify the
values of $p\in[0,\infty)$ for which such equalities exist. Following work of
Li and Weston [13], Kelleher, Miller, Osborn and Weston [10] established that
if a metric space $(X,d)$ is of $p$-negative type, then $(X,d)$ admits no
nontrivial $p$-polygonal equalities if and only if it is of strict
$p$-negative type. In this note we remove the underlying premise of
$p$-negative type from this theorem. As an application we show that the set of
all $p$ for which a finite metric space $(X,d)$ admits a nontrivial
$p$-polygonal equality is always a closed interval of the form $[\wp,\infty)$,
where $\wp>0$, or the empty set. It follows that for each $q\not=2$, the
Schatten $q$-class $\mathcal{C}_{q}$ admits a nontrivial $p$-polygonal
equality for each $p>0$. Other spaces with this same property include $C[0,1]$
and $\ell_{q}^{(3)}$ for all $q>2$.

###### Key words and phrases:

Polygonal equalities, negative type

###### 2010 Mathematics Subject Classification:

46B85, 30L05, 51K99

##  1\. Introduction

Motivated by Enflo’s definition of generalized roundness [6] and results of Li
and Weston [13], Kelleher, Miller, Osborn and Weston [10] introduced the
concept of a $p$-polygonal equality in a metric space $(X,d)$.

######  Definition 1.1.

Suppose that $(X,d)$ is a metric space and that $p\geq 0$. A $p$-polygonal
equality in $(X,d)$ is an equality of the form

$\sum_{i=1}^{s}\sum_{j=1}^{t}m_{i}n_{j}d(x_{i},y_{j})^{p}=\sum_{1\leq
i_{1}<i_{2}\leq s}m_{i_{1}}m_{i_{2}}d(x_{i_{1}},x_{i_{2}})^{p}+\sum_{1\leq
j_{1}<j_{2}\leq t}n_{j_{1}}n_{j_{2}}d(y_{j_{1}},y_{j_{2}})^{p}$ (1.1)

where $x_{1},\dots,x_{s},y_{1},\dots,y_{t}$ are a collection of (not
necessarily distinct) points in $X$, together with real number weights
$m_{1},\dots,m_{s},n_{1},\dots,n_{t}$ that satisfy
$m_{1}+\cdots+m_{s}=n_{1}+\cdots+n_{t}$.

The term ‘polygonal equality’ arises from the work of Elsner et al. [5] who,
in studying a conjecture due to Bernius and Blanchard, characterized the
finite subsets $\\{{\boldsymbol{x}}_{i}\\}_{i=1}^{n}$ and
$\\{{\boldsymbol{y}}_{j}\\}_{j=1}^{n}$ of $L_{1}(\Omega,\mu)$ for which one
obtains

$\displaystyle\sum_{i,j}\left\|{\boldsymbol{x}}_{i}-{\boldsymbol{y}}_{j}\right\|_{1}$
$\displaystyle=$
$\displaystyle\sum_{i<j}\left\|{\boldsymbol{x}}_{i}-{\boldsymbol{x}}_{j}\right\|_{1}+\sum_{i<j}\left\|{\boldsymbol{y}}_{i}-{\boldsymbol{y}}_{j}\right\|_{1}.$
(1.2)

The existence of suitable $p$-polygonal equalities in $(X,d)$ has close
connections with the equivalent concepts of $p$-negative type and generalized
roundness (see for example [12]) and so provides information concerning
classical embedding questions. For instance, Weston [18] applied $p$-polygonal
equalities in $L_{p}$ spaces to show that any two-valued Schauder basis of
$L_{p}$ must have strict $p$-negative type. As noted in [18, Corollary 3.1.3],
this property obstructs the existence of certain types of isometry into
$L_{p}$ spaces.

In any metric space one can easily obtain ‘trivial’ $p$-polygonal equalities.
For example one could make all the weights zero, or choose $x_{1}=y_{1}$,
$x_{2}=y_{2}$ and $m_{1}=m_{2}=n_{1}=n_{2}=1$. To rule out these uninteresting
cases, Kelleher et al. [10] introduced the concept of a nontrivial
$p$-polygonal equality and proved the following theorem.

######  Theorem 1.2.

[10, Lemma 3.21] Suppose that $(X,d)$ is a metric space of $p$-negative type.
Then $(X,d)$ is of strict $p$-negative type if and only if it admits no
nontrivial $p$-polygonal equality.

The property of being of strict $p$-negative type (and particularly the
property of being of strict $1$-negative type), which arose in the study of
isometric embeddings of metric spaces, has now been linked to properties in
many different areas of mathematics, from hyperbolic geometry to graph theory
[3, 4, 8, 9, 11, 13].

Theorem 1.2 left open the question of identifying the set

$P_{(X,d)}=\\{p\geq 0\thinspace:\thinspace\text{$(X,d)$ admits a nontrivial
$p$-polygonal equality}\\}.$

It is the aim of this short note to remove the negative type assumption in
Theorem 1.2 and to thereby identify the set $P_{X}=P_{(X,d)}$. Our main result
is the following.

######  Theorem 1.3.

Suppose that $(X,d)$ is a metric space and that $p\geq 0$. Then $(X,d)$ is of
strict $p$-negative type if and only if $(X,d)$ does not admit any nontrivial
$p$-polygonal equalities.

It is a classical result of Schoenberg [15] that the set of all $p$ for which
a metric space $(X,d)$ is of $p$-negative type is always a closed interval of
the form $[0,\wp]$, where $\wp\geq 0$, or $[0,\infty)$. Included here is the
possibility that $\wp=0$, in which case $[0,\wp]=\\{0\\}$. However, for finite
metric spaces, it is necessarily the case that $\wp>0$. This result is due to
Deza and Maehara [2] and, independently, Weston [17]. As an application of
Theorem 1.3 we show that the set $P_{X}$ is always a closed interval of the
form $[\wp,\infty)$, where $\wp>0$, or the empty set.

In the next section we shall give the main definitions needed. In Section 3 we
shall give the proof of Theorem 1.3 and examine some of the consequences of
this result.

##  2\. Background and definitions

Unless stated otherwise we shall assume that all metric spaces considered
below are finite and have at least two elements. Given such a space
$X=\\{x_{1},\dots,x_{m}\\}$ with metric $d$ we can form its distance matrix
$D=\bigl{(}d(x_{i},x_{j})\bigr{)}_{i,j=1}^{m}$. For $p\geq 0$, the
$p$-distance matrix for $(X,d)$ is
$D_{p}=\bigl{(}d(x_{i},x_{j})^{p}\bigr{)}_{i,j=1}^{m}$. Let $F_{0}$ denote the
hyperplane of all vectors
$\boldsymbol{\xi}=(\xi_{1},\dots,\xi_{m})^{T}\in\mathbb{R}^{m}$ such that
$\sum_{i=1}^{m}\xi_{i}=0$. The usual inner product in $\mathbb{R}^{m}$ will be
denoted by $\langle\cdot,\cdot\rangle$.

######  Definition 2.1.

Let $(X,d)$ be a finite metric space with $m$ points
$\\{x_{1},\ldots,x_{m}\\}$ and suppose that $p\geq 0$. We say that $(X,d)$ is
of $p$-negative type if

$\langle
D_{p}\boldsymbol{\xi},\boldsymbol{\xi}\rangle=\sum_{i,j}d(x_{i},x_{j})^{p}\xi_{i}\xi_{j}\leq
0$ (2.1)

for all $\boldsymbol{\xi}=(\xi_{1},\dots,\xi_{m})^{T}\in F_{0}$. If strict
inequality holds in (2.1) except when $\boldsymbol{\xi}=\boldsymbol{0}$ we say
that $(X,d)$ is of strict $p$-negative type.

The supremal $p$-negative type of $(X,d)$ is defined to be the quantity

$\wp(X)=\sup\\{p\geq 0\thinspace:\thinspace\text{$(X,d)$ is of $p$-negative
type}\\}.$

By extension, a general metric space $(X,d)$ is said to be of $p$-negative
type if every finite metric subspace of $X$ is of $p$-negative type. Similarly
it is of strict $p$-negative type if every finite metric subspace of $X$ has
that property.

It is a classical result of Schoenberg [16] that $(X,d)$ is of $p$-negative
type if and only if $(X,d^{p/2})$ embeds isometrically in a Hilbert space.
Schoenberg showed that $(X,d)$ is of $p$-negative type for all $p\leq\wp(X)$,
and so $(X,d)$ embeds isometrically in a Hilbert space if and only if
$\wp(X)\geq 2$.

Li and Weston [13] showed that for any finite metric space $(X,d)$ we have:

  1. (i)

$(X,d)$ is of strict $p$-negative type for all $p\in[0,\wp(X))$;

  2. (ii)

If $\wp(X)<\infty$, then $(X,d)$ is of $\wp(X)$-negative type but not of
strict $\wp(X)$-negative type.

The hypothesis that $(X,d)$ is a finite metric space is necessary in (ii);
there are infinite metric spaces for which are of strict $\wp(X)$-negative
type (see [3, Example 2] and [13, Section 5]).

The case where $\wp(X)=\infty$ for a general metric space $(X,d)$ is well
understood. Faver et al. [7] have shown that $\wp(X)=\infty$ if and only if
$(X,d)$ is an ultrametric space.

In what follows, $(X,d)$ is assumed to be a finite metric space, unless stated
otherwise.

The main step in proving Theorem 1.3 is to replace the original form for a
$p$-polygonal equality (1.1) with an expression involving the $p$-distance
matrix for $(X,d)$.

A signed $(s,t)$-simplex in $(X,d)$ is a collection of points
$x_{1},\dots,x_{s},y_{1},\dots,y_{t}\in X$ and associated real weights
$m_{1},\dots,m_{s},n_{1},\dots,n_{t}$. We shall denote such a simplex by
$Q=[x_{1}(m_{1}),\dots,x_{s}(m_{s});y_{1}(n_{1}),\dots,y_{t}(n_{t})]=[x_{i}(m_{i});y_{j}(n_{j})]_{s,t}$.
It was shown in [10, Section 3] that condition (2.1) can be reformulated in
terms of the $p$-simplex gaps for such simplices.

The $p$-simplex gap for a signed simplex $Q=[x_{i}(m_{i});y_{j}(n_{j})]_{s,t}$
is the quantity

$\gamma_{p}(Q)=\sum_{i,j}m_{i}n_{j}d(x_{i},y_{j})^{p}-\sum_{1\leq
i_{1}<i_{2}\leq s}m_{i_{1}}m_{i_{2}}d(x_{i_{1}},x_{i_{2}})^{p}-\sum_{1\leq
j_{1}<j_{2}\leq t}n_{j_{1}}n_{j_{2}}d(y_{j_{1}},y_{j_{2}})^{p}.$

In this language, a $p$-polygonal equality is an equality of the form
$\gamma_{p}(Q)=0$ for some signed $(s,t)$-simplex $Q$ in $X$.

######  Definition 2.2.

A signed simplex $Q=[x_{i}(m_{i});y_{j}(n_{j})]_{s,t}$ is said to be
completely refined if the points $x_{1},\dots,x_{s},y_{1},\dots,y_{t}$ are
distinct and the real weights $m_{1},\dots,m_{s}$, $n_{1},\dots,n_{t}$ are all
strictly positive.

Suppose that $Q=[x_{i}(m_{i});y_{j}(n_{j})]_{s,t}$ is a completely refined
simplex in $(X,d)$. We can list the elements of $X$ as
$x_{1},\dots,x_{s},y_{1},\dots,y_{t},z_{1},\dots,z_{u}$ and form the vector

$\boldsymbol{\xi}=(m_{1},\dots,m_{s},-n_{1},\dots,-n_{t},0,\dots,0)^{T},$

which is necessarily a nonzero vector in $F_{0}$. An elementary calculation
then shows that for all $p\geq 0$,

$\langle D_{p}\boldsymbol{\xi},\boldsymbol{\xi}\rangle=-2\gamma_{p}(Q).$ (2.2)

Conversely, starting from any nonzero $\boldsymbol{\xi}\in F_{0}$ one can
construct a completely refined simplex $Q$ satisfying (2.2).

There is a useful dichotomy for signed simplices. A key result in [10] shows
that each signed simplex $Q$ in $X$ may be algorithmically reduced to a so-
called degenerate signed simplex $Q^{\ast}$ (one in which all weights are
zero) or a completely refined signed simplex $Q^{\ast}$. In either case, one
has $\gamma_{p}(Q)=\gamma_{p}(Q^{\ast})$ for all $p\geq 0$. Signed simplices
that can be algorithmically reduced to a completely refined signed simplex are
said to be nondegenerate. By definition, a nontrivial $p$-polygonal equality
in $(X,d)$ is an equality of the form $\gamma_{p}(X)=0$ for some nondegenerate
signed simplex $Q$ in $X$. In what follows we shall make use of the following
characterization of nontrivial $p$-polygonal equalities that is implicit in
[10, Section 3].

######  Theorem 2.3.

Let $(X,d)$ be a finite metric space and suppose that $p\geq 0$. Then the
following conditions are equivalent.

  1. (i)

$(X,d)$ admits a nontrivial $p$-polygonal equality.

  2. (ii)

$\langle D_{p}\boldsymbol{\xi},\boldsymbol{\xi}\rangle=0$ for some nonzero
$\boldsymbol{\xi}\in F_{0}$.

######  Remark 2.4.

In general, finding a nonzero $\boldsymbol{\xi}\in F_{0}$ such that $\langle
D_{p}\boldsymbol{\xi},\boldsymbol{\xi}\rangle=0$ can be a complicated task.
However, the situation that arises when $p=\wp(X)<\infty$ is considerably
simpler. Sánchez [14, Corollary 2.5] showed that if $D_{\wp(X)}$ is singular
then $\ker(D_{\wp(X)})\subseteq F_{0}$ and so any nonzero
$\boldsymbol{\xi}\in\ker(D_{\wp(X)})$ satisfies $\langle
D_{\wp(X)}\boldsymbol{\xi},\boldsymbol{\xi}\rangle=0$. On the other hand, if
$D_{\wp(X)}$ is invertible, we can take
$\boldsymbol{\xi}=D_{\wp(X)}^{-1}(1,1,\dots,1)^{T}$. Then
$\boldsymbol{0}\neq\boldsymbol{\xi}\in F_{0}$ and $\langle
D_{\wp(X)}\boldsymbol{\xi},\boldsymbol{\xi}\rangle=0$.

##  3\. Proofs

In light of Theorem 2.3 we can rephrase Theorem 1.3 in the case of finite
spaces as follows.

######  Theorem 3.1.

Suppose that $(X,d)=(\\{x_{1},x_{2},\dots,x_{m}\\},d)$ is a finite metric
space with $m\geq 2$ and that $p\geq 0$. Then the following are equivalent.

  1. (i)

$(X,d)$ is of strict $p$-negative type.

  2. (ii)

$(X,d)$ admits no nontrivial $p$-polygonal equalities.

  3. (iii)

$\langle D_{p}\boldsymbol{\xi},\boldsymbol{\xi}\rangle\neq 0$ for all nonzero
$\boldsymbol{\xi}\in F_{0}$.

###### Proof.

By Theorem 2.3 it suffices to prove that (i) and (iii) are equivalent.

It follows from the definitions that if $(X,d)$ is of strict negative type
then (iii) holds, while if $(X,d)$ is of $p$-negative type, but not strict
$p$-negative type, then there exists a nonzero $\boldsymbol{\xi}\in F_{0}$
such that $\langle D_{p}\boldsymbol{\xi},\boldsymbol{\xi}\rangle=0$. The issue
then is whether it is possible to have a space which is not of $p$-negative
type for some $p$, and which does not admit any nontrivial $p$-polygonal
equalities.

Suppose that $(X,d)$ is not of $p$-negative type. Then there is some
(necessarily) nonzero
$\boldsymbol{\xi}_{1}=(\alpha_{1},\alpha_{2},\dots,\alpha_{m})^{T}\in F_{0}$
such that $\langle D_{p}\boldsymbol{\xi}_{1},\boldsymbol{\xi}_{1}\rangle>0$.
On the other hand, if we let $\boldsymbol{\xi}_{0}=(1,-1,0,\dots,0)^{T}$, then
$\langle
D_{p}\boldsymbol{\xi}_{0},\boldsymbol{\xi}_{0}\rangle=-2d(x_{1},x_{2})^{p}<0$.
For $0<t<1$ let
$\boldsymbol{\xi}_{t}=(1-t)\boldsymbol{\xi}_{0}+t\boldsymbol{\xi}_{1}$. Then
certainly $\boldsymbol{\xi}_{t}\in F_{0}$ for all $t$, and by the Intermediate
Value Theorem, there exists $s\in(0,1)$ such that $\langle
D_{p}\boldsymbol{\xi}_{s},\boldsymbol{\xi}_{s}\rangle=0$. It just remains to
check that $\boldsymbol{\xi}_{s}\neq\boldsymbol{0}$.

Suppose then that

$\boldsymbol{\xi}_{s}=(1-t+t\alpha_{1},t-1+t\alpha_{2},t\alpha_{3},\dots,t\alpha_{m})^{T}=\boldsymbol{0}.$

This immediately implies that $\alpha_{j}=0$ for $3\leq j\leq m$. As
$\boldsymbol{\xi}_{1}\in F_{0}$ this means that $\alpha_{2}=-\alpha_{1}$. But
if this is the case then $\langle
D_{p}\boldsymbol{\xi}_{1},\boldsymbol{\xi}_{1}\rangle<0$ which is a
contradiction. Thus $\boldsymbol{\xi}_{s}\neq\boldsymbol{0}$ and so we have a
nontrivial $p$-polygonal equality in $(X,d)$. xx $\Box$

Since the existence of a nontrivial $p$-polygonal equality is also determined
by what happens on the finite subsets of $X$, Theorem 1.3 follows immediately
from Theorem 3.1.

######  Corollary 3.2.

If $(X,d)$ is a finite metric space with $\wp(X)$ finite, then

$P_{X}=\\{p\geq 0\thinspace:\thinspace\text{$(X,d)$ admits a nontrivial
$p$-polygonal equality}\\}=[\wp(X),\infty).$

###### Proof.

By Li and Weston [13], $(X,d)$ is of strict $p$-negative type for all
$p<\wp(X)$ and $(X,d)$ admits a nontrivial $\wp(X)$-polygonal equality. Now
apply Theorem 3.1 for all $p\not=\wp(X)$. xx $\Box$

######  Remark 3.3.

In the case of an infinite metric space $(X,d)$ with $\wp(X)<\infty$ we
cannot, in general, draw the exactly same conclusion as that given in
Corollary 3.2. This is because there exist infinite metric spaces that are of
strict supremal $p$-negative type. An example of this phenomenon is the
infinite metric tree given in Doust and Weston [3, Example 2]. So in this case
the best that we can say is that $P_{X}$ is one of the intervals
$[\wp(X),\infty)$ or $(\wp(X),\infty)$. An exception to this arises when
$\wp(X)=0$, wherein one necessarily obtains $P_{X}=(0,\infty)$. The first
example of a metric space $(X,d)$ with $\wp(X)=0$ was constructed by Enflo
[6]. A more recent result of Dahma and Lennard [1] showed that the Schatten
$q$-class $\mathcal{C}_{q}$, $q\not=2$, does not have $p$-negative type for
any $p>0$. In other words, $\wp(\mathcal{C}_{q})=0$ for all $q\not=2$. It
follows from Corollary 3.2 that $\mathcal{C}_{q}$, $q\not=2$, admits a
nontrivial $p$-polygonal equality for all $p>0$. This settles an open question
raised by Kelleher et al. [10, Section 6].

######  Remark 3.4.

A simple example of a finite metric space $(X,d)$ for which $P_{X}$ is the
empty set is a two point discrete metric space. For all $p\geq 0$, $\langle
D_{p}\boldsymbol{\xi},\boldsymbol{\xi}\rangle=-2\xi_{1}^{2}$ for
$\boldsymbol{\xi}\in F_{0}$, and so one may apply Theorem 3.1. More generally,
Faver et al. [7, Section 5] have shown that $P_{(X,d)}$ is the empty set if
and only if $(X,d)$ is an ultrametric space.

## References

  * [1] A. M. Dahma and C. J. Lennard, Generalized roundness of the Schatten $p$-class, $\mathcal{C}_{p}$, J. Math. Anal. Appl. 412 (2014), 676–684.
  * [2] M. Deza and H. Maehara, Metric transforms and Euclidean embeddings, Trans. Amer. Math. Soc. 317 (1990), 661–671.
  * [3] I. Doust and A. Weston,  Enhanced negative type for finite metric trees, J. Funct. Anal. 254 (2008), 2336–2364; with Corrigendum.
  * [4] I. Doust and A. Weston, Beyond trees: the metric geometry of subsets of weighted Hamming cubes, arXiv.
  * [5] L. Elsner, L. Han, I. Koltracht, M. Neumann, M. Zippin, On a polygon equality problem, J. Math. Anal. Appl. 223 (1998), 67–75.
  * [6] P. Enflo, On a problem of Smirnov, Ark. Mat. 8 (1969), 107–109.
  * [7] T. Faver, K. Kochalski, M. Murugan, H. Verheggen, E. Wesson, A. Weston, Roundness properties of ultrametric spaces, Glasgow Math. J. 56 (2014), 519–535.
  * [8] P. Hjorth, P. Lisonĕk, S. Markvorsen and C. Thomassen, Finite metric spaces of strictly negative type, Linear Algebra Appl. 270 (1998), 255–273.
  * [9] P. G. Hjorth, S. L. Kokkendorff and S. Markvorsen, Hyperbolic spaces are of strictly negative type, Proc. Amer. Math. Soc. 130 (2002), 175–181.
  * [10] C. Kelleher, D. Miller, T. Osborn, A. Weston, Polygonal equalities and virtual degeneracy in $L_{p}$-spaces, J. Math. Anal. Appl. 415 (2014), 247–268.
  * [11] J.-F. Lafont and S. Prassidis, Roundness properties of groups, Geom. Dedicata 117 (2006), 137–160.
  * [12] C. J. Lennard, A. M. Tonge and A. Weston, Generalized roundness and negative type, Michigan Math. J. 44 (1997), 37–45.
  * [13] H. Li and A. Weston, Strict $p$-negative type of a metric space, Positivity 14 (2010), 529–545.
  * [14] S. Sánchez, On the supremal $p$-negative type of a finite metric space, J. Math. Anal. Appl. 389 (2012), 98–107.
  * [15] I. J. Schoenberg, On certain metric spaces arising from Euclidean spaces by a change of metric and their imbedding in Hilbert space, Ann. Math. 38 (1937), 787–793.
  * [16] I. J. Schoenberg, Metric spaces and positive definite functions, Trans. Amer. Math. Soc. 44 (1938), 522–536.
  * [17] A. Weston, On the generalized roundness of finite metric spaces, J. Math. Anal. Appl. 192 (1995), 323–334.
  * [18] A. Weston, The geometry of two-valued subsets of $L_{p}$-spaces, Math. Slovaca 67 (2017), 751–758.