# Restricted Positional Games

Pranav Avadhanam  Monta Vista High School  Siddhartha G. Jena  Princeton
University Department of Molecular Biology  Harvard University Department of
Stem Cell and Regenerative Biology

##  1 Introduction

A (two-player) _strong positional game_ played on a hypergraph $(X,H)$ ($H$
being a collection of subsets of $X$) is a game where two players sequentially
label(“claim”) vertices of $X$ with colors assigned to each player until all
vertices of the board are claimed(see [Kri14] for a thorough introduction to
positional games). The first player to claim all elements of a winning set
$h\in H$ wins. If no player claims all the elements of a winning set, then the
game results in a draw. Each particular sequence of vertices claimed by either
player is called a _play_ , and the _terminal position_ is the final
coloring(we use the terms _coloring_ and _labeling_ interchangeably) of the
board as a result of a given play. _Partial plays_ are prefixes of plays(a
partial play of length $k$ is the first $k$ moves of a given play), and the
partial labeling that is the result of a partial play is called a _position_.
One such example of a positional game is _Tic-Tac-Toe_ , where the board is
the $3$-by-$3$ grid:

Here, the collection of winning sets, $H$, is the set of rows, columns, and
diagonals on the board. The first player in Tic-Tac-Toe labels their claimed
elements by $``X"$, and the second player labels $``O"$. Denote this game as
the $3^{2}$-game and define $[n]=\\{i\in\mathbf{N}:1\leq i\leq n\\}$. The
_$n^{d}$ Tic-Tac-Toe_ game is played on the $[n]^{d}$ hypercube with winning
sets being _geometric lines_. Given a board $[n]^{d}$, a geometric line in the
board, $g$, is a collection of vertices $\\{v_{1},v_{2},...,v_{n}\\}$, such
that there exists an $n\times d$ matrix where each row vector is a distinct
element of $g$, and where each column vector is an arithmetic progression(with
common difference $-1$, $0$, or $1$). Positional games such as Tic-Tac-Toe are
_perfect information_ , meaning that each player has knowledge of all the
previous moves up to the current point in the play. Given that the set of
available vertices to claim on each move is known, it is possible to simulate
every possible play(searching through all branches of the game tree) and
computationally determine optimal strategies for both players. The problem
with this approach, when applied to games such as $n^{d}$ Tic-Tac-Toe, is that
there are $(n^{d})!$ possible plays to search through, and so the problem of
finding (winning) strategies becomes intractable for small values of $n$ and
very small values of $d$. This phenomenon, known as _combinatorial
explosion_(sometimes called “combinatorial chaos”), is the primary motivator
for analyzing these games combinatorially rather than computationally. While
Tic-Tac-Toe has already been extensively studied from this viewpoint, a
popular variant of Tic-Tac-Toe known as _Connect-4_(that is played on a
$6$-by-$7$ grid oriented vertically) provides an important example of what
might be called a “restricted positional game”: games in which the set of
available vertices on each move is somehow restricted due to additional
constraints such as gravity. The winning sets in Connect-4 are any $4$
vertices of the board that are aligned in a row, column, or diagonal. Although
the two games are defined similarly, Connect-Tac-Toe additionally has the
influence of gravity to affect what plays are possible(with chips sliding down
the columns to the available vertex of lowest height). Connect-4, like Tic-
Tac-Toe, is a solved game(see [All88]). We similarly generalize Connect-4 to
the $n^{d}$ game played on the $[n]^{d}$ hypercube with winning sets being
geometric lines, and the set of plays being restricted in a way similar to how
gravity slides chips to the bottom of a column in “real-world” play.

##  2 Connect-Tac-Toe

######  Definition (Connect-Tac-Toe).

Connect-Tac-Toe is a strong positional game. It is played on a board $X$,
$X=[n]^{d}$, for a given side-length $n$ and dimension $d$, and with a family
of winning sets $W$, where $W$ is the set of all geometric lines in $X$. For
each fixed $(x_{1},x_{2},x_{3},...,x_{d-1})$ in $[n]^{d-1}$, let

$\textbf{c}_{x_{1}x_{2}...x_{d-1}}=\\{(x_{1},x_{2},...,x_{d-1},k):k\in[n]\\},$

one of $n^{d-1}$ generalized ’columns’ in $d$ dimensions. The game-play is as
follows: for each partial play of $m$ moves, the ${(m+1)}^{th}$ move must be
selected from a set of available vertices $A$. Let $P$ be the set of
previously claimed vertices. Then,

$\mathcal{A}=\\{\mathbf{a}:\exists\mathbf{c}_{x_{1},x_{2},...,x_{d-1}},\mathbf{a}\in\mathbf{c}_{x_{1},x_{2},...,x_{d-1}}\land\mathbf{a}_{d}=\min\\{c_{d}:c\in\mathbf{c}_{x_{1},x_{2},...,x_{d-1}}\cap(X\backslash
P)\\}\\},$

$\mathcal{A}$ being the set of unclaimed vertices with the least vertical
coordinate amongst the unclaimed vertices in their column.

Given the following partial play $((1,1,1),(1,1,2),(2,2,1),(3,3,1),(1,1,3))$
in the $3^{3}$-game, we mark the set of available vertices to be claimed with
$A$(column $\textbf{c}_{1,1}$ is marked in green):

##  3 Restrictions on Positional Games

$C2T$222We will have $C2T$ denote the game Connect-Tac-Toe, and $3T$ denote
the game Tic-Tac-Toe. is an example of a strong positional game where for a
given partial play the set of available moves for the next turn(there are
$|X|$ turns total) is restricted past just the set of unclaimed vertices in
the board. A “usual” strong positional game might be represented by the game
hypergraph $(X,F)$, where $X$ is the board and $F$ is the collection of
winning sets in $X$. Let $\mathcal{P}_{i}$ be the set of partial plays of
length $i$, where $1\leq i\leq|X|$, then
$\mathcal{P}=\bigcup_{i=1}^{|X|}{\mathcal{P}_{i}}$. A _restricted positional
game_ is instead represented by the 3-tuple $(X,F,\mathcal{A})$, where the
additional function $\mathcal{A}$ maps from the set of all partial(but
potentially full) plays $\mathcal{P}$ to the board $X$. $\mathcal{A}$ is
interpreted as assigning the set of available moves given a partial play up to
a certain point in the game(much like the previous definition of $\mathcal{A}$
in section $2$) and we say that $\mathcal{A}(\emptyset)=X$. In “usual”
positional games $\mathcal{A}(m_{1},m_{2},...m_{k})$ is assumed to equal
$X\backslash\\{m_{1},m_{2},...m_{k}\\}$, but in $C2T$ $\mathcal{A}$ has an
alternative definition and where $\mathcal{A}(m_{1},m_{2},...m_{k})$ is some
subset of $X\backslash\\{m_{1},m_{2},...m_{k}\\}$. The sole difference between
$3T$ and $C2T$ is the definition of $\mathcal{A}$, and therefore $C2T$ can be
seen as a certain restricted form of $3T$. In particular, letting
$Pl_{3T}(n,d)$(resp. $Pl_{C2T}(n,d)$) be the set of plays for $n^{d}$
$3T$(resp. $C2T$), we note that ${Pl_{C2T}(n,d)}\subseteq Pl_{3T}(n,d)$. Note
that $Pl_{3T}(n,d)=(n^{d})!$, since each play is an ordering on the vertices
of the board. To make it clearer that $C2T$ is indeed a restricted form of
$3T$, we have the following lemma:

######  Lemma.

$|Pl_{C2T}(n,d)|=\frac{Pl_{3T}(n,d)}{(n!)^{n^{d-1}}}$

###### Proof.

Note that for a given partial play $p$, $\mathcal{A}(p)$ contains at most $1$
vertex from each column. $\mathcal{A}(p)$ has no vertices in a column if and
only if that column has all of its vertices already claimed(that column has
been “chosen” $n$ times previously). Because choosing a not completely claimed
column will uniquely determine the vertex that will be selected for that move,
there is a bijection between $Pl_{C2T}(n,d)$ and the set of permutations of
the multiset $M$ with $i$(each $i$ representing a column) of multiplicity
$n$(eventually choosing the column $n$ times in the course of the play) for
every $i\in[n^{d-1}]$ and $M$ containing no other elements. As a classical
result, $|M|=\binom{n^{d}}{n,n,...n}$($n^{d-1}$ $n$’s in the bottom argument).
So we have $|Pl_{C2T}(n,d)|=|M|=\frac{(n^{d})!}{(n!)^{n^{d-1}}}$. ∎

