acceptodds
Withdrawn from ICLR 2027

Certifying Branch and Event Identity in Finite-Budget Nonconvex Tracking

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Finite-budget nonconvex tracking pipelines often accept candidates because they have low residuals or emerge repeatedly from local solves. That evidence is not the same as certifying branch identity or same-branch event identity: an unobserved branch, or a same-branch opposite-event solution, can remain compatible with the public transcript. Adaptive branch-aware certification (ABAC) makes branch and event identity explicit requirements of finite-budget delivery. Its evidence interface lets a selector allocate budget to branch/support probes and event-complement checks, or abstain when the evidence does not support delivery. Under a public-transcript ambiguity model with an explicit dominance-completability condition, we prove that worst-case zero-false delivery over transcript-compatible instances requires both witness types, and a constructive public-query hard family gives a tight m+1 lower bound for per-location evidence acquisition with m alternative branches and one opposite-event location. We instantiate ABAC with a frozen event-margin fallback and abstention. Exploratory nominal-budget results favor coverage, but omit failed-probe costs and permit seed-derived access to the observation-error direction. Our public-input evaluation charges every probe without retuning the threshold. On 640 synthetic transitions from eight held-out seeds, both the fallback and public GCT make 17 reference-matched deliveries; the fallback also makes four false deliveries, versus zero for GCT. Mean accumulated solver cost is 85.74 versus 110.64 iterations, with every transition capped at 120. The paired seed-bootstrap 95% interval for the safe-coverage difference is [-1.09,1.25] percentage points. These results support a cost–risk tradeoff, not coverage or safety dominance. Correctness uses a best-of-192 SLSQP reference, not a global certificate; all 160 prospective states across eight seed trajectories retain their labels after 320 additional starts each. The theoretical contract remains distinct from the empirical gates and their coarse labels.

Primary area:
optimization
Keywords:
selective certification, nonconvex tracking, branch identity, public-query auditing, abstention

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_SKjUOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

The paper studies how to spend a limited optimization budget before deciding whether to return an answer or abstain. There is some sort of branching procedure which searches for a solution satisfying a 'branch/event identity'. There doesn't seem to be an actual description of what the branching procedure is, or what is actually being branched on, which makes it very hard to understand the rest of the paper. Unfortunately the manuscript does not explain its central objects or experimental procedure clearly enough to understand the contribution without reconstructing it from the code, which makes this review very hard to complete.

Critical strengths

Code for experiments with reproduction instructions are provided in the supplementary material. It seems to match the parts of the text I could understand.

Critical weaknesses

There is a significant amount of terminology which is undefined and uncited in the main text. Section 3 starts with "at transition s, a solver produces a dandidate x_0 with branch identity b_0 and event identity e_0". Unfortunately at this stage in the paper I have no idea what any of these things are. The paragraph, and the next paragraph then go on to write about the decisions the 'selector' makes, which is another completely undefined term. This paper seems to be lacking a very basic section which simply describes the system we are studying.

To make matters worse the introduction does not contain a single citation, and the related work section is tiny. As such, it is not possible to work out the meaning of most of the definitions in the paper from the text. Even if it is the case that I am struggling to understand because I have not worked in this specific part of optimization research before, I should be able to at least understand the problem and find a few resources to learn the essentials of the theory from the first sections of the paper.

Because of the issues I have stated above it was very difficult to read the final sections of the paper.

Questions for authors

I have no questions about the theory because my issues with the paper are all related to presentation and description.

Reviewer_TkYiOpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

Nonconvex tracking and constrained decision pipelines often rely on local optimization, by generating candidates from multiple starts, checking the residuals and accepting the most plausible point. This point belongs to one branch of the nonconvex landscape and within that branch it belongs to one active/inactive constraint pattern (event).

Whether this branch and activated event is the optimal one is not certified. The authors formalize this problem as adaptive branch-aware certification. They propose a evidence-acquisition policy with selective branch/event semantics that, given a finite compute budget and only the public transcript, decides how to spend that budget on branch probes and event-complement checks. The algorithm they propose runs one probe with six starts and 11 local iterations each on an instance, compute public probe features, either routes to the event-complement channel (calibrated event margin) or continues and finally delivers iff the selected channels gate passes. Otherwise it abstains.

The paper lacks clarity; definitions are missing and the connection between the theory section and the algorithm is not described in detail. The algorithm section leaves out important details about the implementation, making the results hard to reproduce. While the general idea seems interesting, this leaves me with the impression that this paper needs another round of polishing. I wasn't able to verify the proofs and I am not an expert in this field which is reflected in my confidence.

Critical strengths
  • The idea seems interesting and the authors transparently report limitations.
Critical weaknesses
  • Missing definitions (e.g. GCT) and a loose connection between theory and algorithm. There is a full page left, therefore there would have been enough space to properly introduce every notation and improve clarity.
  • Details about the algorithm and benchmark are missing (e.g. Gate setup), which hurts reproducibility of the results.
Questions for authors
  • What's GCT? this was never defined, right?
  • Could you clarify the connection between the theory section and the algorithm to me? E.g. the role of the branches to visit in the algorithm.
Reviewer_rtZgOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The authors argue that finite-budget nonconvex tracking pipelines often accept candidates with low residuals, which does not certify branch or same-branch event identity. They propose adaptive branch-aware certification (ABAC), which allocates budget to branch and event-complement probes, or abstains when evidence is insufficient. The theory shows that zero-false delivery requires both witness types, with a tight m+1 lower bound on per-location evidence for m alternative branches. On a synthetic benchmark, the method is compared with an obs-µ GCT comparator on safe deliveries, false deliveries, and solver-iteration cost. The evaluations include nominal-budget held-out splits, a blind audit, an exploratory fallback, and a prospective public-input evaluation.

Critical strengths

The distinction between finding a good candidate and certifying its identity is useful, and allowing the pipeline to abstain is a sensible idea. I also appreciate the authors’ transparency about leakage, omitted costs, and negative results. The separate evaluation splits, prospective comparison using public inputs, and additional checks on reference-label stability help make the results easier to assess.

Critical weaknesses

The paper is hard to assess because the optimization problem, benchmark setup, and main comparator are not clearly defined. The theoretical arguments are elementary and do not justify the implemented gates or routing rules. More importantly, the prospective evaluation shows no gain in safe deliveries and more false deliveries than GCT, with no adaptive routing actually taking place. The lower iteration count alone does not make a convincing case for the method. Much of the main-text evidence also involves hidden-parameter access and incomplete cost accounting. Finally, the reference labels come from multistart local optimization rather than certified global optima, and the single synthetic benchmark offers limited evidence of practical value.

Questions for authors
  1. Please give a complete formal definition of the benchmark problem (objective, constraints, dimension, parameter dynamics, uncertainty cells, cap) and of the GCT comparator.
  2. Are there results on a real tracking application, or on at least one additional, standard nonconvex benchmark?
  3. In the prospective evaluation, the fallback routes every arrival to event-complement. Is there any regime in which adaptive routing provides a measurable benefit?

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

Related papers

Discussion (0)

Sign in to comment.