acceptodds
Under review as a conference paper at ICLR 2027

Diversity with Axiomatic Guarantees in Polynomial Time: Resolving an Open Problem on Diversity Measures

Abstract

Mironov & Prokhorenkova (2025) formulated three axioms that a measure of the diversity of objects, given only their pairwise dissimilarities (with no metric assumption), ought to satisfy: monotonicity, uniqueness and continuity. They showed that no measure in their survey satisfies all three, and constructed two measures that do but are -hard to evaluate. They asked whether any measure satisfying the axioms can be computed in practice, or whether all of them are hard. We resolve this open problem in the affirmative. We give an explicit measure , which satisfies all three axioms and is computable to accuracy in time polynomial in , and the input encoding length. It is not an approximation scheme for some other, harder measure: is itself the object that satisfies the axioms. The measure is built in two steps. Maximum diversity in the sense of Leinster & Meckes (2016), namely Leinster-Cobbold diversity maximised over abundance distributions, satisfies all three axioms once integrated over the scale of the exponential similarity matrices, but its single-scale evaluation is -hard in general. Replacing it by its doubly nonnegative relaxation keeps every axiom and yields a convex optimization problem, that can be solved to prescribed accuracy in polynomial time. The relaxation is exact when the dissimilarity is of negative type, including Euclidean, and tree distances. On these distances, coincides with scale-integrated maximum diversity, and its evaluation reduces to convex quadratic programming with one-dimensional numerical integration. The measure is practical to evaluate: on synthetic Gaussian embeddings of objects, evaluation via the convex quadratic formulation takes a median of seconds using quadrature nodes.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
Diversity measure, desirable properties, axiomatic approach, polynomial time

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_JN7iOpenReview ↗
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 Div⁡μ\operatorname{Div} _ {\mu} by integrating a relaxed maximum-diversity objective over similarity scales. For a dissimilarity matrix D=(dij)D=(d _ {ij}), the construction uses exponential similarity matrices Zθ(D)Z _ {\theta}(D) with entries e−θdije^{-\theta d _ {ij}}, together with a doubly nonnegative semidefinite relaxation.

The main theoretical results establish that Div⁡μ\operatorname{Div} _ {\mu} satisfies all three axioms on general dissimilarity matrices and can be evaluated to additive accuracy ε\varepsilon in time polynomial in nn, 1/ε1/\varepsilon, 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, Div⁡μ\operatorname{Div} _ {\mu} 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 Div⁡μ\operatorname{Div} _ {\mu} 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 Div⁡μ\operatorname{Div} _ {\mu} 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 Div⁡μ\operatorname{Div} _ {\mu} is to the choice of the scale distribution μ\mu, beyond the theoretical conditions ensuring the axiomatic guarantees.

1 comment

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 μ\mu. 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, μ\mu only moves the quadrature nodes; the quadrature error bound and the inner optimization problems are unchanged.

Reviewer_QSGfOpenReview ↗
Rating
3(+1)
Confidence
4
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper constructs a diversity measure for symmetric nonnegative dissimilarity matrices with consistent duplicate rows, without assuming the triangle inequality. It replaces maximum Leinster–Cobbold diversity's quadratic minimization by a doubly nonnegative semidefinite relaxation and integrates its reciprocal optimum over exponential similarity scales. An unbounded scale distribution restores strict monotonicity and uniqueness while retaining continuity and duplicate invariance (Theorem 5, pp. 5 and 13–15). For the default density, the measure admits additive-ε evaluation in time polynomial in n, input encoding length, and 1/ε (Theorem 6, pp. 5 and 17–18). The relaxation is exact for positive semidefinite similarities, giving a convex quadratic route on negative-type dissimilarities (Theorem 7/Corollary 8, pp. 6 and 18).

The numerical evidence consists of duplicate-containing square configurations, 25 shared random starts for point optimization, and Gaussian Euclidean embeddings up to 1,000 objects. These establish illustrative behavior and evaluation cost for the quadratic route; downstream application benefits and general-SDP scalability are not established.

Critical strengths
  1. A substantive solution to a precise axiomatic computation problem. Scale integration and the DNN feasible set jointly give all three axioms on the full stated domain, including consistent duplicates, with polynomial additive-accuracy evaluation (Theorems 5–6). The key step is not merely using a convex relaxation: it is proving that relaxation preserves the structural properties required for strictness after integration. This directly addresses the question in Mironov & Prokhorenkova (2025).
  2. A useful computational specialization and careful evidence boundaries. Theorem 7 links the new measure to the familiar quadratic objective on negative-type inputs. PSD exactness is an established property of DNN relaxations (see Gökmen & Yıldırım, Proposition 4.3); the contribution here is its role in the complete axiomatic construction. The 25 shared starts and 40 scaling cases provide accessible illustrations. The paper distinguishes finite-precision evaluation, empirical quadrature refinement, and mathematical guarantees, and does not claim globally optimal point configurations.
