Approximate Bayesian inference methods provide a powerful suite of tools for finding approximations to intractable posterior distributions. However, machine learning applications typically involve selecting actions, which—in a Bayesian setting—depend on the posterior distribution only via its contribution to expected utility. A growing body of work on “loss-calibrated approximate inference” methods has therefore sought to develop posterior approximations sensitive to the influence of the utility function. Here we introduce loss-calibrated expectation propagation (Loss-EP), a  loss-calibrated variant of expectation propagation. This method resembles standard EP with an additional factor that “tilts” the posterior towards higher-utility decisions. We show applications to Gaussian process classification under binary utility functions with asymmetric penalties on False Negative and False Positive errors, and show how this asymmetry can have dramatic consequences on what information is “useful” to capture in an approximation.

§ INTRODUCTION

Bayesian methods tend to emphasize  inference, which involves modeling the uncertainty over model parameters given an observed dataset. However, in most cases we perform Bayesian inference in order to make decisions or take actions in some end-use task [Von Luxburg et al., 2012].

Bayesian decision theory asserts that the posterior distribution learned from inference is sufficient for Bayes-optimal decision-making [Berger, 2013].  This theoretical result is of limited value if the posterior distribution is intractable—an increasingly common occurrence in modern machine learning settings with

large datasets and/or complex models.

To address this intractability, approximate Bayesian inference methods seek to compute tractable approximations to the posterior distribution.  It is tempting to use these approximations as a plug-in replacement for the posterior during prediction and decision-making. However, information is lost in these approximations, and our goal should be to retain information that allows us to make optimal decisions, i.e., decisions that maximize utility. Unfortunately, common approximate inference methods such as variational inference (VI) and expectation propagation (EP) do not take account of utility, or of the loss of information that could compromise optimal decision-making.
The key intuition is that if we change the utility function, we do not change the posterior distribution, but we may change the best approximation to it. Loss-calibrated approximate inference has only recently emerged as a general framework optimizing and evaluating approximations in a “loss-aware” way [Lacoste-Julien et al., 2011]. Analogously to how Bayesian decision theory prescribes that optimal decision-making under uncertainty maximizes expected utility—an expectation over the posterior distribution of the models' parameters—loss-calibrated inference proposes that the optimal approximation too should maximize expected utility.

With this paper, we introduce loss-calibrated expectation propagation (loss-EP). Like other loss-calibrated inference methods, loss-EP aims to embed features of the decision-making problem into the inference procedure. We show  loss-EP is tantamount to standard EP  augmented by one additional site factor that “calibrates” the approximate posterior to the decision-making problem. In Section 2, we outline the core machinery of Bayesian decision theory and loss-calibrated inference. In Section 3, we introduce EP and loss-calibrated EP. In Section 4, we demonstrate the performance of loss-calibrated and standard approximate inference methods in the familiar Gaussian process classification. In Section 5, we discuss opportunities for future work that could complement and/or improve Loss-EP as presented here.

§ BACKGROUND

§.§ Bayesian decision theory

The Bayesian approach to decision-making starts from a model with parameters $\param$, likelihood $p(y\mid \bx, \param)$, and prior $p(\param)$. Given an observed training dataset $\data=\{\bx_n, y_n\}_{n=1}^N$, the posterior follows from Bayes' rule:

p(|)=p()p(|)/p()∝p()∏_n=1^N p(y_n|_n,)

Given novel datapoints $\bxs$, we can make predictions (incorporating uncertainty) about future observations using the posterior predictive distribution, which incorporates all relevant information from the training data via the posterior:

p(|, )=∫p(|, ) p(|) d
The end-use decision-making problem selects an action $a(\bxs)$ and receives a utility $\util(\ys, a(\cdot))$, depending on the observation $\ys$ thereafter. To select the optimal action, we briefly suppose we can compute the posterior in eq. (<ref>). Bayesian decision theory prescribes that we choose the action(s) that maximize the full expected utility, inversely minimize the full Bayes risk. The full expected utility computes the utility received for future (predictive) data $(\bxs, \ys)$, in expectation over those posterior beliefs about the model parameters:

_p(a)   =∫p(|)∬p()p(|,) (a(), )  dd·d≜∫p(|) (a, ) d
where $\Util(a, \param)$ is the predictive utility, marginalized over data given a fixed value of model parameters. In practice, the data-generating distribution $p(\bxs)$ is often unknown, for which we can define the conditional expected utility given some $\bxs$ to be

_p(a()|) = ∬p(|)p(|,)(a(), )  d·d
The optimal action function $a_\opt$ maximizes the full expected utility in (<ref>) as

a_opt = amin _p(a)

This would be a cumbersome optimization over several intractable integrals, but importantly it is equivalent to the optimal actions achieved by maximizing the conditional expected utility in (<ref>) pointwise, such that $a_{\opt}(\bxs) = {\arg\min_a}\:\:\EEutil_p(a(\bxs)\mid\bxs)$ also.

§.§ Loss-calibration as approximate action selection

In most applications of interest, exact inference of the true posterior is intractable, which poses a major challenge for Bayes-optimal decision-making. Conceivably, the next-best thing we can do is to make actions optimal under some tractable approximation $q(\param)$ of the posterior $p(\param\mid\data)$. In such case, we could define the analogous approximate full and conditional expected utilities under the approximation; the latter, along with the action that maximizes it, would be

_q(a()|)    = ∬q()p(|,)(a(), )  d·d

with  a_q()    = amax  _q(a()|).

Whether or not this $q$-optimal action $a_q$ maximizes the true expected utility in (<ref>) will depend on how we select the approximation $q(\param)$. Our approximate utility maximization using $q(\param)$ and $a_q$ in eqs. (<ref>, <ref>) will be suboptimal—relative to the Bayes-optimal $p(\param\mid\data)$ and $a_\text{opt}$—to the extent that for any $\bxs$, we select a suboptimal action, i.e. $a_q(\bxs)\neq a_\text{opt}(\bxs)$.

In expectation, we can define the discrepancy in utility between $q$-optimal actions and true optimal actions as

d_(p   q) = _p(a_opt) - _p(a_q)

This discrepancy is neither a proper divergence nor regret—there can be many $q$ and $a_q$ such that $d_\util=0$, but still serves as a useful guide for how we should define the “best” approximate posterior. Problematically, optimizing expected utility as a function of $q$ is not the objective of approximate inference methods. Loss-calibrated approximate inference was proposed to bridge this gap, and jointly perform approximate Bayesian inference and action selection, by incorporating the expected utility explicitly into the optimization program that performs inference.

§.§ Variational inference and loss-calibrated variational inference

For example, variational inference (VI) optimizes a bound on the marginal likelihood [Blei et al., 2017]:

logp()    ≥∫q()·log(p(,)/q()) d

s.t.  q_VI()   =qmin  D_KL(p(|)   q())

Minimizing KL divergence optimizes generic statistical features of the posterior, but such an approximation could still result in arbitrarily poor decisions or arbitrarily large discrepancy $d_\util(p\,\|\, q)$. Matching probability density is not important—matching actions is.

Loss-calibrated variational inference (LossVI) approximates the posterior by maximizing a lower-bound on the $\log$-full expected utility using the same approach [Lacoste-Julien et al., 2011, Kusmierczyk et al., 2019]:

log_p(a)    ≥∫q()·log(p(|)(a, )/q()) d

s.t.  q_LossVI()    = qmin  D_KL(p̃_a()   q()),   where   p̃_a() = p(|)(a, )/_p(a)

The resulting bound is exactly the variational inference objective, but minimizes the KL divergence from a utility-weighted posterior $\tilde p_a(\param)$.

Implementation of LossVI requires joint optimization of the approximation $q(\param)$ and the actions $a(\cdot)$, and [Lacoste-Julien et al., 2011] propose an EM procedure that alternates coordinate descents between the two, with applications to Gaussian processes.

§ LOSS-CALIBRATED EXPECTATION PROPAGATION

Expectation propagation (EP) approximates the posterior by decomposing the global inference into a collection of local inferences by message-passing [Minka, 2001, Minka, 2001, Vehtari et al., 2020]. These local inferences operate on each term of some factorization of the posterior, typically the product of the prior and the likelihoods of each of the i.i.d. data:

p(|𝒟) = 1/Zp_0() ∏_i p(_i|)    ∝p_0() ∏_i t_i()  ≈  p_0() ∏_i t̃_i() = q(φ)

Each likelihood term $t_i(\param)$ is approximated in EP by a site potential $\tilde t_i(\param)$, such that the approximation shares the factorization of the true posterior. EP iteratively performs local approximate inferences for each site $\tilde t_i(\param)$, over three steps—Deletion, Projection, and Update—that replaces one site with its true likelihood term, optimizes a new approximation that matches moments to this hybrid distribution, and updates the original site accordingly (cf. box below, Algorithm 1). All of these operations are powered by properties of distributions in the same exponential family (EF), for which purpose we assign all sites to have the (unnormalized) exponential family form

t̃_i() ∝exp(⟨𝐬(), θ⟩)

where $\mathbf{s}(\param)$ are the sufficient statistics and $\boldsymbol{\theta}$ are the natural parameters [Seeger, 2005, Nielsen and Garcia, 2009].

