# NFL Ghosts: A framework for evaluating defender positioning with conditional
density estimation

Ronald Yurko${}^{\text{1}}$ Quang Nguyen${}^{\text{1}}$ Konstantinos
Pelechrinis${}^{\text{2}}$

(${}^{\text{1}}$Department of Statistics & Data Science, Carnegie Mellon
University
${}^{\text{2}}$Department of Informatics and Networked Systems, University of
Pittsburgh
)

###### Abstract

Player attribution in American football remains an open problem due to the
complex nature of twenty-two players interacting on the field, but the
granularity of player tracking data provides ample opportunity for novel
approaches. In this work, we introduce the first public framework to evaluate
spatial and trajectory tracking data of players relative to a baseline
distribution of “ghost” defenders. We demonstrate our framework in the context
of modeling the nearest defender positioning at the moment of catch. In
particular, we provide estimates of how much better or worse their observed
positioning and trajectory compared to the expected play value of ghost
defenders. Our framework leverages high-dimensional tracking data features
through flexible random forests for conditional density estimation in two
ways: (1) to model the distribution of receiver yards gained enabling the
estimation of within-play expected value, and (2) to model the 2D spatial
distribution of baseline ghost defenders. We present novel metrics for
measuring player and team performance based on tracking data, and discuss
challenges that remain in extending our framework to other aspects of American
football.

Keywords: Random forests, high-dimensional data, player tracking data,
American football

##  1 Introduction

Player tracking data have become a powerful resource in sports analytics in
recent years. Many professional sports leagues around the world collect data
on spatial coordinates of players and ball, enabling continuous-time modeling
and analysis of sports at a fine-grained level. This is a massive leap forward
from traditional data sources like box-score statistics and event-by-event
data. For recent surveys on player tracking data in sports, we refer the
reader to Baumer et al., (2023) and Kovalchik, (2023).

Player tracking data provide a great opportunity for novel advancements in
statistical modeling and analysis of sports. In this paper, we focus on one
specific task in sports analytics: player evaluation. Specifically, we propose
a framework for evaluating players based on the rich tracking data features on
player positioning and trajectory. We illustrate our framework with American
football, as we aim to provide an assessment of defensive pass coverage
performance in the context of limiting yards after catch. Below, we briefly
highlight notable contributions on play evaluation, tracking data models, and
player evaluation in sports.

###  1.1 Previous work: expected value of a game state

The task of estimating the expected value of a game state given its contextual
information is fundamental in sports analytics. Prior to tracking data became
available, this task is performed at the discrete level, where a sport can be
divided into categorically distinct events or actions. In baseball, the runs
expectancy matrix (Lindsey,, 1963) contains the expected number of runs in the
remainder of an inning for each situation of number of outs and runners on
base. In soccer, expected goals (xG) (Barnett and Hilditch,, 1993) is commonly
used to value a shot attempt. xG measures the conversion probability of a shot
by accounting for various factors, including distance and angle to goal, part
of the body used for shooting the ball, and type of previous event.

In American football, expected points (EP) is a common concept for estimating
the expected value of a game state. The game state features in an EP model
typically include the current down, yards to go for a first down, current
yardline, time remaining, to name a few. Importantly, EP has the advantage of
interpretability. Since its unit of measurement is on a point scale, EP
provides are useful measure for in-game strategic decision making (Romer,,
2006). For example, one can take the difference between pre-play EP and post-
play EP to measure the value for an individual play. This is commonly known as
expected points added (EPA) (Burke,, 2009; Yurko et al.,, 2019).

Early attempts on modeling EP in football provide estimates at the discrete-
time between-play level. Yurko et al., (2019) summarize the key points and
limitations of previous work (Carter and Machol,, 1971; Carroll et al.,,
1988), before proposing a multinomial logistic regression model to estimate
EP. This approach first estimates the probability of the next scoring outcome,
and then computes EP as a function of these probabilities. The considered
scoring outcomes and their respective point values are touchdown (7), field
goal (3), safety (2), no score (0), opposing team safety (-2), opposing team
field goal (-3), and opposing team touchdown (-7).

At the continuous level, the granularity of player tracking data allows for
the estimation of within-play expected values. Cervone et al., (2016) propose
a continuous-time framework for estimating the expected possession value (EPV)
for the offensive team during a possession in basketball. This framework
consists of two sub-models, one for player movement and one for player
decision-making outcome (pass, shot, or turnover). Sicilia et al., (2019)
introduce a different in-play expected value approach for basketball. This
work first estimates the probability for within-play actions, namely, shot
attempt, foul (shooting and non-shooting), and turnover, before converting to
a point scale. In American football, Yurko et al., (2020) provide continuous-
time within-play valuation estimates by using a long short-term memory model
to predict the expected yards gained for a ball-carrier throughout a play.
Fernandez et al., (2021) use deep learning to develop EPV for soccer, based on
the values of three main actions: shot, pass, and drive. For more discussions
on within-play expected value in sports, see Macdonald, (2020).

###  1.2 Previous work: player tracking data in American football

In American football, the National Football League (NFL) collects tracking
data via their tracking system known as Next Gen Stats by having radio
frequency identification (RFID) tags installed into players’ shoulder pads and
the football. These high-resolution data, measured at a rate of 10 frames per
second, provide positional information for all players on the field (and also
the ball). Along with their player tracking system, the NFL also launched the
Big Data Bowl—an annual data science competition focusing on player tracking
data—in 2018 (NFL Football Operations,, 2024). Each year, the NFL Big Data
Bowl releases a sample of tracking data to accompany a competition theme on a
specific aspect of American football such as pass coverage, special teams, and
linemen on pass plays. The competition has paved the path for many innovations
in football analytics and subsequently established the foundation for the
peer-reviewed literature on statistical analysis of football tracking data
(Lopez,, 2020).

Chu et al., (2020) implement model-based clustering to characterize receiver
routes on passing plays. Yurko et al., (2020) introduce a framework for
obtaining continuous-time estimates of play value in American football.
Deshpande and Evans, (2020) propose an expected hypothetical completion
probability framework for assessing offensive plays and quarterback decision
making. Dutta et al., (2020) use unsupervised learning methods to identify
pass coverage types for NFL defensive backs. Nguyen et al., 2024a ; Nguyen et
al., 2024b  devise novel metrics for evaluating pass rush and tackling in
American football at the frame level. Note that these articles provide novel
means for assessing both offensive and defensive players in American football.
These are remarkable accomplishments, since there were no comprehensive
measures for evaluating positions such as defensive linemen prior to player
tracking data became publicly available (Wolfson et al.,, 2017).

Along with the contribution to their respective evaluation aspect of football,
the aforementioned work all share one common theme. That is, their models
consist of features obtained from tracking data based on player positioning
and trajectory. As classified by Kovalchik, (2023), there are two main types
of features for measuring player performance: directly-derived features and
model-based features. Directly-computed variables such as distance, velocity,
acceleration, orientation and angle for each player (and between players in
the case of distance and angle) are quintessential to developments in player
evaluation with tracking data. For instance, Nguyen et al., 2024b  propose a
model-free, continuous pass rush metric by simply taking the ratio of the pass
rusher’s velocity toward the quarterback and distance to the quarterback. As
for model-based features, one common strategy is to define space ownership for
each player on the field. For example, Yurko et al., (2020) construct
different features with respect to football field region owned by the ball
carrier obtained from Voronoi tessellation.

Nevertheless, the task of player evaluation using inputs that are functions of
players themselves remains an open problem.

###  1.3 Previous work: player evaluation with ghosting

Ghosting is a prominent approach for evaluating players in continuous-time
based on player positioning and movement information. As its name would
suggest, ghosting aims to identify optimal player actions throughout a play by
comparing a player to an average player, i.e., “ghost”. This notion is first
introduced in basketball, as Lowe, (2013) illustrates how the Toronto Raptors
at the time were using tracking data to perform player evaluation. In
particular, the team develops an algorithm for comparing players in reality to
ghost players, in order to analyze the actual player actions on the basketball
court versus what they should have done at any particular moment within a
possession.

Perhaps the most common data-driven technique for ghosting is deep imitation
learning, which is first proposed by Le et al., 2017a . This seminal work
examines defensive strategies in soccer, studying where a defender at any
given moment within a play should have been based on a league average model.
Here, the optimal locations are those that minimize the offense’s chance of
scoring given positional information of every player on the pitch. Le et al.,
2017b  then follow-up by proposing a coordinated multi-agent imitation
learning framework in soccer. This strategy uses a long short-term memory
network to model player trajectories and a three-phase training process that
alternates between evaluating individual player policies and a team’s joint
policy. Le et al., 2017b ’s coordinated multi-agent model is then adopted in
basketball and American football. In basketball, Seidl et al., (2018) propose
an interactive player sketching system, which outputs ghost players that
imitate basketball defensive behaviors after receiving information about
offensive trajectories. In American football, Schmid et al., (2021) offer a
ghosting framework which generates defensive trajectories and allows for the
comparison of player movement within a play with a simulated league-average
behavior. The article also introduces a pass completion probability model to
evaluate the proposed ghosting model for understanding defensive behavior in
the NFL.

Note that the aforementioned work provide ghosting models for only the
defensive players and team. Felsen et al., (2018) use conditional variational
autoencoders to simulate the offense in basketball and predict the
personalized adversarial motion of players on the court. Indeed, recent
developments of ghosting have seen the rise of generative models in their
methodology. Zhan et al., (2019) propose a method for simulating how a
basketball team would execute a play given a defined “macro intent” (e.g.,
setting up a formation). This allows for the understanding of player
trajectories and how they interact with one another to reach a specific end
state and achieve a goal. Gu and De Silva, (2023) introduce a deep generative
ghosting model using conditional variational recurrent neural network to
imitate player movement and interactions in soccer. This approach first
creates sequences of pitch control grids to represent player interactions,
before training the generative model to generate benchmark player and team
performances. More recently, Srinivasan et al., (2023) combine imitation
learning with generative and language models to imitate the playing style and
shot selection of tennis players.

###  1.4 Our contributions

In this paper, we propose a framework for evaluating player positioning and
trajectory relative to baseline ghost players. In doing so, we use a high-
dimensional conditional density estimation approach to account for a rich set
of features derived from tracking data to compute the expected within-play
value. Our flexible framework provides evaluation on the scale of expected
points, thus having the benefit of interpretability. Further, the expected
within-play value for ghosts can be computed using a full probability
distribution of player positioning and movement information. This overcomes a
major limitation of previous ghosting approaches, which only return a point
estimate for the optimal player location and trajectory.

To illustrate our framework, we focus specifically on evaluating defensive
pass coverage performance in the NFL. In every passing play, there are two
separate yardage components that contribute to the final spot where the ball
is placed: (1) air yards, which represents the yards gained at the moment the
ball is caught by the receiver, and (2) yards after catch (YAC), which
represents the extra yards gained by the receiver after the catch is made.
Figure 1 displays a comparison of the distributions of value added through the
air versus YAC in terms of both yards gained and expected points added for
receptions in the 2018 season. It is evident that YAC represents a significant
portion of the value of passing plays and warrants investigation into the role
defenders play in limiting YAC.