Critical weaknesses
  1. The empirical evidence does not evaluate the general computational route that distinguishes the construction. Theorems 5–6 establish the axioms and additive-accuracy tractability on the stated full dissimilarity domain. However, all experiments use Euclidean distances, where the relaxation is exact and evaluation reduces to a convex QP; the supplement explicitly does not implement the general SDP. Thus the experiments do not establish the practical cost or behavior of the relaxed measure outside negative-type inputs. Moreover, Table 1's 1.67-second result measures an 80-node Gauss evaluation: refinement differences and inner QP widths are informative diagnostics, but do not certify total integral error. The paper correctly discloses these distinctions and supplies mathematical error bounds. What remains missing is an empirical connection between the general construction, a specified total accuracy, and actual cost. This is a material limitation of the practical evaluation rather than a theorem defect.

  2. The illustrations leave the practical significance of the chosen measure insufficiently established. The duplicate-containing square examples demonstrate the intended axiomatic behavior, and the 25 shared starts provide useful evidence about local optimization. Their scope remains limited: the contrasts principally expose known failures of Average/Energy, while Energy and the proposed objective both retain 16 distinct points in the optimization experiment. The default scale distribution is used throughout, without a sensitivity study of rankings or optimized configurations. The authors acknowledge that distances and the scale distribution determine which distinctions are rewarded. A focused comparison or behavior-based evaluation could help establish when this choice adds useful discrimination and at what cost. This is a limitation of the acceptance case, not a claim that every theoretical paper requires a downstream benchmark or that the axioms are invalid.

Questions for authors
  1. Can you provide a non-negative-type evaluation of the actual general DNN formulation, reporting runtime, primal/dual feasibility and accuracy diagnostics across a modest range of sizes? Where the original unrelaxed objective is tractable, how do the scores differ? A small controlled study would directly assess the currently unevaluated path.

  2. What is the measured cost of reaching a specified total additive error, accounting for integration and inner optimization, on both the QP and general SDP paths? Equation 20 already provides a basis for integration bounds. Please distinguish such guarantees from the fast Gauss estimate and the empirical 80-versus-160-node change, and explain when small strict improvements are numerically resolvable.

  3. How sensitive are collection rankings and optimized configurations to a fixed reference distance scale and alternative admissible scale distributions? In a focused setting with a stated practical criterion, what useful behavior or tradeoff does the measure offer relative to suitable existing metrics? Per-collection diameter normalization would change the measure and should not be used as if it preserved the axioms.

2 comments

Thank you for the detailed review and specific questions.

Q1. The general formulation on inputs that are not of negative type.

For the setup, sizes and runtime please see 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.

Feasibility and accuracy. Raw solver residuals (positive semidefiniteness, nonnegativity, normalization) are at most 4×10−54\times10^{-5}, but we do not rely on them. At each node we repair the solver output to a feasible matrix, which gives an upper bound on the optimum, and we compute a lower bound from the dual variables as in Appendix G.3. Summed over the 80 nodes, the resulting intervals are at most 10−310^{-3} wide. They cover the inner solves only, not the integration error (see Q2), and as in the paper they are computed in double precision, not machine-verified. For n≤40n\le40, an interior-point solver (Clarabel) agrees with SCS to within 1.3×10−41.3\times10^{-4} at every node.

Relaxed versus unrelaxed. At n=10n=10, where the unrelaxed objective is solved exactly by enumerating supports, the two agree to within 0.003% on all three families, although 23 to 76 of the 80 scales are not positive semidefinite. For n=20n=20 to 8080 the unrelaxed value is only bounded from below by local search, so measured gaps are upper bounds: at most 0.08% on G and N, and up to 9% on A at n=80n=80. A real gap on A is expected, since maximum diversity is NP-hard to approximate on such inputs (Proposition 10).

Q2. Cost of a specified total additive error. We implemented the bracket of Eq. (20) with adaptive bisection and a certified inner interval at every node, and counted solves until the total width, integration plus inner optimization, falls below a target. On the quadratic route (Experiment 3 inputs, n=100n=100), widths of 0.1 and 0.01 take 225 and 2,268 solves (0.35 s and 3.4 s), against 80 solves (0.14 s) for the Gauss estimate. On the semidefinite route (family G, n=40n=40) they take 133 and 1,332 solves (12 s and 124 s), against 15 s. The cost grows like 1/ε1/\varepsilon. As the paper states (Section 8 and Appendix G.3), the 80-node Gauss value is an estimate with no guarantee and the 80-versus-160 difference is an empirical check. In every case we ran, the Gauss value lies inside the certified bracket. A strict improvement is numerically resolvable once the certified width is below the gain, so gains near 10−310^{-3} or smaller are expensive to certify. For pairs ordered by the axioms, the direction is known without computation.

