$\sum_{i}l_{i}\geq n$, is minimized when $l_{i}=n/k$ for all $i$.

The following is now easy:

######  Corollary B.25.

For every $S\subseteq V(K_{n})$, if $|S|\leq(C_{n/k})^{k}/2$, for integer
$k\in[1,n]$, then $|\partial
S|/|S|\geq\Omega(1/((n/2^{\lfloor\log_{3}k\rfloor})^{3/2}\log(n/2^{\lfloor\log_{3}k\rfloor})))$.

######  Proof B.26.

The claim follows from noticing that any such set can be partitioned into its
intersections with Cartesian products (sets of triangulations) of the form
described in Lemma B.23, each of which is at most half full, then noticing
that in each such Cartesian product, by Lemma B.23 each graph $K_{i_{j}}$ in
the product has $i_{j}\leq\frac{n}{2^{\lfloor\log_{3}k\rfloor}}$. Appyling
Theorem 1.4 then proves the claim.

We now combine Lemma B.22 with Lemma B.23, then combine Lemma 2.2 with Theorem
1.4 to obtain mixing time $O(n^{3}\log^{3}n)$ for triangulations, proving
Theorem 1.1:

######  Proof B.27.

Proof of Theorem 1.1 We can write, by Lemma B.22,

$\tau(n)\leq O(1)\int_{\pi_{\min}}^{1/2}{\frac{dx}{(\phi(x))^{2}x}}$
$=O(1)\sum_{k=1}^{n}\int_{(C_{n/(k+1)})^{k+1}/C_{n}}^{(C_{n/k})^{k}/C_{n}}O((n/2^{\lfloor\log_{3}k\rfloor})^{3}\log^{2}(n/2^{\lfloor\log_{3}k\rfloor}))\frac{dx}{x}$
$\leq
O(n^{3}\log^{2}n)\sum_{k=1}^{n}O((1/2^{\lfloor\log_{3}k\rfloor})^{3}\int_{(C_{n/(k+1)})^{k+1}/C_{n}}^{(C_{n/k})^{k}/C_{n}}\frac{dx}{x}$
$=O(n^{3}\log^{2}n)\sum_{k=1}^{n}O((1/2^{\lfloor\log_{3}k\rfloor})^{3}\ln\left(\frac{(C_{n/k})^{k}}{(C_{n/(k+1)})^{k+1}}\right)$
$=O(n^{3}\log^{2}n)\sum_{k=1}^{n}O((1/2^{\lfloor\log_{3}k\rfloor})^{3}\ln(O(n^{3/2}))$
$=O(n^{3}\log^{3}n)\sum_{k=1}^{n}O(1/k^{\log_{3}8})$ $=O(n^{3}\log^{3}n)\cdot
O(1)=O(n^{3}\log^{3}n).$

##  Appendix C Associahedron expansion upper bound

To prove Theorem 1.4, we simply find a sparse cut and apply the definition of
expansion. We use the central-triangle partition we used in Appendix D and
Appendix B. These are the same classes used to show the $\Omega(n^{3/2})$
mixing lower bound by Molloy, Reed, and Steiger [36]. As we discussed in the
introduction, their mixing lower bound does _not_ imply the expansion upper
bound we give here, but our expansion upper bound does imply their mixing
lower bound.

###  C.1 Finding a sparse cut

We will find a cut $(S,\bar{S})$ with $|\partial S|/|S|=O(n^{-1/2}).$ We start
by partitioning the vertices of the associahedron into central-classes as in
Appendix B; within any given class, all vertices will be on the same side of
the cut. Consider the associahedron $K_{n-2}$ over the $n$-gon. Draw the
regular $n$-gon in the plane, and label the vertices of the regular $n$-gon
$[0,n-1]$, with $0$ as the topmost vertex.

Let $\mathcal{C}_{l}=\\{t\in\mathcal{C}(T)|T\textnormal{ has shortest side
length}l\\}$ be the set of all triangulations whose central triangle’s
shortest side has length $l$, $l\in[1,n/3]$.

Let $\mathcal{S}=\bigcup_{\mathcal{C}_{l}|l\in[1,n/6]}\mathcal{C}_{l}$. Let
$\mathcal{\bar{S}}=V(K_{n-2})\setminus\mathcal{S}=\bigcup_{\mathcal{C}_{l}|l\in(n/6,n/3]}\mathcal{C}_{l}$.

######  Lemma C.1.

The cut $\mathcal{S}$ is indeed a partition of $V(K_{n-2})$, has
$|\mathcal{S}|=\Theta(1)|V(K_{n-2})|$ and
$|\mathcal{\bar{S}}|=\Theta(1)|V(K_{n-2}|$.

######  Proof C.2.

It is clear that every triangulation lies in exactly one $\mathcal{C}_{l}$,
and that $\mathcal{S}$ and $\mathcal{\bar{S}}$ together partition all of the
triangulations. To see that
$|\mathcal{S}|=\Theta(1)|V(K_{n-2})|=\Theta(1)C_{n-2}$, we first count the
cardinality of each $\mathcal{C}_{l},l\in[1,n/6]$. Consider the number of ways
to choose a central triangle $T$ so that
$\mathcal{C}(T)\subseteq\mathcal{C}_{l}$, i.e. so that $T$ has shortest side
length $l$. Notice that there are $n$ ways to choose the apex of a central
triangle (the vertex opposite the shortest side). Conditioned on this choice,
and conditioned on a choice of $l$ for the side length opposite the apex,
there are $l$ ways to choose the second vertex (the first vertex after the
apex in counterclockwise order) so that the center of the $n$-gon still lies
inside the triangle. For all of these choices, the side opposite the apex is
indeed shortest. The number of triangulations lying in a class with shortest
side length $l$ is $\Theta\left(\frac{1}{n^{3/2}l^{3/2}}\right)C_{n-2}$, and
thus the number of triangulations is

$\sum_{l=1}^{n/6}nl\frac{1}{\Theta(n^{3/2}l^{3/2})}=\Theta\left(\frac{1}{\sqrt{n}}\right)\sum_{l=1}^{n/6}\Theta\left(\frac{1}{\sqrt{l}}\right)=\Theta\left(\frac{\sqrt{n}}{\sqrt{n}}\right)=\Theta(1).$

Thus $|\mathcal{S}|=\Theta(1)C_{n-2}|$. For $|\mathcal{S}|$, notice that for
every $T$ with shortest side length $l\in(n/6,n/3]$, there are $\Theta(n^{2})$
ways to choose $T$, by the same argument we used for $l\in[1,n/6]$, and each
central-triangle-induced class $\mathcal{C}(T)$ with shortest side
$l\in(n/6,n/3]$ has $|\mathcal{C}(T)|=\Theta\left(\frac{1}{n^{3}}\right)$.
Thus we have the sum

$\sum_{l=n/6+1}^{n/3}\frac{\Theta(n^{2})}{\Theta(n^{3})}=\Theta(1).$

######  Lemma C.3.

The cut $(\mathcal{S},\mathcal{\bar{S}})$ has $|\partial S|/|S|=O(1/\sqrt{n})$

######  Proof C.4.

Notice that in order for a triangulation $t\in\mathcal{C}(T)$, given a
central-triangle class $T$ in $\mathcal{C}_{l}$, $l\in[1,n/6]$, to have a
neighbor in $\mathcal{\bar{S}}$, i.e. for $t$ to have a neighboring
triangulation $t^{\prime}\in\mathcal{C}(T^{\prime})$ with $T^{\prime}$ having
shortest side length $k\geq n/6+1$, the central triangles $T$ and $T^{\prime}$
must form a quadrilateral in $t$ and in $t^{\prime}$. This quadrilateral, in
$t$, consists of $T$ along with a triangle $U$, where $U$ has shortest side
length $k$. The fraction of triangulations lying in the boundary set
$\mathcal{B}_{T^{\prime}}(T)$ is therefore at most
$O\left(\frac{1}{(k-l)^{3/2}}\right).$

For $l\in[1,n/6]$, let

$\partial_{l}S=\\{(t,t^{\prime})\in
E(K_{n-2})|t\in\mathcal{C}_{l},t^{\prime}\in\mathcal{\bar{S}}\\}=\bigcup_{\mathcal{C}(T)\subseteq\mathcal{C}_{l},\mathcal{C}(T^{\prime})\subseteq\mathcal{\bar{S}}}\mathcal{E}(T,T^{\prime})$

be the set of all cut edges incident to triangulations in $\mathcal{C}_{l}$.

We will split the sets $\\{\mathcal{C}_{l}\\}$ in $\mathcal{S}$ into the cases
$l\in[1,n/8]$ and $l\in(n/8,n/6]$. First, for all $l\in[1,n/8]$, by the above
reasoning, we have

$|\partial_{l}S|/|\mathcal{C}_{l}|=\sum_{k=n/6+1}^{n/3}O\left(\frac{1}{(k-l)^{3/2}}\right)\leq(n/3-n/6)O\left(\frac{1}{(n/6+1-l)^{3/2}}\right)$
$\leq(n/3-n/6)O\left(\frac{1}{(n/6+1-n/8)^{3/2}}\right)=O\left(\frac{n}{n^{3/2}}\right)=O(1/\sqrt{n}).$

On the other hand, for $l\in(n/8,n/6]$, we compute the sum

$\frac{\sum_{l=n/8+1}^{n/6}|\partial_{l}S|}{|\mathcal{S}|}=\sum_{l=n/8+1}^{n/6}\frac{|\partial_{l}S|}{\Theta(1)C_{n-2}}\leq\sum_{l=n/8+1}^{n/6}|\mathcal{C}_{l}|\sum_{k=n/6+1}^{n/3}O\left(\frac{1}{(k-l)^{3/2}}\right)$
$=\int_{l=n/8+1}^{n/6}O\left(\frac{1}{\sqrt{n}\sqrt{l}}\right)\int_{k=n/6+1}^{n/3}O\left(\frac{1}{(k-l)^{3/2}}\right)dkdl,$

where for the last inequality we have applied the observation from the proof
of Lemma C.1 that
$|\mathcal{C}_{l}|=O\left(\frac{1}{\sqrt{n}\sqrt{l}}\right)C_{n-2},$ and have
used the fact that asymptotically the summation is equal to a double integral.
Evaluating the inner integral we obtain

$O\left(\frac{1}{\sqrt{n}}\right)\int_{l=n/8+1}^{n/6}O\left(\frac{1}{\sqrt{l}\sqrt{n/6+1-l}}\right)dl=O\left(\frac{1}{n}\right)\int_{u=1}^{n/6-n/8}O\left(\frac{1}{\sqrt{u}}\right)du,$

with the substitution $u=n/6+1-l$ and the observation that when $l\geq n/8$ we
have $1/\sqrt{l}=O(1/\sqrt{n})$. Finally, evaluating the integral gives

$O\left(\frac{1}{n}\cdot\sqrt{n/6-n/8}\right)=O(1/\sqrt{n}).$

We now have

$|\partial
S|/|S|=\sum_{l\in[1,n/6]}|\partial_{l}S|/|S|=\sum_{l\in[1,n/8]}|\partial_{l}S|/|S|+\sum_{l\in[n/8+1,n/6]}|\partial_{l}S|/|S|=O(1/\sqrt{n})+O(1/\sqrt{n})=O(1/\sqrt{n}),$

as claimed.

##  Appendix D $k$-angulations of convex point sets: quasipolynomial mixing

###  D.1 Generalizing triangulations

As we stated in the introduction, one can generalize triangulations to
$k$-angulations. We do so in more detail here. A _quadrangulation_ of a point
set is a maximal subdivision of the point set into quadrilaterals, where each
quadrilateral has all of its vertices in the point set. Consider $P_{2n+2}$,
the regular polygon with $2n+2$ vertices. We denote by $K_{4,2n+2}$ the graph
whose vertex set is the set of all quadrangulations of $P_{2n+2}$, and whose
edges are the flips between quadrilaterals. Here, a flip is defined as
follows: each diagonal belongs to two quadrilaterals, which together form a
hexagon. Replace the diagonal with one of the other two diagonals in the
hexagon. (Thus each diagonal in a qudrangulation can be flipped in two
possible ways [9].)

There is a polytope, analogous to the associahedron, known as the
_accordiohedron_ [23, 5], whose vertices and edges are those of a _subgraph_
of $K_{4,2n+2}$. However, we ignore this polytope and just consider the graph
$K_{4,2n+2}$.

We refer to a _$k$ -angulation_ of a point set as a maximal subdivision of the
point set into $k$-gons, each of whose vertices all belong to the point set. A
bijection exists [22] between the $k$-angulations of $P_{(k-2)n+2}$ and the
set of all $k-1$-ary plane trees with $n$ internal nodes.

It is easy to generalize the definition of a flip between triangulations or
quadrangulations to a flip between $k$-angulations: each diagonal in a
$k$-angulation belongs to two $k$-gons, which together form a $2k-2$-gon. A
flip then consists of replacing this diagonal—which connects two opposite
vertices in the $2k-2$-gon—with one of the $k-2$ other such diagonals.

We generalize the associahedron graph $K_{n}$ as follows:

######  Definition D.1.

Define the _$k$ -angulation flip graph_ $K_{k,(k-2)n+2}$ as the graph whose
vertices represent the $k$-angulations of $P_{(k-2)n+2}$, and whose edges
represent the flips between $k$-angulations.

######  Definition D.2.

Define the _$k$ -angulation flip walk_ as the natural Markov chain whose state
space is $K_{k,(k-2)n+2}$.

###  D.2 (Generalized) Catalan numbers

The usual notation for Catalan numbers is simply $C_{n}$; we will now consider
a generalization:

######  Definition D.3.

[38, 29, 22] Let $C_{k,n}=\frac{1}{(k-2)n+1}\binom{(k-1)n}{n}.$

These numbers, which generalize Catalan numbers, are similar but not identical
to the _Fuss-Catalan_ numbers.

We will use the following fact in proving that the random walk on
$k$-angulations mixes in quasipolynomial time:

######  Lemma D.4.

[29, 22] The number of $k$-angulations of the convex $(k-2)n+2$-gon is counted
by $C_{k,n}.$

One can show using Stirling’s formula, and in particular a result by Robbins
[40], that:

######  Lemma D.5.

For all $k\geq 3$ and $n\geq 1$, $e^{-1/6}\frac{k-2}{k-1}f(k,n)\leq
C_{k,n}\leq e^{1/12}\cdot f(k,n)$, where

$f(k,n)=\frac{\sqrt{k-1}}{\sqrt{2\pi}((k-2)n)^{3/2}}\cdot\frac{(k-1)^{(k-1)n}}{(k-2)^{(k-2)n}}.$

We will prove the following:

######  Lemma D.6.

The flip graph $K_{k,(k-2)n+2}$, along with the partition
$\mathcal{S}_{k,(k-2)n+2}$, satisfies Lemma 4.8.

Theorem 1.5, as we will show in Appendix D, will follow from tracing the
particular quasipolynomial factors in the proof of Lemma D.6.

To prove Lemma D.6, we will partition $K_{k,(k-2)n+2}$ into a set of classes
$\mathcal{S}_{k}$ in a suitable fashion. We will define a partition that
generalizes one by Molloy, Reed, and Steiger [36]. In order to define
$\mathcal{S}_{k}$, we need some observations about the structure of the graph
$K_{k,(k-2)n+2}$.

###  D.3 Partition into classes

Figure 8: Left: a class $\mathcal{C}(T)$ in $K_{3,n+2}$. Each triangulation in
$\mathcal{C}(T)$ contains the central triangle depicted. We depict the polygon
$P_{n+2}$ as a circle for simplicity. Right: the set of edges
$\mathcal{E}(T,T^{\prime})$ (which form a matching) between two classes.

######  Definition D.7.

Given a $k$-gon $T$ containing the center of the regular $(k-2)n+2$-gon
$P_{(k-2)n+2}$ and sharing all of its vertices with $P_{(k-2)n+2}$, identify
$T$ with the class $\mathcal{C}(T)$ of $k$-angulations $v\in
V(K_{k,(k-2)n+2})$ such that $T$ forms one of the $k$-gons in the
$k$-angulation $v$. Let $\mathcal{S}_{k,(k-2)n+2}$ be the set of all such
$\mathcal{C}(T)$ classes.

(If $P_{n+2}$ has an even number of edges, we perturb the center slightly so
that every triangulation lies in some class.)

######  Remark D.8.

The set $\mathcal{S}_{k,(k-2)n+2}$ is a partition of $V(K_{k,(k-2)n+2})$,
because no pair of $k$-gons whose endpoints are polygon vertices can contain
the origin without crossing.

(This generalizes the partition of Molloy, Reed, and Steiger [36].)

######  Definition D.9.

Given classes
$\mathcal{C}(T),\mathcal{C}(T^{\prime})\in\mathcal{S}_{k,(k-2)n+2}$, let
$\mathcal{E}(T,T^{\prime})$ be the set of edges between with one endpoint in
$\mathcal{C}(T)$ and one endpoint in $\mathcal{C}(T^{\prime})$. Let
$\mathcal{B}_{T^{\prime}}(T)$ denote the set of vertices in $\mathcal{C}(T)$
that have at least one neighbor in $\mathcal{C}(T^{\prime})$.

See Figure 8.

######  Remark D.10.

The set of edge sets of the form $\mathcal{E}(T,T^{\prime})$ is a partition of
all edges between pairs of vertices in different classes.

####  D.3.1 Cardinalities of classes and of edge sets

We make some observations about the nature and cardinalities of the classes in
$\mathcal{S}_{k,(k-2)n+2}$, and of the sets and numbers of edges between the
classes.

######  Lemma D.11.

Each $k$-gonal class in $\mathcal{S}_{k,(k-2)n+2}$ induces a subgraph of
$K_{k,(k-2)n+2}$ that is isomorphic to the Cartesian product
$K_{k,(k-2)i_{1}+2}\Box K_{k,(k-2)i_{2}+2}\Box\cdots K_{k,(k-2)i_{k}+2},$ for
some $1\leq i_{1}\leq\cdots\leq i_{k}\leq n/2$, $i_{1}+\cdots+i_{k}=n-1.$

######  Proof D.12.

Each $k$-gon $T$ partitions the regular $(k-2)n+2$-gon into smaller convex
polygons with side lengths $(k-2)i_{1}+2,(k-2)i_{2}+2,\dots,(k-2)i_{k}+2$.
Thus each $k$-angulation in $\mathcal{C}(T)$ can be identified with a tuple of
$k$-angulations of these smaller polygons. The Cartesian product structure
then follows from the fact that every flip between two $k$-angulations in
$\mathcal{C}(T)$ can be identified with a flip in one of the smaller polygons.

######  Lemma D.13.

For each pair of classes $\mathcal{C}(T)$ and $\mathcal{C}(T^{\prime})$, the
boundary set $\mathcal{B}_{T^{\prime}}(T)$ induces a subgraph of
$\mathcal{C}(T)$ isomoprhic to a union of Cartesian products of the form
$K_{(k-2)i_{1}+2}\Box K_{(k-2)i_{2}+2}\Box\cdots\Box K_{(k-2)i_{2k-2}+2}$, for
some $i_{1}\leq\cdots\leq i_{2k-2}\leq n/2,$ $i_{1}+\cdots+i_{2k-2}=n-2$.

######  Proof D.14.

Each flip between $k$-angulations in adjacent classes $\mathcal{C}(T)$
involves flipping a diagonal of the $k$-gon $T$ to transform $k$-angulation
$t\in\mathcal{C}(T)$ into $k$-angulation
$t^{\prime}\in\mathcal{C}(T^{\prime})$. Whenever this is possible, there must
exist a $2k-2$-gon $Q$, sharing $k-1$ sides with $T$ (the $k-1$ sides that are
not flipped), such that both $t$ and $t^{\prime}$ contain $Q$. Furthermore,
every $t\in\mathcal{C}(T)$ containing $Q$ has a flip to a distinct
$t^{\prime}\in\mathcal{C}(T^{\prime})$. The set of all such boundary vertices
$t\in\mathcal{C}(T)$ can be identified with the Cartesian product described
because $Q$ partitions $P_{(k-2)n+2}$ into a collection of smaller polygons,
so that each $k$-angulation in $\mathcal{B}_{T^{\prime}}(T)$ consists of a
tuple of $k$-angulations in each of these smaller polygons, and such that
every flip between $k$-angulations in $\mathcal{B}_{T^{\prime}}(T)$ consists
of a flip in one of these smaller polygons. (There may be many such
$2k-2$-gons for a given pair of classes, but the claim holds as a lower
bound.)

######  Lemma D.15.

Each set of edges between classes in $\mathcal{S}_{k,(k-2)n+2}$ is in
bijection with the vertices of a union of Cartesian products of the form
$K_{(k-2)i_{1}+2}\Box K_{(k-2)i_{2}+2}\Box\cdots\Box K_{(k-2)i_{2k-2}+2}$, for
$i_{1}\leq\cdots\leq i_{2k-2}\leq n/2,$ $i_{1}+\cdots+i_{2k-2}=n-2$.
Furthermore, no two edges in any such edge set share a vertex, i.e. the edge
set is a matching.

######  Proof D.16.

The claim follows from the reasoning in Lemma D.13.

######  Corollary D.17.

Each $k$-gonal class in $\mathcal{S}_{k,(k-2)n+2}$ has cardinality
$C_{k,i_{1}}C_{k,i_{2}}\cdots C_{k,i_{k}}$, and each edge set between classes
has cardinality at least $C_{k,i_{1}}C_{k,i_{2}}\cdots C_{k,i_{2k-2}}$. Here,
$i_{1},\dots,i_{2k-2}$ are as in Lemmas D.11 and D.15.

###  D.4 Applying the framework

We are almost ready to prove that $K_{k,(k-2)n+2}$ satisfies the conditions of
Lemma 4.8, but first we note the following known result:

######  Lemma D.18.

$K_{k,(k-2)n+2}$ is connected.

One way to prove Lemma D.18 is via the isomorphism [22] between flips on
$k$-angulations and rotations on $k-1$-ary plane trees. One can prove that the
rotation graph on $k-1$-ary plane trees is connected as follows: find a path
from any given tree to a “spine,” where all internal nodes belong to a simple
path via left children from the root to the leftmost leaf [13]. (This path
consists of repeated left rotations.) Every non-spine tree has some internal
node at which a left rotation can be performed. Furthermore, when no such
operation is still possible, one has a spine.

Nakamoto, Kawatani, Matsumoto, and Urrutia [37] also gave a proof of
connectedness for the special case $k=4$. Sleator, Tarjan, and Thurston proved
[42] that the diameter of $K_{3,n+2}$ is at most $2n-6$ for $n\geq 11$.

We now prove Lemma D.6: See D.6

######  Proof D.19.

By Lemma D.11 and the observation that there are at most $\binom{(k-2)n+2}{k}$
classes, the partition $\mathcal{S}_{k,(k-2)n+2}$ meets Conditions 1 and 5 of
the framework, with the modification to Condition 1 that the $O(1)$ term is
replaced with $O(n^{O(1)})$, and Condition 6 easily follows from the
identification of each class with a $k$-gon containing the center of the
$(k-2)n+2$-gon.

Corollary D.17 gives a formula for the size of each class and each edge set
between classes. Lemma D.5 then easily gives a polynomial bound on the ratio
of $N=|V(K_{k,(k-2)n+2})|$ to the size of the smallest class (similarly the
smallest edge set). Conditions 2, 3, and 4 follow, with the modification that
the $O(1)$ terms are replaced with $O(n^{O(1)})$ terms.

To derive the specific quasipolynomial bound in Theorem 1.5, we first observe
the following:

######  Remark D.20.

The smallest edge set between classes in $\mathcal{S}_{k,(k-2)n+2}$ has size
at least

$C_{k,i_{1}}\cdots C_{k,i_{2k-2}}\geq N\cdot\frac{f(k,i_{1})\cdots
f(k,i_{2k-2})}{e^{(2k-2)/6+1/12}((k-1)/(k-2))^{2k-2}f(k,n)}$ $\geq
Ne^{(3-4k)/12}\cdot\frac{(k-2)^{k-3/2}}{(k-1)^{3k-5/2}}\cdot\frac{1}{(2\pi)^{k-3/2}}\cdot\frac{1}{n^{3k}}.$

The next fact we need comes from Lemma 4.5: See 4.5 Applying Lemma 4.5, and
using the fact that $K_{k,(k-2)n+2}$ is a $\leq(k-2)n$-regular graph with
$\log N\leq(k-1)n\log(k-1)$, gives

$O((2N/\mathcal{E}_{\min})^{2\log n}(k-1)^{3}(\log(k-1))n^{3})$
$=O((k-1)^{3}(\log(k-1))n^{3}(2e^{(4k-3)/12}\cdot\frac{(k-1)^{3k-5/2}}{(k-2)^{k-3/2}}\cdot(2\pi)^{k-3/2}\cdot
n^{3k})^{2\log n})$
$=O((k-1)^{3}(\log(k-1))n^{3}(2e^{(4k)/12}\cdot(k-1)^{3k}\cdot(2\pi)^{k}\cdot
n^{3k})^{2\log n})$ $=O((k-1)^{3}(\log(k-1))\cdot
n^{2(3k\log(k-1)+k(1+\log\pi)+3k\log n+k)+5}).$

Here we have implicitly used Lemma 2.2 to pass from the expansion bound given
by Lemma 4.5 to a mixing bound. Actually, we can do better using the following
standard lemma, which allows for passing from congestion to mixing without a
quadratic loss:

######  Lemma D.21.

[16, 41] Suppose a uniform multicommodity flow $f$ exists in a graph $G=(V,E)$
with congestion $\rho$, in which for every $s,t\in V$,

$\max_{P\in\Gamma_{st}}|P|\leq l,$

for some $l>0$, where $\Gamma_{st}$ s the set of (simple) paths in $G$ from
$s$ to $t$, and where we use the shorthand $f_{st}(P)$ to denote the fraction
of the $s,t$ commodity that $f$ sends along the path $P$. Then the mixing time
of the uniform random walk on $G$ is

$O\left(\frac{\rho l}{d}\log(|V(G)|)\right),$

where $d$ is the maximum degree of $G$.

Then we obtain mixing time

$O((2N/\mathcal{E}_{\min})^{\log n}(k-1)^{2}(\log(k-1))n^{2}\cdot l),$

where $l$ is the maximum length of a path in the flow construction. It is not
difficult to see that since the diameter of the projection graph is at most
$k$, we obtain a recurrence

$l=T(n)=k+2kT(n/2)=O(n^{\log_{2}k+1}),$

giving total mixing

$O((2N/\mathcal{E}_{\min})^{\log n}(k-1)^{2}(\log(k-1))n^{2}\cdot
n^{\log_{2}k+1}),$

Notice that, as discussed in Remark 4.7, we did not incur a term
$\gamma/\Delta$ in this calculation. Furthermore, it is not clear how one
could avoid this $\gamma/\Delta=k$ factor using the spectral decomposition
technique (Theorem 4.3). That technique would give a mixing bound of

$O(((3N/\mathcal{E}_{\min})\cdot k\cdot k)^{\log n}\cdot(k-2)n).$

(Here we have ignored an additional $\log|\Omega|$ term, as one might be able
to reduce this term via, for instance, the log-Sobolev version of the
Jerrum/Son/Tetali/Vigoda decomposition.) Comparing the two expressions above
shows that our technique gives an improvement of

$\Omega\left(\frac{n^{\log_{2}(k^{2})}}{n^{\log_{2}k+1}\cdot kn\log
k}\right)=\Omega(n^{\log_{2}k-2}/(k\log k)).$

##  Appendix E Proof that the conditions of Lemma 4.4 imply rapid mixing

In this section we prove Theorem 4.2. Lemma 4.4 will then follow by way of
Lemma 4.5.

Figure 9: In the flow construction we use for quasipolynomial mixing (Theorem
1.5), we first find a flow in $\mathcal{C}(T)$ (similarly
$\mathcal{C}(T^{\prime})$) and bound its congestion. (Actually, we assume such
a flow exists, for the inductive hypothesis.) We then reuse the paths from
this flow in routing the flow between $t$ and $t^{\prime}$. Reusing these
paths results in compounding the amount of flow across each path by $f(n)$,
where $f(n)$ is the amount of flow across an edge between the two classes.

See 4.2 Here, instead of a uniform flow in which each pair of states exchanges
a single unit, it will be convenient to use a specification of demands and
definition of congestion that are closer to standard in the analysis of Markov
chains: the demands are $D(z,w)=\pi(z)\pi(w)$, and the congestion across an
edge $(x,y)$ produced by a multicommodity flow $f$ that satisfies the demands
$\\{D(z,w)|z,w\in\Omega\\}$ is $\rho(x,y)=f(x,y)/(\Delta\cdot Q(x,y))$, where
$Q(x,y)=\pi(x)P(x,y)=\pi(y)P(y,x)$ (by reversibility). One can check that in
the uniform case, this definition is equivalent to our definition in Section
3. Furthermore, Lemma 3.2 and Lemma 2.2 are known [41] to work for the
weighted case with this adjusted definition of congestion.

The proof of Theorem 4.2 is in fact not difficult to describe intuitively: if
one finds a flow (collection of fractional paths) through the projection graph
between every pair of classes (restriction chains), this flow induces a
subproblem in each class $\Omega_{i}$, in which each “boundary vertex”—each
vertex (state) $z\in\Omega_{i}$ that brings in flow from a neighbor
$w\in\Omega_{j}$—must route the flow it receives throughout $\Omega_{i}$. The
state $z$ may bring in an amount of flow up to $\bar{\rho}\gamma\Delta$ from
such neighbors, and $z$ must route this flow (which we will show in the proof
is at most $\bar{\rho}\gamma\Delta\pi(z)$ throughout $\Omega_{i}$. By
assumption, it is possible for $z$ to route $\pi(z)$ flow throughout
$\Omega_{i}$ with congestion at most $\rho_{\max}$, and therefore $z$ can
route the $\bar{\rho}\gamma\Delta\pi(z)$ flow throughout $\Omega_{i}$ with
congestion at most $\bar{\rho}\gamma\Delta\rho_{\max}$. The factor of 2 in the
term $1+2\bar{\rho}\gamma\Delta$ comes from applying the above reasoning
twice: once for “inbound flow” that $z$ brings into $\Omega_{i}$, and once for
“outbound flow” that $z$ must route from $\Omega_{i}$ to other classes.
Finally, the factor of 1 comes from routing flow between pairs of states
within $\Omega_{i}$.

We now make this reasoning precise:

######  Proof E.1.

(Proof of Theorem 4.2) Let $\\{f_{i},i=1,\dots,k\\}$ be a collection of flow
functions over the restriction chains with congestion
$\rho_{i}\leq\rho_{max}$, as supposed in the theorem statement. Suppose we
have a flow $\bar{f}$ with congestion $\bar{\rho}$ in the projection chain.

We construct a multicommodity flow $f$ in the overall chain $\mathcal{M}$ as
follows: for every edge $e=(x,y),x\in\Omega_{i},y\in\Omega_{j},i\neq j$
between restriction state spaces, let
$f_{xy}=\bar{f}(i,j)Q(x,y)/\bar{Q}(i,j).$ For pairs of states
$x,y\in\Omega_{i}$, simply use the same (fractional) paths to send flow as in
$f_{i}$. Now, for _non-adjacent_ pairs of states
$x\in\Omega_{i},y\in\Omega_{j}$, $i\neq j$, we will use the flow $\bar{f}$ to
route the $x-y$ flow, perhaps through one or more intermediate restriction
spaces. We need to consider how to route the flow _through_ each intermediate
restriction space. This induces a collection of subproblems over each
restriction space $\Omega_{i}$ in which each state $z\in\Omega_{i}$ “brings
in” and similarly “sends out” at most $\sum_{j\neq
i}\sum_{w\in\Omega_{j}}\bar{\rho}\bar{Q}(i,j)Q(z,w)/\bar{Q}(i,j)\leq\bar{\rho}\pi(z)\gamma\Delta$
units of flow. We reuse the (fractional) paths that produce the flow with
congestion $\rho_{max}$, scaling the resulting congestion by
$\bar{\rho}\gamma\Delta$. More precisely, if $e=(x,y)$ is an edge internal to
a restriction space $\Omega_{i}$, let

$\hat{f}_{zu}(x,y)=(D_{in}(z,u)+D_{out}(u,z))(f_{i,zu}(x,y)\cdot\frac{\bar{\pi}(i)}{\pi(z)\pi(u)})$

and denote

$\hat{f}(x,y)=\sum_{zu}\hat{f}_{zu}(x,y)=\sum_{z,u\in\Omega_{i}}(D_{in}(z,u)+D_{out}(u,z))(f_{i,{zu}}(x,y)\cdot\frac{\bar{\pi}(i)}{\pi(z)\pi(u)})$

and $\hat{\rho}(x,y)=\frac{\hat{f}(x,y)}{Q(x,y)}$, where

$D_{in}(z,u)=(\sum_{j\neq
i}\sum_{w\in\Omega_{j}}\bar{f}(i,j)Q(z,w)/\bar{Q}(i,j))\cdot\frac{\pi(u)}{\bar{\pi}(i)}\leq\bar{\rho}\frac{\pi(z)\pi(u)}{\bar{\pi}(i)}\gamma\Delta$

is the share of the demand brought in by $z$ to $\Omega_{i}$ that must be sent
to $u$, and $D_{out}(u,z)$ is similar. This definition $\hat{f}_{zu}(x,y)$
indeed satisfies the demands $D_{in}(z,u)$ and $D_{out}(u,z)$: $f_{i,zu}$ is
defined as sending $\frac{\pi(z)\pi(u)}{\bar{\pi}(i)}$ units of flow along a
set of fractional paths from $z$ to $u$, so the function

$\hat{f}_{zu}(x,y)=(D_{in}(z,u)+D_{out}(u,z))(f_{i,{zu}}(x,y)\cdot\frac{\bar{\pi}(i)}{\pi(z)\pi(u)})$

sends $D_{in}(z,u)+D_{out}(u,z)$ units of flow along the same set of
fractional paths.

Now, we know by the definition of the congestion $\rho_{i}$ produced by
$f_{i}$ that

$\sum_{z,u\in\Omega_{i}}f_{i,zu}(x,y)\leq\rho_{i}Q_{i}(x,y),$

where $Q_{i}(x,y)=\frac{\pi(x)P(x,y)}{\bar{\pi}(i)}.$ Therefore

$\hat{\rho}(x,y)=\frac{\hat{f}(x,y)}{Q(x,y)}=\frac{1}{Q(x,y)}\sum_{z,u\in\Omega_{i}}(D_{in}(z,u)+D_{out})(f_{i,{zu}}(x,y)\cdot\frac{\bar{\pi}(i)}{\pi(z)\pi(u)})$
$\leq\frac{1}{Q(x,y)}\sum_{z,u\in\Omega_{i}}2\bar{\rho}\gamma\Delta\frac{\pi(z)\pi(u)}{\bar{\pi}(i)}(f_{i,zu}(x,y)\cdot\frac{\bar{\pi}(i)}{\pi(z)\pi(u)})=2\bar{\rho}\gamma\Delta\sum_{z\in\Omega_{i}}\frac{f_{i,zu}(x,y)}{Q(x,y)}\leq
2\bar{\rho}\gamma\Delta\rho_{max}.$

Now, for $x,y\in\Omega_{i}$ and for
$u\in\Omega_{i},v\in\Omega_{j}\neq\Omega_{i}$, we let

$f_{vu}(x,y)=\sum_{z\in\Omega_{i}}\hat{f}_{v,zu}(x,y),$

where

$\hat{f}_{v,zu}(x,y)=(D_{v,in}(z,u)+D_{v,out}(u,z))(f_{i,zu}(x,y)\cdot\frac{\bar{\pi}(i)}{\pi(z)\pi(u)},$

where

$D_{v,in}(z,u)=\frac{\pi(u)}{\bar{\pi}(i)}\sum_{k:\exists w\in\Omega_{k},w\sim
z}\bar{f}_{j,i}(k,i)\cdot\frac{Q(\Omega_{k},z)}{\bar{Q}(k,i)}\cdot\frac{\pi(v)}{\bar{\pi}(j)}$

and $D_{v,out}(u,z)$ is symmetric. It is easy to see that $f_{vu}$ indeed is a
valid flow sending $\pi(u)\pi(v)$ units from $v$ to $u$, and also that

$\sum_{j\neq i}\sum_{v\in\Omega_{j}}\hat{f}_{v,zu}=\hat{f}_{zu}.$

Therefore

$\rho(x,y)=\sum_{u\in\Omega_{i}}\sum_{v\notin\Omega_{i}}\frac{f_{vu}(x,y)}{Q(x,y)}=\sum_{u,z\in\Omega_{i}}\sum_{v}\frac{\hat{f}_{v,zu}(x,y)}{Q(x,y)}=\sum_{u,z\in\Omega_{i}}\frac{\hat{f}_{zu}(x,y)}{Q(x,y)}=\hat{\rho}(x,y)\leq
2\bar{\rho}\gamma\Delta\rho_{max}.$

Finally, in the term $\rho(x,y)$ we have only considered $u,v$ flow where
$u,v$ lie in different classes. Adding the congestion $\rho_{i}\leq\rho_{max}$
produced by reusing the flow $f_{i}$ for pairs $u,v\in\Omega_{i}$ justifies
the expression

$(1+2\bar{\rho}\gamma\Delta)\rho_{max}.$

Lemma 4.4 and Lema 4.5 are now immediate, as is Lemma 4.8.

##  Appendix F Integer lattice triangulation flip graphs

###  F.1 Definition

The integer lattice triangulation flip graph, studied extensively in prior
work ([4, 8, 7, 26, 43]), is analogous to the associahedron and is defined as
follows:

######  Definition F.1.

Let the _integer lattice triangulation flip graph_ be the graph $F_{n}$ whose
vertices are the triangulations of the $n\times n$ integer lattice point set
(integer grid), and whose edges are the pairs of triangulations that differ by
exactly one diagonal.

Figure 10: Left: a triangulation of the 9x9 integer lattice. Center: a
division of the lattice into 9 3x3 sections, as described in the proof of
Theorem 1.6. Right: a full triangulation compatible with the division of the
lattice.

It will be useful to define notation for the number of triangulations in this
graph:

######  Definition F.2.

Let $g(n)$ be the number of triangulations of the $n\times n$ integer lattice
point set.

In fact, $g(n)$ is unknown in general, though much progress has been made on
upper and lower bounds, including the following result of Kaibel and Ziegler
[26]:

######  Lemma F.3.

For $n\geq 1$,

$h(n)=\Theta(2^{cn^{2}}),$

for some constant $c$.

As discussed in the introduction, in recent years progress has been made ([8,
7, 43]) in studying the mixing properties of the natural flip walk on the
integer lattice triangulation flip graph. However, this work has focused on
biased versions of the flip walk, in which a real parameter $\lambda>0$
induces a weight function on the triangulations of the lattice, and in which
the random walk is biased in favor of triangulations with larger weights. The
case of $\lambda=1$ is the unbiased version of the walk. It is now known [7]
that when $\lambda>1$, the walk does not mix rapidly, but that rapid mixing
does occur for certain values of $\lambda$ smaller than one. However, the
question is open for the biased version.

We do not settle the question—which would equate to showing that the integer
lattice triangulation flip graph has expansion at least $1/p(n)$ for some
polynomial function $p$, but we do show a weaker result in a similar spirit:
that the flip graph has large subgraphs with large expansion. Note that
expansion measures the extent to which bottlenecks exist in a graph: large
expansion corresponds to a graph that does not have bottlenecks, roughly
speaking. Thus, even if bottlenecks exist in $F_{n}$—that is, if rapid mixing
does _not_ occur, i.e. if the expansion is too small—then there still exist
regions of the graph that are not prone to bottlenecks, and thus internally
induce rapidly mixing walks. Although far from clear evidence of large
expansion in $F_{n}$ itself, one might hope that if bottlenecks exist, this
result may suggest places to look for them.

###  F.2 Additional preliminaries: treewidth, separators, and vertex expansion

The _treewidth_ of a graph $G$ is a different density parameter from
expansion. There are many equivalent definitions of treewidth; one of the
standard definitions is in terms of a so-called _tree decomposition_.

Closely related to treewidth are _vertex separators_ :

######  Definition F.4.

A _vertex separator_ for a graph $G$ is a subset $X\subseteq V(G)$ of the
vertices of $G$ such that $G\setminus X$ is disconnected. $X$ is a _balanced
separator_ if $G\setminus X$ consists of two subgraphs, $A$ and $B$, such that
no edge exists between $A$ and $B$, and such that
$|V(G)|/3\leq|V(A)|\leq|V(B)|\leq 2|V(G)|/3$. We also say, if $|X|\leq s$ for
a given $s\geq 1$, that $X$ is an _$s$ -separator_.

######  Definition F.5.

With respect to an integer $s\geq 1$, a graph $G$ is _recursively
$s$-separable_ if either $|V(G)|\leq 1$, or $G$ has a balanced $s$-separator
$X$ such that the two mutually disconnected subgraphs induced by removing $X$
from $G$ are both recursively $s$-separable.

The following is known [19]:

######  Lemma F.6.

For every $t\geq 1$, every graph with treewidth at most $t$ is recursively
$t+1$-separable.

Treewidth in general is of interest in large part because many NP-hard
problems become tractable on graphs of bounded treewidth. For a survey of this
phenomenon, known as _fixed-parameter tractability_ , see [6]. Our interest in
treewidth, however, is mainly in its role as a density parameter, in
particular for Theorem 1.6.

Treewidth, as a density parameter, is weaker than vertex expansion, in the
sense that a high vertex expansion implies a high treewidth, but not vice
versa. This is easy to see in the following corollary to Lemma F.6:

######  Corollary F.7.

If the vertex expansion of a family of graphs $G(N)$ on $N$ vertices is at
least $h_{v}(N),$ then the treewidth $t(N)$ of the family is $\Omega(N\cdot
h_{v}(N))$.

######  Proof F.8.

Suppose $G(N)$ has vertex expansion at least $h_{v}(N)$. Then every balanced
separator $X$ is of size at least

$|X|\geq h_{v}(N)\cdot N/3,$

by the definition of a balanced separator and the definition of vertex
expansion.

In this section we prove Theorem 1.6. See 1.6

######  Proof F.9.

We will show that $F_{n}$ has a large induced subgraph with large expansion,
which will imply large treewidth. Partition the points of the $n\times n$ grid
into $n$ grids of size $\sqrt{n}\times\sqrt{n}$. (If $n$ is not a perfect
square, we can take $\sqrt{\lfloor{n}\rfloor}$.) That is, fill in a partial
triangulation as follows: let each point in the grid have coordinates $(i,j)$,
where $1\leq i\leq n$ and $1\leq j\leq n$. Fill in all vertical edges
connecting two consecutive points with the same $j$ coordinate whenever
$j\equiv 0\pmod{\sqrt{n}}$ or $j\equiv 1\pmod{\sqrt{n}}$, and fill in all
horizontal edges connecting two consecutive points with the same $i$
coordinate whenever $i\equiv 0\pmod{\sqrt{n}}$ or $i\equiv 1\pmod{\sqrt{n}}$.

Fill in also all unit horizontal and unit vertical edges connecting vertices
in adjacent $\sqrt{n}\times\sqrt{n}$ sub-grids, and fill in all unit diagonals
with negative slope inside the resulting squares. See Figure 10, center. (The
choice of these edges and diagonals to fill in between subgrids is arbitrary,
but must be consistent.)

Now consider the subgraph $H_{n}$ of $F_{n}$ induced by restricting $V(F_{n})$
to the triangulations that extend this partial triangulation. That is, the
vertices of $H_{n}$ are the triangulations that consist of separately
triangulating each of the $\sqrt{n}\times\sqrt{n}$ grids. $H_{n}$ is the
Cartesian product of $n$ graphs that are each isomorphic to $F_{\sqrt{n}}$.
See Figure 10, right, for an example of such a triangulation.

Assuming the smallest possible expansion for a graph on $g(\sqrt{n})$
vertices, $F_{\sqrt{n}}$ graph has expansion $\Omega(1/g(\sqrt{n}))$. The
degree of $F_{n}$ is $O(n^{2})$. Now, by Lemma 2.15, $H_{n}$ has expansion
$\Omega(1/g(\sqrt{n}))$.

Therefore, by Corollary F.7, $H_{n}$ has treewidth
$\Omega(g(n)/(n^{2}g(\sqrt{n})))$.

Now, by Lemma F.3, $H_{n}$ has treewidth

$\Omega(g(n)/(n^{2}g(\sqrt{n})))=\Omega(2^{c\cdot n^{2}-cn-2\log
n})=\Omega(2^{cn^{2}(1-o(1))})=\Omega(N^{1-o(1)}),$

proving the theorem.

##  Appendix G Missing proofs from previous sections

###  G.1 Missing details from $k$-angulation flip walk mixing proofs

See 2.14

######  Proof G.1.

$\mathcal{C}^{*}(T)$ and $\mathcal{C}^{*}(T^{\prime})$ are Cartesian products
of the form $\mathcal{C}^{*}(T)=K_{i}\Box K_{j+k}$ and $T^{\prime}=K_{i+j}\Box
K_{k}$, where $|\mathcal{E}^{*}(T,T^{\prime})|=K_{i}\Box K_{j}\Box K_{k}$.
Therefore, $|\mathcal{C}^{*}(T)|=C_{i-1}C_{j+k-1}$,
$|\mathcal{C}^{*}(T^{\prime})|=C_{i+j-1}C_{k-1}$, and
$|\mathcal{E}^{*}(T,T^{\prime})|=C_{i-1}C_{j-1}C_{k-1}$. Thus we have

$\frac{|\mathcal{C}^{*}(T)||\mathcal{C}^{*}(T^{\prime})|}{|\mathcal{E}^{*}(T,T^{\prime})|C_{n-1}}\leq\frac{C_{j+k-1}C_{i+j-1}}{C_{j-1}C_{n-1}}.$

This ratio increases as $j$ increases, for any fixed $i$ (similarly, for any
fixed $k$). This is because, if $i$ is fixed, maximizing the ratio is
equivalent to maximizing

$\frac{C_{i+j-1}}{C_{j-1}}.$

It suffices to show that $C_{i+j-1}/C_{j-1}$ increases whenever $j$ increases
by one, i.e.

$\frac{C_{i+j}/C_{j}}{C_{i+j-1}/C_{j-1}}>1.$

I.e., it suffices to show that

$\frac{C_{i+j}}{C_{i+j-1}}>\frac{C_{j}}{C_{j-1}},$

i.e.

$\frac{i+j}{i+j+1}\frac{(2(i+j))!(i+j-1)!^{2}}{(2(i+j-1))!(i+j)!^{2}}>\frac{j}{j+1}\frac{(2j)!(j-1)!^{2}}{(2(j-1))!j!^{2}},$

i.e.

$\frac{2(i+j)-1}{i+j+1}>\frac{2j-1}{j+1}.$

The latter inequality clearly holds for all $i\geq 1$.

Therefore, the ratio in the lemma statement is maximized when $j$ is
maximized, i.e. $j=n-2$ and $i=k=1$. Thus we have

$\frac{|\mathcal{C}^{*}(T)||\mathcal{C}^{*}(T^{\prime})|}{|\mathcal{E}^{*}(T,T^{\prime})|C_{n-1}}\leq\frac{C_{n-2}C_{n-2}}{C_{n-3}C_{n-1}}.$

It is immediate from Definition 2.12 that $C_{n-1}/C_{n-2}\geq
C_{n-2}/C_{n-3}$, so this ratio is at most one, and the claim follows.

See A.1

######  Proof G.2.

Let $g$ and $h$ be as stated; we construct $f$ as follows:

  1. 1.

Within each copy of $H$ in $J$, construct the flow internally according to
$h$. Similarly, use $g$ internal to each $G$ copy for each pair of vertices
within the $G$ copy.

  2. 2.

Order the copies of $H$ arbitrarily $H_{1},\dots,H_{|V(G)|}$. For each pair of
$H$ copies $H_{r}$ and $H_{s}$, $s<r$, and for each vertex $h_{r}\in
H_{r},h_{s}\in H_{s}$, let the flow from $h_{r}$ to $h_{s}$ go through (i) the
$h$ flow in $H_{r}$ from $h_{r}$ to the counterpart vertex $u\in H_{r}$ of
$h_{s}$, then through (ii) the $g$ flow that goes from $u$ to $h_{s}$ (in the
$G$ copy that $h_{s}$ and $u$ both belong to).

Part 1 generates no additional flow. Part 2 generates at most $|V(H)|$ extra
flow through each existing $g$ flow, and at most $|V(G)|$ extra flow through
each existing $h$ flow. This results in scaling the amount of $g$ flow using
any given edge in a $G$ copy by a factor of $|V(H)|$—while replacing the
$\frac{1}{|V(G)|}$ term in the congestion definition by
$\frac{1}{|V(J)|}=\frac{1}{|V(G)||V(H)|}$—and similarly scaling the amount of
$h$ flow using an edge in an $H$ copy by $|V(G)|$. The result follows.

## References

  * [1] Nima Anari, Kuikui Liu, and Shayan Oveis Gharan.  Spectral independence in high-dimensional expanders and applications to the hardcore model.  In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 1319–1330, 2020.  doi:10.1109/FOCS46700.2020.00125.
  * [2] Nima Anari, Kuikui Liu, Shayan Oveis Gharan, and Cynthia Vinzant.  Log-concave polynomials II: High-dimensional walks and an FPRAS for counting bases of a matroid.  In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC 2019), New York, NY, USA, 2019. Association for Computing Machinery.  doi:10.1145/3313276.3316385.
  * [3] Nima Anari, Shayan Oveis Gharan, and Cynthia Vinzant.  Log-concave polynomials, entropy, and a deterministic approximation algorithm for counting bases of matroids.  In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 35–46, 2018.  doi:10.1109/FOCS.2018.00013.
  * [4] Emile E. Anclin.  An upper bound for the number of planar lattice triangulations.  Journal of Combinatorial Theory, Series A, 103(2):383 – 386, 2003\.  URL: http://www.sciencedirect.com/science/article/pii/S0097316503000979, doi:10.1016/S0097-3165(03)00097-9.
  * [5] Pinaki Banerjee.  Scattering amplitudes from positive geometries.  In Prafulla Kumar Behera, Vipin Bhatnagar, Prashant Shukla, and Rahul Sinha, editors, XXIII DAE High Energy Physics Symposium, pages 421–427, Singapore, 2021. Springer Singapore.
  * [6] Hans L. Bodlaender.  Fixed-parameter tractability of treewidth and pathwidth.  volume 7370 of Lecture Notes in Computer Science, pages 196–227. Springer, 2012.  doi:10.1007/978-3-642-30891-8_12.
  * [7] Pietro Caputo, Fabio Martinelli, Alistair Sinclair, and Alexandre Stauffer.  Dynamics of lattice triangulations on thin rectangles.  Electronic Journal of Probability, 21, 05 2015.  doi:10.1214/16-EJP4321.
  * [8] Pietro Caputo, Fabio Martinelli, Alistair Sinclair, and Alexandre Stauffer.  Random lattice triangulations: structure and algorithms.  Annals of Applied Probability, 25:1650–1685, 2015.
  * [9] Alessandra Caraceni and Alexandre Stauffer.  Polynomial mixing time of edge flips on quadrangulations.  Probability Theory and Related Fields, 176(1):35–76, Feb 2020.  doi:10.1007/s00440-019-00913-5.
  * [10] Zongchen Chen, Andreas Galanis, Daniel Štefankovič, and Eric Vigoda.  Rapid mixing for colorings via spectral independence.  In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1548–1557.  arXiv:https://epubs.siam.org/doi/pdf/10.1137/1.9781611976465.94, doi:10.1137/1.9781611976465.94.
  * [11] Zongchen Chen, Kuikui Liu, and Eric Vigoda.  Rapid mixing of Glauber dynamics up to uniqueness via contraction, 2020\.  arXiv:2004.09083.
  * [12] Zongchen Chen, Kuikui Liu, and Eric Vigoda.  Optimal mixing of glauber dynamics: Entropy factorization via high-dimensional expansion.  In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 1537–1550, 2021.
  * [13] Karel Culik II and Derick Wood.  A note on some tree similarity measures.  Information Processing Letters, 15(1):39–42, 1982.
  * [14] Christopher M De Sa, Ce Zhang, Kunle Olukotun, and Christopher Ré.  Rapidly Mixing Gibbs Sampling for a Class of Factor Graphs Using Hierarchy Width.  In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 28. Curran Associates, Inc., 2015.  URL: https://proceedings.neurips.cc/paper/2015/file/b29eed44276144e4e8103a661f9a78b7-Paper.pdf.
  * [15] Persi Diaconis and Laurent Saloff-Coste.  Comparison theorems for reversible markov chains.  The Annals of Applied Probability, 3(3):696–730, 1993.
  * [16] Persi Diaconis and Daniel Stroock.  Geometric Bounds for Eigenvalues of Markov Chains.  The Annals of Applied Probability, 1(1):36 – 61, 1991.  doi:10.1214/aoap/1177005980.
  * [17] Martin Dyer, Leslie Ann Goldberg, and Mark Jerrum.  Matrix norms and rapid mixing for spin systems.  The Annals of Applied Probability, 19(1):71–107, 2021/10/28/ 2009\.  Full publication date: Feb., 2009.  URL: http://www.jstor.org/stable/30243572.
  * [18] David Eppstein and Daniel Frishberg.  Rapid mixing of the hardcore Glauber dynamics and other Markov chains in bounded-treewidth graphs.  2021\.  arXiv:2111.03898, doi:10.48550/arXiv.2111.03898.
  * [19] Jeff Erickson.  Computational topology: Treewidth.  Lecture Notes, 2009.  URL: http://jeffe.cs.illinois.edu/teaching/comptop/2009/notes/treewidth.pdf.
  * [20] F. Graham and P. Tetali.  Isoperimetric inequalities for cartesian products of graphs.  Comb. Probab. Comput., 7:141–148, 1998.
  * [21] Marc Heinrich.  Glauber dynamics for colourings of chordal graphs and graphs of bounded treewidth, 2020.  URL: https://arxiv.org/abs/2010.16158, arXiv:2010.16158.
  * [22] Peter J. Hilton and Jean J. Pedersen.  Catalan numbers, their generalization, and their uses.  The Mathematical Intelligencer, 13:64–75, 1991.
  * [23] Mrunmay Jagadale and Alok Laddha.  Towards positive geometry of multi scalar field amplitudes : Accordiohedron and effective field theory.  2021\.  URL: https://arxiv.org/abs/2104.04915.
  * [24] Mark Jerrum and Alistair Sinclair.  Conductance and the rapid mixing property for Markov chains: The approximation of permanent resolved.  In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, STOC ’88, 1988.  doi:10.1145/62212.62234.
  * [25] Mark Jerrum, Jung-Bae Son, Prasad Tetali, and Eric Vigoda.  Elementary bounds on Poincaré and log-Sobolev constants for decomposable Markov chains.  The Annals of Applied Probability, 14(4):1741–1765, 2004.  URL: http://www.jstor.org/stable/4140446.
  * [26] V. Kaibel and G. Ziegler.  Counting lattice triangulations.  arXiv: Combinatorics, 2002.
  * [27] Volker Kaibel.  On the expansion of graphs of 0/1-polytopes.  In The Sharpest Cut: The Impact of Manfred Padberg and His Work, pages 199–216. SIAM, 2004.
  * [28] Tali Kaufman and Izhar Oppenheim.  High order random walks: Beyond spectral gap.  Combinatorica, 40(2):245–281, 2020.
  * [29] David A. Klarner.  Correspondences between plane trees and binary sequences.  Journal of Combinatorial Theory, 9(4):401–411, 1970.  URL: https://www.sciencedirect.com/science/article/pii/S002198007080093X, doi:10.1016/S0021-9800(70)80093-X.
  * [30] Vedat Levi Alev and Lap Chi Lau.  Improved analysis of higher order random walks and applications.  arXiv e-prints, pages arXiv–2001, 2020.
  * [31] David A Levin, Yuval Peres, and Elizabeth Wilmer.  Markov chains and mixing times, volume 107.  American Mathematical Soc., 2017.
  * [32] J. Loday.  The multiple facets of the associahedron.  In Proc. 2005 Academy Coll. Series, 2005.
  * [33] László Lovász and Ravi Kannan.  Faster mixing via average conductance.  In Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, STOC ’99, page 282–287, New York, NY, USA, 1999. Association for Computing Machinery.  doi:10.1145/301250.301317.
  * [34] Lisa McShine and P. Tetali.  On the mixing time of the triangulation walk and other catalan structures.  In Randomization Methods in Algorithm Design, 1997.
  * [35] Milena Mihail and Umesh Vazirani.  On the expansion of 0-1 polytopes.  Journal of Combinatorial Theory, Series B, 1989.
  * [36] Michael Molloy, Bruce Reed, and William Steiger.  On the mixing rate of the triangulation walk.  In Randomization Methods in Algorithm Design, 1997.
  * [37] Atsuhiro Nakamoto, Gen Kawatani, Naoki Matsumoto, and Jorge Urrutia.  Geometric quadrangulations of a polygon.  Electronic Notes in Discrete Mathematics, 68:59–64, 2018.  Discrete Mathematics Days 2018.  doi:10.1016/j.endm.2018.06.011.
  * [38] Prashanth Raman.  The positive geometry for $\phi$p interactions.  Journal of High Energy Physics, 2019(10):271, Oct 2019.  doi:10.1007/JHEP10(2019)271.
  * [39] Dana Randall and Prasad Tetali.  Analyzing glauber dynamics by comparison of markov chains.  In Latin American Symposium on Theoretical Informatics, pages 292–304. Springer, 1998.
  * [40] Herbert E. Robbins.  A remark on stirling’s formula.  American Mathematical Monthly, 62:402–405, 1955.
  * [41] Alistair Sinclair.  Improved bounds for mixing rates of Markov chains and multicommodity flow.  Combinatorics, Probability and Computing, 1(4):351–370, 1992.  doi:10.1017/S0963548300000390.
  * [42] Daniel D Sleator, Robert E Tarjan, and William P Thurston.  Rotation distance, triangulations, and hyperbolic geometry.  Journal of the American Mathematical Society, 1(3):647–681, 1988\.
  * [43] Alexandre Stauffer.  A Lyapunov function for Glauber dynamics on lattice triangulations.  Probability Theory and Related Fields, 169:469–521, 2015.


#  Comment on “Statistical Modeling: The Two Cultures”
by Leo Breiman

Matteo Bonvini, Alan Mishler, Edward H. Kennedy

Department of Statistics & Data Science
Carnegie Mellon University

{ mbonvini, amishler, edward } @stat.cmu.edu
MB and AM contributed equally.

###### Abstract

Motivated by Breiman’s rousing 2001 paper on the “two cultures” in statistics,
we consider the role that different modeling approaches play in causal
inference. We discuss the relationship between model complexity and causal
(mis)interpretation, the relative merits of plug-in versus targeted
estimation, issues that arise in tuning flexible estimators of causal effects,
and some outstanding cultural divisions in causal inference.

##  1 Introduction

Breiman (2001a) describes two distinct data analysis cultures that animated
the statistical community at the turn of the 21st century. One culture,
popular among statisticians, starts with an explicit probabilistic model of
the data generating process (DGP) and uses this model to answer questions of
interest. In Breiman’s view, such probabilistic models are frequently
misleading; furthermore, he argues that this approach is incapable of tackling
modern challenges involving large, complex datasets, with potentially more
variables than observations.

Breiman argues that such challenges can only be effectively solved by
embracing a purely algorithmic approach. Analysts in this culture choose a
method with the highest predictive accuracy, regardless of whether it
corresponds to some interpretable, parsimonious model for the DGP. They then
extract whatever information they can from the model post-hoc.

In this commentary, we discuss how Breiman’s points relate to problems in
causal inference. Understanding the effect of X on Y is fundamentally about
predicting what happens if the distribution X is artificially manipulated in
some way, which results in an extra layer of complexity compared to standard
prediction problems.

We first discuss how causal misinterpretations can arise regardless of whether
the data generating process is explicitly specified or not. Next, we highlight
two different approaches to causal parameter estimation – plug-in vs. targeted
estimation – that are loosely analogous to Breiman’s two cultures. We then
expand on the targeted approach and discuss how optimal estimation of target
parameters can require undersmoothing the nuisance parameter estimates. This
is a setting in which simply optimizing for predictive accuracy in the
nuisance parameters may lead to suboptimal performance in the overall
estimator. Finally, motivated by Breiman, we briefly note several current
cultural divisions in causal inference.

##  2 Model Complexity and Causal (Mis)interpretations

Breiman describes explicit models of the DGP as being motivated by a desire
for interpretability. One of his chief complaints is that it is easy to
misinterpret such models. If the model does not describe nature well, then
conclusions drawn from its parameter estimates may be spurious or misleading.
Implicit in Breiman’s critique is the fact that misinterpretations of
parameters often have a causal flavor. As Breiman alludes to, in many fields,
it has historically been common to run a linear or generalized linear
regression and then interpret the coefficients as representing causal effects,
without consideration of whether this interpretation is justified. In
Breiman’s view, algorithmic modeling approaches sidestep this pitfall. By not
specifying a DGP, these methods avoid presenting users with parameters which
they may be tempted to misinterpret.

We argue, however, that explicit models of the DGP are not necessarily
intrinsically misleading, and that nothing in the algorithmic approach
intrinsically protects against misinterpretation. Here it seems useful to
distinguish several senses of the word “model.” In one usage, common among
statisticians, “model” refers to a collection of probability distributions,
one of which is generally assumed to represent the true data generating
process. In a second usage, “model” refers to an algorithm that maps a
dataset—the training data—to a function which itself maps from the covariate
or feature space to the output space. That is, a model is a procedure used to
construct a predictor from data. In a third, closely related usage, “model”
refers to the output of this procedure in a particular instance, i.e. a fixed
predictor induced by a particular training dataset.

We note that the use of a model in the second or third sense need not imply a
commitment to a model in the first sense. Simple parametric predictors may be
used without assuming that the regression function follows an analogous
parametric form. Least squares linear regression, for example, can be
understood as estimating the best linear approximation to the true regression
function, regardless of the shape of that function (White, 1982; Buja et al.,
2019a, b). The resulting coefficients represent predictive relationships among
the variables, no matter how they are causally related. The coefficients do
not need to be mapped onto any particular process in nature.

On the other side, there is a large and growing literature dedicated to
rendering complex algorithmic predictors legible. This work falls under the
heading of explainable, interpretable, or transparent machine learning. These
methods involve constructing or extracting simple quantities that describe the
behavior of a complex model. There are now many such methods available
(Guidotti et al., 2018; Arya et al., 2019). Some involve approximating the
complex model by simple global or local models or decision rules; others
quantify the "contribution" of each feature to predictions in order to assign
importance weights to each of the features. Breiman’s own feature importance
method for random forests (Breiman, 2001b) is an example of such a method, and
perhaps he would be pleased that there has been so much work in this area
since.

While the proliferation of methods for interpretable machine learning speaks
to the desire users have to gain insight into the behavior of complex models,
the outputs of many of these methods are susceptible to exactly the same types
of misinterpretations as the parameter estimates from simpler models. Indeed,
many approximation methods involve simple parametric models, such as linear
models, and produce precisely the same types of estimates (Ribeiro et al.,
2016). Feature importance methods yield weights for each feature, which are
superficially similar to the coefficient estimates from a linear model. Though
we have not attempted to verify this, we suspect that it is common to read
feature importance values as indicating relative causal importance, even when
this interpretation is not licensed.

It is simple to see that the method used to model the data is orthogonal to
whether or not causal inference assumptions are satisfied. Consider a causal
graph $X\leftarrow Y$, where $Y$ causes $X$, and suppose we construct a model
that predicts $Y$ from $X$. Whatever quantities we use to summarize the model,
whether they are parameter estimates or feature importance weights or other
outputs from interpretable machine learning methods, it may be tempting to
read these quantities as representing the causal influence of $X$ on $Y$. This
interpretation will always be invalid, because $X$ has no causal effect on
$Y$.

In short, it is always possible to misread causality into a predictive model,
regardless of whether the model is parametric or nonparametric, simple or
complex. The solution, presumably, is to foreground the assumptions required
for causal inference, rather than relying on model opacity to protect us from
ourselves. After all, in many scientific settings, causal inference is the
goal, whether this is expressed explicitly or not. A user who is determined to
find quantities to which causal conclusions can be attached will have many
ways of doing so, whatever modeling technique they use.

##  3 Plug-in Versus Targeted Estimation

Under appropriate causal identification assumptions, there are a variety of
ways to proceed with estimation. The two modeling approaches that Breiman
describes are roughly analogous to two distinct approaches to causal parameter
estimation, which differ in whether they prioritize modeling the entire DGP or
just estimating a particular parameter well. In the first approach, one starts
by developing a generative model for the entire set of observed data, and then
plugs in estimates from this model to answer any generic scientific question
of interest. Often finite-dimensional parametric models are used, in which
case the estimates takes the form of particular coefficients embedded in the
model (or combinations thereof). Examples of this kind of approach include the
parametric g-formula (Taubman et al., 2009; Keil et al., 2014) as well as
other classical approaches relying on coefficients in logistic regression or
Cox models. Matching can also be viewed as a form of plug-in estimator, based
on nearest-neighbor-type regression predictions (Abadie and Imbens, 2006).
There are some advantages to this kind of approach, including its simplicity
and the relative interpretability of the estimators (i.e., one simply takes
the estimand of interest, and plugs in estimates from the model for any
unknown quantities).

However, there are some important disadvantages to the above plug-in approach.
First, simple parametric models induce the risk of substantial bias due to
model misspecification. Alternatively, if one uses more flexible methods, then
inference is no longer straightforward (e.g., the bootstrap may not provide
valid standard errors), and in general the resulting estimator will not be
efficient in a nonparametric model (i.e., there will exist different
estimators with smaller mean squared error, despite not making stronger
assumptions).

These limitations motivate a second approach, where the estimation procedure
is tailored to the specific scientific question and estimand of interest. For
many estimands, such as average treatment effects of discrete treatments, this
tailoring can be framed in terms of semi/nonparametric efficiency theory
(Pfanzagl, 1982; Bickel et al., 1993; van der Laan and Robins, 2003; Tsiatis,
2006; Kennedy, 2016). Namely, for a given pathwise differentiable estimand
(i.e., functional or parameter, for example the average treatment effect
identified under causal assumptions such as no unmeasured confounding), one
can derive the efficient influence function, which yields a benchmark for
efficient estimation: no estimator can have mean squared error smaller than
the variance of the efficient influence function divided by sample size, in a
local asymptotic minimax sense (van der Vaart, 2002). The efficient influence
function is also the crucial ingredient in standard recipes for constructing
efficient estimators, for example based on one-step bias correction,
estimating equations, or targeted maximum likelihood.

Although in some cases the estimators themselves may not be as intuitive as
simple plug-ins, methods that are tailored to specific estimands of interest
come with some important advantages. First, they often force analysts and
investigators to think hard about the scientific question in formulating the
estimand of interest, rather than resorting right away to modeling and
outputting coefficients. More concretely, though, estimators based on
influence functions (now often called doubly robust or double machine learning
methods) can be optimally efficient in nonparametric models, achieving fast
parametric $1/n$-type mean squared errors even in large nonparametric models,
where components of the underlying data generating process can only be
estimated at slower rates. In addition to the references mentioned above, we
also refer to a fast-growing recent literature for more details (van der Laan
and Rose, 2011; Chernozhukov et al., 2018; Robins et al., 2017).

##  4 Tuning in Targeted Estimation

One of Breiman’s core arguments is that methods of data analysis should be
chosen based on their out-of-sample prediction performance. In standard
prediction problems, this can be accomplished, for instance, via cross-
validation. In causal inference, however, the target parameters are often
complex functionals that depend on several nuisance functions. Suppose these
functions are estimated using an algorithm that depends on a tuning parameter
$k$: how should $k$ be chosen?

One could take the usual route and choose $k$ based on cross-validation in a
way that is optimal for estimating the nuisance functions, say in terms of
mean-square-error. Although this choice can still lead to nonparametric
efficient estimators, it is not always optimal for estimating the functional
itself, which is the ultimate target of inference. For example, consider
estimating the expected density $\chi(f)=\int f^{2}(x)dx$, which can be
estimated at root-$n$ rates even in a nonparametric model, e.g., under
smoothness assumptions (Bickel and Ritov, 1988). An intuitive estimator is
$n^{-1}\sum_{i=1}^{n}\widehat{f}(X_{i})$, where, for convenience, we may think
of $\widehat{f}$ as a minimax-optimal estimator of $f$ computed from a
separate independent sample. A simple calculation shows that the estimation
error contains the term $\int\\{\widehat{f}(x)-f(x)\\}f(x)dx$. In a
nonparametric model, the best convergence rate for $\widehat{f}$ is always
slower than root-$n$, which means that this procedure will never result in a
root-$n$ consistent estimator unless some modifications are introduced.

###  4.1 Influence function-based estimators

To achieve faster convergence rates in nonparametric models, plug-in
estimators of "smooth" functionals can be "corrected" by adding averages of
estimates of their influence function(s) (Bickel et al., 1993; van der Vaart,
2002; Tsiatis, 2006; Kennedy, 2016; Chernozhukov et al., 2018). Suppose
$\chi(\mathbb{P})\in\mathbb{R}$ is smooth enough to satisfy a von Mises
expansion of the form

$\displaystyle\chi(\widehat{\mathbb{P}})-\chi(\mathbb{P})=-\int\phi(o;\widehat{\mathbb{P}})d\mathbb{P}(o)+R_{2}(\mathbb{P},\widehat{\mathbb{P}})$

for a second order remainder term $R_{2}$ and a (first order) influence
function $\phi(O;\mathbb{P})$. This expansion, which is the functional
analogue of a Taylor expansion, suggests a "corrected estimator"

$\displaystyle\widehat{\chi}(\widehat{\mathbb{P}})=\chi(\widehat{\mathbb{P}})+\frac{1}{n}\sum_{i=1}^{n}\phi(O_{i};\widehat{\mathbb{P}})$

where $\chi(\widehat{\mathbb{P}})$ is the plug-in estimator. We will refer to
estimators based on first order influence functions simply as first order
estimators, though they are also called doubly robust, targeted, or double
machine learning estimators. For instance, for
$\chi(\mathbb{P})=\mathbb{E}\\{\mathbb{E}(Y\mid A=1,X)-\mathbb{E}(Y\mid
A=0,X)\\}$, i.e. the average treatment effect under no-unmeasured-confounding,
$\widehat{\chi}(\widehat{\mathbb{P}})$ takes the form of the celebrated
doubly-robust estimator (Robins and Rotnitzky, 1995; Robins and Wang, 2000;
van der Laan and Robins, 2003):

$\displaystyle\widehat{\chi}(\widehat{\mathbb{P}})=\sum_{i=1}^{n}\left[\frac{A-\widehat{\pi}(X_{i})}{\widehat{\pi}(X_{i})\\{1-\widehat{\pi}(X_{i})\\}}\\{Y_{i}-\widehat{\mu}_{A}(X_{i})\\}+\widehat{\mu}_{1}(X_{i})-\widehat{\mu}_{0}(X_{i})\right]$

where $\mu_{a}(x)=\mathbb{E}(Y\mid A=a,X=x)$ and $\pi(x)=\mathbb{P}(A=1\mid
X=x)$ are the outcome regression and propensity score, respectively.

The key advantage of correcting a plug-in estimator by subtracting off an
estimate of the functional’s first order influence function term is that the
remainder error $R_{2}$ is second order. For instance, in the case of the
average treatment effect, we have

$\displaystyle
R_{2}(\mathbb{P},\widehat{\mathbb{P}})=-\int\\{\widehat{\pi}(x)-\pi(x)\\}\left\\{\frac{\widehat{\mu}_{1}(x)-\mu_{1}(x)}{\widehat{\pi}(x)}-\frac{\widehat{\mu}_{0}(x)-\mu_{0}(x)}{1-\widehat{\pi}(x)}\right\\}f(x)dx$

where $f(x)$ is the density of $X$. If $\widehat{\pi}(x)$ is bounded away from
zero and one, an application of Cauchy-Schwarz yields that

$\displaystyle|R_{2}(\mathbb{P},\widehat{\mathbb{P}})|\leq
C\sqrt{\int\\{\widehat{\pi}(x)-\pi(x)\\}^{2}f(x)dx}\times\max_{a}\sqrt{\int\\{\widehat{\mu}_{a}(x)-\mu_{a}(x)\\}^{2}f(x)dx}$

for some constant $C$. Therefore, $R_{2}(\mathbb{P},\widehat{\mathbb{P}})$ can
be $o_{\mathbb{P}}(n^{-1/2})$ even if the $L_{2}$ error in estimating the
nuisance functions is $o_{\mathbb{P}}(n^{-1/4})$, for example. In this case,
under mild conditions and provided that the nuisance functions are estimated
from an independent sample, $\widehat{\chi}(\widehat{\mathbb{P}})$ would be
$n^{-1/2}$-consistent and semiparametric efficient.

Achieving $n^{-1/4}$ rates for the nuisance functions, and as a result,
$n^{1/2}$-consistency for the functional, generally requires that the classes
in which the nuisance parameters live are sufficiently regular. For example, a
$d$-dimensional regression would need to live in a $\alpha$-Holder class with
$\alpha>d/2$ in order for a minimax optimal estimator to be
$n^{-1/4}$-consistent (Tsybakov, 2009). Thus, if $\pi(x)$ is $\alpha$-smooth
and $\mu_{a}(x)$ is $\beta$-smooth, $R_{2}(\mathbb{P},\widehat{\mathbb{P}})$
is $o_{\mathbb{P}}(n^{-1/2})$ if $\alpha+\beta>d$. Interestingly, there are
function classes that admit estimation at rates that do not depend
exponentially on $d$. For instance, functions that are cadlag and have bounded
variation norm can be estimated with error $o_{\mathbb{P}}(n^{-1/4})$ using
the Highly Adaptive Lasso (van der Laan, 2017). Similarly, certain neural
network classes allow $n^{-1/4}$-consistency (up to log factors) irrespective
of the dimension of the covariates (Györfi et al., 2002).

Corrected estimators based on first-order influence functions represent a
substantial improvement over plug-ins because they allow for efficient
estimation even in (not overly complex) nonparametric models. Furthermore,
they are straightforward to implement, as they do not require any extra tuning
beyond estimating the nuisance functions. One may then wonder: can first-order
corrected estimators be further improved? The answer is yes, under certain
conditions, but the available estimators are not as easily implementable in
practice.

###  4.2 Higher-order & double sample-split estimators

A natural way to improve upon first-order estimators is to correct for
additional terms in the von-Mises expansion by estimating and subtracting off
higher order influence function terms. However, typical functionals do not
possess influence functions of order $m\geq 2$, and exact corrections are not
possible. Despite this, estimators based on approximate higher order influence
functions (HOIFs) can improve upon first-order estimators (Robins et al.,
2008, 2009a, 2017). At a high level, approximate HOIFs of a functional
$\chi(\mathbb{P})$ can be derived as exact HOIFs of a "smoothed" functional
$\widetilde{\chi}(\mathbb{P})$ that possesses influence functions of all
orders. One can then optimally tune the approximation bias
$\chi(\mathbb{P})-\widetilde{\chi}(\mathbb{P})$ and the error in estimating
$\widetilde{\chi}(\mathbb{P})$. Remarkably, higher-order estimators of the
average treatment effect and the expected conditional covariance are root-$n$
consistent if $\alpha+\beta>d/2$, which is a necessary condition for root-$n$
consistency in the Holder setup (Robins et al., 2009b). Further, under
smoothness constraints on $f$, these estimators can be minimax-optimal even
outside the root-$n$ regime, i.e. when $\alpha+\beta\leq d/2$ (Robins et al.,
2008, 2017). In settings where the covariate density $f$ is non-smooth,
minimax estimation is largely still an open problem, even for relatively
simple causal effect functionals. Finally, HOIFs are higher order U-statistics
involving kernels of projections onto suitable finite-dimensional subspaces.
To the best of our knowledge, there is currently no data-driven way to choose
the orders of the U-statistics and the projections, which can hinder the
applicability of HOIF-based estimators in practice.

In order to construct simpler estimators than the ones based on HOIFs, Newey
and Robins (2018) have proposed using particular forms of sample splitting
with the intent of estimating different components of the functional with
separate, independent subsamples. For example, letting $a(X)=\mathbb{E}(Z\mid
X)$ and $\mu(X)=\mathbb{E}(Y\mid X)$, a first-order estimator of the expected
conditional covariance $\chi(\mathbb{P})=\mathbb{E}\\{\text{cov}(Y,Z\mid
X)\\}=\mathbb{E}[Z\\{Y-\mu(X)\\}]$ is

$\displaystyle\widehat{\chi}(\widehat{\mathbb{P}})=\frac{1}{n}\sum_{i=1}^{n}\\{Z_{i}-\widehat{a}(X_{i})\\}\\{Y_{i}-\widehat{\mu}(X_{i})\\}$

Newey and Robins (2018) show that if $a$ and $\mu$ are estimated with suitable
series estimators constructed from separate independent samples and the
average is over a third sample independent of the other two, then
$\widehat{\chi}(\widehat{\mathbb{P}})$ will be root-$n$ consistent under the
minimal condition $\alpha+\beta>d/2$ when $a$ is $\alpha$-smooth and $\mu$ is
$\beta$-smooth. For other functionals, such as the average treatment effect,
estimators based on HOIF remain the only ones known to achieve root-$n$
consistency under the minimal condition. Recently, Kennedy (2020) has extended
the approach of Newey and Robins (2018) and obtained fast rates for estimating
the conditional average treatment effect, which is a non-pathwise
differentiable parameter that does not satisfy the classic von Mises
expansion.

Despite being simpler to construct than the HOIF estimators, exploiting the
advantages of these estimators based on plug-ins or first-order estimators
that use double sample splitting does appear to require choosing the tuning
parameters for the nuisance functions in a way that is optimal for estimating
the functional, rather than just the nuisance functions. Therefore, just like
HOIF-based estimators, practical implementation poses some challenges. Often,
the optimal choice of the tuning parameters amounts to undersmoothing when
estimating the nuisance functions. Undersmoothing has played an important role
in functional estimation (Goldstein and Messer, 1992; Hahn, 1998; Hirano et
al., 2003; van der Laan et al., 2019). However, only the optimal order
(relative to the sample size) of the tuning parameters is generally known,
leaving the constants unspecified. In finite samples, choosing different
constants could result in widely different estimates, and thus finding the
right amount of undersmoothing in applications is difficult. Finding a data-
driven method for undersmoothing remains largely an open problem. We refer to
Chapter 5 in Wasserman (2006) for a discussion on the practical challenges of
undersmoothing, and to Cui and Tchetgen (2019) for a recent contribution that
could play an important role in tuning parameter selection for doubly robust
functionals.

Finally, the improvements over first-order estimators by either using HOIFs or
carefully choosing the tuning parameters and doing double sample splitting are
based on some structural assumptions. For instance, choosing the optimal order
of the HOIF and the nuisance tuning parameters generally requires knowledge of
the smoothness / sparsity of the nuisance functions (e.g. the order of the
Holder class). Remarkably, there are exceptions to this. For instance, Kennedy
(2020) (Theorem 3) constructs an estimator of the conditional average
treatment effect whose performance depends on two tuning parameters, one of
which is optimized by undersmoothing as much as possible. In practice, this
suggests one may then keep undersmoothing until numerical issues arise. When
the optimal amount of undersmoothing is hard to obtain in finite samples,
Lepski’s method (Lepski and Spokoiny, 1997), originally developed for
nonparametric regression problems, selects tuning parameters in a way that can
adapt to the unknown level of smoothness of the function that is estimated. A
variant of it has been used for estimating the expected value of a density by
Giné et al. (2008), and with second-order influence function estimators by Liu
et al. (2016). Many open problems remain.

##  5 Some Cultural Divisions in Causal Inference

In addition to the distinction between plug-in and targeted estimation, there
are a number of interesting cultural divisions that are unique to (or
especially prominent in) causal inference, which do not necessarily align with
Breiman’s contrast of data modeling versus algorithmic modeling. The
distinctions arise in the types of targets, the formalisms used to frame
assumptions and define estimands, and the techniques used for estimation. Some
of these cultural divisions are:

  * •

causal discovery versus estimation,

  * •

parametric versus nonparametric methods,

  * •

graphs versus potential outcomes,

  * •

explanation versus informing policy,

  * •

sensitivity analysis versus bounds (versus neither).

Although there is much recent work that aims to bridge many of these
divisions, one division remains particularly pronounced: whether the
scientific question is about discovery versus estimation. Causal discovery
(Spirtes et al., 2000) usually aims at questions like: “given some large set
of variables, how can we determine which have non-zero effects on others?”
This is essentially about learning the entire underlying causal structure,
e.g., in the form of a graph. In contrast, estimation problems typically focus
on one or a small number of exposures, and ask only what their effect is on
some outcome of particular interest, leaving unspecified much of the rest of
the causal structure (for example, specific relations among confounding
variables). Thus far these kinds of problems have been pursued quite
separately, with philosophy and machine learning communities taking the lead
on discovery, and with estimation pursued more in statistics and biostatistics
and epidemiology. However, we feel there could be big benefits to more cross-
disciplinary collaboration on these problems; for example, this could lead to
more focus on inference and error guarantees in discovery in nonparametric
models, or on using faithfulness assumptions to enlarge the kinds of questions
that are typically asked in the estimation world. For more details, we refer
to some excellent recent discussion by Cosma Shalizi of work by Kun Zhang at
the Online Causal Inference Seminar (link).

## References

##

  * Abadie and Imbens [2006] A. Abadie and G. W. Imbens.  Large sample properties of matching estimators for average treatment effects.  _Econometrica_ , 74(1):235–267, 2006.
  * Arya et al. [2019] V. Arya, R. K. E. Bellamy, P.-Y. Chen, A. Dhurandhar, M. Hind, S. C. Hoffman, S. Houde, Q. V. Liao, R. Luss, A. Mojsilovi?, S. Mourad, P. Pedemonte, R. Raghavendra, J. Richards, P. Sattigeri, K. Shanmugam, M. Singh, K. R. Varshney, D. Wei, and Y. Zhang.  One explanation does not fit all: A toolkit and taxonomy of AI explainability techniques.  _arxiv preprint arXiv:1909.03012_ , 2019.
  * Bickel and Ritov [1988] P. J. Bickel and Y. Ritov.  Estimating integrated squared density derivatives: sharp best order of convergence estimates.  _Sankhyā_ , pages 381–393, 1988.
  * Bickel et al. [1993] P. J. Bickel, C. A. Klaassen, Y. Ritov, and J. A. Wellner.  _Efficient and Adaptive Estimation for Semiparametric Models_.  Baltimore: Johns Hopkins University Press, 1993.
  * Breiman [2001a] L. Breiman.  Statistical modeling: The two cultures.  _Statistical Science_ , 16(3):199–231, 2001a.
  * Breiman [2001b] L. Breiman.  Random forests.  _Machine Learning_ , 45(1):5–32, 2001b.  doi: 10.1023/A:1010933404324.
  * Buja et al. [2019a] A. Buja, L. Brown, R. Berk, E. George, E. Pitkin, M. Traskin, K. Zhang, and L. Zhao.  Models as approximations I: Consequences illustrated with linear regression.  _Statistical Science_ , 34(4):523–544, 2019a.  doi: 10.1214/18-STS693.
  * Buja et al. [2019b] A. Buja, L. Brown, A. K. Kuchibhotla, R. Berk, E. George, and L. Zhao.  Models as approximations II: A model-free theory of parametric regression.  _Statistical Science_ , 34(4):545–565, 2019b.  doi: 10.1214/18-STS694.
  * Chernozhukov et al. [2018] V. Chernozhukov, D. Chetverikov, M. Demirer, E. Duflo, C. Hansen, W. Newey, and J. M. Robins.  Double/debiased machine learning for treatment and structural parameters.  _The Econometrics Journal_ , 21(1):C1–C68, 2018\.
  * Cui and Tchetgen [2019] Y. Cui and E. T. Tchetgen.  Selective machine learning of doubly robust functionals.  _arXiv preprint arXiv:1911.02029_ , 2019.
  * Giné et al. [2008] E. Giné, R. Nickl, et al.  A simple adaptive estimator of the integrated square of a density.  _Bernoulli_ , 14(1):47–61, 2008.
  * Goldstein and Messer [1992] L. Goldstein and K. Messer.  Optimal plug-in estimators for nonparametric functional estimation.  _The annals of statistics_ , pages 1306–1328, 1992.
  * Guidotti et al. [2018] R. Guidotti, A. Monreale, S. Ruggieri, F. Turini, F. Giannotti, and D. Pedreschi.  A survey of methods for explaining black box models.  _ACM Computing Surveys_ , 51(5):1–42, 2018\.  doi: 10.1145/3236009.
  * Györfi et al. [2002] L. Györfi, M. Kohler, A. Krzykaz, and H. Walk.  _A Distribution-Free Theory of Nonparametric Regression_.  Springer, 2002.
  * Hahn [1998] J. Hahn.  On the role of the propensity score in efficient semiparametric estimation of average treatment effects.  _Econometrica_ , 66(2):315–331, 1998.
  * Hirano et al. [2003] K. Hirano, G. W. Imbens, and G. Ridder.  Efficient estimation of average treatment effects using the estimated propensity score.  _Econometrica_ , 71(4):1161–1189, 2003.
  * Keil et al. [2014] A. P. Keil, J. K. Edwards, D. R. Richardson, A. I. Naimi, and S. R. Cole.  The parametric g-formula for time-to-event data: towards intuition with a worked example.  _Epidemiology (Cambridge, Mass.)_ , 25(6):889, 2014.
  * Kennedy [2016] E. H. Kennedy.  Semiparametric theory and empirical processes in causal inference.  _In: Statistical Causal Inferences and Their Applications in Public Health Research_ , pages 141–167, 2016.
  * Kennedy [2020] E. H. Kennedy.  Optimal doubly robust estimation of heterogeneous causal effects.  _arXiv preprint arXiv:2004.14497_ , 2020.
  * Lepski and Spokoiny [1997] O. V. Lepski and V. G. Spokoiny.  Optimal pointwise adaptive methods in nonparametric estimation.  _The Annals of Statistics_ , pages 2512–2546, 1997.
  * Liu et al. [2016] L. Liu, R. Mukherjee, J. Robins, and E. T. Tchetgen.  Adaptive estimation of nonparametric functionals.  _arXiv preprint arXiv:1608.01364_ , 2016.
  * Newey and Robins [2018] W. K. Newey and J. M. Robins.  Cross-fitting and fast remainder rates for semiparametric estimation.  _arXiv preprint arXiv:1801.09138_ , 2018.
  * Pfanzagl [1982] J. Pfanzagl.  _Contributions to a general asymptotic statistical theory_ , volume 13.  Springer, 1982.
  * Ribeiro et al. [2016] M. T. Ribeiro, S. Singh, and C. Guestrin.  "why should i trust you?": Explaining the predictions of any classifier.  In _Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , pages 1135–1144. ACM, 2016\.  doi: 10.1145/2939672.2939778.
  * Robins and Rotnitzky [1995] J. M. Robins and A. Rotnitzky.  Semiparametric efficiency in multivariate regression models with missing data.  _Journal of the American Statistical Association_ , 90(429):122–129, 1995.
  * Robins and Wang [2000] J. M. Robins and N. Wang.  Inference for imputation estimators.  _Biometrika_ , 87(1):113–124, 2000.
  * Robins et al. [2008] J. M. Robins, L. Li, E. J. Tchetgen Tchetgen, and A. W. van der Vaart.  Higher order influence functions and minimax estimation of nonlinear functionals.  _Probability and Statistics: Essays in Honor of David A. Freedman_ , pages 335–421, 2008.
  * Robins et al. [2009a] J. M. Robins, L. Li, E. Tchetgen Tchetgen, and A. W. van der Vaart.  Quadratic semiparametric von mises calculus.  _Metrika_ , 69(2-3):227–247, 2009a.
  * Robins et al. [2009b] J. M. Robins, E. J. Tchetgen Tchetgen, L. Li, and A. W. van der Vaart.  Semiparametric minimax rates.  _Electronic Journal of Statistics_ , 3:1305–1321, 2009b.
  * Robins et al. [2017] J. M. Robins, L. Li, R. Mukherjee, E. Tchetgen Tchetgen, and A. W. van der Vaart.  Minimax estimation of a functional on a structured high dimensional model.  _The Annals of Statistics_ , 45(5):1951–1987, 2017.
  * Spirtes et al. [2000] P. Spirtes, C. N. Glymour, and R. Scheines.  _Causation, prediction, and search_.  MIT press, 2000.
  * Taubman et al. [2009] S. L. Taubman, J. M. Robins, M. A. Mittleman, and M. A. Hernán.  Intervening on risk factors for coronary heart disease: an application of the parametric g-formula.  _International journal of epidemiology_ , 38(6):1599–1611, 2009.
  * Tsiatis [2006] A. A. Tsiatis.  _Semiparametric Theory and Missing Data_.  New York: Springer, 2006.
  * Tsybakov [2009] A. B. Tsybakov.  _Introduction to Nonparametric Estimation_.  New York: Springer, 2009.
  * van der Laan [2017] M. van der Laan.  A generally efficient targeted minimum loss based estimator based on the highly adaptive lasso.  _The international journal of biostatistics_ , 13(2), 2017\.
  * van der Laan and Robins [2003] M. J. van der Laan and J. M. Robins.  _Unified Methods for Censored Longitudinal Data and Causality_.  New York: Springer, 2003.
  * van der Laan and Rose [2011] M. J. van der Laan and S. Rose.  _Targeted Learning: Causal Inference for Observational and Experimental Data_.  Springer, 2011.
  * van der Laan et al. [2019] M. J. van der Laan, D. Benkeser, and W. Cai.  Efficient estimation of pathwise differentiable target parameters with the undersmoothed highly adaptive lasso.  _arXiv preprint arXiv:1908.05607_ , 2019.
  * van der Vaart [2002] A. W. van der Vaart.  Semiparametric statistics.  _In: Lectures on Probability Theory and Statistics_ , pages 331–457, 2002.
  * Wasserman [2006] L. Wasserman.  _All of Nonparametric Statistics_.  Springer, 2006.
  * White [1982] H. White.  Maximum likelihood estimation of misspecified models.  _Econometrica_ , pages 1–25, 1982.