Machine learning models increasingly inform high-stakes decisions in healthcare, finance, and criminal justice, where knowing when to trust a prediction matters as much as the prediction itself. However, standard training procedures often fail to produce predictions that stakeholders can trust, particularly in the presence of noise, bias, or adversarial manipulations prevalent in real-world datasets. This thesis addresses the fundamental challenge of designing machine learning algorithms that produce trustworthy predictions about uncertain events. We make several key theoretical and algorithmic contributions across four main areas. First, we establish improved guarantees on the fundamental limits on calibration error in online binary prediction, breaking the long-standing O(T^{2/3}) upper bound of Foster and Vohra (1998); Hart (2023) for the first time in over two decades. We also develop efficient techniques for recalibration using Blackwell’s approachability theorem (Blackwell, 1956) and extend calibration to high-dimensional settings through full swap regret minimization. Second, we develop near-optimal algorithms for omniprediction (Gopalan et al., 2022a)—single models that simultaneously optimize for multiple loss functions—and prove this can be achieved without increasing sample complexity beyond what is necessary for standard loss minimization. Third, we extend these frameworks be- yond binary outcomes to regression and distributional learning. We introduce sufficient statistics for loss minimization, establish tight O(1 / epsilon^{2/3}) bounds on the approximate rank of convex Lipschitz functions, and present algorithms for learning omnipredictors in the regression setting. We also solve the fundamental problem of distribution estimation un- der threshold queries feedback with logarithmic sample complexity. Finally, we address fairness and robustness under adversarial conditions. We show that randomized classifiers can achieve O(alpha) accuracy loss for Demographic Parity and O(sqrt(alpha)) loss for Equal Opportunity under malicious noise rate alpha. We also develop oracle-efficient hybrid learning algorithms that achieve statistical and computational efficiency simultaneously under structured adversaries. A unifying methodological contribution is our systematic application of Blackwell (1956)’s approachability theorem to design learning algorithms with robust guarantees. This work provides both theoretical foundations and practical tools for building machine learning systems that stakeholders can trust, enabling more responsible deployment of algorithmic decision-making in high-stakes applications.