- Rating
- 3
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This paper studies what could be learned about the other candidates after selecting a candidate with a robust -optimality using exact linear measurements. The quality of a candidate is measured by the squared positive part of its cosine similarity with an unknown vector. With the selected candidate's quality, the authors obtain a sharp bound on the remaining uncertainty and provide examples attaining the bound. In addition, they further show how a valid confidence interval for the selected candidate could be used to obtain simultaneous intervals for all candidates. A lower bound is also established for the additional queries needed for precise estimation, allowing randomized adaptive procedures. The established theoretical results are demonstrated by a synthetic example.
Critical strengths
-
Theorem 3 gives a sharp bound on the remaining uncertainty with examples attaining the bound. Its dependence on the selected quality provides a useful understanding of what robust selection reveals about the alternatives.
-
The paper handles the different uncertainty guarantees carefully. The finite-interval result accounts for changes in the widths and locations of the compatible ranges, and Equation (19) shows why simply taking the largest singleton diameter is insufficient. Theorem 7 also establishes the additional-query lower bound under a probability guarantee for every fixed input, which supports the claim that estimating the other candidates more precisely could require additional information even after selection is justified.
Critical weaknesses
My main concern is the relevance to learning might not be sufficiently clear. The analysis assumes exact linear measurements and a strong robust selection condition, while the example shows the calculations for a constructed family, but it is still unclear when useful early stopping occurs in natural learning or optimization problems. The authors also assume that a valid confidence interval for the selected candidate is already available, but do not give a general bound on how many queries are needed to obtain it, which makes the overall query savings difficult to assess.
Questions for authors
Could the authors give a concrete learning or optimization example where exact linear measurements are available and robust selection can stop early? In addition, how many queries are needed in total, including those used to obtain a valid confidence interval for the selected candidate? How does this compare with directly estimating the qualities of all candidates?