He, Xi 
ORCID: 0000-0002-4284-9067
(2025).
Recursive optimization: exact and efficient combinatorial optimization algorithm design principles with applications to machine learning.
University of Birmingham.
Ph.D.
This is the latest version of this item.
|
He2025PhD.pdf
Text - Accepted Version Available under License All rights reserved. Download (2MB) | Preview |
Abstract
This 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).
| Type of Work: | Thesis (Doctorates > Ph.D.) | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Award Type: | Doctorates > Ph.D. | |||||||||
| Supervisor(s): |
|
|||||||||
| Licence: | All rights reserved | |||||||||
| College/Faculty: | Colleges > College of Engineering & Physical Sciences | |||||||||
| School or Department: | School of Computer Science | |||||||||
| Funders: | None/not applicable | |||||||||
| Subjects: | Q Science > QA Mathematics > QA75 Electronic computers. Computer science | |||||||||
| URI: | http://etheses.bham.ac.uk/id/eprint/16124 |
Available Versions of this Item
- Recursive optimization: exact and efficient combinatorial optimization algorithm design principles with applications to machine learning. (deposited 13 May 2025 10:18) [Currently Displayed]
Actions
 |
Request a Correction |
 |
View Item |
Downloads
Downloads per month over past year