Figure 1: Comparison of distributions for yards gained during the 2018 NFL
season through the air (in gray) versus yards after catch (in blue), along
with the distribution for expected points added through the air versus after
the catch obtained from the nflfastR R package (Carl and Baldwin,, 2024; R
Core Team,, 2024). Vertical dashed lines indicate the means for the respective
distributions. Yards after catch represent a significant part of the value
obtained through passing.

Using player tracking data provided by the NFL Big Data Bowl, we introduce a
ghosting framework for analyzing the ability of defenders to limit YAC. In
particular, we compare the observed expected value of defensive player
positioning and trajectory with a distribution of ghost defenders on passing
plays. Our approach leverages random forests for conditional density
estimation (RFCDE) as the primary method and consists of two main components:
(1) an estimate for the yards after catch distribution of the receiver, and
(2) an estimate for the 2D location distribution of ghost defenders. For each
model, we account for the high-dimensional features derived from player
tracking data and play-level context. The benefits of our RFCDE approach are
plentiful. RFCDE allows for estimating the full distribution of our quantities
of interest, rather than just a point prediction which differs from previous
ghosting approaches. Thus, we can quantify the uncertainty in the response for
both univariate (yards after catch) and multivariate (2D defender location)
cases, which is crucial for our framework.

Figure 2: Example play heatmap of expected play values (EPV) over a grid of
hypothetical ghost defender locations, with the observed nearest defender to
the receiver at the moment of catch highlighted in red. The team on offense
(in blue) is moving from right to left against the opposing defense (in
orange). The first down line is highlighted in yellow, and the arrows
indicates players’ velocity vectors of movement. The size of the ghost grid
points are proportional to the 2D RFCDE ghost defender location estimates,
indicating which locations are more likely for the defender to be positioned
at. The point color represents the associated location EPV with lower values
(dark blue) corresponding to a better expected outcome for the defense, versus
regions with higher positive EPV (yellow) that are better for the offense.

Figure 2 displays the culmination of our approach for an example play at the
moment of catch, before the receiver was tackled by the nearest defender short
of the first down line. The combination of estimates obtained from RFCDE allow
us to observe expected play values across a grid of hypothetical ghost
defender locations. Thus, our framework enables us to evaluate the positioning
and trajectory of the defender in this play, relative to moving the player
around the grid of ghost locations. We note that even though our focus is on
assessing defenders on passing plays, our framework can be extended to the
within-play evaluation of players in other aspects of American football and
other sports.

The rest of this paper is structured as follows. In Section 2, we provide an
overview of the NFL tracking data. We describe our modeling approach and
player evaluation framework in Section 3, and then demonstrate our framework
with an example play along with a presentation of novel player and team
metrics in Section 4. Finally, we conclude with a discussion of our findings
in Section 5.

##  2 Data

For our analysis, we use the player tracking data supplied by the NFL Big Data
Bowl 2021 (Howard et al.,, 2020). The data are recorded at a frequency of 10
Hz (i.e. 10 times a second) and contain information for every passing play
across all 17 weeks of the 2018 NFL regular season. Of primary interest, the
data provide x and y coordinates of players on the field at every frame within
each play. It is worth noting that offensive and defensive linemen information
are omitted from the provided tracking data. The data also record player
attributes at each time step including speed, acceleration, distance traveled
from previous frame, orientation, and angle of motion. In addition, a vital
feature in our data is the event label (e.g., ball snap, pass release, tackle,
etc.) that corresponds to each moment of time within a play.

As an example, Table 1 presents the tracking data for an example play (from
Figure 2) during the 2018 season week 10 game between the Miami Dolphins and
the Green Bay Packers. For context, this play is a third down with six yards
to go for the offense as Dolphins receiver DeVante Parker caught the forward
pass thrown by his quarterback teammate, before being tackled by Packers
cornerback Jaire Alexander. In Section 4, we use this play as a case study to
illustrate our proposed framework.

Table 1: Example of tracking data for a play during the Miami Dolphins versus Green Bay Packers NFL game on November 11, 2018. The selected variables include frame identifier for each play (frameId); player location on the field (x and y coordinates); speed (s, in yards/second); acceleration (a, in yards/second2); distance traveled from previous frame (dis, in yards); orientation (o, between 0 and 360 degrees); angle of motion (dir, between 0 and 360 degrees); and event label for each frame (event). The data shown here are for Packers cornerback Jaire Alexander, and the frames included are between the ball snap and when the tackle is made (the end-of-play event).  frameId | x | y | s | a | dis | o | dir | event
---|---|---|---|---|---|---|---|---
11 | 84.63 | 43.12 | 0.00 | 0.00 | 0.00 | 92.26 | 238.61 | ball_snap
12 | 84.63 | 43.13 | 0.00 | 0.00 | 0.00 | 92.26 | 250.10 | None
⋮ | ⋮ | ⋮ | ⋮ | ⋮ | ⋮ | ⋮ | ⋮ | ⋮
38 | 81.45 | 33.11 | 8.05 | 1.94 | 0.81 | 167.45 | 180.08 | pass_forward
39 | 81.46 | 32.28 | 8.29 | 1.90 | 0.84 | 162.66 | 178.47 | None
⋮ | ⋮ | ⋮ | ⋮ | ⋮ | ⋮ | ⋮ | ⋮ | ⋮
43 | 81.70 | 28.79 | 9.01 | 0.90 | 0.90 | 167.24 | 174.88 | pass_arrived
44 | 81.78 | 27.88 | 9.13 | 0.49 | 0.91 | 167.24 | 174.72 | None
⋮ | ⋮ | ⋮ | ⋮ | ⋮ | ⋮ | ⋮ | ⋮ | ⋮
51 | 81.87 | 21.40 | 8.93 | 3.03 | 0.90 | 198.63 | 184.53 | pass_outcome_caught
52 | 81.78 | 20.52 | 8.75 | 3.34 | 0.89 | 205.36 | 186.89 | None
⋮ | ⋮ | ⋮ | ⋮ | ⋮ | ⋮ | ⋮ | ⋮ | ⋮
55 | 81.30 | 18.03 | 8.05 | 3.66 | 0.82 | 205.80 | 193.49 | tackle

In total, there are 19,239 passing plays where the play outcome includes
complete pass, incomplete pass, intercepted pass, or quarterback sack. Since
the primary focus of this paper is the assessment of defender ability to limit
yards after catch, we only consider plays that result in a complete pass
outside of the end zone (i.e., the receiver catches the forward pass by the
quarterback with yards remaining to their target end zone). We take a similar
approach to Yurko et al., (2020) to construct tracking data features that
capture information about the players involved at relevant events within a
play. We split the players into four groups: quarterback (qb_), receiver
(rec_), offense excluding quarterback (offX_), and defense (defX_), where we
order the offensive and defensive players based their Euclidean distance to
the receiver at the moment of catch (e.g., def1_x_adj denotes how many yards
away the closest defender is from the receiver’s target endzone). All of the
features are computed at the moment of catch, except for information about the
quarterback which is measured at the moment the ball is thrown. After pre-
processing our data to only consider plays without missing values for the
features in Table 2, our analysis is limited to 10,363 completed passes.

Table 2: List of features constructed from player tracking data. Features (relevant positions) |  Description
---|---
x_adj (rec, off, def) |  Horizontal yards from the receiver’s target endzone.
y_adj (rec, off, def) |  Vertical yards from the center of field with respect to the target endzone, where positive values indicate left side while negative values indicate right side.
dir_endzone (rec, off, def) |  Absolute value of the direction a player is moving with respect to the target endzone, where 0 indicates that the player is moving towards the endzone, while positive degrees between 0 and 180 indicate that the player is moving to the left or right.
o_endzone (rec, off, def) |  Absolute value of the orientation a player’s shoulder pads are facing with respect to the target endzone, where 0 indicates that the player is facing the endzone while positive degrees between 0 and 180 indicate that the player is facing left or right.
x_adj_from_first_down (rec) |  Distance (in yards) the receiver is from the first down line (or endzone in goal to go downs) where positive values denote the yards to go while negative values indicate yards past the first down line.
s (qb, rec, off, def) |  The speed (in yards/second) a player is moving at.
x_adj_change (qb, off, def) |  Horizontal displacement between a player and the receiver according to x_adj values.
y_adj_change (qb, off, def) |  Absolute value of vertical displacement between a player and the receiver according to y_adj values.
dist_to_rec (qb, off, def) |  Euclidean distance between a player and the receiver.
dir_wrt_rec_diff (off, def) |  Minimal absolute difference between a player’s direction of movement and the angle between the player and the receiver.
o_wrt_rec_diff (off, def) |  Minimal absolute difference between a player’s orientation and the angle between the player and the receiver.

##  3 Methods

Our framework for evaluating the positioning of defenders at the moment of
catch relies on distribution estimates for (1) the yards after catch gained by
a receiver and (2) the 2D location of ghost defenders. Instead of relying on
parametric assumptions for these distributions, we use random forests for
conditional density estimation (RFCDE) (Pospisil and Lee,, 2018, 2019). RFCDE
is a flexible nonparametric tree-based approach that can handle the high-
dimensional tracking data features described in Table 2. Here, the features
are accounted for via weighted kernel density estimation, where the weights
are determined by the terminal nodes of the trees in a random forest
(Breiman,, 2001).

Following the notation in Pospisil and Lee, (2019), let $\theta_{t}$ represent
the tree structure for tree $t$ and $R(X^{*},\theta_{t})$ denote the feature
space region covered by its terminal leaf node for observation $X^{*}$. For
observation $X^{*}$, the weight for each observation $i=1,\dots,n$ in the
training data across $T$ trees is calculated as

$w_{i}(X^{*})=\frac{1}{T}\sum_{t=1}^{T}\frac{\mathbbm{1}(X_{i}\in
R(X^{*},\theta_{t}))}{\sum_{i=1}^{n}\mathbbm{1}(X_{i}\in
R(X^{*},\theta_{t}))}.$ (1)

Unlike traditional random forests for regression or classification, the tree
splits in RFCDE are determined to minimize a loss specific to conditional
density estimation (Izbicki and Lee,, 2017). For computational efficiency,
this relies on an orthogonal basis expansion (which we set to fifteen cosine
basis functions in our work). Ultimately, these random forest weights are used
to perform weighted kernel density estimation,

$\hat{f}(Y\mid
X^{*})=\frac{1}{\sum_{i=1}^{n}w_{i}(X^{*})}\sum_{i=1}^{n}w_{i}(X^{*})K_{h}(Y_{i}-Y),$
(2)

where $K_{h}$ is a kernel function (e.g., Gaussian), with bandwidth $h$ chosen
using plug-in methods. The RFCDE estimate $\hat{f}(Y\mid X^{*})$ determines
how “close” each of the training data observations are to the point of
interest based on whether they belong to the same leaf node in the collection
of $T$ trees. This provides a flexible way to capture high-dimensional
features and interactions for the purpose of conditional density estimation.
RFCDE has been successfully demonstrated before in the context of modeling
yards gained by NFL running backs using tracking data (Yurko et al.,, 2020).
For the remainder of this section, we rely on the RFCDE software described in
detail by Dalmasso et al., (2020) and use $T=500$ trees to estimate our
distributions of interest.

###  3.1 Expected play value at the moment of catch

Our quantity of interest is the expected play value (EPV) for the offensive
team at the moment of catch. Let $V$ be some measure of play-value, such as
the output of the previously mentioned expected points (EP) or win probability
(WP) model described in Yurko et al., (2019). Then our quantity of interest is

