{"id":"3fdd1d35-eabd-405e-93dd-5bf940f56e05","arxiv_id":"2501.03017","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A ReLU network is convex iff certain non-negative path products hold, and unlike one-hidden-layer networks, two-hidden-layer convex networks can escape the ICNN constraint.","lead":"The paper characterizes exactly when a ReLU neural network computes a convex function, showing that one-hidden-layer networks cannot beat ICNNs, while two-hidden-layer networks can. Convex networks matter for imaging, optimal transport, and inverse problems, where guarantees depend on convexity.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 7.4's sufficiency and Algorithm 1's exactness both depend on Assumption 7.1, which is asserted generic but not proven; when it fails, condition (31) is only necessary and the numerical 'exact check' can falsely report convexity.","rationale":"The reader's weakest-assumption analysis identifies exactly the same load-bearing point: Theorem 7.4's sufficiency and the Section 8 numerical checker both rest on Assumption 7.1, whose genericity is argued informally in §7.3 ('we believe') rather than proven. This is not a manufactured concern: the assumption is stated explicitly, the proof of the sufficiency direction uses it at the step x ∈ Fno-diff ⇒ x ∈ ∪ν Xν, and Algorithm 1's perturbation procedure silently assumes it when reconstructing d−1 face sign-vectors. Therefore the central characterization is correct as a conditional theorem, but the paper's broader claims—'necessary and sufficient conditions for a ReLU neural network to be convex' and an 'exact check'—are not fully supported for arbitrary networks. The two-hidden-layer counterexample (Proposition 2.1) and the one-hidden-layer equivalence (Proposition 4.9) do not depend on this gap, so the main conceptual contribution survives. Since the reader already assigned CONDITIONAL with the same concern, no verdict adjustment is needed.","tokens_in":40863,"tokens_out":2918,"duration_ms":30769,"concrete_test":"Construct a two-hidden-layer, two-neuron-per-layer network in d=2 with collinear first-layer rows, e.g. W1 = [[1,0],[1,0]], b1 = 0, so Hμ1 = Hμ2 = {x1 = 0}; choose W2, w3, and biases by a small parameter search so that every isolated neuron (those with distinct zero sets) satisfies condition (31), while the slope change across the shared frontier x1 = 0 violates the monotonicity condition of Proposition 3.7(iv). Run Algorithm 1 on this network and compare its Boolean output with a direct CPWL convexity check that evaluates all frontier slope increments. If Algorithm 1 returns True while the direct check returns False, the exactness claim fails outside Assumption 7.1.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing pivot is Assumption 7.1 (§7.1). Theorem 7.4's sufficiency direction uses (30) to route every x ∈ Fno-diff through a single isolated neuron ν ∈ Xν, then applies Lemma 6.8. If two or more neurons switch on a d−1 frontier, condition (31) can hold for every isolated neuron while the function is still nonconvex across that frontier: (31) is then only necessary, not sufficient. The paper's genericity discussion (§7.3) invokes transversality/supertransversality and explicitly says 'we believe' a variant of Assumption 7.1 would hold, but no proof is supplied. This gap is not merely aesthetic: Algorithm 1 (Appendix H) does not verify Assumption 7.1 before declaring convexity. Its perturbation step (Algorithm 1, line 6) reconstructs sign-vectors of d−1 faces by taking 1-face sign-vectors (d−1 zeros) and replacing zeros with ±1, which presupposes every d−1 face carries exactly one zero—i.e., exactly condition (30). On a degenerate network satisfying (31) but violating (30), the algorithm can return True for a nonconvex function. Thus the 'exact check' claim in Section 8 is only valid under an unverified assumption.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies convexity of ReLU neural networks and asks whether Input Convex Neural Networks (ICNNs) exhaust the set of convex functions representable by a given ReLU architecture. It provides a minimal characterization of convexity for continuous piecewise linear functions (Proposition 3.7), proves that for one-hidden-layer networks convexity forces the ICNN non-negative-weight condition (Proposition 4.9), and constructs a two-hidden-layer, two-neuron-per-layer network that implements a convex function not representable by any same-width ICNN (Proposition 2.1). For general DAG ReLU networks, the paper gives a necessary condition based on path-lifting (Proposition 6.3) and, under Assumption 7.1, an if-and-only-if characterization (Theorem 7.4). It also presents a numerical procedure, built on Berzins' polyhedral complex extraction, claimed to be an exact convexity check (Section 8 and Algorithm 1).","tokens_in":41080,"tokens_out":4629,"duration_ms":41658,"significance":"If the main characterization holds, the paper makes a substantial contribution: it shows that ICNNs are not the only way to obtain convex ReLU networks, gives a concrete and checkable counterexample, and opens a path toward architecture-aware convexity constraints. The proofs of the one-hidden-layer result and of the necessary conditions are detailed and appear sound, and the use of the path-lifting framework is elegant and well motivated. The counterexample of Proposition 2.1 is convincing and is a useful addition to the expressivity literature. However, the central sufficiency theorem and the claimed exactness of the numerical check rest on Assumption 7.1, whose genericity is only argued heuristically; this limits the strength of the paper's headline claims until the assumption is either proved to be generic or explicitly verified by the algorithm.","major_comments":[{"comment":"The sufficiency direction of Theorem 7.4 depends on Assumption 7.1, specifically on the inclusion Fno-diff ⊆ ∪ν Xν in Eq. (30). The genericity discussion in Section 7.3 says the authors 'believe' a variant of Assumption 7.1 would follow from transversality and supertransversality, but no proof is supplied. When (30) fails, condition (31) is only necessary (Proposition 6.3), not sufficient, so the 'if and only if' statement is not established for all networks. This is load-bearing for the abstract's claim of 'necessary and sufficient conditions' for convex ReLU networks. The authors should either prove a genericity result or explicitly state Theorem 7.4 as conditional on an unverified assumption and moderate the abstract accordingly.","section":"Section 7.1 and 7.3, Theorem 7.4"},{"comment":"Algorithm 1 is presented as an 'exact check' of convexity, but it does not verify Assumption 7.1 before declaring a network convex. The perturbation step in Algorithm 1 line 6 takes sign-vectors of 1-faces, which have d−1 zeros, and replaces zeros with ±1 to obtain sign-vectors of d−1 faces. This presupposes that every d−1 face has exactly one zero, which is precisely condition (30). On a degenerate network satisfying the necessary condition (31) but violating (30), the algorithm can return True for a nonconvex function. The exactness claim in the abstract and Section 8 is therefore valid only under an unverified assumption. The algorithm should either verify Assumption 7.1 (or a substitute) or be described as a necessary-condition check rather than an exact convexity check.","section":"Section 8 and Appendix H, Algorithm 1"},{"comment":"The numerical convexity check is performed on a compact convex domain Ω, and Remark 8.1 asserts that the framework adapts by replacing Xν and F by their intersection with Ω. However, the proof of Theorem 7.4 relies on the global local characterisation Proposition 3.7(v), and no proof is given that checking the conditions only on Ω suffices for convexity on Ω. Since the algorithm is intended to certify convexity on a domain, the domain-restricted sufficiency needs a precise statement and proof; otherwise the experimental conclusions about 'convex ReLU networks' on the sampled domain are not fully justified.","section":"Section 8 and Remark 8.1"}],"minor_comments":[{"comment":"Theorem 7.4 states that the characterization 'holds even with max-pooling neurons', but Remark F.1 says that whether the proof for the ReLU case can be adapted to the max-pooling framework is left to future work. Since Lemma F.4 appears to provide the missing extension, this inconsistency should be resolved in the text.","section":"Section 6.3 and Appendix F, Remark F.1"},{"comment":"The text compares the frequency of convex ReLU networks with the analytic ICNN probability, but the convex counts in Figure 3 include ICNNs. The statement that the frequency is '4 times greater' should be clarified to indicate that this is the ratio of all convex networks to ICNNs, not the ratio of non-ICNN convex networks to ICNNs.","section":"Section 8.1, Equation (35)"},{"comment":"The proof of Proposition 2.1 uses points A, B, and C in Figure G4, but the figure lacks axis labels and the coordinates of these points are not given in the caption; adding them would substantially improve readability of the case analysis.","section":"Appendix G, Figure G4"},{"comment":"The abstract contains a grammatical error: 'The successes of deep learning has led' should be 'The successes of deep learning have led'.","section":"Abstract"},{"comment":"In the pseudocode, the variable lν is used on line 10 but is not defined before; it should be introduced explicitly as the layer index of neuron ν.","section":"Algorithm 1, Appendix H"}],"recommendation":"major_revision","confidential_remarks":"The paper has a strong core: the one-hidden-layer equivalence, the explicit counterexample, and the path-lifting necessary conditions are valuable and mostly rigorous. The main reservation is the unproven genericity of Assumption 7.1 and the resulting overclaim in the abstract and the numerical exactness section. If the authors can prove a genericity statement or honestly reframe the paper as a conditional characterization plus a necessary-condition checker, I would be willing to support publication. The degree of overclaim on the 'exact check' is the issue that most needs addressing before acceptance."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper gives the first exact, checkable characterization of convexity for DAG ReLU networks in the path-lifting framework, and it earns its keep. The one-hidden-layer equivalence (convex ReLU networks are exactly ICNNs up to degeneracy removal) is proven cleanly in Section 4, and the two-hidden-layer counterexample in Proposition 2.1 is genuinely new and carefully verified in Appendix G. The necessary conditions in Proposition 6.3 are elegant and the path-lifting factorization is a natural tool that the authors use well. This is a real step beyond the ICNN universal approximation results, because it addresses expressivity at fixed architecture rather than with depth growing with the number of affine pieces.\n\nThe main soft spot is exactly where the reader put it: Theorem 7.4's sufficiency direction and the numerical checker in Section 8 both rely on Assumption 7.1, which requires every slope-changing frontier point to be a switching point for exactly one neuron. The authors argue in Section 7.3 that a variant of this assumption should hold under transversality/supertransversality, but they explicitly say 'we believe' and do not prove it. That is honest, but it means the headline 'necessary and sufficient conditions' is conditional, not unconditional. The numerical algorithm does not verify Assumption 7.1 before declaring convexity, so the 'exact check' claim is overstated for degenerate networks. This is not a minor cosmetic issue: the stress-test note correctly spells out a concrete failure mode where condition (31) holds for every isolated neuron but the function is nonconvex across a frontier where two neurons switch simultaneously. Since the condition is only necessary in that case, Algorithm 1 can return true for a nonconvex network.\n\nThat said, this is a fixable flaw rather than a fatal one. The necessary conditions and the one-hidden-layer result stand on their own, and the counterexample is robust. The authors should be asked to either prove the genericity claim, make the checker verify Assumption 7.1 (or detect when it fails), or explicitly restrict the exactness claim to networks satisfying the assumption. No code is shipped, which weakens the numerical contribution but does not affect the core theory. The paper is clearly written and the appendix proofs are detailed enough to follow.\n\nThis deserves a serious referee. I would send it out, with the request that the authors tighten the claims around Assumption 7.1 and make the numerical procedure's scope explicit.","headline":"A solid theoretical contribution on convex ReLU networks with a clean one-hidden-layer result and a nice counterexample, but the sufficiency theorem and the 'exact' numerical checker rest on a genericity assumption that is asserted, not proven.","tokens_in":41682,"tokens_out":1496,"would_cite":true,"duration_ms":16708,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68T07","26B25"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper derives necessary and sufficient conditions for a ReLU neural network to implement a convex function, and uses them to show that Input Convex Neural Networks are exactly the convex one-hidden-layer ReLU networks but strictly…","keywords":["convex neural networks","ReLU networks","Input Convex Neural Networks","piecewise linear functions","path-lifting","convexity characterization","DAG architectures","exact convexity check"],"falsifier":"Search small random two-hidden-layer networks while explicitly verifying Assumption 7.1; if any network satisfies $\\min_{x\\in X_\\nu} \\langle a^{\\nu\\to}, \\Phi^{\\nu\\to}\\rangle \\ge 0$ for every hidden neuron $\\nu$ yet has a non-convex restriction along some line segment, Theorem 7.4's sufficiency direction is false. Alternatively, run Algorithm 1 on a network with two neurons switching at the same frontier point and check whether it still reports convexity; if it does, the unverified assumption is doing real work in the test.","tokens_in":40620,"feed_emoji":"🧠","tokens_out":5080,"duration_ms":51706,"temperature":0.7,"pith_summary":"The paper asks whether standard Input Convex Neural Networks, which enforce convexity by clipping hidden-layer weights to non-negative values, cover every convex function a given ReLU architecture can express. For one hidden layer the answer is yes: any convex one-hidden-layer ReLU network can be rewritten as an ICNN of the same width. From two hidden layers onward the answer is no: the paper exhibits a small convex network that no ICNN with the same architecture can implement. The engine is an exact characterization: under a genericity condition, a DAG ReLU network is convex if and only if, for every hidden neuron, a certain inner product of its outgoing path weights and reachable path activations is non-negative. This turns convexity into a finite check and yields an exact numerical test.","feed_headline":"One inequality decides when a ReLU network is convex","feed_subtitle":"New condition shows one-hidden-layer convex nets are ICNNs, but two-layer convex nets escape ICNNs entirely.","key_machinery":"The path-lifting formalism: each path from a neuron $\\nu$ to the output contributes a product of weights, and its activation is the product of neuron activations along the path, so the network output is written as a scalar product between the path-lifting vector and the path-activations matrix. Convexity is then checked at points $X_\\nu$ where only neuron $\\nu$ switches: local monotonicity of the gradient across such a switch is equivalent to $\\langle a^{\\nu\\to}, \\Phi^{\\nu\\to}\\rangle \\ge 0$. This is combined with a minimal characterization of convex continuous piecewise-linear functions, Proposition 3.7, which says convexity only needs to be tested at pairs of points around the frontiers between neighboring affine regions.","core_discovery":"The central discovery is a necessary and sufficient condition for convexity of deep ReLU networks, stated via path-lifting. For a DAG ReLU network whose hidden neurons are isolated and whose slope-changing frontiers involve a single switching neuron, the function $f_\\theta$ is convex if and only if for every hidden neuron $\\nu$ one has $\\min_{x\\in X_\\nu} \\langle a^{\\nu\\to}(x,\\theta), \\Phi^{\\nu\\to}(\\theta)\\rangle \\ge 0$, where $\\Phi^{\\nu\\to}(\\theta)$ collects the products of weights along paths from $\\nu$ to the output and $a^{\\nu\\to}(x,\\theta)$ records which of those paths are active at $x$. The paper also proves that for one hidden layer this condition reduces to non-negativity of the output weights, i.e. to ICNN; for two hidden layers it permits non-ICNN convex networks, exemplified by the explicit function $f_{\\text{EX}}$ that no same-architecture ICNN can implement.","pith_inferences":["If Assumption 7.1 is indeed generic as the authors argue, the same finite inequalities could serve as differentiable penalties during training, turning convexity into a soft constraint that does not require architectural weight clipping.","The path-based inequality may generalize to other structural properties of learned operators, such as monotonicity or Lipschitzness of gradients, by replacing the non-negativity threshold with interval constraints; the paper does not explore these extensions.","The exact check could be made into a certificate for small architectures: since the condition is a finite set of polynomial inequalities in the weights, symbolic verification of convexity is plausible for networks with few neurons.","The gap between ICNNs and general convex ReLU networks suggests that the common practice of enforcing convexity via ICNN architectures is a strong inductive bias, one that may exclude exactly the compact convex functions that wider, deeper unconstrained ReLU networks can interpolate."],"forward_implications":["For one-hidden-layer ReLU networks, the ICNN restriction is not a loss of expressive power: every convex function from such a network can be re-expressed as an ICNN with the same width.","With two hidden layers, ICNNs are strictly less expressive than unconstrained ReLU networks: the paper constructs a convex function realizable by a two-hidden-layer, two-neuron-per-layer network that no ICNN with the same architecture can realize.","For general DAG ReLU networks, under a generic non-degeneracy assumption, convexity is equivalent to finitely many non-negativity constraints on inner products of path-liftings and reachable path-activations.","These constraints give an exact numerical algorithm that checks convexity of moderate-size ReLU networks by extracting their polyhedral complex, rather than by sampling or approximation.","Random Gaussian draws show that convex ReLU networks become increasingly more common than ICNNs as width grows, indicating that ICNN constraints substantially narrow the set of convex functions reachable by a fixed architecture."],"supporting_citations":[{"why":"Defines Input Convex Neural Networks and establishes the weight-non-negativity construction for convexity.","marker":"[17]"},{"why":"Shows ICNNs can approximate any convex function, but with one neuron per layer, motivating the expressivity question for fixed architectures.","marker":"[18]"},{"why":"Provides the path-lifting and path-activation formalism used to express DAG network outputs and the convexity conditions.","marker":"[32]"},{"why":"Supplies the piecewise-convexity framework that Proposition 3.7 refines into minimal finite convexity conditions for CPWL functions.","marker":"[21]"},{"why":"Gives the gradient monotonicity characterization of convexity used in the local necessity proofs.","marker":"[29]"},{"why":"Supplies the polyhedral complex extraction algorithm used in the numerical exact convexity check.","marker":"[36]"},{"why":"Provides the merging of twin neurons and identifiability results used to remove degeneracies in the one-hidden-layer reduction.","marker":"[31]"},{"why":"Gives the polyhedral partition definition used to formalize CPWL functions and compatible partitions.","marker":"[28]"},{"why":"States the composition rules for convex functions that underlie ICNN convexity and the sufficiency arguments.","marker":"[24]"}],"fun_headline_variants":["Convex ReLU nets beyond ICNNs: a sharp characterization","One-hidden-layer convex ReLU nets are ICNNs; two-layer aren't","A single inequality settles convexity of ReLU networks","New condition separates convex ReLU nets from ICNNs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The characterization's sufficiency and the numerical algorithm rely on Assumption 7.1: every hidden neuron is isolated, and at every point where the function's slope changes only one neuron's activation actually switches; the paper argues this is generic but does not prove it, and Algorithm 1 does not verify it before declaring convexity.","fun_headline_variants_meta":{"raw":{"variants":["Convex ReLU nets beyond ICNNs: a sharp characterization","One-hidden-layer convex ReLU nets are ICNNs; two-layer aren't","A single inequality settles convexity of ReLU networks","New condition separates convex ReLU nets from ICNNs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000768,"raw_usage":{"total_tokens":3413,"prompt_tokens":961,"completion_tokens":2452,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":577,"completion_tokens_details":{"reasoning_tokens":2379}},"tokens_in":577,"tokens_out":2452,"duration_ms":18072,"temperature":1.0,"reasoning_tokens":2379,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T21:58:48.910547+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Search small random two-hidden-layer networks while explicitly verifying Assumption 7.1; if any network satisfies $\\min_{x\\in X_\\nu} \\langle a^{\\nu\\to}, \\Phi^{\\nu\\to}\\rangle \\ge 0$ for every hidden neuron $\\nu$ yet has a non-convex restriction along some line segment, Theorem 7.4's sufficiency direction is false. Alternatively, run Algorithm 1 on a network with two neurons switching at the same frontier point and check whether it still reports convexity; if it does, the unverified assumption is doing real work in the test.","supporting_citations":[{"cited_title":"In: ICML (2017)","cited_arxiv_id":null,"evidence_quote":"Defines Input Convex Neural Networks and establishes the weight-non-negativity construction for convexity."},{"cited_title":"In: ICLR (2019)","cited_arxiv_id":null,"evidence_quote":"Shows ICNNs can approximate any convex function, but with one neuron per layer, motivating the expressivity question for fixed architectures."},{"cited_title":"In: ICLR (2023)","cited_arxiv_id":null,"evidence_quote":"Provides the path-lifting and path-activation formalism used to express DAG network outputs and the convexity conditions."},{"cited_title":"ESAIM: Control, Optimisation and Calculus of Variations 22(3), 728–742 (2016)","cited_arxiv_id":null,"evidence_quote":"Supplies the piecewise-convexity framework that Proposition 3.7 refines into minimal finite convexity conditions for CPWL functions."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the gradient monotonicity characterization of convexity used in the local necessity proofs."},{"cited_title":"In: ICML (2023)","cited_arxiv_id":null,"evidence_quote":"Supplies the polyhedral complex extraction algorithm used in the numerical exact convexity check."},{"cited_title":"Constructive Approximation (2022)","cited_arxiv_id":null,"evidence_quote":"Provides the merging of twin neurons and identifiability results used to remove degeneracies in the one-hidden-layer reduction."},{"cited_title":"Optimization 31(3), 209–221 (1994)","cited_arxiv_id":null,"evidence_quote":"Gives the polyhedral partition definition used to formalize CPWL functions and compatible partitions."},{"cited_title":"Cambridge University Press, Cam- bridge (2004)","cited_arxiv_id":null,"evidence_quote":"States the composition rules for convex functions that underlie ICNN convexity and the sufficiency arguments."}],"review_version":1}