# Asymmetric Ramsey properties of randomly perturbed graphs

Emily Heath Department of Mathematics, Iowa State University, Ames IA.
Email: {eheath<EMAIL_ADDRESS>Daniel McGinnis11footnotemark: 1

###### Abstract

In this note, we investigate for various pairs of graphs $(H,G)$ the question
of how many random edges must be added to a dense graph to guarantee that any
red-blue coloring of the edges contains a red copy of $H$ or a blue copy of
$G$. We determine this perturbed Ramsey threshold for many new pairs of graphs
and various ranges of densities, obtaining several generalizations of results
obtained by Das and Treglown. In particular, we resolve the remaining cases
toward determining the perturbed Ramsey threshold for pairs $(K_{t},K_{s})$
where $t\geq s\geq 5$.

##  1 Introduction

Given graphs $H_{1},\ldots,H_{r}$, we say that a graph $G$ is
_$(H_{1},\ldots,H_{r})$ -Ramsey_ if any $r$-coloring of the edges of $G$
contains a monochromatic copy of $H_{i}$ in color $i$, for some $i\in[r]$. In
the case $H_{1}=\cdots=H_{r}$, we refer to such a graph as being
$(H,r)$-Ramsey. The _Ramsey number_ $R(H_{1},\ldots,H_{r})$ is the smallest
number of vertices needed so that $K_{n}$ is $(H_{1},\ldots,H_{r})$-Ramsey.
Since Ramsey [41] showed that this number exists in 1930, the question of
improving the bounds on $R(H_{1},\ldots,H_{r})$ has received significant
attention. Rödl and Ruciński [42, 43, 44] initiated the study of Ramsey
properties of the _random graph_ $G(n,p)$ which has vertex set $[n]$ and and
where each edge is present with probability $p$, independently of all other
choices. They determined the threshold for the $(H,r)$-Ramsey property in
$G(n,p)$ for all fixed graphs $H$ and $r\geq 2$, showing that it depends on
the so-called 2-density of the graph.

For a graph $H$, let $d_{2}(H)=0$ if $e(H)=0$, $d_{2}(H)=1/2$ if $H$ is an
edge, and $d_{2}(H)=\frac{e(H)-1}{v(H)-2}$ otherwise. The _2-density_ of $H$
is given by $m_{2}(H)=\max_{H^{\prime}\subseteq H}d_{2}(H^{\prime})$. A graph
$H$ is said to be _strictly 2-balanced_ if $m_{2}(H^{\prime})<m_{2}(H)$ for
all $H^{\prime}\subsetneq H$.

######  Theorem 1.1 ([42, 43, 44]).

Let $r\geq 2$ be a positive integer and $H$ be a graph that is not a forest
consisting of stars and paths of length 3. There are positive constants $c$
and $C$ such that

$\lim_{n\rightarrow\infty}\mathbb{P}[G(n,p)\text{ is
}(H,r)\text{-Ramsey}]=\begin{cases}0,&p<cn^{-1/m_{2}(H)},\\\
1,&p>Cn^{-1/m_{2}(H)}.\end{cases}$

Nenadov and Steger [38] later gave a short proof of this result using the
hypergraph container method [5, 45].

More generally, Kohayakawa and Kreuter [27] conjectured that for any graphs
$H_{1},\ldots,H_{r}$, the threshold for $G(n,p)$ to be
$(H_{1},\ldots,H_{r})$-Ramsey is governed by the _asymmetric density_ of the
two densest graphs. The asymmetric density of graphs $H_{1}$ and $H_{2}$ with
$m_{2}(H_{1})\geq m_{2}(H_{2})$ is

$m_{2}(H_{1},H_{2})=\max\left\\{\frac{e(H_{1}^{\prime})}{v(H_{1}^{\prime})-2+1/m_{2}(H_{2})}:H_{1}^{\prime}\subseteq
H_{1}\text{ and }e(H_{1}^{\prime})\geq 1\right\\}.$ (1)

We say that $H_{1}$ is _strictly balanced with respect to
$m_{2}(\cdot,H_{2})$_ if no $H^{\prime}_{1}\subsetneq H_{1}$ with at least one
edge maximizes (1).

######  Conjecture 1.2 ([27]).

Let $r\geq 2$ and suppose that $H_{1},\ldots,H_{r}$ are non-empty graphs such
that $m_{2}(H_{1})\geq m_{2}(H_{2})\geq\cdots\geq m_{2}(H_{r})$ and
$m_{2}(H_{2})>1$. Then there exist constants $c,C>0$ such that

$\lim_{n\rightarrow\infty}P[G(n,p)\text{ is
}(H_{1},\ldots,H_{r})\text{-Ramsey}]=\begin{cases}0,&p<cn^{-1/m_{2}(H_{1},H_{2})},\\\
1,&p>Cn^{-1/m_{2}(H_{1},H_{2})}.\end{cases}$

If true, Conjecture 1.2 would generalize Theorem 1.1, since $m_{2}(H_{1})\geq
m_{2}(H_{1},H_{2})\geq m_{2}(H_{2})$ with equality if and only if
$m_{2}(H_{1})=m_{2}(H_{2})$. As evidence towards this conjecture, Kohayakawa
and Kreuter [27] proved the result in the case $r=2$ where both graphs are
cycles. The conjecture was later proved for the case where $H_{1}$ and $H_{2}$
are cliques in [35] and the case where $H_{1}$ is a clique and $H_{2}$ is a
cycle in [34].

Following progress in [5, 20, 22, 27, 35], the full 1-statement of the
conjecture was proved by Mousset, Nenadov and Samotij [37] using the container
method. The 0-statement was proved by Hyde [23] for almost all pairs of
regular graphs, and by Kuperwasser and Samotij [32] when
$m_{2}(H_{1})=m_{2}(H_{2})$. Very recently, Bowtell, Hancock, and Hyde [14]
and Kuperwasser, Samotij, and Wigderson [33] independently reduced the
0-statement of the conjecture to a deterministic coloring problem. In [14],
the authors resolved the conjecture in many cases, including when $r\geq 3$,
when $H_{2}$ is strictly 2-balanced and not bipartite, and when
$m_{2}(H_{1})=m_{2}(H_{2})$, in addition to proving that an analogous
conjecture holds for almost all pairs of uniform hypergraphs. On the other
hand, in [33], in addition to proving the conjecture for many cases, the
authors extended their results to families of graphs.

While the results above address the Ramsey properties of typical graphs of a
given density, we are interested in this note in the related question of how
far a dense graph can be from satisfying a Ramsey property. Bohman, Frieze and
Martin [10] introduced the model of randomly perturbed graphs to study
questions of this type, beginning with a dense graph and asking how many
random edges must be added to ensure that the resulting graph will satisfy a
given property with high probability. This randomly perturbed graph model has
been extensively studied [1, 2, 4, 6, 8, 9, 12, 13, 17, 15, 19, 25, 26, 30,
31, 39] and generalized to the settings of directed graphs, hypergraphs, and
sets of integers [3, 7, 16, 21, 29, 36].

Krivelevich, Sudakov, and Tetali [31] initiated the study of Ramsey properties
of randomly perturbed graphs, asking how many random edges must be added to
any dense graph to ensure with high probability that the resulting graph is
$(H_{1},H_{2})$-Ramsey. They answered this question in the case when
$H_{1}=K_{t}$ and $H_{2}=K_{3}$ for $t\geq 3$. Their results were generalized
to larger cliques by Das and Treglown [18] and Powierski [40], resolving the
$(K_{t},K_{s})$-Ramsey problem in the range of densities $0<d\leq\frac{1}{2}$
for all cases except $s=4$ and $t\geq 5$, which appears to be quite difficult.
In fact, in [18], the authors addressed the following more refined question:
given any fixed density $0<d<1$, how many random edges must be added to any
graph $G$ of density at least $d$ to ensure that with high probability the
resulting graph is $(H_{1},H_{2})$-Ramsey?

In addition to settling the question for most cliques, Das and Treglown [18]
determined the perturbed Ramsey threshold for all pairs of cycles and all
densities. In each case, their result showed that significantly fewer random
edges are needed for the perturbed $(C_{k},C_{\ell})$-Ramsey question compared
to the result in the random graph setting. They also determined the perturbed
Ramsey thresholds for odd cycles versus cliques. However, the question of
Krivelevich, Sudakov, and Tetali [31] remains open for all other pairs of
graphs.

In this note, we determine the perturbed Ramsey threshold for several
additional classes of graphs and densities. To state our results, we will need
the following definition.

######  Definition 1.3.

Given a density $0<d<1$, a number of colors $r\in\mathbb{N}$, and a sequence
of graphs $(H_{1},\ldots,H_{r})$, the _perturbed Ramsey threshold probability_
$p(n;H_{1},\ldots,H_{r},d)$ satisfies the following:

  1. 1.

If $p=p(n)=\omega(p(n;H_{1},\ldots,H_{r},d))$, then for any sequence
$(G_{n})_{n\in\mathbb{N}}$ of $n$-vertex graphs with density at least $d$, the
graph $G_{n}\cup G(n,p)$ is $(H_{1},\ldots,H_{r})$-Ramsey with high
probability.

  2. 2.

If $p=p(n)=o(p(n;H_{1},\ldots,H_{r},d))$, then for some sequence
$(G_{n})_{n\in\mathbb{N}}$ of $n$-vertex graphs with density at least $d$, the
graph $G_{n}\cup G(n,p)$ is with high probability not
$(H_{1},\ldots,H_{r})$-Ramsey.

If it is the case that every sufficiently large graph of density at least $d$
is $(H_{1},\ldots,H_{r})$-Ramsey, then we define
$p(n;H_{1},\ldots,H_{r},d)=0$. In the symmetric case where
$H_{1}=\cdots=H_{r}=H$, we denote the threshold by $p(n;r,H,d)$.

Our main results are Theorem 3.1 and 3.2 which determine the perturbed Ramsey
threshold for pairs of graphs satisfying several technical conditions. We
refer the statement of these theorems to Section 3, and instead now state
several applications to interesting families of graphs below. The proofs of
these corollaries are presented in Section 4.

In [18], the following perturbed Ramsey threshold result was shown for pairs
of complete graphs.

######  Theorem 1.4 ([18]).

Let $s,t,k$ be integers with $k\geq 2$ and $t\geq s\geq 2k+1$, and let
$\frac{k-2}{k-1}\leq d\leq\frac{k-1}{k}$. If

  1. (i)

$k=2$, or

  2. (ii)

$s\equiv 1$ (mod $k$),

then $p(n;K_{t},K_{s},d)=n^{-1/m_{2}(K_{t},K_{\lceil s/k\rceil})}$. Otherwise
if

  1. (iii)

$k\geq 3$ and $s\not\equiv 1$ (mod $k$),

then $p(n;K_{t},K_{s},d)=n^{-(1-o(1))/m_{2}(K_{t},K_{\lceil s/k\rceil})}$.

In particular, an exact threshold function when $k\geq 3$ and $s\not\equiv 1$
(mod $k$) was not proven. We determine the exact threshold function even in
these cases as a corollary of Theorem 3.1.

######  Corollary 4.2.

Let $s,t,k$ be integers with $k\geq 2$ and $t\geq s\geq 2k+1$, and let
$\frac{k-2}{k-1}\leq d\leq\frac{k-1}{k}$. Then we have that

$p(n;K_{t},K_{s},d)=n^{-1/m_{2}(K_{t},K_{\lceil s/k\rceil})}.$

In addition, Theorem 3.1 yields a similar result for another pair of graphs: a
clique $K_{t}$ and a graph $K_{s}^{\prime}$ obtained by deleting a maximum
matching from the complete graph $K_{s}$.

######  Corollary 4.1.

Let $K_{s}^{\prime}$ be the graph obtained by deleting a maximum matching from
the complete graph $K_{s}$. For an integer $2\leq k<\frac{s}{3}$ and in the
range of densities $\frac{k-2}{k-1}\leq d\leq\frac{k-1}{k}$, we have that for
$t\geq s\geq 7$,

$p(n;K_{t},K_{s}^{\prime},d)=n^{-1/m_{2}(K_{t},K_{\lceil
s/k\rceil}^{\prime})}.$

In [18], Das and Treglown also determined the perturbed Ramsey threshold for
pairs consisting of a complete graph and an odd cycle. Specifically, they
prove the following.

######  Theorem 1.5 ([18]).

For any clique size $t\geq 4$, odd cycle length $\ell\geq 5$, and $0<d\leq
1/2$, we have that

$p(n;K_{t},C_{\ell},d)=n^{-2/(t-1)}.$

As an application of Theorem 3.2, we generalize Theorem 1.5 to pairs
$(K_{t},G)$ where $t\geq 5$ and $G$ is, for example, an odd cycle, an odd
cycle with a chord, an even cycle with a chord connecting two vertices an even
distance away along the cycle, or a star on at least 3 vertices with an
additional vertex that is adjacent to each vertex of the star.

######  Corollary 4.3.

Given a tree $T$ with at least 4 vertices, let $G$ be a graph obtained by
adding a vertex $v$ to $T$ and edges from $v$ to $V(T)$ such that there is no
2-coloring of $T$ where the vertices in $N_{G}(v)$ are all the same color, but
there is some vertex $u\in N_{G}(v)$ such that there is a 2-coloring of $T$
where the vertices of $N_{G}(v)\setminus\\{u\\}$ are colored with the same
color.

Then for $t\geq 5$ and $0<d\leq 1/2$,

$p(n;K_{t},G,d)=n^{-2/(t-1)}.$

Finally, we obtain the following result as another application of Theorem 3.2.
This result determines the perturbed Ramsey threshold for some pairs of
3-chromatic graphs. In particular, unlike in the previous results, both graphs
in the pair have significantly fewer edges than a complete graph.

######  Corollary 4.4.

Let $K$ be the graph obtained by taking a star on $t\geq 4$ vertices and
adding a new vertex that is adjacent to each vertex of the star. Let $G$ be as
in Corollary 4.3. Then for $0<d\leq 1/2$,

$p(n;K,G,d)=n^{-(t+1)/(2t-1)}.$

##  2 Preliminaries

In this section, we will introduce the tools used in our proofs. In addition
to our main tool, the famous Szemerédi Regularity Lemma [28], which allows us
to find useful substructures in the dense underlying graph $G$, we will also
rely on other results to analyze the random edges in $G(n,p)$.

######  Definition 2.1.

Given $\varepsilon>0$, a graph $G$ and two disjoint vertex sets $A,B\subset
V(G)$, the pair $(A,B)$ is $\varepsilon$-regular if for every $X\subset A$,
$B\subset Y$ with $|X|>\varepsilon|A|$ and $|Y|>\varepsilon|B|$, we have
$|d(X,Y)-d(A,B)|<\varepsilon$.

We will make use of the following well-known properties of
$\varepsilon$-regular pairs.

######  Lemma 2.2.

Let $(A,B)$ be an $\varepsilon$-regular pair in a graph $G$ and set
$d=d(A,B)$.

  1. 1.

If $\ell\geq 1$ and $(d-\varepsilon)^{\ell-1}>\varepsilon$, then

$\left|\left\\{(x_{1},x_{2},\dots,x_{\ell})\in A^{\ell}:|\cap_{i}N(x_{i})\cap
B|\leq(d-\varepsilon)^{\ell}|B|\right\\}\right|\leq\ell\varepsilon|A|^{\ell}.$

  2. 2.

If $\alpha>\varepsilon$, and $A^{\prime}\subset A$ and $B^{\prime}\subset B$
satisfy $|A^{\prime}|\geq\alpha|A|$ and $|B^{\prime}|\geq\alpha|B|$, then
$(A^{\prime},B^{\prime})$ is an $\varepsilon^{\prime}$-regular pair of density
$d^{\prime}$, where
$\varepsilon^{\prime}=\textrm{max}\\{\varepsilon/\alpha,2\varepsilon\\}$ and
$|d^{\prime}-d|<\varepsilon$.

Combining the Regularity Lemma with Turán’s Theorem [46] yields the following
corollary, which we will apply in our proofs to build monochromatic copies of
graphs.

######  Theorem 2.3.

For every $\varepsilon,\delta>0$ with $\delta\geq 3\varepsilon$, there is some
$\eta=\eta(\varepsilon,\delta)>0$ and
$n_{0}=n_{0}(\varepsilon,\delta)\in\mathbb{N}$ such that the following holds
for all $n\geq n_{0}$ and $k\geq 2$. If $G$ is an $n$-vertex graph with
density at least $1-\frac{1}{k-1}+\delta$, then there are pairwise disjoint
vertex sets $V_{1},\dots,V_{k}\subset V(G)$ such that
$|V_{1}|=\cdots=|V_{k}|\geq\eta N$, and for each $1\leq i<j\leq k$ the edges
between $V_{i}$ and $V_{j}$ form an $\varepsilon$-regular pair of density at
least $\frac{\delta}{2}$.

In addition to the results above for finding structure in dense graphs, we
will need several tools for finding structure in random graphs. The first is
the following standard application of the Janson inequality [24, Theorem 2.14]
proven in [18].

######  Theorem 2.4.

Let $H$ be a graph with $v\geq 2$ vertices and $e\geq 1$ edges. Let $[n]$ be
the vertex set of $G(n,p)$, and for some $\xi>0$, let $\mathcal{H}$ be a
collection of $\xi n^{v}$ possible copies of $H$ with vertex set in $[n]$. The
probability that $G(n,p)$ does contain a copy of $H$ from $\mathcal{H}$ is at
most $\textrm{exp}(-\xi\mu_{1}/(2^{v+1}v!))$, where
$\mu_{1}=\mu_{1}(H)=\textrm{min}\\{n^{v(F)}p^{e(F)}\mid F\subseteq H,e(F)\geq
1\\}$.

We will also employ results on Ramsey properties of random graphs. While the
1-statement of Conjecture 1.2 is now known for all graphs [37], we need the
following stronger Ramsey properties defined in [18] which are satisfied by
many pairs of graphs $(H_{1},H_{2})$ above the threshold of Conjecture 1.2.

######  Definition 2.5.

Let $H_{1}$ and $H_{2}$ be two fixed graphs, and let $G$ be an $n$-vertex
graph on the vertex set $[n]$.

Given families $\mathcal{F}_{i}\subset\binom{[n]}{v(H_{i})}$, for $i\in[2]$,
of forbidden subsets of $v(H_{i})$ vertices, we say $G$ is robustly
$(H_{1},H_{2})$-Ramsey with respect to $(\mathcal{F}_{1},\mathcal{F}_{2})$ if
for every 2-coloring of $G$, there is a red copy of $H_{1}$ or a blue copy of
$H_{2}$ whose vertex set is not forbidden (i.e. the vertex set of the
monochromatic copy $H_{i}$ is not a member of $\mathcal{F}_{i}$).

Given $\mu>0$, we say that $G$ is $\mu$-globally $(H_{1},H_{2})$-Ramsey if for
every 2-coloring of $G$ and every subset $U\subseteq[n]$ of size at least $\mu
n$, $G[U]$ contains a red copy of $H_{1}$ or a blue copy of $H_{2}$.

By modifying the proofs of Hancock, Staden and Treglown[22] and of Gugelmann,
Nenadov, Person, Škorić, Steger and Thomas [20] proved with hypergraph
containers, Das and Treglown [18] showed that the random graph $G(n,p)$ is not
just $(H_{1},H_{2})$-Ramsey but in fact robustly and globally Ramsey for many
graphs $(H_{1},H_{2})$ beyond the threshold of Conjecture 1.2.

######  Theorem 2.6 ([18]).

Let $H_{1}$ and $H_{2}$ be graphs such that $m_{2}(H_{1})\geq m_{2}(H_{2})\geq
1$ and

  * •

$m_{2}(H_{1})=m_{2}(H_{2})$, or

  * •

$H_{1}$ is strictly balanced with respect to $m_{2}(\cdot,H_{2})$.

The random graph $G(n,p)$ then has the following Ramsey properties.

  1. 1.

There are constants $\gamma=\gamma(H_{1},H_{2})>0$ and
$C_{1}=C_{1}(H_{1},H_{2})$ such that if $p\geq C_{1}n^{-1/m_{2}(H_{1},H_{2})}$
and if for $i\in[2]$, $\mathcal{F}_{i}\subset\binom{[n]}{v(H_{i})}$ is a
collection of at most $\gamma n^{v(H_{i})}$ forbidden subsets, then $G(n,p)$
is with high probability robustly $(H_{1},H_{2})$-Ramsey with respect to
$(\mathcal{F}_{1},\mathcal{F}_{2})$.

  2. 2.

For every $\mu>0$, there is a constant $C_{2}=C_{2}(H_{1},H_{2},\mu)$ such
that if $p\geq C_{2}n^{-1/m_{2}(H_{1},H_{2})}$, then $G(n,p)$ is with high
probability $\mu$-globally $(H_{1},H_{2})$-Ramsey.

##  3 Main Theorems

In this section, we prove our two main results. Both of these theorems are
stated somewhat generally, and we apply them to specific pairs of graphs in
Section 4.

######  Theorem 3.1.

Let $k\geq 2$ and $K$, $G$, and $H$ be graphs satisfying the following
properties.

  1. 1.

For every partition $V_{1},\dots,V_{k}$ of $V(G)$, $H$ is a subgraph of some
$G[V_{i}]$.

  2. 2.

The graph obtained by taking $k$ disjoint copies of $H$ and adding all edges
between the $k$ copies contains $G$ as a subgraph.

  3. 3.

$m_{2}(K)\geq m_{2}(G)\geq 1$, $m_{2}(K)\geq m_{2}(H)\geq 1$, and $K$ is
strictly 2-balanced with respect to $m_{2}(\cdot,G)$ (respectively
$m_{2}(\cdot,H)$) or $m_{2}(K)=m_{2}(G)$ (respectively $m_{2}(K)=m_{2}(H)$).

  4. 4.

There is a graph $K^{\prime}$ obtained by deleting 1 vertex from $K$ such that
$m_{2}(K,H)\geq m_{2}(K^{\prime},G)$ and $m_{2}(K^{\prime})\geq m_{2}(G)$, and
$K^{\prime}$ is strictly 2-balanced with respect to $m_{2}(\cdot,G)$ or
$m_{2}(K^{\prime})=m_{2}(G)$.

  5. 5.

The 0-statement of Conjecture 1.2 holds for the pair of graphs $(K,H)$.

Then for $\frac{k-2}{k-1}<d\leq\frac{k-1}{k}$,

$p\left(n;K,G,d\right)=n^{-1/m_{2}\left(K,H\right)}.$

###### Proof.

First we consider the lower bound. Let
$p=o\left(n^{-1/m_{2}\left(K,H\right)}\right)$ and
$\frac{k-2}{k-1}<d\leq\frac{k-1}{k}$. Let $\Gamma_{n}$ be the balanced
complete $k$-partite graph on $n$ vertices, and color each edge of
$\Gamma_{n}$ blue. Since the pair of graphs $(K,H)$ satisfies the
$0$-statement of Conjecture 1.2, there exists a 2-coloring of $G(n,p)$ that
does not have a red copy of $K$ or a blue copy of $H$. Color the remaining
edges of $\Gamma_{n}\cup G(n,p)$ according to this coloring. Then
$\Gamma_{n}\cup G(n,p)$ certainly contains no red $K$, and since any
$k$-partition of $G$ contains $H$ in one of its partite sets, $\Gamma_{n}\cup
G(n,p)$ also contains no blue $G$.

For the upper bound, let $p=\omega\left(n^{-1/m_{2}\left(K,H\right)}\right)$
and $\frac{k-2}{k-1}<d\leq\frac{k-1}{k}$. Let $t=|V(K)|$ and $h=|V(H)|$. By
Theorem 2.3 with $\delta=d-\frac{k-2}{k-1}$, and $\varepsilon>0$, for every
$n$-vertex graph $\Gamma$ with $n$ sufficiently large, there exist $k$
disjoint vertex sets $V_{1},\dots,V_{k}$ such that
$|V_{1}|=\cdots=|V_{k}|=\eta n$ for some $\eta>0$, and for $1\leq i<j\leq k$
the pair $(V_{i},V_{j})$ is $\varepsilon$-regular of density at least
$\delta/2$. Let $\gamma=\gamma(K,H)$ be as in Theorem 2.6.

We now prove by induction that with high probability, in any red-blue coloring
of $\Gamma\cup G(n,p)$, either there is a red copy of $K$, or we may a find a
blue copy of $H$ within each vertex set $V_{i}$ with all blue edges between
the copies. This must necessarily contain a blue copy of $G$ as a subgraph,
and hence will complete the proof.

We begin by proving the base case, when $k=2$. Let $\Gamma\cup G(n,p)$ be
2-colored with red and blue. By Lemma 2.2, for sufficiently small
$\varepsilon$, there are at most $h\varepsilon|V_{1}|^{h}$ $h$-sets in $V_{1}$
whose common neighborhood in $V_{2}$ in $\Gamma$ has size at most
$(\delta/2-\varepsilon)^{h}|V_{2}|$. Choose $\varepsilon$ so that
$h\varepsilon<\gamma$. Let $\mathcal{F}_{1}=\emptyset$ and $\mathcal{F}_{2}$
be those $h$-sets of $V_{1}$ whose common neighborhood in $V_{2}$ in $\Gamma$
has size at most $(\delta/2-\varepsilon)^{h}|V_{2}|$. We may assume that
$G(n,p)[V_{1}]$ does not contain a red copy of $K$. Then since
$G(n,p)[V_{1}]\sim G(\eta n,p)$, and since $m_{2}(K)\geq m_{2}(H)\geq 1$ and
$K$ is strictly 2-balanced with respect to $m_{2}(\cdot,H)$ or
$m_{2}(K)=m_{2}(H)$, Theorem 2.6 implies that there is a blue copy of $H$ in
$G(n,p)[V_{1}]$ whose vertex set is not a member of $\mathcal{F}_{2}$.

Taking $\alpha=\left(\frac{\delta/2-\varepsilon}{2}\right)^{h}$, if $U\subset
V_{2}$ is the common neighborhood of the vertices in the blue copy of $H$ in
$V_{1}$, then $|U|\geq\alpha 2^{h}|V_{2}|=\alpha 2^{h}\eta n$. By the
pigeonhole principle, there exists a vertex set $U^{\prime}\subset U$ of size
at least $\alpha\eta n$ such that for each vertex $v\in V(H)$, the edges from
$v$ to $U^{\prime}$ are monochromatic.

Since $m_{2}(K,H)\geq m_{2}(K^{\prime},G)$, we have that
$p=\omega\left(n^{-1/m_{2}(K^{\prime},G)}\right)$. Now with $\mu=\alpha\eta$,
Theorem 2.6 implies that $G(n,p)$ is $\mu$-globally $(K^{\prime},G)$-Ramsey
with high probability. Therefore, with high probability, $G(n,p)[U^{\prime}]$
contains either a red copy of $K^{\prime}$ or a blue copy of $G$. If there is
a blue copy of $G$, then we are done, so assume there is a red copy of
$K^{\prime}$ in $G(n,p)[U^{\prime}]$. Then the edges between $V(H)$ and
$U^{\prime}$ must all be blue, as otherwise a red copy of $K$ is created. We
also have that $G(n,p)$ is $(K,H)$-Ramsey with high probability, so we can
assume that $G(n,p)[U^{\prime}]$ contains a blue copy of $H$. But then
$\Gamma\cup G(n,p)$ contains the blue graph consisting of two disjoint copies
of $H$ with all edges in between, which contains $G$ as a subgraph. Therefore,
$\Gamma\cup G(n,p)$ is $(K,G)$-Ramsey with high probability.

Now assume $k\geq 3$. As before, let $\Gamma\cup G(n,p)$ be 2-colored with red
and blue. For sufficiently small $\varepsilon$ and for $2\leq j\leq k$, there
are at most $h\varepsilon|V_{1}|^{h}$ $h$-sets in $V_{1}$ whose common
neighborhood in $V_{j}$ in $\Gamma$ has size at most
$(\delta/2-\varepsilon)^{h}|V_{j}|$. Let $\varepsilon$ be sufficiently small
so that $(k-1)h\varepsilon<\gamma$. Let $\mathcal{F}_{1}=\emptyset$ and
$\mathcal{F}_{2}$ be those $h$-sets of $V_{1}$ whose common neighborhood in
some $V_{j}$ in $\Gamma$ has size at most $(\delta/2-\varepsilon)^{h}|V_{j}|$.
Note that
$|\mathcal{F}_{2}|\leq(k-1)h\varepsilon|V_{1}|^{h}<\gamma|V_{1}|^{h}$.
Therefore, similar to the case of $k=2$ above, we have that with high
probability, in any red-blue coloring, there is a blue copy of $H$ whose
vertex set is not a member of $\mathcal{F}_{2}$. For $2\leq j\leq k$, let
$U_{j}\subset V_{j}$ be the common neighborhood of $V(H)$ in $V_{j}$ in
$\Gamma$. As in the $k=2$ case, we can assume that there is a vertex set
$U^{\prime}_{j}\subset U_{j}$ for each $2\leq j\leq k$ of size $\alpha\eta n$
such that for each $v\in V(H)$, each edge from $v$ to $U^{\prime}_{j}$ is
blue. After decreasing $\varepsilon$ if necessary so that
$\alpha>\varepsilon$, we have by Lemma 2.2 that for $2\leq i<j\leq k$, the
pair $(U^{\prime}_{i},U^{\prime}_{j})$ is $\varepsilon^{\prime}$-regular for
$\varepsilon^{\prime}=\varepsilon/\alpha$ and with density
$\delta^{\prime}>0$. By induction, we may assume with high probability that
there is a blue copy of $H$ within each $U^{\prime}_{j}$ and that all edges
between these copies are blue. This together with the blue copy of $H$ from
$V_{1}$ contains a blue copy of $G$ as a subgraph. This completes the proof. ∎

The following theorem provides a different set of conditions on pairs
$(H_{1},H_{2})$ for which we can determine the associated perturbed Ramsey
threshold. For the purpose of stating Theorem 3.2 below, we denote
$m(G)=\textrm{max}\\{e(H)/v(H)\mid H\subseteq G\\}$ (the $m$-density of $G$),
and we say that $G$ is balanced if $e(G)/v(G)=m(G)$.

######  Theorem 3.2.

Let $K$ and $G$ be graphs such that $m_{2}(K)\geq m_{2}(G)\geq 1$. Let
$d(K)=\frac{e(K)}{v(K)}$ and assume that $K$ is balanced. Let $G$ be a
$k$-chromatic graph with $k\geq 3$ such that $m(G)\leq d(K)$. Suppose the
following conditions are satisfied.

  1. 1.

There exist graphs $K^{\prime}$ and $G^{\prime}$ obtained by deleting one
vertex of $K$ and $G$, respectively, such that $d(K)\geq
m_{2}(K^{\prime},G^{\prime})$, $m_{2}(K^{\prime})\geq m_{2}(G^{\prime})\geq
1$, and $K^{\prime}$ is strictly 2-balanced with respect to
$m_{2}(\cdot,G^{\prime})$ or $m_{2}(K^{\prime})=m_{2}(G^{\prime})$.

  2. 2.

There exists a graph $K^{\prime\prime}$ obtained by deleting two vertices from
$K$ such that $d(K)\geq m_{2}(K^{\prime\prime},G)$,
$m_{2}(K^{\prime\prime})\geq m_{2}(G)\geq 1$ and $K^{\prime\prime}$ is
strictly 2-balanced with respect to $m_{2}(\cdot,G)$ or
$m_{2}(K^{\prime\prime})=m_{2}(G)$.

  3. 3.

$G$ is a subgraph of the graph obtained by taking the complete balanced
$(k-1)$-partite graph on $(k-1)|V(G)|$ vertices and adding $k-2$ additional
edges, which are contained in distinct partite sets.

Then for $\frac{k-3}{k-2}<d\leq\frac{k-2}{k-1}$,

$p(n;K,G,d)=n^{-1/d(K)}.$

###### Proof.

For the lower bound, let $p=o\left(n^{-1/d(K)}\right)$ and
$\frac{k-3}{k-2}<d\leq\frac{k-2}{k-1}$. Define $\Gamma_{n}$ to be the complete
balanced $(k-1)$-partite graph on $n$ vertices, and color the edges of
$\Gamma_{n}$ blue. Color the remaining edges of $\Gamma_{n}\cup G(n,p)$ red.
Since $n^{-1/d(K)}$ is the threshold function for $G(n,p)$ to contain $K$
[11], and since $G$ is $k$-partite, with high probability $\Gamma_{n}\cup
G(n,p)$ contains no red $K$ or blue $G$ in this 2-coloring.

For the upper bound, let $p=\omega\left(n^{-1/d(K)}\right)$ and
$\frac{k-3}{k-2}<d\leq\frac{k-2}{k-1}$. Let $\Gamma$ be an $n$-vertex graph of
density $d$, for sufficiently large $n$. By Theorem 2.3 with
$\delta=d-\frac{k-3}{k-2}$ and $\varepsilon>0$, there are vertex sets
$V_{1},\dots,V_{k-1}$ of size $\eta n$ such that $(V_{i},V_{j})$ is an
$\varepsilon$-regular pair of density at least $\delta/2$ for all $i<j$. Let
$t=|V(K)|$ and $m=|V(G)|$. Choose $\varepsilon$ small enough so that
$(\delta/2-\varepsilon)^{t+m-1}>\varepsilon$. By Lemma 2.2 applied to the
pairs of the form $(V_{1},V_{i})$, we can choose $\varepsilon$ so that at
least a $\frac{k-2}{k-1}$ proportion of the $(t+m)$-sets of $V_{1}$ have a
common neighborhood in $\Gamma$ of size at least
$(\delta/2-\varepsilon)^{t+m}|V_{i}|$ in $V_{i}$. Then at least a
$\frac{1}{k-1}$ proportion of the $(t+m)$-sets of $V_{1}$ have a common
neighborhood in $\Gamma$ of size at least
$(\delta/2-\varepsilon)^{t+m}|V_{i}|$ in $V_{i}$ for all $2\leq i\leq k-1$.

Let $F$ be the disjoint union of $K$ and $G$. Let $\mathcal{H}$ be all the
possible copies of $F$ on the $(t+m)$-sets in $V_{1}$ described above with
large common neighborhoods in $\Gamma$ in each of $V_{2},\ldots,V_{k-1}$. Then
there is some $\xi>0$ depending only on $t,m$, and $d$ such that
$|\mathcal{H}|\geq\xi n^{t+m}$. Since $p=\omega\left(n^{-1/d(K)}\right)$, it
follows from the fact that $K$ is balanced and $m(G)\leq d(K)$ that
$\mu_{1}(F)=\omega(1)$, where $\mu_{1}$ is as in Theorem 2.4. By Theorem 2.4,
the probability that $G(n,p)[V_{1}]$ does not contain a copy of $F$ with
vertex set in $\mathcal{H}$ is at most
exp$(-\xi\omega(1)/(2^{t+m+1}(t+m)!))=o(1)$. Thus, with high probability,
$G(n,p)[V_{1}]$ contains a copy $F_{1}$ of $F$ whose common neighborhood, say
$U_{i}$, in $V_{i}$ has size at least $(\delta/2-\varepsilon)^{t+m}|V_{i}|$
for all $2\leq i\leq k-1$. Now take $\alpha$ so that $\alpha
2^{t+m}=(\delta/2-\varepsilon)^{t+m}$, so in particular, $|U_{i}|\geq\alpha
2^{t+m}|V_{i}|$ for all $2\leq i\leq k-1$. Take an arbitrary 2-coloring of the
edges of $\Gamma\cup G(n,p)$. By the pigeonhole principle, for each $2\leq
i\leq k-1$ we can find a subset $U_{i}^{\prime}\subset U_{i}$ of size at least
$\alpha|V_{i}|$ such that for every vertex $v\in V(F_{1})$, each edge $vu$
with $u\in U_{i}^{\prime}$ has the same color.

Since $d(K)\geq m_{2}(K^{\prime},G^{\prime})$ and $d(K)\geq
m_{2}(K^{\prime\prime},G)$, by Theorem 2.6, $G(n,p)$ is $\alpha\eta$-globally
$(K^{\prime},G^{\prime})$-Ramsey and $\alpha\eta$-globally
$(K^{\prime\prime},G)$-Ramsey with high probability. Suppose there are
vertices $u,v\in V(F_{1})$ such that all edges from $u$ to $U_{2}^{\prime}$
are red and all edges from $v$ to $U_{2}^{\prime}$ are blue. Since $G(n,p)$ is
$\alpha\eta$-globally $(K^{\prime},G^{\prime})$-Ramsey, $U_{2}^{\prime}$
contains either a red copy of $K^{\prime}$ or a blue copy of $G^{\prime}$.
However, if $U_{2}^{\prime}$ contains a red copy of $K^{\prime}$, then this
creates a red copy of $K$ with $u$, and if $U_{2}^{\prime}$ has a blue copy of
$G^{\prime}$, then this makes a blue copy of $G$ with $v$. Hence, we may
assume that the edges from $V(F_{1})$ to $U_{2}^{\prime}$ are either all red
or all blue. First assume that all of the edges from $V(F_{1})$ to
$U_{2}^{\prime}$ are red. Since $G(n,p)$ is $\alpha\eta$-globally
$(K^{\prime\prime},G)$-Ramsey, we have that $U_{2}^{\prime}$ contains a red
copy of $K^{\prime\prime}$. We may assume that one of the edges of the copy of
$G$ in $F_{1}$ is red, and we then obtain a red copy of $K$. Therefore, all of
the edges from $V(F_{1})$ to $U_{2}^{\prime}$ must be blue. By a similar
argument, we may assume that all of the edges from $V(F_{1})$ to
$U_{i}^{\prime}$ are blue for all $2\leq i\leq k-1$.

By decreasing $\varepsilon$ if necessary, we may assume that
$\alpha>\varepsilon$, where $\alpha$ is defined as above. Then since
$|U_{i}^{\prime}|\geq\alpha|V_{i}|$ for $2\leq i\leq k-1$, Lemma 2.2 implies
that $(U_{i}^{\prime},U_{j}^{\prime})$ is an
$\frac{\varepsilon}{\alpha}$-regular pair with density $\delta^{\prime}>0$ for
all $2\leq i<j\leq k-1$. Now, by an inductive argument on $k$, we may find a
copy $F_{i}$ of $F$ in $U_{i}^{\prime}$ for $2\leq i\leq k-2$ and a constant
$\alpha^{\prime}$ depending only on $\varepsilon$ such that there exists a
vertex set $U_{k-1}^{\prime\prime}\subset V_{k-1}$ of size
$\alpha^{\prime}\eta n$ for which all edges with endpoints coming from
distinct vertex sets among $V(F_{1}),\dots,V(F_{k-2})$ and
$U_{k}^{\prime\prime}$ are blue. (Indeed, the base case $k=3$ was essentially
proved above.) Furthermore, we may assume that each $F_{i}$ contains at least
one blue edge, as otherwise it contains a red copy of $K$. However, by our
assumptions on $G$, this implies that $\Gamma\cup G(n,p)$ contains a blue copy
of $G$. Therefore, $\Gamma\cup G(n,p)$ is $(K,G)$-Ramsey with high
probability. ∎

##  4 Applications of Theorems 3.1 and 3.2

In this section, we show that Theorem 3.1 can be applied when $K$ is a
complete graph and $G$ is a complete graph minus a perfect matching. Denoting
by $K_{s}^{\prime}$ the complete graph on $s$ vertices minus a maximum
matching, we determine the threshold function $p(n;K_{t},K_{s}^{\prime},d)$
for the range of densities $\frac{k-2}{k-1}\leq d\leq\frac{k-1}{k}$ for each
integer $k$ such that $2\leq k<\frac{s}{3}$.

######  Corollary 4.1.

Let $K_{s}^{\prime}$ be the graph obtained by deleting a maximum matching from
the complete graph $K_{s}$. For an integer $2\leq k<\frac{s}{3}$ and in the
range of densities $\frac{k-2}{k-1}\leq d\leq\frac{k-1}{k}$, we have that for
$t\geq s\geq 7$,

$p(n;K_{t},K_{s}^{\prime},d)=n^{-1/m_{2}(K_{t},K_{\lceil
s/k\rceil}^{\prime})}.$

###### Proof.

It suffices to show that the hypothesis of Theorem 3.1 is satisfied when we
take $K=K_{t}$, $G=K_{s}^{\prime}$ and $H=K_{\lceil s/k\rceil}^{\prime}$. It
is clear that in every partition of $V(K_{s}^{\prime})$ into $k$ sets
$V_{1},\dots,V_{k}$, some part contains $K_{\lceil s/k\rceil}^{\prime}$, and
that taking $k$ copies of $K_{\lceil s/k\rceil}^{\prime}$ and adding all
possible edges between each pair of copies contains $K_{s}^{\prime}$.

Routine calculation shows that $m_{2}(K_{t})\geq
m_{2}(K_{s}^{\prime}),m_{2}(K_{\lceil s/k\rceil}^{\prime})$ and that $K_{t}$
is strictly 2-balanced with respect to $m_{2}(\cdot,K_{s}^{\prime})$ and
$m_{2}(\cdot,K_{\lceil s/k\rceil}^{\prime})$.

Similarly, $m_{2}(K_{t-1})\geq m_{2}(K_{s}^{\prime})$, and $K_{t-1}$ is
strictly 2-balanced with respect to $K_{s}^{\prime}$. It is also routine to
check that $m_{2}(K_{t},K_{\lceil s/k\rceil}^{\prime})\geq
m_{2}(K_{t-1},K_{s}^{\prime})$.

Finally, by Theorem 1.5 in [14], the 0-statement for Conjecture 1.2 holds for
the pair $(K_{t},K_{\lceil s/k\rceil}^{\prime})$.

Therefore, we may apply Theorem 3.1, and this completes the proof. ∎

######  Remark.

We require that $k<\frac{s}{3}$ in Theorem 3.1 since if
$k\geq\lceil\frac{s}{3}\rceil$. then $K_{\lceil\frac{s}{3}\rceil}^{\prime}$ is
a subgraph of the path on 3 vertices. Hence,
$m_{2}(K_{\lceil\frac{s}{3}\rceil}^{\prime})\leq 1$, so the statement of
Conjecture 1.2 does not apply to the pair
$(K_{t},K_{\lceil\frac{s}{3}\rceil}^{\prime})$ when $k\geq\frac{s}{3}$.

Additionally, in [18] Das and Treglown proved that for an integer $2\leq
k<\frac{s}{2}$ and for the range of densities $\frac{k-2}{k-1}\leq
d\leq\frac{k-1}{k}$, if $k=2$ or $s\equiv 1$ (mod $k$), then

$p(n;K_{t},K_{s},d)=n^{-1/m_{2}(K_{t},K_{\lceil s/k\rceil})}.$

However, if $k\geq 3$ and $s\not\equiv 1$ (mod $k$), they only show that

$p(n;K_{t},K_{s},d)=n^{-(1-o(1))/m_{2}(K_{t},K_{\lceil s/k\rceil})}.$

We are able to use Theorem 3.1 to remove the $o(1)$ term in the expression,
and thus obtain an exact threshold function when $k\geq 3$ and $s\not\equiv 1$
(mod $k$).

######  Corollary 4.2.

Let $s,t,k$ be integers with $k\geq 2$ and $t\geq s\geq 2k+1$, and let
$\frac{k-2}{k-1}\leq d\leq\frac{k-1}{k}$. Then

$p(n;K_{t},K_{s},d)=n^{-1/m_{2}(K_{t},K_{\lceil s/k\rceil})}.$

###### Proof.

The proof is similar to the proof of Corollary 4.1, i.e., it is a
straightforward application of Theorem 3.1. ∎

Das and Treglown also determined the threshold function for pairs of the form
$(K_{t},C_{2k+1})$ [18]. Specifically, they showed that for $0<d\leq 1/2$,

$p(n;K_{t},C_{2k+1},d)=n^{-2/(t-1)}.$

Using Theorem 3.2, we generalize this result to pairs $(K_{t},G)$ for $t\geq
5$ including, for example, the cases where $G$ is an odd cycle, an odd cycle
with a chord, an even cycle with a chord connecting two vertices an even
distance away along the cycle, or a star on at least 3 vertices with an
additional vertex that is adjacent to each vertex of the star.

######  Corollary 4.3.

Given a tree $T$ with at least 4 vertices, let $G$ be a graph obtained by
adding a vertex $v$ to $T$ and edges from $v$ to $V(T)$ such that there is no
2-coloring of $T$ where the vertices in $N_{G}(v)$ are all the same color, but
there is some vertex $u\in N_{G}(v)$ such that there is a 2-coloring of $T$
where the vertices of $N_{G}(v)\setminus\\{u\\}$ are colored with the same
color.

Then for $t\geq 5$ and $0<d\leq 1/2$,

$p(n;K_{t},G,d)=n^{-2/(t-1)}.$

###### Proof.

This follows from applying Theorem 3.2 when $K=K_{t}$ and $G$ is given as in
the statement of this corollary. The graph $G^{\prime}$ is obtained by
deleting $v$, hence $G^{\prime}=T$. We also have that $K^{\prime}=K_{t-1}$ and
$K^{\prime\prime}=K_{t-2}$.

Here, $d(K)=\frac{t-1}{2}$, and it is straightforward to verify that
$\frac{t-1}{2}\geq m_{2}(K_{t-1},T)=\frac{t-1}{2}$, $m_{2}(K_{t-1})\geq
m_{2}(T)=1$, and $K_{t-1}$ is strictly 2-balanced with respect to
$m_{2}(\cdot,G^{\prime})$.

Note that $m_{2}(G)\leq 2$, and it is straightforward to verify that
$m_{2}(K_{t-2})\geq m_{2}(G)\geq 1$ and $K_{t-2}$ is strictly 2-balanced with
respect to $m_{2}(\cdot,G)$.

Notice that $G$ is 3-chromatic, so we are applying Theorem 3.2 for $k=3$. Take
a 2-coloring of $T$ where the vertices $N_{G}(v)\setminus\\{u\\}$ all have the
same color, say red. Let $V_{1}$ be the set of red vertices and $V_{2}$ be the
set of blue vertices, and add all possible edges in between $V_{1}$ and
$V_{2}$. Then add $v$ to $V_{2}$, add an edge between $v$ and $u$ ($u$ must be
colored blue and hence is in $V_{2}$), then add all edges between $v$ and
$V_{1}$. The resulting graph contains $G$ as a subgraph, so the last condition
in Theorem 3.2 is satisfied. This completes the proof. ∎

In the following corollary, we present another application of Theorem 3.2
where $K$ has significantly fewer edges than a complete graph.

######  Corollary 4.4.

Let $K$ be the graph obtained by taking a star on $t\geq 4$ vertices and
adding a new vertex that is adjacent to each vertex of the star. Let $G$ be as
in Corollary 4.3. Then for $0<d\leq 1/2$,

$p(n;K,G,d)=n^{-(t+1)/(2t-1)}.$

###### Proof.

Let $T$ be a star on $t\geq 4$ vertices, and let $v$ be the vertex of $K$ that
is adjacent to each vertex in $T$. We have that $d(K)=\frac{2t-1}{t+1}$ and
$m_{2}(K)=2$. Let $K^{\prime}=T$, and let $G^{\prime}$ be as in the proof of
Corollary 4.3. Then $d(K)\geq m_{2}(K^{\prime},G^{\prime})=1$ and
$m_{2}(K^{\prime})=m_{2}(G^{\prime})=1$.

Let $K^{\prime\prime}$ be obtained by deleting 2 vertices of $T$ from $K$. It
is straightforward to check that $d(K)\geq m_{2}(K^{\prime\prime},G)$,
$m_{2}(K^{\prime\prime})\geq m_{2}(G)\geq 1$ and $K^{\prime\prime}$ is
strictly 2-balanced with respect to $m_{2}(\cdot,G)$.

Finally, $G$ satisfies the last condition of Theorem 3.2 as in the proof of
Corollary 4.3.

This completes the proof since $n^{-1/d(K)}=n^{-(t+1)/(2t-1)}$. ∎

## Acknowledgements

Work on this project started during the Research Training Group (RTG) rotation
at Iowa State University. Both authors were supported by NSF grant
DMS-1839918. We would like to thank Ryan Martin for helpful discussions during
early stages of this project.

## References

  * [1] E. Aigner-Horev, O. Danon, D. Hefetz, and S. Letzter.  Large rainbow cliques in randomly perturbed dense graphs.  SIAM J. Discrete Math., 36(4):2975–2994, 2022.
  * [2] E. Aigner-Horev, O. Danon, D. Hefetz, and S. Letzter.  Small rainbow cliques in randomly perturbed dense graphs.  Eur. J. Comb., 101:103452, 2022.
  * [3] E. Aigner-Horev and Y. Person.  Monochromatic Schur triples in randomly perturbed dense sets of integers.  SIAM J. Discrete Math., 33(4):2175–2180, 2019.
  * [4] J. Balogh, J. Finlay, and C. Palmer.  Rainbow connectivity of randomly perturbed graphs.  arXiv:2112.13277, 2021.
  * [5] J. Balogh, R. Morris, and W. Samotij.  Independent sets in hypergraphs.  J. Am. Math. Soc., 28(3):669–709, 2015.
  * [6] J. Balogh, A. Treglown, and A. Z. Wagner.  Tilings in randomly perturbed dense graphs.  Comb. Probab. Comput., 28(2):159–176, 2019.
  * [7] W. Bedenknecht, J. Han, Y. Kohayakawa, and G. O. Mota.  Powers of tight Hamilton cycles in randomly perturbed hypergraphs.  Random Struct. Algor., 55(4):795–807, 2019.
  * [8] P. Bennett, A. Dudek, and A. Frieze.  Adding random edges to create the square of a Hamilton cycle.  arXiv:1710.02716, 2017.
  * [9] T. Bohman, A. Frieze, M. Krivelevich, and R. Martin.  Adding random edges to dense graphs.  Random Struct. Algor., 24(2):105–117, 2004.
  * [10] T. Bohman, A. Frieze, and R. Martin.  How many random edges make a dense graph Hamiltonian?  Random Struct. Algor., 22(1):33–42, 2003.
  * [11] B. Bollobás.  Random graphs.  In Combinatorics, Proceedings, pages 80–102. Swansea, 1981.
  * [12] J. Böttcher, J. Han, Y. Kohayakawa, R. Montgomery, O. Parczyk, and Y. Person.  Universality for bounded degree spanning trees in randomly perturbed graphs.  Random Struct. Algor., 55(4):854–864, 2019.
  * [13] J. Böttcher, R. Montgomery, O. Parczyk, and Y. Person.  Embedding spanning bounded degree graphs in randomly perturbed graphs.  Mathematika, 66(2):422–447, 2020.
  * [14] C. Bowtell, R. Hancock, and J. Hyde.  Proof of the Kohayakawa–Kreuter conjecture for the majority of cases.  arXiv:2307.16760, 2023.
  * [15] Y. Chang, J. Han, Y. Kohayakawa, P. Morris, and G. O. Mota.  Factors in randomly perturbed hypergraphs.  Random Struct. Algor., 60(2):153–165, 2022.
  * [16] S. Das, C. Knierim, and P. Morris.  Schur properties of randomly perturbed sets.  arXiv:2205.01456, 2022.
  * [17] S. Das, P. Morris, and A. Treglown.  Vertex Ramsey properties of randomly perturbed graphs.  Random Struct. Algor., 57(4):983–1006, 2020.
  * [18] S. Das and A. Treglown.  Ramsey properties of randomly perturbed graphs: cliques and cycles.  Comb. Probab. Comput., 29(6):830–867, 2020.
  * [19] A. Dudek, C. Reiher, A. Ruciński, and M. Schacht.  Powers of Hamiltonian cycles in randomly augmented graphs.  Random Struct. Algor., 56(1):122–141, 2020.
  * [20] L. Gugelmann, R. Nenadov, Y. Person, N. Škorić, A. Steger, and H. Thomas.  Symmetric and asymmetric Ramsey properties in random hypergraphs.  In Forum of Mathematics, Sigma, volume 5, page e28. Cambridge University Press, 2017.
  * [21] J. Han and Y. Zhao.  Hamiltonicity in randomly perturbed hypergraphs.  J. Comb. Theory Ser. B, 144:14–31, 2020.
  * [22] R. Hancock, K. Staden, and A. Treglown.  Independent sets in hypergraphs and Ramsey properties of graphs and the integers.  SIAM J. Discrete Math., 33(1):153–188, 2019.
  * [23] J. Hyde.  Towards the 0-statement of the Kohayakawa–Kreuter conjecture.  Comb. Probab. Comput., 32(2):225–268, 2023.
  * [24] S. Janson, T. Łuczak, and A. Ruciński.  Random Graphs.  Wiley, 2000.
  * [25] F. Joos and J. Kim.  Spanning trees in randomly perturbed graphs.  Random Struct. Algor., 56(1):169–219, 2020.
  * [26] K. Katsamaktsis and S. Letzter.  Rainbow Hamiltonicity in uniformly coloured perturbed graphs.  arXiv:2304.09155, 2023.
  * [27] Y. Kohayakawa and B. Kreuter.  Threshold functions for asymmetric Ramsey properties involving cycles.  Random Struct. Algor., 11:245–276, 1997.
  * [28] J. Komlós and M. Simonovits.  Szemerédi’s regularity lemma and its applications in graph theory.  In Combinatorics, Paul Erdős is eighty, Vol. 2, pages 295–352. János Bolyai Math. Soc., 1996.
  * [29] M. Krivelevich, M. Kwan, and B. Sudakov.  Cycles and matchings in randomly perturbed digraphs and hypergraphs.  Comb. Probab. Comput., 25(6):909–927, 2016.
  * [30] M. Krivelevich, M. Kwan, and B. Sudakov.  Bounded-degree spanning trees in randomly perturbed graphs.  SIAM J. Discrete Math., 31(1):155–171, 2017.
  * [31] M. Krivelevich, B. Sudakov, and P. Tetali.  On smoothed analysis in dense graphs and formulas.  Random Struct. Algor., 29:180–193, 09 2006.
  * [32] E. Kuperwasser and W. Samotij.  The list-Ramsey threshold for families of graphs.  arXiv:2305.19964, 2023.
  * [33] E. Kuperwasser, W. Samotij, and Y. Wigderson.  On the Kohayakawa–Kreuter conjecture.  arXiv:2307.16611, 2023.
  * [34] A. Liebenau, L. Mattos, W. Mendonça, and J. Skokan.  Asymmetric Ramsey properties of random graphs for cliques and cycles.  arXiv:2010.11933, 2020.
  * [35] M. Marciniszyn, J. Skokan, R. Spöhel, and A. Steger.  Asymmetric Ramsey properties of random graphs involving cliques.  Random Struct. Algor., 34, 2009.
  * [36] A. McDowell and R. Mycroft.  Hamilton $\ell$-cycles in randomly perturbed hypergraphs.  Electron. J. Comb., 25(4):4–36, 2018.
  * [37] F. Mousset, R. Nenadov, and W. Samotij.  Towards the Kohayakawa–Kreuter conjecture on asymmetric Ramsey properties.  Comb. Probab. Comput., 29:943–955, 2020.
  * [38] R. Nenadov and A. Steger.  A short proof of the random Ramsey theorem.  Comb. Probab. Comput., 25(1):130–144, 2016.
  * [39] R. Nenadov and M. Trujić.  Sprinkling a few random edges doubles the power.  SIAM J. Discrete Math., 35(2):988–1004, 2021.
  * [40] E. Powierski.  Ramsey properties of randomly perturbed dense graphs.  arXiv:1902.02197, 2019.
  * [41] F. P. Ramsey.  On a problem of formal logic.  Proc. Lond. Math. Soc., 30:264–286, 1930.
  * [42] V. Rödl and A. Ruciński.  Lower bounds on probability thresholds for Ramsey properties.  In Combinatorics, Paul Erdős is eighty, Vol. 1, pages 317–346. János Bolyai Math. Soc., 1993.
  * [43] V. Rödl and A. Ruciński.  Random graphs with monochromatic triangles in every edge coloring.  Random Struct. Algor., 5(2):253––270, 1994.
  * [44] V. Rödl and A. Ruciński.  Threshold functions for Ramsey properties.  J. Am. Math. Soc., 8(4):917–942, 1995.
  * [45] D. Saxton and A. Thomason.  Hypergraph containers.  Invent. Math., 201(3):925–992, 2015.
  * [46] P. Turán.  On an extremal problem in graph theory (in Hungarian).  Math. Fiz. Lapok, 48:436–452, 1941.


# Some models are useful, but for how long?: A decision theoretic approach to
choosing when to refit large-scale prediction models

Kentaro Hoffman
University of Washington
Seattle, WA
<EMAIL_ADDRESS>
&Stephen Salerno
Fred Hutch Cancer Center
Seattle, WA
<EMAIL_ADDRESS>
Jeff Leek
Fred Hutch Cancer Center
Seattle, WA
<EMAIL_ADDRESS>
Tyler McCormick
University of Washington
Seattle, WA
<EMAIL_ADDRESS>

###### Abstract

Large-scale prediction models (typically using tools from artificial
intelligence, AI, or machine learning, ML) are increasingly ubiquitous across
a variety of industries and scientific domains. Such methods are often paired
with detailed data from sources such as electronic health records, wearable
sensors, and omics data (high-throughput technology used to understand
biology). Despite their utility, implementing AI and ML tools at the scale
necessary to work with this data introduces two major challenges. First, it
can cost tens of thousands of dollars to train a modern AI/ML model at scale.
Second, once the model is trained, its predictions may become less relevant as
patient and provider behavior change, and predictions made for one
geographical area may be less accurate for another. These two challenges raise
a fundamental question: how often should you refit the AI/ML model to
optimally trade-off between cost and relevance? Our work provides a framework
for making decisions about when to refit AI/ML models when the goal is to
maintain valid statistical inference (e.g. estimating a treatment effect in a
clinical trial). Drawing on portfolio optimization theory, we treat the
decision of recalibrating versus refitting the model as a choice between
“investing” in one of two “assets.” One asset, recalibrating the model based
on another model, is quick and relatively inexpensive but bears uncertainty
from sampling and the possibility that the other model is not relevant to
current circumstances. The other asset, refitting the model, is costly but
removes the irrelevance concern (though not the risk of sampling error). We
explore the balancing act between these two potential investments in this
paper.

##  1 Introduction

With the rapid advancement of artificial intelligence (AI) and machine
learning (ML), large-scale models are becoming standard tools in scientific
research and industry settings to to generate predictions of hard-to-measure
outcomes [47]. For example, AI/ML techniques applied to electronic health
records can identify metastatic cancers [56, 3], determine causes of death
[15], or provide targeted real-time early warning systems for adverse health
events such as sepsis in emergent settings [53]. Transformer models such as
AlphaFold can predict protein structures from easily obtained amino acid
sequences [22]. Deep learning of spatio-temporal dependencies in energy
consumption data can forecast future consumption patterns [41]. Today,
researchers and practitioners benefit from large generative AI models, which
have afforded greater access to AI/ML infrastructure and have enabled the
performance of more general tasks with a high degree of accuracy [55, 42].
Particularly in research, AI/ML predicted outcomes are then used in place of
the true, unmeasured outcomes for downstream inference [i.e., finding
associations, estimating a treatment effect; see 48, 6, 32].

The economic cost of computing to train these complex prediction models can
easily reach into the tens of thousands of dollars [40]. There are, of course,
organizations that exploit economies of scale and train general models for a
wide variety of prediction tasks [30, 31], although even in these settings,
some local training is typically required for high-quality predictions. Models
also decay with time – user behavior changes, healthcare technology and norms
adapt, physical systems evolve , and concept and model drift occur [33, 45,
49, 26, 57] – meaning that users must answer a fundamental question: what is
the optimal strategy for maintaining model accuracy and relevance?

We address this question in the context of statistical inference, where a user
wants to perform downstream statistical tests based on outcomes generated from
said prediction model. Inference is critical in a range of scientific settings
to learn associations between observable covariates and outcomes or estimate
treatment effects in randomized experiments. For example, global public health
researchers can estimate cause-specific death rates by regional differences in
demographics using NLP-derived cause-of-death labels from verbal autopsies
[15]. In the context of pragmatic clinical trials, trialists predict outcomes
that may have occurred between regularly scheduled clinic visits to better
estimate the real-world effectiveness of interventions in everyday clinical
practice [16, 52].

In this work, we propose a pragmatic strategy for choosing when to refit
complex prediction models, when the goal is inference, by exploiting a novel
connection to portfolio optimization theory. We compare three distinct
strategies: (1) fully refitting the ML/AI model from scratch, (2) partially
recalibrating predictions using a small new sample, or (3) simply retaining
the existing model without update. The decision of whether to refit,
recalibrate, or retain involves significant financial considerations. Fully
refitting a large-scale predictive model can incur substantial computational
resource, labor, and time costs [40]. Recalibrating uses a few labeled samples
to adjust for bias induced by the prediction model, though we do not know
until after making the decision how effective this will be. Instead, we only
know how well a similar procedure worked in a previous calibration period.
Retaining the existing model without updates, while cost-free in the short
term, risks a gradual decline in accuracy and relevance of the model over time
[46].

We approach refitting versus recalibrating using portfolio optimization
theory, where this decision is treated as ‘investing’ in one of two options,
or ‘assets.’ This powerful connection, to our knowledge, has not yet been
exploited in the machine learning literature. Portfolio theory comes with a
natural language for expressing uncertainty. Refitting the model has
statistical uncertainty, or risk. We know approximately how well our
prediction algorithm will do based on prior fits of the model, but we expect
some variation based on the inherent stochasticity of the prediction task.
Recalibrating also introduces ambiguity, meaning that we do not know how much
the prediction model has decayed from the last time it was trained and, thus,
how effective our adjustment will be. Portfolio optimization theory has a
similar conundrum, where an investor must choose between assets (stocks,
bonds, etc.) that are volatile, but in a mostly predictable way, and more
uncertain assets where the distribution of volatility is harder to predict. In
both cases, it is impossible to characterize the optimal decision solely in
terms of statistical properties – the user has incomplete information in a
stochastic environment, which necessitates introducing idiosyncratic user
preferences to avoid either risk or ambiguity.

We formalize this connection to portfolio optimization, after providing a full
description of the three options, in Section 2. Decisions depend on a
specified utility function that weighs the loss associated with each choice,
plus user-specific preferences that represent aversion to risk and ambiguity.
Specifying these preference parameters typically requires an extensive
solicitation process. In Section 2.2, we propose an alternative that requires
specifying only a Type 1 error rate. Section 3 provides simulation results and
Section 4 gives an example decision process in the context of electric
consumption forecasting. We conclude with limitations and future directions.

##  2 Determining the Optimal Strategy

###  2.1 Decision Rule

We assume that the user starts with a trained AI/ML model and access to a
stable (calibration) period where they can collect new training feature
(predictor) and ground-truth label (outcome) data. The goal is optimally
decide how to maintain the model at some point in the future when its
performance may have changed by an unknown amount, having seen the predictors
and predicted outcomes leading up to that point. The three potential
strategies trade-off between cost, risk, and ambiguity:

  1. 1.

Retain the model - Cheap but uncertain. Responses may no longer be
accurate/useful.

  2. 2.

Refit the model - Expensive but certain. Need to collect new training data,
plus pay model fitting cost. Inherent/natural variation in data generating
process (risk).

  3. 3.

Recalibrate the model - Intermediate option. Use a few labeled cases to
estimate adjustment factor that accounts for concept drift. Natural variation
in data generating process (risk) and uncertain quality of the correction
factor (ambiguity).

As we only collect new data after the decision to refit or recalibrate, our
strategy must reflect our present uncertainty surrounding the future model’s
performance. To accomplish this, we exploit a novel parallel to selecting the
optimal asset distribution in the presence of stochastic returns from
portfolio optimization theory [8, 29]. In choosing an asset distribution, the
goal is to assign a fixed amount of wealth between assets, with stochastic
returns, to maximize a given economic utility function. Our ‘assets’ are the
three strategies, and we seek to minimize the mean squared error (MSE) in
statistical inference subject cost, budget, and preferences over
risk/ambiguity. Importantly, the MSE is for estimating the parameters of a
model we wish to draw inference on, using outcomes predicted from our AI/ML
model, and not the mean squared error of the AI/ML model itself. To formalize
this, assume the maintainer of the AI/ML model is a rational actor [see 34].
Following Maccheroni et al. [27], we define the utility function, $U(\cdot)$,
such that

$U(MSE,\lambda,\theta)=-1\times
E_{P}(MSE)-\frac{\lambda}{2}\sigma^{2}_{P}(MSE)-\frac{\theta}{2}\sigma^{2}_{\mu}(MSE),$
(1)

where $E_{P}(MSE)$ is the expected MSE of the downstream inferential model,
$\sigma_{P}^{2}(MSE)$ and $\sigma_{\mu}^{2}(MSE)$ are the variation in the MSE
that are attributable to sampling (i.e., risk) versus variability in
estimating the recalibration factor (i.e., ambiguity), respectively. The
parameters $\lambda$ and $\theta$ are positive real numbers that indicate how
averse one is to risk and ambiguity, respectively. Letting $MSE_{rec}$,
$MSE_{ref}$, and $MSE_{ret}$ be the respective MSEs of the downstream
inferential model after recalibrating, refitting, or retaining the AI/ML
model, the optimal allocation of our budget between $MSE_{rec}$ and
$MSE_{ref}$ is determined by allocations $w_{rec}$ and $w_{ref}$ such that

$w_{rec}\times MSE_{rec}+w_{ref}\times MSE_{rec}$

maximizes our utility. Differentiating Eq. (1) with respect to $\lambda$ and
$\theta$ yields the system of equations

$\displaystyle\lambda$
$\displaystyle\begin{bmatrix}\sigma_{P}^{2}(MSE_{ref})&\sigma_{P}(MSE_{ref},MSE_{rec})\\\
\sigma_{P}(MSE_{ref},MSE_{rec})&\sigma_{P}^{2}(MSE_{rec})\end{bmatrix}\begin{bmatrix}\hat{w}_{ref}\\\
\hat{w}_{rec}\end{bmatrix}+$
$\displaystyle\quad\quad\theta\begin{bmatrix}0&0\\\
0&\sigma^{2}_{\mu}(MSE_{rec})\end{bmatrix}=\begin{bmatrix}E_{p}(MSE_{ref})-MSE_{ret)}\\\
E_{p}(MSE_{rec})-MSE_{ret)}\\\ \end{bmatrix}.$