These updates are repeated across all site potentials until convergence. While these local inferences only minimize the forward KL divergence from $N$ different tilted distributions, this iterative message-passing procedure approximates the global minimization forward KL divergence from the posterior, $D_{KL}(p(\param\mid\data\,\|\,q(\param))$ [Minka, 2001]. Convergence is not guaranteed, but empirically EP performs well.

Our contribution begins with the observation that the full expected utility in (<ref>) admits a factorization similar to that utilized by EP:

_p(a) = ∫1/Z p_0()∏_n p(y_n|_n,) (, a) df
∝∫p()∏_n t_n() t_ℓ() d
where the the utility function $\Util(a, \param)$ becomes the $N+1$th term $t_\ell(\param)$.
As before, we approximate the $N$ likelihood terms and the new utility term with $N+1$ exponential family site potentials $\tilde t_i(\param)$ and $\tilde t_\ell(\param)$, respectively. The resulting loss-calibrated EP approximation $\overline{q}(\param)$ takes the form

q()= p_0()∏_i t̃_i() t̃_ℓ() ∝q() t̃_ℓ()

and approximates the same utility-weighted posterior $\tilde p_a(\param)$ as LossVI in eq. (<ref>). The approximation to the posterior $p(\param\mid\data)\approx q(\param)$ is a partial product of the site potentials that comprise $\overline{q}(\param)$: all except the utility site $\tilde t_\ell(\param)$. EP updates for the $N$ site approximations $\tilde t_i(\param)$ follow the standard EP procedure; the update for the new site approximation $\tilde t_\ell(\param)$ requires one extra computation. We present a single site update below in full detail, and give the aggregate LossEP procedure in Algorithm 1.

[center, breakable, width=0.95, colback=pale-gray, boxrule=0pt]
Deletion: Divide the utility site $\tilde t_\ell(\param)$ from $\overline{q}(\param)$ to form the cavity distribution, which for the utility site is identically the posterior approximation:

qℓ()    = q()/t̃_ℓ() ∝p_0() ∏_i t̃_i() ∝q()

In natural parameters, $\boldsymbol{\theta}\scav{\ell} = \overline{\boldsymbol{\theta}} - \boldsymbol{\theta}_\ell$.

Projection: Reinsert the true term $t_\ell(\param)$ into $q\scav{\ell}(\param)$ to form the tilted distribution, and project back into the approximating family:

q()    = [t_ℓ()qℓ()] ≜qmin D_KL(t_ℓ()qℓ()   q())

In natural parameters, this divergence minimization is equivalent to the gradient update $\overline{\boldsymbol{\eta}}\new = \boldsymbol{\eta}\scav{\ell} + \nabla_{\boldsymbol{\theta}\scav{i}}\log Z_\ell$, where $\boldsymbol{\eta}=\EE[\mathbf{s}(\param)]$ are the mean parameters and and

logZ_ℓ= log∫t_ℓ()qℓ() d= _q(a)

is the log-normalizer of the tilted distribution. For the utility site, the true term $t_\ell(\param)=\Util(a, \param)$ is the full predictive utility and the log-normalizer is identically the $q$-full expected utility. To resolve the dependence on actions $a$, introduce the following prerequisite step:

Action Selection: [Utility site only] Select the $q\cav{\ell}$-optimal actions

a_q   =amax _qℓ(a)

Performing this step only requires information already available at the local site update.

Update: Divide the utility-cavity distribution from the projected $\overline{q}\new(\varphi)$ to back out the updated site $\tilde t_\ell(\varphi)$. With damping $\delta\in[0, 1)$,

t̃_ℓ()    = (q() /  qℓ())^δ·t̃_ℓ()^1-δ

In natural parameters, $\boldsymbol{\theta}_\ell\new = \delta(\overline{\boldsymbol{\theta}}\new - \boldsymbol{\theta}\scav{\ell})+(1-\delta)\boldsymbol{\theta}_\ell$.

Only the tilted distribution of the utility site is an explicit function of actions $a$, presenting the only opportunity to optimize actions $a$ during LossEP. Performing action selection at this site maximizes the $q$-gain, which is consistent with other loss-calibrated methods, albeit motivated more naturally in this context. Critically though, loss-calibration is still occuring at all site updates, as the Gaussian approximation to the utility $\tilde t_\ell(\param)$ is present in every cavity distribution $q\scav{i}(\param)$, and it contains information about the decision-making process.

Given: Dataset of $N$ i.i.d. datapoints $\data=\{\bx_i,y_i\}$, Model with posterior over parameters $p(\param\mid\data)$ that admits factorization of the form $p(\param\mid\data)\propto p_0(\param) \prod_i t_i(\param)$, Decision problem with utility function $\util(a(\cdot),\cdot)$
Initialize site approximations $\tilde t_i(\param)$ and $\tilde t_\ell(\param)$ s.t. $\overline{q}(\param)=p_0(\param)\prod_{i=1}^N \tilde t_i(\param)\tilde t_\ell(\param)$ approximates the utility-weighted posterior $p(\param\mid\data)\Util(a,\param)$
In random order:
For each $n$
(Deletion) Compute the cavity distribution $q\scav{i}(\param)=\overline{q}(\param)/\tilde t_i(\param)$
(Projection) Minimize $\overline{q}^{\text{new}}(\param)=\proj[t_i(\varphi)q\scav{i}(\param)]$ by matching moments
(Update) Back out the site update $\tilde t_i^\text{new}(\param)=(q^{\text{new}}(\param)/q\scav{i}(\param))^\delta\cdot \tilde t_i(\param)^{1-\delta}$
For $\ell$
(Deletion) Compute the cavity distribution $q\cav{\ell}(\param)=\overline{q}(\param)/t_\ell(\param)$
(Action Selection) Select the $q\scav{\ell}$-optimal actions $a_{q}={\arg\max}_a\:\EEutil_{q\cav{\ell}}(a)$
(Projection) Minimize $\overline{q}^{\text{new}}(\param)=\proj[U(a_q, \param)q\scav{\ell}(\param)]$ by matching moments
(Update) Back out the site update $\tilde t_\ell^\text{new}(\param)=(\overline{q}^{\text{new}}(\param)/q\scav{\ell}(\param))^\delta\cdot \tilde t_\ell(\param)^{1-\delta}$

Loss-calibrated expectation propagation

§.§ Example: the clutter/nuclear reactor problem

To illustrate loss-calibration, we repurpose the “nuclear reactor” problem used by [Lacoste-Julien et al., 2011] and [Abbasnejad et al., 2015] in those works on loss calibration. Conveniently, this decision problem can be superimposed on the generative model of the clutter problem used in [Minka, 2001] in that work on expectation propagation. We consider a decision-maker receiving noisy measurements of the temperature $\param$ of a nuclear reactor, tasked with shutting it down ($a=1$) if that temperature has exceeded a “meltdown” point ($\varphi>T_\text{crit}$) or leaving it on ($a=0$) otherwise. Defining $\util_{ij}$ as the utility received for taking action $a=i$ when the state $\II[\varphi>T_\text{crit}]=j$ was true [Poor, 2013], this decision problem features a natural asymmetry, with a maximal penalty for the False Negative case of leaving it on during a meltdown ($\util_{01}= 0$) and a modest penalty for the False Positive of shutting down despite normal operation ($\util_{10}$).

After a small number of observations, suppose we have a complicated, bimodal posterior distribution $p(\param\mid\data)$ with the minor mode informing a potential meltdown (Figure 1). Under a Gaussian approximation, we may underrepresent or ignore this probability mass, and select the suboptimal action of “leaving it on” when the Bayes-optimal action is to “shut it down” (see figure legend). For not only VI and EP but also LossVI, this is exactly what happens (Figure 1; blue curves). Only LossEP captures the tail and can select the Bayes-optimal action (Figure 1; red curves). It is a poor visual approximation of the true posterior, but when our goal is decision-making, this is not important.

Nuclear reactor decision problem for a small dataset observed under the clutter problem. A decision-maker must act to leave the reactor running or shut it down, based on whether the true mean temperature, inferred from that dataset, is greater than a critical meltdown threshold. Given this bimodal posterior distribution (black), the optimal action shuts it down (see legend, $a_\text{opt}=1$). However, the Gaussian approximations from VI, LossVI, and EP (pale blue, dark blue, and pale red, resp.) do not capture the second mode and do not select this action ($a_q=0$). The Gaussian approximation from LossEP (dark blue) skews to overrepresent the second mode, and selects the optimal action ($a_q=1$).

§ APPLICATIONS TO DATA WITH GAUSSIAN PROCESS MODELS

We explore the differences in the approximations achieved between loss-calibrated EP and standard EP, as well as VI and LossVI, using a simulated decision-making problem with asymmetric utility functions. When the inference and/or decision-making is difficult enough to yield loss of information and/or ambiguous predictions, we suspect that our loss-calibrated methods will be most differentially successful. We use Gaussian process classification in all cases for its analytical tractability. We present two applications: the first is a minimal two-point dataset [Nickisch and Rasmussen, 2008] to visualize the various approximations, and the second a sweep of different utility functions and predictive datasets [Lacoste-Julien et al., 2011]. Together, they show that loss-calibration—at least within this context—can yield modest increases in performance, as measured by utility.

We implement all of EP, and LossEP in python using JAX [Bradbury et al., 2018], and MCMC, VI, and LossVI in numpyro [Phan et al., 2019, Bingham et al., 2019].
To begin, we derive the relevant equations for loss-calibrated inference in the GP context, with notation following Rasmussen and Williams, 2005.

§.§ Approximate inference and loss-calibration for Gaussian process classifiers

Approximate inference in GP classification provides an approximation to the intractable posterior $p(\bff\mid X, \by)\xrightarrow{\text{approx.}}q(\bff\mid X,\by)=\Nrm(\bff;\, \bmu_q, \Sigma_q)$, where the latent function at the observed datapoints $\bff$ assumes the role of the parameters $\param$. We assume the probit likelihood model throughout such that all integrals can be resolved in closed-form. The prior, likelihood, and posterior take the form

p(|X)    = (;  0, ),  p(|) = ∏_i=1^N Φ(y_i f_i),  p(|X, ) = p(|)p(|X)/p(|X)

where $K$ is the covariance kernel which, in our case, is the radial basis function kernel defined by

K_ij=k_ξ(_i, _j)=σ^2exp(- _i-_j^2_2 / 2ℓ^2)

with variance and lengthscale hyperparameters $\xi=\{\sigma^2,\ell\}$. To make predictions for latent function values outside the dataset, we can marginalize the product of any approximation $q(\bff)$ and the conditional distribution, yielding the posterior predictive distribution.

p_q(|X, , )    = ∫d  p(|X, , ) q(|X, ) = (;  m_, v_)

where  m_    = _q

v_    = -+Σ_q

and $\ksx$ is the predictive covariance kernel, with ${\ksx}_j = k_\xi(\bxs, \bx_j)$.

The expected utility depends on the marginal predictive distribution, which is available in closed-form for the probit likelihood. As above, we marginalize the product of the probit likelihood and the posterior predictive distribution, yielding

p_q(|X, , )    = ∫d  p(|) p_q(|X, , ) = Φ(·m_/√(1+v_) )

For action selection in GPC, we can rearrange the order of integration in  (<ref>) of the conditional expected utility in (<ref>), reducing it to a single integral of this predictive likelihood and the utility function [Vehtari et al., 2012], which decomposes into four pieces for each of the four outcomes. We define them as $u_{00}$, $u_{01}$, $u_{10}$, and $u_{11}$, where $u_{ij}$ is the utility of selection action $i$ when outcome $j$ occurred [Poor, 2013].

_q(a()|)    = ∫d p_q(|,X, ) (,a())

= [a=+1](u_10Φ(-z)+u_11Φ(z)) + [a=-1](u_00Φ(-z)+u_01Φ(z))

where  z=m_/√(1+v_)

and $\II[\cdot]$ is an indicator function with value $1$ if the condition is true and $0$ otherwise. The conditional expected utility, when minimized pointwise, minimizes the full expected utility [Berger, 2013]. No matter the procedure for selecting $q(\bff)$, we select actions by minimizing this term, which generates the following $q$-action in closed form:

a_q()    = sign(m_/√(1+v_) - b),  b=Φ(u_00 - u_10/(u_00- u_10) - (u_01- u_11))

The "bias" $b$ reflects the asymmetry of the utilities, and acts to move the decision boundary / threshold up if its more favorable to select $-1$ or down if its more favorable to select $+1$.

§.§ Visualizing a two-point dataset

Suppose we had a dataset of only two points, $\data=\{(-\sqrt{2},-1), (\sqrt{2},+1)\}$. In this case, we can compute the exact posterior $p(\bff\mid X,\by)$ on a grid and plot it against the various approximations. We select hyperparameters $\log \sigma=1.5$ and $\log \ell=1.0$ (cf. [Nickisch and Rasmussen, 2008], Figs. 3, 4) and a decision problem with an asymmetric utility function: $u_{00}=u_{11}=1.0$, $u_{01}=0.0$, and $u_{10}=0.5$ (cf. [Lacoste-Julien et al., 2011], Table 4).

Together, these induce a non-Gaussian posterior—the product of a joint Gaussian prior with steep, sigmoidal likelihoods yields a posterior with tails strongly skewed into one quadrant. The predictive utility skews this posterior very slightly towards the upper right quadrant, as overestimating the latent function's values is more favorable under the utility function which disproportionately penalizes underestimating (Fig. <ref>A). Compared to standard EP and VI, their loss-calibrated counterparts do not modify the means, and LossEP increases the covariance estimate (Fig. <ref>C).

Loss-calibrated approximate inference for GP classification on a two-point dataset.  A, The utility-weighted posterior approximated by loss-calibration, achieved by multiplying the jointly Gaussian GP prior and the probit likelihood for the two datapoints, $(-\sqrt{2}, -1)$ and $(\sqrt{2},+1)$, and the predictive utility. B, Approximations to the posterior for VI (pale blue) EP (pale red), and to the utility-weighted posterior for loss-calibrated VI (dark blue) and loss-calibrated EP (dark red).

§.§ Assessing the impact of loss-calibration under asymmetric utilities

We continued with a quantitive performance test of Loss-EP versus EP as well as Loss-VI and VI (Table <ref>). We simulated datasets as $N=15$ datapoints $\bx_i$ sampled uniformly from $[-10, 10]$, followed by draws from the GP prior and binary observations $y_i$ under the GPC model with hyperparameters as above. Action selection was performed for each of five increasingly asymmetric utility functions, with the False Negative utility always taking the minimum-possible value $u_{01}=0.0$ and the False Positive utility ranging from minimum-possible $u_{10}=0.0$ to nearly maximum-possible $u_{10}=0.95$. Utilities were evaluated at 1000 predictive datapoints uniformly sampled from each of $[-10, 10]$, $[-8, 12]$, or $[-5, 15]$, increasing covariate shift from the observed datasets. Using this finite dataset for prediction can be viewed in the transductive scenario in which we are interested in evaluating the utility at these points. This is beneficial, as it reduces the unknown data-generating distribution $p(\bxs)$ to a trivial “comb” distribution over that dataset $p(\bxs)=\sum_{c} \delta(\bxs - {\bxs}_c)$. The resulting experiment is identical to that used in [Lacoste-Julien et al., 2011].

The performance is the full expected utility $\EEutil_p(a_q)$ of the actions selected under any of the four approximations $q$: EP, Loss-EP, VI, and Loss-VI. This utility is at best $\EEutil_p(a_\text{opt})$—the utility of the Bayes-optimal action—and is at worst $\EEutil_p(-a_\text{opt})$—the utility of always taking the opposite of the Bayes-optimal action. The following metric normalizes the utility discrepancy in eq. (<ref>) from $0$ to $1$:

U(q) = _p(a_opt) - _p(a_q)/_p(a_opt) - _p(-a_opt)

Different datasets vary in their best-case and worst-case expected utilities, and the metric permits meaningful averaging across datasets. We report this utility metric for each inference method, utility function, and covariate shift as averages over 20 simulated datasets each in Table <ref>.

Recall that the motivation of loss-calibrated approximate inference was that the expected utility $\EEutil_p(a_\text{opt})$ is difficult to compute. For GPC, we can compute it using MCMC [Hoffman and Gelman, 2014], generating samples $\bff\sim p(\bff\mid X, \by)$ and computing an sample-based estimate of the conditional expected utility in (<ref>). Averaging over the dataset defining $p(\bxs)$, we recover an estimate of $\EEutil_p(a)$.

We can either optimize this function for $a$ to estimate $a_\text{opt}$ (and $-a_\text{opt}$) or plug in $a_q$ for one of the approximations $q$ to estimate $\widetilde{U}(q)$ for each of VI, LossVI, EP, and LossEP.

All methods report near-ceiling performance across all utility functions and degrees of predictive covariate shift, though EP and LossEP consistently outperform VI and LossVI by several orders of magnitude (Table <ref>). While LossVI does not outperform VI in any case, LossEP offers very small improvements over EP when the utility asymmetry is moderate and covariate shift is not large, echoing the results visualized in the previous section and those observed by [Lacoste-Julien et al., 2011] in their original report. No differences between EP and Loss-EP or VI and Loss-VI were significant by a Wilcoxon signed-rank test after corrections for multiple comparisons.

Performance comparison of loss-calibrated methods on simulated datasets. Expected utility from actions selected under approximate posterior distributions from each of VI, loss-calibrated VI, EP, and loss-calibrated EP, for utility functions of increasing asymmetry and predictive datasets with increasing covariate shift. Performance is reported using the normalized expected utility metric in eq. (<ref>), averaged over 20 repeats of the simulation. Zero is Bayes-optimal performance, and does not mean perfect performance. EP is consistently better than both VI-type methods, and LossEP is better still for moderate utility asymmetries. Bolded results are best performances within each experimental category.

§ DISCUSSION AND FUTURE WORK

With this paper, we introduced loss-calibrated expectation propagation, diversifying the suite of loss-calibrated inference methods to include the message-passing-like iterative computations of EP. We showed that the factorization of the posterior distribution approximated by EP can be repurposed to a factorization of the expected utility, and appends one site factor to the resultant approximation: $\tilde t_\ell(\param)$ which approximates the predictive utility function $\Util(a,\param)$. When iteratively updating all data site factors $\tilde t_i(\param)$, the utility site factor $\tilde t_\ell(\param)$ is included in all cavity distributions $q\scav{i}(\param)$, making all sites “aware” of the utility function. When iteratively updating the utility site itself, the tilted distribution's log-normalizer is precisely the $q$-expected utility, providing a principled justification of optimizing $\EEutil_q(a)$ as a surrogate for the true expected utility $\EEutil_p(a)$. As a bonus, action selection can be transparently performed within this site update.
In these ways, Loss-EP shares the elegant, intuitive, and desirable theoretical foundations of loss-calibrated approximate inference more broadly.

That said, it also shares the situational, modest performance increases in practice observed in previous works, which spans not only Gaussian process models [Lacoste-Julien et al., 2011] but also Bayesian neural networks [Cobb et al., 2018] and continuous-valued estimation tasks [Kusmierczyk et al., 2019] not considered here. Using any EP-type approximation, loss-calibrated or not, does grant dramatic performance improvements, however, and is an important, novel observation from our efforts.
Curiously, we observe that there is likely more than one way to develop a loss-calibrated inference procedure around the flexible machinery of expectation propagation, and future work could better harness the desirable computational properties commonly associated with EP to improve performance.

Following [Kuśmierczyk et al., 2020], future work could develop an EP-type approximation to Generalized Bayesian Inference [Bissiri et al., 2016], which updates prior beliefs about a parameter of interest that is connected to our observations by arbitrary loss functions, rather than likelihood functions. Following the substantial body of theory work into loss functions and machine learning [Reid and Williamson, 2011], we could perform iterative EP updates that minimize not the KL divergence, but instead some general divergence measure (also suggested in [Vehtari et al., 2020]) that is uniquely determined by the loss function in the classification case. This could be considered optimization in the natural “geometry” of the decision problem [Dawid and Lauritzen, 2005], of which a certain subclass of problems are well-defined [Dawid, 1994].

§.§ Related work

Loss-calibrated approximate inference is only one family of approaches for “loss-aware” model learning. Direct loss minimization [Wei et al., 2021] directly minimizes expected loss, but in a constrained optimization akin to rate-distortion theory [Cover, 1999], which has a natural connection to variational inference [Alemi et al., 2018]. Accuracy-versus-uncertainty calibration [Krishnan and Tickoo, 2020] provides a heuristic objective for training deep networks to enforce better-calibrated estimators. Target-aware Bayesian inference [Rainforth et al., 2020] formalizes an sampling-based approach to estimating the expected utility with importance sampling (IS). Loss-calibrated Monte Carlo action selection [Abbasnejad et al., 2015] also optimizes an importance sampling proposal distribution, but minimizing the probability of selecting suboptimal actions with minimal number of samples.

This last work echoes the deep theory of surrogate loss functions from statistical learning theory, which minimize a bound on the generalization error (equivalently, the 0-1 loss, or the probability of error) that depends directly on the utility/loss function of the decision problem [Bartlett et al., 2006, Steinwart and Christmann, 2008, Reid and Williamson, 2011]. Nguyen et al., 2009 even select actions according to an approximation, and such results hinge on an expected loss over datasets. In contrast, our complementary Bayesian viewpoint has emphasized how to make optimal decisions conditionally on a given dataset rather than in expectation over all possible datasets.

§ BROADER IMPACT

Optimal decision-making under specific design constraints (as represented by a utility function and/or tolerances on error rates) is a fundamental aspect of fair and safe applications of ML to real-world data. While loss-calibration as we present it here is a generic theoretical tool, principles such as these could be leveraged to better-constrain the decision-making faculties of modern Bayesian ML tools. For example, it could be productive for researchers to think explicitly about the costs/utilities of decision-making in their applications at inference time. Because Bayesian decision theory only prescribes optimal decision-making under exact Bayesian inference, a modernized theory will be critical as approximate methods for complex models become more and more prevalent.

MJM was supported by an NSF Graduate Research Fellowship.

[Von Luxburg et al., 2012]
Ulrike Von Luxburg, Robert C Williamson, and Isabelle Guyon.
Clustering: Science or art?
In Proceedings of ICML workshop on unsupervised and transfer
learning, pages 65–79. JMLR Workshop and Conference Proceedings, 2012.

[Berger, 2013]
James O Berger.
Statistical decision theory and Bayesian analysis.
Springer Science & Business Media, 2013.

[Lacoste-Julien et al., 2011]
Simon Lacoste-Julien, Ferenc Huszár, and Zoubin Ghahramani.
Approximate inference for the loss-calibrated bayesian.
In Proceedings of the Fourteenth International Conference on
Artificial Intelligence and Statistics, pages 416–424. JMLR Workshop and
Conference Proceedings, 2011.

[Blei et al., 2017]
David M Blei, Alp Kucukelbir, and Jon D McAuliffe.
Variational inference: A review for statisticians.
Journal of the American statistical Association, 1120
(518):0 859–877, 2017.

[Kusmierczyk et al., 2019]
Tomasz Kusmierczyk, Joseph Sakaya, Arto Klami, et al.
Variational bayesian decision-making for continuous utilities.
Advances in Neural Information Processing Systems 32 (NIPS
2019), 2019.

[Minka, 2001]
Thomas P Minka.
Expectation propagation for approximate bayesian inference.
In Proceedings of the Seventeenth conference on Uncertainty in
artificial intelligence, pages 362–369, 2001a.

[Minka, 2001]
Thomas Minka.
The ep energy function and minimization schemes.
www. stat. cmu. edu/minka/papers/learning. html,

[Vehtari et al., 2020]
Aki Vehtari, Andrew Gelman, Tuomas Sivula, Pasi Jylänki, Dustin Tran,
Swupnil Sahai, Paul Blomstedt, John P Cunningham, David Schiminovich, and
Christian P Robert.
Expectation propagation as a way of life: A framework for bayesian
inference on partitioned data.
J. Mach. Learn. Res., 21:0 17–1, 2020.

[Seeger, 2005]
Matthias Seeger.
Expectation propagation for exponential families.
Technical report, 2005.

[Nielsen and Garcia, 2009]
Frank Nielsen and Vincent Garcia.
Statistical exponential families: A digest with flash cards.
arXiv preprint arXiv:0911.4863, 2009.

[Abbasnejad et al., 2015]
Ehsan Abbasnejad, Justin Domke, and Scott Sanner.
Loss-calibrated monte carlo action selection.
In Proceedings of the AAAI Conference on Artificial
Intelligence, volume 29, 2015.

[Poor, 2013]
H Vincent Poor.
An introduction to signal detection and estimation.
Springer Science & Business Media, 2013.

[Nickisch and Rasmussen, 2008]
Hannes Nickisch and Carl Edward Rasmussen.
Approximations for binary gaussian process classification.
Journal of Machine Learning Research, 90
(Oct):0 2035–2078, 2008.

[Bradbury et al., 2018]
James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary,
Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye
Wanderman-Milne, and Qiao Zhang.
JAX: composable transformations of Python+NumPy programs,
URL <http://github.com/google/jax>.

[Phan et al., 2019]
Du Phan, Neeraj Pradhan, and Martin Jankowiak.
Composable effects for flexible and accelerated probabilistic
programming in numpyro.
arXiv preprint arXiv:1912.11554, 2019.

[Bingham et al., 2019]
Eli Bingham, Jonathan P. Chen, Martin Jankowiak, Fritz Obermeyer, Neeraj
Pradhan, Theofanis Karaletsos, Rohit Singh, Paul A. Szerlip, Paul Horsfall,
and Noah D. Goodman.
Pyro: Deep universal probabilistic programming.
J. Mach. Learn. Res., 20:0 28:1–28:6, 2019.
URL <http://jmlr.org/papers/v20/18-403.html>.

[Rasmussen and Williams, 2005]
Carl Edward Rasmussen and Christopher KI Williams.
Gaussian processes for machine learning, 2005.

[Vehtari et al., 2012]
Aki Vehtari, Janne Ojanen, et al.
A survey of bayesian predictive methods for model assessment,
selection and comparison.
Statistics Surveys, 6:0 142–228, 2012.

[Hoffman and Gelman, 2014]
Matthew D Hoffman and Andrew Gelman.
The no-u-turn sampler: adaptively setting path lengths in hamiltonian
monte carlo.
J. Mach. Learn. Res., 150 (1):0 1593–1623,

[Cobb et al., 2018]
Adam D Cobb, Stephen J Roberts, and Yarin Gal.
Loss-calibrated approximate inference in bayesian neural networks.
arXiv preprint arXiv:1805.03901, 2018.

[Kuśmierczyk et al., 2020]
Tomasz Kuśmierczyk, Joseph Sakaya, and Arto Klami.
Correcting predictions for approximate bayesian inference.
In Proceedings of the AAAI Conference on Artificial
Intelligence, volume 34, pages 4511–4518, 2020.

[Bissiri et al., 2016]
Pier Giovanni Bissiri, Chris C Holmes, and Stephen G Walker.
A general framework for updating belief distributions.
Journal of the Royal Statistical Society. Series B, Statistical
methodology, 780 (5):0 1103, 2016.

[Reid and Williamson, 2011]
Mark D Reid and Robert C Williamson.
Information, divergence and risk for binary experiments.
Journal of Machine Learning Research, 12:0 731–817,

[Dawid and Lauritzen, 2005]
A Philip Dawid and Steffen L Lauritzen.
The geometry of decision theory.
In Proceedings of the Second International Symposium on
Information Geometry and its Applications, pages 22–28. University of
Tokio, 2005.

[Dawid, 1994]
A Philip Dawid.
Proper measures of discrepancy, uncertainty and dependence, with
applications to predictive experimental design.
Technical report, Technical Report 139, Department of Statistical
Science, University College …, 1994.

[Wei et al., 2021]
Yadi Wei, Rishit Sheth, and Roni Khardon.
Direct loss minimization for sparse gaussian processes.
In International Conference on Artificial Intelligence and
Statistics, pages 2566–2574. PMLR, 2021.

[Cover, 1999]
Thomas M Cover.
Elements of information theory.
John Wiley & Sons, 1999.

[Alemi et al., 2018]
Alexander Alemi, Ben Poole, Ian Fischer, Joshua Dillon, Rif A Saurous, and
Kevin Murphy.
Fixing a broken elbo.
In International Conference on Machine Learning, pages
159–168. PMLR, 2018.

[Krishnan and Tickoo, 2020]
Ranganath Krishnan and Omesh Tickoo.
Improving model calibration with accuracy versus uncertainty
Advances in Neural Information Processing Systems, 33, 2020.

[Rainforth et al., 2020]
Tom Rainforth, A Goliński, Frank Wood, and Sheheryar Zaidi.
Target–aware bayesian inference: how to beat optimal conventional
Journal of Machine Learning Research, 210 (88), 2020.

[Bartlett et al., 2006]
Peter L Bartlett, Michael I Jordan, and Jon D McAuliffe.
Convexity, classification, and risk bounds.
Journal of the American Statistical Association, 1010
(473):0 138–156, 2006.

[Steinwart and Christmann, 2008]
Ingo Steinwart and Andreas Christmann.
Support vector machines.
Springer Science & Business Media, 2008.

[Nguyen et al., 2009]
XuanLong Nguyen, Martin J Wainwright, Michael I Jordan, et al.
On surrogate loss functions and f-divergences.
The Annals of Statistics, 370 (2):0 876–904,

§ SUPPLEMENTAL MATERIALS FOR: LOSS-CALIBRATED EXPECTATION PROPAGATION FOR APPROXIMATE BAYESIAN DECISION-MAKING

§ ANALYTICAL EP AND LOSS-EP UPDATES FOR THE CLUTTER/REACTOR PROBLEM

Here, we describe EP and Loss-EP for the clutter and reactor examples that we use in Fig. <ref>.

The "clutter problem" was the guiding example used by Minka in the original paper introducing expectation propagation, and consequently is often the gateway example for hopeful users of EP. In practice, the clutter problem is a two-component Bayesian mixture-of-Gaussians, with all parameters fixed in advance except for the latent mean of one of the components. In this way, inference in the clutter problem can be conceptualized as both a signal detection and/or latent variable model, in which we learn from noisy observations the mean of a signal buried amongst "clutter" (noise).

We define the observations as $y$, the signal mean as $\param$, the proportion of clutter as $\pi$, and the clutter variance as $v_c$. The resulting likelihood function for $y\mid\param$, alongside a Gaussian prior over $\param$, defines the clutter problem's generative model:

p_0()    = (;  0, v_0)

p(y|)    = (1-π)(y;  , 1) + π(y;  0, v_c)

where $\Nrm(\param; a, A)$ defines a Gaussian distribution over $\param$ with mean $a$ and variance $A$. We use the same values used by Minka: $\pi=0.5$, $v_c=10$, and $v_0=100$ (a non-informative prior); however, we assume scalar observations to simplify algebra and visualization.

The clutter problem is deceivingly simple to write down. However, given a dataset of observations $\data=\{y_i\}_{i=1}^N$, the posterior is a mixture of $2^N$ Gaussians[To see why, note that the total data likelihood is $\prod_i\left((1-\pi)\Nrm(y_i;\, \param, 1) + \pi\Nrm(y_i;\, 0, v_c)\right)$ which, if we multiply out each binomial, yields $2^N$ terms of the form $c\cdot\Nrm(y\; ...)\Nrm(y\; ...)$.], and it is exponentially difficult to compute exact moments e.g., if attempting belief propagation, as was the motivation for EP at the time. This posterior becomes the target of our EP approximation:

p(|𝒟) = 1/Zp_0() ∏_i p(_i|)    ∝p_0() ∏_i t_i()

≈p_0() ∏_i t̃_i() = q()

where $t_i(\param)$ is the exact likelihood factor in (<ref>), $\tilde{t}_i(\param)=\Nrm(\param;\, m_i, v_i)$ is its Gaussian approximate factor in the EP approximation. The prior $p_0(\param)$ is Gaussian and needs no approximation.

EP in the clutter problem can be performed analytically. We present the Deletion-Projection-Update steps using the mean and variance $(m, v)$ on the left, and using the natural and mean parameters $(\nat, \Nat)$ and $(\mean, \Mean)$, resp., on the right to emphasize the exponential family perspective. Note that only (<ref>) and its gradients are specific to the clutter problem; the rest is fully general.

\begin{equation}
\begin{aligned}[t]
q\scav{i}(\param) &= q(\param)\,/\, \tilde{t}_i(\param) \\
v\scav{i} &= \left(v\inv - v_i\inv\right)\inv \\
m\scav{i} &= v\scav{i}\left(v\inv m - v_i\inv m_i\right)
\end{aligned}
\qquad
\begin{aligned}[t]
q\scav{i}(\param) &= q(\param)\,/\, \tilde{t}_i(\param) \\
\Nat\scav{i} &= \Nat - \Nat_i \\
\nat\scav{i} &= \nat - \nat_i
\end{aligned} \label{eq:clutter-deletion}
\end{equation}

The projection step hinges on the log-normalizer of the tilted distribution, which for the clutter problem is given by

Z_i = ∫d  qi()p(_i|)    = ∫d  (;  mi, vi)((1-π)(y;  , 1) + π(y;  0, v_c) )

= (1-π)(y;  mi, 1+vi) + π(y;  0, v_c)

where the first term follows from the following Gaussian refactoring of prior-times-likelihood into evidence-times-posterior. We can then integrate out the posterior:

— Multiplication of two Gaussians (prior $\times$ likelihood = evidence $\times$ posterior)

(x;  a, A)(x;  b, B)    = (x;  a, A)(b;  x, B)  (symmetry)

= (a; b, A+B)(x;  B(A+B)a+A(A+B)b, A(A+B)B)

\begin{equation}
\begin{aligned}[t]
q\new(\param) &= \proj\big[q\scav{i}(\param)p(\data_i\mid\param)\big] \\
m\new &= m\scav{i} + v\scav{i}\nabla_{m\scav{i}}\log Z_i \\
v\new &= v\scav{i} + v\scav{i}\left(2\nabla_{v\scav{i}}\log Z_i - (\nabla_{m\scav{i}}\log Z_i)^2\right)v\scav{i}
\end{aligned}
\qquad
\begin{aligned}[t]
q\new(\param) &= \proj\big[q\scav{i}(\param)p(\data_i\mid\param)\big] \\
\mean\new &= \mean\scav{i} + \nabla_{\nat\scav{i}}\log Z_i \\
\Mean\new &= \Mean\scav{i} + \nabla_{\Nat\scav{i}}\log Z_i
\end{aligned} \label{eq:clutter-projection}
\end{equation}

The projection operator $\proj$ is a common shorthand for KL divergence minimization, i.e. $\proj[p(\param)]=\arg\min_q D_{KL}(p(\param)\,\|\,q(\param))$, which for an exponential family $q$ is equivalent to moment-matching to $p$. These moments, which we represent as the mean parameters of $q$, take the form above due to specific exponential family properties similar to exponential tilting <cit.>. We can manually compute the gradients of the $log$ of (<ref>) to yield analytical updates

m   = mi + vi·r_i y_i-mi/1+vi

v   = vi - vi^2·(r_i 1/1+vi - r_i(1-r_i) (y_i-mi)^2/(1+vi)^2)

and  r_i=1-π/Z_i(y_i; mi, 1+vi)

In practice, we found it easier and more concise to compute automatic gradients with modern ML tools such as  directly on (<ref>), but we provide these analytical solutions in terms of mean and variance for completeness. Because these are very short expressions, we observed that the automatic gradients were accurate up to numerical precision.

\begin{equation}
\begin{aligned}[t]
\tilde{t}_i\new(\param) &= (q\new(\param)\,/\, q\scav{i}(\param))^\delta\cdot \tilde{t}_i(\param)^{1-\delta} \\
v_i\new &= (\delta(v^{\text{new},-1}- v^{\backslash i,-1})+(1-\delta)v_i\inv)\inv \\
m_i\new &= v_i\new(\delta(v^{\text{new},-1}m\new- v^{\backslash i,-1}m\scav{i}) \\
&\quad- (1-\delta)v_i\inv m_i)
\end{aligned}
\qquad
\begin{aligned}[t]
\tilde{t}_i\new(\param) &= (q\new(\param)\,/\, q\scav{i}(\param))^\delta\cdot \tilde{t}_i(\param)^{1-\delta} \\
\Nat_i\new &= \delta(\Nat\new - \Nat\scav{i})+(1-\delta)\Nat_i \\
\nat_i\new &= \delta(\nat\new - \nat\scav{i})+(1-\delta)\nat_i
\end{aligned} \label{eq:clutter-update}
\end{equation}

The "reactor problem" is the guiding example used by Lacoste-Julien et al. in the original paper introducing loss-calibrated approximate inference, and conveniently sits atop the clutter problem with no modifications necessary. The reactor problem assigns a binary utility/cost function to whether a signal—putatively the internal temperature of a nuclear reactor—is above or below a critical "meltdown" temperature, and whether a user acts to keep the system on or turn it off. This real-world framing motivates use of a highly asymmetric utility/cost, in which it is catastrophically costly to keep the system on when the internal temperature is critical.

Atop the clutter problem, this temperature can be the latent mean itself $\param$. We define the utility of a true negative $\Util(\param<\Tcrit, a=\text{keep on})=L_0$, a false positive $\Util(\param<\Tcrit, a=\text{turn off})=L_1,$ a true positive $\Util(\param\ge\Tcrit, a=\text{keep on})=H_1$, and a false negative $\Util(\param\ge\Tcrit, a=\text{turn off})=H_0$. Following Abbasnejad et al., we choose $H_0\ll L_1 \le L_0 < H_1$, with the notational convenience $H_a$ to equal $H_1$ if $a=1$ and $H_0$ if $a=0$.

Note that the clutter problem would defines $\Util(a, \param)$ directly with a single action $a$ over the entire dataset. We do not have a utility function of the form $\util(a(\cdot), \ys)$ with an action function as used in the main text. In essence, we infer: does this dataset $\data$ reflect a single latent signal whose mean "temperature" $\param$ is above the critical threshold $\Tcrit$? Clearly, this is a function of the posterior $p(\param\mid\data)$ that we are approximating with EP.

For loss-calibrated EP in the reactor problem, the only major change from the clutter problem is the projection step at the utility site (cf. Section 3, main text). This extension can substantially complicate computation in more elaborate decision problems, but reduces to a sum of Gaussian CDFs in our case.

Projection with loss-calibration:
The projection step still hinges on the log-normalizer of the utility-tilted distribution, which for the reactor problem is given by

Z_ℓ   = ∫d  qi()U(a, )

= L_a·∫_-∞^ d  (;  mℓ, vℓ) + H_a·∫_^∞ d  (;  mℓ, vℓ)

= L_a·Φ(; mℓ,vℓ) + H_a·(1-Φ(; mℓ,vℓ))

The shorthand $\Phi(\tau;\, c, C)=\int_{-\infty}^\tau dy\,\Nrm(y;\, c,C)$ is the normal cdf with mean $c$ and [co]variance $C$, evaluated at $\tau$. With an analytic form for the utility-tilted distribution, we can compute automatic gradients as above and use the same projection equations in (<ref>). Deletion and update computations are identical to those in (<ref>) and (<ref>), respectively.


# Internet Congestion Control Benchmarking

Soheil Abbasloo

(2023)

###### Abstract.

How do we assess a new Internet congestion control (CC) design? How do we
compare it with other existing schemes? Under what scenarios and using what
network parameters? These are just a handful of simple questions coming up
every time a new CC design is going to be evaluated. Interestingly, the number
of specific answers to these questions can be as large as the number of CC
designers. In this work, we aim to highlight that the network congestion
control, as a hot and active research topic, requires a crystal clear set(s)
of CC Benchmarks to form a common ground for quantitatively comparing and
unambiguously assessing the strengths and weaknesses of a design with respect
to the existing ones. As a first step toward that goal, we introduce general
benchmarks that can capture the different performance of the existing Internet
CC schemes. Using these benchmarks, we rank the Internet CC algorithms and
illustrate that there is still lots of room for more innovations and
improvements in this topic.

††copyright: none††copyright: acmcopyright††copyright: acmlicensed††copyright:
rightsretained††copyright: usgov††copyright: usgovmixed††copyright:
cagov††copyright: cagovmixed††journalyear: 2023††copyright:
acmcopyright††conference: ; 2023; Canada††price: 15.00††doi:
10.1145/3387514.3405892††isbn: 978-1-4503-7955-7/20/08

##  1\. Introduction

###  1.1. Setting the Context

After about four decades of the first series of ”congestion collapses” (Nagle,
1984) in the Internet and one of the first CC designs (Jacobson, 1988),
controlling congestion in the network remained a hot, active, and challenging
topic that attracts new designs every year (Abbasloo et al., 2020, 2021; Arun
and Balakrishnan, 2018; Cardwell et al., 2019; Ha et al., 2008; Henderson et
al., 2012; Yan et al., 2018; Jay et al., 2019; Winstein et al., 2013; Winstein
and Balakrishnan, 2013; Dong et al., 2018; Floyd, 2003; Fu and Liew, 2003;
Caini and Firrincieli, 2004; Rossi et al., 2010; Hayes and Armitage, 2011;
Baiocchi et al., 2007; Katabi et al., 2002; Baiocchi et al., 2007; Zaki et
al., 2015; Park et al., 2018; Abbasloo et al., 2019b; Abbasloo et al., 2018;
Yen et al., 2023). One of the main reasons behind the importance of this topic
is the fact that CC algorithms directly impact the end-user quality of
experience. That is why the improvements of the underlying network
technologies, the arrival of new applications, and the changes in the end-
users demands always push the community toward introducing better CC designs.
Although there is a consensus on the need for novel CC designs in the
community, when it comes to how to identify better ones and questions such as
how we assess a new CC algorithm, how we compare it with other existing
designs, under what network scenarios, and using what network parameters,
there still is a lack of crystal clear consensus among the community. In other
words, we lack useful benchmark(s) in the community to have clear, fair, and
universal comparisons between various CC algorithms.

###  1.2. Motivations

The Benchmarking in Other Communities: Using benchmark(s) to assess the
performance of a new algorithm (or simply put: benchmarking it) is a very
primary and common mechanism that has worked as a cornerstone for driving the
innovation in different communities spanning from machine learning (ML) to
hardware communities. For example, the ImageNet benchmark (Deng et al., 2009;
Krizhevsky et al., 2017, 2012; Russakovsky et al., 2015) has been widely
recognized for boosting innovation in the deep learning context and
stimulating competition for improving computer image analysis. Among other
examples of established simple benchmarks that are used enormously in the ML
literature especially in the reinforcement learning topic either for testing
the functionality of algorithms or positioning them among existing ones, the
HalfCheetah, Hopper, Walker2d, Swimmer, Ant, and Humanoid benchmarks can be
named (Brockman et al., 2016).

From the CC Reviewers/Critics’ Perspective: When reviewing a CC work, usually,
one of the main questions that a reviewer faces is whether the new scheme is
evaluated in a fair manner compared to the existing CC schemes. The general
tendency of the designers to show the good aspects of their new CC designs can
unintentionally impact the scenarios or network parameters they use for
highlighting the benefits of their design compared to the existing ones. In
other words, the issue is about the scope of the evaluations and making sure
that the presented results are representative enough and not cherry-picked in
the worst case.

To show that, we perform two very simple experiments following the settings
detailed in Section 3.2. In particular, we set up a simple single bottleneck
link where we have control over three main network parameters named: minimum
end-to-end delay of the network (minRTT), buffer size, and link capacity (BW).
In the first experiment, we choose two Internet CC schemes (Scheme A: TCP
Cubic (Ha et al., 2008) and Scheme B: LEDBAT (Rossi et al., 2010)) to send and
receive traffic through this network and set BW to 48Mbps and minRTT to 40ms.
Then, we change the underlying buffer size of the network to capture its
impact on the overall performance of these schemes. To that end, we use the
score defined in Eq. 1 that encapsulates the gained throughput and delay of a
CC scheme (a scheme with a higher score is a better scheme). As Fig. 1
illustrates, it is clear that the relative performance of Schemes A and B
depends heavily on the chosen underlying buffer size of the network. So,
performing experiments only in one of the three regions mentioned in Fig. 1,
cannot lead to any meaningful comparison of these schemes. In the second
experiment, we use the same network, set BW to 48Mbps, the buffer size to
5$\times$BDP, and change the minRTT value of the network. Here, we use two
other Internet CC schemes (Scheme C: TCP Vegas (Brakmo et al., 1994) and
Scheme D: BBR (Cardwell et al., 2016)). Again, the results reported in Fig. 2
illustrate that the relative performance of Schemes C and D depends heavily on
the chosen minimum delay of the network.

Figure 1. The impact of bottleneck buffer size on the relative performance of
two CC schemes. In [64, 256)kB region, scheme A outperforms B, in [256, 512]kB
region, both schemes perform roughly similar, and in (512, 1024]kB region,
scheme B outperforms A. Figure 2. The impact of minimum delay of a network on
the relative performance of two CC schemes. In [20, 50)ms region, scheme C
performs better than D, while in (50, 120]ms region, scheme D outperforms C.

The mentioned issues can highlight the fact that using transparent and clear
CC benchmark(s) can greatly increase the trust in the reported results of a
new design, significantly facilitate the process of reviewing CC algorithms,
and avoid reviewers’ time and efforts to be spent on the verification of the
scenarios, settings, and test methodologies used throughout a work.

From the CC Designers’ Perspective: Assuming that the first potential critics
of an algorithm are the designers of it and they can improve their works by
criticizing it before anyone else can, all the benefits discussed earlier can
be considered as the benefits of benchmarking during the design of a CC
algorithm. Moreover, benchmarking a design can work not only as a vigorous
approach for observing the strengths and weaknesses of a design with respect
to the existing ones, but also as a mechanism to perform functionality tests
of it. In other words, benchmarking can facilitate and accelerate the design
process by revealing the problems of a CC scheme during the design process. In
addition, benchmarking can help designers to focus on designing better-
performing algorithms rather than spending time on finding test scenarios or
corner cases where other schemes perform poorly.

ML and the New Wave of CC Designs: The recent advances in machine learning
techniques and algorithms have impacted different research communities
including the system and network community. In particular, a new wave of CC
designs based on (or inspired by) ML has been proposed in the recent years
(e.g., (Abbasloo et al., 2020; Jay et al., 2019; Yan et al., 2018; Abbasloo et
al., 2021; Dong et al., 2018; Winstein and Balakrishnan, 2013)) and likely in
the coming years, there will be more of them out there.

Generally, learning-based CC schemes are designed and trained over a set of
network scenarios and later tested over other scenarios where they are shown
to perform very well. Based on these performance reports, the designers may
conclude that their scheme poses certain properties. For example, the authors
of Indigo mention ”We find that Indigo consistently achieves good performance”
(Yan et al., 2018) or PCC’s authors say that ”PCC achieves consistent high
performance” (Dong et al., 2015). However, usually, these kinds of statements
will be shown to generally not hold true (e.g. check the poor performance of
Indigo in (Abbasloo et al., 2020) or the poor performance of PCC in (Arun and
Balakrishnan, 2018)).

The main issue here is not with certain schemes or certain claims. The issue
is that these general statements are ambiguous and susceptible to multiple
interpretations (or simply put they are not comparable), because they are not
reported using the same setting or over the same scenarios. That’s why usually
the reported results of CC schemes create confusion and consequently, make it
very difficult to determine whether the improvements reported over the prior
state-of-the-art CC designs are meaningful. Benchmarking is a powerful
mechanism to prevent such ambiguities.

###  1.3. Summary of This Work

Considering the motivations discussed, our main goal in this work is to
highlight the need to have and use CC benchmarks. On the one hand, the CC
benchmarks can lead to producing verifiable, comparable, and crystal clear
statements about the performance of CC designs and make it possible to rank
them among the existing approaches, a ranking that can be reproduced and
trusted. On the other hand, CC benchmarks can stimulate more competition and
greatly accelerate more innovations in this topic. As a first step toward that
end, in this paper, we introduce a set of benchmarks named the CC-Bench1 and
the CC-Bench2 for evaluating Internet CC schemes (Section 3). In particular,
the CC-Bench1 focuses on the single-flow performance of Internet CC algorithms
with respect to their gained throughput and round-trip delay. On the other
hand, the CC-Bench2 provides a common ground for assessing the TCP-
friendliness criterion of Internet CC schemes. As part of each benchmark, we
present the notion of the scores and the winner schemes to facilitate the
quantitative comparison of CC schemes. Using these two benchmarks (publicly
available at (tcp, 2023)), we examine the performance of twenty two different
Internet CC algorithms and rank them based on their gained scores in each
benchmark (Section 4). These rankings point to some interesting findings. For
example, when considering the CC-Bench1, the top-ranked scheme, that happens
to be a ML-based approach, is able to get the best score in only about 33% of
the scenarios! That means in any of the remaining 67% of the scenarios, the
top-ranked scheme performs at least worse than one of the twenty one remaining
schemes. This can show the remaining opportunities in this domain and provide
a base challenge for observing more innovations and improvements.

##  2\. Related Work

There are vast body of work in the literature centered around theoretically
analyzing performance of different CC schemes or modeling certain classes of
designs such as AIMD (additive increase multiplicative decrease) protocols
(Mathis et al., 1997; Padhye et al., 2000; Srikant and Başar, 2004). These
models and analysis always can improve our understanding of CC schemes.
However, since these analysis and modelings are usually based on simplified
assumptions about the underlying networks (e.g., Poisson arrival of traffic,
M/M/1 queue models, etc.), they do not suffice and we need to always accompany
them with a lot of experiments to really observe the relative performance of
CC schemes.

To perform extensive experiments, from long time ago, network community has
adapted to use network simulators and emulators. Frameworks such as NS-2 (ns2,
2000), NS-3 (ns3, 2006), NetEm (Hemminger et al., 2005), Mininet (Handigol et
al., 2012), and Mahimahi (Netravali et al., 2014) provide different underlying
parameters and components that can simulate/emulate various network
models/functionalities. However, the specific choice of all these various
parameters and settings, which as shown in Section 1.2 will impact the output
of evaluating network protocols and designs such as CC schemes, remains open.
In this work, we exploit these tools, in particular Mahimahi, and take a
pragmatic approach by introducing a set of benchmarks that do not delegate the
choice of proper settings for evaluating CC schemes to the CC designers
themselves.

The goal of evaluating CC schemes over the same network scenarios is not
necessarily new. As a recent important example aiming this problem, Pantheon
(Yan et al., 2018) can be named. Pantheon hosted a testbed of measurement
nodes on the Internet and performed periodic experiments with some of CC
designs and generated periodic reports on relative performance of the tested
schemes. However, it is for more than three years that the platform is not
maintained anymore. Inspired by these efforts, we argue that having CC
benchamrks that can be executed locally can have their own advantages over
real testbeds. First, local CC benchamrking can prevent the costs and fees
associated with maintaining a centralized platform and hosting a common
testbed. Second, locally available CC benchmarks can potentially cover more
variety of scenarios compared to real testbeds. Third, there is no control
over the other competing flows in a real testbed, so lots of data are required
to make sure that on average results indicate something meaningful. Also, it
will be hard to assess properties such as TCP-friendliness of a CC scheme over
an uncontrolled network.

##  3\. CC Benchmarking

The process of benchmarking usually consists of two main elements: (1) the
metrics and (2) the set of environments, tasks, or scenarios. So, here, we
start with these components and elaborate on the details of each element in
our benchmarks.

###  3.1. The Metrics & the Notion of Scores

When discussing the benchmarking of algorithms/systems, the very first
question that comes to mind is what metric we should use for comparing them
quantitatively in a way that it’ll be transparent and clear enough to reveal
the differences among various systems. This question brings up the need for
having clear quantitative metrics that can represent the main objective(s) in
the targeted domain.

The Right Metric vs. a Good Metric: If we consider the CC problem as a subset
of general decision-making problems, wearing an Operations Research glass may
lead us toward formulating the CC problem as a classic optimization problem
where the key objective is to maximize a given utility function that
represents the problem. However, when it comes to how to model a CC problem
and choose the right utility function, which should represent the main
objective in the context of the CC problem, there are no unique answers out
there. An interesting sign of that fact can be found among the recent
learning-based CC designs. By looking at the details of these works, one can
realize that utility functions used in these works span a wide range of
possible candidates from more classic ones such as the Power (Giessler et al.,
1978) (or modified versions of that as in (Abbasloo et al., 2020; Winstein and
Balakrishnan, 2013)) to very handcrafted and engineered functions including
the first (or higher) derivatives of delay, throughput, etc. (e.g. as in (Dong
et al., 2018)). That’s why here, we do not try to formulate the Internet CC
problem or come up with the right utility function. Instead, we wear a System
Designer glass, and look for a good metrics that can practically encapsulate
the general properties of a good CC scheme from the end-user perspective.

The early practical CC schemes were designed centered around maximizing users’
throughput while maintaining fairness among different flows. This main
practical goal led to an enormous number of heuristic AIMD algorithms for
Internet CC (e.g. (Jacobson, 1988; Cox and Dependence, 1984; Henderson et al.,
2012; Xu et al., 2004; Ha et al., 2008)), and even today, the default CC
algorithm in most platforms is still an AIMD algorithm that had the same
intrinsic objective during the design (TCP Cubic (Ha et al., 2008)). The
throughput-oriented nature of CC designs was a practical and acceptable
assumption mainly due to the throughput-oriented nature of the dominant
applications at the time. Recently though, the emerging applications (such as
AR/VR, online gaming, tactile Internet, vehicle-to-vehicle communications,
etc.) and their intrinsic delay-sensitive natures have spurred a new wave of
CC designs that try not only to maximize user’s throughput, but also to reduce
the delay (Cardwell et al., 2016, 2019; Abbasloo et al., 2020; Dong et al.,
2018; Arun and Balakrishnan, 2018; Abbasloo et al., 2021; Winstein et al.,
2013).

In addition, the notion of incremental growth of the Internet over existing
technologies and protocols has brought up another key practical challenge for
designing new Internet CC schemes named TCP-friendliness. The challenge of
TCP-friendliness comes from the fact that a new Internet CC scheme should not
only provide a good throughput and delay performance, but also should be able
to compete fairly with the default and established Internet CC scheme used by
the majority of devices on the Internet. A scheme that is very aggressive
toward the default scheme usually loses ground among the community and a
scheme that is very polite/shy usually is not considered a practical solution.

So, putting it all together, we can reason about the performance of a CC
scheme when we consider its throughput, delay, and TCP-friendliness. That
said, to capture these three main metrics in different scenarios, we define
two different scores for a flow $F_{c}$ that uses the CC scheme $c$. To
reflect the throughput and delay performance metrics of $F_{c}$, we use a
modified version of Power (Giessler et al., 1978) and define $S^{c}_{p}$ for a
flow $F_{c}$:

(1) $\footnotesize S^{c}_{p}=\frac{r_{c}^{\alpha}}{d_{c}}$

where $r_{c}$ and $d_{c}$ are the average delivery rate and the average round-
trip delay of $F_{c}$, respectively, and $\alpha$ is a coefficient determining
the relative importance of throughput and delay (unless otherwise mentioned,
we set $\alpha=2$). A bigger value of $S^{c}_{p}$ indicates better throughput
and delay performance for the CC scheme $c$. To reflect the TCP-friendliness
metric, in a multi-flow scenario, we define $S^{c}_{fr}$ as:

(2) $\footnotesize S^{c}_{fr}=|f_{c}-r_{c}|$

where $f_{c}$ is the expected average fair share of $F_{c}$, when competing
with the flows with default CC scheme, and $r_{c}$ is the actual achieved
average delivery rate of $F_{c}$. A smaller value of $S^{c}_{fr}$ indicates a
better TCP-friendliness property for $c$.

###  3.2. Scenarios Covered

On the one hand, clearly, a benchmark cannot cover all possible scenarios and
putting too many scenarios may lead to some practical issues such as the
resources required to run the benchmark. On the other hand, a benchmark that
spans only a few cases will not be able to effectively reveal differences
among various CC schemes. So, as a general rule of thumb and as a first step
to making CC benchmarks, we tried to keep the set big enough to see
differences among the CC schemes and small enough to make them practical
benchmarks. One can imagine that in the future more sets of scenarios can be
added to the current list (as is the case in other communities (Brockman et
al., 2016)).

In this section, we elaborate on the network model used in the benchmarks and
describe the range of underlying network parameters and the details of the
scenarios.

Network Model: To keep things simple, we use a single bottleneck link model of
the network. This model can be specified using three main parameters: (1)
bottleneck link capacity (BW), (2) minimum end-to-end delay (minRTT), and (3)
bottleneck buffer size ($qs$). We will show later in Section 4 that this
simple model is good enough to reveal the differences among various Internet
CC schemes. To emulate this network model, we use Mahimahi (Netravali et al.,
2014) that creates TUN/TAP interfaces on Linux OS and provides us with control
over the BW, minRTT, and $qs$ values. In addition, we optimize different Linux
Kernel parameters (in particular, TCP related ones) to have best performance
(tcp, 2023).

Range of Underlying Network Parameters: For choosing the range of parameters,
we considered typical Internet scenarios with a focus on normal end users on
the Internet and some limitations of Mahimahi such as its large overhead for
the large values of BW. That said, the benchmarks cover BWs from a few Mbps to
about 200Mbps, minRTTs from 10ms to 160ms, and $qs$ from
$\frac{1}{2}\times$BDP to $16\times$BDP111The problem of how to set buffer
sizes in a network is for itself an interesting (and not a simple) problem
that still attracts new solutions. E.g. check out (buf, 2019) and the papers
therein for a recent workshop dedicated to this issue..

We categorize benchmarks into two separate groups called CC-Bench1 and CC-
Bench2 which include single-flow and multi-flow scenarios, respectively.

####  3.2.1. The CC-Bench1

This set of benchmarks consists of single flow scenarios where schemes are
evaluated with respect to $S^{c}_{p}$ score that reflects their throughput and
delay performance. The CC-Bench1 includes two main classes of scenarios: (1)
the flat scenarios and (2) the step scenarios.

The Flat Scenarios: This set of scenarios represents general wired scenarios
on the Internet. As its name suggests, it includes wired links with
constant/flat bandwidths throughout the experiments. The ranges of BW, minRTT,
and $qs$ are $[12,192]$Mbps, $[10,160]$ms, $[\frac{1}{2},16]\times$BDP,
respectively.

The Step Scenarios: The flat scenarios alone cannot show the performance of CC
schemes over a more dynamic network. So to answer questions such as how a CC
scheme reacts when BW reduces or increases suddenly, we bring up the step
scenarios. In these scenarios, we start with a given network BW ($BW_{1}$) and
after a specific period of time, we change the underlying BW of the network to
$m\times{BW_{1}}$. Then, we repeat this cycle until the end of the evaluation.
The $m$ value is chosen from $(0.25,0.5,2,4)$ list.

There are a couple of points here. First, we observed that some of the CC
schemes perform periodic tasks (e.g. every 10s, BBR reduces its congestion
windows to a few packets (Cardwell et al., 2016) to observe the change of
minRTT). So, to keep the benchmarking process fair, we tried to avoid having
overlaps between the times of changes and these periodic tasks by choosing a
safe time period for the changes. That said, we perform the changes every 7
seconds222As far as we know, this value does not overlap with any settings for
the existing CC schemes., unless mentioned otherwise. Second, we observed that
for large values of BW, Mahimahi’s overhead increases to a point that it
tangibly impacts the results. To prevent these unwanted impacts, when changing
BW, we always choose to be under 200Mbps. That means if $BW_{1}$ is 96Mbps, we
choose $m<4$. The range of other parameters is similar to flat scenarios. For
both flat and step scenarios, each CC scheme sends traffic for 30s.

####  3.2.2. The CC-Bench2

This set of benchmarks provides scenarios for assessing the TCP-friendliness
of Internet CC schemes. To that end, we let TCP Cubic, which is the default CC
scheme in most platforms (including Linux, Windows, and macOS), compete with
the CC scheme under the test for accessing a shared bottleneck link and we
capture the performance of schemes with respect to $S^{c}_{fr}$ score. Similar
to the CC-Bench1, the three main network parameters are changed to make
different scenarios. The ranges of minRTT and BW values are similar to CC-
Bench1. In addition, we at least let the bottleneck link have $1\times$BDP
buffer size to be able to effectively absorb more than one flow during the
tests. In particular, we choose $qs$ from $[1,16]\times$BDP range.

In a general Internet scenario, with a good probability, we can assume that a
new incoming flow will observe flows controlled by the default CC scheme on
the bottleneck link. This comes from the definition of a default CC scheme and
its property of being used by the majority of flows. Therefore, we let TCP
Cubic come to the network earlier than the CC scheme under the test. When
buffer size increases, generally, it takes more time for flows to reach the
steady-state (if any). In our experiments, we observed that reaching a fair-
share point may take more than a minute (even when both flows are Cubic
flows). So, in the CC-Bench2, we let flows send their packets for 120s to make
sure that the results can present meaningful TCP-friendliness scores.

###  3.3. The Notion of the Winner Schemes

A more classic way of looking at who should be called the winner in a certain
scenario may lead us toward recognizing the CC scheme with the best score
gained throughout a scenario as the winner in that scenario. However, there
are two issues with this way of identifying a winner.

First, since the scores defined in equations 1 and 2 are Real numbers, their
absolute values can differ slightly for two CC schemes. So, if we simply
perform a mathematical comparison between scores, these slight differences can
impact the choice of the winner in a scenario. That said, instead of picking
the CC scheme with the best score as the winner, we pick all CC schemes with
scores less than 10% worse than the best score as the winners of a scenario.
In other words, any scheme with at most 10% lower performance than the best
performing scheme is included in the winner list of that scenario.

Second, simply assigning a number to the performance of a scheme over an
entire scenario and then comparing these numbers together to decide the
winners may smooth out the important differences among the CC schemes. For
instance, how fast CC schemes can react to a sudden change in the network may
not be visible in an overall score of the scheme over a longer period. To
address this issue, we calculate the score of a scheme in separate intervals
throughout the experiments and instead of one score, assign four scores
corresponding to the performance of the scheme in four different intervals
throughout the test. Now, comparing the scores of a certain interval for all
schemes can get a better sense of the performance of different schemes.

Putting all together, we compare the scores of all CC algorithms over a
certain interval of a certain scenario and pick the best performing schemes
(considering the 10% winning margins) as the winners. Then, we sweep over all
intervals and scenarios.

##  4\. The Ranking of the Internet CC

In this section, we rank the Internet CC schemes based on their performance in
the CC-Bench1 and CC-Bench2 benchmarks333All benchmarks are run over 48-Core,
256GB RAM servers.. The non-exhausting list of schemes consists of 22
different Internet CC algorithms. These algorithms include 14 available TCP
schemes in Linux Kernel named Cubic (Ha et al., 2008), Vegas (Brakmo et al.,
1994), YeAH (Baiocchi et al., 2007), BBRv2 (Cardwell et al., 2019), NewReno
(Henderson et al., 2012), Illinois (Liu et al., 2008), Westwood (Casetti et
al., 2002), Veno (Fu and Liew, 2003), HighSpeed (Floyd, 2003), CDG (Hayes and
Armitage, 2011), HTCP (Leith and Shorten, 2004), BIC (Xu et al., 2004), C2TCP
(Abbasloo et al., 2019a), and Hybla (Caini and Firrincieli, 2004), 5 recent
ML-Based CC schemes named Orca (Abbasloo et al., 2020), Indigo (Yan et al.,
2018), Aurora (Jay et al., 2019), PCC Vivace (Dong et al., 2018), and DeepCC
(Abbasloo et al., 2021), and 3 other CC schemes named Copa (Arun and
Balakrishnan, 2018), LEDBAT (Rossi et al., 2010), and Sprout (Winstein et al.,
2013).

To report the results, we use the winning rate index defined as the percentage
of the times that a CC algorithm was a winner in a benchmark. The rankings of
the Internet CC schemes based on their winning rate index for the CC-Bench1
and CC-Bench2 benchmarks are depicted in Fig. 3.

Benchmarking to Reveal Opportunities: The very first thing that Fig. 3
illustrates is that none of these Internet CC schemes are perfect and can
achieve a 100% winning rate! A simple CC benchmark such as the CC-Bench1 can
reveal the huge opportunities existing in this topic, especially when we
consider that the top-ranked schemes in CC-Bench1 (Orca & Indigo) can be
winners in only 1/3rd of the scenarios. How to boost performance further and
design a CC algorithm that can achieve higher winning rates is an interesting
challenge embracing more innovative designs.

The Good and the Bad, but not the Ugly: When we look at the results of Fig. 3
from another angle, we may see that having clear CC benchmarks provides us
with both the full-half of the glass (the part that the designers of the top-
ranked schemes can be happy about) and the empty-half of the glass (the extent
of the remaining performance issues which embrace more novel designs). We
think that this is a much more transparent and fair evaluation mechanism
compared to when designers of a new CC scheme choose the scope and the details
of scenarios in their evaluations.

Getting Inspired by Looking at the Bigger Picture: Results of Fig. 3 indicate
a common pattern among the CC algorithms: generally, delay-based schemes are
among the top-ranked schemes in CC-Bench1, while throughput-oriented schemes
are among the top-ranked schemes in CC-Bench2. This is based on the fact that
being TCP-friendly when coexisting with a loss-based scheme and (at the same
time) being able to minimize delay and maximize throughput when not competing
with a loss-based scheme is very hard and challenging. Interestingly, some of
the results in Fig. 3 may point to some pragmatic ways to achieve a better
trade-off between TCP-friendliness and throughput/delay performance of a CC
scheme444In particular, C2TCP, BBR2, and Orca seem to have managed this trade-
off to some different degrees.. This notion of potentially getting inspired by
the good/bad results of existing schemes is among the benefits that CC
benchmarks can bring to the table.

Shedding Light on Neglected Evaluation Aspects: As expected, Cubic is the top-
ranked scheme in CC-Bench2. However, the fact that it cannot achieve a 100%
winning rate may seem to be somewhat unexpected. One reason for this
performance lies in a key but usually neglected aspect of CC schemes: the
convergence speed of a CC scheme. In particular, although it can be shown that
Cubic can eventually approach its fair share when competing with another Cubic
flow, its convergence time for reaching that point is not necessarily the
best, especially when compared with other top 5 schemes in large $qs$
scenarios555The mechanism of segmenting an entire run to different intervals
and assigning scores to each interval enables us to capture this behavior..
The bottom line is that CC benchmarks (e.g., CC-Bench2) can potentially shed
light on some neglected evaluation aspects of CC algorithms.

Figure 3. The ranking of Internet CC schemes based on their winning rates in
the CC-Bench1 (left) and the CC-Bench2 (right) benchmarks

##  5\. A Brief Discussion & Final Note

I Think I Can Define Better CC Benchmarks! The main point of this work is not
to introduce the best set of benchmarks, but to highlight the benefits of
having CC benchmarks and the need for using them. The CC-Bench1 and the CC-
Bench2 benchmarks are by no means the only or the best benchmarks out there.
We think that when a community starts using benchmarks, it will not be hard to
imagine that as part of an evolutionary process, more attractive benchmarks
will be introduced and adopted in the future.

Are These Benchmarks Enough? Clearly, one or two benchmarks cannot cover all
sets of evaluations and potentially highlight all the specific characteristics
of different CC algorithms. That said, the main role of CC benchmarking is not
to replace existing detailed stress tests of schemes, but to provide a base
and a common ground for unambiguously comparing general results of different
works in this domain.

A Couple of Points on the Reported Rankings: First, none of the scenarios in
our benchmarks were designed to push certain schemes either to the top or
bottom parts of the rankings reported. Second, our focus on this work was not
to pinpoint the issues with certain CC schemes in certain scenarios. This
alone can manifest itself as a good motivation for separate future work.

Final Note: Although benchmarking is a common practice in different
communities, when it comes to CC design, this powerful tool is still missing.
With the recent rise of a new wave of CC designs, the need for having such
common foundations to unambiguously evaluating new algorithms increases. We
hope this work will highlight this need and provide the community with a few
samples to continue with.

## References

  * (1)
  * ns2 (2000) 2000\.  The network simulator 2.  http://www.isi.edu/nsnam/ns/. (2000).
  * ns3 (2006) 2006\.  The network simulator 3.  https://www.nsnam.org/. (2006).
  * buf (2019) 2019\.  Workshop on Buffer Sizing.  https://buffer-workshop.stanford.edu/. (2019).
  * tcp (2023) 2023\.  Project’s Rep.  https://github.com/Soheil-ab/ccBench. (2023).
  * Abbasloo et al. (2018) Soheil Abbasloo, Tong Li, Yang Xu, and H. Jonathan Chao. 2018\.  Cellular Controlled Delay TCP (C2TCP). In IFIP Networking Conference (IFIP Networking), 2018.
  * Abbasloo et al. (2019a) Soheil Abbasloo, Yang Xu, and H. Jonathan Chao. 2019a.  C2TCP: A Flexible Cellular TCP to Meet Stringent Delay Requirements.  IEEE Journal on Selected Areas in Communications 37, 4 (2019), 918–932.
  * Abbasloo et al. (2019b) Soheil Abbasloo, Yang Xu, H Jonathon Chao, Hang Shi, Ulas C Kozat, and Yinghua Ye. 2019b.  Toward Optimal Performance with Network Assisted TCP at Mobile Edge.  2nd USENIX Workshop on Hot Topics in Edge Computing (HotEdge 19) (2019).
  * Abbasloo et al. (2020) Soheil Abbasloo, Chen-Yu Yen, and H. Jonathan Chao. 2020\.  Classic Meets Modern: A Pragmatic Learning-Based Congestion Control for the Internet. In Proceedings of the 2020 ACM SIGCOMM Conference (SIGCOMM ’20). 632–647.
  * Abbasloo et al. (2021) Soheil Abbasloo, Chen-Yu Yen, and H Jonathan Chao. 2021\.  Wanna make your TCP scheme great for cellular networks? Let machines do it for you!  IEEE Journal on Selected Areas in Communications 39, 1 (2021), 265–279.
  * Arun and Balakrishnan (2018) Venkat Arun and Hari Balakrishnan. 2018.  Copa: Practical delay-based congestion control for the internet. In 15th USENIX Symposium on Networked Systems Design and Implementation (NSDI 18). 329–342.
  * Baiocchi et al. (2007) Andrea Baiocchi, Angelo P Castellani, and Francesco Vacirca. 2007\.  YeAH-TCP: yet another highspeed TCP. In Proc. PFLDnet, Vol. 7. 37–42.
  * Brakmo et al. (1994) Lawrence S. Brakmo, Sean W. O’Malley, and Larry L. Peterson. 1994.  TCP Vegas: New Techniques for Congestion Detection and Avoidance. In Proceedings of the Conference on Communications Architectures, Protocols and Applications (SIGCOMM ’94). 24–35.
  * Brockman et al. (2016) Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. 2016.  Openai gym.  arXiv preprint arXiv:1606.01540 (2016).
  * Caini and Firrincieli (2004) Carlo Caini and Rosario Firrincieli. 2004.  TCP Hybla: a TCP enhancement for heterogeneous networks.  International journal of satellite communications and networking 22, 5 (2004), 547–566.
  * Cardwell et al. (2016) Neal Cardwell, Yuchung Cheng, C Stephen Gunn, Soheil Hassas Yeganeh, and Van Jacobson. 2016\.  BBR: Congestion-Based Congestion Control.  Queue 14, 5 (2016), 50.
  * Cardwell et al. (2019) Neal Cardwell, Yuchung Cheng, C Stephen Gunn, Soheil Hassas Yeganeh, and Van Jacobson. 2019\.  TCP BBR v2 Alpha/Preview Release.  https://github.com/google/bbr/blob/v2alpha/README.md. (2019).
  * Casetti et al. (2002) Claudio Casetti, Mario Gerla, Saverio Mascolo, Medy Y Sanadidi, and Ren Wang. 2002.  TCP Westwood: end-to-end congestion control for wired/wireless networks.  Wireless Networks 8, 5 (2002), 467–479.
  * Cox and Dependence (1984) DR Cox and Long-Range Dependence. 1984.  a Review.  Statistics: An Appraisal, HA David and HT David (Eds.) (1984), 55–74.
  * Deng et al. (2009) Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. 2009\.  Imagenet: A large-scale hierarchical image database. In 2009 IEEE conference on computer vision and pattern recognition. Ieee, 248–255.
  * Dong et al. (2015) Mo Dong, Qingxi Li, Doron Zarchy, P Brighten Godfrey, and Michael Schapira. 2015.  $\\{$PCC$\\}$: Re-architecting congestion control for consistent high performance. In 12th USENIX Symposium on Networked Systems Design and Implementation (NSDI 15). 395–408.
  * Dong et al. (2018) Mo Dong, Tong Meng, Doron Zarchy, Engin Arslan, Yossi Gilad, Brighten Godfrey, and Michael Schapira. 2018.  PCC Vivace: Online-Learning Congestion Control. In 15th USENIX Symposium on Networked Systems Design and Implementation (NSDI 18). 343–356.
  * Floyd (2003) Sally Floyd. 2003\.  HighSpeed TCP for large congestion windows.  Technical Report.
  * Fu and Liew (2003) Cheng Peng Fu and Soung C Liew. 2003.  TCP Veno: TCP enhancement for transmission over wireless access networks.  IEEE Journal on selected areas in communications 21, 2 (2003), 216–228.
  * Giessler et al. (1978) Alfred Giessler, J Haenle, Andreas König, and E Pade. 1978.  Free buffer allocation—An investigation by simulation.  Computer Networks (1976) 2, 3 (1978), 191–208.
  * Ha et al. (2008) Sangtae Ha, Injong Rhee, and Lisong Xu. 2008.  CUBIC: a new TCP-friendly high-speed TCP variant.  ACM SIGOPS Operating Systems Review 42, 5 (2008), 64–74.
  * Handigol et al. (2012) Nikhil Handigol, Brandon Heller, Vimalkumar Jeyakumar, Bob Lantz, and Nick McKeown. 2012.  Reproducible network experiments using container-based emulation. In Proceedings of the 8th international conference on Emerging networking experiments and technologies. 253–264.
  * Hayes and Armitage (2011) David A Hayes and Grenville Armitage. 2011.  Revisiting TCP congestion control using delay gradients. In International Conference on Research in Networking. Springer, 328–341.
  * Hemminger et al. (2005) Stephen Hemminger et al. 2005\.  Network emulation with NetEm. In Linux conf au, Vol. 5. 2005\.
  * Henderson et al. (2012) Tom Henderson, Sally Floyd, Andrei Gurtov, and Yoshifumi Nishida. 2012.  The NewReno modification to TCP’s fast recovery algorithm.  Technical Report.
  * Jacobson (1988) Van Jacobson. 1988\.  Congestion avoidance and control. In ACM SIGCOMM CCR, Vol. 18. ACM, 314–329.
  * Jay et al. (2019) Nathan Jay, Noga Rotman, Brighten Godfrey, Michael Schapira, and Aviv Tamar. 2019.  A Deep Reinforcement Learning Perspective on Internet Congestion Control. In International Conference on Machine Learning. PMLR, 3050–3059.
  * Katabi et al. (2002) Dina Katabi, Mark Handley, and Charlie Rohrs. 2002\.  Congestion control for high bandwidth-delay product networks.  ACM SIGCOMM computer communication review 32, 4 (2002), 89–102.
  * Krizhevsky et al. (2012) Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. 2012\.  Imagenet classification with deep convolutional neural networks.  Advances in neural information processing systems 25 (2012).
  * Krizhevsky et al. (2017) Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. 2017\.  Imagenet classification with deep convolutional neural networks.  Commun. ACM 60, 6 (2017), 84–90.
  * Leith and Shorten (2004) Douglas Leith and Robert Shorten. 2004.  H-TCP: TCP for high-speed and long-distance networks. In Proceedings of PFLDnet, Vol. 2004.
  * Liu et al. (2008) Shao Liu, Tamer Başar, and Ravi Srikant. 2008\.  TCP-Illinois: A loss-and delay-based congestion control algorithm for high-speed networks.  Performance Evaluation 65, 6-7 (2008), 417–440.
  * Mathis et al. (1997) Matthew Mathis, Jeffrey Semke, Jamshid Mahdavi, and Teunis Ott. 1997.  The macroscopic behavior of the TCP congestion avoidance algorithm.  ACM SIGCOMM Computer Communication Review 27, 3 (1997), 67–82.
  * Nagle (1984) John Nagle. 1984\.  Congestion control in IP/TCP internetworks.  ACM SIGCOMM Computer Communication Review 14, 4 (1984), 11–17.
  * Netravali et al. (2014) Ravi Netravali, Anirudh Sivaraman, Keith Winstein, Somak Das, Ameesh Goyal, and Hari Balakrishnan. 2014\.  Mahimahi: A Lightweight Toolkit for Reproducible Web Measurement. In Proceedings of the 2014 ACM Conference on SIGCOMM (SIGCOMM ’14). 129–130.
  * Padhye et al. (2000) Jitendra Padhye, Victor Firoiu, Donald F Towsley, and James F Kurose. 2000.  Modeling TCP Reno performance: a simple model and its empirical validation.  IEEE/ACM transactions on Networking 8, 2 (2000), 133–145.
  * Park et al. (2018) Shinik Park, Jinsung Lee, Junseon Kim, Jihoon Lee, Sangtae Ha, and Kyunghan Lee. 2018\.  ExLL: An Extremely Low-Latency Congestion Control for Mobile Cellular Networks. In Proceedings of the 14th International Conference on Emerging Networking EXperiments and Technologies (CoNEXT ’18). 307–319.
  * Rossi et al. (2010) Dario Rossi, Claudio Testa, Silvio Valenti, and Luca Muscariello. 2010.  LEDBAT: The New BitTorrent Congestion Control Protocol.. In ICCCN. 1–6.
  * Russakovsky et al. (2015) Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, et al. 2015\.  Imagenet large scale visual recognition challenge.  International journal of computer vision 115, 3 (2015), 211–252.
  * Srikant and Başar (2004) Rayadurgam Srikant and Tamer Başar. 2004.  The mathematics of Internet congestion control.  Springer.
  * Winstein and Balakrishnan (2013) Keith Winstein and Hari Balakrishnan. 2013.  TCP Ex Machina: Computer-generated Congestion Control. In Proceedings of the 2013 Conference of the ACM SIGCOMM (SIGCOMM ’13). ACM, 123–134.  https://doi.org/10.1145/2486001.2486020
  * Winstein et al. (2013) Keith Winstein, Anirudh Sivaraman, and Hari Balakrishnan. 2013\.  Stochastic Forecasts Achieve High Throughput and Low Delay over Cellular Networks.. In 10th USENIX Symposium on Networked Systems Design and Implementation (NSDI 13). 459–471.
  * Xu et al. (2004) Lisong Xu, Khaled Harfoush, and Injong Rhee. 2004\.  Binary increase congestion control (BIC) for fast long-distance networks. In IEEE INFOCOM 2004, Vol. 4. 2514–2524.
  * Yan et al. (2018) Francis Y Yan, Jestin Ma, Greg D Hill, Deepti Raghavan, Riad S Wahby, Philip Levis, and Keith Winstein. 2018.  Pantheon: the training ground for Internet congestion-control research. In 2018 USENIX Annual Technical Conference (USENIX ATC 18). 731–743.
  * Yen et al. (2023) Chen-Yu Yen, Soheil Abbasloo, and H Jonathan Chao. 2023\.  Computers Can Learn from the Heuristic Designs and Master Internet Congestion Control. In ACM SIGCOMM 2023 Conference (ACM SIGCOMM ’23).
  * Zaki et al. (2015) Yasir Zaki, Thomas Pötsch, Jay Chen, Lakshminarayanan Subramanian, and Carmelita Görg. 2015\.  Adaptive congestion control for unpredictable cellular networks. In ACM SIGCOMM CCR, Vol. 45. ACM, 509–522.