| Paper ID | MLSP-32.3 |
| Paper Title |
Constant approximation algorithm for minimizing concave impurity |
| Authors |
Thuan Nguyen, Hoang Le, Thinh Nguyen, Oregon State University, United States |
| Session | MLSP-32: Optimization Algorithms for Machine Learning |
| Location | Gather.Town |
| Session Time: | Thursday, 10 June, 15:30 - 16:15 |
| Presentation Time: | Thursday, 10 June, 15:30 - 16:15 |
| Presentation |
Poster
|
| Topic |
Machine Learning for Signal Processing: [MLR-LEAR] Learning theory and algorithms |
| IEEE Xplore Open Preview |
Click here to view in IEEE Xplore |
| Virtual Presentation |
Click here to watch in the Virtual Conference |
| Abstract |
Partitioning algorithms play a key role in many scientific and engineering disciplines. A partitioning algorithm divides a set into a number of disjoint subsets or partitions. Often, the quality of the resulted partitions is measured by the amount of impurity in each partition, the smaller impurity the higher quality of the partitions. Let $M$ be the number of $N$-dimensional elements in a set and $K$ be the number of desired partitions, then an exhaustive search over all the possible partitions to find a minimum partition has the complexity of $O(K^M)$ which quickly becomes impractical for many applications with modest values of $K$ and $M$. Thus, many approximate algorithms with polynomial time complexity have been proposed, but few provide the bounded guarantee. In this paper, we propose a linear-time algorithm with a bounded guarantee based on the maximum likelihood principle. Furthermore, the guarantee bound of the proposed algorithm is better than the state-of-the-art method in \cite{cicalese2019new} for many impurity functions, and at the same time, for $K \ge N$, the computational complexity is reduced from $O(M^3)$ to $O(M)$. |