where $\sigma_{P}(MSE_{ref},MSE_{rec})$ is the risk covariance for recalibrate
versus refit. The solution is

$\hat{w}_{rec}=\frac{BD-HA}{CD-H^{2}}\hskip 18.06749pt\hat{w}_{ref}=\frac{CA-
HB}{CD-H^{2}},$

where

$\displaystyle A$ $\displaystyle=-1*(E_{p}(MSE_{rec})-\overline{MSE_{ret}})$
$\displaystyle D=\lambda\sigma_{P}(MSE_{rec})+\theta\sigma_{\mu}(MSE_{ref})$
$\displaystyle B$ $\displaystyle=-1*(E_{p}(MSE_{ref})-\overline{MSE_{ret}})$
$\displaystyle H=\lambda\sigma_{P}(MSE_{ref},MSE_{rec}).$ $\displaystyle C$
$\displaystyle=\lambda\sigma_{P}(MSE_{ref})$

Finally, we choose the option has the larger allocation if it is better than
retaining, which yields the final decision rule

$\text{Decision Rule}=\begin{cases}\text{ Refit is Optimal}&\text{If
}\hat{w}_{ref}>\hat{w}_{rec}\text{ and }A>0\\\ \text{ Recalibrate is
Optimal}&\text{If }\hat{w}_{ref}>\hat{w}_{rec}\text{ and }B>0\\\ \text{ Retain
is Optimal }&\text{If }A<0\text{ and }B<0\end{cases}.$ (2)

