I present CELLO, an algorithm for predicting the covariances of any Gaussian model used to account for uncertainty in a complex system. The primary motivation for this work is state estimation; often, complex raw sensor measurements are processed into low dimensional observations of a vehicle state. I argue that the covariance of these observations can be well-modelled as a function of the raw sensor measurement, and provide a method to learn this function from data. This method is computationally cheap, asymptotically correct, easy to extend to new sensors, and noninvasive, in the sense that it augments, rather than disrupts, existing filtering algorithms. I additionally present two important variants; first, I extend CELLO to learn even when ground truth vehicle states are unavailable; and second, I present an equivalent Bayesian algorithm. I then use CELLO to learn covariance models for several systems, including a laser scan-matcher, an optical flow system, and a visual odometry system. I show that filtering using covariances predicted by CELLO can quantitatively improve estimator accuracy and consistency, both relative to a fixed covariance model and relative to carefully tuned domain-specific covariance models.