If we define $TP_{3T}(n,d)$ to be the set of terminal positions in $[n]^{d}$,
we note that
$|TP_{3T}(n,d)|={n^{d}\choose\lfloor\frac{n^{d}}{2}\rfloor}$(elements of
$TP_{3T}(n,d)$ are known as _halving colorings_ of $[n]^{d}$). Consider the
_layers_ $L_{i}$, $L_{i}=\\{(x_{1},x_{2},...x_{d-1},i)\in[n]^{d}\\}$, of the
$n^{d}$ hypercube. Any halving coloring with $L_{1}$ monochromatic in color
$``O"$ is necessarily not in $TP_{C2T}(n,d)$(defined similarly to
$TP_{3T}(n,d)$) since the first vertex which would be marked $``X"$ must be in
$L_{1}$ if $C2T$-restrictions were in place. So we know that
$|TP_{C2T}(n,d)|<|TP_{3T}(n,d)|$ for $n,d>1$. Here is an example of a terminal
position that is in $TP_{3T}(4,2)$ but not in $TP_{C2T}(4,2)$:

##  4 The $C2T$ Hales Jewett Number

The _Hales-Jewett Theorem_ , proved in [HJ63], provides a condition where as
long as the dimension is sufficiently large($\geq HJ(n)$), there will be no
drawing position in the Tic-Tac-Toe game on $[n]^{d}$. Pairing this with the
following theorem, we have what Beck, Pegden, and Vijay [BPV09] have called a
“soft existential criterion”: without any demonstrated strategy, the
properties of the game hypergraph alone guarantee a first player win. As a way
to distinguish $TP$ and $C2T$ game-theoretically, we study variants of this
number. Alternatively, and perhaps more to the point, we can consider the win
number $w(n)=\min(d_{0}:\forall d\geq d_{0},\ first\ player^{\prime}s\ win\
on\ n^{d}\ 3T)$ and $w_{C2T}(n)=\min(d_{0}:\forall d\geq d_{0},\ first\
player^{\prime}s\ win\ on\ n^{d}\ C2T)$, but these seem to be more difficult
to study.

######  Theorem (Strategy-Stealing).

The first player always has a drawing or winning strategy for $n^{d}$ Tic-Tac-
Toe.

The reasoning for this comes from the classical “Strategy Stealing” argument,
due to Nash. Suppose the second player had a winning strategy. Then we can
show that the first player can have a first move at random without decreasing
the chance of the first player winning or drawing. After the first player
having “given up” the first move, the second player becomes the effective
“first player” and the first player can adopt whatever winning strategy the
second player had to win the game. Since this implies the second player can
never have a winning strategy, we have the result.

######  Theorem (Hales-Jewett).

For every positive integer $n$, there exists a minimum integer $HJ(n)$, such
that for every $2$-coloring of $[n]^{HJ(n)}$, there exists a monochromatic
geometric line.

Call a coloring _proper_ if it does not contain a monochromatic geometric
line. All though the Hales-Jewett theorem shows that there exists a dimension
at which all $2$-colorings of $[n]^{d}$ are improper, the Hales-Jewett theorem
implies something much stronger to hold for $HJ(n)$.

######  Corollary ($HJ(n)$ is a strict threshold).

$\forall d\geq HJ(n)$, every $2$-coloring of $[n]^{d}$ is improper and
$\forall d<HJ(n)$, there exists a proper $2$-coloring of $[n]^{d}$.

###### Proof.

By definition, for every $d<HJ(n)$, there exists a proper $2$-coloring of
$[n]^{d}$. Suppose for some dimension $d\prime$, we have that every
$2$-coloring of $[n]^{d\prime-1}$ is improper. Given that $[n]^{d\prime}$
consists of $n$ layers that are “copies” of $[n]^{d\prime-1}$, any coloring of
$[n]^{d\prime}$ with a layer necessarily containing a monochromatic geometric
line will also contain a monochromatic geometric line as a whole coloring: so
every $2$-coloring of $[n]^{d\prime}$ is improper. Setting $d\prime=HJ(n)+1$,
we verify that $\forall d\geq HJ(n),\ \nexists\ proper\ $2$-coloring$ of
$[n]^{d}$ by induction on $d\prime$. ∎

Define $HJ_{1/2}(n)=\min(d:\forall\ c\in TP_{3T}(n,d),\exists\ monochromatic\
geometric\ line)$ and $HJ_{C2T}(n)=\min(d:\forall\ c\in TP_{C2T}(n,d),\exists\
monochromatic\ geometric\ line)$. Note that $HJ(n)\geq HJ_{1/2}(n)\geq
HJ_{C2T}(n)$, this following from $TP_{C2T}(n,d)\subset TP_{3T}(n,d)$. For
these variants of the Hales-Jewett Number($HJ(n)$) such a “threshold” property
has not been proven. In the paper [BPV09](which also discussed the threshold
property), exponential lower bounds were proven for the Hales-Jewett and
Hales-Jewett halving number:

######  Theorem (Beck-Pegden-Vijay).

$HJ(n)\geq HJ_{1/2}(n)\geq\frac{2^{(n-2)/4}}{3(n-2)^{4}}$

We are able to provide logarithmic lower bounds for the Hales-Jewett $C2T$
number, and it is an open question whether these bounds can be improved to
exponential. If these logarithmic bounds are tight, we can quantitatively
describe just how restrictive(from more of a game-theoretic perspective) $C2T$
is versus $3T$. For a given $2$-coloring $C:X\rightarrow\\{0,1\\}$, let
$C\prime:X\rightarrow\\{0,1\\}$ denote the _color-flip_ of $C$ with
$C:x\mapsto 0$ if and only if $C\prime:x\mapsto 1$.

######  Lemma.

Every $2$-coloring of $[n]^{d}$ such that $\lceil\frac{n}{2}\rceil$ layers are
colored by a halving coloring $C$ and $\lfloor\frac{n}{2}\rfloor$ layers are
colored by $C\prime$ is an element of $TP_{C2T}(n,d)$.

###### Proof.

