{"id":"708fc0d4-8e6a-4a73-a4b3-ed4fd8b0385e","arxiv_id":"2607.06642","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Greedy myopic Bayesian active learning for linear regression achieves risk within a factor linear in the maximum initial leverage score of optimal, and this factor is tight.","lead":"The paper proves that the greedy (myopic) algorithm for Bayesian linear regression active learning has risk at most roughly MILS + 1.58 times optimal, where MILS is the largest initial leverage score. This is the first constant-factor guarantee on residual risk itself (not just risk reduction) and is tight up to a constant.","discovery_kind":"extension","skeptic_critique":{"model":"grok-4.5","headline":"No significant objection identified","rationale":"The reader's weakest-assumption note correctly flags the matrix identities underlying Lemma 1, yet those identities are standard and are applied only where they are valid. The remainder of the argument (approximate-submodularity ratio, conversion to a risk ratio via Proposition 1, and the matching Hadamard construction) is self-contained and free of free parameters or circular steps. Consequently the ACCEPT verdict with low correctness risk stands; no adjustment is warranted.","tokens_in":15369,"tokens_out":366,"duration_ms":4508,"concrete_test":"Independently recompute the four numerical checks already present in Appendices C and D (ConstructedProblem for h=10,100,1000 and the RandomProblem d=20,n=1000 trajectory) from the supplied code snippets; confirm that the observed ratios equal (1+h)/5 and that the Chamon-style reduction bound becomes vacuous while the new bound remains informative. Any discrepancy larger than floating-point noise would indicate an implementation or transcription error.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim (Theorem 1) rests on a short chain of classical matrix identities (Cauchy-Schwarz for traces, monotonicity of the Loewner order, Sherman-Morrison) that are applied correctly in the proof of Lemma 1. The same identities are used only in regimes where they hold (symmetric positive-definite matrices). The matching lower-bound construction (Theorem 2 / Lemma 3) is fully explicit and numerically verified for the base case d=4. No hidden assumption, free parameter, or gap in the approximation chain is present that would threaten the stated guarantee.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","summary":"The paper studies the greedy algorithm for A/V-optimal experimental design (equivalently, myopic Bayesian active learning for linear regression), which selects a cardinality-k set S minimizing the risk f(S) = tr((Λ + ∑_{i∈S} v_i v_i^T)^{-1}). It proves that the reciprocal risk F_reciprocal = 1/f is approximately submodular with submodularity ratio γ ≥ 1/(1 + h_max), where h_max is the maximum initial leverage score max_i v_i^T Λ^{-1} v_i. Invoking Das–Kempe then yields the risk approximation guarantee f(S_greedy)/f(S*) ≤ h_max + 1/(1 − 1/e) ≤ h_max + 1.582 (Theorem 1). A matching lower-bound family based on Hadamard matrices shows that a linear dependence on h_max is necessary up to an absolute constant (Theorem 2 / Lemma 3). Numerical checks confirm both the construction and the comparative tightness of the new bound versus prior reduction-based guarantees.","tokens_in":15473,"tokens_out":850,"duration_ms":19626,"significance":"If correct, this is the first non-vacuous approximation ratio on the risk itself (rather than on risk reduction) for the classical greedy heuristic in A/V-optimal design. The identification of MILS as the governing parameter is clean and new, the upper-bound proof is a short chain of classical matrix identities (trace Cauchy–Schwarz, Loewner monotonicity, Sherman–Morrison), and the lower-bound construction is fully explicit and numerically verified. The result also supplies the first rigorous link between one-step myopic selection and multi-step optimality for Bayesian linear regression, a setting that underpins many practical active-learning heuristics. Machine-readable proofs and reproducible code snippets in the appendices further strengthen the contribution.","major_comments":[{"comment":"Equation (3) defines S* = arg max f(S), yet the problem statement and Algorithm 1 both minimize f. The subsequent theorems correctly treat the minimization ratio, so this is an isolated but load-bearing notational error that must be corrected to arg min.","section":null},{"comment":"Section 7 (Discussion) states the result for “Bayesian Logistic Regression.” The entire development (model, risk, proofs) is for linear regression; the logistic claim is unsupported and should be removed or deferred to future work.","section":null}],"minor_comments":[{"comment":"Proposition 1 and Theorem 1 write the constant as 1.582; a parenthetical note that 1/(1−1/e) ≈ 1.58198 would improve precision.","section":null},{"comment":"Figure 1 caption and the surrounding text refer to “Chamon and Ribeiro [2017]” but never display the corresponding α-values used for the plotted lower bound; a short table or inline formula would aid reproducibility.","section":null},{"comment":"In the proof of Lemma 1 (restated), the transition from (26) to (27) invokes “definition of h_max and monotonicity of X^{-1}”; an explicit citation of the Loewner-order fact would make the step self-contained.","section":null},{"comment":"Appendix C code uses math.exp without an import; a one-line fix would make the snippet immediately executable.","section":null},{"comment":"Typographical inconsistencies appear in several places (e.g., “acheives”, “tomopicBayesian”, missing spaces around operators). A careful copy-edit pass is needed.","section":null}],"recommendation":"minor_revision","confidential_remarks":"The manuscript is technically solid and fills a genuine gap. The two major comments are pure errata; once fixed the paper is ready for acceptance. Scope fits a theory-oriented ML or optimization venue well."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"The one thing worth knowing is that this paper finally gives a multiplicative guarantee on residual risk itself (not risk reduction) for the greedy/myopic algorithm in Bayesian linear regression / A-V optimal design. Prior bounds (Bian et al., Chamon & Ribeiro) only controlled how much risk is removed and become vacuous once the residual is small; this one does not.\n\nWhat is new is clean. They work with the reciprocal risk F = 1/f, prove its submodularity ratio is at least 1/(1 + h_max) via a short chain of classical matrix facts (trace Cauchy-Schwarz, Loewner monotonicity, Sherman-Morrison), invoke Das-Kempe, and obtain f(greedy)/f(opt) ≤ h_max + 1/(1-1/e) ≤ h_max + 1.582. They then build an explicit Hadamard-based family showing the ratio is at least (1+h)/5, so the linear dependence on MILS is necessary. The proofs are fully written out, the base-case construction is numerically verified, and the illustrative simulation correctly shows when the older reduction bounds go to zero while theirs remains informative. Code snippets are included.\n\nSoft spots are minor and proportionate. The absolute constant is a bit loose (their own numerics suggest something closer to 3.2 is possible for large d), the discussion briefly says “Bayesian Logistic Regression” when the whole paper is linear, and the result is confined to the linear/Gaussian setting where adaptivity is irrelevant. None of that touches the central claim. The matrix identities hold in the regimes used; there is no free parameter or circularity.\n\nThis is for people who care about theoretical guarantees for experimental design and myopic active learning. A serious referee should see it. I would accept it for peer review and would cite the MILS bound when I next need a residual-risk statement for greedy A-optimal design.","headline":"First non-vacuous residual-risk approximation for greedy A/V design, linear in MILS and tight up to a constant; clean matrix proof, matching hard instance, no load-bearing gaps.","tokens_in":16101,"tokens_out":499,"would_cite":true,"duration_ms":6118,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.5","headline":"Greedy (myopic) selection for Bayesian linear regression risk is within a factor linear in the maximum initial leverage score of the optimal set.","keywords":["active learning","Bayesian linear regression","A-optimal design","V-optimal design","greedy algorithm","approximate submodularity","leverage score","myopic planning"],"falsifier":"Construct (or sample) a Bayesian linear-regression instance whose maximum initial leverage score is moderate, compute both the true optimal set of size k and the greedy set, and check whether the observed risk ratio exceeds the claimed linear upper bound or falls below the matching lower-bound construction.","tokens_in":16234,"feed_emoji":"📐","tokens_out":699,"duration_ms":6936,"temperature":0.7,"pith_summary":"Active learning and optimal experiment design both ask which inputs to observe under a budget so that estimation or prediction risk is as small as possible. For Bayesian linear regression the risk does not depend on the observed labels, so the offline greedy algorithm is exactly the myopic one-step policy used by most practical Bayesian active learners. Prior guarantees only controlled how much risk is reduced; those bounds become vacuous when the residual risk is small. This paper proves the first constant-factor guarantee on the residual risk itself: the risk of the greedy set is at most roughly (h_max + 1.58) times the optimal risk, where h_max is the largest leverage of any single candidate under the prior precision. A matching hard instance shows that a linear dependence on h_max is necessary. The result therefore tells practitioners when myopic selection is nearly as good as multi-step planning and when it can fail badly.","feed_headline":"Greedy risk stays within a leverage-score factor of optimal","feed_subtitle":"Myopic Bayesian active learning for linear regression is proven near-optimal when initial leverages are small","key_machinery":"Approximate submodularity of the reciprocal risk F_reciprocal = 1/f. Lemma 1 proves that its submodularity ratio is at least 1/(1+h_max) by a matrix Cauchy–Schwarz identity, monotonicity of the inverse, and the Sherman–Morrison formula; Das–Kempe then converts the ratio into the claimed risk guarantee.","core_discovery":"For the risk f(S) = tr((Λ + ∑_{i∈S} v_i v_i^T)^{-1}), the greedy set satisfies f(S_greedy)/f(S*) ≤ h_max + 1/(1-1/e) ≤ h_max + 1.582, where h_max = max_i v_i^T Λ^{-1} v_i is the maximum initial leverage score. The bound is tight up to an absolute constant: there exist instances on which the ratio is already at least (1+h_max)/5.","pith_inferences":[],"forward_implications":[],"fun_headline_variants":["Greedy risk stays linear in max initial leverage score","Myopic active learning risk bounded by MILS plus constant","First tight approx ratio for greedy Bayesian linear regression","Greedy set risk ≤ h_max + 1.58 times optimal risk","Max initial leverage controls greedy active learning gap"],"cache_read_input_tokens":128,"weakest_assumption_plain":"The whole chain rests on a matrix Cauchy–Schwarz inequality that must hold for the particular positive-definite matrices that appear after any partial selection; if that inequality failed for those matrices the submodularity-ratio lower bound would collapse.","fun_headline_variants_meta":{"raw":{"variants":["Greedy risk stays linear in max initial leverage score","Myopic active learning risk bounded by MILS plus constant","First tight approx ratio for greedy Bayesian linear regression","Greedy set risk ≤ h_max + 1.58 times optimal risk","Max initial leverage controls greedy active learning gap"]},"model":"grok-4.5","effort":"low","cost_usd":0.004308,"raw_usage":{"total_tokens":1184,"prompt_tokens":699,"num_sources_used":0,"completion_tokens":82,"cost_in_usd_ticks":43080000,"prompt_tokens_details":{"text_tokens":699,"audio_tokens":0,"image_tokens":0,"cached_tokens":0},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":403,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":699,"tokens_out":82,"duration_ms":4749,"temperature":1.0,"reasoning_tokens":403,"cache_read_input_tokens":0,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-11T00:41:14.779682+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"Construct (or sample) a Bayesian linear-regression instance whose maximum initial leverage score is moderate, compute both the true optimal set of size k and the greedy set, and check whether the observed risk ratio exceeds the claimed linear upper bound or falls below the matching lower-bound construction.","supporting_citations":[],"review_version":1}