$EPV_{catch}=\mathbb{E}[V\mid X_{catch}],$ (3)

where $X_{catch}$ contains covariate information observed at (or up to) the
moment of time the receiver makes the catch, such as the features described in
Table 2.

In practice, the play value $V$ is the result of a complex utility function
$g()$ of the receiver’s ending yard line $Y$. A receiver’s ending yard line is
simply a combination of their field position at the moment of catch and their
yards gained after the catch (YAC). In other words, modeling the receiver’s
ending yard line is equivalent to modeling the receiver’s YAC conditioned on
their known starting position at the moment of catch. In order to compute
$EPV_{catch}$, we need to integrate over the conditional density $f$ for the
receiver’s ending yard line $Y$ given covariate information $X_{catch}$,

$EPV_{catch}=\int g(Y)f(Y\mid X_{catch})dY.$ (4)

As for measuring the utility $g()$, we use the expected points approach of
Yurko et al., (2019), which relies on a multinomial logistic regression model
to predict that next scoring event given a play’s context (e.g., down, yards
to go, yardline, etc.). This is just one example of an EP model, with a
variety of approaches in the literature each possessing their own problems and
limitations (see Brill and Wyner, (2023) for a description). However, the
choice of the EP approach does not matter in the context of our framework. As
long as the choice of the utility function $g()$ is a function of the ending
yard line, then our considered EP model can be replaced but our approach will
remain valid.

To compute $EPV_{catch}$ in Equation 4, we need an estimate for the
conditional density of the receiver’s ending yard line, $\hat{f}(Y\mid
X_{catch})$. To this end, we use RFCDE to estimate this density as a function
of high-dimensional tracking data features $X_{catch}$. Although the trees
within RFCDE implicitly perform variable selection, we use leave-one-week-out
cross validation (LOWO CV) to assess the out-of-sample performance of the
RFCDE estimate $\hat{f}(Y\mid X_{catch})$ for a varying set of features based
on the included number of defensive and offensive players. We consider three
evaluation metrics for the YAC model: (1) CDE loss considered in Dalmasso et
al., (2020), (2) root mean squared error (RMSE) between the observed YAC with
RFCDE mean, and (3) RMSE with RFCDE mode. We consider both the mean and mode
relevant since the YAC distributions will likely be skewed and exhibit non-
symmetrical behavior. We observe that the YAC density estimate’s LOWO CV
performance do not improve after accounting for information about the nearest
defender (def1), in addition to accounting for the receiver and quarterback
information in Table 2 (see Supplementary Figure S1). This simplicity in the
considered number of defenders is likely driven by the fact we are only
modeling information at the moment of catch (as well as quarterback
information at the moment when the pass is released), with challenges for
extending this approach discussed later in Section 5.

For each of our considered 10,363 passing plays, we obtain
$\widehat{EPV}_{catch}$ using RFCDE for yards after catch trained on all plays
with the quarterback (qb), receiver (rec), and closest defender (def1)
features listed in Table 2. Specifically, for each play, we generate
conditional density estimates for the receiver’s YAC (or ending yard line)
$\hat{f}(Y\mid X_{catch})$ over a grid of possible values in increments of one
yard that range from -10 yards gained (determined based on the yardage
distribution displayed in Figure 1) to the maximum possible yards gained given
the location of the catch (i.e., distance to the target end zone). Similar to
the RFCDE approach in Yurko et al., (2020), we include a “padding” of
additional two yards to the maximum possible value for a better estimate of
the receiver reaching the target end zone. Since we are estimating the
conditional density in a discrete-like manner, for a given play, we normalize
the conditional density estimates $\hat{f}(Y\mid X_{catch})$ over the
considered grid of values so that they add up to one. Our estimate for
$\widehat{EPV}_{catch}$ is then based on the summation of these discrete
probability estimates multiplied by their respective utility function $g(Y)$
values.

###  3.2 Expected ghost play value

While the quantity in Equation 4 gives us the receiver’s expected value at the
moment of catch, our goal is to assess the spatial positioning of defenders in
limiting the receiver’s value added after the catch. This amounts to the
difference between $EPV_{catch}$ and the expected value if we replaced the
defender of interest with a hypothetical ghost defender, which we denote as
$EPV_{catch}^{ghost}$. With regards to Equation 4, this means replacing the
observed covariate information $X_{catch}$ with a ghost version
$\tilde{X}_{catch}$.

However, we recognize that $\tilde{X}_{catch}$ is itself random, i.e., there
is a distribution for the positioning of hypothetical defenders with certain
locations more likely than others. For ease of notation, we let $\ell$
represent the location tuple ($\texttt{x},\texttt{y}$) across the grid of
possible locations $\mathcal{L}$ on the field in one yard increments (6,897
possible values based on 121 unique x and 57 unique y coordinates). Since we
are interested in the nearest defender, for a given play, we restrict the set
of possible locations $\mathcal{L}$ to be all locations that are less than or
equal to the distance between the receiver and second closest defender. Thus,
to compute $EPV_{catch}^{ghost}$, we integrate over the distribution of 2D
locations for the nearest defender,

$EPV_{catch}^{ghost}=\int_{\ell\in\mathcal{L}}\Big{(}\int_{Y}g(Y)f(Y\mid\tilde{X}_{\ell})\
dY\Big{)}h(\ell\mid X_{catch}^{-\texttt{def1}})\ d\ell.$ (5)

In this form, we can rely on our conditional density estimate for the ending
yard line described in the previous section for $f$ that takes in the updated
features for def1 represented by $\tilde{X}_{\ell}$. However, we now need an
estimate for the conditional density $h$ of the ghost defender location $\ell$
given the covariate information $X_{catch}^{-\texttt{def1}}$ that excludes the
features on the nearest defender to the receiver.

To address this problem, we use a 2D RFCDE for the nearest defender locations
conditional density $h$. Similar to the previously discussed RFCDE for yards
after catch, this 2D conditional density estimate relies on the high-
dimensional tracking data information $X_{catch}$, but with information about
the nearest defender removed (i.e., without the def1 features). We again
assess the performance of the 2D RFCDE modeling the nearest defender location
with different sets of player tracking data features using LOWO CV. We observe
that only relying information about the receiver and quarterback is optimal
(based two criteria: cross-entropy and Euclidean distance between observed
location with RFCDE mean), relative to including information about other
defensive and offensive players (see Supplementary Figure S2). We recognize
that there is potentially other information that is relevant in modeling a
defender’s location, but leave expanding on additional features with larger
datasets than our considered sample for future work.

Coupling a 2D RFCDE trained on all available plays with the YAC RFCDE, we are
able to estimate $\widehat{EPV}_{catch}^{ghost}$ in Equation 5 for each play
as follows.

  1. 1.

For each 2D location $\ell\in\mathcal{L}$, update the nearest defender
features with the ghost location $\ell$ to create $\tilde{X}_{\ell}$, then
integrate over the YAC RFCDE to compute the expected play value for a
particular ghost location, $\widehat{EPV}_{catch}^{\ell}$.

  2. 2.

Integrate over the 2D location RFCDE to compute
$\widehat{EPV}_{catch}^{ghost}$. Similar to the YAC RFCDE, we normalize the
conditional density estimates $\hat{h}(\ell\mid X_{catch}^{-\texttt{def1}})$
to sum to one and compute the expectation as a summation with the location
discrete probability estimates multiplied by their respective
$\widehat{EPV}_{catch}^{\ell}$ values.

Although the above steps provide us with an estimate of ghost defender value,
modifying the defender’s observation location does not change all of the
relevant features describing that defender listed in Table 2. Beyond the
defender’s location, their trajectory (speed (s), direction of movement (dir),
orientation (o)) is also relevant and affects several of the considered
features describing the context at the moment of catch. Rather than dealing
with the complexity of jointly modeling defender trajectory with their
location, we use a sampling strategy by resampling the observed trajectories
for the nearest defenders at the moment of catch (where their angular
measurements are all normalized with respect to the receiver so that the
values are not distorted based on the field location).

In detail, for each sample $b$ in $B$ iterations, we update the previous
process for estimating the ghost expected value associated with a location
$\ell$ as follows.

  1. 1.

Sample with replacement a defender’s trajectory from the observed dataset
(i.e., sample the speed, direction, and orientation of the nearest defender
(def1) together to preserve their correlation structure).

  2. 2.

Update the nearest defender features with the ghost location $\ell$ and
sampled trajectory to create $\tilde{X}_{\ell,b}$.

  3. 3.

Integrate over the YAC RFCDE conditioned on $\tilde{X}_{\ell,b}$ to compute
the expected play value for a particular ghost location and sampled
trajectory, $\widehat{EPV}_{catch}^{\ell,b}$.

We then average over the $B$ samples to compute $\widehat{EPV}_{catch}^{\ell}$
for a given location, and then integrate over the 2D location RFCDE as before
to compute $\widehat{EPV}_{catch}^{ghost}$. This naive sampling approach
represents a reasonable starting point for handling the defender trajectory,
and we leave the exploration of modeling the trajectory information for future
work.

###  3.3 Evaluation of defender positioning

In order to evaluate the defender positioning and trajectory at the moment of
catch for a given play, we simply take the difference between the observed and
ghost expected play values, denoted by $\delta$. Specifically,

$\delta=\widehat{EPV}_{catch}-\widehat{EPV}_{catch}^{ghost}.$ (6)

Our novel framework results in this single value $\delta$, which provides an
estimate for a defender’s contribution based on their positioning and
trajectory relative to a distribution of hypothetical defenders. We are able
to aggregate these values for players and teams across the observed season of
data to create new valuation metrics based on player tracking data. All of the
code to implement our framework are available on GitHub at
https://github.com/ryurko/nfl-ghosts.

##  4 Results

###  4.1 Example play valuations

We demonstrate our framework with the example play mentioned in Section 2,
where Green Bay Packers cornerback Jaire Alexander tackled the receiver short
of the first down line. First, we estimate the expected value at the moment of
catch ($\widehat{EPV}_{catch}$) using the RFCDE for yards after catch
described in Section 3.1. Figure 3 displays the locations of players on the
field for the example play along with the CDE of the receiver’s YAC based on
the observed tracking data at the moment of catch. We observe that the mass of
the YAC density estimate is behind the first down line, which is beneficial to
the defense. Using this CDE along with the previously described EP model, we
get $\widehat{EPV}_{catch}=-0.16$ as the expected play value when the receiver
catches the ball. Here, notice that the expected value for the offense when
the receiver catches the ball based on the observed player tracking data, with
the considered features that include the nearest defender, is negative. In
other words, the defense is more likely to score next based on information
observed up to the moment of the ball being caught. Ultimately, this play does
result in the nearest defender tackling the receiver short of the first down,
which leads to the offensive team turning the ball over to the defense with a
punt.

Next, we use our proposed framework in Section 3.2 to evaluate the positioning
and trajectory of the nearest defender to the receiver relative to the ghost
distribution baseline. Figure 4 displays the 2D RFCDE output for the example
play, showing which locations on the field are more likely for the closest
defender to be positioned at. We observe the most likely location (in yellow)
with notably an asymmetric distribution for the ghost defender locations,
supporting the need for a flexible technique to model player locations.