Q3. Sensitivity, and behaviour relative to existing metrics. Sensitivity of rankings and of optimized configurations to μ\mu and to the distance unit is in Part 2 of the general response (Experiments 5 and 6). The unit is fixed in advance and shared by all collections being compared. We agree that per-collection diameter normalization changes the measure, and we do not use it (Section 3).

For a focused comparison we ran one check with a single criterion: does a measure strictly prefer AA to BB when AA is obtained from BB by a move that the axioms declare an improvement? On 3,000 random moves of 16 points in [0,1]2[0,1]^2, Average reverses 44% of the uniqueness moves and the Vendi score 15%. Energy and the DPP log-determinant cannot distinguish the two collections whenever a duplicate remains in both. Divμ\mathrm{Div}_\mu ranks all 3,000 correctly, as Theorem 5 requires, at about 5 ms per evaluation against microseconds for the others.

We hope that our response addresses both weaknesses. If you have any other questions or concerns, we are happy to discuss further.

Thank you for your detailed response and the additional experiments. They have addressed most of my main concerns. I will adjust my ratings.

Reviewer_KKf3OpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The authors construct a diversity measure for a collection of items that satisfies three key axioms: monotonicity, uniqueness, and continuity. Mironov & Prokhorenkova (2025) originally proposed these axioms and introduced two measures that satisfy them but are NP-hard to compute. Unlike previous work, this new measure is computable to epsilon accuracy in polynomial time. Their measure is roughly constructed by first considering an existing notion of diversity called "maximum diversity", which is NP-Hard to compute and can violate monotonicity. They then modify this measure by relaxing its computation and considering a carefully averaged version that they show is monotonic. Empirically, the authors demonstrate on synthetic 2-D datasets with Euclidean dissimilarity that their measure satisfies a visually intuitive notion of diversity and scales well in practice with the number of objects.

Critical strengths
  • This paper resolves an interesting open question of Mironov & Prokhorenkova (2025) by providing an efficiently computable measure of diversity that satisfies 3 desirable axioms. I believe the three axioms Mironov & Prokhorenkova (2025) establish are well motivated; therefore, pursuing a practical measure is worthwhile, and the results are general (not restricted, for example, to Euclidean dissimilarities or requiring the triangle inequality to be respected). The introduced measure is not a direct port of an existing measure; it requires additional techniques (e.g., scale-averaged diversity) to work. The synthetic experimental evidence also supports that this measure performs well in practice.
Critical weaknesses
  • On the whole, I think the writing is acceptable for ICLR, but there are a few examples where the paper is hard to follow. For example, section 4 starts off abruptly with the sentence “The tension is between ignoring duplicates and responding continuously to new objects.”, which is hard to parse. In general, this first paragraph should be rewritten. I think some additional definitions would also be useful. For instance, I couldn’t directly find a definition of “negative-type dissimilarities” or “abundance distributions”.

  • Given the generality of the measure to non-Euclidean dissimilarity data, I would have liked to see more experiments on non-Euclidean data to understand whether we expect the practical performance of the algorithms to continue to hold.

Questions for authors
  • I understand that rho(\theta) = 2/(1+theta)^3 is sufficient to build your computable measure and has certain desirable properties discussed in appendix D. I would like to understand in what sense is this the best choice for rho(\theta). For instance, could we hope for better stability bounds or a better quantitative uniqueness proposition by using a different rho?
2 comments

Thank you for the detailed review and writing improvement suggestions.

Writing. In the revised paper, we have rewritten the opening of Section 4 and added an explicit definition of negative-type dissimilarities to Section 3. The defining condition previously appeared in Corollary 8 in the main text and Proposition 16 in Appendix F; the new definition introduces the terminology earlier and makes it easier to find. We also briefly explain "abundance distribution" at its first use in the text, in Section 2. All changes are marked in blue.

Experiments on non-Euclidean data (general semidefinite formulation). Please see 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.

Is ρ(θ)=2/(1+θ)3\rho(\theta)=2/(1+\theta)^3 the best choice? No single ρ\rho is optimal for both the stability bound and the quantitative uniqueness bound. Either can be improved by another ρ\rho, but only at the expense of the other: the two trade off, and every choice with a finite mean, including ours, is Pareto-optimal. Stability is governed by the mean of μ\mu, and the guaranteed gain from a new object at distance δ\delta by the tail mass of μ\mu beyond about log⁡k/δ\log k/\delta. At equal stability, a heavier tail guarantees more at small δ\delta and less at some larger δ\delta, and a lighter tail the reverse. We chose the default as a simple member, with mean 1 and a closed-form quantile. The short justifications are in the revised Appendix D.

Thank you for your reply. I will maintain my score.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.