AF: MEDIUM: Efficient Algorithms for Learning with Distribution Shift

Machine learning models have demonstrated remarkable capabilities across various domains. However, a fundamental challenge, known as "distribution shift," arises when models trained on one set of data encounter new, different data in deployment, often leading to a significant drop in performance and reliability. This issue is critical in applications like healthcare or autonomous systems, where erroneous predictions can have severe consequences. The goal of this project is to develop novel algorithms that provide provable guarantees on a model's performance even under such distribution shifts, enabling models to either make reliable predictions or to recognize when data is too different and abstain from making a prediction. This project will also contribute to training the next generation of researchers in this area and disseminate findings through workshops and publicly available educational resources. This project will develop and analyze efficient learning algorithms designed to operate robustly under distribution shift, without making any assumptions on the unseen test distribution. The investigators will extend classical learning frameworks to new paradigms, such as Testable Learning with Distribution Shift (TDS learning), where a learner can reject an entire problematic test set, and PQ learning, which allows for instance-level abstention if a significant shift is detected for a particular example. A core focus will be on circumventing the computationally intractable problem of measuring distances between training and test distributions. Instead, the algorithms will output a classifier accompanied by a proof that either the classifier performs optimally on the test set or a significant distribution shift has occurred. Research will also address sequential prediction settings where decisions are made on a sequential (potentially adversarial) stream of data. The theoretical approaches will draw from and establish new connections between machine theory, pseudorandomness, sum-of-squares proofs, robust statistics, and information theory, with empirical validation on standard benchmarks in biology and natural language. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.