###  2.2 Risk and Ambiguity Aversion

The above decision rule (2) relies on user-specified preferences for risk
($\lambda$) and ambiguity ($\theta$). Soliciting such preferences is an active
area of research, and there exists a large body of literature on the topic
[18, 12, 11, 28]. Two promising approaches, as described in Bonhomme and
Weidner [9], are a context-specific approach versus a hypothesis testing
approach. The context-specific approach elicits informative choices of
$\lambda$ and $\theta$ using prior knowledge of the type of misspecification.
The hypothesis testing approach is most salient when a user lacks such domain
knowledge.

We develop a strategy based on the hypothesis testing approach. Immediately
after AI/ML model training, we expect minimal drift, and thus retaining is
likely the best option. As we are dealing with a stochastic decision-making
process, there is always a nonzero probability that we could choose to refit
or recalibrate during this period. We can decrease the probability that
refitting or recalibrating is chosen by increasing $\lambda$ and $\theta$, our
aversion parameters. We choose values of $\lambda$ and $\theta$ such that,
early on, we have a less than $\alpha$ probability of choosing anything but to
retain the current model by setting

$\hat{\lambda}=\arg\min_{\lambda>0}\Pr[U(MSE_{ref},\lambda,0)>U(MSE_{ret},0,0)]\leq\alpha.$