Let $C$ be halving coloring of the set of $n^{d-1}$ columns in
$[n]^{d}$(alternatively $C$ represents a halving coloring of a layer of the
hypercube). Denote our assignment of colorings to each layer by
$f:[n]\mapsto\\{C,C\prime\\}$. If $n$ is even, then $C\prime$ is also a
halving coloring. Call a (partial) play $C2T$-valid, if it satisfies
$C2T$-restrictions. Then we may construct a $C2T$-valid play layer-by-layer:
let
$C=(\\{x_{1},x_{2},...x_{\frac{n^{d-1}}{2}}\\},\\{y_{1},y_{2},...y_{\frac{n^{d-1}}{2}}\\})$.
For even $n$, we have the $C2T$-valid play(here we have presented it as a
sequence of vertices rather than columns) on $n^{d}$,
$P=(p_{1},p_{2},...p_{n^{d}})$, such that $\forall i\in\\{0,1,...n-1\\}$ with
$f(i)=C$(resp. $f(i)=C\prime$), $(p_{n^{d-1}\cdot i+1},p_{n^{d-1}\cdot
i+2},...p_{n^{d-1}\cdot
i+n^{d-1}})=(x_{1,i},y_{1,i},...x_{\frac{n^{d-1}}{2},i},y_{\frac{n^{d-1}}{2},i})$
(resp.
$(y_{1,i},x_{1,i},...y_{\frac{n^{d-1}}{2},i},x_{\frac{n^{d-1}}{2},i})$). For
odd $n$, we claim that $\forall w\in[n]$, $\exists$ $C2T$-valid partial play
on $\bigcup_{i=1}^{w}L_{i}\backslash X$ where $X$ is a monochromatic(with
respect to $f(w)$) subset of $L_{w}$ such that
$|\bigcup_{i=1}^{w}L_{i}\backslash X|$ is even and having a position labeled
as $(f(1),...f(w-1),f(w)[L_{w}\backslash X])$. In this case, let
$C=(\\{x_{1},x_{2},...x_{\lceil\frac{n^{d-1}}{2}\rceil}\\},\\{y_{1},y_{2},...y_{\lfloor\frac{n^{d-1}}{2}\rfloor}\\})$.
We proceed with induction on $w$. For the base case of $w=1$, we explicitly
construct a $C2T$-valid partial play $P_{1}$ on
$L_{1}\backslash\\{\phi_{1}\\}$ where for $f(1)=C$(resp. $f(1)=C\prime$)
$\phi\in$ $\\{x_{1},x_{2},...x_{\lceil\frac{n^{d-1}}{2}\rceil}\\}$(resp.
$\\{y_{1},y_{2},...y_{\lceil\frac{n^{d-1}}{2}\rceil}\\}$): we may arbitrarily
choose $\phi$ to be $x_{\lceil\frac{n^{d-1}}{2}\rceil}$(resp.
$y_{\lceil\frac{n^{d-1}}{2}\rceil}$) so that
$P_{1}=(x_{1},y_{1},...,x_{\lfloor\frac{n^{d-1}}{2}\rfloor},y_{\lfloor\frac{n^{d-1}}{2}\rfloor})$(resp.
$(y_{1},x_{1},...,y_{\lfloor\frac{n^{d-1}}{2}\rfloor},x_{\lfloor\frac{n^{d-1}}{2}\rfloor})$).
Suppose for some $w-1$, we have that there is a $C2T$-valid partial play
$P_{w-1}$ on $\bigcup_{i=1}^{w-1}L_{i}\backslash X$(with an appropriate $X$
and position of $P_{w-1}$ being a subset of $f$). Note that for the terminal
position $f(1),f(2),...f(w-1)$, the difference in sizes between the color
classes is $||\\{1\leq i\leq w-1:f(i)=C\\}|-|\\{1\leq i\leq
w-1:f(i)=C\prime\\}||$. Since the terminal position of
$\bigcup_{i=1}^{w-1}L_{i}\backslash X$ has zero difference in the size of the
color classes, $X$ must be responsible for this overall discrepancy:
$|X|=||\\{1\leq i\leq w-1:f(i)=C\\}|-|\\{1\leq i\leq w-1:f(i)=C\prime\\}||$.
Given that for $f$ there are at most $\lceil\frac{n}{2}\rceil$ layers that can
be $C$(and at most $\lfloor\frac{n}{2}\rfloor$ that can be $C\prime$),
$|X|\leq\lceil\frac{n}{2}\rceil$. There are at least
$\lfloor\frac{n^{d-1}}{2}\rfloor-\lceil\frac{n}{2}\rceil>|X|$ columns
$\mathbf{c}$ with $\mathbf{c}_{w}$ of the opposite color and
$X\cap\mathbf{c}=\emptyset$ such that we can choose $\mathbf{c}_{w}$ to pair
with an element from $X$. We want to extend the partial play $P_{w-1}$ to a
partial play $P_{w}$ on $\bigcup_{i=1}^{w}L_{i}\backslash X\prime$. For each
of the elements in $X$, we have shown that we can pair them with an above
element from $L_{w}$ while satisfying the $C2T$-restrictions. But after
pairing off(sequentially selecting vertices with opposite labels in the
terminal position) these elements of $X$, there will remain at least(depending
on the color of $X$ and what $f(w)$ is)
$\lfloor\frac{n^{d-1}}{2}\rfloor-\lceil\frac{n}{2}\rceil$ vertices of each
color on $L_{w}$ that have not yet been claimed in the course of the partial
play. Pairing off these remaining vertices, we will be left with a
monochromatic set $X\prime\subset L_{w}$ and $P_{w}$ will be $C2T$-valid on
$\bigcup_{i=1}^{w}L_{i}\backslash X\prime$. Having completed the induction, we
know the case for $w=n$ holds: there exists a $C2T$-valid play $P$ on
$[n]^{d}\backslash X_{n}$. Furthermore, we know that
$|X_{n}|=||f^{-1}[C]|-|f^{-1}[C\prime]||=|f^{-1}[C]|-|f^{-1}[C\prime]|=1$, so
$X_{n}$ must contain a single element $\chi$ of
$\\{x_{1,n},x_{2,n},...x_{\lceil\frac{n^{d-1}}{2}\rceil,n}\\}$(resp.
$(y_{1,n},y_{2,n},...y_{\lceil\frac{n^{d-1}}{2}\rceil,n})$) for $f(n)=C$(resp.
$f(n)=C\prime$). Selecting $\chi$ as the first player’s final move of the
play, we have that $(P,col(\chi))$333Let $col(x)$ be the column a vertex
$x\in[n]^{d}$ is in. is a $C2T$-valid play(represented as a sequence of
columns) on $[n]^{d}$ with terminal position described by $f$. ∎

######  Lemma (Folklore).

There are $\frac{(n+2)^{d}-n^{d}}{2}$ geometric lines in the $[n]^{d}$ board.

###### Proof.

Consider the geometric line $g=\\{v_{1},v_{2},...v_{n}\\}$. There exists two
orderings $(v_{1},v_{2},...v_{n}),(v_{n},v_{n-1},...v_{1})$ on $g$ that we
count such that for every $i\in[n]$, $c_{i}=(v_{1,i},v_{2,i},...v_{n,i})$ is
equal to $(1,2,...n)$, $(n,n-1,...1)$, or $(a,a,...a)$(for some $a\in[n]$).
Given that there are $n$ values of $a$, and two additional choices for whether
$(c_{i})$ is an arithmetic progression of positive or negative common
difference, there are $(n+2)^{d}$ (possibly degenerate) orderings on the
geometric lines. Subtracting for the $n^{d}$ degenerate geometric lines(lines
where all the columns are arithmetic progressions with common difference 0),
and dividing by $2$ to take into account the fact that there are twice as many
orderings than geometric lines, there must be $\frac{(n+2)^{d}-n^{d}}{2}$
unique geometric lines. ∎

######  Theorem.

We have the following lower bound:

$HJ_{C2T}(n)>\frac{n-6}{4\log_{2}(n)}$

###### Proof.

$dim(L_{i})=d-1<HJ_{C2T}(n)$, so there exists some proper halving coloring,
$C$, of each $L_{i}$. Note that it suffices to show(given the previous lemma)
that there exists a proper coloring of $n^{d}$ with $\lceil\frac{n}{2}\rceil$
layers colored $C$ and $\lfloor\frac{n}{2}\rfloor$ layers colored $C\prime$
provided some restriction on $n$. Since $C$ is proper, $C\prime$ is also
proper, and therefore all geometric lines contained within a layer will be
non-monochromatic. Suppose $L_{i}$ is colored with $C$ and $L_{j}$ is colored
with $C\prime$. Then, for every $x_{i}\in L_{i}$, the corresponding $x_{j}\in
L_{j}$ that is in the same column as $x_{i}$ will have coloring opposite of
that of $x_{i}$. Therefore the column containing both $x_{i}$ and $x_{j}$ will
be guaranteed to be non-monochromatic. Spanning over all $x_{i}$, all columns
will also be guaranteed to be non-monochromatic no matter $C$. We know there
are $\frac{(n+2)^{d}-n^{d}}{2}$ geometric lines. The total number of geometric
lines that we still haven’t accounted(to be guaranteed non-monochromatic) is
going to be
$\frac{(n+2)^{d}-n^{d}}{2}-(n\cdot\frac{(n+2)^{d-1}-n^{d-1}}{2})-n^{d-1}=(n+2)^{d-1}-n^{d-1}$.
All of these remaining geometric lines
$G_{1},G_{2},...G_{k}(k=(n+2)^{d-1}-n^{d-1})$ intersect every layer once. Fix
$L_{1}$ to be colored by $\mu$(denoted by $(L_{1},\mu)$,
$\mu\in\\{C,C\prime\\}$). Let $proj_{i}(j,\ell)$ be the unique $g\in L_{i}$
such that $g$ and $G_{j}(\ell)$($\ell$th vertex of the geometric line) are in
the same column. Let
$x_{1}=|\\{j\in[k]:\mu(proj_{1}(j,1))=\mu(proj_{1}(j,2))\\}|$, and
$y_{1}=k-x_{1}$. If we choose $(L_{2},\mu)$, the set of geometric lines that
are currently monochromatic in our partially constructed coloring is reduced
by $y_{1}$. If we choose $(L_{2},M)$($M$ being the color-flip of $\mu$), $k$
is instead reduced by $x_{1}$. Denote the remaining quantity of monochromatic
geometric lines as $k\prime$. We may force
$k\prime=k-max(x_{1},y_{1})\leq\frac{k}{2}$, reducing $k$ by a factor of at
least 2. We repeat this process, coloring $L_{i+1}$ in terms of $L_{i}$, until
layer q, where $k^{(q-1)}=0$. Since we only have freedom to choose colorings
between $C,C\prime$ in $\lfloor\frac{n}{2}\rfloor$ layers(we cannot
arbitrarily color between $C,C\prime$ in $\lceil\frac{n}{2}\rceil$ layers
since there is a possibility that all of those $\lceil\frac{n}{2}\rceil$
layers would be colored with $C\prime$ which would violate our initial
assumption),
$q=\log_{2}(k=(n+2)^{d-1}-n^{d-1})+2\leq\lfloor\frac{n}{2}\rfloor$. If
$d=HJ_{C2T}(n)$, then there does not exist a proper coloring in
$TP_{C2T}(n,d)$, and so we have
$\log_{2}((n+2)^{HJ_{C2T}(n)-1}-n^{HJ_{C2T}(n)-1})+2>\lfloor\frac{n}{2}\rfloor$.
From here, we derive the lower bounds. ∎

