{"id":"f2dd9ebe-0214-458d-b1b4-c9329d6371ae","arxiv_id":"2607.08074","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":5,"one_line_summary":"A stochastic cost-benefit greedy algorithm with approximation guarantees is proposed for multi-type sensor placement in linear Bayesian inverse problems, and a non-intrusive BAE-based lower bound on EIG is used for nonlinear problems.","lead":"This paper develops algorithms for placing different types of sensors (different costs, accuracies, or measurement types) to maximize information gain in PDE-based Bayesian inverse problems. A smart generalist might read it to understand how to design cost-effective sensor networks for applications like groundwater monitoring or source detection.","discovery_kind":"unclear","skeptic_critique":{"model":"glm-5.2","headline":"Lower bound (Thm 4.5) is sound; the load-bearing gap is whether the bound is tight enough across designs to preserve ranking — the paper's own framing acknowledges this is unproven.","rationale":"The reader correctly identified the load-bearing assumption: the uniformity of the gap Ψ_MT − Ψ^O_MT across designs. My review confirms this is indeed the weakest link, but it is not a flaw in the theoretical argument — Theorem 4.5 is correctly proven. The issue is that the theorem establishes a bound, while the OED formulation requires the bound to be a good surrogate (i.e., rank-preserving). This gap between 'valid lower bound' and 'effective optimization proxy' is the genuine soft spot. However, the authors are transparent about this limitation (Section 4.3, Section 4.4), the numerical evidence in Section 5.2 is reasonably convincing for the tested regime, and the approach is non-intrusive and practically motivated. The linear-Gaussian results (Section 3, Theorem 3.3) are independently solid with proper approximation guarantees. The paper makes genuine contributions to an underexplored problem (multi-type sensors in PDE-based Bayesian OED). The concern about surrogate quality across designs is a standard limitation of approximate OED methods and does not undermine the paper's core theoretical contributions. An ACCEPT verdict is appropriate; the concern would become actionable only if future applications reveal systematic rank-reversal patterns, which the paper's honest framing already anticipates.","tokens_in":26558,"tokens_out":841,"duration_ms":159808,"concrete_test":"Construct a nonlinear inverse problem where the forward map F(m) has strongly design-dependent nonlinearity — e.g., a parameter-to-observable map where the Jacobian rank/structure varies sharply with sensor location (such as a transport-dominated problem with localized sensors near vs. far from a nonlinear front). Compute both Ψ^O_MT(S) and a nested-MMC estimate of Ψ_MT(S) for a representative set of ~50 designs spanning the objective range. Check whether the ranking correlation (Spearman ρ) between Ψ^O_MT and Ψ_MT drops below ~0.7, which would indicate the gap varies enough to cause rank reversals and surrogate-driven suboptimality.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central theoretical claim — Theorem 4.5, that Ψ_MT ≥ Ψ^O_MT — is correctly proven via the KL chain rule and moment-matching (Lemma 4.3). The proof itself is clean: the gap equals E_{π_d}[D_KL(π_{m|d} ∥ π^O_{m|d})] ≥ 0, which is non-negative by construction. No internal inconsistency exists. The real concern is one step downstream: the paper's OED formulation for nonlinear problems (Section 4.1, Eq. 4.8) uses Ψ^O_MT as the optimization objective, and the justification for this surrogate rests on the assumption that the gap 'does not vary significantly across designs' (paragraph after Theorem 4.5). This is the load-bearing assumption for the *practical* claim, not the theorem itself. The paper provides no theoretical control on how this gap varies with S. In principle, two designs S1, S2 could satisfy Ψ^O_MT(S1) > Ψ^O_MT(S2) while Ψ_MT(S1) < Ψ_MT(S2), if the posterior approximation quality differs substantially across designs. The single numerical example (Section 5.2) shows the surrogate designs outperform random ones and are competitive with NMC-based greedy, but this is one problem with one nonlinearity structure. The concern is not that the theorem is wrong — it is that the gap between 'valid lower bound' and 'effective surrogate objective' is bridged only empirically. This is honestly acknowledged by the authors, which limits the severity.","agreement_with_reader":"agree"},"referee_report":{"model":"glm-5.2","summary":"This paper addresses optimal placement of multi-type sensors (different costs, accuracies, and observation types) for Bayesian inverse problems governed by PDEs. For linear Gaussian inverse problems with uncorrelated noise, the EIG is monotone submodular, and the authors propose a stochastic cost-benefit greedy algorithm (Algorithm 3.1) with an approximation guarantee under knapsack constraints (Theorem 3.3). For nonlinear inverse problems, the authors develop a non-intrusive framework based on the Bayesian approximation error (BAE) approach, constructing a pure-BAE global linear model F_O = Γ_{Fm} Γ_{mm}^{-1}. They prove (Theorem 4.2) that this operator equals the prior expectation of the Jacobian of the parameter-to-observable map, and (Theorem 4.5) that the corresponding pure-BAE EIG is a lower bound on the exact EIG. The methods are demonstrated on a linear source inversion problem and a nonlinear porous-medium flow problem.","tokens_in":26740,"tokens_out":2350,"duration_ms":99069,"significance":"The paper makes two distinct theoretical contributions. First, the stochastic cost-benefit greedy algorithm and its approximation guarantee (Theorem 3.3, Corollary 3.4) extend stochastic greedy methods to the knapsack-constrained submodular setting in a principled way; this is of independent interest beyond sensor placement. Second, the lower bound result (Theorem 4.5) — that the pure-BAE EIG lower-bounds the exact EIG for nonlinear problems with Gaussian priors — provides a rigorous justification for using a computationally cheap surrogate in the OED loop. The connection to the expected Jacobian (Theorem 4.2, a multidimensional Stein's lemma) is a nice interpretive result. The non-intrusive nature of the BAE approach (no adjoint solves needed) is a practical strength. The numerical experiments are reasonably comprehensive, including comparison against NMC-based greedy designs.","major_comments":[{"comment":"Section 4.3, paragraph after Theorem 4.5: The practical justification for using Ψ^O_MT as the OED objective for nonlinear problems rests on the assumption that the gap Ψ_MT − Ψ^O_MT = E_{π_d}[D_KL(π_{m|d} ∥ π^O_{m|d})] does not vary significantly across designs S. The authors acknowledge this is unproven and support it only with the single numerical example in Section 5.2. This is the load-bearing assumption for the practical (nonlinear) claim. While the lower bound theorem itself is correct and cleanly proven, the paper would benefit from either (a) a more detailed discussion of conditions under which the gap is approximately design-independent, or (b) at minimum, a second nonlinear test problem with a different nonlinearity structure to strengthen the empirical evidence. As it stands, the leap from valid lower bound to effective surrogate is bridged by one example.","section":null},{"comment":"Algorithm 3.1, line 4 vs. Lemma 3.2: The algorithm states that R is a 'random subset' of the remaining feasible sensors, which suggests sampling without replacement. However, the proof of Lemma 3.2 (and Lemma A.2) uses a binomial distribution argument that assumes sampling with replacement. This discrepancy should be clarified: is R sampled with or without replacement? If without replacement, the binomial argument in Lemma A.2 needs modification. If with replacement, the algorithm description should say so explicitly, and the practical implications (possibly selecting the same sensor multiple times in the inner loop) should be addressed.","section":null}],"minor_comments":[{"comment":"Section 3.3, Eq. (3.15): The approximation ratio depends on C̄ = max_v c(v), which can be arbitrarily large relative to B, making the bound vacuous in some settings. A brief remark on when this bound is non-trivial (e.g., when costs are within a bounded range of each other) would help the reader calibrate expectations.","section":null},{"comment":"Section 5.2.1: The packing constraint (at most one sensor type per location) is introduced informally. It would help to state precisely how this modifies the optimization problem and why the greedy algorithms still apply (or are heuristically adapted).","section":null},{"comment":"Section 5.2.2: The choice N=5000 samples for BAE statistics is stated as 'sufficiently stable empirically' but no convergence study or sensitivity analysis is provided. A brief remark on how the design quality depends on N would strengthen the practical guidance.","section":null},{"comment":"Section 4.4, last paragraph: The note that lazy evaluations are 'neither justified nor recommended' without submodularity is important but buried. Consider highlighting this more prominently, as practitioners may be tempted to use lazy evaluations based on the linear-case discussion.","section":null},{"comment":"Figure 7 (right): The histogram axis labels and binning are somewhat hard to read. Consider adding tick marks or a summary statistic (e.g., median gap) to aid interpretation.","section":null},{"comment":"Section 2.1: The notation π = N(x̄, Γ_xx) is introduced but the shorthand is used inconsistently; sometimes the full N(·,·) notation is used. Minor consistency fix.","section":null},{"comment":"The reference list includes several 2025–2026 entries (e.g., [3], [5], [38], [41]) that appear to be preprints or forthcoming. Ensure final publication details are updated upon acceptance.","section":null}],"recommendation":"minor_revision","confidential_remarks":"The paper is a solid contribution to the OED-for-PDEs literature. The theoretical results are correct and the proofs are clean. The main concern — that the surrogate quality in the nonlinear case is supported by a single example — is real but the authors are transparent about it. I would not push for major revision on this point alone, but a second nonlinear example or a more thorough discussion of gap behavior would significantly strengthen the paper. The sampling-with/without-replacement ambiguity in Algorithm 3.1 should be resolved before publication as it affects the correctness of the proof."},"author_rebuttal":null,"desk_editor":{"model":"glm-5.2","letter":"This paper does two things worth knowing about. First, it formulates multi-type sensor placement (different costs, accuracies, observation types) as a knapsack-constrained EIG maximization problem and gives a stochastic cost-benefit greedy algorithm with an approximation guarantee in expectation (Theorem 3.3). Second, for nonlinear inverse problems, it proves that the EIG computed from a pure-BAE global linear model is a lower bound on the exact EIG (Theorem 4.5), and shows this operator equals the prior expectation of the Jacobian (Theorem 4.2, a multidimensional Stein's lemma). Both results are cleanly proved from first principles. The lower bound proof goes through differential entropy, moment-matching (Lemma 4.3), and the KL chain rule — no gaps in the logic. The stochastic greedy analysis is a natural adaptation of Mirzasoleiman et al. [34] to the knapsack setting, with the cost-benefit ratio replacing the standard marginal gain. The approximation ratio degrades to (1−e^{−(1−ε)/C}) where C is the max sensor cost, which is reasonable. The numerical experiments are solid: the linear advection-diffusion example confirms the theoretical guarantees hold, and the nonlinear porous-medium example shows the BAE-based designs are competitive with NMC-based greedy at a fraction of the cost. The soft spot is real but honestly acknowledged: Theorem 4.5 gives a valid lower bound, but using it as a surrogate objective requires the gap Ψ_MT − Ψ^O_MT to be roughly uniform across designs. The paper provides no theoretical control on this uniformity — it is bridged only by the single numerical example in Section 5.2. In principle, two designs could have their ranking flipped if the posterior approximation quality varies substantially with S. The authors flag this explicitly (paragraph after Theorem 4.5), which is the right thing to do, but it remains the load-bearing assumption for the practical claim. A second minor issue: submodularity is lost in the nonlinear case due to the non-diagonal total error covariance, so the greedy guarantees from Section 3.3 do not apply there. The authors note this and report good empirical performance anyway, which is consistent with prior experience in the literature but is not theoretically grounded. No code is shipped, which limits reproducibility of the numerical results, though the theoretical claims stand on their own. This is a well-written paper with two genuine contributions — the knapsack-constrained stochastic greedy analysis and the BAE-based EIG lower bound. The gap between 'valid lower bound' and 'effective surrogate' is the main open question, but it is clearly identified and not oversold. It deserves a serious referee.","headline":"Multi-type sensor placement for PDE-based Bayesian inverse problems: knapsack-constrained greedy with BAE-based EIG lower bound for nonlinear problems","tokens_in":27530,"tokens_out":640,"would_cite":true,"duration_ms":104172,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"glm-5.2","headline":"Cheap sensors, pricey sensors: a greedy recipe for picking the best mix","keywords":[],"falsifier":"A nonlinear PDE-based inverse problem where the BAE lower-bound gap Ψ_MT − Ψ^O_MT varies substantially across designs, causing the surrogate-optimal design to be far from the true-EIG-optimal design. Such a counterexample would show that the lower-bound property alone is insufficient to justify the surrogate as an optimization objective.","tokens_in":26779,"feed_emoji":"","tokens_out":1273,"duration_ms":193699,"temperature":0.7,"pith_summary":"This paper solves the problem of where to place sensors—and which kinds to place—when you are trying to infer a hidden field governed by a partial differential equation, and when different sensor types cost different amounts and measure different things. The core formulation reframes the sensor-selection problem as a knapsack-constrained binary optimization: each candidate sensor has a cost and an expected information payoff, and you want the best total payoff under a fixed budget. For the case where the underlying inverse problem is linear and Gaussian with uncorrelated measurement noise, the expected information gain (EIG) is a monotone submodular set function, meaning it has diminishing returns. The authors exploit this structure to design a stochastic cost-benefit greedy algorithm that samples only a subset of candidate sensors per iteration, reducing the number of expensive objective evaluations while retaining an approximation guarantee in expectation. For nonlinear inverse problems, where the EIG has no closed form, they build a global linear surrogate of the parameter-to-observable map using the Bayesian approximation error (BAE) framework. This error-corrected linear model is constructed non-intrusively: you only need prior samples and forward-model outputs, no Jacobians or adjoint solves. The paper's central theoretical result for the nonlinear case is that the EIG computed from this BAE-based linear model is a guaranteed lower bound on the exact EIG. This means maximizing the surrogate objective is principled rather than heuristic: you are optimizing a quantity that provably underestimates the true information gain, and the gap between the two measures how well the linear surrogate captures the posterior on average over the data distribution. The authors also show that the BAE global linear operator equals the prior expectation of the Jacobian of the nonlinear forward map, connecting their construction to the more familiar approach of averaging local linearizations at prior samples.","feed_headline":"","feed_subtitle":"","key_machinery":"The argument rests on three pieces of machinery. First, the knapsack-constrained EIG formulation: each sensor has a cost c(v) and the design must satisfy c(S) ≤ B, replacing the usual cardinality constraint. Second, the stochastic cost-benefit greedy rule, which at each iteration samples T = c(V) log(1/ε)/B candidate sensors and selects the one maximizing the marginal-gain-to-cost ratio Δ(v|S)/c(v); the analysis chains an expected incremental-gain lemma (Lemma 3.2) through an induction to get E[f(S_k)] ≥ (1 − exp(−k(1−ε)/B)) f*. Third, the pure-BAE construction: the global linear operator F_O = Γ_{Fm} Γ_{mm}^{-1} (the cross-covariance of the forward output and the parameter, times the prior-","core_discovery":"The paper establishes that for nonlinear Bayesian inverse problems with Gaussian priors, the expected information gain computed from the pure-BAE global linear model (an error-corrected, data-driven linear surrogate requiring no Jacobian evaluations) is a provable lower bound on the exact EIG. This transforms the surrogate from a heuristic proxy into a principled objective for knapsack-constrained sensor placement. A complementary contribution is the stochastic cost-benefit greedy algorithm, which provides an expected approximation ratio for monotone submodular maximization under knapsack constraints while requiring only O(c(V) log(1/ε)) marginal-gain evaluations.","pith_inferences":["If the BAE lower bound gap varies significantly across designs in some problem class, the method could systematically prefer designs where the linear surrogate is poor rather than where the true information gain is high. The paper's single nonlinear numerical example is insufficient to rule this out for general nonlinear PDE problems with strong non-Gaussian posteriors.","The non-submodularity of the pure-BAE EIG (due to the non-diagonal total-error covariance) means the greedy algorithm's empirical success in the nonlinear case is not covered by the linear-case theory. A problem class where greedy fails for non-submodular objectives would expose the limits of the approach.","Extending the lower-bound argument to non-Gaussian priors introduces a design-independent correction term, which the paper notes but does not develop; whether this correction term is truly design-independent for structured non-Gaussian priors (e.g., mixture priors) is an open question."],"forward_implications":["The stochastic cost-benefit greedy algorithm and its approximation guarantee apply to any monotone submodular maximization problem under a knapsack constraint, not just sensor placement for inverse problems.","The lower-bound result means practitioners can perform nonlinear OED without adjoint solves or Jacobian computations, using only input-output pairs from the forward model—a significant simplification for black-box or legacy simulation codes.","The gap formula Ψ_MT − Ψ^O_MT = E_{π_d}[D_KL(π_{m|d} ∥ π^O_{m|d})] provides a concrete diagnostic: if the gap is roughly constant across candidate designs, the surrogate preserves the ranking of designs and the approach is trustworthy; if it varies, the surrogate may mislead.","The connection to Stein's lemma (Theorem 4.2) suggests that the prior-expected Jacobian could serve as a natural linearization point in other contexts, such as uncertainty quantification or reduced-order modeling, beyond experimental design."],"fun_headline_variants":["BAE-based EIG shown to lower-bound exact EIG for nonlinear Bayesian inverse problems","Knapsack-constrained multi-type sensor placement via stochastic cost-benefit greedy","Error-corrected linear surrogate gives provable EIG lower bound for PDE inverse problems","Cost-benefit greedy for multi-type sensor placement with submodular approximation guarante","Data-driven linear surrogate serves as principled OED objective for nonlinear PDE inversio"],"cache_read_input_tokens":0,"weakest_assumption_plain":"The effectiveness of the pure-BAE EIG as a proxy for the exact EIG in nonlinear problems depends on the gap between the true EIG and the surrogate being roughly uniform across candidate designs. The paper proves the gap is non-negative but provides no theoretical guarantee of its uniformity; the claim rests on a single numerical example.","fun_headline_variants_meta":{"raw":{"variants":["BAE-based EIG shown to lower-bound exact EIG for nonlinear Bayesian inverse problems","Knapsack-constrained multi-type sensor placement via stochastic cost-benefit greedy","Error-corrected linear surrogate gives provable EIG lower bound for PDE inverse problems","Cost-benefit greedy for multi-type sensor placement with submodular approximation guarantees","Data-driven linear surrogate serves as principled OED objective for nonlinear PDE inversion","Stochastic greedy sensor placement under budget constraints with expected approximation ratio","Multi-type sensor placement via submodular maximization with knapsack constraints","BAE global linear model yields lower bound on exact EIG for nonlinear inverse problems","Budgeted sensor selection for Bayesian PDE inversion using error-corrected linearization","Approximate EIG from BAE linearization certified as lower bound for sensor placement OED"]},"model":"glm-5.2","effort":"low","cost_usd":0.0,"raw_usage":{"total_tokens":1124,"prompt_tokens":460,"completion_tokens":664,"prompt_tokens_details":null},"tokens_in":460,"tokens_out":664,"duration_ms":18390,"temperature":1.0,"reasoning_tokens":546,"cache_read_input_tokens":0,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-10T00:30:54.489844+00:00","model_set":{"reader":"glm-5.2"},"falsifier":"A nonlinear PDE-based inverse problem where the BAE lower-bound gap Ψ_MT − Ψ^O_MT varies substantially across designs, causing the surrogate-optimal design to be far from the true-EIG-optimal design. Such a counterexample would show that the lower-bound property alone is insufficient to justify the surrogate as an optimization objective.","supporting_citations":[],"review_version":1}