Pith. sign in

REVIEW 2 major objections 4 minor 85 references

Testing Approximate Stationarity Concepts for Piecewise Affine Functions

T0 review · 2 major / 4 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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.

desk verdict 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. read the letter →

arxiv 2501.03224 v1 pith:7LEEZLDV submitted 2025-01-06 math.OC

Lai Tian , Anthony Man-Cho So This is my paper · ORCID
classification math.OC MSC 90C2649J5268Q1790C60
keywords piecewiseaffinefunctionsapproximatestationarityClarkesubdifferentialFréchetsumruleNP-hardnessnonsmoothoptimizationfinite-timestopping
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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$.

What would settle it

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.

Watch

Extended reading notes

Core claim

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^*)\}$.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

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.

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 (2)
  1. [§5.3.2 (Algorithm 1) and §5.4 (Theorem 5.8, Step 1)] 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.
  2. [§5.4, Step 2] 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.
minor comments (4)
  1. [§4.4, proof of Theorem 4.11, (¬(b) ⇒ ¬(a))] 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.
  2. [§5.3.1, definition of U^{w,δ,g}_{j_k,...,i_n,j_n}] 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δ`.
  3. [§B.2, proof of Corollary 3.7] 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.
  4. [§5.4, Lemma 5.11 and related lemmas] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: every load-bearing claim is proved from external hardness sources or standard nonsmooth-analysis facts, and the only deferred bound is a routine rational-gap estimate rather than a self-referential input.

full rationale

The derivation chain is self-contained and does not reduce to its own inputs. The hardness results in Theorems 3.1 and 3.4 are obtained by explicit polynomial-time reductions from the externally established strongly NP-hard problems PAR{−1,0,1}MAX1 and 3SAT to Problems 3.10, 3.11, 3.16, and 3.17; the proofs in Lemmas 3.12, 3.13, 3.18, and 3.19 construct the relevant PA functions directly and verify both directions by elementary inequalities and Gordan's theorem. No step assumes the claimed hardness conclusion. The membership proofs in Theorems 3.2 and 3.5 are also constructive, using explicit certificates based on essentially active indices and polynomial-time LP verifications, so completeness is not imported from the hardness results. The sum-rule characterization in Theorem 4.11 is not circular: compatibility is defined purely geometrically in Definition 4.6 in terms of extreme points of Minkowski sums, and the proof derives the equivalence between compatibility and the subdifferential equality using Lemma 2.18, Gordan's theorem, and standard Clarke calculus; the same holds for the transversality and zonotope results in Propositions 4.18 and 4.19, whose proofs are given in detail. The paper's new notions are not renamings of the target conclusions, as evidenced by the nontrivial R^4 example showing compatibility without transversality. The oracle-polynomial algorithm in Theorem 5.8 explicitly assumes a stationarity-testing oracle as a black box; this is an idealized assumption stated up front, not a fitted parameter renamed as a prediction. The only external deferral is the separation bound in Section 5.4: the paper says 'It is tedious but routine to show that 12R · δsep(w) ≥ 2^{−O(L)}; see, e.g., [78, Lemma 3.1].' This is a missing proof of a routine lower bound on nonzero gaps among finitely many rational affine value functions at a rational point, and it does not replay any of the paper's own claims. No load-bearing self-citation was found: the cited facts are standard results in polyhedral geometry, Clarke calculus, and LP theory, not prior works by the same authors asserting the paper's own conclusions. Accordingly, the circularity score is 0.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The central claims rest on standard convex analysis and complexity results. No free parameters are fitted to data: the paper is fully theoretical. The only nonstandard premise is the availability of an exact stationarity-testing oracle for the robust algorithm, which is explicitly assumed and is NP-hard to realize in general.

assumptions (6)
  • standard math Every PA function admits a DC representation h-g with convex PA h,g (Fact 2.9).
    Used throughout; standard result from [51,43] and [69].
  • standard math Clarke subdifferential fuzzy sum rule: ∂(f1+f2)(x) ⊆ ∂f1(x)+∂f2(x) for locally Lipschitz f1,f2 (Fact 1.3).
    Basis for the SRR relaxation and for inclusion directions in sum rule proofs.
  • standard math Gordan's theorem (Lemma 2.17).
    Used to prove existence of separating vectors in compatibility and zonotope proofs.
  • standard math Minkowski-Weyl and extreme point structure of Minkowski sums (Lemma 2.18).
    Core tool for relating ext(A-B) and ext(A+B) to subdifferentials.
  • standard math Strong NP-hardness of PAR{-1,0,1}MAX1 (Problem 3.9) and 3SAT.
    Base problems for the hardness reductions; standard complexity results.
  • domain assumption Existence of an exact ε-stationarity testing oracle (Definition 5.1).
    The robust testing algorithm's oracle-polynomial complexity is conditional on this oracle, which is NP-hard to realize in general.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Testing Approximate Stationarity Concepts for Piecewise Affine Functions." pith.science (2026). https://pith.science/paper/7LEEZLDV

@misc{pith2026250103224,
  author       = {Pith},
  title        = {Pith review of: Testing Approximate Stationarity Concepts for Piecewise Affine Functions},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/7LEEZLDV}},
  note         = {Machine review of arXiv:2501.03224}
}
abstract

We study the basic computational problem of detecting approximate stationary points for continuous piecewise affine (PA) functions. Our contributions span multiple aspects, including complexity, regularity, and algorithms. Specifically, we show that testing first-order approximate stationarity concepts, as defined by commonly used generalized subdifferentials, is computationally intractable unless P=NP. To facilitate computability, we consider a polynomial-time solvable relaxation by abusing the convex subdifferential sum rule and establish a tight characterization of its exactness. Furthermore, addressing an open issue motivated by the need to terminate the subgradient method in finite time, we introduce the first oracle-polynomial-time algorithm to detect so-called near-approximate stationary points for PA functions. A notable byproduct of our development in regularity is the first necessary and sufficient condition for the validity of an equality-type (Clarke) subdifferential sum rule. Our techniques revolve around two new geometric notions for convex polytopes and may be of independent interest in nonsmooth analysis. Moreover, some corollaries of our work on complexity and algorithms for stationarity testing address open questions in the literature. To demonstrate the versatility of our results, we complement our findings with applications to a series of structured piecewise smooth functions, including $\rho$-margin-loss SVM, piecewise affine regression, and nonsmooth neural networks.

Figures

Figures reproduced from arXiv: 2501.03224 by the authors.

Figure 1
Figure 1. Interrelations of various conditions validating the exact sum rule for PA functions. [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗
Figure 2
Figure 2. Illustration of various stationarities (better viewed in color); see Example [PITH_FULL_IMAGE:figures/full_fig_p017_2.png] view at source ↗
Figure 3
Figure 3. Illustration the proof of Theorem 3.2(b). The existence of the short certificate p ∈ Qd will certify, by continuity, polyhedrality, and positive homogeneity, for any p ′ near p and t > 0, that (h−g)(tp ′ ) = (h−g) ′ (0;tp ′ ) = max gh∈ext ∂h(0) (tp ′ ) ⊤gh− max gg∈ext ∂g(0) (tp ′ ) ⊤gg = (g ∗ h−g ∗ g ) ⊤(tp ′ ) = g ⊤ I1 (tp ′ ), confirming I1 ∈ Ie h−g (0). To find such a certificate, by the first-order optimality co… view at source ↗
Figures from the paper (3 more)
Figure 4
Figure 4. Figure 4: Incompatible polytopes in Example 4.9. Example 4.9 (Incompatible polytopes in R 2 ). Let vectors x1 := 0, x2 := (−1, −1), x3 := (1, −1), y1 := 0, and y2 := (0, −1/2) in R 2 be given. Consider polytopes X := conv{xi : i ∈ {1, 2, 3}}, Y := [y1, y2]. Let a := x1 and b := …
Figure 5
Figure 5. Figure 5: Illustration of zonotopes in R 3 . Proposition 4.19 (Zonotopes; compatibility implies transversality). Given two convex PA func￾tions h, g : R d → R and a point x ∈ R d , suppose that the polytopes ∂h(x) and ∂g(x) are zonotopes. Then, the functions h and g are transver…
Figure 6
Figure 6. Figure 6: Illustration of sets in Remark 5.6. By definition, we have w ∈/ R d\(t − 2δ)B, so that w ∈/ Sε + min{δ, δ∗}B as desired. Remark 5.7. We emphasize that the positive radius min{δ, δsep(w∗ )} is independent of the point w. Such independence is crucial for terminating an a…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

85 extracted references · 76 canonical work pages

  1. [78]

    S. J. Wright. Primal-Dual Interior-Point Methods . SIAM, 1997

    1997

  2. [1]

    A. A. Ahmadi and J. Zhang. Complexity aspects of local minima and related notions. Advances in Mathematics , 397:108119, 2022

    2022

  3. [2]

    A. A. Ahmadi and J. Zhang. On the complexity of finding a local minimizer of a quadratic function over a polytope. Mathematical Programming, 195(1-2):783–792, 2022

    2022

  4. [3]

    Arora, A

    R. Arora, A. Basu, P. Mianjy, and A. Mukherjee. Understanding deep neural networks with rectified linear units. In International Conference on Learning Representations , 2018

    2018

  5. [4]

    Bena ¨ ım, J

    M. Bena ¨ ım, J. Hofbauer, and S. Sorin. Stochastic approximations and differential inclusions. SIAM Journal on Control and Optimization , 44(1):328–348, 2005

    2005

  6. [5]

    Bertsimas and J

    D. Bertsimas and J. N. Tsitsiklis. Introduction to Linear Optimization , volume 6. Athena Scientific Belmont, MA, 1997

    1997

  7. [6]

    H. L. Bodlaender, P. Gritzmann, V. Klee, and J. Van Leeuwen. Computational complexity of norm-maximization. Combinatorica, 10:203–225, 1990

    work page 1990

  8. [7]

    Bolte, R

    J. Bolte, R. Boustany, E. Pauwels, and B. Pesquet-Popescu. On the complexity of nonsmooth automatic differentiation. In International Conference on Learning Representations , 2022

    work page 2022

Show all 85 references
  1. [8]

    J. P. Brooks. Support vector machines with the ramp loss and the hard margin loss. Operations Research, 59(2):467–479, 2011

    2011

  2. [9]

    J. V. Burke and A. Engle. Strong metric (sub) regularity of Karush–Kuhn–Tucker mappings for piecewise linear-quadratic convex-composite optimization and the quadratic convergence of Newton’s method. Mathematics of Operations Research, 45(3):1164–1192, 2020

    2020

  3. [10]

    F. H. Clarke. Generalized gradients and applications. Transactions of the American Mathe- matical Society, 205:247–262, 1975

    1975

  4. [11]

    F. H. Clarke. Optimization and Nonsmooth Analysis . SIAM, 1990

    1990

  5. [12]

    Cui and J.-S

    Y. Cui and J.-S. Pang. Modern Nonconvex Nondifferentiable Optimization . SIAM, 2021

    2021

  6. [13]

    Cui, J.-S

    Y. Cui, J.-S. Pang, and B. Sen. Composite difference-max programs for modern statistical estimation problems. SIAM Journal on Optimization , 28(4):3344–3374, 2018

    2018

  7. [14]

    Y. Cui, Z. He, and J.-S. Pang. Multicomposite nonconvex optimization for training deep neural networks. SIAM Journal on Optimization , 30(2):1693–1723, 2020

    2020

  8. [15]

    Davis and D

    D. Davis and D. Drusvyatskiy. Stochastic model-based minimization of weakly convex func- tions. SIAM Journal on Optimization , 29(1):207–239, 2019

    2019

  9. [16]

    Davis, D

    D. Davis, D. Drusvyatskiy, S. Kakade, and J. D. Lee. Stochastic subgradient method converges on tame functions. Foundations of Computational Mathematics , 20(1):119–154, 2020

    2020

  10. [17]

    Davis, D

    D. Davis, D. Drusvyatskiy, Y. T. Lee, S. Padmanabhan, and G. Ye. A gradient sampling method with complexity guarantees for Lipschitz functions in high and low dimensions. In Advances in Neural Information Processing Systems , 2022. 72

    2022

  11. [18]

    de Oliveira

    W. de Oliveira. The ABC of DC programming. Set-Valued and Variational Analysis , 28: 679–706, 2020

    2020

  12. [19]

    Edmonds, W

    J. Edmonds, W. Pulleyblank, and L. Lov´ asz. Brick decompositions and the matching rank of graphs. Combinatorica, 2:247–274, 1982

    1982

  13. [20]

    Fearnley, P

    J. Fearnley, P. Goldberg, A. Hollender, and R. Savani. The complexity of gradient descent: CLS = PPAD ∩ PLS. Journal of the ACM , 70(1):1–74, 2022

    2022

  14. [21]

    K. Fukuda. From the zonotope construction to the Minkowski addition of convex polytopes. Journal of Symbolic Computation , 38(4):1261–1272, 2004

    2004

  15. [22]

    M. R. Garey and D. S. Johnson. “Strong” NP-completeness results: Motivation, examples, and implications. Journal of the ACM , 25(3):499–508, 1978

    1978

  16. [23]

    M. R. Garey and D. S. Johnson. Computers and Intractability , volume 174. 1979

    1979

  17. [24]

    Goodfellow, D

    I. Goodfellow, D. Warde-Farley, M. Mirza, A. Courville, and Y. Bengio. Maxout networks. In International Conference on Machine Learning , pages 1319–1327. PMLR, 2013

    2013

  18. [25]

    Griewank

    A. Griewank. On stable piecewise linearization and generalized algorithmic differentiation. Optimization Methods and Software , 28(6):1139–1178, 2013

    2013

  19. [26]

    Griewank and A

    A. Griewank and A. Walther. Evaluating Derivatives: Principles and Techniques of Algorith- mic Differentiation. SIAM, 2008

    2008

  20. [27]

    Griewank and A

    A. Griewank and A. Walther. First-and second-order optimality conditions for piecewise smooth objective functions. Optimization Methods and Software , 31(5):904–930, 2016

    2016

  21. [28]

    Griewank and A

    A. Griewank and A. Walther. Relaxing kink qualifications and proving convergence rates in piecewise smooth optimization. SIAM Journal on Optimization , 29(1):262–289, 2019

    2019

  22. [29]

    Gritzmann and B

    P. Gritzmann and B. Sturmfels. Minkowski addition of polytopes: Computational complexity and applications to Gr¨ obner bases. SIAM Journal on Discrete Mathematics , 6(2):246–269, 1993

    1993

  23. [30]

    Gr¨ otschel, L

    M. Gr¨ otschel, L. Lov´ asz, and A. Schrijver. Geometric Algorithms and Combinatorial Opti- mization, volume 2. Springer Science & Business Media, 2012

    2012

  24. [31]

    Gr¨ unbaum.Convex Polytopes, volume 221

    B. Gr¨ unbaum.Convex Polytopes, volume 221. Springer Science & Business Media, 2003

    2003

  25. [32]

    G¨ uler and Y

    O. G¨ uler and Y. Ye. Convergence behavior of interior-point algorithms. Mathematical Pro- gramming, 60(1):215–228, 1993

    1993

  26. [33]

    G. Hahn, M. Banerjee, and B. Sen. Parameter estimation and inference in a continuous piecewise linear regression model. Manuscript, Department of Statistics, Columbia University , 32(2):407–451, 2017

    2017

  27. [34]

    W. L. Hare and A. S. Lewis. Identifying active constraints via partial smoothness and prox- regularity. Journal of Convex Analysis , 11(2):251–266, 2004. 73

    2004

  28. [35]

    Hiriart-Urruty and C

    J.-B. Hiriart-Urruty and C. Lemar´ echal. Fundamentals of Convex Analysis . Springer Science & Business Media, 2004

    2004

  29. [36]

    Hollender and E

    A. Hollender and E. Zampetakis. The computational complexity of finding stationary points in non-convex optimization. In The Thirty Sixth Annual Conference on Learning Theory , pages 5571–5572. PMLR, 2023

    2023

  30. [37]

    Huang, L

    X. Huang, L. Shi, and J. A. Suykens. Ramp loss linear programming support vector machine. Journal of Machine Learning Research , 15(1):2185–2211, 2014

    2014

  31. [38]

    C. Jones. Polyhedral tools for control. PhD Thesis, University of Cambridge , 2005

    2005

  32. [39]

    Jordan, G

    M. Jordan, G. Kornowski, T. Lin, O. Shamir, and M. Zampetakis. Deterministic nonsmooth nonconvex optimization. In The Thirty Sixth Annual Conference on Learning Theory , pages 4570–4597. PMLR, 2023

    2023

  33. [40]

    Kong and A

    S. Kong and A. S. Lewis. The cost of nonconvexity in deterministic nonsmooth optimization. Mathematics of Operations Research, 2023

    2023

  34. [41]

    Kornowski and O

    G. Kornowski and O. Shamir. Oracle complexity in nonsmooth nonconvex optimization. Jour- nal of Machine Learning Research , 23(314):1–44, 2022

    2022

  35. [42]

    M. K. Kozlov, S. P. Tarasov, and L. G. Khachiyan. The polynomial solvability of convex quadratic programming. USSR Computational Mathematics and Mathematical Physics , 20(5): 223–228, 1980

    1980

  36. [43]

    Kripfganz and R

    A. Kripfganz and R. Schulze. Piecewise affine functions as a difference of two convex functions. Optimization, 18(1):23–29, 1987

    1987

  37. [44]

    H. A. Le Thi and T. Pham Dinh. DC programming and DCA: Thirty years of developments. Mathematical Programming, 169(1):5–68, 2018

    2018

  38. [45]

    A. S. Lewis and S. J. Wright. Identifying activity. SIAM Journal on Optimization , 21(2): 597–614, 2011

    2011

  39. [46]

    J. Li, A. M.-C. So, and W.-K. Ma. Understanding notions of stationarity in nonsmooth optimization: A guided tour of various constructions of subdifferential for nonsmooth functions. IEEE Signal Processing Magazine , 37(5):18–31, 2020

    2020

  40. [47]

    W. Liu, X. Liu, and X. Chen. An inexact augmented lagrangian algorithm for training leaky ReLU neural network with group sparsity. Journal of Machine Learning Research , 24(212): 1–43, 2023

    2023

  41. [48]

    Majewski, B

    S. Majewski, B. Miasojedow, and E. Moulines. Analysis of nonsmooth stochastic approxima- tion: The differential inclusion approach. arXiv preprint arXiv:1805.01916 , 2018

    2018 arXiv

  42. [49]

    Mazumder, A

    R. Mazumder, A. Choudhury, G. Iyengar, and B. Sen. A computational framework for mul- tivariate convex regression and its variants. Journal of the American Statistical Association , 114(525):318–331, 2019. 74

    2019

  43. [50]

    Mehrotra and Y

    S. Mehrotra and Y. Ye. Finding an interior point in the optimal face of linear programs. Mathematical Programming, 62(1):497–515, 1993

    1993

  44. [51]

    D. Melzer. On the expressibility of piecewise-linear continuous functions as the difference of two piecewise-linear convex functions. Mathematical Programming Studies, 29:118–134, 1986

    1986

  45. [52]

    Mohri, A

    M. Mohri, A. Rostamizadeh, and A. Talwalkar. Foundations of Machine Learning. MIT press, 2018

    2018

  46. [53]

    B. S. Mordukhovich. Variational Analysis and Applications . Springer, 2018

    2018

  47. [54]

    B. S. Mordukhovich and Y. Shao. Nonsmooth sequential analysis in Asplund spaces. Trans- actions of the American Mathematical Society , 348(4):1235–1280, 1996

    1996

  48. [55]

    K. G. Murty and S. N. Kabadi. Some NP-complete problems in quadratic and nonlinear programming. Mathematical Programming, 39(2):117–129, 1987

    1987

  49. [56]

    Nemirovski and D

    A. Nemirovski and D. Yudin. Problem Complexity and Method Efficiency in Optimization . Wiley-Interscience, 1983

    1983

  50. [57]

    Nesterov

    Y. Nesterov. Introductory Lectures on Convex Optimization: A Basic Course , volume 87. Springer Science & Business Media, 2003

    2003

  51. [58]

    Nesterov

    Y. Nesterov. Gradient methods for minimizing composite functions. Mathematical Program- ming, 140:125–161, 2013

    2013

  52. [59]

    Nesterov and A

    Y. Nesterov and A. Nemirovskii. Interior-Point Polynomial Algorithms in Convex Program- ming. SIAM, 1994

    1994

  53. [60]

    Nouiehed, J.-S

    M. Nouiehed, J.-S. Pang, and M. Razaviyayn. On the pervasiveness of difference-convexity in optimization and statistics. Mathematical Programming, 174(1-2):195–222, 2019

    2019

  54. [61]

    Paffenholz

    A. Paffenholz. Polyhedral geometry and linear optimization. Unpublished Lecture Notes., 2010

    2010

  55. [62]

    J.-S. Pang, M. Razaviyayn, and A. Alvarado. Computing B-stationary points of nonsmooth DC programs. Mathematics of Operations Research, 42(1):95–118, 2017

    2017

  56. [63]

    P. M. Pardalos and G. Schnitger. Checking local optimality in constrained quadratic program- ming is NP-hard. Operations Research Letters, 7(1):33–35, 1988

    1988

  57. [64]

    P. M. Pardalos and S. A. Vavasis. Open questions in complexity theory for numerical opti- mization. Mathematical Programming, 57(1-3):337–339, 1992

    1992

  58. [65]

    R. T. Rockafellar. Convex Analysis, volume 18. Princeton university press, 1970

    1970

  59. [66]

    R. T. Rockafellar. Directionally Lipschitzian functions and subdifferential calculus. Proceedings of the London Mathematical Society , 3(2):331–355, 1979

    1979

  60. [67]

    R. T. Rockafellar. Extensions of subgradient calculus with applications to optimization. Non- linear Analysis: Theory, Methods & Applications , 9(7):665–698, 1985. 75

    1985

  61. [68]

    R. T. Rockafellar and R. J.-B. Wets. Variational Analysis, volume 317. Springer Science & Business Media, 2009

    2009

  62. [69]

    Scholtes

    S. Scholtes. Introduction to Piecewise Differentiable Equations . Springer Science & Business Media, 2012

    2012

  63. [70]

    X. Shen, G. C. Tseng, X. Zhang, and W. H. Wong. On ψ-learning. Journal of the American Statistical Association, 98(463):724–734, 2003

    2003

  64. [71]

    D. A. Spielman and S.-H. Teng. Smoothed analysis of termination of linear programming algorithms. Mathematical Programming, 97:375–404, 2003

    2003

  65. [72]

    Taylor, R

    G. Taylor, R. Burmeister, Z. Xu, B. Singh, A. Patel, and T. Goldstein. Training neural networks without gradients: A scalable ADMM approach. In International Conference on Machine Learning, pages 2722–2731. PMLR, 2016

    2016

  66. [73]

    Tian and A

    L. Tian and A. M.-C. So. Computing d-stationary points of ρ-margin loss SVM. In Interna- tional Conference on Artificial Intelligence and Statistics , pages 3772–3793. PMLR, 2022

    2022

  67. [74]

    Tian and A

    L. Tian and A. M.-C. So. No dimension-free deterministic algorithm computes approximate stationarities of Lipschitzians. Mathematical Programming, 208:51–74, 2024

    2024

  68. [75]

    L. Tian, K. Zhou, and A. M.-C. So. On the finite-time complexity and practical computation of approximate stationarity concepts of Lipschitz functions. In International Conference on Machine Learning, pages 21360–21379. PMLR, 2022

    2022

  69. [76]

    S. A. Vavasis and Y. Ye. A primal-dual interior point method whose running time depends only on the constraint matrix. Mathematical Programming, 74(1):79–120, 1996

    1996

  70. [77]

    Walther and A

    A. Walther and A. Griewank. Characterizing and testing subdifferential regularity in piecewise smooth optimization. SIAM Journal on Optimization , 29(2):1473–1501, 2019

    2019

  71. [79]

    Y. Ye. On the finite convergence of interior-point algorithms for linear programming. Mathe- matical Programming, 57(1-3):325–335, 1992

    1992

  72. [80]

    C. Yun, S. Sra, and A. Jadbabaie. Efficiently testing local optimality and escaping saddles for ReLU networks. In International Conference on Learning Representations , 2019

    2019

  73. [81]

    J. Zeng, T. T.-K. Lau, S. Lin, and Y. Yao. Global convergence of block coordinate descent in deep learning. In International Conference on Machine Learning , pages 7313–7323. PMLR, 2019

    2019

  74. [82]

    Zhang, M

    C. Zhang, M. Pham, S. Fu, and Y. Liu. Robust multicategory support vector machines using difference convex algorithm. Mathematical Programming, 169:277–305, 2018

    2018

  75. [83]

    Zhang, H

    J. Zhang, H. Lin, S. Jegelka, A. Jadbabaie, and S. Sra. Complexity of finding stationary points of nonsmooth nonconvex functions. In International Conference on Machine Learning , pages 11173–11182, 2020. 76

    2020

  76. [84]

    Zhang and M

    Z. Zhang and M. Brand. Convergent block coordinate descent for training Tikhonov regularized deep neural networks. Advances in Neural Information Processing Systems , 30, 2017

    2017

  77. [85]

    G. M. Ziegler. Lectures on Polytopes, volume 152. Springer Science & Business Media, 2012. 77

    2012

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.