## References

  * [HJ63] A. Hales and R. Jewett  “Regularity and Positional Games”  In _Transactions of the American Mathematical Society_ 106.2, 1963, pp. 222–229
  * [All88] V. Allis  “A Knowledge-based Approach of Connect-Four”, 1988
  * [BPV09] J. Beck, W. Pegden and S. Vijay  “The Hales-Jewett number is exponential: game-theoretic consequences”  In _Analytic Number Theory: Essays in Honour of Klaus Roth_ Cambridge University Press, 2009
  * [Kri14] M. Krivelevich  “Positional Games”  In _Proceedings of the ICM 2014_ , 2014


# Sources of Irreproducibility in Machine Learning: A Review

Odd Erik Gundersen1 111Contact Author Kevin Coakley1,2&Christine Kirkpatrick2
1Norwegian University of Science and Technology, Trondheim, Norway
2 San Diego Supercomputer Center, California, USA
<EMAIL_ADDRESS>{kcoakley<EMAIL_ADDRESS>
###### Abstract

Lately, several benchmark studies have shown that the state of the art in some
of the sub-fields of machine learning actually has not progressed despite
progress being reported in the literature. The lack of progress is partly
caused by the irreproducibility of many model comparison studies. Model
comparison studies are conducted that do not control for many known sources of
irreproducibility. This leads to results that cannot be verified by third
parties. Our objective is to provide an overview of the sources of
irreproducibility that are reported in the literature. We review the
literature to provide an overview and a taxonomy in addition to a discussion
on the identified sources of irreproducibility. Finally, we identify three
lines of further inquiry.

##  1 Introduction

Figure 1:  The _scientific method_ is a systematic process for acquiring
knowledge about the world: First, the world is observed (1) to form beliefs
about it. A scientific theory is developed (2) to explain the causes and
effects of the observed beliefs. A hypothesis is formed (3) in order to test
the scientific theory. An experiment is designed and the research protocol is
documented (4) to test the hypothesis. The experiment is carried out using the
research protocol (5) and outcomes are produced (6). The experiment outcomes
are analyzed (7) and the outcomes analysis is interpreted (8) with respect to
the hypothesis. Finally, the beliefs of the world are updated (9) based on the
results of the analysis and the scientific method is repeated by observing the
world (10) with the updated beliefs.

Progress in machine learning is to a large degree driven by empirical
evidence. _Model comparison_ experiments are the standard method to identify
the best performing machine learning model for a given task Melis et al.
(2018); Sculley et al. (2018); Bouthillier et al. (2019); Dacrema et al.
(2021), and clear wins are typically required for a research paper to be
published at a top venue Sculley et al. (2018). Wagstaff Wagstaff (2012)
proposed to focus research on real world impact challenges such as improve ELO
rating of chess engines and discovering a new physical law using machine
learning. Although several such impact challenges have been achieved lately,
such as in game play, protein folding and software programming, model
comparison studies are still the standard. Lately, however, several model
comparison studies that benchmark state of the art results have shown that
progress is not as steady as one could get the impression of when reading the
scientific literature. Topics covered by such studies include forecasting
Makridakis et al. (2018), natural language processing Belz et al. (2021a),
generative adversarial networks Lucic et al. (2018), deep reinforcement
learning Henderson et al. (2018), recommender systems Dacrema et al. (2019),
and image recognition Bouthillier et al. (2019). The findings establish that
many state of the art results published at top venues in machine learning are
not reproducible.

Proper methodology requires a good understanding of what can cause
irreproducible results. An experiment conducted by Pham et al. Pham et al.
(2020) where 16 identical training runs of a deep learning model resulted in
test accuracy varying from 8.9% to 99%. According to a survey also done by
Pham et al. Pham et al. (2020), 83.8% out of 901 participants were unsure or
unaware about variance caused by how an experiment is implemented while most,
although not all, participants knew about the algorithmic-level influences on
variation in performance. This poor understanding of what can cause conclusion
to be false in machine learning method development trickles down to the
application areas that are downstream and use the methods developed by machine
learning researchers, such as medicine Roberts et al. (2021).

In the application areas, the stakes can be high and lead to unfortunate
situations if relying on unsound evidence. While false findings and
irreproducible results are expected products of the scientific method, the
method is self-correcting if done correctly. However, methodological care has
to be taken to reach sound conclusions when interpreting machine learning
results. All too often, the conclusions reached are applied to a scope beyond
what the original experiment was poised to suggest. While there are challenges
regarding reproducibility that appear to be unique to the field of machine
learning compared to other disciplines Pineau et al. (2021), we do not focus
on these alone in this paper. We review the literature to identify a larger
scope of sources of irreproducibility and not only those that lead to a
variation in results. In addition, we provide a taxonomy and a discussion on
these sources of irreproducibility.

##  2 Reproducibility

_Reproducibility_ is defined as the ability of independent investigators to
draw the same conclusions from an experiment by following the documentation
shared by the original investigators Gundersen (2021b), and a _reproducibility
experiment_ is the experiment conducted by independent researchers to confirm
research findings. The documentation of a machine learning experiment is not
restricted to written text in the form of a scientific report, it could also
include the code and data used to conduct the experiment, but these are not
required for independent investigators to conduct a reproducibility
experiment. Still, code and data are commonly acknowledged as important for
third parties to reproduce results Haibe-Kains et al. (2020). Having access to
code and data reduces the effort required to reproduce the results, while also
leading to increased trust in the research Gundersen (2019). Drummond Drummond
(2009) argues that the power of a reproducibility experiment is greater with
increased difference from the original study, which can be enforced by
providing less documentation.

There are three degrees of reproducibility that are derived from the steps of
the scientific method (see figure 1). _Outcome reproducibility_ is achieved if
an independent researcher can produce the same outcome as the original
experiment. If the experiment outcomes are reproduced exactly and the analysis
and interpretation of the original investigators are sound, the results
support the original hypothesis. _Analysis reproducibility_ is when the
outcomes by an independent investigator are different from the original
investigators, but as long as the analysis of the outcomes as done by the
original investigators lead to the same interpretation, the reproducibility
experiment supports the original hypothesis. _Interpretation reproducibility_
is achieved when a different analysis is done by independent investigators (on
the same or different outcome), but the independent researcher’s
interpretation of the analysis supports the original hypothesis. If the
interpretation of an independent researcher when applying the same analysis on
the same or similar outcome does not support the original interpretation, the
reproducibility experiment is inconclusive; new experiments are needed to
confirm the findings.

##  3 Sources of Irreproducibility

The sources of irreproducibility are properties of the experiment that have
not been properly controlled for by the original investigators. Sometimes even
a small variation in these properties could change the interpretation of the
analysis so that the belief update from the reproducibility experiment differ
from the original study. As such, these properties could lead independent
investigators to draw different conclusions after having conducted a
reproducibility experiment. The sources of irreproducibility can be as diverse
as the stochasticity of the machine learning algorithms, a bug in the
performance metric code and the choice of baseline. The stochasticity of the
algorithm can produce a highly unlikely outcome, so drawing any conclusions
from it would be ill-advised. A bug in the performance metric will invalidate
the analysis while a poor choice of baseline i.e. one that is actually not
state of the art will invalidate the interpretation.

The sources of irreproducibility is a broader term than the sources of
variation introduced by Pahm et al. Pham et al. (2020), which include
algorithm- and implementation-level factors. We have identified a total of six
groups of factors including those introduced by Pham et al.: 1) study design
factors, 2) algorithmic factors, 3) implementation factors, 4) observation
factors 5) evaluation factors, and 6) documentation factors. The factors are
presented in the following sections222The final version of the paper will
contain the following figure of the taxonomy:
https://folk.idi.ntnu.no/odderik/taxonomy.pdf.

