{"id":"6e41ddce-7554-47af-b54d-ad49bdc45ebf","arxiv_id":"2412.05697","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":5.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"An inexact nonmonotone boosted DC algorithm is shown to converge to critical points under relative-error subproblem tolerances and summable error sequences, with O(1/sqrt(N)) iteration complexity.","lead":"This paper designs an inexact version of the boosted difference-of-convex algorithm that works when both parts of the objective are nondifferentiable, solving subproblems approximately and using a nonmonotone linesearch. The main result gives conditions under which every limit point of the iterates is a critical point, plus worst-case complexity bounds.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Algorithm 2's stopping rule can return a non-critical point when ε_k>0; the infinite-sequence convergence proof is sound, but the termination guarantee is weaker than the abstract's claim.","rationale":"The reader's verdict is CONDITIONAL and focuses on the relative-error oracle in Step 2. I agree that this oracle is a practical weak point, but the more concrete mathematical gap is the termination rule: because w_k is allowed to lie in the ε_k-subdifferential of h, the condition d_k=0 only guarantees an ε_k-critical point, not a critical point. The constructed 1D example satisfies all standing assumptions and makes Algorithm 2 stop immediately at a noncritical point. This does not invalidate the infinite-sequence convergence theorems, which are checked carefully and appear correct; it does mean the algorithm as stated can output a point outside the claimed criticality guarantee. The paper's own Proposition 13 is honest about this, so the fix is to weaken the termination claim or to require an exact subgradient of h, or to treat ε_k-criticality as the stopping certificate. The main mathematical contribution of the paper remains intact, hence I do not move the reader's CONDITIONAL verdict; I would only add this stopping-rule qualification to the revision conditions. The numerical section's disclaimer correctly states that no performance comparison is made, so the abstract's 'outperforms' wording remains an overclaim that should also be corrected, as the reader noted.","tokens_in":20929,"tokens_out":27698,"duration_ms":264784,"concrete_test":"Run Algorithm 2 on the one-dimensional instance g(x)=x²/2+x⁴/4, h(x)=x²/2+2x, ε_0=2, x_0=0, with any θ∈(0,1/2), ρ>0, β∈(0,1), and ν_0>0. At Step 2 take w_0=0 and y_0=0 (the exact minimizer of g−⟨0,·⟩); then d_0=0 and the algorithm returns 0. Verify that ∂g(0)={0} while ∂h(0)={2}, so the returned point is not critical. This settles whether the stated stopping rule can terminate at a noncritical point.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The infinite-sequence convergence proofs (Theorems 17, 18, 21) are internally sound, but the stopping rule in Algorithm 2 does not certify criticality when ε_k>0. In Step 2, w_k is chosen from ∂_{ε_k}h(x_k), and the pair (y_k, ξ_k) satisfying (11)-(12) can have d_k=0 at a point that is only ε_k-critical, not critical. Concretely, take g(x)=x²/2+x⁴/4, h(x)=x²/2+2x, ε_0=2, and x_0=0. Both g and h are strongly convex with modulus 1, and ϕ(x)=x⁴/4−2x is bounded below, so (H1)-(H2) hold. At x=0, ∂g(0)={0} and ∂h(0)={2}, so 0 is not critical. Since h(z)=z²/2+2z satisfies h(z)≥0·z−2 for all z (because (z+2)²/2≥0), we have 0∈∂_2 h(0). Choosing w_0=0, the exact minimizer of g(x)−⟨0,x⟩ is y_0=0, and ξ_0=0∈∂g(0) gives (12) with equality. Algorithm 2 then stops with d_0=0 and returns the noncritical point 0. Thus the output of the stated stopping rule is only an ε_k-critical point, exactly as Proposition 13 says, and the abstract's unconditional criticality claim is stronger than what the algorithm's termination guarantees. Separately, Step 2 is an oracle: the paper supplies no implementable inner-solver certificate for (12), so a finite-precision implementation may violate the hypothesis precisely when ∥d_k∥ is small.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript proposes an inexact nonmonotone boosted difference-of-convex algorithm (InmBDCA) for minimizing g−h where both g and h may be nondifferentiable but are strongly convex. At each iteration, the method chooses w_k in the ε_k-subdifferential of h at x_k and computes a pair (y_k, ξ_k) satisfying ξ_k ∈ ∂g(y_k) and ||w_k − ξ_k|| ≤ θ||y_k − x_k||; then it sets d_k = y_k − x_k and performs a nonmonotone Armijo-type linesearch. Under assumptions (H1)–(H2), with summable error parameters and with either summable or asymptotically controlled nonmonotonicity terms, the authors prove that every accumulation point of the infinite iterate sequence is a critical point in the sense ∂g ∩ ∂h ≠ ∅. They also provide O(1/sqrt(N)) iteration-complexity bounds on the minimal step norm. The numerical section reports two two-dimensional experiments verifying that approximate subproblem solutions obtained with fminsearch satisfy the relative-error inequalities used in the algorithm.","tokens_in":21294,"tokens_out":11540,"duration_ms":107405,"significance":"If the theoretical results are taken at face value, the paper gives a useful extension of BDCA/nmBDCA to an inexact setting with fully nonsmooth DC decompositions. The proof architecture is coherent: Proposition 13 provides a clean descent estimate, Proposition 16 correctly transfers d_k→0 into criticality via subdifferential closure, and Theorems 17, 18, and 21 establish the stated accumulation-point and complexity results under explicit assumptions. The authors also provide explicit bounds rather than only qualitative convergence, and the numerical section makes a step toward showing that the relative-error condition can actually be satisfied by black-box solvers. However, the paper as written has several mismatches between the algorithm's stated parameter ranges and the theorem hypotheses, an oracle formulation of the key inner step, a stopping-rule guarantee that is weaker than the abstract claims, and an unsupported numerical performance claim. These issues affect the precision and scope of the main claims, though the central derivation appears fixable.","major_comments":[{"comment":"The abstract states that 'Numerical experiments show that InmBDCA outperforms both the nonsmooth BDCA (nmBDCA) and the monotone version of DCA in practical scenarios,' but Section 8 explicitly says 'we are not focused on analyzing the computational performance of the method compared to others' and only verifies that the relative-error inequalities (11)–(12) hold for two examples. The numerical performance claim is therefore unsupported by the reported experiments and must be corrected or replaced with an actual comparison.","section":"Abstract and Section 8"},{"comment":"The entire convergence analysis depends on the existence, at every iteration, of a pair (y_k, ξ_k) satisfying the relative-error condition ||w_k − ξ_k|| ≤ θ||y_k − x_k|| with ξ_k ∈ ∂g(y_k). The paper proves existence via the exact solution of subproblem (7), but no implementable procedure or finite-time certificate is given for an inexact solver to obtain such a pair; the numerical section checks (11)–(12) only after the computation. Since Proposition 13 and Theorem 14 use (12) to derive the descent estimate, a finite-precision implementation that cannot certify (12) falls outside the stated guarantees. This should be stated explicitly as an oracle assumption, or an implementable inner-line-search/stopping rule with a verifiable certificate should be provided.","section":"Algorithm 2, Step 2, equations (11)–(12)"},{"comment":"The algorithm allows ν_k ≥ 0, and Theorems 17, 18, and 21 state assumptions only in terms of (A2) or (A3), which do not exclude ν_k = 0. However, Theorem 14 and Proposition 15, which justify well-definiteness of the linesearch and the descent estimate, explicitly assume ν_k > 0. If ν_k = 0 and d_k is not a descent direction for the nondifferentiable DC objective, the while loop in Step 3 need not terminate. The convergence and complexity theorems therefore do not cover the stated parameter range; either ν_k > 0 should be made a standing requirement, or the ν_k = 0 case must be analyzed separately.","section":"Algorithm 2, Step 3, and Theorems 14–18"},{"comment":"The stopping rule 'If d_k = 0 then STOP and return x_k' does not guarantee that x_k is critical for problem (5) when ε_k > 0; Proposition 13 only yields ε_k-criticality. A concrete instance is g(x) = x^2/2 + x^4/4, h(x) = x^2/2 + 2x, ε_0 = 2, x_0 = 0, for which all assumptions hold and Algorithm 2 returns the noncritical point 0. Moreover, the abstract's claim about accumulation points is an infinite-sequence statement and does not apply to a finite terminated run. The authors should either require ε_k = 0 at termination, or explicitly state that the finite output is an ε_K-critical point, and align the abstract and conclusion with that guarantee.","section":"Algorithm 2, Step 3, stopping rule"}],"minor_comments":[{"comment":"The term 'ε_k-critical point' is used in the statement and proof but never defined in the paper; please add a formal definition and use it consistently throughout the stopping-rule discussion.","section":"Proposition 13"},{"comment":"The remark claims that 'strict convexity of the objective function guarantees the uniqueness of minimizers; see Proposition 5,' but Proposition 5 applies to a differentiable strongly convex function, while the DC objective φ = g − h is not necessarily convex; the justification should be rephrased or removed.","section":"Remark 2"},{"comment":"The statement of Theorem 22 writes 'ε_k ≤ ξ(ρ/2 − θ)||d_k||^2' while the proof uses σ/2 − θ; this appears to be a typo and should be corrected.","section":"Theorem 22"},{"comment":"The theorem statement has a factor (1 − ξ) in the denominator of the complexity bound, whereas the proof derives the bound with (1 − 2ξ); the displayed statement and the proof should be harmonized.","section":"Theorem 22"},{"comment":"The initialization of the linesearch permits ¯λ_k = 0; with ¯λ_k = 0 the while loop never changes x_{k+1}, and the algorithm would not make progress. Either require ¯λ_k > 0 or explain why zero initial steps are admissible.","section":"Algorithm 2 and Theorem 14"},{"comment":"The y-axis label '|| k−wk||' should presumably be '||ξ_k − w_k||', and the phrase 'MATLAB solves Example 5 inaccurately' is unclear; please clarify what 'inaccurately' means in that context.","section":"Section 8, Figures 1 and 2"}],"recommendation":"major_revision","confidential_remarks":"The theoretical core of the paper is largely sound, but the abstract overstates the numerical results, and the algorithm relies on an unstated oracle condition in Step 2. The ν_k > 0 gap and the stopping-rule issue are substantial but fixable. If the authors correct these points and revise the abstract, the paper could become acceptable for publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: the central math holds up, and the paper is a legitimate, if incremental, extension of nmBDCA to inexact subproblem solves. The issues are in the framing and the abstract, not the proofs.\n\nWhat's actually new: Algorithm 2, InmBDCA, weakens the subproblem solve in nmBDCA to allow a relative error tolerance (12), using ε-subdifferentials of h and a nonmonotone Armijo linesearch. The convergence results—Theorems 17, 18, and 21—are correct: under summable error ε_k and standard nonmonotonicity strategies, every accumulation point is critical, with an O(1/√N) bound on the best ||d_k||. The descent estimate in Proposition 13 and the well-definedness proof in Theorem 14 check out; the relation to exact nmBDCA (θ=0, ε_k=0) is clearly stated.\n\nCredit where due: this is the first inexact BDCA variant I know of for the nonsmooth case, and the proofs are careful. The numerical section honestly disclaims performance comparison—it only verifies that the computed quantities satisfy (11)–(12), which is appropriate.\n\nSoft spots, in order of importance. The abstract claims InmBDCA \"outperforms\" nmBDCA and monotone DCA, but Section 8 says the opposite: the experiments do not compare performance. That should be corrected. Second, the stopping rule in Algorithm 2 is not a criticality certificate. If d_k = 0 at an iteration with ε_k > 0, the point is only ε_k-critical, as Proposition 13 states. The stress-test example (g = x^2/2 + x^4/4, h = x^2/2 + 2x, ε_0 = 2, x_0 = 0) hits this exactly: d_0 = 0 at a non-critical x_0. The infinite-sequence theorems are unaffected, but the algorithm as written can terminate with an approximate, not exact, critical point, and the abstract should not blur that. Third, condition (12) is an oracle: no implementable certificate is given for verifying it, so a finite-precision implementation may violate the assumption precisely when ||d_k|| is small. The authors verify (11)–(12) numerically in two examples, but that is not a general procedure. Finally, there are minor typos—the proof of Theorem 20 has the inequality direction reversed, and Theorem 22 uses ρ where the proof needs σ.\n\nBottom line: this is a solid, careful extension with a correct proof. The packaging needs a serious revision, especially the abstract's performance claim and a caveat on the stopping rule. Worth sending to a good refereed venue; the mathematics should survive review.","headline":"A sound, incremental extension of nmBDCA to inexact subproblem solves, with correct proofs but an overstated abstract and a stopping rule that only certifies ε-criticality.","tokens_in":21824,"tokens_out":5243,"would_cite":true,"duration_ms":41586,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["49J53","90C26","65K05","65K10"],"pacs":[],"model":"deepseek-v4-flash","headline":"Inexact boosted DC algorithm with approximate subproblem solves and nonmonotone line search still converges to critical points for nondifferentiable difference-of-convex problems, at O(1/√N) step-norm complexity.","keywords":["DC functions","Boosted difference of convex functions algorithm","Nonmonotone linesearch","Convergence analysis","Complexity analysis","Inexact algorithm","Nondifferentiable optimization"],"falsifier":"Run exactly the paper's Algorithm 2 on a DC program with a known unique minimizer (such as Example 5, $\\varphi(x,y) = x^2 + y^2 + x + y - |x| - |y|$), verifying at each iteration that $w_k \\in \\partial_{\\varepsilon_k} h(x_k)$, $\\xi_k \\in \\partial g(y_k)$, and $\\|w_k - \\xi_k\\| \\le \\theta \\|y_k - x_k\\|$ with summable $\\varepsilon_k$ and $\\nu_k$ chosen by (A2). If the iterates accumulate at any point $\\bar{x}$ with $\\partial g(\\bar{x}) \\cap \\partial h(\\bar{x}) = \\emptyset$, the main theorem is false; conversely, if the hypotheses hold and every accumulation point is critical, the claim is confirmed.","tokens_in":20746,"feed_emoji":"🎯","tokens_out":13287,"duration_ms":102649,"temperature":0.7,"pith_summary":"The paper presents an inexact version of the Boosted Difference of Convex Functions Algorithm (BDCA) for minimizing functions written as the difference of two convex functions, allowing both parts to be nondifferentiable. In the proposed algorithm, the convex subproblem that generates each search direction is solved only approximately, up to a controlled relative error, and the step size is chosen by an inexact nonmonotone Armijo line search. Under the assumptions that both DC components are strongly convex, the objective is bounded below, the error-tolerance sequence is summable, and the nonmonotonicity parameters follow one of three strategies, the algorithm is well-defined and every accumulation point of its iterates is a critical point of the DC program. The paper also gives an $O(1/\\sqrt{N})$ iteration-complexity bound on the minimal step norm and reports numerical experiments where the inexact method outperforms the nonmonotone BDCA and the monotone DCA.","feed_headline":"Inexact solves keep boosted DC algorithm convergent to critical points","feed_subtitle":"Approximate subproblem solves still yield critical limit points, with an O(1/sqrt(N)) step-length bound.","key_machinery":"The load-bearing object is the relative-error condition $\\|w_k - \\xi_k\\| \\le \\theta \\|y_k - x_k\\|$ together with $w_k \\in \\partial_{\\varepsilon_k} h(x_k)$ and $\\xi_k \\in \\partial g(y_k)$. This condition makes the approximate subproblem solve 'exact enough': combined with the strong convexity of $g$ and $h$, it yields the descent estimate $\\varphi(y_k) \\le \\varphi(x_k) - (\\sigma/2 - \\theta)\\|d_k\\|^2 + \\varepsilon_k$ (Proposition 13), playing the role that the descent lemma plays in exact DCA and BDCA. The second mechanism is the nonmonotone Armijo line search with slack $\\nu_k$; it keeps the line search well-defined even when $d_k$ is not a descent direction, and the summability/decay conditions on $\\nu_k$ control the cumulative slack so that the quasi-monotone decrease still forces $\\|d_k\\| \\to 0$. The $\\varepsilon_k$-subdifferential of $h$, defined by $h(z) \\ge h(x) + \\langle w, z - x \\rangle - \\varepsilon_k$, is what allows inexact subgradient information at the current iterate.","core_discovery":"The central claim is that the acceleration strategy of BDCA can be made inexact without losing convergence, even when the first DC component is nondifferentiable and the subproblem cannot be solved exactly. Specifically, for the problem $\\min \\varphi = g - h$ with $g$ and $h$ strongly convex of modulus $\\sigma > 0$ and $\\varphi$ bounded below, the algorithm at each iteration chooses an $\\varepsilon_k$-subgradient $w_k$ of $h$ at $x_k$, computes an approximate solution $y_k$ of the subproblem together with a subgradient $\\xi_k$ of $g$ at $y_k$ satisfying the relative-error condition $\\|w_k - \\xi_k\\| \\le \\theta \\|y_k - x_k\\|$ for fixed $\\theta < \\sigma/2$, and then performs a nonmonotone Armijo line search along $d_k = y_k - x_k$ with nonmonotonicity measure $\\nu_k$. If the $\\nu_k$ follow strategy (A2) (summable) or (A3) (eventually small relative to $\\|d_k\\|^2$) and the errors $\\varepsilon_k$ are summable, then every accumulation point of $(x_k)$ is critical, meaning $\\partial g(\\bar{x}) \\cap \\partial h(\\bar{x}) \\ne \\emptyset$ (Theorems 17, 18, and 21). The proof engine is the descent estimate $\\varphi(y_k) \\le \\varphi(x_k) - (\\sigma/2 - \\theta)\\|d_k\\|^2 + \\varepsilon_k$, which holds even though $d_k$ need not be a descent direction, and which turns the algorithm into a quasi-monotone process. The complexity bound is $\\min_{0 \\le k \\le N-1} \\|d_k\\| \\le C/\\sqrt{N}$, with $C$ depending only on the initial gap, the sums of $\\nu_k$ and $\\varepsilon_k$, and $\\sigma/2 - \\theta$.","pith_inferences":["In practice the true bottleneck is not the line search but the relative-error certificate: for nonsmooth convex $h$, producing $w_k \\in \\partial_{\\varepsilon_k} h(x_k)$ and then bounding its distance to some $\\xi_k \\in \\partial g(y_k)$ requires solving a nearby convex problem, so an adaptive $\\theta$ or a duality-gap surrogate for (12) would be a natural follow-up.","The convergence target is criticality, which is strictly weaker than the stationarity notion based on the limiting subdifferential (whose calculus rules would require plus-minus symmetry that $\\partial \\varphi$ lacks); the paper notes in Remark 3 that the symmetric subdifferential construction could be used to get stronger stationarity.","The same quasi-monotone accounting (descent estimate plus slack plus summable errors) could be transplanted to other DC variants such as proximal or inertial algorithms with approximate oracles, simply by swapping the descent estimate while keeping the slack/error bookkeeping."],"forward_implications":["When both DC components are nondifferentiable and only approximate subproblem solves are available, the algorithm still provably converges to critical points, so inexact inner solvers can be used without losing the convergence guarantee.","The complexity estimate means that after about $O(1/\\varepsilon^2)$ iterations, some step $\\|d_k\\|$ is below $\\varepsilon$, giving a concrete stopping criterion for practical implementations.","Setting $\\varepsilon_k = 0$ and $\\theta = 0$ recovers the exact nonmonotone BDCA, so the analysis contains the existing nmBDCA theory as a special case.","The nonmonotonicity strategies (A1)–(A3) provide concrete, checkable rules for choosing $\\nu_k$, including the cost-update scheme of [44], which makes the slack an algorithmic parameter rather than an abstract assumption."],"supporting_citations":[{"why":"Presents the original accelerated BDCA for smooth DC components; the paper describes InmBDCA as an inexact variant of it.","marker":"[3]"},{"why":"Introduces the BDCA line search for nonsmooth DC problems that InmBDCA builds on.","marker":"[5]"},{"why":"Supplies the nonmonotone line search strategies (A1)–(A3) that are adapted to the inexact setting.","marker":"[18]"},{"why":"Provides the strong convexity and Lipschitz gradient tools used in the descent estimates and Proposition 13.","marker":"[9]"},{"why":"Gives the epsilon-subdifferential properties (Propositions 6 and 7) that justify the approximate subgradient step.","marker":"[22]"},{"why":"Provides the nonmonotone cost-update scheme used in Example 2 as a concrete realization of strategy (A2).","marker":"[44]"}],"fun_headline_variants":["Inexact boosted DC algorithm converges for nonsmooth functions","Inexact boosted DCA hits critical points via nonmonotone steps","Approximate subproblems still yield critical points in boosted DC","Inexact nonmonotone DC algorithm keeps convergence guarantee"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that at every iteration a solver can certify a pair $(y_k, \\xi_k)$ satisfying the relative-error bound $\\|w_k - \\xi_k\\| \\le \\theta \\|y_k - x_k\\|$ for the fixed tolerance $\\theta < \\sigma/2$; if no such certificate can be produced, the descent estimate and all downstream convergence and complexity claims no longer have ground to stand on.","fun_headline_variants_meta":{"raw":{"variants":["Inexact boosted DC algorithm converges for nonsmooth functions","Inexact boosted DCA hits critical points via nonmonotone steps","Approximate subproblems still yield critical points in boosted DC","Inexact nonmonotone DC algorithm keeps convergence guarantee"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001014,"raw_usage":{"total_tokens":4442,"prompt_tokens":1267,"completion_tokens":3175,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":883,"completion_tokens_details":{"reasoning_tokens":3103}},"tokens_in":883,"tokens_out":3175,"duration_ms":21663,"temperature":1.0,"reasoning_tokens":3103,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T20:26:09.988174+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run exactly the paper's Algorithm 2 on a DC program with a known unique minimizer (such as Example 5, $\\varphi(x,y) = x^2 + y^2 + x + y - |x| - |y|$), verifying at each iteration that $w_k \\in \\partial_{\\varepsilon_k} h(x_k)$, $\\xi_k \\in \\partial g(y_k)$, and $\\|w_k - \\xi_k\\| \\le \\theta \\|y_k - x_k\\|$ with summable $\\varepsilon_k$ and $\\nu_k$ chosen by (A2). If the iterates accumulate at any point $\\bar{x}$ with $\\partial g(\\bar{x}) \\cap \\partial h(\\bar{x}) = \\emptyset$, the main theorem is false; conversely, if the hypotheses hold and every accumulation point is critical, the claim is confirmed.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Presents the original accelerated BDCA for smooth DC components; the paper describes InmBDCA as an inexact variant of it."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces the BDCA line search for nonsmooth DC problems that InmBDCA builds on."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the nonmonotone line search strategies (A1)–(A3) that are adapted to the inexact setting."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the strong convexity and Lipschitz gradient tools used in the descent estimates and Proposition 13."},{"cited_title":"Springer, Berlin (1993)","cited_arxiv_id":null,"evidence_quote":"Gives the epsilon-subdifferential properties (Propositions 6 and 7) that justify the approximate subgradient step."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the nonmonotone cost-update scheme used in Example 2 as a concrete realization of strategy (A2)."}],"review_version":1}