Exact Partitioning of High-order Models with a Novel Convex Tensor Cone Relaxation
This addresses exact partitioning for high-order models in machine learning, but it appears incremental as it builds on prior literature with a novel relaxation approach.
The paper tackles the problem of exact partitioning in high-order models by formulating it as a tensor optimization problem and relaxing it to a convex conic form, achieving a solution that equals the true group assignment with a statistical upper bound analysis.
In this paper we propose an algorithm for exact partitioning of high-order models. We define a general class of $m$-degree Homogeneous Polynomial Models, which subsumes several examples motivated from prior literature. Exact partitioning can be formulated as a tensor optimization problem. We relax this high-order combinatorial problem to a convex conic form problem. To this end, we carefully define the Carathéodory symmetric tensor cone, and show its convexity, and the convexity of its dual cone. This allows us to construct a primal-dual certificate to show that the solution of the convex relaxation is correct (equal to the unobserved true group assignment) and to analyze the statistical upper bound of exact partitioning.