Back to search

Cornell University

Algorithmic Foundations of Trustworthy Machine Learning

Abstract

dc:description.abstract

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.

Degree

thesis:*
Name thesis:degree_name
Ph. D., Computer Science
Level thesis:degree_level
Doctor of Philosophy
Discipline thesis:degree_discipline
Computer Science
Grantor
Cornell University
Year dc:date.issued
2025

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Okoroafor, Princewill
Chair dc:contributor.chair
  • Kleinberg, Robert
Committee members dc:contributor.committeemember
  • Tardos, Eva
  • Stephens-Davidowitz, Noah
  • Sun, Wen

Subjects

dc:subject × 4

Rights

dc:rights
Statement dc:rights
  • Attribution 4.0 International
Language dc:language.iso
en

Identifiers

dc:identifier.*
Dc Identifier Bibid
17422495
Dc Identifier Other
ProQuest Submission ID: 15251
ProQuest Publication ID: 32171420

Chain of custody

source
Harvested from
Cornell University
Base URL
ecommons.cornell.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Okoroafor, Princewill. Algorithmic Foundations of Trustworthy Machine Learning. Doctor of Philosophy thesis, Cornell University, 2025. https://hdl.handle.net/1813/120753