{"id":"9d400e37-b1f6-46fd-be75-de675be5a4f5","arxiv_id":"2506.03974","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper unifies the convex ingredients of ℓ0-penalized optimization into closed-form formulas and packages them in an open-source solver that outperforms existing exact solvers on several benchmarks.","lead":"El0ps is a new open-source Branch-and-Bound solver for problems that minimize a convex loss plus an ℓ0 sparsity penalty plus a convex regularizer. The paper proves that the key convex-analysis objects the solver needs (biconjugate, conjugate, subdifferential, proximal operators) have closed forms for a broad class of regularizers, and shows large speedups over commercial MIP solvers.","discovery_kind":"unification","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified; the central closed-form characterization is sound under the explicitly stated convexity assumption (H3), and the convexity limitation is not an internal inconsistency.","rationale":"The reader's weakest_assumption correctly identifies convexity as the enabling premise. My stress-test agrees that this is the most load-bearing condition, but it is an explicit assumption of the paper, and the theorem statements are conditional on it. The internal proofs in Appendices E-F are consistent, and I found no algebraic or logical gap. The main residual risk is over-interpretation of \"generic\" in the title, but the paper's abstract and introduction clearly limit the scope. The requested revision remains the addition of variance information and version pinning for the numerical experiments, which is an experimental reproducibility issue, not a correctness issue. Therefore the CONDITIONAL verdict stands unchanged.","tokens_in":34673,"tokens_out":19990,"duration_ms":174680,"concrete_test":"Independently verify Proposition 2 on a nontrivial convex h not in Table 1, e.g., h(x) = (|x|-1)_+^2, by symbolically computing g⋆(z) = [h⋆(z)-λ]_+, then g⋆⋆, and checking that (23) reproduces it for several λ values; if any mismatch appears, the proof of Proposition 2 has a gap.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim (Proposition 2, Eq. (23)) is correct under (H1)-(H2)-(H3)-(H5). The single most load-bearing assumption is H3 (convexity of h), because the proof uses h = h⋆⋆ and convex subdifferential calculus. If h is nonconvex (e.g., SCAD or MCP), g⋆⋆ becomes the convex envelope and the simple form in (23) does not hold; the lower bounds used in the BnB would then be invalid. However, H3 is explicitly stated in the paper, and the abstract qualifies results as holding under the \"blanket assumptions considered in our work.\" Thus this is a clearly signposted scope limitation, not a hidden flaw or an internal inconsistency. The paper's empirical claims would benefit from variance estimates and pinned code versions, but these do not affect the truth of the theoretical characterization. I therefore find no load-bearing objection to the central mathematical claim.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper presents a generic branch-and-bound (BnB) framework for the exact solution of ℓ0-penalized problems of the form min_x f(Ax)+Σ g(x_i) with g(x)=λ‖x‖0+h(x). The central theoretical result is that, under assumptions (H1)-(H5), the biconjugate g**, the conjugate g*, their subdifferentials, and their proximal operators admit closed-form expressions involving three scalar parameters τ, μ, and κ; in particular, g**(x)=τ|x| for |x|≤μ and g**(x)=h(x)+λ otherwise. The authors show that this unifies earlier results for quadratic and box penalties, and they introduce El0ps, an open-source Python solver implementing the framework. Numerical experiments compare El0ps with Cplex, Mosek, an outer-approximation baseline, and L0bnb on feature-selection and Bernoulli-mixture recovery problems.","tokens_in":34845,"tokens_out":15791,"duration_ms":155654,"significance":"The theoretical characterization is elegant and, if correct, valuable: all BnB ingredients are reduced to three scalar parameters and standard operators of h, and the appendix supplies detailed step-by-step proofs that recover the known formulas (6a)-(6b) as special cases. The paper also contributes an open-source solver and detailed experimental scripts, which aids reproducibility. The convexity assumption (H3) is clearly stated and constitutes an explicit scope limitation rather than a hidden flaw. However, the experimental section uses two penalties that violate the evenness assumption (H5) of the main theorems, and the promised relaxation of (H5) is not proved; this gap must be closed before the experimental claims in Section 5.3 can be considered fully supported.","major_comments":[{"comment":"The 'Exponential' and 'Half-Normal' densities in Table 3 give penalties h(x) = -ζ² log ϕ(x) that are +∞ on (-∞,0), hence not even; (H5) fails. All formal results in Propositions 2-7 are stated and proved under (H5), and the proof of Proposition 2 in Appendix F.1 explicitly uses evenness to restrict attention to x ≥ 0 and to symmetrize via Corollary 8. The footnote in Section 1 saying that (H5) 'can be relaxed' does not state or prove the one-sided versions used in these experiments. As written, formula (23) would give finite τ|x| for x<0 in such cases; for example, for h(x)=σx+η(x≥0) one has g**(x)=+∞ for x<0, not σ|x|. The lower bounds and proximal/subdifferential formulas used by the solver are therefore not mathematically justified for these instances. Please add a one-sided (non-even) statement of Propositions 2 and 5-7 with proofs, or restrict the corresponding numerical claims to penalties satisfying (H5).","section":"§5.3, Table 3; Propositions 2-7, Eq. (23)"}],"minor_comments":[{"comment":"Averaging over 10 runs is reported, but no standard deviation, error bars, or quantiles are shown; because the speedups are a central empirical claim, please add variability information.","section":"§5.2, Fig. 2"},{"comment":"The Oa baseline is implemented by the authors because no public implementation exists; please describe how this implementation was verified (for example, agreement with known small instances) so that the comparison is transparent.","section":"§5.1, Appendix H.3"},{"comment":"The legend entry 'Lobnb' is a typo for L0bnb.","section":"Fig. 2"},{"comment":"The phrase 'an acceleration factor varying between two and three in average' is ambiguous; please specify whether this is a factor of 2-3× or 2-3 orders of magnitude.","section":"§5.2"},{"comment":"The statement that El0ps is 'the only procedure able to address' the Laplace and Exponential instances should be qualified as 'the only procedure that solved any instance within the 10-minute budget', since the baselines can in principle encode the same MIP formulations (Appendix H.2).","section":"§5.3"},{"comment":"The appendix lists software versions but not commit hashes of the El0ps and l0exp repositories; pinning these would strengthen reproducibility.","section":"Appendix H.1"}],"recommendation":"major_revision","confidential_remarks":"The theoretical core appears sound and the manuscript is well organized. My main concern is confined to the non-even penalties used in Section 5.3; once the one-sided extension is stated and proved, or the experiments are adjusted to satisfy (H5), I would expect the paper to be acceptable. The self-citation to the companion paper [31] is present but is appropriate given that the companion describes the implementation details."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The main thing to know: Proposition 2 is the real deal. Under the explicit convexity assumption (H3), the biconjugate g** takes the simple form tau|x| on [-mu, mu] and h(x)+lambda outside, with tau and mu defined via sublevel sets of h*. That unifies earlier results for quadratic h and Big-M constraints and extends them to any closed convex coercive even h. The proof chain in Appendices E and F is step-by-step, and I found no internal contradiction. Propositions 3–7 give subdifferentials and proximal operators for g** and g*, so every BnB ingredient is closed-form. This is a genuine contribution, not a repackaging.\n\nThe solver El0ps is open-source, with code and datasets linked. The experiments cover least-squares, logistic, SVM, and Bernoulli-mixture models, and El0ps is orders of magnitude faster than generic MIP solvers on that test suite. That is plausible and consistent with the theory.\n\nSoft spots: the empirical claims would be stronger with variance bars. Averages over 10 runs without spread make it hard to judge stability, and the Oa baseline is the authors' own Python implementation. Cplex and Mosek use standard MIP reformulations, but MIP modeling choices can affect timings, so pinned code versions and maybe an independent baseline would help. None of this touches the theoretical core.\n\nThe convexity assumption is the only real scope limit: SCAD and MCP penalties are out, and the lower bounds would not be valid there. But the paper states this plainly, so it is a signposted limitation, not a hidden flaw.\n\nWho this is for: anyone doing exact l0-penalized optimization with convex h. The closed-form biconjugate is a useful reference result, and the solver is a practical tool. I would cite it and would be happy to referee it. With variance information and pinned code versions, I would expect it to pass review without much trouble.\n\nRecommendation: send it to peer review. The math holds up, and the code is out there for anyone to check.","headline":"Closed-form biconjugate and a working solver make this a real contribution; the empirical section just needs more care.","tokens_in":35398,"tokens_out":1570,"would_cite":true,"duration_ms":16129,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C25","90C57","90C90"],"pacs":[],"model":"deepseek-v4-flash","headline":"For any ℓ0-penalized problem whose coordinate penalty is closed, convex, coercive, and even, the paper derives closed-form formulas for every quantity a branch-and-bound solver requires.","keywords":["ℓ0 regularization","branch-and-bound","convex relaxation","biconjugate","sparse optimization","proximal operator","Bernoulli mixture model","El0ps"],"falsifier":"Compute the true biconjugate of g(x)=λ∥x∥0+σ|x| by numerical Legendre transform on a fine grid and compare it with formula (23) for several values of λ and σ, especially around x=μ; any mismatch, or any instance where the solver's lower bound exceeds the known global optimum, would falsify the central claim.","tokens_in":34472,"feed_emoji":"🧮","tokens_out":7251,"duration_ms":68999,"temperature":0.7,"pith_summary":"This paper claims that for any ℓ0-penalized optimization problem whose regularizer splits coordinate-wise as g(x)=λ∥x∥0+h(x), with h closed, convex, coercive, and even, all the ingredients a branch-and-bound solver needs can be written in closed form. The central object is the biconjugate g⋆⋆, the tightest convex lower bound on g, and the paper gives its explicit expression using only three scalar parameters. If the derivation is correct, a single generic solver can handle far more losses and penalties than earlier methods, including logistic and SVM losses and many Bayesian priors. The paper also introduces an open-source Python solver implementing these formulas and reports large speedups on machine-learning and signal-processing instances.","feed_headline":"One formula unlocks exact ℓ0 sparse optimization","feed_subtitle":"Closed-form lower bounds let one branch-and-bound solver handle many losses and penalties at once.","key_machinery":"The carrying object is the biconjugate g⋆⋆, the largest proper closed convex function below g, together with the three scalars τ, μ, and κ defined by equations (7)-(9): τ is the first level at which the conjugate h⋆ crosses λ, μ is the corresponding subgradient endpoint, and κ records how steeply h rises at μ. Proposition 2 expresses g⋆⋆ as a rescaled absolute value in a central interval and as h+λ outside it. Propositions 3-7 then derive the subdifferentials and proximal operators of g⋆⋆ and g⋆ from these same parameters, so the numerical routines that solve the convex relaxations have closed-form oracles. The construction works for any f that is closed, convex, differentiable, lower-bounded, and satisfies 0∈int(dom f), and for any h satisfying the blanket assumptions with h(0)=0, closedness, convexity, coercivity, and evenness.","core_discovery":"The paper establishes that under assumptions (H1)-(H5), the biconjugate of g(x)=λ∥x∥0+h(x) is g⋆⋆(x)=τ|x| for |x|≤μ and g⋆⋆(x)=h(x)+λ for |x|≥μ, where τ is the largest nonnegative z with h⋆(z)≤λ and μ is the largest nonnegative element of ∂h⋆(τ), taken as +∞ when that subdifferential is empty. Because g⋆⋆ is the tightest proper closed convex lower bound on g, this one formula provides the convex relaxation on which branch-and-bound lower bounds are built. The same parameters, together with κ=sup{z≥0:z∈∂h(μ)}, give closed forms for the subdifferentials and proximal operators of both g⋆⋆ and its conjugate g⋆(z)=[h⋆(z)−λ]+, proved as Propositions 3-7. This is what lets the accompanying solver run branch-and-bound with general f and h, unifying earlier special cases that were derived separately for particular penalties.","pith_inferences":["If the formula is correct, a direct extension is to allow h to be any even closed convex coercive function with tractable conjugate and proximal operators; users would only need to code h, h⋆, and prox_h, not the branch-and-bound logic.","For nonconvex h, such as SCAD or MCP penalties, formula (23) would not hold, but replacing h by its convex envelope in the same derivation would still give a valid albeit weaker lower bound; whether that bound preserves speed is a testable question.","The explicit biconjugate could also be used outside branch-and-bound, for instance in safe screening or as a warm-start relaxation for continuous optimization, where the closed form might accelerate existing methods.","Because the interval [−μ, μ] and slope τ track the trade-off between λ and h, the closed form could guide adaptive tuning of λ along regularization paths."],"forward_implications":["A user only needs to specify f and h; the relaxation, subdifferentials, and proximal steps are built automatically from formulas (23)-(29), so losses beyond least squares, such as logistic and SVM classification, become exactly solvable by the same solver.","Early stopping of the relaxed subproblem is safe, because the dual objective (21) can be evaluated at any point and still gives a valid lower bound on the node's optimum.","Previously published relaxations, including the interval constraint h(x)=η(|x|≤M) and the quadratic penalty h(x)=σ/2 x², are special cases of one formula, so the framework unifies them.","For signal-processing models with Bernoulli mixture priors, including Laplace and exponential priors, the solver reaches optimality on instances that no compared solver completed within the time budget.","On the tested regularization-path and mixture-model instances, the solver reports speedups of one to four orders of magnitude over the compared implementations."],"supporting_citations":[{"why":"Supplies the convex-analysis toolkit (biconjugate, subdifferential calculus, Moreau decomposition) used to prove Propositions 2-7.","marker":"[6]"},{"why":"Supplies the closed-function and Moreau-decomposition results used to manipulate g⋆⋆ and g⋆ and their proximal operators.","marker":"[7]"},{"why":"Gives a previous closed-form relaxation for a specific choice of h, the special case that the new formula generalizes.","marker":"[9]"},{"why":"Introduces the modern mixed-integer-programming and branch-and-bound viewpoint that motivates exact ℓ0 optimization.","marker":"[12]"},{"why":"Provides the specialized L0bnb solver that the paper's numerical experiments compare against on its supported setting.","marker":"[34]"},{"why":"Provides the branch-and-bound approach rooted in first-order optimization that the generic solver builds on.","marker":"[35]"},{"why":"Gives the Boolean-relaxation result for h(x)=σ/2 x² that the new biconjugate formula recovers as a special case.","marker":"[45]"}],"fun_headline_variants":["Closed-form bound makes L0 branch-and-bound generic","One formula unifies exact L0 sparse optimization","Generic L0 branch-and-bound with plug-and-play losses","Unified lower bound extends L0 solver to new problems"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The construction hinges on h being convex: when h is not convex, h≠h⋆⋆, the claimed expression for g⋆⋆ is no longer the biconjugate, and the lower bounds used to prune nodes in the branch-and-bound tree may be wrong.","fun_headline_variants_meta":{"raw":{"variants":["Closed-form bound makes L0 branch-and-bound generic","One formula unifies exact L0 sparse optimization","Generic L0 branch-and-bound with plug-and-play losses","Unified lower bound extends L0 solver to new problems"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000207,"raw_usage":{"total_tokens":1392,"prompt_tokens":930,"completion_tokens":462,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":546,"completion_tokens_details":{"reasoning_tokens":398}},"tokens_in":546,"tokens_out":462,"duration_ms":5111,"temperature":1.0,"reasoning_tokens":398,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T10:50:16.325713+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute the true biconjugate of g(x)=λ∥x∥0+σ|x| by numerical Legendre transform on a fine grid and compare it with formula (23) for several values of λ and σ, especially around x=μ; any mismatch, or any instance where the solver's lower bound exceeds the known global optimum, would falsify the central claim.","supporting_citations":[{"cited_title":"Springer (2017)","cited_arxiv_id":null,"evidence_quote":"Supplies the convex-analysis toolkit (biconjugate, subdifferential calculus, Moreau decomposition) used to prove Propositions 2-7."},{"cited_title":"SIAM (2017)","cited_arxiv_id":null,"evidence_quote":"Supplies the closed-function and Moreau-decomposition results used to manipulate g⋆⋆ and g⋆ and their proximal operators."},{"cited_title":"Optimization Methods and Software 37(5), 1740–1769 (2022)","cited_arxiv_id":null,"evidence_quote":"Gives a previous closed-form relaxation for a specific choice of h, the special case that the new formula generalizes."},{"cited_title":"The Annals of Statistics 44(2), 813–852 (2016)","cited_arxiv_id":null,"evidence_quote":"Introduces the modern mixed-integer-programming and branch-and-bound viewpoint that motivates exact ℓ0 optimization."},{"cited_title":"Journal of Machine Learning Research 24(205), 1–8 (2023)","cited_arxiv_id":null,"evidence_quote":"Provides the specialized L0bnb solver that the paper's numerical experiments compare against on its supported setting."},{"cited_title":"Mathematical Programming 196(1), 347–388 (2022)","cited_arxiv_id":null,"evidence_quote":"Provides the branch-and-bound approach rooted in first-order optimization that the generic solver builds on."},{"cited_title":"Mathematical Programming 151(1), 63–87 (2015)","cited_arxiv_id":null,"evidence_quote":"Gives the Boolean-relaxation result for h(x)=σ/2 x² that the new biconjugate formula recovers as a special case."}],"review_version":1}