Then, using $\hat{\lambda}$ as a plug-in estimator, we choose $\theta$ such
that

$\hat{\theta}=\arg\min_{\theta>0}\Pr[U(MSE_{rec},\hat{\lambda},\theta)>U(MSE_{ret},0,0)]\leq\alpha.$

This gives a simple approach for choosing $\lambda$ and $\theta$ that controls
the Type I error rate under a null hypothesis that there is no drift.
Alternative approaches based on likelihood-ratio testing [9], robust control
theory [7], and robust sequential hypothesis testing [37] could also be used.

###  2.3 Estimating the Mean Squared Errors of Each Strategy

We evaluate the mean squared errors for each of the three model maintenance
strategies when conducting downstream inference using predicted outcomes from
our upstream AI/ML model. That is, we use our AI/ML model to generate
predicted outcomes, $\hat{Y}$, which are then carried forward to a model that
estimates a parameter, $\beta$, describing the relationship between a set of
features, $X$, and $\hat{Y}$. In a randomized experiment, for example, $\beta$
is the effect of the treatment. We will denote the objective function for this
regression as

$\hat{\beta}=\arg\min_{\beta}g\left(\hat{Y},X;\beta\right).$

Let $g$ be a generalized linear model (e.g., $g=||\hat{Y}-X\beta||_{2}^{2}$ in
linear regression), however, this approach can be adapted to any model with a
convex objective function with a similar strategy. Let $\hat{Y}_{ret}$,
$\hat{Y}_{ref}$, $\hat{Y}_{rec}$, and $Y$ are the predicted $Y$ under the
retain, refit, and recalibrate strategies, and true $Y$, respectively.
Further, let $\hat{\beta}_{ret}$, $\hat{\beta}_{ref}$, $\hat{\beta}_{rec}$,
and ${\beta}$ represent the parameter vectors.

