  Conformal prediction is a popular, modern technique for providing valid
predictive inference for arbitrary machine learning models. Its validity relies
on the assumptions of exchangeability of the data, and symmetry of the given
model fitting algorithm as a function of the data. However, exchangeability is
often violated when predictive models are deployed in practice. For example, if
the data distribution drifts over time, then the data points are no longer
exchangeable; moreover, in such settings, we might want to use a nonsymmetric
algorithm that treats recent observations as more relevant. This paper
generalizes conformal prediction to deal with both aspects: we employ weighted
quantiles to introduce robustness against distribution drift, and design a new
randomization technique to allow for algorithms that do not treat data points
symmetrically. Our new methods are provably robust, with substantially less
loss of coverage when exchangeability is violated due to distribution drift or
other challenging features of real data, while also achieving the same coverage
guarantees as existing conformal prediction methods if the data points are in
fact exchangeable. We demonstrate the practical utility of these new tools with
simulations and real-data experiments on electricity and election forecasting.
