{"id":"83d28f1f-4891-4450-9ae9-baeec7226a4a","arxiv_id":"2506.08374","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"A primal 0/1-loss composite problem is recast as a nonconvex ℓ0-regularized dual, and a subspace gradient semismooth Newton method solves it with global and locally quadratic convergence.","lead":"The paper builds a 'stationary dual' for minimizing a strongly convex function plus a zero-one loss on linear terms, turning the problem into sparse optimization with an ℓ0 penalty and a nonnegativity constraint. It then designs a subspace semismooth Newton method with global and local superlinear convergence, and tests it on AUC and multi-label classification.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The global-convergence theorem is conditional on a boundedness assumption (Assumption 1) that SGSN can fail to satisfy on a valid instance: from a nullspace ray the iterates diverge even though a P-stationary point and primal local minimizer exist.","rationale":"The paper's central novelty is Theorem 10 (local-minimizer equivalence between primal and dual) plus the claim that SGSN is the first algorithm with both global convergence and local superlinear rate for Problem (1). The equivalence argument appears structurally sound; I found no hidden inconsistency there. The load-bearing point is the global-convergence half: Theorem 16 assumes the iterates are bounded (Assumption 1), but SGSN has no mechanism enforcing boundedness and the dual objective is not coercive. Because the l0 regularizer is flat along rays z=t*d with d>=0 and A^T d=0, the linear term -<b,z> can drive F to -infinity. On the simple instance above, a primal local minimizer and a dual P-stationary point coexist, yet every proximal gradient step from (T,T) sends (t,t) to (t+tau,t) and the Newton step is rejected for the paper's stated parameter choice, so the iterate set is unbounded. Thus 'global convergence' cannot be read as an unconditional guarantee: it applies only to runs that by assumption stay bounded. This matches and sharpens the reader's weakest assumption. It does not invalidate the conditional theorems, so the appropriate verdict remains CONDITIONAL, with the condition that boundedness/coercivity be either guaranteed, checked, or relaxed (e.g., by an explicit safeguarding rule).","tokens_in":34961,"tokens_out":14526,"duration_ms":187407,"concrete_test":"Run SGSN on the instance f(x)=0.5x^2, A=[1;-1]^T, b=[1;0], mu=1, tau=0.25, gamma=0.1, c1=1/6, c2=6, starting from z^0=(100,100). The iteration is analytically computable: the proximal gradient step sends (t,t) to (t+0.25,t), and the Newton candidate is rejected by (C1) because F(v)-F(ez) is about 6.36, which is less than c1*||ez-v||^2 about 13.34. Hence z^{k+1}=(t+0.25,t) and z^k tends to (infinity,infinity), while z*=0 is a P-stationary point with a corresponding primal local minimizer. If this divergence is observed, Assumption 1 is not guaranteed by the data, and the global-convergence statement must be qualified as applying only to bounded runs.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Assumption 1 (Section 4.2, Remark 2) requires the SGSN iterates {z^k} to be bounded, but this is not implied by the problem data. With h(z)=f^*(-A^T z)-<b,z> and g(z)=mu*||z||_0+delta_+(z), the dual objective F(h+g) can be unbounded below along any ray z=t*d with d>=0, A^T d=0, and <b,d>>0, because g stays constant while h goes to -infinity. Such rays exist precisely when A is row-rank deficient, a case the paper explicitly wants to allow. Example: f(x)=0.5x^2, A=[1;-1]^T, b=(1,0)^T, mu=1, tau=0.25, gamma=0.1, c1=1/(3*ell_h)=1/6, c2=3*ell_h. Here z*=0 is a P-stationary point of (21) and corresponds to the primal local minimizer x*=0. From z^0=(T,T) with T large, the proximal gradient step maps (t,t) to (t+tau,t); the Newton candidate has d=(6.445,6.206), and C1 fails uniformly in t (F(v)-F(ez) is about 6.36 while c1*||ez-v||^2 is about 13.34), so z^{k+1}=v and the iterates diverge along the ray. Thus Theorem 16's boundedness premise is not a mild verifiable condition; it selects exactly the runs that happen not to escape. The 'first algorithm with both global convergence and local superlinear rate' claim is therefore substantially weaker than the abstract's wording suggests, even though the conditional theorems are internally consistent.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the nonconvex composite problem min_x f(x) + I(Ax+b), where I is a sum of zero-one indicators on positive intervals and f is strongly convex. Because the Fenchel conjugate of I is trivial, the authors construct a 'stationary dual' g(z)=μ||z||_0+δ_+(z) satisfying the subdifferential inversion relation z∈∂I(u) iff u∈∂g(z). They show that local minimizers of the primal problem correspond to local minimizers of the dual problem min_z F(z)=h(z)+g(z) with h(z)=f^*(-A^T z)-⟨b,z⟩ (Theorem 10). They then propose a subspace gradient semismooth Newton method (SGSN) that alternates a proximal gradient step, which identifies the support T_k, with a semismooth Newton step on that support. Global convergence is proved under a boundedness assumption and a PLK assumption (Theorem 16), and local superlinear convergence is proved under a semismoothness and reduced positive-definiteness assumption (Theorem 19). Numerical experiments on AUC maximization and sparse multi-label classification show competitive speed and accuracy.","tokens_in":35400,"tokens_out":15463,"duration_ms":194076,"significance":"The stationary duality idea is genuinely interesting: replacing the unavailable conjugate of the zero-one loss by an ℓ0-plus-nonnegativity function whose subdifferential inverts that of the indicator is a useful construction, and the main equivalence theorem is sound once a small typo in the proof of Proposition 5 is fixed. The algorithm has low per-iteration complexity, and the numerical study is extensive and largely supports the practical value of the method. However, the paper's central 'global convergence' claim is conditional on Assumption 1, which is not implied by the problem data and can fail on a valid instance with row-rank-deficient A; this weakens the claim that SGSN is the first algorithm with both global convergence and local superlinear rate for Problem (1). The local analysis under Assumption 3 appears correct and is a genuine contribution.","major_comments":[{"comment":"The boundedness assumption on the generated sequence {z^k} is not a mild or verifiable condition, and SGSN can fail it on a valid instance even when the stationary set is nonempty. Consider f(x)=x^2/2, A=[1;-1]^T, b=(1,0)^T, μ=1, τ=0.25, γ=0.1, c1=1/6, c2=6. Here ℓ_h=2, z*=0 is a P-stationary point of (21), and x*=0 is a local minimizer of (1). Starting at z^0=(T,T), the proximal gradient step (32) gives v^0=(T+0.25,T); the Newton direction is approximately (6.46,6.22), and condition (C1) fails (F(v)-F(ez)≈6.37 while c1||ez-v||^2≈13.4), so z^1=v^0. The same pattern repeats and the iterate diverges along the nullspace ray of A^T while F(z)→-∞. Thus Assumption 1 is not implied by the data and selects exactly those runs that happen not to escape. The global convergence theorem should be restated with explicit sufficient conditions that can be checked from the problem data (for example, exclusion of b-components in the nullspace of A^T that make F unbounded below), or the algorithm should be safeguarded against such rays. As written, the abstract's and Section 1.2's claim of 'global convergence' is substantially weaker than stated.","section":"§4.2, Assumption 1 and Theorem 16"},{"comment":"The local superlinear convergence result is conditional not only on Assumption 3 but also on the same Assumption 1, since the proof first uses Assumption 1 to obtain convergence of {v^k} to z* (see Remark 3(iii)). In the counterexample above, the sequence does not converge, so the local rate theorem does not apply even though the dual objective is semismooth and the reduced positive-definiteness condition is satisfied at z*=0 (vacuously, since S*=∅). The contribution statement in Section 1.2 should therefore be qualified: SGSN is the first algorithm with local superlinear rate and global convergence under an a priori boundedness condition on the iterates, not for Problem (1) in general. This is a genuine limitation, not merely a presentational issue.","section":"Section 4.3, Theorem 19 and the 'first algorithm' claim"}],"minor_comments":[{"comment":"The displayed inclusion {i:u_i>0} ⊇ J_-^* appears to have the wrong set. To justify I(u)≥I(u*) for u near u*, one needs all indices with u*_i>0 to remain positive, i.e., {i:u_i>0} ⊇ [m]\\J_-^*. As written, the proof's claim in the F*∩N(w*,δ*) case does not follow, although the argument is easily repaired.","section":"Proposition 5, equation (20)"},{"comment":"At the end of the proof of part (iv), the text says 'we complete the proof of (iii)' but should say '(iv)'. This is a minor cross-reference error.","section":"Lemma 1, proof of part (iv)"},{"comment":"The heading 'converges to z* with local superliner rate' contains a typo; it should read 'superlinear'.","section":"Theorem 19 heading"},{"comment":"The phrase 'one-to-one correspondence between local minimizers' is stronger than what Theorem 10 establishes. The theorem gives mutual implication with a recovery formula, but when the KKT multiplier is nonunique, the correspondence need not be a literal bijection between solution sets. The wording should be softened to 'equivalence'.","section":"Section 1.2, Theorem 10 description"},{"comment":"The experiments set c2=3ℓ_h, whereas Lemma 18(iii) proves the Newton acceptance condition under c2≥ℓ_h+η4+1, which in the AUC setting is 3ℓ_h+1. The numerical choice slightly violates the proven sufficient condition; either the condition should be stated with a smaller constant or the experiment should use the theory-consistent value.","section":"Section 5.1, parameter setting"},{"comment":"The column headers 'RSF', 'LLSF', and 'MFDS' are typos for RFS, LLFS, and MDFS used elsewhere in the text and in Table 3.","section":"Table 5"}],"recommendation":"major_revision","confidential_remarks":"The stationary duality framework and the local convergence analysis are sound and worth publishing after revision. The main issue is that the global convergence claim is conditional on a boundedness assumption that can fail on a valid instance with row-rank-deficient A; the authors should either add a checkable sufficient condition, modify the algorithm to prevent divergence along nullspace rays, or substantially qualify the 'first algorithm with global convergence and local superlinear rate' claim. I also recommend proofreading the Proposition 5 inclusion and the parameter-setting discrepancy in Section 5.1."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear Colleague,\n\nThe useful core of this paper is the stationary-duality construction: replacing the Fenchel conjugate of the 0/1 indicator with g(z)=μ||z||0+δ_+(z) and proving the subdifferential inversion z∈∂I(u)⇔u∈∂g(z). That gives a genuine dual problem (21) and a clean one-to-one correspondence between local minimizers (Theorem 10). The proofs in Section 3 are careful and mostly check out; the equivalence is somewhat built into the definition of g, but once you accept that trick, the correspondence is real. SGSN is also a reasonable piece of algorithm design: proximal gradient step for globalization, a subspace Newton step on the identified support, and (C1)-(C2) for acceptance. The PLK-based global convergence and the semismooth Newton local rate are nontrivial.\n\nNow the soft spots.\n\nThe global convergence theorem (Theorem 16) rests on Assumption 1: the iterates are bounded. This is not a mild or verifiable condition. Because A is allowed to be row-rank deficient (the paper explicitly wants to cover composite ℓ0), the dual objective can be unbounded below along a nullspace ray. The stress-test example is correct: take f(x)=0.5x^2, A=[1;-1], b=(1,0), μ=1, τ=0.25, γ=0.1. Then z*=0 is a P-stationary point of (21) and corresponds to primal local minimizer x*=0, but along z=t(1,1) the dual objective goes to -∞, and SGSN started at z^0=(T,T) produces v^k=(T+0.25k, T), diverging; the Newton candidates fail (C1) every time. So Theorem 16's premise selects exactly the runs that do not escape. The abstract's phrase \"global convergence ... under mild conditions\" and the claim of being 'the first algorithm that enjoys both global convergence and local superlinear rate' are substantially weaker than advertised. The conditional theorems are internally fine, but the headline claim needs to be softened or the algorithm needs a safeguard.\n\nMinor issues: the inclusion direction in (20) looks off (likely a typo), and the numerical section is persuasive but not reproducible—no code, no error bars, and the reported τ and c values don't always match the theory (e.g., the adaptive τ in Section 5.2).\n\nWho should read this? Anyone working on nonconvex composite optimization, 0/1 loss, or dual methods for sparse problems. The duality framework is worth engaging with seriously; the algorithm needs another pass before it can be called globally convergent in a meaningful sense.\n\nI would send this to a serious referee. With revision, it could be a solid paper. Would I cite it? The duality construction, yes; the convergence claim, no.\n\nBest.","headline":"The stationary-duality frame is new and the equivalence theorem holds up, but the global convergence claim is conditional on a boundedness assumption that can fail on simple valid instances, so the 'first algorithm' claim is overstated.","tokens_in":35911,"tokens_out":6838,"would_cite":true,"duration_ms":78122,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C26","90C46","90C53","49J52"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims that minimizing a strongly convex function plus a zero-one loss can be recast as a sparse dual problem, with local minimizers in one-to-one correspondence, and that a subspace semismooth Newton method on that dual…","keywords":["composite optimization","zero-one loss","indicator function","stationary duality","semismooth Newton method","L0 regularization","global convergence","AUC maximization"],"falsifier":"Construct data with a nonzero $d\\ge 0$ satisfying $A^\\top d=0$ and $\\langle b,d\\rangle>0$, then run SGSN: $F(td)\\to -\\infty$ as $t\\to\\infty$, so no bounded sequence exists and global convergence cannot hold. To test the rate claim instead, run SGSN on an instance satisfying the semismooth and positive-definiteness assumptions and check whether the support $T_k$ eventually equals the true support and whether $\\lVert z^{k+1}-z^*\\rVert/\\lVert z^k-z^*\\rVert\\to 0$; a single instance where $T_k$ keeps changing indefinitely would contradict the support-identification lemma.","tokens_in":34728,"feed_emoji":"📉","tokens_out":6946,"duration_ms":81559,"temperature":0.7,"pith_summary":"Minimizing a strongly convex function plus a zero-one (indicator) loss is hard because the loss is discontinuous and the standard Fenchel dual is degenerate: the conjugate of the indicator is finite only at zero. This paper bypasses that obstruction by replacing the conjugate with a specially constructed function $g(z)=\\mu\\lVert z\\rVert_0+\\delta_+(z)$ that satisfies a stationarity correspondence with the indicator's limiting subdifferential. The resulting dual is a sparse optimization with an $\\ell_0$ regularizer and nonnegativity constraint, and the paper proves a one-to-one correspondence between local minimizers of the primal and of this dual. On the dual, a proximal gradient step identifies a support subspace, and within that subspace a semismooth Newton step drives the iteration; the paper proves global convergence to a P-stationary point and local superlinear (or quadratic) rate under stated assumptions. If correct, this gives the first algorithm for the primal class with both global convergence and fast local rate, and the experiments on AUC maximization and sparse multi-label classification show the dual route is competitive or faster than existing solvers.","feed_headline":"Zero-one loss tamed by a sparse dual Newton method","feed_subtitle":"Strong convexity plus 0/1 losses becomes a sparse dual problem with global and superlinear convergence.","key_machinery":"The load-bearing object is the stationary-duality function $g(z)=\\mu\\lVert z\\rVert_0+\\delta_+(z)$, defined so that $z\\in\\partial I(u)$ if and only if $u\\in\\partial g(z)$; this replaces the classical conjugate, which is degenerate for the zero-one indicator. Its proximal operator has a closed form: each coordinate is kept when it exceeds $\\sqrt{2\\tau\\mu}$ and otherwise set to zero, which lets SGSN identify the support $T_k$ and restrict computation to that subspace. The second ingredient is the semismooth Newton step in the reduced subspace, regularized by $\\gamma_k I$ and accepted only when sufficient-descent and residual conditions hold; the P LK sharpness inequality then converts local descent into global convergence, and semismoothness plus positive definiteness of the generalized Hessian on the support subspace produces the superlinear rate.","core_discovery":"The central claim is Theorem 10: a point $w^*=(x^*,u^*)$ is a local minimizer of $\\min f(x)+I(u)$ subject to $Ax+b=u$ if and only if the associated multiplier $z^*$ is a local minimizer of the dual problem $\\min_z h(z)+g(z)$, where $h(z)=f^*(-A^\\top z)-\\langle b,z\\rangle$ and $g(z)=\\mu\\lVert z\\rVert_0+\\delta_+(z)$; the correspondence is explicit, with $x^*=\\nabla f^*(-A^\\top z^*)$. Because the dual's nonsmooth term is a sparse regularizer with a closed-form proximal operator, a subspace can be identified cheaply, and the paper's SGSN method alternates a proximal gradient step and a regularized semismooth Newton step in that subspace. Under boundedness of the generated sequence, the P LK property, semismoothness of $\\nabla f^*$, and a reduced positive-definiteness condition, the iteration converges to a P-stationary point at a superlinear rate, and the paper claims this combination is the first for Problem (1).","pith_inferences":["The stationary-duality construction is not tied to the specific indicator $1_{(0,\\infty)}$: any loss whose limiting subdifferential has the same pattern (all nonnegative multipliers at zero, zero elsewhere) should admit an analogous $g$, so the approach may extend to other discontinuous losses.","The dual support set is an active-set certificate. In AUC it identifies the margin pairs that constrain the solution, suggesting an online or incremental variant that adds pairs only when they are violated.","The weakest point is boundedness: adding an explicit constraint or proximal term in the dual to force boundedness even when $h$ is unbounded below along the nullspace of $A^\\top$ would make the global theorem depend only on problem data rather than on iterate behavior.","The one-to-one correspondence plus explicit primal reconstruction $x^*=\\nabla f^*(-A^\\top z^*)$ gives a natural hot-starting mechanism for primal-dual methods on zero-one problems, which the paper leaves for future work."],"forward_implications":["Solving the sparse dual yields a local minimizer of the original zero-one problem, so combinatorial search over configurations of the loss is replaced by continuous sparse optimization.","Per-iteration cost is $O(|T_k|n)$ for the gradient step and $O(n|T_k|^2)$ for the Newton system when $f$ is separable, making problems with millions of pairs such as AUC maximization tractable.","The method does not require $A$ to have full row rank, so it covers composite $\\ell_0$ norms written as $I(Bx+b)+I(-Bx-b)$.","Once the support of the dual solution is identified, the iteration is essentially a smooth Newton method on a fixed subspace, so numerically the final digits converge superlinearly or quadratically.","In AUC, the dual variable lives over sample pairs and its support selects the informative pairs; in multi-label classification with elastic net, SGSN returns sparse classifiers with low Hamming loss."],"supporting_citations":[{"why":"Supplies the primal KKT characterization and smoothing Newton baseline for the zero-one loss problem that this paper extends and compares against.","marker":"[70]"},{"why":"Provides Fenchel duality and the conjugate-subdifferential property that the paper extends to the indicator function.","marker":"[56]"},{"why":"Source of the limiting subdifferential, proximal behavior, and subdifferential calculus used throughout the paper.","marker":"[57]"},{"why":"Supplies generalized Jacobians, semismoothness, and second-order sufficient conditions used for the local superlinear rate.","marker":"[21]"},{"why":"Provides the P LK / semi-algebraic convergence framework used for the global convergence analysis.","marker":"[8]"},{"why":"Subspace Newton method for $\\ell_0$-regularized optimization that SGSN generalizes and benchmarks against.","marker":"[69]"},{"why":"Coderivative-based Newton method used as a comparison baseline and a source of P-stationarity and proximal-point properties.","marker":"[35]"},{"why":"Classical semismooth Newton method whose local convergence machinery the paper adapts to the subspace setting.","marker":"[55]"},{"why":"Provides the descent lemma and conjugate-function smoothness properties used in the descent arguments.","marker":"[3]"}],"fun_headline_variants":["Dual view tames 0/1 loss with sparse Newton","First dual for indicator functions","L0-regularized dual enables superlinear Newton","Semismooth Newton on sparse dual for 0/1 loss"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"Everything about global convergence rests on the assumption that the iterates $\\{z^k\\}$ stay bounded; the problem data alone do not imply this, and if the dual objective is unbounded below along a nonnegative direction in the nullspace of $A^\\top$, the sequence can diverge and the theorem's conclusion is unavailable.","fun_headline_variants_meta":{"raw":{"variants":["Dual view tames 0/1 loss with sparse Newton","First dual for indicator functions","L0-regularized dual enables superlinear Newton","Semismooth Newton on sparse dual for 0/1 loss"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000611,"raw_usage":{"total_tokens":2872,"prompt_tokens":1003,"completion_tokens":1869,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":619,"completion_tokens_details":{"reasoning_tokens":1805}},"tokens_in":619,"tokens_out":1869,"duration_ms":16704,"temperature":1.0,"reasoning_tokens":1805,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T05:17:15.484140+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct data with a nonzero $d\\ge 0$ satisfying $A^\\top d=0$ and $\\langle b,d\\rangle>0$, then run SGSN: $F(td)\\to -\\infty$ as $t\\to\\infty$, so no bounded sequence exists and global convergence cannot hold. To test the rate claim instead, run SGSN on an instance satisfying the semismooth and positive-definiteness assumptions and check whether the support $T_k$ eventually equals the true support and whether $\\lVert z^{k+1}-z^*\\rVert/\\lVert z^k-z^*\\rVert\\to 0$; a single instance where $T_k$ keeps changing indefinitely would contradict the support-identification lemma.","supporting_citations":[],"review_version":1}