acceptodds
Under review as a conference paper at ICLR 2027

WHAT DOES ROBUST SELECTION REVEAL ABOUT THE ALTERNATIVES?

Abstract

Choosing a good candidate need not require estimating every candidate well. We ask how much uncertainty can remain after a choice is already justified. We study unit directions whose quality is the squared positive part of their cosine similarity with an unknown vector. We observe that vector through exact linear measurements. A choice is robustly -optimal if it stays within of the best candidate for every nonzero vector consistent with the measured history. Once the selected direction has been measured, we derive the exact worst-case uncertainty in an alternative's quality, conditional on the selected quality . For , this diameter is below and above it. Matching histories attain both branches. For an already valid selected confidence interval, we derive a location-sensitive bound on simultaneous intervals obtained from the same observations and coverage event. A complementary construction shows that, for , randomized adaptive continuation can require \[ \Omega\!\left(\min\left{m,\varepsilon\eta^2\right}\right) \] additional queries in the worst case, even with the exact norm and selected quality supplied. Here is the unmeasured dimension, is the target interval width, the failure probability is fixed below , and is sufficiently small. These results quantify what robust selection reveals about unselected alternatives and what it can leave unmeasured.

Primary area:
learning theory
Keywords:
candidate geometry, affine comparison, finite-sample coverage

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_tHMyOpenReview ↗
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 ε\varepsilon-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
  1. 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.

  2. 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?

Reviewer_WnuHOpenReview ↗
Rating
3(+2)
Confidence
2
Informativeness
2(+1)
Presentation
2(+1)
Soundness
3
Read review
Paper summary

The paper studies how much information about unselected candidates can be inferred after a robustly near-optimal candidate has been identified, using exact linear measurements. The authors derive bounds on the uncertainty of unselected candidates, use it to construct simultaneous confidence intervals without additional measurements, and establish lower bounds on the measurements needed for finer precision.

Critical strengths

None

Critical weaknesses

Unclear presentation. The paper is difficult to follow. The authors introduce several concepts and technical definitions without clean introduction. In particular, the problem formulation and main theoretical results could be explained more clearly.

Lack of problem motivation. The paper does not provide enough background to motivate the problem being studied.

Questions for authors

Presentation: Could the authors provide some concrete examples to illustrate the overall problem formulation? It would be helpful to give more insight into the main theoretical results before presenting the technical details. Problem motivation: Could the authors elaborate on the motivation for studying uncertainty in unselected candidates? Some practical scenarios in which such estimates are used would benefit the paper.

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

This paper investigates the uncertainty remaining about unselected candidates after robust ε\varepsilon-optimal selection under exact linear measurements. It establishes a sharp and attainable characterization of conditional candidate-quality uncertainty (Theorem 3), derives location-sensitive bounds for simultaneous confidence intervals obtained from an existing selected-candidate interval (Theorem 5), and proves a worst-case lower bound on additional adaptive queries required for finer simultaneous estimation (Theorem 7). The results distinguish the information sufficient for robust selection from that required for precise estimation.

Critical strengths
  1. Theorem 3 establishes an exact and attainable characterization of uncertainty after robust selection, supported by constructive matching examples and rigorous analysis.

  2. Theorem 5 provides location-sensitive simultaneous confidence interval guarantees, while Theorem 7 establishes a complementary adaptive query lower bound, clarifying the distinction between selection and estimation.

Critical weaknesses
  1. The analysis relies on exact noiseless linear measurements, full-fiber robust selection, and a specialized quality function, limiting its applicability to practical stochastic settings.

  2. The general finite-interval bound Gε(L,V)G_\varepsilon(L,V) is not proven tight, while the total calibration cost and practical query efficiency remain insufficiently characterized. The evaluation is limited to a synthetic worked example.

Questions for authors
  1. Can the authors quantify the gap between the general bound Gε(L,V)G_\varepsilon(L,V) and the exact worst-case interval diameter outside the regimes covered by Corollary 6?

  2. How does the total query complexity, including selected-quality calibration, compare with directly estimating all candidate qualities to a prescribed precision?

  3. Which theoretical guarantees remain valid under bounded measurement noise or approximate robust selection, and which fundamentally require exact observations?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.