  In this work, we consider the problem of building distribution-free
prediction intervals with finite-sample conditional coverage guarantees.
Conformal prediction (CP) is an increasingly popular framework for building
prediction intervals with distribution-free guarantees, but these guarantees
only ensure marginal coverage: the probability of coverage is averaged over a
random draw of both the training and test data, meaning that there might be
substantial undercoverage within certain subpopulations. Instead, ideally, we
would want to have local coverage guarantees that hold for each possible value
of the test point's features. While the impossibility of achieving pointwise
local coverage is well established in the literature, many variants of
conformal prediction algorithm show favorable local coverage properties
empirically. Relaxing the definition of local coverage can allow for a
theoretical understanding of this empirical phenomenon. We aim to bridge this
gap between theoretical validation and empirical performance by proving
achievable and interpretable guarantees for a relaxed notion of local coverage.
Building on the localized CP method of Guan (2023) and the weighted CP
framework of Tibshirani et al. (2019), we propose a new method,
randomly-localized conformal prediction (RLCP), which returns prediction
intervals that are not only marginally valid but also achieve a relaxed local
coverage guarantee and guarantees under covariate shift. Through a series of
simulations and real data experiments, we validate these coverage guarantees of
RLCP while comparing it with the other local conformal prediction methods.
