This thesis investigates three areas targeted at improving the reliability of machine learning; fairness in machine learning, strategic classification, and algorithmic robustness. Each of these domains has special properties or structure that can complicate learning. A theme throughout this thesis is thinking about ways in which a'plain' empirical risk minimization algorithm will be misleading or ineffective because of a mis-match between classical learning theory assumptions and specific properties of some data distribution in the wild. The overarching research goal for these related topics is to provide a crisp mathematical model for each learning scenario that exposes different failure modes and makes trade-offs between important metrics explicit in order to provide algorithmic advice or recommendations to practitioners and expose gaps for future research. By tuning our learning algorithms to be more distribution specific in these scenarios, the resulting learned system will exhibit higher utility and avoid catastrophic failure modes. This research is grounded in the theory of machine learning and is fundamentally mathematical in nature, with empirical support when appropriate. Theory is particularly important in these sensitive domains as it is unclear which poor behavior in deployed systems is a natural or benign consequence of a learning system with the underlying distribution,contrasting with problematic but correctable behavior caused by an error in algorithm design or implementation, how to mitigate these issues, or what a successful outcome even looks like in each problem. Theoretical understanding in each domain can help guide best practices and allow for the design of effective, reliable, and robust systems.

Patch attacks [Brown et al., 2017, Karmon et al., 2018, Yang et al., 2020] are an important threat model in the general field of test-time evasion attacks [Goodfellow et al., 2014]. In a patch attack, the adversary replaces a contiguous block of pixels with an adversarially crafted pattern. Patch attacks can realize physical world attacks to computer vision systems by printing and attaching a patch to an object. To secure the performance of computer vision systems against patch-attacks, there has been an active line of research for providing certifiable robustness guarantees against them [see e.g., McCoyd et al., 2020, Xiang et al., 2020, Xiang and Mittal, 2021, Metzen and Yatsura, 2021, Zhang et al., 2020, Chiang et al., 2020]. Xiang et al. [2022] recently proposed a state-of-the-art algorithm called Patch-Cleanser that can provably defend against patch attacks. They use a double-masking approach based on zero-ing out two different contiguous blocks of an input image, hopefully to remove the adversarial patch. For each one-masked image, if for all possible locations of the second mask, the prediction model outputs the same classification, it means that the first mask removed the adversarial patch, and the agreed-upon prediction is correct. Any disagreements in these predictions imply that the mask was not covered by the first patch.