{"id":"61412fc7-4ee9-4646-84ee-a78a4e5c15b2","arxiv_id":"2501.03224","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Testing approximate stationarity of piecewise affine functions is NP-hard; an exact Clarke subdifferential sum rule holds under a new polytope compatibility condition; near-approximate stationarity can be certified in oracle-polynomial time.","lead":"This paper proves that checking whether a point is approximately stationary for a piecewise affine function, such as the loss of a ReLU network, is computationally intractable unless P=NP. It also characterizes exactly when the subdifferential sum rule holds for such functions and gives an oracle-based algorithm that can certify near-stationarity in polynomial time.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified; the flagged separation bound is routine and the algorithm's oracle dependence is explicit.","rationale":"The reader correctly located the only genuinely deferred technical step, namely the separation lower bound in Section 5.4 Step 2. However, the bound is a standard consequence of rational arithmetic: the gaps defining delta_sep(w) are absolute values of nonzero rational affine expressions, so they are bounded below by 2^{-O(L)}. Thus the concern is not load-bearing for correctness; it is a presentational gap. The oracle-polynomial framing is explicit and does not overclaim polynomial-time implementation of the exact test. I checked the main hardness reductions and the sum-rule equivalence for internal consistency and found no fatal gaps. Therefore the reader's conditional verdict need not be changed; no new substantive objection is identified.","tokens_in":69423,"tokens_out":32450,"duration_ms":312459,"concrete_test":"Re-derive the separation bound directly from Definition 5.4: for each nested value-function gap at a rational w with bit size L, write the gap as |p/q| with p,q integers of bit size O(L); since a nonzero integer p satisfies |p| >= 1, every positive gap is at least 1/|q| >= 2^{-O(L)}. Taking the minimum over the polynomially many gaps and dividing by 12R reproduces the claimed bound. If this calculation confirms the bound, the conditional concern is resolved.","verdict_should_be":"UNCHANGED","load_bearing_attack":"After close review, I find no load-bearing flaw in the central claims. The hardness reductions in Theorems 3.1 and 3.4 are internally consistent: the seesaw gadgets work, the Gordan-alternative arguments are sound, and the fixed-depth MC and Max-Min representations are polynomial-size. Theorem 4.11's compatibility characterization is carefully proved and the non-transversal example in R4 is consistent with the stated equivalence. The reader's flagged concern, the unproved separation bound 12R*delta_sep(w) >= 2^{-O(L)} in Section 5.4, does not actually threaten Theorem 5.8. By Definition 5.4, delta_sep(w) is the minimum nonzero gap among finitely many rational affine value functions evaluated at a rational point w. Each such gap is a nonzero rational number whose numerator and denominator have bit size O(L), so every positive gap is at least 1/2^{O(L)} = 2^{-O(L)}. Hence the halving loop in Algorithm 1 terminates after O(L) iterations, and the oracle-polynomial claim follows. The NP-hardness of exact stationarity testing is not an inconsistency, because the algorithm is explicitly oracle-polynomial and treats the exact test as a black box. The only legitimate criticism is expositional: the bound is deferred to [78] rather than proved, but it is a routine rational-gap argument.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the computational problem of testing approximate stationarity for continuous piecewise affine (PA) functions. For PA functions given in DC form with constant-depth multi-composite convex components, it proves that checking Fréchet ε-stationarity is strongly co-NP-hard and that checking Clarke ε-stationarity is strongly NP-hard (Theorem 3.1), with complementary completeness results when the depth is part of the input (Theorem 3.2). Analogous hardness and completeness results are proved for the Max-Min representation (Theorems 3.4 and 3.5). The paper then introduces a geometric notion of compatible polytopes and proves that the equality-type Clarke subdifferential sum rule ∂(h−g)(x)=∂h(x)−∂g(x) holds exactly when ∂h(x) and ∂g(x) are compatible (Theorem 4.11); transversality is shown to be a polynomial-time verifiable sufficient condition, and an equivalence is proved for zonotopes (Propositions 4.18 and 4.19). Finally, the paper proposes an oracle-polynomial-time algorithm, the butterfly-net algorithm, for deciding (ε,δ)-near-approximate stationarity for DC-represented PA functions (Algorithm 1 and Theorem 5.8), and applies these results to SVMs, piecewise affine regression, ReLU networks, and penalized deep networks.","tokens_in":69670,"tokens_out":25151,"duration_ms":229168,"significance":"If the results stand, they are substantial. The hardness theorems provide the first strong intractability results for testing a non-minimizing first-order stationarity concept for PA functions, and the completeness results clarify the complexity distinction between Fréchet and Clarke stationarity. Theorem 4.11 gives a new, fully characterized condition for an equality-type Clarke subdifferential sum rule, a question that had previously only received sufficient conditions. The proposed NAS-testing algorithm, despite relying on an idealized exact-stationarity oracle, gives a finite-time stopping framework for the subgradient method on PA functions and resolves a problem mentioned in the literature on ReLU networks. The proofs are detailed and use standard tools (Gordan's theorem, Minkowski-Weyl, polyhedral subdifferential calculus), and the geometric notions are likely to be of independent interest. However, as detailed in the major comments, the proof of the central algorithmic theorem has a load-bearing indexing/stoppage issue, and a key rational-gap bound is deferred rather than proved; these must be repaired before the claims can be accepted as stated.","major_comments":[{"comment":"The stopping condition in Algorithm 1 is inconsistent with the correctness proof. After the body executes with radius 2^{-k}δ, k is incremented, so the test `2^{-k-2}δ ≤ δsep(w)` first fires when the radius used in the last call is at most 8δsep(w) (if the last call had radius δ_t, the test reads δ_t/8 ≤ δsep(w)). The proof of Theorem 5.8, however, repeatedly uses the existence of a last call whose radius satisfies `δsep(w) < 2^{-k}δ ≤ 2δsep(w)` (see the second and third bullets of Step 1). Lemma 5.12 and Corollary 5.14 only give guarantees when the current radius is at most 2δsep(w*) and 2δsep(w), respectively. With the printed condition, the loop can stop at a radius in (4δsep(w), 8δsep(w)], which can exceed both thresholds; for example, if δsep(w)=1 and δsep(w*)=1.5, the loop can stop at a radius in (4,8], while Lemma 5.12 requires a radius at most 3. Thus the proof as written does not rule out false negatives, and the oracle-polynomial-time claim is not established. The stopping rule should be corrected—for instance, with the present indexing, `until 2^{-k}δ ≤ δsep(w)` makes the final radius lie in (δsep(w), 2δsep(w)]—or the proof cases must be reworked.","section":"§5.3.2 (Algorithm 1) and §5.4 (Theorem 5.8, Step 1)"},{"comment":"The bound `12R·δsep(w) ≥ 2^{-O(L)}` is asserted as \"tedious but routine\" and deferred to [78, Lemma 3.1]. This exponential lower bound is load-bearing: it controls the number of halving steps in Algorithm 1 and hence the polynomial runtime in Theorem 5.8. Please include a self-contained proof, or state the cited lemma precisely and verify that the rational linear inequality systems in Definition 5.4 satisfy its hypotheses. A short rational-gap argument should suffice, but it needs to be written down in the manuscript.","section":"§5.4, Step 2"}],"minor_comments":[{"comment":"In the second bullet of the proof, the displayed chain `v(z+th) ≥ (z−th)ᵀ(x''−x)` is invalid because it lower-bounds v at z+th using an expression evaluated at z−th. The intended argument works with `v(z−th)`; please correct this typo.","section":"§4.4, proof of Theorem 4.11, (¬(b) ⇒ ¬(a))"},{"comment":"The last inequality in the definition uses `v_{j_k,...,i_n,j_n}(w) − 4Rδ`, but it should refer to the corresponding value function of g, i.e., `u_{j_k,...,i_n,j_n}(w) − 4Rδ`.","section":"§5.3.1, definition of U^{w,δ,g}_{j_k,...,i_n,j_n}"},{"comment":"The sentence \"we have shown verification of FOM is NP-complete\" conflicts with the stated result that testing FOM is co-NP-complete. Presumably the intended claim is that non-FOM certificates are checkable in polynomial time, so FOM is in co-NP, and the reduction establishes co-NP-hardness. Please rephrase.","section":"§B.2, proof of Corollary 3.7"},{"comment":"Several technical lemmas are stated as \"elementary\" or \"routine\" with proofs omitted (e.g., Lemma 5.11, the convexity argument for P^{w,δ,h,g}, and the lower bound on δsep(w)). Since these underpin the main algorithmic theorem, adding the short proofs in an appendix would improve verifiability.","section":"§5.4, Lemma 5.11 and related lemmas"}],"recommendation":"major_revision","confidential_remarks":"The paper is strong and likely publishable after revision. The main concern is the termination-condition error in Theorem 5.8: it appears to be a fixable typo in the pseudocode, but as printed the proof does not go through. The deferred separation bound should also be supplied. No concerns about novelty or attribution beyond the usual need to check the cited external lemma [78]."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know two things about this paper. First, it is a genuinely substantial contribution to nonsmooth optimization and computational complexity: it shows strong NP-hardness for testing Clarke stationarity of piecewise affine functions in DC form, co-NP-hardness for Fréchet stationarity/local minimality, and analogous results for the Max-Min representation. These are the first hardness results for testing a non-minimizing first-order condition, and they resolve the weak/gap left by Nesterov's 2-PARTITION-based reduction. Second, the paper also delivers a clean necessary and sufficient condition for the exact Clarke subdifferential sum rule for PA functions, via the new geometric notion of polytope compatibility, with transversality as a polynomial-time verifiable sufficient condition that is also necessary for zonotopes. That part is well proved and, as far as I can tell, correct.\n\nThe claims that matter are well supported. The seesaw gadgets in the hardness reductions are sound. The membership proofs for the NP/co-NP completeness results are involved but use standard LP certificate techniques. Theorem 4.11 is carefully argued, and the R4 counterexample showing nontransversality with a valid sum rule is consistent with the statement. The applications to SVM, piecewise affine regression, and ReLU networks are plausible and not just ornamental.\n\nThe soft spots are relatively minor. The termination analysis of the butterfly-net algorithm (Theorem 5.8) rests on a separation bound, 12R·δsep(w) ≥ 2^{-O(L)}, which is asserted as \"tedious but routine\" and deferred to [78]. The reader's report flagged this as a potential gap. I checked the stress-test argument: δsep(w) is the minimum positive gap among finitely many rational affine expressions evaluated at a rational point, so every such gap is at least 2^{-O(L)}. So the bound is indeed routine, and the oracle-polynomial claim stands. The paper would still benefit from including a sketch of this argument rather than citing an external lemma.\n\nSome proofs in Sections 3 and 4 are marked elementary or routine and then deferred to appendices. That is acceptable for a paper of this length, but a referee should ask for enough details in the appendix to make verification possible without tracking down the cited references. The oracle assumption for exact stationarity testing is explicit and not a flaw; it is a clean way to separate the hardness of exact testing from the value of the rounding procedure.\n\nWho should read this? People working on subgradient method termination, stationarity testing in nonsmooth optimization, and complexity of continuous optimization. It is a long paper, but the main results and proofs are worth careful attention. I would send it to serious peer review. With minor revisions to fill in the deferred separation bound and tighten a few proof sketches, it should be publishable at a strong journal.","headline":"Strong paper: the hardness results and sum rule characterization hold up, and the only flagged issue is a routine omitted bound rather than a real gap.","tokens_in":70168,"tokens_out":1650,"would_cite":true,"duration_ms":21031,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C26","49J52","68Q17","90C60"],"pacs":[],"model":"deepseek-v4-flash","headline":"Testing approximate stationarity for piecewise affine functions is strongly NP-hard unless P=NP, and the exact subdifferential sum rule holds precisely when two polytopes are compatible.","keywords":["piecewise affine functions","approximate stationarity","Clarke subdifferential","Fréchet subdifferential","subdifferential sum rule","NP-hardness","nonsmooth optimization","finite-time stopping rule"],"falsifier":"To refute the oracle-polynomial-time claim, one could search for rational multi-composite inputs with bit length $L$ where the true minimum nonzero gap between distinct affine pieces is smaller than $2^{-cL}$ for every fixed $c$; if such inputs exist, Algorithm 1's halving loop cannot terminate in polynomial time. Alternatively, a pair of polytopes satisfying the compatibility definition but violating $\\partial(h-g)(x)=\\partial h(x)-\\partial g(x)$ would refute the characterization.","tokens_in":69226,"feed_emoji":"🧩","tokens_out":14705,"duration_ms":126507,"temperature":0.7,"pith_summary":"Piecewise affine functions—continuous functions assembled from finitely many linear pieces—underlie many nonsmooth machine-learning and statistical objectives, but deciding whether a point is approximately stationary is not a routine calculus step. This paper shows that for such functions written as the difference of two convex piecewise affine functions, testing approximate Fréchet stationarity (which for these functions means local minimality) is strongly co-NP-hard, and testing approximate Clarke stationarity is strongly NP-hard, at any fixed representation depth of at least two; the max-min representation is hard in the same way. Because the cheap substitute test $0\\in\\partial h(x)-\\partial g(x)$ is polynomial-time solvable but can certify a false point, the paper gives the first necessary and sufficient condition for that substitute to be exact: the equality $\\partial(h-g)(x)=\\partial h(x)-\\partial g(x)$ holds if and only if the two subdifferential polytopes are compatible. It then builds an algorithm that, given an exact stationarity oracle, certifies or refutes $(\\varepsilon,\\delta)$-near-approximate stationarity in oracle-polynomial time, yielding a finite-time stopping rule for subgradient-type methods on piecewise affine objectives.","feed_headline":"Approximate stationarity tests for piecewise affine are NP-hard","feed_subtitle":"Subdifferential sum rule holds exactly iff two polytopes are compatible — enabling finite-time stopping.","key_machinery":"The load-bearing machinery is the pair of convex polytopes $A=\\partial h(x)$ and $B=\\partial g(x)$ attached to a DC representation $f=h-g$ of a piecewise affine function. The defining identity is the exact Clarke subdifferential sum rule, $\\partial(h-g)(x)=A-B$, and the paper's characterization says this identity holds exactly when $A$ and $B$ are compatible: for every $a\\in A$, $b\\in B$ with $a-b$ extreme in $A-B$, the sum $a+b$ is extreme in $A+B$. This compatibility condition is what separates tractable stationarity tests (via the sum-rule relaxation $0\\in A-B$, a convex quadratic program) from intractable ones. For algorithm design, the key mechanism is the butterfly net: a family of convex polyhedra $P_{\\delta}$ around the query point whose projection, when the unknown stationary point is within the net, reproduces exactly the same active pieces and hence the same subdifferential as the target point; termination relies on the separation constant $\\delta_{\\mathrm{sep}}(w)$, the smallest nonzero gap between distinct affine pieces scaled by the Lipschitz radius $R$.","core_discovery":"The paper's central claim is that the computational difficulty of stationarity testing for piecewise affine functions is governed by a geometric property of two polytopes. For a piecewise affine function written as $f=h-g$ with convex piecewise affine $h,g$, the paper proves that deciding $0\\in\\hat{\\partial}(h-g)(0)+\\varepsilon B$ (Fréchet stationarity, equivalent to $0$ being a local minimum) is strongly co-NP-hard, and deciding $0\\in\\partial(h-g)(0)+\\varepsilon B$ (Clarke stationarity) is strongly NP-hard, whenever $h$ and $g$ are given in fixed-depth multi-composite form with integer data; the analogous statements hold for the max-min representation. The source of hardness is the failure of the exact subdifferential sum rule, and the paper pins that failure down completely: $\\partial(h-g)(x)=\\partial h(x)-\\partial g(x)$ holds if and only if the polytopes $\\partial h(x)$ and $\\partial g(x)$ are compatible, i.e., whenever $a-b$ is an extreme point of $\\partial h(x)-\\partial g(x)$, the sum $a+b$ must be an extreme point of $\\partial h(x)+\\partial g(x)$. A polynomial-time-checkable sufficient condition called transversality, meaning the parallel subspaces of the two polytopes meet only at the origin, is also necessary when the two polytopes are zonotopes, covering many neural-network losses. On the algorithmic side, the 'butterfly net' algorithm reacts to the hardness by working with an exact stationarity oracle: it repeatedly projects the query point onto a family of polyhedral nets around unknown stationary points, halving the net size until it either produces a certificate of $(\\varepsilon,\\delta)$-near-approximate stationarity or certifies absence at distance at least $\\min\\{\\delta,\\delta_{\\mathrm{sep}}(w^*)\\}$.","pith_inferences":["The compatibility characterization suggests that exact subdifferential calculus for DC decompositions is not governed by smoothness or separability but by extreme-point geometry of the two subdifferentials; if this extends beyond piecewise affine functions, the tractability boundary for stationarity testing may be similarly geometric.","Because the hardness is strong, any practical polynomial-time stationarity test for ReLU-type networks must either accept a coarser stationarity notion (such as DC-criticality or Goldstein stationarity) or impose a condition like transversality; the paper's corollaries make this trade-off explicit.","A testable extension would be to run the butterfly-net algorithm with a heuristic oracle that checks only DC-criticality and measure empirically how often the certified point is actually Clarke stationary on benchmark problems; the completeness results predict the two notions will diverge frequently.","Whether the hardness persists in fixed dimension remains open; if it does not, dimension-dependent algorithms for stationarity testing of piecewise affine functions are conceivable."],"forward_implications":["For any fixed MC depth $n\\ge 2$, there is no pseudo-polynomial or polynomial algorithm for approximate Fréchet or Clarke stationarity testing of piecewise affine functions unless P=NP; the strong hardness rules out algorithms whose running time depends polynomially on the numeric values.","The equality-type subdifferential sum rule for $h-g$ is exactly characterized by compatibility of the subdifferential polytopes, so an efficient stationarity test via $0\\in\\partial h(x)-\\partial g(x)$ is correct precisely under that geometric condition.","Transversality of the two polytopes is polynomial-time verifiable and sufficient for the sum rule; for zonotope subdifferentials—covering many SVM and ReLU-network losses—it is also necessary, giving a clean test for when the standard subdifferential formula applies.","The butterfly-net algorithm provides a finite-time stopping rule for the subgradient method on piecewise affine objectives, converting purely asymptotic convergence statements into a certification procedure with an explicit certificate point.","Determining whether a DC-critical point is Clarke stationary is NP-hard, so the distinction between these two solution concepts is computationally intractable even though verifying DC-criticality itself is easy."],"supporting_citations":[{"why":"Source of the strongly NP-hard PAR{−1,0,1}MAX1 problem, from which the DC-representation hardness reductions are built.","marker":"[6, Theorem 12]"},{"why":"Source of 3SAT, the basis of the Max-Min representation hardness reductions.","marker":"[23, Section 3.1.1]"},{"why":"Defines the Clarke subdifferential, the fuzzy sum rule, and Clarke regularity used throughout the paper.","marker":"[11, Proposition 2.3.3]"},{"why":"Supplies the convex-analysis facts on support functions, extreme points, and separation used in the polytope arguments.","marker":"[65]"},{"why":"Earlier co-NP-hardness for local minima of polynomials; the paper's PA result extends this to degree one and to strong hardness.","marker":"[55, Theorem 2]"},{"why":"Previous weak co-NP-hardness for local minimizers of PA functions, which the present paper strengthens and makes DC-representable.","marker":"[58]"},{"why":"Provides variational analysis tools, including normal-cone calculus and the perturbation principle used in the sum-rule arguments.","marker":"[68, Exercise 8.8(c)]"},{"why":"Supplies the essentially active index-set characterization of the Clarke subdifferential of piecewise affine functions.","marker":"[69, Proposition 4.3.1]"},{"why":"The deferred separation bound $12R\\delta_{\\mathrm{sep}}(w)\\ge 2^{-O(L)}$ on which the butterfly-net termination proof relies.","marker":"[78, Lemma 3.1]"},{"why":"Two-layer ReLU network stationarity testing; the paper's finite-time stopping rule answers its open robust-testing question.","marker":"[80, Section 5]"}],"fun_headline_variants":["Testing approximate stationarity for piecewise affine functions is NP-hard","Approximate stationarity for piecewise affine is computationally intractable","Piecewise affine stationarity testing is NP-hard and co-NP-hard","Subdifferential sum rule holds iff polytopes are compatible","Polytope compatibility enables finite-time near-stationarity detection"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The polynomial-time guarantee of the butterfly-net algorithm rests on a bound it does not prove: that the smallest nonzero gap between the values of two distinct linear pieces of a rational multi-composite input is at least exponentially small in the bit length of the input. If that bound is false, the halving loop that drives the algorithm can run for exponentially many steps, so the claimed oracle-polynomial-time termination fails; the paper also assumes an idealized oracle that can decide exact $\\varepsilon$-stationarity.","fun_headline_variants_meta":{"raw":{"variants":["Testing approximate stationarity for piecewise affine functions is NP-hard","Approximate stationarity for piecewise affine is computationally intractable","Piecewise affine stationarity testing is NP-hard and co-NP-hard","Subdifferential sum rule holds iff polytopes are compatible","Polytope compatibility enables finite-time near-stationarity detection"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000406,"raw_usage":{"total_tokens":2229,"prompt_tokens":1179,"completion_tokens":1050,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":795,"completion_tokens_details":{"reasoning_tokens":962}},"tokens_in":795,"tokens_out":1050,"duration_ms":10412,"temperature":1.0,"reasoning_tokens":962,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T21:53:35.730014+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"To refute the oracle-polynomial-time claim, one could search for rational multi-composite inputs with bit length $L$ where the true minimum nonzero gap between distinct affine pieces is smaller than $2^{-cL}$ for every fixed $c$; if such inputs exist, Algorithm 1's halving loop cannot terminate in polynomial time. Alternatively, a pair of polytopes satisfying the compatibility definition but violating $\\partial(h-g)(x)=\\partial h(x)-\\partial g(x)$ would refute the characterization.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the convex-analysis facts on support functions, extreme points, and separation used in the polytope arguments."},{"cited_title":"Nesterov","cited_arxiv_id":null,"evidence_quote":"Previous weak co-NP-hardness for local minimizers of PA functions, which the present paper strengthens and makes DC-representable."}],"review_version":1}