acceptodds
Under review as a conference paper at ICLR 2027

Exchange Barriers and Exact Recovery in Experimental Design

Abstract

Batch active learning and optimal experimental design commonly select measurements through individual acquisition scores or greedy batch construction. We identify information and exchange barriers when a prediction target requires several measurements jointly. The closure objective's submodularity ratio is exactly zero, making ratio-based weak-submodularity guarantees vacuous. Any strategy accessing the instance only through order- information values and purchased responses cannot distinguish two targets whose minimal closing sets are disjoint and have size , regardless of its number of oracle calls. With known features, even greedy selection using exact risk can terminate at strict local optima. For paired designs with cycle-structured nuisance, escaping a complete-pair starting batch requires replacements, where scales nuisance strength and is the budget. The same structure that obstructs local improvement enables global optimization: for paired designs with graph-structured nuisance, we recover hidden measurement pairs from the candidate Gram matrix and compute an exactly optimal batch in polynomial time. These results include full-row-rank designs with positive reconstruction residual. Witness search is polynomial on regular matroids; closing the uniform grand mean is NP-complete on complete three-factor interaction grids. On a real perovskite task, an automatically discovered three-measurement exchange reduces design risk by beyond complete one/two-measurement descent. Removing cross-candidate nuisance correlations while preserving singleton risk and information scores reverses this gain, isolating joint geometry as the mechanism that pointwise acquisition scores leave unresolved.

Primary area:
learning theory
Keywords:
batch active learning, optimal experimental design, data selection, information-theoretic lower bounds, local search, combinatorial optimization, submodularity

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_NNLjOpenReview ↗
Rating
2(+1)
Confidence
2(+1)
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

This paper investigates whether batch measurement selection can capture value that arises only when multiple measurements are acquired jointly. The authors demonstrate that, under the conditions considered, the submodularity ratio of the closure objective is zero, rendering traditional theoretical guarantees based on positive submodularity ratios inapplicable. The paper distinguishes between two types of obstacles—insufficient low-order information and restricted small-scale swaps—and presents results on exact recovery and global optimization for designs with specific pairwise graph structures.

Critical strengths

The authors validate, using real-world data, a scenario where improvement is impossible via single- or double-measurement swaps but achievable through triple-measurement swaps. Furthermore, altering interference correlations while keeping individual scores constant reverses the gains from such swaps, providing compelling evidence for the role of joint geometric structure.

Critical weaknesses

Concepts such as closure, witness, information order, and swap scale are introduced in rapid succession, making the material challenging to grasp. It is recommended to include a simple numerical example prior to the formal definitions and to use a unified diagram to illustrate the relationships between the theorems.

Additionally, it is suggested to strengthen the discussion regarding recent research on batch active learning and experimental design, thereby more clearly articulating the paper's innovations and positioning relative to that work.

Questions for authors

When accounting for overheads such as proposal generation and coefficient optimization, do the advantages of witness swaps over baseline methods—specifically simulated annealing and sparse recovery—persist under a fixed end-to-end time budget?

Reviewer_dVHHOpenReview ↗
Rating
4(+2)
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper provides theoretical insights (both negative and positive) about experimental design for the case where the predictive model is y=φ(x)Tβ+ϵy = \varphi(x)^T \beta + \epsilon, where ϕ(.)\phi(.) is a fixed kernel mapping, and β\beta is to be trained from data. At each stage, there is an already observed pool TT, and the goal is to perchase labels for a set of instances UU such that the error or uncertainty on the query instance qq is minimised.

The paper starts by a negative result about when the coverage of the linear span of T∪UT \cup U on qq (and a measure of it, called submodularity ratio) is used. When submodularity ratio is positive, the greedy algorithm that gradually expands the perchase pool is guaranteed to work, but Theorem 2.2. provides a situation where submodularity ratio is exactly zero.

In Sec. 3. the paper then proceeds to present a similar negative result for a speicifc case (features in −1,0,+1{-1,0,+1}, with exatcly 2 non-zero elements at each row). It is shown that a order-j oracle (that ideally and hypothetically knows about the conditional mutual information of the readout value at any purchasable set AA and qq) fails to reliably find the closing set of size j+1j+1.