Since the MSE depends on the number of labeled/unlabeled observations we
collect, we also need to specify the relationship between budget and data
collection. Let our total budget be $c$, let model refitting cost be
$c_{model}$, let collecting $(X,Y)$ together cost $c_{labeled}$, and let
collecting $X$ alone cost $c_{unlabeled}$. If one retains a model, no model
refitting cost is needed, and one can use the entire budget to collect
$\frac{c}{c_{unlabeled}}$ samples to estimate $\beta$. If one refits a model,
one must first spend $c_{model}$ for refitting, leaving a budget of
$\frac{c-c_{model}}{c_{unlabeled}}$ samples. Finally, if one chooses to
recalibrate, choose the optimal ratio of labeled to unlabeled data ( costing
$\frac{c}{c_{labeled}}$ and $\frac{c}{c_{unlabeled}}$) respectively to best
estimate $\beta$ (we specify how to get this ratio below).

####  2.3.1 Strategy 1: Retain the Model

The simplest strategy is to continue using the original AI/ML model. In such a
case, we would expect the difference between $\beta$ and $\hat{\beta}_{ret}$
to grow with time as the model drifts. To measure the rate at which this
difference grows, we shall assume that post-initial training, the maintainers
have collected data at regular time intervals to evaluate the performance of
the model post-deployment. This is referred to as the monitoring, maintenance,
verification, or, the moniker we shall use, the calibration phase [38, 21].
During the calibration phase we shall repeatedly compare $\beta$ and
$\hat{\beta}_{ret}$ and fit a time series model to estimate the expected MSE
at $t_{future}$. This allows us to extrapolate out how well retaining the
model works from the calibration data, where we observe data, to $t_{future}$
where we are yet to observe data and a decision needs to be made. This can be
done via the algorithm below:

