The big data revolution along with the success of black-box machine learning models have given us access to a large volumes of information. These models are then used to inform all manner of algorithmic and decision-making tasks. However, black-box machine learning models can be unreliable in ways that are hard to predict, and we are far from having a full characterization of the failure modes of these methods. If the black-box model could be arbitrarily wrong, conventional worst-case analysis may suggest that the best an algorithm can do is to ignore it, as it could be as hurtful as it might be helpful. This is pessimistic, as model predictions are often useful and valuable, even if it is hard to predict failure. In many high-stakes applications it is unreasonable, if not irresponsible, to fully disregard model predictions.

An alternative is to evaluate an algorithm both on reliability, and on how well it uses the black-box model. This thesis develops new algorithmic methods that simultaneously utilize the model as well as possible when it is correct, while also remaining robust in the setting where the model is not useful, or even misleading. A key aspect of this thesis is simultaneously providing

(1) pessimistic guarantees: that the method is reliable even when the black-box model is not, and

(2) optimistic guarantees: that the method provably distills useful information if the black-box model provides it.

This work extends the areas of algorithms with predictions and conformal prediction, and develops new algorithmic techniques that make new connections to other areas of algorithms including robust statistics, and online algorithms.