- Rating
- 4
- Confidence
- 2
- Informativeness
- 3
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
The paper addresses an open problem posed by Mironov and Prokhorenkova (2025): whether there exists a computationally tractable diversity measure satisfying monotonicity, uniqueness, and continuity.
The authors construct a measure by integrating a relaxed maximum-diversity objective over similarity scales. For a dissimilarity matrix , the construction uses exponential similarity matrices with entries , together with a doubly nonnegative semidefinite relaxation.
The main theoretical results establish that satisfies all three axioms on general dissimilarity matrices and can be evaluated to additive accuracy in time polynomial in , , and the input encoding length. For dissimilarities of negative type, the relaxation is exact, and evaluation reduces to convex quadratic programming.
Critical strengths
The main strength of the paper is its theoretical contribution. The construction of a polynomial-time computable diversity measure satisfying monotonicity, uniqueness, and continuity resolves a concrete open problem in axiomatic diversity measurement.
The proposed approach is mathematically interesting. In particular, the combination of integration over similarity scales with a doubly nonnegative relaxation provides a natural way to address both the failure of strict monotonicity at individual scales and the computational hardness of maximum diversity. The resulting guarantees hold for general dissimilarity matrices, without requiring the triangle inequality.
Another important aspect is the exactness result for negative-type dissimilarities. In this setting, coincides with scale-integrated maximum diversity, and evaluation can be performed using convex quadratic programming rather than a general semidefinite program.
Critical weaknesses
The main limitation is the relatively restricted empirical evaluation. The experiments focus primarily on synthetic Euclidean data, for which the exactness of the relaxation permits the use of convex quadratic programming. The practical computational cost of evaluating through the general semidefinite formulation is therefore not explored in comparable detail.
Questions for authors
Could the authors comment further on the practical computational complexity of evaluating for dissimilarities that are not of negative type, where the general semidefinite formulation is required?
It would also be interesting to understand how sensitive the numerical behavior of is to the choice of the scale distribution , beyond the theoretical conditions ensuring the axiomatic guarantees.
Thank you for the detailed review and the positive assessment.
General semidefinite formulation. The empirical evaluation and computational cost of the general semidefinite formulation, for inputs that are not of negative type, are in Part 1 of the general response (Experiment 4 in the revised paper). In short, evaluation continues to work on inputs that are not of negative type, at a much higher cost: about a minute for 80 objects. We will add the semidefinite programming code for the general case to the repository.
Choice of the scale distribution. Please see Part 2 of the general response (Experiments 5 and 6 in the revised paper). Comparisons decided by the axioms are the same for every admissible μ. In Experiment 5 we measured how often a different scale distribution changes which of two collections scores higher: at least 95% of pairs keep their order. In Experiment 6 we optimized point configurations under several scale distributions and then scored each result under the default: 24 of 25 results are within 0.1% of the best default-optimized configuration. On numerical behaviour, μ only moves the quadrature nodes; the quadrature error bound and the inner optimization problems are unchanged.