##  4 Study Design Factors

Study design factors are related to the methodology of an experiment and
whether a study answers the research questions that are posed in tests suited
for genuine evaluation.

Choice of baselines For many machine learning tasks, it is often not clear
what comprises the state of the art. Studies have found that many deep
learning papers only compared against other deep learning algorithms, even
though they were not performing better than other simpler baselines Cremonesi
and Jannach (2021). This could happen in cases where progress is shown by
reusing experimental designs that propagate weak baselines without questioning
them Dacrema et al. (2021).

p-fishing is when seeking statistically significant results beyond the
original hypothesis Cockburn et al. (2020).

p-hacking Cockburn et al. Cockburn et al. (2020) use the term collectively for
research practices that allow manipulation of experimental and analysis
methods to produce statistically significant results.

HARKing (Hypotheses After Results are Known) is post-hoc reframing of
experimental intentions to present a p-fished outcome as having been predicted
from the start.

Computational budget Researchers with large computational budgets prevent
meaningful comparisons of performance experiments as they can spend the budget
on intensive hyperparameter tuning to improve the results Melis et al. (2018);
Lucic et al. (2018); Dodge et al. (2019); Zhang and Duh (2020). Bouthilier and
Varoquaux Bouthillier and Varoquaux (2020) report that around 45% of
hyperparameters were manually tuned at NeurIPS 2019 and ICLR 2020, so
systematic search could give a huge advantage.

Experiment setup Differences in the setup of an experiment can lead to a
difference between 5% to 40% in the number of solved instances of a SAT solver
when running on the same hardware Fichte et al. (2021), so they have to be
reported Henderson et al. (2018).

Unsuited experiment designs Experimental analyses deviates from the claimed or
implicit research goals Cremonesi and Jannach (2021).

Study design factors lead to poorer outcomes for both baselines and false
interpretations of the results as the basis of the interpreations is unsuited
experiment designs and poor experiment setup. The factors are controlled
through ensuring that all models are given the same amount of computation
budget and validation, that is finding out whether the right study is done.
Validation procedures could be improved through registered reports and pre-
registration Cockburn et al. (2020), which there are few if any examples of in
artificial intelligence and machine learning research Gundersen (2021a).

##  5 Algorithmic Factors

Algorithmic factors are properties of the learning algorithms and training
process that might affect the performance of an algorithm.

Hyperparameter optimization Different hyperparameter optimization methods find
different optimal hyperparameters Reimers and Gurevych (2017); Henderson et
al. (2018); Bouthillier et al. (2019, 2021), so researchers should specify
exactly which method is used Cooper et al. (2021). Reimers and Gurevych
Reimers and Gurevych (2017) evaluated the variation of three different
methods: random search, grid search and Bayesian optimization, and found that
the variation that they caused is not negligible compared to other sources of
variation. Raff Raff (2019) found that specification of hyperparameters
correlated with reproducibility.

Random weight initialization How weight in neural networks are initialized
affect performance Pham et al. (2020); Zhuang et al. (2021). Different initial
weights might lead the hyperparameter optimization method to converge to
different local minima.

Stochastic Layers Dropout, variational dropout and noisy activations that are
developed to make the deep neural networks robust affect performance Reimers
and Gurevych (2017); Pham et al. (2020); Zhuang et al. (2021).

Random feature selection Features are selected at random for each tree that is
trained in a Gradient Boosted Tree learning algorithms Pouchard et al. (2020).

Data Shuffling is when data samples are shuffled randomly and batched during
training Reimers and Gurevych (2017); Pham et al. (2020); Zhuang et al.
(2021).

Batch ordering is when the batch order is randomized for every epoch Pham et
al. (2020); Bouthillier et al. (2021).

Algorithmic factors describe stochastic properties of machine learning methods
and they affect the outcome of an experiment. Hence, the variation in outcome
over several experiment runs must be reported. As pointed out by Miller and
Miller Miller and Miller (2018): _”No quantitative results are of any value
unless they are accompanied by some estimate of the errors inherent in them.”_
Algorithmic factors can be controlled by setting the pseudo-random number
generator initialization seed so that the outcome will be the exact same for
each experiment run, given that all other things are equal.

##  6 Implementation Factors

Implementation factors are related to which laboratory conducts the
experiment, as they include the hardware and ancillary software used to
conduct the experiment.

Initialization seeds Difference in the seeds used to initialize the pseudo-
random number generator leads to difference in performance Melis et al.
(2018); Bouthillier et al. (2019). Reimers and Gurevych Reimers and Gurevych
(2017) show that the seed value for the random number generator can result in
statistically significant ($p<10^{-4}$) for different state-of-the-art
systems. The same seed on different platforms produce different results
Pouchard et al. (2020). Averaging results over multiple runs using different
seeds provides insight into population distribution. Gundersen et al.
Gundersen et al. (2022) pointed out that fixing seeds was not straightforward
as they had to be fixed for many different libraries and that a bug in a
framework prevented control of all stochasticity.

Ancillary software Results across platforms, such TensorFlow or PyTorch, vary
Pouchard et al. (2020). Hong et al. Hong et al. (2013) showed that difference
in operating system affected the result of weather simulations.

Ancillary software version Difference in software versions that the
reproducibility experiment relies on can affect the performance Crane (2018);
Gundersen et al. (2022).

Bugs in software Bugs in either one’s own implementation of novel algorithms
or baselines, and ancillary software such as libraries, frameworks or
operating systems might affect performance Crane (2018); Pham et al. (2020);
Pineau et al. (2021); Gundersen et al. (2022).

Non-deterministic ordering of floating-point operations Truncation error of
floating point calculations introduces variability as $A+B+C\neq C+B+A$, which
is a problem when such operations are calculated in parallel, as they are for
GPUs Pham et al. (2020); Gundersen et al. (2022). Truncation error can be
reduced by changing from single precision (32 bits) to double precision (64
bits) at a cost of doubling memory requirements and tripling the training time
Pinto et al. (2021).

Parallel execution Random completion order of parallel tasks introduce
variation Pham et al. (2020). Increased parallelism is a driver for
implementation noise Zhuang et al. (2021).

Compiler settings Hong et al, Hong et al. (2013) tested sensitivity to Intel
compiler optimization levels for experiments that relies on huge amounts of
floating point calculation, such as weather simulations.

Auto-selection of primitive operations High level libraries implement deep
learning algorithms using GPU-optimized deep learning primitives provided by
low-level libraries such as cuDNN and CUDA Pham et al. (2020). Autotune in
cuDNN automatically benchmarks several modes of operation for primitive
functions in run-time, which might change between runs.

Processing unit Changing the processor can affect results Hong et al. (2013).
Nagarajan et al. Nagarajan et al. (2019) found that a deterministic GPU
implementation repeatedly generated the same result when executed on the same
GPU, but changed to a different, but deterministic result when being executed
on another GPU.

Implementation factors cannot be fully controlled unless the experiments are
repeated on the same computer, in which the results are not reproduced, but
repeated. However, they can be controlled partly by not using multiple
processes that cannot guarantee data order, deterministic implementations of
primitive operations, use single thread process and force running in serial
manner Pham et al. (2020), and conducting the experiment in a Docker container
with the same seed. Difference in results caused by floating point precision,
conducting the experiments on a HPC, and differing processing units cannot yet
be controlled for.