Figure 3: Visualization of the example play featuring nearest defender Jaire
Alexander (in red), offensive players (in blue), and other defensive players
(in orange) at the moment of catch, along with the corresponding RFCDE for
yards after catch. The first down line (in gold) is displayed for reference,
indicating that the mass of the conditional density estimate for YAC is before
the first down line (as the play direction is from right to left).

We then estimate the expected value associated for each ghost defender
location $\widehat{EPV}_{catch}^{\ell}$ using the combination of the YAC RFCDE
and sampling of defender trajectories outlined in Section 3.2. Figure 2
displays the $\widehat{EPV}_{catch}^{\ell}$ values across the field with the
observed nearest defender displayed on top. Here, the locations with the
lowest $\widehat{EPV}_{catch}^{\ell}$ values, which are more beneficial to the
defense, are located right on top of the receiver, which is where the nearest
defender is actually observed. We also observe that the locations further away
from the actual location of the defender are more beneficial for the offense.
From this view, we can already see that the defender is positioned in an
optimal location for the defensive point of view at the moment of catch.

Figure 4: Heatmap display of 2D RFCDE for nearest defender positioning in the
example play (with the actual nearest defender removed). The most and least
likely locations correspond to high (in yellow) and low (in dark blue) CDE
values. The heatmap also reveals an asymmetrical distribution for the ghost
defender location.

Next, we integrate the $\widehat{EPV}_{catch}^{\ell}$ values over the 2D RFCDE
values to arrive the baseline ghost expected value
$\widehat{EPV}_{catch}^{ghost}=0.77$. This means that the baseline expected
value to assess the observed nearest defender location, based on player
tracking data for the receiver at the moment of catch and quarterback at
release, is a small positive quantity. Hence, we expect a positive situation
for the offense given the observed information and quantified uncertainty
about the distribution of player locations and YAC outcome.

Finally, we apply our calculated $\widehat{EPV}_{catch}$ and
$\widehat{EPV}_{catch}^{ghost}$ for this example play to Equation 6 and get
$\delta=-0.16-0.77=-0.93$. This indicates that the observed nearest defender’s
spatial positioning and trajectory is worth about one point in benefit of the
defense, relative to the expected value of the baseline ghost defender
distribution. Ultimately, this approach provides us with the first known
point-based evaluation system of a player’s spatial positioning and trajectory
from tracking data.

###  4.2 Player and team performance

For each of the 10,363 considered plays in the data, we apply the same
procedure as outlined in Section 4.1 to compute the $\delta$ values defined in
Equation 6. This allows us to assess the positioning and trajectory of the
closest defender to the receiver at the moment of catch relative to a baseline
ghost defender over the entire 2018 NFL regular season.

Table 3 displays the top ten NFL defenders based on their accumulated $\delta$
values across all plays where they are the closest to the receiver at the
moment of catch. This leaderboard is dominated by cornerbacks (CB), with only
one strong safety (Derwin James). The top CB Adoree’ Jackson accumulates a
total $\delta$ of -7.23 across the 56 plays where he is the nearest defender
to the receiver, which means that Jackson’s positioning and trajectory at the
moment of catch is effectively seven points better than the ghost baseline
across the entire 2018 NFL season. Since this aggregate is based on the change
in expected points, it is measured in an interpretable scale which relates to
actual game outcomes. In particular, Adoree’ Jackson’s spatial positioning
when the receiver catches the ball is worth approximately a single touchdown
across the entire regular season. We also present in Table 3 the observed YAC
allowed for these defenders for the plays in which they are the nearest
defender at the moment of catch, since our EPV-based $\delta$ values do not
actually account for the play outcome. We observe noticeable differences in
$\delta$ and YAC values. For example, Derwin James records the highest total
and average YAC allowed among the top ten players rated by total $\delta$.
This signals that James may be in great positioning at the moment of catch,
but consistently fails to tackle the receiver shortly after they catch the
ball.

Table 3: Top ten defensive players based on total accumulated $\delta$ across the 2018 NFL season. The total and average $\delta$ values are displayed (where lower values indicate better defensive positioning than ghost baseline), along with the total and average YAC allowed for the number of plays where they are the nearest defender to the receiver at the moment of catch. Player | Position | Plays | Total $\delta$ | Total YAC | Average $\delta$ | Average YAC
---|---|---|---|---|---|---
Adoree’ Jackson | CB | 56 | -7.23 | 158.32 | -0.13 | 2.83
A.J. Bouye | CB | 41 | -6.98 | 76.19 | -0.17 | 1.86
Jaire Alexander | CB | 53 | -6.65 | 128.46 | -0.13 | 2.42
Johnathan Joseph | CB | 50 | -6.40 | 152.47 | -0.13 | 3.05
Janoris Jenkins | CB | 53 | -6.01 | 152.06 | -0.11 | 2.87
Desmond Trufant | CB | 52 | -5.68 | 104.28 | -0.11 | 2.01
Ronald Darby | CB | 39 | -5.62 | 56.82 | -0.14 | 1.46
Derwin James | SS | 40 | -5.50 | 232.20 | -0.14 | 5.80
Malcolm Butler | CB | 48 | -5.48 | 161.48 | -0.11 | 3.36
Kyle Fuller | CB | 54 | -5.42 | 207.86 | -0.10 | 3.85

We also explore the relationship between our framework’s $\delta$ values and
the actual play outcome in terms of YAC in Figure 5. We observe a moderately
strong positive relationship between the average $\delta$ (change in EPV
values) and the average YAC allowed for defenders that faced at least ten
receptions as the nearest defender at the moment of catch. This indicates that
players who tend to be more optimally positioned relative to the ghost
baseline, thus more negative average $\delta$ values, also allow fewer YAC on
average. Figure 5 also stresses a positional separation between defensive
backs (cornerbacks and safeties) and linebackers. Linebackers are
traditionally expected to be weaker in pass coverage relative to defensive
backs, and we can see that linebackers display more positive average $\delta$
values. From a player evaluation perspective, this motivates conditioning on
the player position in the 2D ghost RFCDE model. For now, a post-hoc position
adjustment can be used for our results by simply taking the difference in the
total or average $\delta$ values for players relative to their respective
position groups. We leave the consideration of position and other categorical
variables for future work.

Figure 5: Relationship between the average YAC allowed (y-axis) and average
$\delta$ (change in EPV values, x-axis) across the 2018 NFL season for
defenders with at least ten plays where they are the nearest defender to the
receiver at the moment of catch. The overall correlation is moderately strong
($r=0.65$) and there are similar levels of correlation within the two position
groups: defensive backs (in blue, $r=0.51$) and linebackers (in yellow,
$r=0.65$).

Although we demonstrate our framework for evaluating the spatial positioning
of defenders at only the moment of catch, we observe in Figure 6 that our
novel $\delta$ metrics (in terms of change in EPV) are associated with
aggregate measures of team passing defense performance using expected points
added (EPA) available from the nflfastR package in R (Carl and Baldwin,,
2024). These pass defense EPA metrics are outcome-based, and include all pass
attempts unlike our $\delta$ metrics which are only for passes that are
complete. In Figure 6 (left), we observe a moderate positive relationship
($r=0.41$) between each team’s total pass defensive EPA and our novel
accumulated $\delta$ values across all receptions allowed by the team. We
observe a similar positive relationship ($r=0.46$) on the average scale in
Figure 6 (right). These results indicate that more optimal spatial positioning
and defender trajectories at the moment of catch is related to better
aggregate pass defense performance. For example, the Chicago Bears were
considered one of the best defensive teams during the 2018 NFL season, with
the best aggregate pass defense EPA relative to other teams. Our change in EPV
metrics is in agreement as the Bears defenders on completed passing plays have
the best total change in EPV relative to the ghost baseline. While this may
sound unsurprising, our novel framework is the first approach to properly
quantify and evaluate player positioning and trajectory information in
American football.

Figure 6: Scatterplots displaying relationship between team-level passing
defensive EPA (y-axis) and $\delta$ (change in EPV, x-axis) across the 2021
NFL season for both the total (left) and average (right) calculations. Teams
are displayed by their respective logos using the nflplotR package in R
(Carl,, 2024) . Negative passing defensive EPA values indicate better team-
level defensive performance.

##  5 Discussion

In this work, we introduce a framework for evaluating the spatial positioning
and trajectory of NFL defenders at the moment of catch relative to baseline
ghost defenders. Our framework is the first public approach to evaluate the
observed tracking data of players with proper consideration that hypothetical
ghost players come from a distribution. We illustrate our framework in the
context of modeling the nearest defender positioning at the moment of catch
and estimate how much better or worse their positional information compares to
ghosts with regards to the receivers value added through yards after catch.
Using high-dimensional, flexible random forests for conditional density
estimation, our proposed framework provides estimates for (1) the distribution
of a receiver’s YAC which enables the estimation of the expected value of an
interpretable utility function, and (2) the 2D distribution of hypothetical
defender locations, providing full uncertainty quantification for baseline
comparisons of defender positioning. This approach allows us to develop new
metrics for player valuation using tracking data, and we demonstrate how such
metrics are related to aggregate measures of performance.

We recognize that our framework and results are subject to various
limitations. With regards to evaluating the spatial positioning of players, we
cannot attribute the entire change in EPV to a single player without
recognizing that the scheme of the team’s coaching staff may have played a
large role. Additionally, we only the nearest defender to the receiver at the
moment of catch in our framework. This definition of nearest defender may be
viewed as undesirable, since by chance a defender that is covering a different
receiver may be physically closer than the defender that is actually
responsible for covering the receiver. There is opportunity to address this
concern via a Hidden Markov Model approach, such as a basketball example
demonstrated by Franks et al., (2015). Furthermore, our framework imposes a
simplified representation of American football, as we imagine that we can
effectively move the nearest defender around without altering the positions of
their teammates. Modeling a team’s defense together, instead of just a single
defender, is a challenging problem that could address this concern. However,
we leave these problems and considerations for accounting for additional
information (e.g., coverage type, receiver route type) for future work that
can expand on our framework with more publicly-released data by the NFL over
time.

Throughout this work, we emphasize that our main contribution is the framework
in which we are evaluating the observed tracking data of players with an
appropriate baseline. Our consideration for only considering a defender’s
positioning at the moment of catch with regards to receiver’s YAC is
relatively simple compared to the rest of play. Indeed, in order for the catch
to be made, this means the defender has already “failed” in preventing the
receiver from catching the football. We could extend our framework and attempt
to evaluate defender’s ability prior to completion, however this would require
additional models for whether a receiver is targeted by the quarterback and
catches the football (Yurko et al.,, 2020; Deshpande and Evans,, 2020). Moving
beyond a single moment of time, we look forward to implementing our framework
in full continuous-time and dealing with the challenges of modeling temporal
ghost distributions to create new ways of measuring player performance in
American football.

## Acknowledgements

The authors would like to thank Mike Lopez and the NFL Big Data Bowl 2021 for
releasing publicly-available player tracking data, as well as Sam Ventura, Nic
Dalmasso, the attendees and organizers of the 2023 New England Symposium on
Statistics in Sports, and participants at the 2024 CMSAC Football Analytics
Workshop for their valuable feedback.

