Pith. sign in

REVIEW 2 major objections 5 minor 20 references

The Approximation Ratio for the Risk of Myopic Bayesian Active Learning for Linear Regression

T0 review · 2 major / 5 minor · reviewed 2026-07-11 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Greedy (myopic) selection for Bayesian linear regression risk is within a factor linear in the maximum initial leverage score of the optimal set.

desk verdict 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. read the letter →

arxiv 2607.06642 v1 pith:DNRSHEZQ submitted 2026-07-07 cs.LG

Stephen Mussmann This is my paper · ORCID
classification cs.LG
keywords activelearningBayesianlinearregressionA-optimaldesignV-optimalgreedyalgorithmapproximatesubmodularityleveragescoremyopicplanning
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 5 minor

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.

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 (2)
  1. 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.
  2. 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.
minor comments (5)
  1. Proposition 1 and Theorem 1 write the constant as 1.582; a parenthetical note that 1/(1−1/e) ≈ 1.58198 would improve precision.
  2. 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.
  3. 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.
  4. Appendix C code uses math.exp without an import; a one-line fix would make the snippet immediately executable.
  5. Typographical inconsistencies appear in several places (e.g., “acheives”, “tomopicBayesian”, missing spaces around operators). A careful copy-edit pass is needed.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: self-contained matrix inequalities plus off-the-shelf approximate-submodularity theorem

full rationale

The derivation chain for Theorem 1 is: (i) define F_reciprocal = 1/f, (ii) prove via classical trace Cauchy-Schwarz (Lemma 2), Loewner monotonicity and Sherman-Morrison that its submodularity ratio satisfies γ ≥ 1/(1+h_max) (Lemma 1), (iii) invoke the black-box guarantee of Das & Kempe (or Bian et al. with α=1) to obtain a constant-factor guarantee on F_reciprocal, (iv) algebraically invert to a linear bound on the risk ratio. None of these steps defines a quantity in terms of the target ratio, fits a free parameter to the hard instances, or relies on a self-citation for uniqueness or an ansatz. The matching lower-bound construction (Theorem 2 / Lemma 3) is an independent, fully explicit family of matrices (diagonal Λ plus scaled Hadamard columns) whose greedy-vs-optimal gap is computed directly and verified numerically; it does not feed back into the upper-bound proof. External citations (Nemhauser, Das-Kempe, Bian, Chamon-Ribeiro) are used only as standard black boxes. Consequently the claimed approximation ratio is not forced by construction or by self-reference.

Assumptions & free parameters 0 free parameters · 4 assumptions · 1 invented entities

The result rests entirely on classical linear-algebra identities and one external approximate-submodularity theorem; no free parameters are fitted and the only new named object (MILS) is simply the maximum of already-defined leverage scores. The ledger therefore contains only standard mathematical background and the problem-dependent quantity that the paper itself introduces and proves necessary.

assumptions (4)
  • standard math Matrix Cauchy-Schwarz: tr(X^T Y)^2 <= tr(X^T X) tr(Y^T Y) for compatible matrices (used to prove Lemma 2).
    Invoked verbatim in the proof of Lemma 2; classical and uncontroversial.
  • standard math Sherman-Morrison formula for rank-one updates of the inverse.
    Used repeatedly to express marginal risk reductions; standard linear-algebra identity.
  • standard math Das & Kempe (2018) / Bian et al. (2017) greedy guarantee for set functions with submodularity ratio gamma: F(S_greedy)/F(S*) >= 1-exp(-gamma).
    Black-box application after Lemma 1 establishes gamma >= 1/(1+h_max); the paper does not re-prove the combinatorial theorem.
  • standard math Existence of Hadamard matrices of order d (powers of 2 via Sylvester construction) for the lower-bound family.
    Used only to exhibit concrete hard instances; existence is classical.
invented entities (1)
  • Maximum Initial Leverage Score (MILS / h_max) independent evidence
    purpose: Single problem-dependent scalar that upper-bounds the submodularity ratio of reciprocal risk and appears linearly in the final approximation factor; also shown necessary by the matching lower bound.
    Defined as max_i v_i^T Lambda^{-1} v_i; while ordinary leverage scores are classical, the paper isolates the maximum initial value as the governing quantity for greedy risk and proves both the upper and lower bounds in terms of it.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The Approximation Ratio for the Risk of Myopic Bayesian Active Learning for Linear Regression." pith.science (2026). https://pith.science/paper/DNRSHEZQ

@misc{pith2026260706642,
  author       = {Pith},
  title        = {Pith review of: The Approximation Ratio for the Risk of Myopic Bayesian Active Learning for Linear Regression},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/DNRSHEZQ}},
  note         = {Machine review of arXiv:2607.06642}
}
read the original abstract

