6 papers · 1 filter
Deep-ICE: the first globally optimal algorithm for minimizing 0-1 loss in two-layer ReLU and maxout networks
Xi He, Yi Miao, Max A. Little
This paper introduces the first globally optimal algorithm for the empirical risk minimization problem of two-layer maxout and ReLU networks, i.e., minimizing the number of misclas…
Optimal hypersurface decision trees
Xi He
The study of optimal decision trees has gained increasing attention in recent years; however, despite substantial progress, it still suffers from two major challenges: First, trees…
An efficient, provably optimal algorithm for the 0-1 loss linear classification problem
Xi He, Max A. Little
Algorithms for solving the linear classification problem have a long history, dating back at least to 1936 with linear discriminant analysis. For linearly separable data, many algo…
Foundational theory for optimal decision tree problems. I. Algorithmic and geometric foundations
Xi He
In the first paper (part I) of this series of two, we introduce four novel definitions of the ODT problems: three for size-constrained trees and one for depth-constrained trees. Th…
Proper decision trees: An axiomatic framework for solving optimal decision tree problems with arbitrary splitting rules
Xi He, Max A. Little
We present an axiomatic framework for analyzing the algorithmic properties of decision trees. This framework supports the classification of decision tree problems through structura…
EKM: An exact, polynomial-time algorithm for the -medoids problem
Xi He, Max A. Little
The -medoids problem is a challenging combinatorial clustering task, widely used in data analysis applications. While numerous algorithms have been proposed to solve this proble…