Retain: Do-Nothing Algorithm

  1. 1.

For each calibration point $t$ in calibration data $(\tau_{1},...,\tau_{T})$,

  2. Compute $\hat{\beta}_{ret,t}=\arg\min_{\beta}g(Y_{t},X_{t};\beta)$

    1. (a)

For $j$ in $1,...,B$, take a bootstrap sample $(X_{t}^{b}Y_{t}^{b})$ of size
$c/c_{unlab}$

    2. (b)

Compute $\hat{\beta}_{ret}^{b}=\arg\min_{\beta}g(Y_{t}^{b},X_{t}^{b};\beta)$

  3. 2.

$\hat{r}_{t}=||\hat{\beta}_{ret,t}-Median(\hat{\beta}_{ret}^{1},...,\hat{\beta}^{B})||_{2}^{2}$

  4. 3.

Fit a time series on $(\hat{r}_{\tau_{1}},...,\hat{r}_{\tau_{T}})$.

  5. 4.

$MSE_{ret}$ be the predicted value at $t_{future}$ using said time series

The bootstrap sample size of $c/c_{unlab}$ illustrates the fact that since
retaining does not require model refitting or additional labeled data, we get
our best estimate for the MSE by spending it all on the unlabeled data,
pushing it through our retained model, and computing its MSE.

####  2.3.2 Strategy 2: Refit the Model

If AI/ML model performance has degraded considerably, the best option may be
to retire the old model and refit a new one. We make the assumption that any
newly fit AI model, when trained on the new data, will have similar accuracy
to the previous model. To refit, one must spend $c_{model}$ of their budget to
train a new model and the remaining $(c-c_{model})/c_{unlab}$ for unlabeled
samples to estimate the accuracy of the estimates using the new model. Since
$g$ is a member of the generalized linear model family, we have, via Agresti
[2], that

$MSE(\hat{\beta}_{ref})=Var(\hat{\beta}_{ref})=(X^{T}WX)^{-1}.$

Here, $(X^{T}WX)$ is the information matrix for $\beta$, $W$ is the
corresponding weight matrix and $(X^{T}\hat{W}X)$ is the asymptotic covariance
estimated at $\hat{\beta}$. We estimate $MSE(\hat{\beta}_{refit})$ using the
bootstrap procedure described below:

AI Model refitting Algorithm

  1. 1.

For b in 1, …, B

    1. (a)

Take a bootstrap $(X^{b},Y^{b})$ of size $(c-c_{model})/(c_{unlab})$ from the
data that was held out during initial model training

    2. (b)

Compute $\hat{Var}(\hat{\beta}_{ref}^{b})=(X^{bT}\hat{W}^{b}X^{b})^{-1}$ where
$\hat{\beta}_{ref}^{b}=\arg\min_{\beta}g(Y_{t}^{b},X_{t}^{b};\beta)$

  2. 2.

$MSE_{ref}=$Median($\hat{Var}(\hat{\beta}^{1}_{ref}),...,\hat{Var}(\hat{\beta}^{b}_{ref}))$

####  2.3.3 Strategy 3: Recalibrate the Model

The middle ground between retaining and refitting is to recalibrate the model.
This requires us to first spend our budget on collecting an appropriate ratio
of unlabeled and labeled data. Regressing the AI/ML-estimated outcomes from
the unlabeled data against X yields a biased estimate of the parameter of
interest. Using the labeled data, we compare our AI/ML generated $\hat{Y}$ to
real $Y$ to learn the appropriate correction factor. Combining the biased
parameter estimate with its appropriate correction factor to conduct valid
statistical inference is what [20] call “Inference on Predicted Data.” Here,
we utilize a mature procedure for such inference known as “PPI++” Angelopoulos
et al. [5, 6] but other approaches that yield valid parameter estimates will
work as well. Given the associated loss function $l(X,Y;\beta)$ for estimator
of $\beta$, PPI++ is a parameter estimation procedure that minimizes:

$\displaystyle\hat{\beta}_{rec}$
$\displaystyle=\arg\min_{\beta}l(X_{unlab,i},\hat{Y}_{unlab,i};\beta)+\gamma*(l(X_{lab,i},$
$\displaystyle\hat{Y}_{lab,i};\beta)-l(X_{lab,i},Y_{lab,i};\beta))$
$\displaystyle=\hat{\beta}_{ref}-\gamma*\hat{\Delta}$

where $\gamma\in[0,1]$ is a data-estimated tuning parameter. When $\gamma$ is
close to 0, this indicates that the AI model is perfectly accurate and the
parameter estimates require no correction. Using the consistency results in
Angelopoulos et al. [6] allow us to decompose the MSE via:

$\displaystyle MSE(\hat{\beta}_{rec})$ $\displaystyle=Var(\hat{\beta}_{rec})$
$\displaystyle=Var(\hat{\beta}_{ref})+\gamma^{2}Var(\hat{\Delta}_{ref})$
$\displaystyle=(X_{unlab}^{T}\hat{W}X_{unlab})^{-1}+\gamma^{2}(X_{lab}^{T}\hat{D}_{ref}X_{lab})^{-1}$

where $(X_{lab}^{T}\hat{D}_{ref}X_{lab})$ is the information matrix for
$\hat{\Delta}$. To extend this recalibration procedure to our temporal
setting, we make the following extension to the PPI++ procedure:

AI/ML Model Recalibration Algorithm

  1. 1.

For each calibration point $t$, perform PPI++ and compute
$\hat{W}_{i,ref},\hat{D}_{i,ref},$ and $\hat{\gamma}_{i}$.

  2. 2.

Fit time series for $\hat{W}_{i,ref},\hat{D}_{i,ref},$ and $\hat{\gamma}_{i}$.

  3. 3.

Using said time series, estimate the forested distribution for for
$\hat{W}_{i,refit},\hat{\Delta}_{i,ref},$ and $\hat{\gamma}_{i}$ at
$t_{future}$.

  4. 4.

For each sample size ratios $\zeta\in(0,...,1)$:

    1. (a)

For $b=1,...B$:

      1. i.

Draw $\hat{\gamma}^{b}$, $\hat{W}_{i,ref}$, and $\hat{D}_{i,ref}$ from their
forecast distributions.

      2. ii.

