Submodular Hamming Metrics
We show that there is a largely unexplored class of functions (positive polymatroids) that can define proper discrete metrics over pairs of binary vectors and that are fairly tractable to optimize over. By exploiting submodularity, we are able to give hardness results and approximation algorithms for optimizing over such metrics. Additionally, we demonstrate empirically the effectiveness of these metrics and associated algorithms on both a metric minimization task (a form of clustering) and also a metric maximization task (generating diverse k-best lists).
First, I must say that the paper was very well written and was a joy to read.The authors analyse metrics of the form d(A, B) = F(A \triangle B), where F is a positive polymatroid function. As the authors state, it was known that even a weaker condition is sufficient for metricity, and the authors analyse the benefits of the additional submodular assumption. The resulting analysis is for both minimizing and maximizing the sum of distances. The algorithms mostly rely on approximating F(A \trinagle B) by F(A \ B) + F(B \ A), which is submodular in A and is a 2-approximation (as they prove). Moreover, this seems to hold even when f is only subadditive and positive, not necessarily submodular. Can the authors please clarify this?The theoretical results seem correct and they are clearly presented. I went only through some of the proofs, and they were also well written and easily understandable.The authors propose two new algorithms for minimization. It is a bit disappointing that in the homogeneous case, they could not improve on the existing algorithm B-Bound, which makes a much weaker assumption. I would have been much happier if there were experimental results for minimization as well, as it is not clear if this is due to the looseness of the bound of Union-Split. The proposed algorithm (Major-Min) for the constrained case is very natural as the same strategy (minimize the upper bound from a supergradient) has been already used.For maximization, the authors suggest the same approximation strategy and then their results follow from the 2-approximation. I believe that it would be more instructive if the authors present the fact that the maximization of any positive symmetric submodular function is a special case for m=2 in the main paper.Here are some questions I have regarding the experimental section: * You claim that the greedy algorithm has a 1 - 1/e approximation guarante for HM,  but adding the |A \triangle A_i| term destroys the monotonicity of the objective.  Isn't this a mistake? * Did you try experimenting with alpha * hamming? I would be interested in the  results under such a simple modification of the baseline model. * Do you present variance, or standard error in the results? Almost all of the  intervals seem to be significantly overlapping.