{"id":"66065d23-402b-447a-bcda-b6d4e7286956","arxiv_id":"2501.18471","paper_version":1,"verdict":"REJECT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":2,"one_line_summary":"First subgradient propagation rules for convex and concave relaxations of implicit functions, enabling forward-mode AD subgradient evaluation.","lead":"This paper derives rules for computing subgradients, the slope-like objects used in convex optimization, for convex relaxations of implicit functions defined by equations. The rules are meant to plug these relaxations into automatic differentiation libraries for global optimization.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Prop. 5.1's 'any optimal solution' claim is false: with nonunique optimizers the LP (5.12) depends on the chosen optimizer and can return a non-derivative; this invalidates the Section 5 subgradient rules.","rationale":"The reader's REJECT verdict is supported, but the specific objection in the reader's rationale (Proposition 5.2 is false) is not the most load-bearing issue. Proposition 5.2 is easily repaired by using d = 1 only, and it is not needed for Theorem 5.1. The deeper problem is Proposition 5.1's arbitrary-optimizer claim. Section 5's entire architecture, including the LP directional derivative, the cardinal-direction subgradient for np = 2, and the L-derivative LP sequence for np > 2, rests on equation (5.12). If (5.12) can return values above or below the true directional derivative depending on which solver-returned optimizer is used, then the advertised 'AD-compatible subgradients' are not guaranteed to be subgradients. The counterexample is minimal and satisfies the Slater constraint qualification of Assumption 5.2, so this is an internal gap in the argument, not a disagreement with external consensus. The reader's flagged Slater-boundary concern is also real but secondary: the failure here occurs even when Slater's condition holds. Section 4's closed-form results and the numerical illustrations do not offset the flawed foundation of Section 5, and no code was shipped to independently verify the LP rules. I therefore keep the reader's rejection, while locating the weight differently.","tokens_in":6,"tokens_out":12458,"duration_ms":189299,"concrete_test":"Construct the parameterized convex program v(p) = min{x : x \\ge 0, 0 \\le y \\le 1, x + y \\ge p} and apply the recipe of Proposition 5.1 at p = 0 with d = 1, using the two optimal solutions (0,0) and (0,1). The two LP values are 1 and 0, while the true directional derivative is 0; this directly falsifies the 'any optimal solution' assertion in Proposition 5.1 and Remark 5.1.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Proposition 5.1 and Remark 5.1 assert that the directional derivative of x_cv_i(p) can be computed by the LP (5.12) using any optimal solution \\hat{\\xi} of (5.11). This is not supported by Assumption 5.2. Consider the convex program v(p) = min{x : x \\ge 0, 0 \\le y \\le 1, x + y \\ge p}, which satisfies the strong Slater condition and has v(p) = max(0, p - 1) near p = 0. At p = 0 with d = 1, the true directional derivative is 0. The two optimal solutions (0,0) and (0,1) are both minimizers. Applying (5.12) at (0,0) gives min{w_x : w_x \\ge 0, w_y \\ge 0, w_x + w_y \\ge 1} = 1, while at (0,1) it gives 0. Thus the computed value is not independent of the chosen optimal solution. The proof that this 'follows directly from [29]' cannot be correct unless an additional uniqueness condition is imposed, and no such condition appears in Assumption 5.2. Since Proposition 5.1 is the foundation for Propositions 5.2-5.3 and Theorem 5.1, every nx > 1 subgradient rule is exposed to this failure. Separately, Proposition 5.2 is also false for d = -1: for a differentiable convex f at an interior point, f'(p; -1) = -f'(p), which is a subgradient only when f'(p) = 0; for example, f(t) = t^2 at p = 1 gives -2, not a subgradient.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript proposes subgradient computation rules for convex relaxations of implicit functions defined by residual equations (the optimal-value relaxations of Cao and Khan). For a scalar implicit function (nx = 1) with piecewise affine residual relaxations, it derives closed-form subgradients. For vector-valued implicit functions (nx > 1), it presents an LP-based formula for the directional derivative of the convex relaxation and uses this to construct subgradients for np = 1, np = 2, and np > 2 (the last via lexicographic derivatives). The claimed goal is to make implicit function relaxations compatible with forward-mode AD subgradient libraries for global optimization. Numerical proof-of-concept examples in Julia are provided.","tokens_in":14209,"tokens_out":5581,"duration_ms":47278,"significance":"If correct, the nx > 1 subgradient rules would be a valuable contribution, enabling implicit functions to enter standard AD-based subgradient propagation. The scalar case in Section 4 is elegant and appears sound, and the numerical examples illustrate the intended use. However, the central claims for nx > 1 are invalid as stated: the LP formula (5.12) is not independent of the chosen optimal solution of (5.11), and the claimed subgradient rule for np = 1 fails for the direction d = -1 at differentiable points with a nonzero derivative. These errors invalidate Propositions 5.2, 5.3, and Theorem 5.1, which are the core advertised results of the paper. The paper therefore does not currently support its main claims, although the defect is localized to Section 5 and the scalar-section remains a useful contribution.","major_comments":[{"comment":"The assertion that (5.12) computes [x_cv_i]'(\\hat{p}; d) for any optimal solution \\hat{\\xi} of (5.11) is false. Consider the convex program v(p) = min{ x : x >= 0, 0 <= y <= 1, x + y >= p }, which satisfies Assumption 5.2 at \\hat{p} = 0: the Slater condition holds, e.g., at (x,y) = (1, 0.5) for p near 0. The value function is v(p) = max(0, p - 1), so v'(0; 1) = 0. The two points (0,0) and (0,1) are both optimal at p = 0. Applying (5.12) at (0,0) with d = 1 yields min{ w_x : w_x >= 0, w_y >= 0, w_x + w_y >= 1 } = 1, while at (0,1) it yields 0. Thus the value of (5.12) depends on the chosen optimal solution and can be a non-derivative. Since the proof cites only [29, Theorem 3 and Proposition 1] and Assumption 5.2 imposes no uniqueness or tie-breaking condition, the claim 'any optimal solution' cannot be correct as stated. Proposition 5.2, Proposition 5.3, and Theorem 5.1 all rely on Proposition 5.1, so they inherit this failure.","section":"Section 5, Proposition 5.1, Eq. (5.12)"},{"comment":"The claim that for np = 1 the directional derivative in direction d = -1 is a subgradient is false. For a differentiable convex function f at an interior point p with f'(p) != 0, the directional derivative is f'(p; -1) = -f'(p), which is a subgradient only when f'(p) = 0. For example, f(t) = t^2 at p = 1 has f'(1; -1) = -2, while the unique subgradient is 2. Consequently, even if the directional derivative in (5.12) were computed correctly, the advertised np = 1, nx > 1 case does not provide a valid subgradient in general.","section":"Section 5.1, Proposition 5.2"}],"minor_comments":[{"comment":"In the displayed definition of the concave pieces, the final term '... , \\tilde f^{cv,l_i}_i' should presumably read '\\tilde f^{cc,l_i}_i' to match the notation for the concave relaxation.","section":"Section 5, Assumption 5.1"},{"comment":"In the bullet for the concave case, the text writes 'scv := - a^{cc,j} / \\alpha^{cc,j}' and 'scv := - a^{cv,i} / \\alpha^{cv,i}' where 'scc' is clearly intended; this is a notation slip that should be corrected.","section":"Section 4, Proposition 4.1"},{"comment":"The numerical active-constraint tolerance of 1e-7 is a free parameter, but the sensitivity of the resulting subgradients to this tolerance is not discussed; a brief remark on how to choose this tolerance robustly would strengthen the proof-of-concept presentation.","section":"Section 6, Example 6.2"},{"comment":"The proof delegates entirely to [29] without stating which theorem is being invoked or verifying its hypotheses in this setting; given that the result is central and false as stated, the paper should state the precise conditions from [29] and check them explicitly.","section":"Section 5, Proposition 5.1 proof"}],"recommendation":"reject","confidential_remarks":"The manuscript relies heavily on the authors' earlier work [29,36,37], and the Section 5 results are essentially a specialization of [29] to the optimal-value relaxations of [6]. The novelty relative to [29] is not clearly articulated beyond the application setting. The technical flaw in Proposition 5.1 is severe because it is not a matter of missing regularity: the formula (5.12) is demonstrably optimizer-dependent and can return a non-derivative. A revision that adds a uniqueness condition would change the stated claims and the practical 'any optimal solution' appeal, so I do not see a minor fix within the current scope."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First, what's good. The paper attacks a real gap: Cao and Khan's implicit-function relaxations are optimal-value functions, and nobody had working subgradient rules for them. Section 4 is a clean closed-form result for scalar implicit functions with piecewise affine residual relaxations, and the derivation from the max/min representation is convincing. The idea of leveraging Song and Barton's LP sensitivity theory to get directional derivatives of the relaxation is natural and, where it works, it would give a practical AD-compatible subgradient.\n\nThe problem is that the two central claims in the vector case do not hold as stated. Proposition 5.1 says that any optimal solution of (5.11) can be used in the LP (5.12). That is false. Consider the convex program v(p)=min{x : x≥0, 0≤y≤1, x+y≥p}, which satisfies Assumption 5.2 around p=0. The true directional derivative v'(0;1)=0. Both (0,0) and (0,1) are optimal at p=0. The LP (5.12) at (0,0) gives 0, but at (0,1) gives 1. So the computed value depends on the chosen optimizer and is not the directional derivative in general. This kills the 'any optimal solution' remark and undermines everything that rides on Proposition 5.1, i.e. all of Section 5.\n\nProposition 5.2 is also independently false. For a convex function of one variable, the directional derivative in direction -1 is not generally a subgradient. Example: f(t)=t^2 at t=1, f'(1;-1)=-2, which is not a subgradient. So the advertised np=1 case is wrong.\n\nThe rest of Section 5 might be repairable: add a uniqueness or lexicographic selection condition for the optimal solution in (5.11), and either drop the d=-1 claim or use the right subgradient from the L-derivative machinery. But as written, the core of the paper is unsupported. No code was shipped, so the examples don't mitigate the correctness gap. The authors' own prior work is cited appropriately; the failure isn't a citation problem.\n\nThis deserves a serious referee, but the current version should not be accepted. I'd send it back for major revision.","headline":"Useful first subgradient rules for implicit-function relaxations, but the Section 5 LP claims are wrong as stated and need major revision.","tokens_in":14754,"tokens_out":4476,"would_cite":false,"duration_ms":38492,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C26","90C31","49J52","65K05"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper establishes the first LP-based subgradient propagation rules for convex relaxations of implicit functions, making those relaxations compatible with forward-mode automatic differentiation.","keywords":["convex relaxations","implicit functions","subgradients","automatic differentiation","lexicographic derivatives","global optimization","optimal-value functions","linear programming"],"falsifier":"Take a vector-valued implicit function whose defining relaxation (5.11) has two distinct optimal solutions $u_1$ and $u_2$ at the reference parameter while Assumption 5.2 holds; solve the auxiliary LP (5.12) in a fixed direction $d$ using each solution in turn. If the two computed directional derivatives differ, Proposition 5.1's claim that any optimal solution works would be false, and the LP-based subgradient rules built on it would not be reliable.","tokens_in":13599,"feed_emoji":"🧮","tokens_out":11115,"duration_ms":93438,"temperature":0.7,"pith_summary":"The paper aims to make a recent class of convex relaxations of implicit functions usable inside automatic-differentiation-based subgradient propagation for global optimization. It claims that the subgradient of such a relaxation can be computed from the relaxations of the residual function alone, without differentiating through the original implicit equation. The paper establishes closed-form rules for scalar implicit functions and LP-based rules, using directional derivatives or lexicographic derivatives, for vector-valued ones. Since the relaxed value function is convex, the computed lexicographic derivative is a valid subgradient. If correct, this adds implicit functions to the elemental function library used by forward-mode AD subgradient propagation.","feed_headline":"Subgradients for implicit functions now fit into forward-mode AD","feed_subtitle":"New LP-based rules compute valid subgradients, letting implicit functions join AD libraries for global optimization.","key_machinery":"The load-bearing mechanism is the auxiliary linear program (5.12), which converts the nonlinear sensitivity of the optimal-value relaxation into a direction-dependent LP formed from the active inequality constraints and the affine equality constraints at an optimal solution. In the scalar case the mechanism is instead the closed-form reduction $x^{cv}(p)=\\max\\{x_L,h^{cv}(p)\\}$, whose subgradient is the slope of the active affine piece. In higher-dimensional parameter spaces, Theorem 5.1 feeds the directional-derivative LP through the homogenization sequence that defines lexicographic derivatives, directional derivatives taken successively in prescribed directions, and equation (2.5) turns the resulting LD-derivative into an L-derivative, which is a valid subgradient because the relaxation is convex.","core_discovery":"On the paper's own terms, the central claim is that the convex relaxation $x_i^{cv}$ defined in (2.3) as the optimal value of minimizing $\\xi_i$ over the relaxed residual inequalities $f^{cv}(\\xi,p) \\le 0 \\le f^{cc}(\\xi,p)$ can be differentiated in the AD sense using only the relaxations of the residual function. For scalar implicit functions with piecewise affine residual relaxations, the relaxation reduces to $x^{cv}(p)=\\max\\{x_L,h^{cv}(p)\\}$ and a subgradient is read off from whichever piece is active. For vector-valued implicit functions, the paper proves that a directional derivative $[x_i^{cv}]'(p;d)$ can be computed by solving a small LP formed from the active constraints at any optimal solution of the defining program, and that composing these directional derivatives through the L-derivative homogenization sequence yields a valid subgradient because $x_i^{cv}$ is convex. This is the first subgradient propagation rule for these implicit-function relaxations, and it is designed to drop into the existing forward mode for subgradient propagation.","pith_inferences":["A likely consequence is that any convex relaxation expressed as the optimal value of a parameterized convex program with piecewise smooth data could be given AD-compatible subgradients by the same LP-based route, not just the implicit-function relaxations treated here.","Because the paper notes that one new approach is nonlinear in the input direction, reverse-mode integration would probably need to store or recompute the LP solutions rather than run a straightforward adjoint sweep, a practical trade-off the paper does not address.","When the strong Slater condition fails because the relaxed optimizer sits on a variable bound, a pragmatic workaround would be to enlarge the enclosing interval $X$ slightly to restore a strict interior point, accepting a looser relaxation in exchange for a valid subgradient."],"forward_implications":["Implicit functions defined by residual equations enter the elemental function library of forward-mode AD subgradient propagation, so global optimization solvers can build and minimize convex relaxations of models that contain implicit functions.","In the scalar case, when the residual relaxations are piecewise affine, both the relaxation value and a subgradient are obtained in closed form without solving any optimization problem.","For one parameter, the directional derivative in the single available direction is already a subgradient; for two parameters, four cardinal directional derivatives, each from one LP, give a subgradient.","In the high-dimensional parameter case, the L-derivative method requires only a short sequence of LPs, and in practice often just two: the first LP plus an auxiliary LP that tests uniqueness of its optimal solution.","Concave relaxations are covered with no extra machinery, by applying the same rules to $-x_i^{cc}$."],"supporting_citations":[{"why":"Defines the implicit-function relaxation (2.3) as an optimal-value problem; all new subgradient rules apply to these objects.","marker":"[6]"},{"why":"Supplies the generalized-derivative and LP framework for optimal-value functions with embedded convex programs, from which Proposition 5.1 and Theorem 5.1 are specialized.","marker":"[29]"},{"why":"The forward AD subgradient-propagation mode whose elemental function library the new rules are designed to enter.","marker":"[23]"},{"why":"Introduces lexicographic derivatives and the result that L-derivatives of convex functions are valid subgradients, which the paper uses to turn computed LD-derivatives into subgradients.","marker":"[24]"},{"why":"Provides the two-variable construction of a subgradient from four cardinal directional derivatives, specialized in Proposition 5.3.","marker":"[36]"},{"why":"Supplies closed-form AD rules for box-constrained convex optimal-value functions that inspire the scalar implicit-function reformulation in Section 4.","marker":"[37]"}],"fun_headline_variants":["Implicit function subgradients now fit forward AD","First subgradient rules for implicit relaxations","LP-based subgradients extend AD libraries","Subgradients for implicit functions: AD breakthrough","Forward-mode AD gains implicit function subgradients"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The vector-valued subgradient rules all require a strong Slater condition: near the reference parameter the relaxed feasible region must contain a point that satisfies every inequality strictly and all equalities exactly, with the affine equality constraints linearly independent.","fun_headline_variants_meta":{"raw":{"variants":["Implicit function subgradients now fit forward AD","First subgradient rules for implicit relaxations","LP-based subgradients extend AD libraries","Subgradients for implicit functions: AD breakthrough","Forward-mode AD gains implicit function subgradients"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00014,"raw_usage":{"total_tokens":1148,"prompt_tokens":917,"completion_tokens":231,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":533,"completion_tokens_details":{"reasoning_tokens":160}},"tokens_in":533,"tokens_out":231,"duration_ms":2411,"temperature":1.0,"reasoning_tokens":160,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T23:23:16.276279+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a vector-valued implicit function whose defining relaxation (5.11) has two distinct optimal solutions $u_1$ and $u_2$ at the reference parameter while Assumption 5.2 holds; solve the auxiliary LP (5.12) in a fixed direction $d$ using each solution in turn. If the two computed directional derivatives differ, Proposition 5.1's claim that any optimal solution works would be false, and the LP-based subgradient rules built on it would not be reliable.","supporting_citations":[{"cited_title":"Cao and K","cited_arxiv_id":null,"evidence_quote":"Defines the implicit-function relaxation (2.3) as an optimal-value problem; all new subgradient rules apply to these objects."},{"cited_title":"Song and P","cited_arxiv_id":null,"evidence_quote":"Supplies the generalized-derivative and LP framework for optimal-value functions with embedded convex programs, from which Proposition 5.1 and Theorem 5.1 are specialized."},{"cited_title":"Mitsos, B","cited_arxiv_id":null,"evidence_quote":"The forward AD subgradient-propagation mode whose elemental function library the new rules are designed to enter."},{"cited_title":"Nesterov, Lexicographic differentiation of nonsmooth functions , Math","cited_arxiv_id":null,"evidence_quote":"Introduces lexicographic derivatives and the result that L-derivatives of convex functions are valid subgradients, which the paper uses to turn computed LD-derivatives into subgradients."},{"cited_title":"Yuan and K","cited_arxiv_id":null,"evidence_quote":"Provides the two-variable construction of a subgradient from four cardinal directional derivatives, specialized in Proposition 5.3."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies closed-form AD rules for box-constrained convex optimal-value functions that inspire the scalar implicit-function reformulation in Section 4."}],"review_version":1}