Draw $(1-\zeta)*\frac{c}{c_{unlab}}$ samples of $X_{unlab}$ and
$(\zeta*\frac{c}{c_{lab}}$ samples of $X_{lab}$ with replacement. Call these
$X_{unlab}^{b}$ and $X_{lab}^{b}$ respectively.

      3. iii.

Let
$MSE_{ref}^{b}(\eta)=(X_{unlab}^{bT}\hat{W}^{b}X_{unlab})^{-1}+\gamma^{b2}(X_{lab}^{bT}\hat{D}_{refit}^{b}X_{lab}^{b})^{-1}$
.

    2. (b)

Let $MSE_{rec}(\eta)=Median(MSE_{rec}^{1}(\eta),...,MSE_{rec}^{B}(\eta))$.

  5. 5.

$MSE_{rec}=\min_{\eta}(MSE_{rec}(\eta))$

As time increases, we expect the original parameter estimates to become
increasingly unreliable. Thus, $\hat{\gamma}$ and $\hat{W}$ should decrease,
while $\hat{\Delta}$ should increase.

##  3 Simulation Study

We start by showing a simple simulation in which we know the ground truth. We
generate 10,000 samples of $X_{1},X_{2}$, independent standard normal
variables. We then generate

$Y(t)=X_{1}\cdot\exp(0.25t)+10\cdot I(X_{2}>=0)+\epsilon,$

where $I(\cdot)$ is the indicator function, and $\epsilon\sim N(0,0.05)$. We
start with a model that is trained to predict $Y$ from $X_{1}$ and $X_{2}$ at
time $t=0$. Then a downstream model estimates the relationship between $X_{1}$
and $Y$ via a linear regression, $\hat{Y}=X_{1}\hat{\beta}+\hat{\epsilon}$.

If the prediction model is accurate at time $t$, $\hat{\beta}$ should be close
to $\exp(0.25t)$. As $t$ increases, the prediction model will be less
accurate, and our model evaluation strategy will change from recalibrate to
refit. As our data generating mechanism contains a step function, a reasonable
choice for the prediction model is to use random forests trained with 5-fold
cross-validation.

We simulate a calibration period between times $t=0$ and $t=3$, where we have
50 distinct points in which 200 labeled and unlabeled samples were collected.
We seek to make a decision to refit, recalibrate, or retain at time point
$t=3.5$. Our total budget to make a decision is $200, the cost of model
fitting was $10, unlabeled data, $(X_{1,unlab},X_{2,unlab})$, each cost $1 to
collect, and labeled data, $(X_{1,lab},X_{2,lab},Y_{lab})$, cost $2. As we are
interested in a parameter from linear regression, $\hat{W}$ and
$\hat{D}_{refit}$ has a simple representation

$MSE(\hat{\beta}_{rec})\approx\hat{\sigma}_{unlab}(X_{unlab}^{T}X_{unlab})^{-1}+\gamma^{2}*\hat{\sigma}_{unlab}(X_{lab}^{T}X_{lab})^{-1}$

and $X=[X_{1},X_{2}]$. The approximation here comes from how the classical
$\hat{\sigma}_{unlab}(X_{unlab}^{T}X_{unlab})^{-1}$ estimator for the
variance-covariance matrix is known to be biased when $Y$ is nonlinear. The
common solution to this is to employ the sandwich estimator [51, 50, 25], but
in practice, we find the extra number of parameters this requires makes it
ill-suited for the extrapolation we require.

Table 1: Mean MSE and Variances for the 3 options from the Simulation Study  | Mean MSE | Variance from Uncertainty | Variance from Ambiguity
---|---|---|---
Retain | 0.133 | – | –
Recalibrate | 0.092 | 5.55e-06 | 8.28e-06
Refit | 0.073 | 9.10e-05 | –

With the settings above, each MSE estimation algorithm was run with 100
bootstrap samples on an M2 Max Macbook Pro with 32 GB of RAM, giving us the
mean MSEs and variances as seen in Table 1. From this, we see that the retain
strategy has the worst average MSE, followed by recalibrate and then refit.
However, the recalibrate MSE has lower variance than the refit MSE, so our
preference between the two is determined by how averse we are to ambiguity. In
Figure 1, we evaluate our decision rules with $\lambda$ varying from 0 to
0.00125 and $\theta$ varying from 0 to 0.0012. We find a clear trade-off where
one prefers to recalibrate when uncertainty aversion is high and refit when
ambiguity aversion is high. The utility function chosen by our Type I error
rate control with $\alpha=0.05$ indicates a preference for recalibration
(Figure 1, left panel, black cross). At no point is retention the optimal
choice under these simulation settings.

Figure 1: (Left): Our estimate of the best decision for various levels of
aversion to uncertainty ($\theta$) and ambiguity ($\lambda$). The hypothesis-
driven choice for $\lambda$, $\theta$ in Section 2.2 is marked with a square.
(Middle): $\frac{\hat{w}_{ref}}{w_{rec}}$ and $\lambda$ for various levels of
$\theta$. Values above 1 choose refit as optiomal. Above the horizontal line
denotes refit, below is recalibrate. (Right): $\frac{\hat{w}_{ref}}{w_{rec}}$
for various $\theta$’s and $\lambda$’s. Above the horizontal line is refit,
below is recalibrate.

##  4 Electricity Forecasting in New South Wales

As an example of decision-making using this procedure, we put ourselves in the
situation of a large data center in New South Wales, Australia that requires
2000MWh of electricity [1]. In early 2024, this is a little over half of the
capacity of the largest data center in the world [17]. To estimate electrical
costs, the company created a two-step model forecasting electrical costs as
follows:

  1. 1.

Step 1: Demand Forecasting Every half hour, our AI/ML demand forecasting model
estimates electrical demand $\hat{D}$ using data from the previous 7 days.

  2. 2.

Step 2: Elasticity Estimation All forecasts for the day are regressed against
price to obtain and estimate the daily price elasticity, $\beta$ from the
equation: $\hat{D}=\beta X_{price}+\hat{\epsilon}.$

All estimation will be done using the Elec2 dataset [19] downloaded from
Kaggle [39]. The data were pre-scaled so traditional log-log transformation
was omitted [54]. The reliability of this procedure is based on the AI/ML
demand model providing accurate forecasts of electrical demand. This makes
this procedure sensitive to unpredictable shocks such as natural disasters or
system failures. As an example of such a shock, midway through 1997, the
electrical grid of New South Wales joined the grid in the neighboring state of
Victoria to allow for load sharing. The decision maker, of course, may not
always know when a shock (or gradual drift) occurs. We use a calibration
period of 180 days with 60 days before grid unification and 120 days after. As
we see the ground truth, we expect recalibrating to be appealing at first and
then refitting to be preferable after unification. The decision-making process
does not rely on knowing when, or if, unification has occurred a priori.

Our demand forecasting model is a long short-term memory model (LSTM) of 336
cells (equivalent to one week of demand data measured every 30 minutes)
implemented in using the Keras machine learning library [13]. The model was
trained on 11,150 datapoints at the start of the study. The LSTM had a $\tanh$
activation function, a sigmoid function for the recurrent activation function,
and no dropout. All other parameters were set to the default as determined by
the keras3 package in R [23].

Figure 2: (Left): Electrical price elasticity over time. (Right): MSE of
estimated electrical price elasticity using the pre-unification forecast
model. Vertical purple line represents the grid unification day. The
elasticity and our ability to estimate rapidly decay, signifying a case of
concept drift.

We can see from Figure 2 that as soon as the grids were unified, the price
elasticity nearly doubled from 6 to 15. Consequently, our errors in estimating
$\beta$ increase 500%, from 0.186 to 0.903. Each day, the model makes 48,
30-minute-ahead demand forecasts. Our company would like us to decide using
this data and a budget of $4,800. For costs, the cost of fitting the model was
set at $ 4,000 and our local electrical provider has offered to provide us
$120 for each instantaneous measurement of demand and price $(c_{labeled})$ or
$100 for just the price $(c_{unlabeled})$.

Figure 3: (Left): The decision that we chose using our Type I error rate controlled utility function at each week up to and after grid unification. (Center): Choice preference 60 days before grid unification for a variety of utility functions. The black cross represents our Type I error rate controlled procedure. (Right): Choice preference 120 days after grid unification for a variety of utility functions.  Table 2: True values for mean MSE of $\beta$, estimated electrical bill for one month running the data center, and sum of differences between what we expected to pay versus what we paid  | Est. Avg MSE | True Avg MSE | Est. Electrical Bill | Total Error
---|---|---|---|---
Retain | 1.52 | 1.37 | $ 34,629,695 | $ 1,263,295 ($ 809)
Recalibrate | 1.14 | 0.73 | $ 32,853,507 | $ 837,450 ($ 1,540)
Refit | 0.123 | 0.08 | $ 33,942,799 | $ 411,145 ($434)

We see in Figure 3 that while our preference for refitting is steadily
increasing as we move away from the calibration period, this rate of change
rapidly increases after grid unification. This is echoed in our Type I error
rate-controlled utility function which chooses to recalibrate before grid
unification and refit afterward. retain was not optimal at any point.

To validate the accuracy of our decision, we decided to take all three options
and computed the resulting $\beta$ estimates for a month, as well as our
accuracy in estimating electrical costs. As we had predicted, refit was the
most accurate, followed by recalibrate and retain. Moreover, of a total
electrical bill of $ 33,307,959, the retain and recalibrate strategies were
off by roughly a million dollars, while refit was only off by around $400,000.
This shows that we are able to identify the most optimal of the three options.

##  5 Discussion

As complex prediction models play ever more essential roles across nearly
every sphere of inquiry, it has become more and more pertinent to answer the
question: how much should one rely on an AI/ML model? By connecting this to a
deep literature on portfolio optimization and the inference on predicted data
paradigm [20], we suggest a new framework to evaluate the efficacy of an AI/ML
model. We show that with this toolkit, one can create actionable decision
rules based on your budget, the cost of model training, the cost of data, and
the performance of the models, that can accurately determine the most
efficient way to keep AI models up-to-date. Although we show this in the
context of downstream statistical inference, the asset allocation framework
has the potential to be extended to many other metrics used to evaluate AI/ML
quality such as accuracy, fairness, and interpretability.

As researchers integrate AI technology across all levels, from domains where
data collection is cheap and plentiful (such as web-based text or image data)
to domains where data are siloed and expensive (such as healthcare), our
framework provides new language to evaluate how to spend limited resources.
This can be helpful in situations such as clinical trials, where there is the
potential to intelligently replace human subjects with AI-approximated
datapoints. This has the potential to save resources while ensuring that
traditional efficacy and safety requirements are met. This can even be helpful
in situations where the economics of data within a field is in flux.

Finally, we note that through this new connection to portfolio optimization
theory, we are revisiting an old question of the value of synthetic data. In
the last century, this was raised in statistics through the controversy over
the two-phase sampling procedure [35, 10]. More recently, in the machine
learning world, we have seen both that model training can be greatly improved
by incorporating synthetic data [44, 36] and concerns that such procedures can
lead to model collapse [4, 14]. In this paper, we study synthetic outcomes in
terms of their ability to estimate outcomes for downstream statistical
inference. By balancing the competing objectives of increasing accuracy and
minimizing uncertainty, we observe that the value of synthetic data can vary
wildy depending on one’s economic utility.

##  6 Limitations

There are two important limitations. First, we assume that if a model were to
be retrained in the future, one would get an MSE distribution that resembles
the one during initial model training. This makes this procedure ill-suited
when the signal-to-noise ratio in the data changes due to external factors
influencing the “learnability” of the outcome. The second assumption is in the
choice of how to forecast $\hat{W}$ and $\hat{D}$. We forecast both $\hat{W}$
and $\hat{D}$ using simple linear regression. In cases where more data is
available, more complex forecasting methods can be used.

## References

  * AFL [2023] AFL.  What makes hyperscale, hyperscale?, Apr 2023.  URL https://www.aflhyperscale.com/articles/what-makes-hyperscale-hyperscale/.
  * Agresti [2015] Alan Agresti.  _Foundations of Linear and Generalized Linear Models_.  Wiley Series in Probability and Statistics. Wiley, 2015.  ISBN 9781118730034.  URL https://books.google.com/books?id=jlIqBgAAQBAJ.
  * Alba et al. [2021] Patrick R Alba, Anthony Gao, Kyung Min Lee, Tori Anglin-Foote, Brian Robison, Evangelia Katsoulakis, Brent S Rose, Olga Efimova, Jeffrey P Ferraro, Olga V Patterson, et al.  Ascertainment of veterans with metastatic prostate cancer in electronic health records: demonstrating the case for natural language processing.  _JCO clinical cancer informatics_ , 5:1005–1014, 2021.
  * Alemohammad et al. [2023] Sina Alemohammad, Josue Casco-Rodriguez, Lorenzo Luzi, Ahmed Imtiaz Humayun, Hossein Babaei, Daniel LeJeune, Ali Siahkoohi, and Richard G. Baraniuk.  Self-consuming generative models go mad, 2023.
  * Angelopoulos et al. [2023] Anastasios N Angelopoulos, Stephen Bates, Clara Fannjiang, Michael I Jordan, and Tijana Zrnic.  Prediction-powered inference.  _Science_ , 382(6671):669–674, 2023.
  * Angelopoulos et al. [2024] Anastasios N. Angelopoulos, John C. Duchi, and Tijana Zrnic.  PPI++: Efficient prediction-powered inference.  _arXiv Preprint_ , 2024.
  * Baltas [2024] Ioannis Baltas.  Optimal investment in a general stochastic factor framework under model uncertainty.  _Journal of Dynamics and Games_ , 11(1):20–47, 2024.  ISSN 2164-6066.  doi: 10.3934/jdg.2023011.  URL https://www.aimsciences.org/article/id/65017ccfa76bb04c48c3a923.
  * Berns [2020] D.M. Berns.  _Modern Asset Allocation for Wealth Management_.  Wiley Finance. Wiley, 2020.  ISBN 9781119566946.  URL https://books.google.com/books?id=UmLXDwAAQBAJ.
  * Bonhomme and Weidner [2022] Stéphane Bonhomme and Martin Weidner.  Minimizing sensitivity to model misspecification.  _Quantitative Economics_ , 13(3):907–954, 2022\.  doi: https://doi.org/10.3982/QE1930.  URL https://onlinelibrary.wiley.com/doi/abs/10.3982/QE1930.
  * Bose [1951] Chameli Bose.  Some further results on errors in double sampling technique.  _Sankhyā: The Indian Journal of Statistics (1933-1960)_ , 11(2):191–194, 1951.  ISSN 00364452.  URL http://www.jstor.org/stable/25048080.
  * Brenner and Izhakian [2018] Menachem Brenner and Yehuda Izhakian.  Asset pricing and ambiguity: Empirical evidence*.  _Journal of Financial Economics_ , 130(3):503–531, 2018.  ISSN 0304-405X.  doi: https://doi.org/10.1016/j.jfineco.2018.07.007.  URL https://www.sciencedirect.com/science/article/pii/S0304405X18301831.
  * Buhren et al. [2021] Christoph Buhren, Fabian Meier, and Marco Pleßner.  Ambiguity aversion: bibliometric analysis and literature review of the last 60 years.  _Management Review Quarterly_ , 73(2):495–525, December 2021.  ISSN 2198-1639.  doi: 10.1007/s11301-021-00250-9.  URL http://dx.doi.org/10.1007/s11301-021-00250-9.
  * Chollet et al. [2015] François Chollet et al.  Keras.  https://keras.io, 2015.
  * Dohmatob et al. [2024] Elvis Dohmatob, Yunzhen Feng, and Julia Kempe.  Model collapse demystified: The case of regression, 2024.
  * Fan et al. [2024] Shuxian Fan, Adam Visokay, Kentaro Hoffman, Stephen Salerno, Li Liu, Jeffrey T Leek, and Tyler H McCormick.  From narratives to numbers: Valid inference using language model predictions from verbal autopsy narratives.  _arXiv preprint arXiv:2404.02438_ , 2024.
  * Gamerman et al. [2019] Victoria Gamerman, Tianxi Cai, and Amelie Elsäßer.  Pragmatic randomized clinical trials: best practices and statistical guidance.  _Health Services and Outcomes Research Methodology_ , 19:23–35, 2019.
  * Gooding [2024] Matthew Gooding.  Newmark: Us data center power consumption to double by 2030, 2024.  URL www.datacenterdynamics.com/en/news/us-data-center-power-consumption/.
  * Guidolin and Rinaldi [2012] Massimo Guidolin and Francesca Rinaldi.  Ambiguity in asset pricing and portfolio choice: a review of the literature.  _Theory and Decision_ , 74(2):183–217, December 2012.  ISSN 1573-7187.  doi: 10.1007/s11238-012-9343-2.  URL http://dx.doi.org/10.1007/s11238-012-9343-2.
  * Harries [1995] Michael Harries.  Splice-2 comparative evaluation: Electricity pricing.  _University of New South Wales. School of Computer Science and Engineering Technical Report_ , 1995.
  * Hoffman et al. [2024] Kentaro Hoffman, Stephen Salerno, Awan Afiaz, Jeffrey T. Leek, and Tyler H. McCormick.  Do we really even need data?  _arXiv preprint arXiv:2401.08702_ , 2024.
  * IBM [2024] IBM.  IBM watsonx.governance.  https://www.ibm.com/products/watsonx-governance, 2024.
  * Jumper et al. [2021] John Jumper, Richard Evans, Alexander Pritzel, Tim Green, Michael Figurnov, Olaf Ronneberger, Kathryn Tunyasuvunakool, Russ Bates, Augustin Žídek, Anna Potapenko, et al.  Highly accurate protein structure prediction with alphafold.  _Nature_ , 596(7873):583–589, 2021.
  * Kalinowski et al. [2024] Tomasz Kalinowski, JJ Allaire, and François Chollet.  _keras3: R Interface to ’Keras’_ , 2024.  URL https://CRAN.R-project.org/package=keras3.  R package version 0.2.0.
  * Kingma and Ba [2017] Diederik P. Kingma and Jimmy Ba.  Adam: A method for stochastic optimization, 2017.
  * Liang and Zeger [1986] Kung-Yee Liang and Scott L. Zeger.  Longitudinal data analysis using generalized linear models.  _Biometrika_ , 73(1):13–22, 1986.  ISSN 00063444.  URL http://www.jstor.org/stable/2336267.
  * Lu et al. [2019] Jie Lu, Anjin Liu, Fan Dong, Feng Gu, João Gama, and Guangquan Zhang.  Learning under concept drift: A review.  _IEEE Transactions on Knowledge and Data Engineering_ , 31(12):2346–2363, 2019.  doi: 10.1109/TKDE.2018.2876857.
  * Maccheroni et al. [2013] Fabio Maccheroni, Massimo Marinacci, and Doriana Ruffino.  Alpha as ambiguity: Robust mean-variance portfolio analysis.  _Econometrica_ , 81(3):1075–1113, 2013.
  * Marinacci [2015] Massimo Marinacci.  Model Uncertainty.  _Journal of the European Economic Association_ , 13(6):1022–1100, 12 2015.  ISSN 1542-4766.  doi: 10.1111/jeea.12164.  URL https://doi.org/10.1111/jeea.12164.
  * Markowitz [1990] Harry Markowitz.  _Mean-variance Analysis in Portfolio Choice and Capital Markets_.  Blackwell, 1990.  ISBN 9780631178545.  URL https://books.google.com/books?id=1Y2wQgAACAAJ.
  * McIntosh et al. [2023] Timothy R McIntosh, Teo Susnjak, Tong Liu, Paul Watters, and Malka N Halgamuge.  From google gemini to openai q*(q-star): A survey of reshaping the generative artificial intelligence (ai) research landscape.  _arXiv preprint arXiv:2312.10868_ , 2023.
  * Mhlanga [2023] David Mhlanga.  Open ai in education, the responsible and ethical use of chatgpt towards lifelong learning.  In _FinTech and Artificial Intelligence for Sustainable Development: The Role of Smart Technologies in Achieving Development Goals_ , pages 387–409. Springer, 2023.
  * Miao et al. [2023] Jiacheng Miao, Xinran Miao, Yixuan Wu, Jiwei Zhao, and Qiongshi Lu.  Assumption-lean and data-adaptive post-prediction inference.  _arXiv preprint arXiv:2311.14220_ , 2023.
  * Nelson et al. [2015] Kevin Nelson, George Corbin, Mark Anania, Matthew Kovacs, Jeremy Tobias, and Misty Blowers.  Evaluating model drift in machine learning algorithms.  In _2015 IEEE Symposium on Computational Intelligence for Security and Defense Applications (CISDA)_ , pages 1–8, 2015.  doi: 10.1109/CISDA.2015.7208643.
  * Neumann and Morgenstern [1944] John Von Neumann and Oskar Morgenstern.  _Theory of Games and Economic Behavior_.  Princeton University Press, Princeton, NJ, USA, 1944.
  * Neyman [1938] Jerzy Neyman.  Contribution to the theory of sampling human populations.  _Journal of the American Statistical Association_ , 33(201):101–116, 1938.  ISSN 01621459.  URL http://www.jstor.org/stable/2279117.
  * Nikolenko [2021] S.I. Nikolenko.  _Synthetic Data for Deep Learning_.  Springer Optimization and Its Applications. Springer International Publishing, 2021.  ISBN 9783030751784.  URL https://books.google.com/books?id=nTQ1EAAAQBAJ.
  * Quang [1985] Pham Xuan Quang.  Robust sequential testing.  _The Annals of Statistics_ , 13(2):638–649, 1985\.  ISSN 00905364.  URL http://www.jstor.org/stable/2241200.
  * Schwendicke and Krois [2021] Falk Schwendicke and Joachim Krois.  Better reporting of studies on artificial intelligence: Consort-ai and beyond.  _Journal of dental research_ , 100:22034521998337, 03 2021\.  doi: 10.1177/0022034521998337.
  * Sharan [2020] Yash Sharan.  The elec2 dataset, Jul 2020.  URL https://www.kaggle.com/datasets/yashsharan/the-elec2-dataset.
  * Smith [2023] Craig S Smith.  What large models cost you – there is no free ai lunch.  _Forbes_ , 2023.  URL https://www.forbes.com/sites/craigsmith/2023/09/08/what-large-models-cost-you--there-is-no-free-ai-lunch/?sh=4826ec024af7.
  * Somu et al. [2021] Nivethitha Somu, Gauthama Raman MR, and Krithi Ramamritham.  A deep learning framework for building energy consumption forecast.  _Renewable and Sustainable Energy Reviews_ , 137:110591, 2021.
  * Stokel-Walker and Noorden [2023] Chris Stokel-Walker and Richard Van Noorden.  The promise and peril of generative ai.  _Nature_ , 614(1):214–216, 2023.
  * Transgrid [2018] Transgrid.  New south wales transmission annual planning report, 2018.  URL https://www.transgrid.com.au/media/0q1dau2w/transmission-annual-planning-report-2018.pdf.
  * Tremblay et al. [2018] Jonathan Tremblay, Aayush Prakash, David Acuna, Mark Brophy, Varun Jampani, Cem Anil, Thang To, Eric Cameracci, Shaad Boochoon, and Stan Birchfield.  Training deep networks with synthetic data: Bridging the reality gap by domain randomization.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR) Workshops_ , June 2018.
  * Tsymbal [2004] Alexey Tsymbal.  The problem of concept drift: Definitions and related work.  _Technical Report Computer Science Department Trinity College Dublin_ , 05 2004.
  * Vela et al. [2022] Daniel Vela, Andrew Sharp, Richard Zhang, Trang Nguyen, An Hoang, and Oleg S Pianykh.  Temporal quality degradation in ai models.  _Scientific Reports_ , 12(1):11654, 2022.
  * Wang et al. [2023] Hanchen Wang, Tianfan Fu, Yuanqi Du, Wenhao Gao, Kexin Huang, Ziming Liu, Payal Chandak, Shengchao Liu, Peter Van Katwyk, Andreea Deac, et al.  Scientific discovery in the age of artificial intelligence.  _Nature_ , 620(7972):47–60, 2023.
  * Wang et al. [2020] Siruo Wang, Tyler H McCormick, and Jeffrey T Leek.  Methods for correcting inference based on outcomes predicted by machine learning.  _Proceedings of the National Academy of Sciences_ , 117(48):30266–30275, 2020.
  * Webb et al. [2016] Geoffrey Webb, Roy Hyde, Hong Cao, Hai Nguyen Long, and Francois Petitjean.  Characterizing concept drift.  _Data Mining and Knowledge Discovery_ , 30(4):964–994, April 2016.  ISSN 1573-756X.  doi: 10.1007/s10618-015-0448-4.  URL http://dx.doi.org/10.1007/s10618-015-0448-4.
  * White [1980] Halbert White.  A heteroskedasticity-consistent covariance matrix estimator and a direct test for heteroskedasticity.  _Econometrica_ , 48(4):817–838, 1980.  ISSN 00129682, 14680262.  URL http://www.jstor.org/stable/1912934.
  * White [1982] Halbert White.  Maximum likelihood estimation of misspecified models.  _Econometrica_ , 50(1):1–25, 1982.  ISSN 00129682, 14680262.  URL http://www.jstor.org/stable/1912526.
  * Williams et al. [2015] Hywel C Williams, Esther Burden-Teh, and Andrew J Nunn.  What is a pragmatic clinical trial.  _J Invest Dermatol_ , 135(6):1–3, 2015.
  * Wong et al. [2021] Andrew Wong, Erkin Otles, John P Donnelly, Andrew Krumm, Jeffrey McCullough, Olivia DeTroyer-Cooley, Justin Pestrue, Marie Phillips, Judy Konye, Carleen Penoza, et al.  External validation of a widely implemented proprietary sepsis prediction model in hospitalized patients.  _JAMA internal medicine_ , 181(8):1065–1070, 2021\.
  * Wooldridge [2010] Jefrey M. Wooldridge.  _Econometric Analysis of Cross Section and Panel Data_.  The MIT Press, 2010.  ISBN 9780262232586.  URL http://www.jstor.org/stable/j.ctt5hhcfr.
  * Wu et al. [2023] Tianyu Wu, Shizhu He, Jingping Liu, Siqi Sun, Kang Liu, Qing-Long Han, and Yang Tang.  A brief overview of chatgpt: The history, status quo and potential future development.  _IEEE/CAA Journal of Automatica Sinica_ , 10(5):1122–1136, 2023.
  * Yang et al. [2022] Ruixin Yang, Di Zhu, Lauren E Howard, Amanda De Hoedt, Stephen B Williams, Stephen J Freedland, and Zachary Klaassen.  Identification of patients with metastatic prostate cancer with natural language processing and machine learning.  _JCO clinical cancer informatics_ , 6:e2100071, 2022.
  * Žliobaitė et al. [2016] Indrė Žliobaitė, Mykola Pechenizkiy, and João Gama.  _An Overview of Concept Drift Applications_ , pages 91–114.  Springer International Publishing, Cham, 2016.  ISBN 978-3-319-26989-4.  doi: 10.1007/978-3-319-26989-4_4.  URL https://doi.org/10.1007/978-3-319-26989-4_4.