##  7 Observation Factors

Observational factors are related to the observations that are made as part of
the reproducibility experiment, which for most machine learning experiments
are offline data from measurements and sensors, but also include online data
and benchmark gyms used in reinforcement learning.

Dataset bias The methods used to gather data (manual or automated) and the way
data is captured (objects are often centered when photographed) bias datasets
Torralba and Efros (2011). Recth et al. Recht et al. (2019) show that
algorithms generalize poorly even on datasets that are replicated using the
same source populations, so the lack of access to data used in the original
study could lead to differences in data distribution for reproducibility
experiments Pineau et al. (2021). In the social and environmental sciences,
models might not generalize from one geographic area to another because of
spatial dependence and heterogeneity Goodchild and Li (2021).

Pre-processing Differences in data pre-processing could change outcomes
Dacrema et al. (2021); Gundersen (2021b).

Data augmentation Stochastic data augmentation procedures will affect how data
is augmented, and difference the resulting difference in training data will
lead to different performance Pham et al. (2020); Zhuang et al. (2021);
Bouthillier et al. (2021).

Data splits Difference in data splits cause difference in results Makridakis
et al. (2018), which includes stochastic sampling from the training set
instead of training on a static validation set Bouthillier et al. (2019,
2021). Also, random selection of samples during training is typically used in
gradient boosted trees Pouchard et al. (2020). According to Gundersen and
Kjensmo Gundersen and Kjensmo (2018), only 16% specify the validation set and
30% specify the test set, which means that outcome reproducibility is not
possible to achieve. A 2% to 12% variation has been shown in labeled
attachment scores of Natural Language Processing experiments when comparing
models trained using standard test splits versus random test splits, which
suggests that the results reported by experiments that only use the standard
test splits can be influenced by a bias in the standard test splits that favor
certain types of parsers Çöltekin (2020).

Environment properties Stochasticity and different dynamic properties of the
testing environment could affect the variability of the performance,
especially in continuous control domains such as those used by deep
reinforcement learning Henderson et al. (2018).

How data was gathered and prepared will affect the outcome of the experiment.
Observation factors can be partly controlled by setting the random seed,
sharing details about pre-processing and data provenance, that is keeping a
record of how the data set was created Gebru et al. (2021). What is done with
duplicate data, outliers and missing values can introduce bias into the
dataset Stodden (2015). As long as datasets are finite samples of an infinite
population Melis et al. (2018), they cannot be fully controlled.

##  8 Evaluation factors

Evaluation factors are related to how the investigators reach the conclusions
from doing an experiment.

Selective reporting Selective reporting of results, for example through
careful selection of datasets, and ignoring the danger of adaptive over-
fitting could lead to the wrong conclusions being made Pineau et al. (2021).

Over-claiming of results By drawing conclusions that go beyond the evidence
presented (e.g. insufficient number of experiments, mismatch between
hypothesis and claim) results are over-estimated Pineau et al. (2021).

Error estimation Machine learning methods must be able to specify certainty
and confidence intervals around them Makridakis et al. (2018) and preferably
testing statistical significance taking the confidence intervals into account
Henderson et al. (2018). Reporting single scores without any estimate of error
or variation in performance is insufficient to compare non-deterministic
approaches Reimers and Gurevych (2017). Error estimates are more prevalent in
machine learning experiments reported in healthcare than for other domains
McDermott et al. (2021).

Statistical analysis Improper use of statistics to analyze results, such as
claiming significance without proper statistical testing or using the wrong
statistic test lead to false conclusions Card et al. (2020); Pineau et al.
(2021). Power analyses should be done prior to evaluation when comparing
against baselines, and the number of instances in the test will determine the
effect size and should be chosen accordingly Card et al. (2020).

Test data issues Data leakage results in overestimating the performance as a
model is trained on data that should only be available at test time Dacrema et
al. (2021). Götz-Han et al. Götz-Hahn et al. (2020) demonstrate five cases of
reported performance gains well above the state of the art that were the
results of data leakage. The performance results far below the claims of the
original researchers when the data leakage errors were corrected. Cases where
metrics have been reported on training data instead of test data has been
found Kurach et al. (2018).

Lack of naive baselines Lack of comparison with simple statistical methods or
naive benchmarks such as linear regression and persistence in time-series
forecasting could obscure results Makridakis et al. (2018).

Annotation quality Difference in human evaluation of performance will affect
the outcome Belz et al. (2021b).

Sampled metrics Sampling from the test set is used sometimes when evaluations
are computationally demanding. This could lead to sampled metrics being
inconsistent with the exact versions and thus the wrong conclusions can be
inferred Cremonesi and Jannach (2021).

Tuning of algorithms Own algorithms are often fine-tuned to get the best
possible result Latifi et al. (2021) while baselines are often not properly
tuned Cremonesi and Jannach (2021); Dacrema et al. (2021) or old performance
results are used to claim greater improvement than what could otherwise be
claimed against the state of the art Crane (2018). The result is over-
estimates of the performance of own algorithms.

Evaluation factors could affect both the outcome and the analysis and thus
lead to the wrong interpretation. As documentation factors, evaluation factors
can only be controlled through validation and ensuring that one is doing the
right experiment. Sculley et al. Sculley et al. (2018) list the following
practices that should be included in empirical studies: 1) tuning methodology,
2) sliced analysis, 3) ablation studies, 4) sanity checks and counterfactuals
and 5) at least one negative result. However, they noted that we have not seen
a material increase in standards for empirical analysis or rigor across the
field.

##  9 Documentation Factors

Documentation factors are related to whether the original investigators share
enough information about their experiment for third parties to reproduce the
results. This means documenting the factors listed above.Additional factors
include:

Readability The readability of papers influences whether it is possible to
reproduce results. Mathiness could lead to reduced readability Lipton and
Steinhardt (2019). Gundersen and Kjensmo Gundersen and Kjensmo (2018) found
that a large degree of papers only implicitly state what research questions
they answer (94%), which problems that they seek to solve (53%), and what the
objective (goal) of conducting the research is (78%). Only 5% of the papers
explicitly states the hypothesis and 54% contain pseudo-code. Raff Raff (2019)
found that number of tables, readability, specification of hyperparameters,
pseudo-code, number of equations and compute needed to run the experiment
correlated strongly with reproducibility.

Experiment design details Under-specification of the metrics used to report
results and misspecification or under-specification of the model or training
procedure might lead to the wrong conclusions Pineau et al. (2021).

Workflow The exact steps taken and their order when conducting the empirical
machine learning studies will affect the outcome Gundersen (2021b), especially
when they become more complex Rupprecht et al. (2020). Missing documentation
of steps could also affect the reproducibility. Kurach et al. Kurach et al.
(2018) found that whether data was augmented was not specified, even when it
was.

Implementation details Details on how novel algorithms and baselines are
implemented, especially details that can affect reproducibility are important
Henderson et al. (2018). Inconsistencies in the documentation and
implementation of ancillary software can cause reproducibility experiments to
fail when using different ancillary software. Alahmari et al. Alahmari et al.
(2020) showed how a difference in Karas’ documented equation for the Glorot
uniform and the actual implementation differ.

Access to data The availability of data will help to reproduce results.
However, data cannot always be made publicly available Pineau et al. (2021)
and might not be easily available to collect, i.e. medical data that that is
sensitive McDermott et al. (2021).

Access to code Reproducing the experiments will require more effort if the
code that necessary to run the experiments is not available Pineau et al.
(2021); McDermott et al. (2021).

Documentation factors affect all reproducibility degrees, but can mostly be
controlled by sharing code and data. This is why code and data sharing is so
effective for increasing reproducibility. Documentation factors will support
validation of study design, the evaluation and observation factors as well as
verification of an experiment.

##  10 Discussion

This review has shown that there are many sources of irreproducibility, and
there are probably others that we have not covered. Because of this, it cannot
be expected that all experiments published as scientific articles will be able
to control for all the sources of irreproducibility covered in this review.
Controlling for all these sources is time-consuming, requires a huge effort in
configuration, requires too many computational resources as well as more
diversity between the resources than can be expected from a single lab. The
value of the taxonomy presented here is as a resource for helping the machine
learning community to better understand the possible sources of
irreproducibility that could affect the results of machine learning
experiments and render the conclusions made from them invalid. As such, the
taxonomy could help inform the limitations of experiments, so that over-
claiming of results can be avoided to a greater extent.

