{"id":"11126459-db83-4e40-86dc-65409234c73b","arxiv_id":"2505.17382","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A Newton-type method for box-constrained ℓ0-regularized optimization is shown to converge globally and quadratically near a strict local minimizer.","lead":"This paper proposes a subspace Newton method for sparse optimization problems with box constraints, updating part of the variables with Newton steps and the rest with proximal gradient steps. The authors claim global convergence and local quadratic convergence, supported by compressed sensing and image recovery experiments.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Algorithm 1's displayed Newton direction uses x−∇f, while the convergence proof requires x−τ∇f; the theorem analyzes a different method unless τ=1.","rationale":"The reader's weakest-assumption concern about condition (2.3) is a genuine typo/inconsistency, but it is not the most load-bearing one: the later parameter choice (4.1) actually imposes the correct upper bound τ ≤ a/(2λ), so the convergence theorems are partly insulated from that slip. The τ mismatch between Algorithm 1's (3.2)/(3.4) and the analyzed Fτ/Newton system is more serious because the proof's crucial estimates—descent of the Γ-component via Proposition 4, acceptance of the Newton step, and the quadratic rate—are derived for the τ-projection direction. If the algorithm really uses x − ∇f(x), then Proposition 4 cannot bound the Γ-component and the cancellation in (4.43) no longer follows. The central claim can survive if the algorithm statement is corrected to x − τ∇f(x), and the numerical results in Section 5 likely use such a corrected implementation; however, as printed, Theorem 7 is not a proof of the stated Algorithm 1. This supports the reader's conditional verdict without changing it to rejection, since the defect is concrete and fixable rather than a demonstrated counterexample.","tokens_in":30095,"tokens_out":22664,"duration_ms":175371,"concrete_test":"Check the algorithm statement against its own Newton derivation: for a problem with τ ≠ 1 (e.g., two variables, one active upper-bound variable and one free variable), solve the linear system Hk d = −Fτ(xk; Θk; Γk; Ik) and compare with (3.2). If the system requires dΓ = [ΠΩ(xk − τ∇f(xk))]Γ − xΓ, then (3.2) is misprinted; if the authors intend dΓ = [ΠΩ(xk − ∇f(xk))]Γ, re-prove Lemma 3.1 and Theorem 7(iii) without invoking Proposition 4 on a direction that violates its hypothesis. A specific algebra check is to substitute the displayed no-τ dΓ into the chain around (4.43) and verify that the cancellation using zk = xk − τ∇f(xk) remains valid; it does not unless τ = 1.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's convergence theorem does not analyze the Newton step that Algorithm 1 actually defines. The τ-stationary equation Fτ in (2.10) has Γ-row xΓ − [ΠΩ(x − τ∇f(x))]Γ, and the quadratic-rate proof around (4.43) explicitly uses zk = xk − τ∇f(xk) and replaces dΓ by [ΠΩ(zk)]Γ − xΓ. But the algorithm as stated in (3.2) and (3.4) defines dΓ = [ΠΩ(x − ∇f(x))]Γ − xΓ, and the trial point projection is ΠΩ(xk − gk). Unless τ = 1, which is not required or assumed, the implemented direction is not the Newton direction for Fτ. Lemma 3.1 applies Proposition 4 to dΓ, whose inequality ⟨gF,dF⟩ ≤ −(1/τ)∥dF∥² is only valid for dF = [ΠΩ(x − τg)]F − xF; the displayed dΓ does not satisfy that hypothesis. Lemma 4.1, Theorem 7(ii) (Newton step always accepted), and the quadratic convergence estimate (4.43)–(4.45) all inherit this mismatch. If τ was dropped from (3.2) by typographical error, the algorithm statement must be corrected; if not, the convergence results prove a different method.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript proposes BNL0R, a subspace Newton method for box-constrained ℓ0-regularized minimization. It introduces a τ-stationary point via the proximal operator of the ℓ0-plus-indicator objective, partitions the support into active and inactive sets, applies Newton's method to the inactive variables, and uses a projected gradient step as a fallback when the Newton direction is not acceptable. Under assumptions of strong smoothness, local strong convexity, strict complementarity, and Abadie's constraint qualification, the authors claim global convergence of the full sequence to a strict local minimizer, eventual acceptance of the Newton step, and local quadratic convergence when the Hessian is locally Lipschitz. The numerical section reports compressed sensing and image recovery experiments comparing BNL0R with PGA and PIHT.","tokens_in":30393,"tokens_out":8399,"duration_ms":83688,"significance":"If the convergence theory is made correct, the contribution is significant: it would provide a box-constrained ℓ0 method with a proven global convergence result and a local quadratic rate, extending the unconstrained subspace Newton method of [25] to the box-constrained setting and going beyond the first-order methods previously available for problem (1.1). The τ-stationarity characterization and the support-identification results are also useful. The numerical experiments are reasonably extensive, covering noise-free and noisy recovery, varying box constraints, and image recovery, and the reported gains in iteration count, time, and accuracy over PGA and PIHT support the practical value of the approach. However, as written the central theorems are not established for the algorithm that is actually stated: the standing parameter condition in (2.3) is inconsistent with the proof of Lemma 2.1 and with the later parameter choice (4.1), and the Newton direction in Algorithm 1 omits the factor τ that is used throughout the convergence analysis. These are load-bearing issues that must be repaired before the advertised results are valid.","major_comments":[{"comment":"The standing assumption (2.3), τ < 1/(2λa) with a = min_i min(l_i²,u_i²), is inconsistent with the proof of Lemma 2.1. In Cases 2 and 3 of the proof, the boundary comparison h(u_i) < h(0) requires τ < u_i²/(2λ), and similarly τ < l_i²/(2λ) for every i, i.e. τ < a/(2λ). For a < 1 the stated bound 1/(2λa) is larger than a/(2λ), so (2.3) can hold while the required inequality fails; for a > 1 it is stronger than needed. The later parameter choice (4.1) correctly uses a/(2λ), showing that the manuscript itself switches conventions. This should be repaired by replacing (2.3) with the correct condition τ < a/(2λ) and propagating it consistently through Definition 1, Lemma 2.2, and Proposition 2.","section":"§2.1, Lemma 2.1 and Eq. (2.3)"},{"comment":"The algorithm as stated defines the Newton direction on Γ_k by d^k_{Γ_k} = [Π_Ω(x^k − ∇f(x^k))]_{Γ_k} − x^k_{Γ_k} and evaluates the trial point with Π_Ω(x^k − g^k). The entire convergence analysis, however, is for the τ-projection: Proposition 4 gives (3.10) only for d_F = [Π_Ω(x−τg)]_F − x_F, Lemma 3.1 applies this inequality to d^k_{Γ_k}, and the quadratic-rate proof in (4.43)–(4.45) replaces d^k_{Γ_k} with [Π_Ω(z^k)]_{Γ_k} − x^k_{Γ_k} for z^k = x^k − τ∇f(x^k). Unless τ = 1, which is not assumed, the descent, acceptance, and quadratic-convergence proofs concern a different method from Algorithm 1. The displayed definitions in (3.2) and (3.4) should be changed to use x−τ∇f(x), or the theorem statements must be restricted to τ = 1.","section":"§3, Eqs. (3.2) and (3.4); §4, Eqs. (4.43)–(4.45)"},{"comment":"The descent property (4.2) and the Armijo step-size lower bound (4.5) are load-bearing: they enter (4.12)–(4.13), Lemma 4.3, and Theorem 7. Yet Lemma 4.1's proof is deferred by saying that replacing T_k and S_k with I_k and S̃_k in [25, Lemma 3] makes the proof analogous, and Lemma 4.2 similarly defers to [25, Lemma 4] after introducing ψ. This is not a self-contained proof in a journal submission, especially because the box constraint changes the projection and the inequalities with τ must be re-verified. Please supply the full arguments or quote the exact results from [25] and verify all hypotheses, including the corrected τ-condition from (2.3).","section":"§4, Lemmas 4.1 and 4.2"}],"minor_comments":[{"comment":"The text refers to 'Algorithm 3' in several places (e.g., Lemmas 4.3 and 4.4, Theorem 6) while the displayed algorithm is Algorithm 1; please harmonize the numbering.","section":"Throughout"},{"comment":"The sentence 'we ready to prove that condition (4.12) always holds' appears to refer to the acceptance criterion (3.3), not to the descent inequality (4.12); please correct the reference.","section":"§4, Theorem 7(ii)"},{"comment":"The caption of Table 5 says 'Results on E3 with m = n' but the text in §5.3 specifies m = 0.25n; the two statements should be made consistent.","section":"§5.3, Table 5"},{"comment":"In Theorem 6(ii), the formula x^*_{Γ_l∞} = −l_{Γ_u∞} should presumably be x^*_{Γ_l∞} = −l_{Γ_l∞}; please fix this typo.","section":"§4, Eq. (4.21)"},{"comment":"There are numerous typographical slips such as 'marix', 'Amijio', 'T able', 'Barzilar-Borwein', and duplicated I_2 in §5.3; a careful proofreading pass is needed.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The paper's heavy reliance on [25] and [38] is dependency rather than circularity, and the two main technical inconsistencies identified above appear reparable without changing the overall approach. I would not reject on those grounds alone, but the manuscript as submitted does not prove the advertised theorem for the stated algorithm. The numerical results are encouraging, but the authors should also make code/data availability explicit and consider reporting variance or worst-case outcomes for the averaged trials."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper extends NL0R to box-constrained ℓ0 problems and claims global plus local quadratic convergence. That would be a genuinely useful result, and the numerical experiments support the practical value of the method. But there is a load-bearing inconsistency between the algorithm as written and the convergence proof.\n\nThe issue is simple: the Newton direction in (3.2) defines dΓk = [ΠΩ(x − ∇f(x))]Γk − xΓk, and the trial point in (3.4) projects xk − gk. The entire convergence analysis, though, uses zk = xk − τ∇f(xk): Proposition 4, Lemma 3.1, Lemma 4.1, and the quadratic-rate proof in (4.43)–(4.45) all rely on dΓ having the τ-dependent form. Unless τ = 1, which is never assumed (and typically excluded by the small-τ conditions), Theorem 7 does not analyze Algorithm 1. This is not a cosmetic gap; it is the core of the paper.\n\nI should also note the parameter condition ambiguity. Condition (2.3) is written as τ < 1/(2λ) a (or τ < 1/(2λa) — the text is ambiguous), while Lemma 2.1's proof needs τ < a/(2λ), and (4.1) uses a/(2λ). If (2.3) is a/(2λ), then it is just poorly typeset; if it is 1/(2λa), it is wrong. Either way, the manuscript should be cleaned up.\n\nWhat the paper does well: the τ-stationary characterization for box constraints is a sensible adaptation, the support-splitting idea is natural, and the numerical study is honest and reasonably thorough. The comparisons against PGA and PIHT show clear gains in accuracy and iteration count, especially in exact recovery. The heavy reliance on [25] for Lemma 4.1 and 4.2 is acceptable if the adaptation is truly mechanical, but here the omitted details hide the τ mismatch — so the omission is not harmless. The final appeal to [38, Theorem 3.3] for unit stepsize is also underexplained; the hypotheses are not checked.\n\nIf the algorithm statement has a typo and the direction is meant to be x − τ∇f(x), the proofs may well go through after a careful rewrite. But as presented, the claims overreach.\n\nWho should read this: anyone building on NL0R for constrained sparse problems, and researchers who want a concrete example of why algorithm statements and proofs must match exactly. It deserves a serious referee, but the referee should insist on fixing the mismatch before acceptance.","headline":"Useful box-constrained extension of NL0R, but the main theorem analyzes a different algorithm than the one stated unless the missing τ is a typo.","tokens_in":30899,"tokens_out":4366,"would_cite":false,"duration_ms":29320,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C53","90C30","90C26","65K10"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper establishes a subspace Newton method for box-constrained ℓ0-regularized optimization that converges globally and, under a Hessian Lipschitz condition, quadratically to a strict local minimizer.","keywords":["box-constrained ℓ0 regularization","subspace Newton method","τ-stationary point","active set identification","global convergence","quadratic convergence","compressed sensing","proximal gradient method"],"falsifier":"A one-dimensional check settles the parameter condition: with box [−0.5, 0.5], λ=1, τ=1, and z=1, the minimizer of ½(y−1)²+‖y‖0+δΩ(y) is 0, not 0.5 as the claimed case split would return, so any proof relying on that formula would not hold for such τ.","tokens_in":29886,"feed_emoji":"🧮","tokens_out":9401,"duration_ms":70783,"temperature":0.7,"pith_summary":"The paper's goal is to give the box-constrained version of ℓ0-regularized sparse optimization the same second-order guarantee that, until now, only the unconstrained case had: an algorithm that provably converges from any start and speeds up to quadratic convergence near the answer. It defines a τ-stationary point through a proximal operator with a hard-thresholding closed form, then partitions the support into active variables (at their box bounds) and inactive variables (candidates for Newton refinement). The proposed BNL0R method updates inactive variables by a subspace Newton step and active variables by a proximal gradient step, falling back to the proximal gradient direction whenever the Newton step is not a valid descent direction. Under strong smoothness, strict complementarity, and a constraint qualification at the limit, the authors prove the whole sequence converges to a strict local minimizer and that Newton steps are eventually always accepted, with a quadratic rate when the Hessian is Lipschitz near the solution. The numerical experiments on compressed-sensing and image-recovery instances show the method reaching machine-precision recovery in four to six iterations and outperforming an ℓ1 projected-gradient solver and a proximal iterative hard-thresholding solver.","feed_headline":"Global and quadratic convergence proven for boxed ℓ0 method","feed_subtitle":"Active-inactive support split lets Newton steps fire where they count, recovering sparse signals in 4-6 iterations.","key_machinery":"The load-bearing object is the τ-stationary point. With τ>0, x is τ-stationary when it solves x = Prox_{τλ(‖·‖0+δΩ)}(x−τ∇f(x)); the paper shows the proximal operator has a closed form: coordinates stay themselves when inside the box and above √(2τλ), clip to u_i or −l_i when pushed past the boundary, and zero out otherwise. That closed form yields the index sets Θ (inactive, sign-uncertain, gradient-free target), Γ (active, at a box bound), and I (support complement, forced to zero), and the stationarity equation Fτ(x;Θ,Γ,I)=0. The algorithm applies a Newton step to the Θ block of that equation, sets Γ coordinates by projection and I coordinates to zero; a feasibility/descent criterion checks that the direction is acceptable, and when it fails a proximal gradient step (projection of x−τ∇f(x) onto the box) is used instead. The convergence proof leans on the projection inequality, the Armijo line search with a step-size lower bound, eventual stability of the index sets, and a final appeal to a standard result on unit stepsizes to convert linear contraction into the quadratic estimate.","core_discovery":"The central claim is that the box-constrained ℓ0 problem min f(x)+λ‖x‖0 subject to −l≤x≤u can be solved by a hybrid subspace Newton/proximal-gradient scheme with guarantees that first-order methods for the same model lack. The authors introduce τ-stationary points, characterized by x = Prox_{τλ(‖·‖0+δΩ)}(x−τ∇f(x)), prove that every global minimizer is τ-stationary for τ<1/L and that τ-stationary points are local (or, for strongly convex f with τ>1/ℓ, unique global) minimizers. Around such a point the algorithm declares a support set, splits it into an active set at the box boundaries and an inactive set where the gradient should vanish, and solves the stationarity equation by Newton's method on the inactive block while projecting the active block onto the box and zeroing the complement. Theorem 7 asserts global convergence to a strict local minimizer, eventual unconditional acceptance of the Newton direction, and, if the Hessian is locally Lipschitz, the quadratic bound ||$x^{{k+1}}$−x*|| ≤ (M*/(2ℓ̃*))||x^k−x*||²—making this, in the authors' account, the first box-constrained ℓ0 method with a proven quadratic rate.","pith_inferences":["If the τ-stationary condition is reused as a stopping certificate, the residual ‖x−Prox_{τλp}(x−τ∇f(x))‖ gives a computable, thresholded check of optimality; nothing in the paper develops it as such, but the equivalence results make it natural.","The independence of the proof from the specific structure of f suggests the same active-set split could be applied to ℓ0 group sparsity or ℓp penalties with box constraints; the proximal formula would need re-deriving, but the Newton-on-inactive/zero-on-rest machinery is generic.","Because the theorem assumes strict complementarity and a constraint qualification at the limit, degenerate limits—where a coordinate is optimal simultaneously at zero and at a bound that coincides with zero—are the likely trouble zone; a test with l_i=0 or u_i=0 would probe whether the method still converges and how the rate degrades.","The reported machine-precision accuracy in noise-free recovery suggests BNL0R could serve as a refinement oracle inside larger sparse-modeling pipelines, for example after a first-order method has identified a support, rather than as a replacement for inexpensive warm starts."],"forward_implications":["For the first time, box-constrained ℓ0 problems inherit a second-order convergence theory: global convergence from any start plus local quadratic rate under Hessian Lipschitzness.","Support identification becomes algorithmic: after finitely many iterations the active/inactive partition is fixed, so Newton updates act on small reduced Hessians rather than the full n-dimensional system.","The proximal-gradient fallback is not just a safety net: it keeps iterates feasible, decreases the objective by a fixed margin, and is eventually replaced by Newton steps, so the method automatically transitions from first-order to second-order behavior.","On compressed-sensing problems, the method recovers the ground truth to machine precision in a handful of iterations and, in the reported experiments, dominates both ℓ1 projected gradient and proximal iterative hard thresholding in accuracy and runtime.","For noisy recovery and image reconstruction, the same method yields substantially higher PSNR with far fewer nonzeros, indicating the box constraints plus ℓ0 model are practically useful, not only theoretically clean."],"supporting_citations":[{"why":"Supplies the subspace-Newton template and the global/quadratic convergence framework for the unconstrained ℓ0 case that this paper extends.","marker":"[25]"},{"why":"Provides the proximal iterative hard-thresholding step used as the fallback direction and the support-set perspective for ℓ0-regularized cone programming.","marker":"[30]"},{"why":"Is the source of the compressive-sensing test matrix construction used in the numerical experiments.","marker":"[32]"},{"why":"Supplies the projection inequality used repeatedly to prove descent of projected directions.","marker":"[34]"},{"why":"Gives the variational-inequality stationarity characterization used to identify active sets at the limit.","marker":"[35]"},{"why":"Supplies the KKT and constraint-qualification background needed to prove that index sets stabilize at the limit.","marker":"[36]"},{"why":"Provides the lemma that turns ∥x^{k+1}−x^k∥→0 plus isolatedness of the limit into convergence of the whole sequence.","marker":"[37]"},{"why":"Gives the unit-stepsize theorem that converts eventual Newton acceptance plus linear contraction into the quadratic-rate estimate.","marker":"[38]"},{"why":"Is the projected-gradient ℓ1 baseline against which BNL0R is compared in the experiments.","marker":"[39]"}],"fun_headline_variants":["First box-constrained ℓ0 with proven quadratic rate","Quadratic convergence for boxed ℓ0 via subspace Newton","τ-stationarity unlocks Newton for boxed sparse","Hybrid Newton-proximal: quadratic rate for ℓ0 with bounds","Boxed ℓ0 solved: subspace Newton hits quadratic"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the step size τ is small enough that √(2τλ) is smaller than every box bound, equivalently τ < min_i min(l_i²,u_i²)/(2λ); without that inequality the closed-form proximal threshold that defines the supports is not exact.","fun_headline_variants_meta":{"raw":{"variants":["First box-constrained ℓ0 with proven quadratic rate","Quadratic convergence for boxed ℓ0 via subspace Newton","τ-stationarity unlocks Newton for boxed sparse","Hybrid Newton-proximal: quadratic rate for ℓ0 with bounds","Boxed ℓ0 solved: subspace Newton hits quadratic"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000445,"raw_usage":{"total_tokens":2255,"prompt_tokens":955,"completion_tokens":1300,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":571,"completion_tokens_details":{"reasoning_tokens":1215}},"tokens_in":571,"tokens_out":1300,"duration_ms":10351,"temperature":1.0,"reasoning_tokens":1215,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T14:48:23.144989+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A one-dimensional check settles the parameter condition: with box [−0.5, 0.5], λ=1, τ=1, and z=1, the minimizer of ½(y−1)²+‖y‖0+δΩ(y) is 0, not 0.5 as the claimed case split would return, so any proof relying on that formula would not hold for such τ.","supporting_citations":[{"cited_title":"Numerical Algorithms, 1–30 (2021)","cited_arxiv_id":null,"evidence_quote":"Supplies the subspace-Newton template and the global/quadratic convergence framework for the unconstrained ℓ0 case that this paper extends."},{"cited_title":"Mathematical Programming 147(1), 125–154 (2014)","cited_arxiv_id":null,"evidence_quote":"Provides the proximal iterative hard-thresholding step used as the fallback direction and the support-set perspective for ℓ0-regularized cone programming."},{"cited_title":"Journal of Scientific Computing 79(2), 809–826 (2019)","cited_arxiv_id":null,"evidence_quote":"Is the source of the compressive-sensing test matrix construction used in the numerical experiments."},{"cited_title":"Mathematical Programming 39(1), 93–116 (1987)","cited_arxiv_id":null,"evidence_quote":"Supplies the projection inequality used repeatedly to prove descent of projected directions."},{"cited_title":"Mathematical Programming 48(1-3), 161–220 (1990)","cited_arxiv_id":null,"evidence_quote":"Gives the variational-inequality stationarity characterization used to identify active sets at the limit."},{"cited_title":"Springer (2003)","cited_arxiv_id":null,"evidence_quote":"Supplies the KKT and constraint-qualification background needed to prove that index sets stabilize at the limit."},{"cited_title":"SIAM Journal on scientific and statistical computing 4(3), 553–572 (1983)","cited_arxiv_id":null,"evidence_quote":"Provides the lemma that turns ∥x^{k+1}−x^k∥→0 plus isolatedness of the limit into convergence of the whole sequence."},{"cited_title":"Operations Research Letters 17(3), 131–137 (1995)","cited_arxiv_id":null,"evidence_quote":"Gives the unit-stepsize theorem that converts eventual Newton acceptance plus linear contraction into the quadratic-rate estimate."},{"cited_title":"Optimization Letters 11(1), 55–70 (2017)","cited_arxiv_id":null,"evidence_quote":"Is the projected-gradient ℓ1 baseline against which BNL0R is compared in the experiments."}],"review_version":1}