  We are interested in probabilistic prediction in online settings in which
data does not follow a probability distribution. Our work seeks to achieve two
goals: (1) producing valid probabilities that accurately reflect model
confidence; and (2) ensuring that traditional notions of performance (e.g.,
high accuracy) still hold. We introduce online algorithms guaranteed to achieve
these goals on arbitrary streams of data points, including data chosen by an
adversary. Specifically, our algorithms produce forecasts that are (1)
calibrated -- i.e., an 80% confidence interval contains the true outcome 80% of
the time -- and (2) have low regret relative to a user-specified baseline
model. We implement a post-hoc recalibration strategy that provably achieves
these goals in regression; previous algorithms applied to classification or
achieved (1) but not (2). In the context of Bayesian optimization, an online
model-based decision-making task in which the data distribution shifts over
time, our method yields accelerated convergence to improved optima.
