{"id":"1fa5d4fc-5a97-4b64-b249-5ff73b2823f1","arxiv_id":"2505.14957","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Regularized A-optimal design is NP-hard, and a new convex relaxation dominates previous ones with finite optimality gaps for every k, enabling faster exact and greedy solvers.","lead":"This paper proves that the regularized A-optimal experimental design problem is NP-hard, and introduces a new convex relaxation that has provably bounded error for every selection size. The work also gives exact and greedy algorithms that run quickly on high-dimensional, small-k instances, and applies the model to cold-start movie recommendations.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proposition 3(ii) gives an invalid subgradient: the proposed matrix is positive semidefinite, but conv Γ is decreasing, so the Algorithm 1 cuts are not valid underestimators.","rationale":"The reader's weakest_assumption focuses on the imported convex-envelope formula, Proposition 3(i), and on the C=AA^T vs C=A^T A typo in Appendix A.2. My reading agrees those need attention, but the most load-bearing issue is Proposition 3(ii): the stated subgradient is demonstrably not a subgradient. This is not a matter of citation strength or consensus; it is an internally checkable false statement. Since Remark 3 and Algorithm 1, and therefore the exact-solver numerical claims, are built on this subgradient, the paper's algorithmic contribution is currently unsupported. The relaxation dominance and bounded-gap theorems do not use the subgradient, so a revision that corrects the subgradient formula and re-runs the experiments could preserve the central theoretical claims. I would keep the CONDITIONAL verdict, with the added explicit condition that Proposition 3(ii) be corrected and the empirical results revalidated.","tokens_in":34335,"tokens_out":34753,"duration_ms":287053,"concrete_test":"Evaluate Proposition 3(ii) on the explicit case d=2, k=1, λ=1, X=I_2. Compute conv Γ(X)=1/(tr X+1)=1/3, the proposed W=I_2/3, and test the subgradient inequality at Y=2I_2: it fails because 1/5 < 1/3+2/3. Then re-derive the correct subgradient from the derivative of conv Γ (ς_i = −1/(σ_i+λ)^2 for i≤η, and ς_i = −(k−η)^2/D^2 for i>η, where D=Σ_{j>η}σ_j+(k−η)λ) and rerun the cutting-plane experiments in Tables 3–4; if Algorithm 1's MIPGaps and runtimes change materially, the numerical claims depend on the erroneous formula.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Proposition 3(ii) (Section 4.1) asserts that Q Diag(ς) Q^T is a subgradient of conv Γ(X;λ), with ς_i = 1/(σ_i+λ) for i≤η and ς_i = (k−η)/(Σ_{j>η}σ_j+(k−η)λ) for i>η, all entries positive. But conv Γ is a decreasing convex function of X: adding a PSD matrix increases eigenvalues and decreases the summed reciprocal eigenvalues. Every subgradient of a decreasing convex function must be negative semidefinite. A direct check settles the error: take d=2, k=1, λ=1, X=I_2. Then conv Γ(X)=1/(tr X+1)=1/3, and the proposed W=I_2/3 is positive definite. Against Y=2I_2, conv Γ(Y)=1/5, but the subgradient inequality requires 1/5 ≥ 1/3 + ⟨I_2/3, I_2⟩ = 1, which fails. The correct derivative there is −(tr X+1)^{-2} I. Consequently Remark 3's g_i = a_i^T W a_i has the wrong sign and magnitude, so the outer-approximation cuts in (4) and Algorithm 1 are not valid underestimators; the claimed exactness of the cutting-plane algorithm and the MIPGap tables for Algorithm 1 are unsupported as written. The relaxation-gap results (Theorem 5, Corollary 2) do not use this subgradient, so those parts may survive, but the algorithmic contribution needs a substantive correction.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper studies the Regularized A-optimal Design (RAOD) problem, in which one selects k experiment vectors a_i so as to minimize tr((Σ_{i∈S} a_i a_i^T + λ I_d)^{-1}). The authors claim four main contributions: a proof of NP-hardness via a reduction from independent set through an equivalence with AMESP; a new convex relaxation RAOD-RII based on the convex envelope of Γ(X;λ)=Σ_{i=1}^{min{k,d}} 1/(σ_i+λ), which they show dominates the existing RAOD-RI and AMESP-R relaxations and has bounded optimality gaps for every k; an exact cutting-plane algorithm for the resulting convex integer formulation; and data-independent approximation guarantees for forward and backward greedy algorithms. The paper also reports numerical experiments on synthetic, UCI, and movie-rating data, including a user cold-start recommendation application.","tokens_in":34672,"tokens_out":17416,"duration_ms":158753,"significance":"If the results are correct, the paper makes substantial contributions: the first NP-hardness proof for RAOD (and hence for the conjectured hardness of Bayesian AOD), a relaxation that provably dominates the two existing relaxations for all k with finite worst-case gaps, and new approximation guarantees for greedy methods. The theoretical relaxation analysis (Theorems 2, 3, and 5 with Corollary 2), the NP-hardness strategy, and the greedy performance proofs are presented in detail and appear largely sound. However, the algorithmic centerpiece is currently invalid: Proposition 3(ii) gives a positive semidefinite matrix as a subgradient of a decreasing convex function, which is impossible, and the displayed counterexample in this report confirms that the proposed subgradient inequality fails. Consequently, the outer-approximation cuts in Eq. (4) and Algorithm 1 are not valid underestimators, and the exactness claims plus the MIPGap tables for Algorithm 1 are unsupported as written. The relaxation-gap results and greedy theorems do not rely on this subgradient and may survive.","major_comments":[{"comment":"Proposition 3(ii) is incorrect as stated. The proposed matrix W = Q Diag(ς)Q^T has positive entries ς_i and is positive semidefinite, but conv Γ is a decreasing convex function of X in the positive semidefinite order, so every subgradient of conv Γ must be negative semidefinite. A direct check settles the matter: take d=2, k=1, λ=1, and X=I_2. Then Proposition 3(i) gives conv Γ(X) = 1/(tr X + 1) = 1/3, while Proposition 3(ii) gives W = I_2/3. At Y = 2I_2, conv Γ(Y) = 1/5, but the subgradient inequality with W would require 1/5 ≥ 1/3 + ⟨I_2/3, I_2⟩ = 1, which fails. The correct subgradient at this point is -(tr X + 1)^{-2} I = -I/9. As a consequence, the vector g(x) defined in Remark 3 has the wrong sign, and the cuts in Eq. (4) and Algorithm 1 are not valid underestimators of the objective of (3). The claimed convergence of Algorithm 1 and the MIPGap results in Tables 3–4 are therefore unsupported as written. This is a load-bearing error for the exact-algorithm contribution, although the relaxation-gap results in Theorem 5 and Corollary 2 do not use this subgradient and may still be correct. The subgradient formula should be replaced by a valid negative semidefinite expression and the numerical experiments re-run.","section":"Section 4.1–4.3, Proposition 3(ii), Remark 3, Eq. (4), Algorithm 1"},{"comment":"The NP-hardness reduction writes C = AA^T + λ I_n and says the Cholesky factor A of C − λ I_n yields this representation, but Proposition 1 defines C = A^T A + λ I_n. The trace of a principal submatrix of A^T A is not generally equal to the corresponding trace for AA^T, so the proof as written does not literally match the equivalence on which the reduction relies. The intended construction is clear: choose the Cholesky factor so that C − λ I_n = A^T A (or transpose the usual Cholesky factor), with the resulting dimension d = n, and state this explicitly. This correction is needed for the NP-hardness proof to be literally correct.","section":"Appendix A.2, proof of Theorem 1"}],"minor_comments":[{"comment":"The statement of Theorem 6 gives the approximation ratio for Algorithm 3 as (n−d−1)/(k−d+1), while the proof and Table 2 both use (n−d+1)/(k−d+1). The formula in the theorem statement should be corrected.","section":"Theorem 6"},{"comment":"In Corollary 1(ii), the text says 'there is a case of RAOD-RI where z_k/ν^k_C → ∞'; the ratio is for the relaxation (2) or RAOD-RI's bound, so the wording should be adjusted to avoid identifying the relaxation with the integer problem.","section":"Corollary 1"},{"comment":"There are several typographical errors, including 'seminar work' for 'seminal work' in Section 1.1 and 'subgragh' for 'subgraph' in Appendix A.2. A careful proofreading pass is needed.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The main reason for major revision is the invalid subgradient in Proposition 3(ii), which undermines the exact cutting-plane algorithm and the associated numerical tables. I do not see evidence of circularity: the self-citations provide supporting technical lemmas rather than the paper's main conclusions. The relaxation and greedy results appear substantial and likely salvageable, so a corrected version could be publishable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Read Li's RAOD paper. The new relaxation and complexity results are real: NP-hardness via independent set, the RAOD-RII relaxation that dominates both RAOD-RI and AMESP-R with bounded gaps for all k, and the backward greedy guarantee. These are worth a serious look. The equivalence between RAOD and AMESP (Proposition 1) is also clean.\n\nBut the cutting-plane algorithm, which is the headline computational contribution, has a load-bearing error. Proposition 3(ii) asserts that Q diag(ς) Q^T with positive ς is a subgradient of conv Γ(X;λ). conv Γ is decreasing in X (adding PSD increases eigenvalues, decreases reciprocals), so every subgradient must be negative semidefinite. The proposed W is positive semidefinite. The stress-test counterexample (d=2, k=1, λ=1, X=I_2) confirms it: the subgradient inequality fails for Y=2I_2. Consequently Remark 3, the cuts in (4), and Algorithm 1's exactness are invalid as written, and the MIPGap tables in Tables 3-4 are unsupported. This is not a minor typo; it changes the sign and magnitude of the gradient.\n\nThe relaxation-gap results (Theorem 5, Corollary 2) do not use this subgradient, so they may survive. The same goes for the NP-hardness proof, though Appendix A.2 says C = AA^T + λI_n while Proposition 1 needs C = A^T A + λI_n; for the square reduction matrix this is likely harmless but should be fixed. Theorem 6 also misprints (n-d-1)/(k-d+1) instead of (n-d+1)/(k-d+1).\n\nThe paper leans heavily on the author's prior results for the convex envelope and majorization lemmas without full reproof. That is acceptable if the import is correct, but the subgradient slip suggests the transfer was not checked carefully.\n\nBottom line: this is a potentially valuable paper with a serious flaw in one of its three pillars. I would send it to peer review, but the referee should be told to focus on the subgradient. If the authors can supply a correct subgradient (or drop the cutting-plane claim), the relaxation and approximation results stand on their own.","headline":"Solid relaxation and complexity results, but the cutting-plane algorithm's subgradient is wrong and needs a substantive fix.","tokens_in":35184,"tokens_out":5651,"would_cite":true,"duration_ms":47888,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C11","90C25","62K05"],"pacs":[],"model":"deepseek-v4-flash","headline":"Regularized A-optimal design — choosing k experiments to minimize the trace of the inverse of a regularized Fisher information matrix — is NP-hard, and a new convex-envelope relaxation dominates all existing relaxations for every k.","keywords":["regularized A-optimal design","NP-hardness","convex envelope","convex relaxation","cutting-plane algorithm","greedy algorithms","cold-start recommendation","mixed-integer programming"],"falsifier":"Take the instance of Example 2 from the paper: d=1, k=2, n=3, λ=1, with a1=1, a2=−1, a3=2. Solving the three relaxations should produce ν^M_2 = −1/28 (negative), while RAOD-RII returns a value satisfying ν^N_2 ≥ ν^C_2 and ν^N_2 ≥ ν^M_2; a violation of these inequalities would refute the dominance claim of Theorem 5.","tokens_in":34118,"feed_emoji":"📐","tokens_out":9767,"duration_ms":79373,"temperature":0.7,"pith_summary":"The paper establishes that Regularized A-optimal Design (RAOD) — selecting k experiments to minimize the trace of the inverse of a regularized Fisher information matrix — is NP-hard, resolving the complexity of the isotropic-prior case of Bayesian A-optimal design. The main contribution is a new convex integer formulation built from the convex envelope of a spectral function, whose continuous relaxation RAOD-RII is provably at least as tight as the two standard relaxations for every k, and strictly tighter in the previously hard small-k regime. Unlike existing relaxations, which can have unbounded gaps for k < d or negative lower bounds for k > d, RAOD-RII has finite data-independent optimality gaps for all k. The formulation drives an exact cutting-plane algorithm that certifies optimality in high-dimensional, small-k instances where previous exact methods stall, and the paper supplies forward and backward greedy algorithms with the first data-independent guarantees in their respective k ranges.","feed_headline":"A-optimal design is NP-hard; new relaxation wins for all k","feed_subtitle":"A convex-envelope formulation gives bounded optimality gaps and fast exact solving, taming small-k high-dimensional cases.","key_machinery":"The load-bearing object is $\\operatorname{conv}\\Gamma(X;\\lambda)$, the convex envelope of the spectral function $\\Gamma(X;\\lambda)=\\sum_{i=1}^{\\tilde k} \\frac{1}{\\sigma_i+\\lambda}$ on the cone of $d\\times d$ positive semidefinite matrices, where $\\sigma_1\\ge\\dots\\ge\\sigma_d\\ge0$ are the eigenvalues of $X$. Proposition 3 gives the closed form $\\operatorname{conv}\\Gamma(X;\\lambda)=\\sum_{i\\in[\\eta]}\\frac{1}{\\sigma_i+\\lambda}+\\frac{(\\tilde k-\\eta)^2}{\\sum_{i\\in[\\eta+1,d]}\\sigma_i+(\\tilde k-\\eta)\\lambda}$, where $\\eta$ is the unique integer $0\\le\\eta\\le\\tilde k-1$ satisfying a spectral-gap condition, and Lemma 7 shows that for matrices of rank at most $\\tilde k$, $\\operatorname{conv}\\Gamma(X;\\lambda)+(d-\\tilde k)/\\lambda=\\operatorname{tr}((X+\\lambda I_d)^{-1})$. This equality makes the new integer program exact on binary vectors while remaining convex, and the envelope's explicit subgradient makes the relaxation tractable by first-order methods such as Frank–Wolfe.","core_discovery":"The paper claims that RAOD, the problem of minimizing $\\operatorname{tr}((\\sum_{i\\in S} a_i a_i^\\top + \\lambda I_d)^{-1})$ over subsets $S$ of size $k$, is NP-hard, and that the relaxation RAOD-RII — obtained by replacing the objective of an exact convex integer program with the convex envelope $\\operatorname{conv}\\Gamma(X;\\lambda)$ plus the constant $(d-\\tilde k)/\\lambda$, where $\\tilde k=\\min\\{k,d\\}$ — dominates both the conventional relaxation RAOD-RI and the AMESP relaxation AMESP-R for every $k$. Concretely, Theorem 5 asserts $\\nu^N_k = \\nu^C_k$ for $k\\in[d,n]$, $\\nu^N_k \\ge \\nu^C_k$ for $k\\in[d-1]$, and $\\nu^N_k \\ge \\nu^M_k$ for all $k$. Because the envelope is exact on the rank-constrained binary feasible set, the new formulation is an exact convex integer program, not merely a relaxation, and its relaxation carries finite optimality gaps for all $k$ (Corollary 2), closing the unbounded-gap and negative-bound pathologies of the prior relaxations.","pith_inferences":["The NP-hardness reduction in Appendix A.2 writes $C=AA^\\top+\\lambda I_n$, whereas Proposition 1 and the AMESP equivalence use $C=A^\\top A+\\lambda I_n$; a skeptical reader should check this orientation discrepancy, since the independent-set gadget is symmetric and the reduction could likely be repaired by transposition.","The convex-envelope technique is not limited to the isotropic regularizer: replacing $\\lambda I$ with a general positive-definite prior $\\Sigma$ may yield analogous envelopes for Bayesian A-optimal design, turning the paper's dominance result into a template for the general problem whose complexity the paper leaves open.","The gap bound $(d-1)/(d-k)$ decreases with $d$, suggesting that RAOD-RII becomes relatively stronger precisely in the high-dimensional, small-k settings where A-optimality is most used in practice, so the numerical speedups observed for Algorithm 1 may be intrinsic rather than an artifact of the test instances.","The backward greedy guarantee is novel and gives a theoretical justification for a heuristic that practitioners often prefer when $k$ is close to $n$; combining it with forward greedy and taking the better of the two, as in Algorithm 4, inherits both guarantees at $O(n^2d^2)$ cost."],"forward_implications":["Exact solvers for RAOD can replace the standard relaxation with RAOD-RII as the dual bound; Theorem 5 guarantees this never weakens the bound, and in the small-k regime $k<d$ it strictly strengthens it, enabling more aggressive node pruning in branch-and-bound.","The bounded gaps in Corollary 2 mean that for any $k$, the relaxation value is within a known factor of the optimum: $\\min\\{(d-1)/(d-k),\\, n-k+1\\}$ for $k<d$, $\\min\\{d,\\, n-d+1\\}$ for $k=d$, and $(n-d+1)/(k-d+1)$ for $k>d$.","The forward greedy algorithm is certified for $k<d$ with a $(d-1)/(d-k)$ approximation ratio — the first data-independent guarantee in this regime — and the new backward greedy algorithm is certified for $k\\ge d$ with ratio $(n-d+1)/(k-d+1)$, together covering all $k$.","Because RAOD is equivalent to AMESP up to the additive constant $(d-k)/\\lambda$, any approximation or exact result for either problem transfers to the other after adjusting for this constant, including the negative-gap pathology that makes AMESP-R useless for $k>d$."],"supporting_citations":[{"why":"Supplies the permutation-invariant convex-envelope theorem from which Proposition 3 derives the closed form of conv Γ(X;λ).","marker":"Kim et al. (2022, Theorem 8)"},{"why":"Establishes the λ=0 convex envelope and the spectral function Φ underlying AMESP-R, which the paper extends to λ>0 and compares against.","marker":"Li and Xie (2024, Theorems 8 and 9)"},{"why":"Provides the sampling-probability and spectral-ratio technique used in Lemma 2 to bound the removal cost, which drives both the relaxation gap and greedy guarantees.","marker":"Derezi´nski and Warmuth (2017, Lemma 5)"},{"why":"The harmonic–arithmetic mean inequality (Lemma 1) used throughout the gap proofs and in the independent-set reduction.","marker":"Sedrakyan and Sedrakyan (2018)"},{"why":"Source for the NP-hard independent set decision problem used as the reduction target in Theorem 1.","marker":"Cormen et al. (2022, Chapter 34)"},{"why":"Prior D-optimality equivalence between Bayesian design and maximum entropy sampling that Proposition 1 adapts to A-optimality.","marker":"Li et al. (2024, Theorems 1 and 2)"},{"why":"Origin of the MISOCP formulation whose continuous relaxation is shown (Corollary 1) to coincide with RAOD-RI.","marker":"Sagnol and Harman (2015)"}],"fun_headline_variants":["RAOD is NP-hard; convex envelope yields bounded gaps for each k","Exact convex integer program beats all RAOD relaxations for all k","High-dim small-k A-optimal design solved exactly via new cuts","Greedy and exact algorithms with guarantees for A-optimal design"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The entire dominance and gap analysis rests on the convex-envelope formula for Γ(X;λ) in Proposition 3, which is imported from prior work on the λ=0 case; if that formula fails for λ>0, the relaxation RAOD-RII and all its guarantees collapse.","fun_headline_variants_meta":{"raw":{"variants":["RAOD is NP-hard; convex envelope yields bounded gaps for each k","Exact convex integer program beats all RAOD relaxations for all k","High-dim small-k A-optimal design solved exactly via new cuts","Greedy and exact algorithms with guarantees for A-optimal design"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000682,"raw_usage":{"total_tokens":3128,"prompt_tokens":1006,"completion_tokens":2122,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":622,"completion_tokens_details":{"reasoning_tokens":2045}},"tokens_in":622,"tokens_out":2122,"duration_ms":14587,"temperature":1.0,"reasoning_tokens":2045,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T15:27:14.438694+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take the instance of Example 2 from the paper: d=1, k=2, n=3, λ=1, with a1=1, a2=−1, a3=2. Solving the three relaxations should produce ν^M_2 = −1/28 (negative), while RAOD-RII returns a value satisfying ν^N_2 ≥ ν^C_2 and ν^N_2 ≥ ν^M_2; a violation of these inequalities would refute the dominance claim of Theorem 5.","supporting_citations":[{"cited_title":"Mathematics of Operations Research 47(4):2547--2584","cited_arxiv_id":null,"evidence_quote":"Supplies the permutation-invariant convex-envelope theorem from which Proposition 3 derives the closed form of conv Γ(X;λ)."},{"cited_title":"Subsampling for Ridge Regression via Regularized Volume Sampling","cited_arxiv_id":"1710.05110","evidence_quote":"Provides the sampling-probability and spectral-ratio technique used in Lemma 2 to bound the removal cost, which drives both the relaxation gap and greedy guarantees."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The harmonic–arithmetic mean inequality (Lemma 1) used throughout the gap proofs and in the independent-set reduction."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Source for the NP-hard independent set decision problem used as the reduction target in Theorem 1."},{"cited_title":"The Annals of Statistics 43(5):2198--2224","cited_arxiv_id":null,"evidence_quote":"Origin of the MISOCP formulation whose continuous relaxation is shown (Corollary 1) to coincide with RAOD-RI."}],"review_version":1}