  Crucial for building trust in deep learning models for critical real-world
applications is efficient and theoretically sound uncertainty quantification, a
task that continues to be challenging. Useful uncertainty information is
expected to have two key properties: It should be valid (guaranteeing coverage)
and discriminative (more uncertain when the expected risk is high). Moreover,
when combined with deep learning (DL) methods, it should be scalable and affect
the DL model performance minimally. Most existing Bayesian methods lack
frequentist coverage guarantees and usually affect model performance. The few
available frequentist methods are rarely discriminative and/or violate coverage
guarantees due to unrealistic assumptions. Moreover, many methods are expensive
or require substantial modifications to the base neural network. Building upon
recent advances in conformal prediction [13, 33] and leveraging the classical
idea of kernel regression, we propose Locally Valid and Discriminative
prediction intervals (LVD), a simple, efficient, and lightweight method to
construct discriminative prediction intervals (PIs) for almost any DL model.
With no assumptions on the data distribution, such PIs also offer finite-sample
local coverage guarantees (contrasted to the simpler marginal coverage). We
empirically verify, using diverse datasets, that besides being the only locally
valid method for DL, LVD also exceeds or matches the performance (including
coverage rate and prediction accuracy) of existing uncertainty quantification
methods, while offering additional benefits in scalability and flexibility.