## References

  * Barnett and Hilditch, (1993) Barnett, V. and Hilditch, S. (1993).  The effect of an artificial pitch surface on home team performance in football (soccer).  Journal of the Royal Statistical Society. Series A (Statistics in Society), 156(1):39.
  * Baumer et al., (2023) Baumer, B. S., Matthews, G. J., and Nguyen, Q. (2023).  Big ideas in sports analytics and statistical tools for their investigation.  WIREs Computational Statistics, 15(6).
  * Breiman, (2001) Breiman, L. (2001).  Random forests.  Machine Learning, 45(1):5–32.
  * Brill and Wyner, (2023) Brill, R. S. and Wyner, A. J. (2023).  Analytics, have some humility: a statistical view of fourth-down decision making.  arXiv preprint arXiv:2311.03490v1.
  * Burke, (2009) Burke, B. (2009).  Expected point values.  https://www.advancedfootballanalytics.com/2009/12/expected-point-values.html.
  * Carl, (2024) Carl, S. (2024).  nflplotR: NFL Logo Plots in ‘ggplot2’ and ‘gt’.  R package version 1.3.1, https://github.com/nflverse/nflplotR.
  * Carl and Baldwin, (2024) Carl, S. and Baldwin, B. (2024).  nflfastR: Functions to Efficiently Access NFL Play by Play Data.  R package version 4.6.1. https://CRAN.R-project.org/package=nflfastR.
  * Carroll et al., (1988) Carroll, B. N., Palmer, P., Thorn, J., and Pietrusza, D. (1988).  The Hidden Game of Football.  New York: Total Sports, Inc.
  * Carter and Machol, (1971) Carter, V. and Machol, R. E. (1971).  Operations research on football.  Operations Research, 19(2):541–544.
  * Cervone et al., (2016) Cervone, D., D’Amour, A., Bornn, L., and Goldsberry, K. (2016).  A multiresolution stochastic process model for predicting basketball possession outcomes.  Journal of the American Statistical Association, 111(514):585–599.
  * Chu et al., (2020) Chu, D., Reyers, M., Thomson, J., and Wu, L. Y. (2020).  Route identification in the National Football League.  Journal of Quantitative Analysis in Sports, 16(2):121–132.
  * Dalmasso et al., (2020) Dalmasso, N., Pospisil, T., Lee, A. B., Izbicki, R., Freeman, P. E., and Malz, A. I. (2020).  Conditional density estimation tools in python and R with applications to photometric redshifts and likelihood-free cosmological inference.  Astronomy and Computing, 30:100362.
  * Deshpande and Evans, (2020) Deshpande, S. K. and Evans, K. (2020).  Expected hypothetical completion probability.  Journal of Quantitative Analysis in Sports, 16(2):85–94.
  * Dutta et al., (2020) Dutta, R., Yurko, R., and Ventura, S. L. (2020).  Unsupervised methods for identifying pass coverage among defensive backs with nfl player tracking data.  Journal of Quantitative Analysis in Sports, 16(2):143–161.
  * Felsen et al., (2018) Felsen, P., Lucey, P., and Ganguly, S. (2018).  Where Will They Go? Predicting Fine-Grained Adversarial Multi-Agent Motion using Conditional Variational Autoencoders.  In Proceedings of the European Conference on Computer Vision (ECCV), pages 732–747.
  * Fernandez et al., (2021) Fernandez, J., Bornn, L., and Cervone, D. (2021).  A framework for the fine-grained evaluation of the instantaneous expected value of soccer possessions.  Machine Learning, 110(6):1389–1427.
  * Franks et al., (2015) Franks, A., Miller, A., Bornn, L., and Goldsberry, K. (2015).  Characterizing the spatial structure of defensive skill in professional basketball.  The Annals of Applied Statistics, pages 94–121.
  * Gu and De Silva, (2023) Gu, C. and De Silva, V. (2023).  Deep Generative Multi-Agent Imitation Model as a Computational Benchmark for Evaluating Human Performance in Complex Interactive Tasks: A Case Study in Football.  arXiv preprint arXiv:2303.13323.
  * Howard et al., (2020) Howard, A., Reid, J. E., Lopez, M., Bliss, T., and Cukierski, W. (2020).  NFL Big Data Bowl 2021.  https://kaggle.com/competitions/nfl-big-data-bowl-2021.
  * Izbicki and Lee, (2017) Izbicki, R. and Lee, A. B. (2017).  Converting high-dimensional regression to high-dimensional conditional density estimation.  Electronic Journal of Statistics, 11(2).
  * Kovalchik, (2023) Kovalchik, S. A. (2023).  Player Tracking Data in Sports.  Annual Review of Statistics and Its Application, 10(1):677–697.
  * (22) Le, H. M., Carr, P., Yue, Y., and Lucey, P. (2017a).  Data-driven ghosting using deep imitation learning.  In Proceedings of the 2017 MIT Sloan Sports Analytics Conference.
  * (23) Le, H. M., Yue, Y., Carr, P., and Lucey, P. (2017b).  Coordinated multi-agent imitation learning.  In Precup, D. and Teh, Y. W., editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 1995–2003. PMLR.
  * Lindsey, (1963) Lindsey, G. R. (1963).  An investigation of strategies in baseball.  Operations Research, 11(4):477–501.
  * Lopez, (2020) Lopez, M. J. (2020).  Bigger data, better questions, and a return to fourth down behavior: an introduction to a special issue on tracking datain the National Football League.  Journal of Quantitative Analysis in Sports, 16(2):73–79.
  * Lowe, (2013) Lowe, Z. (2013).  Lights, cameras, revolution.  Grantland.  https://grantland.com/features/the-toronto-raptors-sportvu-cameras-nba-analytical-revolution/. [Accessed 22-June-2024].
  * Macdonald, (2020) Macdonald, B. (2020).  Recreating the game: using player tracking data to analyze dynamics in basketball and football.  Harvard Data Science Review, 2(4).
  * NFL Football Operations, (2024) NFL Football Operations (2024).  Big Data Bowl.  NFL.com.  https://operations.nfl.com/gameday/analytics/big-data-bowl. [Accessed 22-June-2024].
  * (29) Nguyen, Q., Jiang, R., Ellingwood, M., and Yurko, R. (2024a).  Fractional Tackles: Leveraging Player Tracking Data for Within-Play Tackling Evaluation in American Football.  arXiv preprint arXiv:2403.14769.
  * (30) Nguyen, Q., Yurko, R., and Matthews, G. J. (2024b).  Here Comes the STRAIN: Analyzing Defensive Pass Rush in American Football with Player Tracking Data.  The American Statistician, 78(2):199–208.
  * Pospisil and Lee, (2018) Pospisil, T. and Lee, A. B. (2018).  RFCDE: Random forests for conditional density estimation.  arXiv preprint arXiv:1804.05753.
  * Pospisil and Lee, (2019) Pospisil, T. and Lee, A. B. (2019).  (f) RFCDE: Random Forests for Conditional Density Estimation and Functional Data.  arXiv preprint arXiv:1906.07177.
  * R Core Team, (2024) R Core Team (2024).  R: A Language and Environment for Statistical Computing.  R Foundation for Statistical Computing, Vienna, Austria.  https://www.R-project.org/.
  * Romer, (2006) Romer, D. (2006).  Do Firms Maximize? Evidence from Professional Football.  Journal of Political Economy, 114(2):340–365.
  * Schmid et al., (2021) Schmid, M., Blauberger, P., and Lames, M. (2021).  Simulating defensive trajectories in american football for predicting league average defensive movements.  Frontiers in Sports and Active Living, 3.
  * Seidl et al., (2018) Seidl, T., Cherukumudi, A., Hartnett, A., Carr, P., and Lucey, P. (2018).  Bhostgusters: Realtime interactive play sketching with synthesized nba defenses.  In Proceedings of the 2018 MIT Sloan Sports Analytics Conference.
  * Sicilia et al., (2019) Sicilia, A., Pelechrinis, K., and Goldsberry, K. (2019).  DeepHoops: Evaluating Micro-Actions in Basketball Using Deep Feature Representations of Spatio-Temporal Data.  In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. ACM.
  * Srinivasan et al., (2023) Srinivasan, P., Subramanian, R., and Knottenbelt, W. (2023).  Thinking the GOAT: Imitating Tennis Styles.  In Proceedings of the 2023 MIT Sloan Sports Analytics Conference.
  * Wolfson et al., (2017) Wolfson, J., Addona, V., and Schmicker, R. (2017).  Forecasting the Performance of College Prospects Selected in the National Football League Draft.  In Handbook of Statistical Methods and Analyses in Sports, pages 137–163. Boca Raton, FL: CRC Press.
  * Yurko et al., (2020) Yurko, R., Matano, F., Richardson, L. F., Granered, N., Pospisil, T., Pelechrinis, K., and Ventura, S. L. (2020).  Going deep: models for continuous-time within-play valuation of game outcomes in american football with tracking data.  Journal of Quantitative Analysis in Sports, 16(2):163–182.
  * Yurko et al., (2019) Yurko, R., Ventura, S., and Horowitz, M. (2019).  nflWAR: a reproducible method for offensive player evaluation in football.  Journal of Quantitative Analysis in Sports, 15(3):163–183.
  * Zhan et al., (2019) Zhan, E., Zheng, S., Yue, Y., Sha, L., and Lucey, P. (2019).  Generating multi-agent trajectories using programmatic weak supervision.  In 7th International Conference on Learning Representations, ICLR 2019.

## Supplementary Material

Figure S1: Comparison of leave-one-week-out cross validation performance
(y-axis) for YAC RFCDE based on set of player features accounted for (x-axis)
for three different metrics (in order): CDE loss, RMSE using RFCDE mean, and
RMSE using RFCDE mode. Mean values are displayed as points with intervals for
plus/minus one standard error. Figure S2: Comparison of leave-one-week-out
cross validation performance (y-axis) for nearest defender 2D RFCDE based on
set of player features accounted for (x-axis) for three different metrics (in
order): cross entropy, distance from observed location using RFCDE mean, and
distance from observed location using RFCDE mode. Mean values are displayed as
points with intervals for plus/minus one standard error.


Note that the algorithm returns the correct answer, unless for one of the
polynomials $q_{i}$ it holds that, $\mathsf{DS}^{\prime}_{q_{i}}(\vec{x})\neq
q_{i}(\vec{x})$. This event happens with probability at most
$O(\sqrt{\frac{d}{{\left|\mathbb{F}\right|}\alpha}})$. Hence, by applying
union bound we can bound the failure probability to
$O(\sqrt{\frac{d}{{\left|\mathbb{F}\right|}\alpha}})$. ∎

Finally, we prove Lemma 6.4.

###### Proof of Lemma 6.4.

The proof of this lemma basically relies on the local decoding algorithm for
Reed-Muller codes. Given a point $\vec{x}$, the query algorithm samples a
random line $\ell_{x,y}=\\{\vec{x}+r(\vec{y}-\vec{x}):r\in\mathbb{F}\\}$
passing through $\vec{x}$, and queries the data structure for all the points
on this line. Given these values, the algorithm finds the closest univariate
polynomial of degree at most $d$, call it $h$, and outputs $h(\vec{x})$. It is
not hard to see that the algorithm succeeds with probability at least
$1-4\gamma$.