One way of managing expectations of which sources of irreproducibility should
be controlled in a study is to distinguish between _confirmatory_ and
_hypothesis generating_ studies. Confirmatory studies test explicit and
precise hypotheses about the effect of factors while in hypothesis generating
studies hypotheses are suggested and help design experiments Cohen (1995).
Expectations about reproducibility would be lower for hypotheses generating
studies while they would be higher for confirmatory studies. We propose that
study design and observation factors can be relaxed while implementation and
evaluation factors do not have to be given much consideration for hypothesis
generating studies. Only algorithmic (when relevant) and documentation factors
should be given attention for hypothesis generation studies. For confirmatory
studies, one could argue that all relevant factors should at least be
discussed if not controlled for.

Another way of managing expectations of which sources of irreproducibility to
be controlled is to distinguishes between inter- and intra-laboratory
reproducibility. This is done in other domains of scientific discovery, such
as analytical chemistry Miller and Miller (2018). Inter-laboratory
reproducibility is a measure of variance in results between laboratories,
while intra-laboratory reproducibility measures variance in the results within
the laboratory. A similar distinction can be made in machine learning if one
considers differing hardware and ancillary software as inter-laboratory
conditions. This means that for experiments run in one laboratory intra-
laboratory variation should be reported. Could studies that do not consider
inter-laboartory reproducibility be considered confirmatory at all? Ioannidis
Ioannidis (2005) suggests that care should be taken for small effect sizes,
which is defined as less than 1.5%. Pham et al. Pham et al. (2020) found that
implementation factors results in a 2.9% difference in performance when
conducting the exact same experiment, so many state of the art results are
likely just caused by implementation factors.

A striking finding that was commented on by Belz et al. Belz et al. (2021a) is
that reproduction under same conditions far more frequently yields results
that are worse than results that are better. However, it is non-trivial to
determine the number of identical runs needed to decide which algorithm is
best. A solution Pham et al Pham et al. (2020) propose is to iteratively
performing more experiment runs where results are compared to a selected
baseline; the process can stop when statistical tests confirm the significance
of the difference between the algorithms.

This review shows that the interest in the methodological issues caused by the
apparent stagnation of some sub-fields of machine learning has grown lately.
Still, some challenges remain. We identify three main lines of inquiry:

  1. 1.

Methodology: Methodologies must be developed that lay out how experiments can
be designed to control for the sources of irreproducibility.

  2. 2.

Control: Which sources of irreproducibility different experiment types are
expected to control for should be identified.

  3. 3.

Distributed scenarios: How will distributed data and computation affect the
reproducibility of results, and how can the sources of irreproducibilty be
controlled for in these scenarios?

The community needs better guidance in how to improve reproducibility of
experiments and need to better understand how distributed experiments will
affect reproducibility. A proper understanding of the sources of
irreproducibility is a first step.

