# Exact Partitioning of High-order Models with a Novel Convex Tensor Cone Relaxation

arXiv: https://arxiv.org/abs/1911.02161 · HTML: https://mlsanity.com/paper/1911.02161/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Nov 2019.

## Built on by (most cited first, 1 of 1)

- [Exact Inference in High-order Structured Prediction](https://mlsanity.com/paper/2302.03236/) (2023)

## Abstract (arXiv)

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'eodory 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.