Towards Scalability and Insight of Machine Learning and Decision-Making Problems

Abstract

Advancing machine learning and decision-making requires not only improving accuracy but also addressing the challenges of scalability and gaining insight into model behavior and problem structure. This thesis examines these dimensions through distinct but complementary studies. First, we investigate integer programming games, applying SAT solvers to compute locally optimal integer solutions (LOIS) in cybersecurity and graph interdiction settings, demonstrating improved scalability compared to traditional solvers. We further extend this investigation by developing LOIS-guided genetic metaheuristics for computing approximate equilibria in integer programming games, integrating local rationality with evolutionary search to achieve scalable and interpretable solutions in complex strategic environments. We analyze the scalability of exact linear programming formulations for Markov decision processes and constrained variants, benchmarking GPU-accelerated solvers against classical value- iteration methods. We explore correlated time-series forecasting by combining multiple kernels within a Sparse Gaussian Process Framework, showing how kernel design influences predictive performance and offering insights into real-world web traffic forecasting. Together, these studies underscore the importance of strategically engineered approaches that achieve scalability and yield broadly applicable insights into the design of solutions for machine learning and decision-making problems.