- Rating
- 2
- Confidence
- 2
- Informativeness
- 1
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
This paper studies a number of different metric optimization questions under the relatively new "weak-strong oracle" model. In this model we can query the distance between two points using a strong oracle, which returns the correct distance, or a weak oracle that with probability returns an answer that is within of the true distance, and with probability is "corrupted" and returns an adversarially chosen value. The goal is to give a good approximation to the problem of interest while using very few strong oracle calls (obviously using calls we could figure out all distances and then just solve our problem). Previous work has focused mostly on clustering problems, but this paper gives a variety of new results for many different problems.
They basically break these down into two "types": what they call "Max-Rigidity", where good approximations are possible with few strong oracle queries using an "anchor-median" algorithm (and which are generally maximization problems), and "Min-Fluidity", where essentially nothing nontrivial is possible (and which are generally minimization problems). One can intuitively think of diameter as a prototypical example of "max-rigidity", and closest pair as a prototypical example of min-fluidity. Intuitively, diameter is robust to mistakes: if have the maximum distance then for every other node at least one of the two is far from (by the triangle inequality), so if we sample a bunch of "anchor points" and then use the weak oracle on distances from everyone to , we'll get a good idea of what the maximum distance is. On the other hand, the closest pair is not robust: if you start with something like the uniform metric and hide one extremely short distance in a pair , then there is no way to find this distance unless you actually use the strong oracle on .
For the Max-Rigidity problems they give one meta-algorithm and show that it can be applied to each of the problems individually, and also give nearly-matching lower bounds. For the Min-Fluidity problems they design a general lower-bounding framework and apply it to each of the problems.
Overall, I do not think that this paper is up to the bar for ICLR. While the WSO model is interesting, the algorithms and the lower bounds in this paper are quite straightforward, and the algorithm in particular is just a straightforward adaptation of a previous algorithm used by Bateni et al. for clustering problems. The lower bounds are slightly more technically involved, but follow the obvious lower bound approach of starting with the uniform metric and then either hiding a bad pair (for min-fluidity) or a bad pair of nodes (for max-rigidity). Relatedly, the writing in this paper is a major issue -- perhaps because their techniques are relatively straightforward, they seem to claim a lot of things that are not formally backed up anywhere. At a high level, this paper reads to me as "a collection of pretty straightforward results in an interesting model, tied together through unnecessarily obscure writing".
Critical strengths
- The WSO model has received some attention recently, and this paper gives some tight bounds for a variety of simple questions in this model.
Critical weaknesses
-
The writing of this paper was very strange. To me, it seems like the authors took an interesting new model (WSO), and proved some simple things for some very basic problems. This would be a reasonable contribution, although not quite as interesting as the previous work on WSO which mostly focuses on more interesting problems. But instead, they seem to insist on claiming some kind of generality which the results don't support. Most notably:
-
The first sentence in "Our Contributions" is
In this paper, we perform a comprehensive study over the classes of metric optimization problems that admit guaranteed approximations with a “small number” of strong-oracle queries in the -WSO model.
This is a completely unjustified sentence. In no way is this study comprehensive -- it considers a small number of problems. There is no claim whatsoever that they characterize easy or hard problems, which would be necessary for a "comprehensive" study. More qualitatively, it only considers very "simple" problems, rather than problems that exhibit lots of interesting structure (like the clustering problems considered previously).
-
Possibly as a way of supporting their claim about comprehensiveness, they introduce the "max-rigidity" and "min-fluidity" concepts. But these don't actually mean anything! Neither of them is defined formally anywhere. So of course they cannot prove something like "every problem is one or the other", or even "a wide variety of problems fit inside this framework", since there are no actual definitions. But they seem to informally claim things like this, e.g., referring to their two notions as a "dichotomy" (see just before Corollary D.7) which by definition means that everything is on one side or the other. Again, it seems like they observed that some simple problems admit a similar algorithm (max-rigidity) or a similar lower bound (min-fluidity) and decided for some reason to phrase this as finding something fundamental about problems in the WSO model rather than just the (still reasonably interesting) fact that simple problems are somewhat simple.
-
-
The techniques do not seem super interesting to me, particularly on the upper bound side.
- Their algorithm is essentially a simple variant of a previous algorithm of Bateni et al. So it's hard to see it as much of a contribution -- it was already defined, and doesn't do anything surprising.
- The lower bounds are slightly more interesting, but even here they are relatively simple and dramatically oversold. Their lower bounds are basically of the form "start with the uniform metric, and define a bunch of nearby metrics that cause different answers and argue that many queries are needed to distinguish which metric we're in". This is the obvious approach, and the metrics that they consider are not particularly complicated or surprising. But they try to obscure this by going through various metatheorems and complicated definitions. This isn't valueless, but isn't particularly valuable either. To me, the "right" way to phrase these is to give one of them for a specific problem, and then say "the proofs of the other problems follow similar lines, see the appendix". But they don't do this, possibly because they want to claim more generality about max-rigidity and min-fluidity despite not actually defining either of them. It's hard for me to care too much about the meta-theorems when the class of problems has not actually been formally defined, or even defined informally in a convincing way.
Questions for authors
- Is there an actual definition of max-rigidity and min-fluidity anywhere?
3 comments
The lower bounds are slightly more interesting, but even here they are relatively simple and dramatically oversold. Their lower bounds are basically of the form "start with the uniform metric, and define a bunch of nearby metrics that cause different answers and argue that many queries are needed to distinguish which metric we're in". This is the obvious approach, and the metrics that they consider are not particularly complicated or surprising. But they try to obscure this by going through various metatheorems and complicated definitions.
We believe the meta-theorem's technical contribution is to isolate and prove a reusable information bound for the weak-strong oracle model. The proof accounts for information from unlimited weak queries, establishes the conditional distribution of the hidden perturbation after observing those responses, and couples adaptive strong-query executions until a changed distance is queried. Certificate overlap then bounds how many candidates those queries can expose. The list-recovery statement additionally handles outputs that contain the hidden candidate without identifying it uniquely. These ingredients are proved once, and each application need only supply a metric family, an output-separation or list-recovery condition, and an overlap bound.
This abstraction has concrete uses beyond repeating the closest-pair argument. It yields strong-query lower bounds for diameter approximation, certified 1-center, and exact MST recovery. As detailed in our response concerning clustering, it also recovers the known strong-pair-query lower bounds of Bateni et al. for discrete metric -median and -means using a different metric family construction. Its applicability to extremal distances, sum objectives, and structured outputs demonstrates the benefit of a reusable theorem. We have also modified the presentation in the revised draft to remove claims such as a "comprehensive study" and a formal "dichotomy," and have emphasized the theorem’s sufficient conditions for lower bounds. Our novelty claim concerns this reusable theorem and the quantitative barriers it establishes.
I am going to leave my score where it is.
- While I think the revision has improved the paper, the entire original storyline was about max-rigidity vs min-fluidity. Taking this out makes the paper an essentially different paper altogether, even with the same set of results. If the authors believe that it is not a significantly different paper, then I would find it slightly disturbing that the entire storyline can be replaced without changing the paper. That, to me, indicates a severe disconnect between the writing and the results. So I would encourage the authors to actually spend the time to write a clear and convincing paper and send it to the next appropriate conference.
- Even with the changes to the intro, it still feels to me "like the authors took an interesting new model (WSO), and proved some simple things for some very basic problems" (as I said in my review). As the authors acknowledge, the upper bound is not particularly interesting. And I still don't think the lower bound is particularly exciting. The authors claim in their response that "Our novelty claim concerns this reusable theorem and the quantitative barriers it establishes." But while reusability is certainly a plus, it's not (in my opinion) a huge deal, particularly if the technique itself is relatively straightforward (as in this case).
Thank you for this feedback. We agree that "comprehensive" overstates the scope of our results. We do not characterize all easy and hard problems in the WSO model. We have replaced the opening claim in the updated version and revised the surrounding discussion to distinguish these results from the more general clustering problems studied in prior work.
There is no standalone formal definition of both labels as exhaustive classes of objectives. However, the underlying framework is formally defined. Definitions 4.2 and 4.3 specify perturbation families, certifying sets, certificate overlap, and flagged families, while Definition 5.1 specifies admissible single-edge contraction families. Theorem 4.4 states explicit conditions on these objects and acceptable output sets. In Section 2, we also describe the sparse-certificate mechanism quantitatively. We agree that referring to the informal labels as a "dichotomy" goes beyond these formal statements.
We have removed both labels and the dichotomy claim. Instead, we state the concrete geometric observation that a very short pair can be hidden in a uniform metric without changing any other distances, while making one pair sufficiently long requires neighboring distances to change as well. This observation motivates our examples, but is not a universal distinction between minimization and maximization. The formal general statement is Theorem 4.4, which gives sufficient conditions for a lower bound using a specified family of metrics, acceptable output sets, and certificate overlap.
We agree that the anchor-median method and the general indistinguishability approach are not new. The manuscript directly credits the algorithmic approach:
Our primary contribution is a common lower-bounding framework that establishes both approximation barriers for diameter and impossibility results for the minimization problems studied. For diameter, Theorem 4.8 shows that factors strictly below 2α2 require Ω(n) strong queries, while factors below 2 require Ω(n2) queries. Together with the (2α2+1)-approximation using O(log2n) strong queries, this establishes the necessary quadratic dependence on α. The same framework yields a stronger obstruction for closest pair and several other metric minimization problems, concluding every fixed approximation factor requires Ω(n2) strong queries. Thus, the framework captures both a threshold below which diameter approximation becomes expensive and problems for which no fixed approximation factor permits a sublinear number of queries in the number of candidate pairs.
Thank you for this suggestion. We have improved the order of presentation by placing the concrete examples before the first informal meta-theorem, so that readers encounter the motivation before the terminology. These examples exist in Section 2, where we introduce the uniform-metric contraction example in lines 122-125 and the diameter dilation example in lines 152-158. We have further emphasized these motivating problems in the updated version. In Section 4.3, we also explicitly defer the formal application statements and proofs to Appendix D.3, and the contraction applications are summarized in Table 3, with detailed proofs in Appendix E.2.
The meta-theorem isolates the common information bottleneck for sublinear-query algorithms for the problems we study. The weak oracle leaves many perturbations plausible, while each strong query can distinguish only a limited number. It handles unlimited weak queries and adaptive strong queries once, reducing each application to checking a metric construction, its effect on acceptable outputs, and its certificate overlap. This yields lower bounds for each of the problems we study, and the list-recovery form handles structured outputs. Separate proofs would repeat this analysis, while the reusable theorem instead makes explicit which properties determine each bound.