For correctness since $\mathsf{DS}_{p}$ agrees with $q$ on $1-\gamma$ fraction
of the points $z\in\mathbb{F}^{n}$, it follows that for a random line $\ell$
through $x$ the data structure $\mathsf{DS}$ satisfies $\Pr[agr\geq 3/4]\geq
1-4\gamma$, where $agr$ denotes the fraction of points $z\in\ell$ with
$\mathsf{DS}_{q_{i}}(z)=q_{i}(z)$. For each such line $\ell$ the only
polynomial that agrees with $\mathsf{DS}$ on $\ell$ is $q_{i}$, and hence with
probability at least $1-4\gamma$ the data structure outputs $q_{i}(x)$, as
required. ∎

##### Putting it all together:

Below we summarize the reductions above, and describe the full reduction that
given a weak-average-case data structure $\mathsf{DS}$ that computes the
correct answer for only $\alpha$ fraction of $(q,x)$, gives us a data
structure that works with high probability for all inputs $q$ and all queries
$x$.

We first use Lemma 6.4, reducing the problem to evaluating $p$ on a random
line $\ell$ passing through $\vec{x}$. Then, we apply Lemma 6.3, to write $p$
as sum of $5$ polynomials, for which we know one of them is sparse and can be
computed efficiently, and the other four belong to the set of good
polynomials, i.e., those polynomials for which the data structure succeeds in
evaluating them on all but a small fraction of inputs. Finally, for each of
these polynomials we apply the reduction in Proposition 6.5. This last step
corresponds to choosing a random reference point $\vec{w}\in\mathbb{F}^{n}$,
and passing lines between every $\vec{z}\in\ell$ and $\vec{w}$, and evaluating
each of the $q_{i}$ on each of the $\mathbb{F}$ lines.

## References

  * [AD97] Miklós Ajtai and Cynthia Dwork.  A public-key cryptosystem with worst-case/average-case equivalence.  In STOC 1997, pages 284–293, 1997.
  * [Ajt96] Miklós Ajtai.  Generating hard instances of lattice problems.  In STOC 1996, pages 99–108, 1996.
  * [Aka08] Adi Akavia.  Learning significant fourier coefficients over finite abelian groups.  In Ming-Yang Kao, editor, Encyclopedia of Algorithms - 2008 Edition. Springer, 2008.
  * [AMN98] Yossi Azar, Rajeev Motwani, and Joseph Seffi Naor.  Approximating probability distributions using small sample spaces.  Combinatorica, 18(2):151–171, 1998.
  * [AV21] Josh Alman and Virginia Vassilevska Williams.  A refined laser method and faster matrix multiplication.  In SODA 2021, pages 522–539. SIAM, 2021.
  * [BABB19] Enric Boix-Adserà, Matthew Brennan, and Guy Bresler.  The average-case complexity of counting cliques in Erdős–Rényi hypergraphs.  In FOCS 2019, pages 1256–1280. IEEE, 2019.
  * [BFNW93] László Babai, Lance Fortnow, Noam Nisan, and Avi Wigderson.  BPP has subexponential time simulations unless EXPTIME has publishable proofs.  Computational Complexity, 3(4):307–318, 1993.
  * [BLR90] Manuel Blum, Michael Luby, and Ronitt Rubinfeld.  Self-testing/correcting with applications to numerical problems.  In STOC 1990, pages 73–83. ACM, 1990.
  * [BRSV17] Marshall Ball, Alon Rosen, Manuel Sabin, and Prashant Nalini Vasudevan.  Average-case fine-grained hardness.  In STOC 2017, pages 483–496, 2017.
  * [BRSV18] Marshall Ball, Alon Rosen, Manuel Sabin, and Prashant Nalini Vasudevan.  Proofs of work from worst-case assumptions.  In CRYPTO 2018, pages 789–819. Springer, 2018.
  * [BRTW14] Eli Ben-Sasson, Noga Ron-Zewi, Madhur Tulsiani, and Julia Wolf.  Sampling-based proofs of almost-periodicity results and algorithmic applications.  In ICALP 2014, pages 955–966. Springer, 2014.
  * [BT06] Andrej Bogdanov and Luca Trevisan.  Average-case complexity.  Foundations and Trends in Theoretical Computer Science, 2(1):1–106, 2006.
  * [CGL15] Raphael Clifford, Allan Grønlund, and Kasper Green Larsen.  New unconditional hardness results for dynamic and online problems.  In FOCS 2015, pages 1089–1107. IEEE, 2015.
  * [Cha02] Mei-Chu Chang.  A polynomial bound in Freiman’s theorem.  Duke Mathematical Journal, 113(3):399 – 419, 2002.
  * [CKL18] Diptarka Chakraborty, Lior Kamma, and Kasper Green Larsen.  Tight cell probe bounds for succinct boolean matrix-vector multiplication.  In STOC 2018, pages 1297–1306, 2018.
  * [CKLM18] Arkadev Chattopadhyay, Michal Kouckỳ, Bruno Loff, and Sagnik Mukhopadhyay.  Simulation beats richness: New data-structure lower bounds.  In STOC 2018, pages 1013–1020, 2018.
  * [CS10] Ernie Croot and Olof Sisask.  A probabilistic technique for finding almost-periods of convolutions.  Geometric and Functional Analysis, 20(6):1367––1396, 2010.
  * [DKKS21] Pavel Dvořák, Michal Kouckỳ, Karel Král, and Veronika Slívová.  Data structures lower bounds and popular conjectures.  arXiv:2102.09294, 2021.
  * [DLV20] Mina Dalirrooyfard, Andrea Lincoln, and Virginia Vassilevska Williams.  New techniques for proving fine-grained average-case hardness.  In FOCS 2020, pages 774–785. IEEE, 2020.
  * [FF93] Joan Feigenbaum and Lance Fortnow.  Random-self-reducibility of complete sets.  SIAM Journal on Computing, 22(5):994–1005, 1993.
  * [FHM01] Gudmund Skovbjerg Frandsen, Johan P. Hansen, and Peter Bro Miltersen.  Lower bounds for dynamic algebraic problems.  Information and Computation, 171(2):333–349, 2001.
  * [Fre77] Rusins Freivalds.  Probabilistic machines can use less running time.  In IFIP 1977, pages 839–842, 1977.
  * [GR18] Oded Goldreich and Guy Rothblum.  Counting $t$-cliques: Worst-case to average-case reductions and direct interactive proof systems.  In FOCS 2018, pages 77–88. IEEE, 2018.
  * [HKNS15] Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, and Thatchaphol Saranurak.  Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture.  In STOC 2015, pages 21–30, 2015.
  * [HLS21] Monika Henzinger, Andrea Lincoln, and Barna Saha.  The complexity of average-case dynamic subgraph counting.  ECCC, 2021.
  * [Imp95] Russell Impagliazzo.  A personal view of average-case complexity.  In CCC 1995, pages 134–147. IEEE, 1995.
  * [Imp11] Russell Impagliazzo.  Relativized separations of worst-case and average-case complexities for NP.  In CCC 2011, pages 104–114. IEEE, 2011.
  * [Juk12] Stasys Jukna.  Boolean function complexity: advances and frontiers, volume 27.  Springer Science & Business Media, 2012.
  * [KU08] Kiran S. Kedlaya and Christopher Umans.  Fast modular composition in any characteristic.  In FOCS 2008, pages 146–155. IEEE, 2008.
  * [Lar12] Kasper Green Larsen.  Higher cell probe lower bounds for evaluating polynomials.  In FOCS 2012, pages 293–301. IEEE, 2012.
  * [Lev86] Leonid A. Levin.  Average case complete problems.  SIAM Journal on Computing, 15(1):285–286, 1986.
  * [Lip91] Richard Lipton.  New directions in testing.  Distributed computing and cryptography, 2:191–202, 1991.
  * [LLV19] Rio LaVigne, Andrea Lincoln, and Virginia Vassilevska Williams.  Public-key cryptography in the fine-grained setting.  In CRYPTO 2019, pages 605–635. Springer, 2019.
  * [Lov15] Shachar Lovett.  An exposition of Sanders’ quasi-polynomial Freiman-Ruzsa theorem.  Theory of Computing, pages 1–14, 2015.
  * [Lov17] Shachar Lovett.  Additive combinatorics and its applications in theoretical computer science.  Theory of Computing, pages 1–55, 2017.
  * [LW17] Kasper Green Larsen and Ryan Williams.  Faster online matrix-vector multiplication.  In SODA 2017, pages 2182–2189. SIAM, 2017.
  * [MR06] Dana Moshkovitz and Ran Raz.  Sub-constant error low degree test of almost-linear size.  In STOC 2006, pages 21–30. ACM, 2006.
  * [NN93] Joseph Naor and Moni Naor.  Small-bias probability spaces: Efficient constructions and applications.  SIAM J. Comput., 22(4):838–856, 1993.
  * [Reg04] Oded Regev.  New lattice-based cryptographic constructions.  Journal of the ACM, 51(6):899–942, 2004.
  * [San12] Tom Sanders.  On the Bogolyubov–Ruzsa lemma.  IEEE Trans. Inf. Theory, 5(3):627–655, 2012.
  * [Sho09] Victor Shoup.  A computational introduction to number theory and algebra.  Cambridge, 2009.
  * [STV01] Madhu Sudan, Luca Trevisan, and Salil Vadhan.  Pseudorandom generators without the XOR lemma.  Journal of Computer and System Sciences, 62(2):236–266, 2001.
  * [TS17] Amnon Ta-Shma.  Explicit, almost optimal, epsilon-balanced codes.  In STOC 2017, pages 238–251, 2017.
  * [Vas18] Virginia Vassilevska Williams.  On some fine-grained questions in algorithms and complexity.  In ICM 2018, 2018.

##  Appendix A Proof of the probabilistic version of Sanders’ lemma

Below we prove Lemma 3.3. The proof follows the approach of Sanders, with
several modifications. We follow the exposition of Lovett [Lov15] in the proof
of the lemma.

See 3.3

Before starting with the proof, let us establish some notation. For a set
$A\subseteq\mathbb{F}^{n}$, we denote by
$1_{A}\colon\mathbb{F}^{n}\to\\{0,1\\}$ the indicator function of $A$, where
$1_{A}(x)=1$ if $x\in A$, and $1_{A}(x)=0$ otherwise. In particular
$\mathbb{E}_{x\in\mathbb{F}^{n}}[1_{A}(x)]=\frac{{\left|A\right|}}{{\left|\mathbb{F}\right|}^{n}}$.
We also let $\varphi_{A}\colon\mathbb{F}^{n}\to\mathbb{R}$ be the
normalization of $1_{A}$ defined as
$\varphi_{A}(x)=1_{A}(x)\cdot\frac{{\left|\mathbb{F}\right|}^{n}}{{\left|A\right|}}$
so that $\mathbb{E}_{x\in\mathbb{F}^{n}}[\varphi_{A}(x)]=1$. When the set $A$
is a singleton $A=\\{a\\}$, we will write $\varphi_{a}=\varphi_{\\{a\\}}$.

It is easy to verify that for a set $A$ and a function $f$ the convolution
$\varphi_{A}*f$ is given by $\varphi_{A}*f(x)=\mathbb{E}_{a\in A}[f(x-a)]$. In
particular, for $a\in\mathbb{F}^{n}$ we have $\varphi_{a}*f(x)=f(x-a)$.

