We introduce an analytic distance function for moderately sized point sets of known cardinality that is shown to have very desirable properties, both as a loss function as well as a regularizer for machine learning applications. We compare our novel construction to other point set distance functions and show proof of concept experiments for training neural networks end-to-end on point set prediction tasks such as object detection. Parametric machine learning models, like artificial neural networks, are routinely trained by empirical risk minimization. If we aim to predict an output y ∈ Y from an input x ∈ X , we collect a training set D of (x, y) pairs and train a parametrized prediction function h θ : X → Y by minimizing DISPLAYFORM0 Here, L : Y × Y → R is a loss function that assigns a scalar loss value to the predictionŷ = h θ (x) for the true value y. Classical machine learning problems allow for standard choices for the loss function. E.g., for regression problems, where y,ŷ ∈ R, it is common to use the squared loss L(ŷ, y) = (ŷ − y) 2 .Assume , however, that we want to train a machine learning system which-given some inputpredicts a set of points. In particular , the ordering of the points is neither semantically meaningful nor in any way consistent across data instances. As an example , one may consider an object detection task such as finding the positions of the black stones on an image of a real-world game of Nine Men's Morris. What should the loss function be in such a case?Naively, we might just impose an arbitrary ordering to the sets and treat them as ordered tuples. However, this conceals an important property of the task, the permutation invariance, from our machine learning system. This property might in fact be crucial to learn such a task efficiently. Instead, we would like our loss function to define a meaningful distance between two sets, which requires such a loss to be permutation-invariant. We discussed a novel point set loss function, which is analytic everywhere, vis-a-vis two other simple alternatives with matching computational complexity for point set prediction tasks as alternatives to more involved approaches BID3 BID2 . Proof of concept experiments showed that end-to-end training with such simple loss functions is a viable approach for point set prediction tasks, such as object detection. We expect that simple constructions such as the "holographic" point set distance introduced here may turn out useful not only for point set predictions, but also as a regularizer, for example to encourage (unsupervised) clustering to align its clusters with the clusters found by an earlier version of the model. We will need the following Lemma, which states that the roots of a complex polynomial continuously depend on its coefficients. DISPLAYFORM0 k=0 c k u k be a monic complex polynomial and factor it as F (u) = (u − a 1 )(u − a 2 ) · · · (u − a N ) with a k ∈ C some ordering of the roots. Then, for every ε > 0 there exists δ > 0 such that every polynomial DISPLAYFORM1 Proof. This is a reformulation of the well-known continuity result, a proof of which can be found, for example, inĆurgus & Mascioni (2006) . One notes that, to first order in a small shift in the coefficients of a polynomial, the shift of the zeros can be found by a single step of Newton-Raphson iteration, except at higher-degree zeros (where the derivative of the polynomial in the denominator also has a zero).We can now prove the Proposition. DISPLAYFORM2 We already observed that L(Ẑ, Z) 2 = 0 if and only ifẐ = σ(Z) for some σ ∈ S N . Now assume L(Ẑ , Z) 2 = 0. To see thatẐ can not be a local minimum, we need to show that for any ε > 0 there DISPLAYFORM3 To construct such a Z , we define the polynomial Q λ : C → C, DISPLAYFORM4 which linearly interpolates between PẐ and P Z . Note that Q λ is monic for λ ∈ [0, 1] and Q 0 = PẐ. Let Z λ be some ordering of the roots of Q λ . Then DISPLAYFORM5 Since we assumed L(Ẑ, Z) > 0, this means that L(Z λ , Z) < L(Ẑ, Z) for any λ > 0. It remains to show that for any ε > 0 there is λ ε > 0 and a permutation σ such that d(Ẑ, σ(Z λε )) < ε. However, since the coefficients of Q λ continuously depend on λ, this follows as a simple consequence of Lemma 1.
Permutation-invariant loss function for point set prediction. Proposes a new loss for points registration (aligning two point sets) with preferable permutation invariant property.  This paper introduces a novel distance function between point sets, applies two other permutation distances in an end-to-end object detection task, and shows that in two dimensions all local minima of the holographic loss are global minima. Proposes permutation invariant loss functions which depend on the distance of sets.