In Sec. 3.2 the paper provides another negative result, a case where there are mm bundles and mm distractors, and a C-greedy algorithm ends up in an all-distractor pool S0S_0. Importantly, no exchange in S0S_0 can reduce the risk, unless all instances are replaced by bundle ones, indicating a bad local optimum for the greedy algorithm.

In Sec. 4, an extremely specific case of the pool and problem (several conditions on uiu_is and viv_is) is presented, for which at least 2 positive results are provided: the identifiability of the pairings and factors (Theorem 4.2) and the feasibility of the exact optimal perchase (Theorem 4.3).

Critical strengths
  • The paper provides several negative results about greedy sample aquisition in a reasonably-general experimental design setting.
  • The paper provides several theoretical insights.
Critical weaknesses

I have two major concerns, which if addressed, I'm open to increasing my score in the rebuttal.

  • The setting of Sec. 4 is extremely specific. Besides the specific way that pool samples are created from uiu_is and viv_is, the test deployment instance qq is assumed to be a specific vector, calculated from uiu_is. This setting might significantly limit the application and breadth of the theorey that follows in Sec. 4.

  • The paper has to clearly separate novel findings/insights from the ones that already exist in the literature.

Questions for authors

Please see my comments above.

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

The paper studies budgeted acquisition of measurements whose purpose is to make a deployment query reconstructible (“query closure”) under a linear-Gaussian model. It introduces a witness/query-closure formalism, proves an exact-zero submodularity ratio for closure, gives interaction-order oracle lower bounds and exchange-size barriers, analyzes recovery and global optima in a paired design family, and connects cheapest closing purchases to minimum-weight circuits in a real vector matroid and to sparse recovery. Empirical sections report HOIP, reaction-yield, and resistor-network experiments, with emphasis on cases where local exchange fails and joint witness bundles help.

Critical strengths

1 The paper identifies a genuine and non-obvious failure mode of greedy and local-exchange acquisition under exact reconstruction objectives. The exchange-barrier construction is a useful cautionary result for the active-learning and experimental-design communities.

2 The connection between cheapest closing purchases, matroid circuits, and sparse linear-system optimization is conceptually elegant and could inspire further work at the interface of combinatorial optimization and Bayesian design.

Critical weaknesses

1 The presentation is a major barrier to acceptance. The main text is overloaded with formal notation, while the algorithmic contribution and the recommended practical workflow remain unclear. A reader cannot easily tell which theorem justifies which algorithmic step, or what the authors would actually recommend running on a new problem.

2 The empirical validation is too limited and too disconnected from the theoretical claims. The HOIP and reaction-yield experiments involve small budgets, restricted pools, and a small number of tasks. The paper does not provide a convincing comparison against strong batched Bayesian experimental-design baselines under realistic model misspecification. Consequently, the practical significance of the exchange barrier and witness exchange is not established.

Questions for authors
  1. What is the actual recommended algorithm for a practitioner who has a new design problem and cannot afford the full appendix machinery? Please state the procedure, its assumptions, and its computational cost in one place.
  2. The theoretical lower bounds use carefully constructed instances. To what extent do these constructions reflect behavior on the real HOIP and reaction-yield tasks? Can you quantify how often the predicted local traps occur in the empirical candidate pools?
  3. The empirical comparisons appear to use restricted candidate pools and small budgets. How do the proposed methods compare with BatchBALD, EPIG, and greedy C-optimal under the same full candidate pool and larger budgets, with appropriate statistical uncertainty?
  4. Several claims depend on exact closure and the low-noise limit. How sensitive are the conclusions to finite noise, model misspecification, and non-Gaussian observation models?
  5. The paper argues that interaction-order oracles and exchange-size limits are separate barriers. Can you give a concrete example where an algorithm that respects both limits nevertheless performs well in practice, or argue why such an algorithm cannot exist?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.