University of Birmingham
Recursive optimization: exact and efficient combinatorial optimization algorithm design principles with applications to machine learning
Abstract
dc:description.abstractThis thesis presents a generic algorithm design framework for solving combinatorial optimization problems, it subsumes the classical recursive optimization methods, such as greedy, dynamic programming, divide-and-conquer, and branch-and-bound (BnB) methods. In particular, this thesis focuses on solving combinatorial optimization problems in machine learning to demonstrate the effectiveness and practicality of this framework. Our framework is grounded in Bird's theory of the algebra of programming, which is a relational formalism for deriving correct-by-construction algorithms from specifications. We introduce this theory through Haskell code, with a particular emphasis on its application to combinatorial optimization. Additionally, we reformulate the branch-and-bound method to integrate it formally into this framework, thereby establishing a unified approach for designing recursive combinatorial optimization algorithms. More broadly, our theoretical foundation is an integration of constructive algorithmics (or transformational programming), combinatorial generation, and combinatorial geometry. These topics are integrated together to achieve our final goal—designing efficient combinatorial optimization algorithms. They are interconnected in such a way that both geometric algorithms for addressing fundamental combinatorial geometry problems and efficient combinatorial generators can be structured or reformulated systematically using principles from constructive algorithmics. This approach facilitates the design of efficient (in terms of worse-case complexity and parallelizability) geometric algorithms and combinatorial generators that are sound and concise. Moreover, the geometric insights allow us to reveal the combinatorial properties of combinatorial problems, which allows us to significantly simplify the combinatorial complexity of the problem. In addition to providing algorithm design principles, and to demonstrate the effectiveness of our framework, we address four fundamental problems in machine learning: classification, clustering, decision tree, and empirical risk minimization for ReLU neural networks. We provide a detailed analysis of the combinatorial properties of these problems, demonstrating that these problems can be solved in polynomial time. To the best of our knowledge, all algorithms we propose are the fastest known in terms of worst-case complexity, and their performance can be further improved through the acceleration techniques we introduce. Finally, two example problems (the 0-1 loss linear classification problem and the K-medoids problem) are selected to show end-to-end implementations in Haskell. In our experiments, we compare our algorithm with state-of-the-art BnB algorithms. Our method not only provides provably exact solutions but also achieves significantly lower computational time. We demonstrate that the wall-clock time of our algorithm aligns with its worst-case time complexity analysis on synthetic datasets. In contrast, state-of-the-art BnB algorithms for these two problems exhibit exponential time complexity, even in cases where the brute-force algorithm has polynomial time complexity. Moreover, for the K-medoids problem, we demonstrate that a carefully designed brute-force algorithm, leveraging the generator proposed in this thesis, outperforms the state-of-the-art BnB algorithm across all datasets tested. Since a brute-force algorithm is guaranteed to yield the exact solution, our experiments revealed that the state-of-the-art BnB algorithm for the K-medoids problem often produces incorrect results. This highlights the importance of adopting a rigorous framework, like the one proposed here, when designing exact algorithms. Moreover, our contribution to the study of interpretable machine learning is substantial. We believe that some of the algorithms proposed in this thesis will revolutionize the field of interpretable machine learning, as previous research has demonstrated the effectiveness of exact algorithms, even for simplified problems. The solution we propose is more generic (capable of solving a broader range of problems) and efficient (with polynomial-time complexity in the worst case, parallelizable, and amenable to further speed-up).
Degree
thesis:*- Name dc:type.qualificationname
- d_ph
- Level dc:type.qualificationlevel
- d_ph
- Grantor dc:publisher.institution
- University of Birmingham
- Year dc:date.issued
- 2025
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- He, Xi
- ORCID person:identifier.orcid
Subjects
dc:subject × 1Rights
- Language dc:language.dcterms_iso639_2
- eng