  Accounting for the uncertainty in the predictions of modern neural networks
is a challenging and important task in many domains. Existing algorithms for
uncertainty estimation require modifying the model architecture and training
procedure (e.g., Bayesian neural networks) or dramatically increase the
computational cost of predictions such as approaches based on ensembling. This
work proposes a new algorithm that can be applied to a given trained neural
network and produces approximate prediction intervals. The method is based on
the classical delta method in statistics but achieves computational efficiency
by using matrix sketching to approximate the Jacobian matrix. The resulting
algorithm is competitive with state-of-the-art approaches for constructing
predictive intervals on various regression datasets from the UCI repository.