## References

  * Alahmari et al. [2020] Saeed S Alahmari, Dmitry B Goldgof, Peter R Mouton, and Lawrence O Hall.  Challenges for the repeatability of deep learning models.  IEEE Access, 8:211860–211868, 2020.
  * Belz et al. [2021a] Anya Belz, Shubham Agarwal, Anastasia Shimorina, and Ehud Reiter.  A systematic review of reproducibility research in natural language processing.  In 16th Conference of the European Chapter of the Associationfor Computational Linguistics 2021, pages 381–393. Association for Computational Linguistics, 2021.
  * Belz et al. [2021b] Anya Belz, Anastasia Shimorina, Shubham Agarwal, and Ehud Reiter.  The reprogen shared task on reproducibility of human evaluations in nlg: Overview and results.  In The 14th International Conference on Natural Language Generation, 2021.
  * Bouthillier and Varoquaux [2020] Xavier Bouthillier and Gaël Varoquaux.  Survey of machine-learning experimental methods at neurips2019 and iclr2020.  Technical Report hal-02447823, Inria Saclay Ile de France, 2020.
  * Bouthillier et al. [2019] Xavier Bouthillier, César Laurent, and Pascal Vincent.  Unreproducible research is reproducible.  In International Conference on Machine Learning, pages 725–734. PMLR, 2019.
  * Bouthillier et al. [2021] Xavier Bouthillier, Pierre Delaunay, Mirko Bronzi, Assya Trofimov, Brennan Nichyporuk, Justin Szeto, Nazanin Mohammadi Sepahvand, Edward Raff, Kanika Madan, Vikram Voleti, et al.  Accounting for variance in machine learning benchmarks.  Proceedings of Machine Learning and Systems, 3, 2021.
  * Card et al. [2020] Dallas Card, Peter Henderson, Urvashi Khandelwal, Robin Jia, Kyle Mahowald, and Dan Jurafsky.  With little power comes great responsibility.  In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 9263–9274, 2020.
  * Cockburn et al. [2020] Andy Cockburn, Pierre Dragicevic, Lonni Besançon, and Carl Gutwin.  Threats of a replication crisis in empirical computer science.  Communications of the ACM, 63(8):70–79, 2020.
  * Cohen [1995] Paul R Cohen.  Empirical methods for artificial intelligence, volume 139.  MIT press Cambridge, 1995.
  * Çöltekin [2020] Çağrı Çöltekin.  Verification, reproduction and replication of nlp experiments: A case study on parsing universal dependencies.  In Proceedings of the Fourth Workshop on Universal Dependencies (UDW 2020), pages 46–56, 2020.
  * Cooper et al. [2021] A Feder Cooper, Yucheng Lu, Jessica Forde, and Christopher M De Sa.  Hyperparameter optimization is deceiving us, and how to stop it.  Advances in Neural Information Processing Systems, 34, 2021.
  * Crane [2018] Matt Crane.  Questionable answers in question answering research: Reproducibility and variability of published results.  Transactions of the Association for Computational Linguistics, 6:241–252, 2018.
  * Cremonesi and Jannach [2021] Paolo Cremonesi and Dietmar Jannach.  Progress in recommender systems research: Crisis? what crisis?  AI Magazine, 42(3):43–54, 2021.
  * Dacrema et al. [2019] Maurizio Ferrari Dacrema, Paolo Cremonesi, and Dietmar Jannach.  Are we really making much progress? a worrying analysis of recent neural recommendation approaches.  In Proceedings of the 13th ACM Conference on Recommender Systems, pages 101–109, 2019.
  * Dacrema et al. [2021] Maurizio Ferrari Dacrema, Simone Boglio, Paolo Cremonesi, and Dietmar Jannach.  A troubling analysis of reproducibility and progress in recommender systems research.  ACM Transactions on Information Systems (TOIS), 39(2):1–49, 2021\.
  * Dodge et al. [2019] Jesse Dodge, Suchin Gururangan, Dallas Card, Roy Schwartz, and Noah A Smith.  Show your work: Improved reporting of experimental results.  In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pages 2185–2194, 2019.
  * Drummond [2009] Chris Drummond.  Replicability is not reproducibility: nor is it good science.  In Proc. of the Evaluation Methods for Machine Learning Workshop at the 26th International Conference on Machine Learning, Montreal, Canada, June 2009.
  * Fichte et al. [2021] Johannes K Fichte, Markus Hecher, Ciaran McCreesh, and Anas Shahab.  Complications for computational experiments from modern processors.  In 27th International Conference on Principles and Practice of Constraint Programming (CP 2021). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2021.
  * Gebru et al. [2021] Timnit Gebru, Jamie Morgenstern, Briana Vecchione, Jennifer Wortman Vaughan, Hanna Wallach, Hal Daumé Iii, and Kate Crawford.  Datasheets for datasets.  Communications of the ACM, 64(12):86–92, 2021.
  * Goodchild and Li [2021] Michael F Goodchild and Wenwen Li.  Replication across space and time must be weak in the social and environmental sciences.  Proceedings of the National Academy of Sciences, 118(35), 2021.
  * Götz-Hahn et al. [2020] Franz Götz-Hahn, Vlad Hosu, and Dietmar Saupe.  Critical analysis on the reproducibility of visual quality assessment using deep features.  arXiv preprint arXiv:2009.05369, 2020.
  * Gundersen and Kjensmo [2018] Odd Erik Gundersen and Sigbjørn Kjensmo.  State of the art: Reproducibility in artificial intelligence.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
  * Gundersen et al. [2022] Odd Erik Gundersen, Saeid Shamsaliei, and Richard Juul Isdahl.  Do machine learning platforms provide out-of-the-box reproducibility?  Future Generation Computer Systems, 126:34–47, 2022.
  * Gundersen [2019] Odd Erik Gundersen.  Standing on the feet of giants - reproducibility in ai.  AI Magazine, 40(4):9–23, 2019.
  * Gundersen [2021a] Odd Erik Gundersen.  The case against registered reports.  AI Mag., 42(1):88–92, 2021.
  * Gundersen [2021b] Odd Erik Gundersen.  The fundamental principles of reproducibility.  Philosophical Transactions of the Royal Society A, 379(2197):20200210, 2021.
  * Haibe-Kains et al. [2020] Benjamin Haibe-Kains, George Alexandru Adam, Ahmed Hosny, Farnoosh Khodakarami, Levi Waldron, Bo Wang, Chris McIntosh, Anna Goldenberg, Anshul Kundaje, Casey S Greene, et al.  Transparency and reproducibility in artificial intelligence.  Nature, 586(7829):E14–E16, 2020.
  * Henderson et al. [2018] Peter Henderson, Riashat Islam, Philip Bachman, Joelle Pineau, Doina Precup, and David Meger.  Deep reinforcement learning that matters.  In Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018.
  * Hong et al. [2013] Song-You Hong, Myung-Seo Koo, Jihyeon Jang, Jung-Eun Esther Kim, Hoon Park, Min-Su Joh, Ji-Hoon Kang, and Tae-Jin Oh.  An evaluation of the software system dependency of a global atmospheric model.  Monthly Weather Review, 141(11):4165–4172, 2013.
  * Ioannidis [2005] John PA Ioannidis.  Why most published research findings are false.  PLoS medicine, 2(8):e124, 2005.
  * Kurach et al. [2018] Karol Kurach, Mario Lucic, Xiaohua Zhai, Marcin Michalski, and Sylvain Gelly.  The gan landscape: Losses, architectures, regularization, and normalization.  In ICML 2018 Workshop on Reproducibility in Machine Learning, 2018\.
  * Latifi et al. [2021] Sara Latifi, Noemi Mauro, and Dietmar Jannach.  Session-aware recommendation: A surprising quest for the state-of-the-art.  Information Sciences, 573:291–315, 2021.
  * Lipton and Steinhardt [2019] Zachary C. Lipton and Jacob Steinhardt.  Troubling trends in machine learning scholarship: Some ml papers suffer from flaws that could mislead the public and stymie future research.  Queue, 17(1):45–77, feb 2019.
  * Lucic et al. [2018] Mario Lucic, Karol Kurach, Marcin Michalski, Sylvain Gelly, and Olivier Bousquet.  Are gans created equal? a large-scale study.  In NeurIPS, 2018.
  * Makridakis et al. [2018] Spyros Makridakis, Evangelos Spiliotis, and Vassilios Assimakopoulos.  Statistical and machine learning forecasting methods: Concerns and ways forward.  PloS one, 13(3):e0194889, 2018.
  * McDermott et al. [2021] Matthew BA McDermott, Shirly Wang, Nikki Marinsek, Rajesh Ranganath, Luca Foschini, and Marzyeh Ghassemi.  Reproducibility in machine learning for health research: Still a ways to go.  Science Translational Medicine, 13(586):eabb1655, 2021.
  * Melis et al. [2018] Gábor Melis, Chris Dyer, and Phil Blunsom.  On the state of the art of evaluation in neural language models.  In International Conference on Learning Representations, 2018.
  * Miller and Miller [2018] James Miller and Jane C Miller.  Statistics and chemometrics for analytical chemistry.  Pearson education, 2018.
  * Nagarajan et al. [2019] Prabhat Nagarajan, Garrett Warnell, and Peter Stone.  The impact of nondeterminism on reproducibility in deep reinforcement learning.  Presented at the AAAI 2019 Workshop on Reproducible AI, Hon- olulu, Hawaii, 2019.
  * Pham et al. [2020] Hung Viet Pham, Shangshu Qian, Jiannan Wang, Thibaud Lutellier, Jonathan Rosenthal, Lin Tan, Yaoliang Yu, and Nachiappan Nagappan.  Problems and opportunities in training deep learning software systems: An analysis of variance.  In Proceedings of the 35th IEEE/ACM International Conference on Automated Software Engineering, pages 771–783, 2020.
  * Pineau et al. [2021] Joelle Pineau, Philippe Vincent-Lamarre, Koustuv Sinha, Vincent Larivière, Alina Beygelzimer, Florence d’Alché Buc, Emily Fox, and Hugo Larochelle.  Improving reproducibility in machine learning research: a report from the neurips 2019 reproducibility program.  Journal of Machine Learning Research, 22, 2021.
  * Pinto et al. [2021] Wagner Gonçalves Pinto, Antonio Alguacil, and Michaël Bauerheim.  On the reproducibility of fully convolutional neural networks for modeling time-space evolving physical systems.  arXiv preprint arXiv:2105.05482, 2021.
  * Pouchard et al. [2020] Line Pouchard, Yuewei Lin, and Hubertus Van Dam.  Replicating machine learning experiments in materials science.  In Parallel Computing: Technology Trends, pages 743–755. IOS Press, 2020.
  * Raff [2019] Edward Raff.  A step toward quantifying independently reproducible machine learning research.  Advances in Neural Information Processing Systems, 32, 2019.
  * Recht et al. [2019] Benjamin Recht, Rebecca Roelofs, Ludwig Schmidt, and Vaishaal Shankar.  Do imagenet classifiers generalize to imagenet?  In International Conference on Machine Learning, pages 5389–5400. PMLR, 2019.
  * Reimers and Gurevych [2017] Nils Reimers and Iryna Gurevych.  Reporting score distributions makes a difference: Performance study of lstm-networks for sequence tagging.  In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pages 338–348, 2017.
  * Roberts et al. [2021] Michael Roberts, Derek Driggs, Matthew Thorpe, Julian Gilbey, Michael Yeung, Stephan Ursprung, Angelica I Aviles-Rivero, Christian Etmann, Cathal McCague, Lucian Beer, et al.  Common pitfalls and recommendations for using machine learning to detect and prognosticate for covid-19 using chest radiographs and ct scans.  Nature Machine Intelligence, 3(3):199–217, 2021.
  * Rupprecht et al. [2020] Lukas Rupprecht, James C Davis, Constantine Arnold, Yaniv Gur, and Deepavali Bhagwat.  Improving reproducibility of data science pipelines through transparent provenance capture.  Proceedings of the VLDB Endowment, 13(12):3354–3368, 2020.
  * Sculley et al. [2018] David Sculley, Jasper Snoek, Alex Wiltschko, and Ali Rahimi.  Winner’s curse? on pace, progress, and empirical rigor.  In ICLR 2018 Workshop Track, 2018.
  * Stodden [2015] Victoria Stodden.  Reproducing statistical results.  Annual Review of Statistics and Its Application, 2:1–19, 2015.
  * Torralba and Efros [2011] Antonio Torralba and Alexei A Efros.  Unbiased look at dataset bias.  In CVPR 2011, pages 1521–1528. IEEE, 2011.
  * Wagstaff [2012] Kiri L Wagstaff.  Machine learning that matters.  In Proceedings of the 29th International Coference on International Conference on Machine Learning, pages 1851–1856, 2012.
  * Zhang and Duh [2020] Xuan Zhang and Kevin Duh.  Reproducible and efficient benchmarks for hyperparameter optimization of neural machine translation systems.  Transactions of the Association for Computational Linguistics, 8:393–408, 2020.
  * Zhuang et al. [2021] Donglin Zhuang, Xingyao Zhang, Shuaiwen Leon Song, and Sara Hooker.  Randomness in neural network training: Characterizing the impact of tooling.  arXiv preprint arXiv:2106.11872, 2021.