##  7 Appendix

###  7.1 LSTM Model

The model used for the electrical data example is a 336 unit LSTM implemented
in the keras_model_sequential function from the keras3 package in R [23]. The
architecture of the LSTM consisted of a 366 dimensional input, an layer_lstm
with 366 units followed by a dense layer with a sigmoid activation function to
predict the next time point. This gives a total of 454,609 trainable
parameters. All parameters for the LSTM layer were set to their default as of
their keras3 implementation while the dense layer is all default except for a
sigmoid activation function. The model was fit using the adam optimizer [24]
and mean squared error was used as the loss function. The training was
performed on an M2 Macbook Pro with 32 Gb of RAM and took 10 epochs. Data
splitting was performed automatically using the validation_split argument in
keras3’s fit function. This achieved a loss function of 1.4736e-04 on the
validation set.

###  7.2 Dataset and Preprocessing

The dataset that was used for the electrical example is the Elec2 dataset
Harries [19] downloaded from Kaggle [39]. The dataset consists of 45312
samples and 10 dimensions described in Table 3. While the normalization was
helpful for the LSTM fitting and elasticity measurements (both of which used
the normalized demands and prices), they posed an issue in converting these
back to their original units MWh for demand and cents per MWh for price. As
the authors were unable to obtain the original, nonnoramlized data, using
historical cost data from the Australia Energy Regulator’s “Annual Volume
Weighted Average 30 minute Prices Across Regions” plot, and demand data from
[43], we derive the following simple formulas which give an unnoramlization
that resembles what is seen in the reports:

$\text{Cost}=\text{ Normalized Cost}*120+5$

where Cost is in cents per MWh.

Name | Description | Normalization
---|---|---
id | row number | None
date | Date of Study | normalized from 0 to 1
period | 30 minute intervals delineating the time of day | normalized from 0 to 1
nswprice | Price of electricty in NSW | normalized from 0 to 1
nswdemand | Demand for electricty in NSW | normalized from 0 to 1
vicprice | Price of electricty in Vic | normalized from 0 to 1
vicdemand | Demand for electricty in Vic | normalized from 0 to 1
transfer | Electricity transfered between Grids | normalized from 0 to 1
class | Change in Price compared to 24 hours ago in NSW | None
Table 3: variable names, descriptions, and normalizations for the Elec2
Dataset.

###  7.3 Temporal Shifts

An important component of the bootstrap procedure is the forecasting of each
of the components of the regression models, $\hat{W}$ and $\hat{D}$. In both
the simulated example and the electrical example, we focused our attention to
the case of when the downstream inference model was $g$ and thus our
forecasting is unidimensional. To make most efficient use of the limited
number of calibration points, 50 datapoints for simulated dataset and 177 for
the electricity example, both $\hat{W}$ and $\hat{D}$ were forecasted out
using simple linear regression. In cases where more data are available, more
complex forecasting methods may be used. Figures 4 and 5 show the liner
regression forecast for the model relevance parameters, $\hat{\gamma}$,
variance of the model $\hat{W}$ and the variance of the residuals $\hat{D}$
for the simulated example and electricity examples respectively. In the
simulated example, even though the data generating function was exponential,
the change in $\hat{\gamma}$, $\hat{W}$ and $\hat{D}$ is linear. In the
electricity example, the change in $\hat{\gamma}$ is nearly constant
(-2.181e-06 ), while $\hat{W}$ and $\hat{D}$ exhibit significant positive
slopes with potential heteroskedasticity.

Figure 4: Lines of best fit for model relevance, and model and residual
variance for the simulated data example Figure 5: Lines of best fit for model
relevance, and model and residual variance for the electrical example

.

.