Sparse and Accurate Models Towards Interpretable Machine Learning

Abstract

As machine learning models increasingly govern high-stakes decisions in healthcare, finance, and criminal justice, the prevailing "black-box" paradigm has created a critical crisis of transparency. Existing explainable AI efforts largely rely on post-hoc approximations, which often fail to remain faithful to the original model’s logic, creating a dangerous "explanation gap." Furthermore, a persistent misconception suggests the trade-off between interpretability and accuracy -- a belief that has relegated inherently interpretable models to a secondary status, predominantly limited to simple classification tasks.This dissertation challenges these conventions by developing accurate, sparse, and computationally efficient inherently interpretable models for diverse learning tasks beyond classification. To bridge this gap, we employ global optimization techniques and exploit hidden mathematical structures to solve the NP-hard problems of finding optimal sparse models.The research is organized into three core contributions:\begin{itemize}[nosep] \item In regression, we introduce the first method capable of finding provably-optimal sparse regression trees within a practical time frame, overcoming the limitations of greedy heuristics. \item In survival analysis, we provide two novel approaches: a method for learning provably-optimal sparse survival trees and a new optimization framework for sparse Cox Proportional Hazards models that avoids the common issue of loss explosion. \item In multi-output learning, we present the first method that captures the shared structure of multiple correlated targets using a single, sparse model, effectively mitigating the curse of dimensionality. \end{itemize}The results of this work demonstrate that sparse models, when globally optimized, can match or even exceed the predictive performance of complex black-box systems across regression, survival, and multi-output tasks. Ultimately, this dissertation provides the theoretical and algorithmic foundations to prove that sparsity is not a compromise for clarity, but an asset for generalization. These findings empower practitioners in high-stakes environments to deploy transparent AI systems that are human-understandable.