As a starting point, we define the set
$D=\\{d\in\mathbb{F}^{n}:1_{A}*1_{-A}(d)\geq\delta\\}$ for a parameter
$\delta=\alpha^{2}/20$. That is, $D$ is the set of all _popular differences_
of two elements of $A$. In other words, $D$ consists of all
$d\in\mathbb{F}^{n}$ such that there are $\delta{\left|\mathbb{F}\right|}^{n}$
pairs $(a,a^{\prime})\in A^{2}$ satisfying $d=a-a^{\prime}$, i.e.,
$\Pr_{a\in\mathbb{F}^{n},a^{\prime}=d-a}[a\in A,a^{\prime}\in-A]\geq\delta$.

Note first that $\left\langle
1_{A-A},\varphi_{A}*\varphi_{-A}\right\rangle=\mathbb{E}_{x,y\in\mathbb{F}^{n}}[1_{A-A}(x-y)\varphi_{A}(x)\varphi_{-A}(-y)]=\mathbb{E}_{x,y\in
A}[1_{A-A}(x-y)]=1$. Next we observe that $D$ approximates $A-A$, in the sense
that $\left\langle 1_{D},\varphi_{A}*\varphi_{-A}\right\rangle\geq
1-\frac{\delta}{\alpha^{2}}=0.95$. Indeed, using the fact that $D\subseteq
A-A$, we have

$\displaystyle\left\langle 1_{D},\varphi_{A}*\varphi_{-A}\right\rangle$
$\displaystyle=\left\langle
1_{A-A},\varphi_{A}*\varphi_{-A}\right\rangle-\left\langle
1_{\mathbb{F}^{n}\setminus D},\varphi_{A}*\varphi_{-A}\right\rangle$
$\displaystyle=1-\frac{1}{\alpha^{2}}\left\langle 1_{\mathbb{F}^{n}\setminus
D},1_{A}*1_{-A}\right\rangle$
$\displaystyle=1-\frac{1}{\alpha^{2}}\cdot\Pr_{d,a\in\mathbb{F}^{n}}[a\in
A,d-a\in-A|d\notin D]\cdot\Pr_{d\in\mathbb{F}^{n}}[d\notin D]$
$\displaystyle\geq 1-\frac{\delta}{\alpha^{2}}\,.$ (5)

We remark that this is one of the main differences in our proof compared to
the original proof of Sanders, who only relied on the fact that $\left\langle
1_{A-A},\varphi_{A}*\varphi_{-A}\right\rangle=1$.

The proof of Lemma 3.3 consists of the following two parts.

######  Lemma A.1.

Let $A\subseteq\mathbb{F}^{n}$ be a set of size
${\left|A\right|}=\alpha{\left|\mathbb{F}\right|}^{n}$. Set
$t=O(\log(1/\alpha))$. There exists a set $X\subseteq\mathbb{F}^{n}$ of size
${\left|X\right|}\geq\alpha^{O(\log^{3}(1/\alpha))}{\left|\mathbb{F}\right|}^{n}$
such that for all $x_{1},x_{2},\dots,x_{t}\in X$ it holds that

$\Pr_{a_{1},a_{2}\in A}[a_{1}-a_{2}-\sum_{i=1}^{t}x_{i}\in D]\geq
0.9\enspace.$ (6)

Given the set $X$ from Lemma A.1 we use a standard Fourier-analytic argument
to define a large subspace $V$ such that ${\left|D\cap V^{\prime}\right|}\geq
0.8{\left|V\right|}$ where $V^{\prime}$ is some coset of $V$. In fact, we show
that there are many such cosets. Formally, we prove the following lemma.

######  Lemma A.2.

Let $A\subseteq\mathbb{F}^{n}$ be a set of size
${\left|A\right|}=\alpha{\left|\mathbb{F}\right|}^{n}$, Then, there exists a
subspace $V\subseteq\mathbb{F}^{n}$ of dimension
$\dim(V)=n-O(\log^{4}(1/\alpha))$ and a vector $b\in\mathbb{F}^{n}$ such that
if we sample a uniformly random $a\in A$ and $v\in V$ then

$\Pr_{a\in A,v\in V}[v+a+b\in D]\geq 0.85\enspace.$ (7)

######  Remark A.3.

Lemma A.1 corresponds to Lemma 4.2 in [Lov15]. The only difference is that we
claim that the sum belongs to $D$ with high probability, while in [Lov15] the
sum belongs to $A-A$. Note that the two statements are indeed close to each
other by Eq. 5.

Lemma A.2 roughly corresponds to the conclusion of the section _“A Fourier-
analytic argument”_ in [Lov15].

We show next how to conclude the proof of Lemma 3.3 from Lemma A.2. Indeed, by
Eq. 7 it follows that $\mathbb{E}_{a\in A}[\Pr_{v\in V}[v+a+b\in D]]\geq
0.85$, and hence for at least $0.05{\left|A\right|}$ many $a\in A$ it holds
that $\Pr_{v\in V}[v+a+b\in D]\geq 0.8$. In particular, for
$C=\\{c\in\mathbb{F}^{n}:{\left|D\cap(V+c)\right|}\geq 0.8{\left|V\right|}\\}$
we have ${\left|C\right|}\geq 0.05\alpha{\left|\mathbb{F}\right|}^{n}$.

######  Claim A.4.

The set $C\subseteq\mathbb{F}^{n}$ is symmetric. Namely, if $c\in C$, then
$-c\in C$.

###### Proof.

Let $c\in C$ and let $V+c$ be the corresponding coset of $V$. We claim that
$-c\in C$, i.e., ${\left|\\{v\in V:\text{ there are
$\geq\delta{\left|\mathbb{F}\right|}^{n}$ pairs $(a_{1},a_{2})\in A^{2}$ such
that $a_{1}-a_{2}=v-c$}\\}\right|}\geq 0.8{\left|V\right|}$.

For $c\in C$ let $P_{c}=\\{v\in V:\text{there are
$\geq\delta{\left|\mathbb{F}\right|}^{n}$ pairs $(a_{1},a_{2})\in A^{2}$ such
that $a_{1}-a_{2}=-v+c$}\\}$. By definition of $C$, we have
${\left|P_{c}\right|}\geq 0.8{\left|V\right|}$.

To see that $-c\in C$ take any $v\in P_{C}$, and note that $a_{1}-a_{2}=-v+c$
if and only if $a_{2}-a_{1}=v-c$. Therefore, for each $v\in P_{c}$ there are
$\geq\delta{\left|\mathbb{F}\right|}^{n}$ pairs $(a_{1},a_{2})\in A^{2}$ such
that $a_{2}-a_{1}=v-c$, and thus $-c\in C$, as required. ∎

Let us choose a unique representative $c^{*}$ for each coset $V+c$ of $V$ such
that ${\left|D\cap(V+c)\right|}\geq 0.8{\left|V\right|}$, and let
$C^{*}=\\{\mbox{$c^{*}$ is the representative of
$V+c$}:{\left|D\cap(V+c)\right|}\geq 0.8{\left|V\right|}\\}$. And furthermore,
let us assume without loss of generality that $C^{*}$ is symmetric, i.e.
$c^{*}\in C^{*}$ implies that $-c^{*}\in C^{*}$. Then, the union of all these
coset covers is at least $0.05\alpha$ fraction of $\mathbb{F}^{n}$, i.e.,

${\left|\cup_{c^{*}\in C^{*}}(V+c^{*})\right|}\geq
0.05\alpha{\left|\mathbb{F}\right|}^{n}\enspace.$ (8)

We are now ready to show that

$\Pr_{\begin{subarray}{c}a_{1},a_{2},a_{3}\in\mathbb{F}^{n}\\\
a_{4}=v-a_{1}-a_{2}-a_{3}\end{subarray}}[a_{1},a_{2}\in
A,a_{3},a_{4}\in-A]\geq\Omega(\alpha^{5})\enspace.$

###### Proof of Lemma 3.3.

Fix $v\in V$. Since ${\left|D\cap(V+c^{*})\right|}\geq 0.8{\left|V\right|}$
for every coset $V+c^{*}$ such that $c^{*}\in C^{*}$, it follows by the
symmetry of $C^{*}$ that for every $c^{*}\in C^{*}$ we have at least
$0.1\cdot{\left|V\right|}$ pairs $(u+c^{*},v-u-c^{*})\in D^{2}$ such that
$u\in V$. Therefore, by Eq. 8 for every $v\in V$ there are at least $0.1\times
0.05\alpha{\left|\mathbb{F}\right|}^{n}$ different pairs $(u+c^{*},v-u-c^{*})$
such that both $u+c^{*}\in D\cap(V+c^{*})$ and $v-u-c^{*}\in D\cap(V-c^{*})$.

Letting $d_{1}=u+c^{*}$, so far we got that for every $v\in V$ we have
$\Pr_{d_{1}\in\mathbb{F}^{n},d_{2}=v-d_{1}}[d_{1},d_{2}\in
D]\geq\Omega(\alpha)$.

Recall that by the definition of $D$, every $d_{1}\in D$ is a popular
difference of elements of $A$, i.e.
$\Pr_{\begin{subarray}{c}a_{1}\in\mathbb{F}^{n}\\\
a_{3}=d_{1}-a_{1}\end{subarray}}[a_{1}\in A,a_{3}\in-A]\geq\delta$. Similarly,
for $d_{2}\in D$ we have $\Pr_{\begin{subarray}{c}a_{2}\in\mathbb{F}^{n}\\\
a_{4}=d_{2}-a_{2}\end{subarray}}[a_{2}\in A,a_{4}\in-A]\geq\delta$. This
implies that

$\Pr_{\begin{subarray}{c}a_{1},a_{2},a_{3}\in\mathbb{F}^{n}\\\
a_{4}=v-a_{1}-a_{2}-a_{3}\end{subarray}}[a_{1},a_{2}\in
A,a_{3},a_{4}\in-A]\geq\Omega(\alpha\cdot\delta^{2})\enspace,$

as required. ∎

We now turn to proving each of the two steps stated in Lemma A.1 and Lemma
A.2.

###  A.1 Proof of Lemma A.1

The proof starts with the following lemma of Croot and Sisask [CS10].

######  Lemma A.5 (Croot-Sisask [CS10, Proposition 3.3]).

Let $A,B\subseteq\mathbb{F}^{n}$ be two sets, and let $\varepsilon\in(0,1)$
and $p\geq 1$. Let
$\alpha=\frac{{\left|A\right|}}{{\left|\mathbb{F}\right|}^{n}}\in(0,1)$. Then,
there exists a set $X\subseteq\mathbb{F}^{n}$ of size
${\left|X\right|}\geq(\alpha/2)^{O(p/\varepsilon^{2})}{\left|\mathbb{F}\right|}^{n}$
such that for all $x\in X$ it holds that

${\|\varphi_{x}*\varphi_{A}*1_{B}-\varphi_{A}*1_{B}\|}_{p}\leq\varepsilon\,.$

Let $p=\log_{2}(1/\alpha)$, $t=\Theta(\log(1/\alpha))$, and
$\varepsilon=(1/40t)$. By applying Lemma A.5 we obtain a set
$X\subseteq\mathbb{F}^{n}$ of size
${\left|X\right|}\geq(\alpha/2)^{O(p/\varepsilon^{2})}\geq\alpha^{O(\log^{3}(1/\alpha))}{\left|\mathbb{F}\right|}^{n}$.
We show below that $X$ satisfies Eq. 6.