Active learning studies the fundamental question: what data should we choose to observe? The greedy algorithm in optimal experiment design is a common heuristic and also equivalent to myopic Bayesian active learning for linear regression, the common framework where long-term planning is replaced with the one-step optimal choice. In this work, we prove a first-of-its-kind approximation ratio for the greedy algorithm's risk that is tight up to an absolute constant. The approximation ratio is linear in the maximum initial leverage score (MILS), a newly identified quantity fundamental to the greedy algorithm's performance. Finally, we illustrate the results with simple numerical simulations.

Figures

Figures reproduced from arXiv: 2607.06642 by the authors.

Figure 1
Figure 1. We can see that the bound based on Freduction from Chamon and Ribeiro [2017] becomes vacuous around k = 10. The numerical results conclude that the bound from Bian et al. [2017] (not shown in figure) is vacuous even for k = 1 due to the γ and α bounds being very close to 0 and 1, respectively. 7 Discussion The results in this work not only provide the first A/V -optimality criteria approximation ratio guarantee (not… view at source ↗
Figure 1
Figure 1. The objective value of the greedy algorithm and the lower bound on the optimal objective [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

20 extracted references · 20 canonical work pages

  1. [1]

    Statistical science , pages=

    Bayesian experimental design: A review , author=. Statistical science , pages=. 1995 , publisher=

    work page 1995

  2. [2]

    2012 , publisher=

    Active learning , author=. 2012 , publisher=

    work page 2012

  3. [3]

    Kevin P. Murphy. Probabilistic Machine Learning: Advanced Topics

    work page

  4. [4]

    2013 , publisher=

    Theory of optimal experiments , author=. 2013 , publisher=

    work page 2013

  5. [5]

    2006 , publisher=

    Pattern recognition and machine learning , author=. 2006 , publisher=

    work page 2006

  6. [6]

    2007 , publisher=

    Optimum experimental designs, with SAS , author=. 2007 , publisher=

    work page 2007

  7. [7]

    Neural computation , volume=

    Information-based objective functions for active data selection , author=. Neural computation , volume=. 1992 , publisher=

    work page 1992

  8. [8]

    Journal of the Royal Statistical Society: Series B (Methodological) , volume=

    Optimum experimental designs , author=. Journal of the Royal Statistical Society: Series B (Methodological) , volume=. 1959 , publisher=

    work page 1959

Show all 20 references
  1. [9]

    arXiv preprint arXiv:2505.14957 , year=

    Strong formulations and algorithms for regularized a-optimal design , author=. arXiv preprint arXiv:2505.14957 , year=

    arXiv

  2. [10]

    Mathematics of Operations Research , volume=

    Proportional volume sampling and approximation algorithms for A-optimal design , author=. Mathematics of Operations Research , volume=. 2022 , publisher=

    2022

  3. [11]

    Mathematical Programming , volume=

    Near-optimal discrete optimization for experimental design: A regret minimization approach , author=. Mathematical Programming , volume=. 2021 , publisher=

    2021

  4. [12]

    Conference on Learning Theory , pages=

    Combinatorial algorithms for optimal design , author=. Conference on Learning Theory , pages=. 2019 , organization=

    2019

  5. [13]

    Advances in neural information processing systems , volume=

    Batchbald: Efficient and diverse batch acquisition for deep bayesian active learning , author=. Advances in neural information processing systems , volume=

  6. [14]

    International conference on machine learning , pages=

    Deep bayesian active learning with image data , author=. International conference on machine learning , pages=. 2017 , organization=

    2017

  7. [15]

    International conference on artificial intelligence and statistics , pages=

    Prediction-oriented bayesian active learning , author=. International conference on artificial intelligence and statistics , pages=. 2023 , organization=

    2023

  8. [16]

    arXiv preprint arXiv:2211.09283 , year=

    Active learning with expected error reduction , author=. arXiv preprint arXiv:2211.09283 , year=

    arXiv

  9. [17]

    Mathematical programming , volume=

    An analysis of approximations for maximizing submodular set functions—I , author=. Mathematical programming , volume=. 1978 , publisher=

    1978

  10. [18]

    Proceedings of the 34th International Conference on Machine Learning , pages =

    Guarantees for Greedy Maximization of Non-submodular Functions with Applications , author =. Proceedings of the 34th International Conference on Machine Learning , pages =. 2017 , editor =

    2017

  11. [19]

    Advances in Neural Information Processing Systems , volume=

    Approximate supermodularity bounds for experimental design , author=. Advances in Neural Information Processing Systems , volume=

  12. [20]

    Journal of Machine Learning Research , volume=

    Approximate submodularity and its applications: Subset selection, sparse approximation and dictionary selection , author=. Journal of Machine Learning Research , volume=

Pith tools

Reviewed July 11, 2026 · model on record in the stance chip above.