Fix $x_{1},\dots,x_{t}\in X$, and let $s=\sum_{i=1}^{t}x_{i}$. Note first that
by setting $B=D$ in Lemma A.5 and combining it with triangle inequality we get
that

${\|\varphi_{s}*\varphi_{A}*1_{D}-\varphi_{A}*1_{D}\|}_{p}\leq
t\cdot\varepsilon\leq 1/40\enspace,$

where the last inequality is by the choice of $\varepsilon=1/40t$. Let
$q=p/(p-1)$, then by the choice of $p=\log_{2}(1/\alpha)$ we have

${\|\varphi_{A}\|}_{q}=\left(\alpha\cdot\frac{1}{\alpha^{q}}\right)^{1/q}=\left(\frac{1}{\alpha}\right)^{1/p}\leq
2\enspace.$

Then, by applying Hölder’s inequality with $q=p/(p-1)$ we get

${\left|\left\langle\varphi_{s}*\varphi_{A}*1_{D}-\varphi_{A}*1_{D},\varphi_{A}\right\rangle\right|}\leq{\|\varphi_{s}*\varphi_{A}*1_{D}-\varphi_{A}*1_{D}\|}_{p}\cdot{\|\varphi_{A}\|}_{q}\leq
1/20\enspace.$

By combining the above inequality with Eq. 5 we get

$\displaystyle\Pr_{a_{1},a_{2}\in A}[a_{1}-a_{2}-s\in D]$ $\displaystyle=$
$\displaystyle\left\langle\varphi_{s}*\varphi_{A}*1_{D},\varphi_{A}\right\rangle$
$\displaystyle=$
$\displaystyle\left\langle\varphi_{A}*1_{D},\varphi_{A}\right\rangle-\left\langle\varphi_{A}*1_{D}-\varphi_{s}*\varphi_{A}*1_{D},\varphi_{A}\right\rangle$
$\displaystyle=$ $\displaystyle\left\langle
1_{D},\varphi_{A}*\varphi_{-A}\right\rangle-\left\langle\varphi_{A}*1_{D}-\varphi_{s}*\varphi_{A}*1_{D},\varphi_{A}\right\rangle$
$\displaystyle\geq$ $\displaystyle(1-\delta/\alpha^{2})-1/20\geq 0.9\enspace,$

as required.

###  A.2 Proof of Lemma A.2

The proof of this step is essentially Section 5 of [Lov15]. The only (minor)
difference is that we work over $\mathbb{F}_{p}$ and not over
$\mathbb{F}_{2}$.

Given the set $X\subseteq\mathbb{F}^{n}$ from Lemma A.1 of size
${\left|X\right|}\geq\alpha^{O(\log^{3}(1/\alpha))}{\left|\mathbb{F}\right|}^{n}$,
we define
${\mathrm{Spec}}_{\gamma}(X)=\\{r\in\mathbb{F}^{n}:{\left|\widehat{\varphi}_{X}(r)\right|}\geq\gamma\\}$.
Since
$\sum_{q\in\mathbb{F}^{n}}{\left|\widehat{\varphi}_{X}(r)\right|}^{2}=\mathbb{E}_{z}[\varphi_{X}(z)^{2}]=1/\alpha$,
it follows that
${\left|{\mathrm{Spec}}_{\gamma}(X)\right|}\leq\frac{1}{\alpha\gamma^{2}}$.
Chang’s lemma provides a non-trivial bound on the dimension of the subspace
containing ${\mathrm{Spec}}_{\gamma}(X)$.

######  Lemma A.6 (Chang [Cha02]).

Let $X\subseteq\mathbb{F}^{n}$ of size
${\left|X\right|}=\beta\cdot{\left|\mathbb{F}\right|}^{n}$, and let
$\gamma>0$. Then

$\dim({\mathrm{Spec}}_{\gamma}(X))\leq
O\left(\frac{\log(1/\beta)}{\gamma^{2}}\right)\enspace.$

Define the subspace
$V={\mathrm{Spec}}_{1/2}(X)^{\perp}=\\{v\in\mathbb{F}^{n}:\left\langle
v,r\right\rangle=0\ \forall r\in{\mathrm{Spec}}_{1/2}(X)\\}$. Lemma A.6
implies that $\dim(V)\geq
n-O(\log^{4}({\left|\mathbb{F}\right|}^{n}/{\left|X\right|}))\geq
n-O(\log^{4}(1/\alpha))$.

We now show that $V$ indeed satisfies the guarantee of Lemma A.2. For
$x_{1},x_{2},\dots,x_{t}\in X$ let $s=\sum_{i=1}^{t}x_{i}$ as in the previous
lemma. By Lemma A.1 for all $x_{1},x_{2},\dots,x_{t}\in X$ we have

$\Pr_{a_{1},a_{2}\in A}[a_{1}-a_{2}-s\in D]\geq 0.9\enspace.$

Next, we are comparing this probability to the following.

$\Pr_{\begin{subarray}{c}v\in V\\\ a_{1},a_{2}\in
A\end{subarray}}[v+a_{1}-a_{2}-s\in D]\enspace.$ (9)

We claim that if we sample $v\in V$, $a_{1},a_{2}\in A$, and
$x_{1},\dots,x_{t}\in X$ uniformly at random (and let
$s=\sum_{i=1}^{t}x_{i}$), then the two quantities are close to each other. We
prove this by rewriting the two probabilities using the Fourier expansion.
Note that the Fourier coefficients of $\varphi_{V}$ are simple to describe
since $V$ is a linear subspace, and they are equal to
$\widehat{\varphi_{V}}(r)=1$ if $r\in V^{\perp}$ and
$\widehat{\varphi_{V}}(r)=0$ otherwise. Therefore,

$\displaystyle\Pr_{\begin{subarray}{c}v\in V\\\ x_{1},\dots,x_{t}\in X\\\
a_{1},a_{2}\in A\end{subarray}}[v+a_{1}-a_{2}-s\in D]$ $\displaystyle=$
$\displaystyle\left\langle\varphi_{V}*\varphi_{A}*\varphi_{-A}*\varphi_{-X}^{(t)},\mathbf{1}_{D}\right\rangle$
$\displaystyle=$
$\displaystyle\sum_{r\in\mathbb{F}^{n}}\widehat{\varphi_{V}}(r)\cdot\widehat{\varphi_{A}}(r)\cdot\widehat{\varphi_{A}}(-r)\cdot\widehat{\varphi_{X}}^{t}(-r)\cdot\overline{\widehat{\mathbf{1}_{D}}(r)}$
$\displaystyle=$ $\displaystyle\sum_{r\in
V^{\perp}}\widehat{\varphi_{A}}(r)\cdot\widehat{\varphi_{A}}(-r)\cdot\widehat{\varphi_{X}}^{t}(-r)\cdot\overline{\widehat{\mathbf{1}_{D}}(r)}\enspace.$

On the other hand

$\Pr_{\begin{subarray}{c}x_{1},\dots,x_{t}\in X\\\ a_{1},a_{2}\in
A\end{subarray}}[a_{1}-a_{2}-s\in
D]=\left\langle\varphi_{A}*\varphi_{-A}*\varphi_{-X}^{(t)},\mathbf{1}\right\rangle=\sum_{r\in\mathbb{F}^{n}}\widehat{\varphi_{A}}(r)\cdot\widehat{\varphi_{A}}(-r)\cdot\widehat{\varphi_{X}}^{t}(-r)\cdot\overline{\widehat{\mathbf{1}_{D}}(r)}\enspace.$

This implies

$\displaystyle{\left|\Pr_{\begin{subarray}{c}v\in V\\\ x_{1},\dots,x_{t}\in
X\\\ a_{1},a_{2}\in A\end{subarray}}[v+a_{1}-a_{2}-s\in
D]-\Pr_{\begin{subarray}{c}x_{1},\dots,x_{t}\in X\\\ a_{1},a_{2}\in
A\end{subarray}}[a_{1}-a_{2}-s\in D]\right|}$ $\displaystyle=$
$\displaystyle\sum_{r\not\in
V^{\perp}}\widehat{\varphi_{A}}(r)\cdot\widehat{\varphi_{A}}(-r)\cdot\widehat{\varphi_{X}}^{t}(r)\cdot\overline{\widehat{\mathbf{1}_{D}}(r)}$
$\displaystyle\leq$ $\displaystyle\sum_{r\not\in
V^{\perp}}{\left|\widehat{\varphi_{A}}(r)\cdot\widehat{\varphi_{A}}(-r)\cdot
2^{-t}\cdot\overline{\widehat{\mathbf{1}_{D}}(r)}\right|}$ $\displaystyle\leq$
$\displaystyle
2^{-t}\sum_{r\in\mathbb{F}^{n}}{\left|\widehat{\varphi_{A}}(r)\cdot\widehat{\varphi_{A}}(-r)\right|}$
By Cauchy-Schwarz $\displaystyle\leq$ $\displaystyle
2^{-t}\sum_{r\in\mathbb{F}^{n}}{\left|\widehat{\varphi_{A}}^{2}(r)\right|}$
$\displaystyle=$ $\displaystyle
2^{-t}\cdot\mathbb{E}_{x\in\mathbb{F}^{n}}[\varphi_{A}^{2}(x)]$
$\displaystyle=$ $\displaystyle\frac{1}{\alpha\cdot 2^{t}}<0.05\enspace,$

where the last inequality holds due to the choice of $t=O(\log(1/\alpha))$.
Therefore,

$\Pr_{\begin{subarray}{c}v\in V\\\ x_{1},\dots,x_{t}\in X\\\ a_{1},a_{2}\in
A\end{subarray}}[v+a_{1}-a_{2}-s\in
D]\geq\Pr_{\begin{subarray}{c}x_{1},\dots,x_{t}\in X\\\ a_{1},a_{2}\in
A\end{subarray}}[a_{1}-a_{2}-s\in D]-0.05\geq 0.85\enspace.$

Finally, we can fix $a_{2}+s$ maximizing the probability, and let $b=-a_{2}-s$
to conclude the proof of Lemma A.2.

###  A.3 Algorithmic construction of the subspace $V$

Given a set $A$ we can construct $V$ using the algorithm described in
[BRTW14]. Indeed, the only ingredients we need for our construction are the
set $X$ from Lemma A.1 and the subspace $V$ guaranteed by Lemma A.2.

A straightforward inspection of the algorithm described in [BRTW14] gives the
desired result. Informally, the algorithm works as follows: The set $X$ is
defined as the set of all $x\in X$ such that

${\|\varphi_{x}*\varphi_{A}*1_{D}-\varphi_{A}*1_{D}\|}_{p}\leq\varepsilon\enspace.$

Note that given $x\in\mathbb{F}^{n}$ we can estimate the norm efficiently (up
to a small error). This gives us a membership oracle to the set $X$.

Given such a query oracle, we can use Goldreich-Levin algorithm over
$\mathbb{F}$ to compute $R={\mathrm{Spec}}_{1/2}(X)$ [Aka08], or more
precisely its superset that is not too large, and using it we define the
subspace $V=\\{v\in\mathbb{F}^{n}:\left\langle v,r\right\rangle=0\;\forall
r\in R\\}$.