Pith. sign in

REVIEW 2 major objections 5 minor 107 references

On computing Goldstein approximate second-order stationary points of structured nonsmooth nonconvex programs

T0 review · 2 major / 5 minor · reviewed 2026-07-31 · deepseek-v4-flash

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

Pith's one-line read A randomized first-order algorithm computes Goldstein approximate second-order stationary points of L-smooth functions, with oracle complexity Õ(n²/ε⁹ + n³/ε⁷), by smoothing the function and applying cubic Newton.

desk verdict Real new technique with one mechanical proof gap in the main theorem; fix the r⋆ scaling and this is a strong paper. read the letter →

arxiv 2607.24122 v1 pith:Q5IC7JPP submitted 2026-07-27 math.OC

Jiewen Guan , Anthony Man-Cho So This is my paper · ORCID
classification math.OC MSC 90C2690C3049J52
keywords randomizedsmoothingGoldsteinsubdifferentialsecond-orderstationarypointsnonsmoothnonconvexoptimizationcubicNewtonmethodweaklyconvexfunctionsbileveloraclecomplexity
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

Second-order stationarity—vanishing gradient plus a curvature nonnegativity condition—is the standard way to escape saddle points in nonconvex optimization, but for nonsmooth functions even defining a second-order critical point is delicate, and deterministic algorithms hit a fundamental barrier. This paper shows the barrier is not fatal: randomizing the smoothing radius turns any function with Lipschitz gradient into a twice-differentiable function with Lipschitz Hessian, and stationarity of the smoothed function transfers to a Goldstein-style second-order stationarity of the original. Then a cubic regularization method applied to the smoothed function finds such a point in Õ(n²/ε⁹ + n³/ε⁷) first-order oracle calls, with high probability. The same smoothing machinery extends to weakly convex functions via their Moreau envelopes and to bilevel programs, where it removes a third-differentiability assumption.

What carries the argument

The workhorse is the Goldstein generalized Hessian ∂²_δ f(x) = conv(∪_{y∈x+δBⁿ} ∂²_C f(y)) — the convex hull of Clarke Hessians in a δ-ball — together with the second-order randomized smoothing identity ∇²f_σ(x) = (n/σ) E_{s∼Unif(Sⁿ)}[∇f(x+σs)sᵀ], which lets the Hessian of the smoothed function be estimated from gradient values alone. The cubic subproblem min_p pᵀg + ½pᵀHp + (ξ/6)‖p‖³, whose global minimizers satisfy H + λI ⪰ 0 with λ = ξ‖p‖/2, provides the descent mechanism.

What would settle it

Check whether the stated r⋆ in Algorithm 2 satisfies r⋆ ≤ 1; if not, the inequality 17ξr⋆²/16 ≤ ε_g used in Proposition 4.7 is not guaranteed, and a function attaining these parameters would invalidate the proof.

Watch

Extended reading notes

Core claim

The central discovery is a second-order transfer theorem: for an L-smooth f and its uniformly smoothed version f_σ(x)=E_{u∼Unif(Bⁿ)}[f(x+σu)], ∇²f_σ is Lipschitz with constant O(L√n/σ), and moreover ∇f_σ(x)∈∂_σ f(x) and ∇²f_σ(x)∈∂²_σ f(x), the Goldstein subdifferential and generalized Hessian. Consequently, any (ε_g,ε_H)-second-order stationary point of f_σ with ε_g=ε₁/3, ε_H=ε₂ and σ≤min{δ,ε₁/(3L)} is an (ε₁,ε₂,δ)-Goldstein approximate SOSP of f. Algorithm 1 runs cubic Newton on f_σ, estimating its gradient and Hessian by finite differences of ∇f along random directions, and returns the desired point with probability 1−η.

Load-bearing premise

The algorithm requires an exact global minimizer of the cubic subproblem at every iteration; with only an approximate subproblem solution the model-decrease lemma fails and the proof gives no guarantee.

Editorial extensions

If this is right

  • With probability at least 1−η, Algorithm 1 returns an (ε₁,ε₂,δ)-Goldstein approximate SOSP of any L-smooth function using only first-order oracle calls; complexity is Õ(ΔL⁸n²/ε⁹ + ΔL⁶n³/ε⁷) when ε₁,ε₂,δ ≍ ε.
  • The same algorithm computes Goldstein approximate SOSPs of ρ-weakly convex functions once the Moreau envelope and its proximal map are available (Corollary 5.8).
  • For nonconvex–strongly-convex bilevel programs it yields second-order guarantees without third-order differentiability of the lower-level problem (Corollary 5.11).
  • For nonconvex–PŁ bilevel programs it applies through the weak-convexity route (Corollary 5.13).
  • The paper conjectures that no dimension-free randomized algorithm exists for this task, and its framework may be extended to trilevel optimization.

Reading between the lines

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

  • If the exact-cubic-solver assumption can be relaxed to an inexact solve with controlled error, the algorithm would become directly usable with standard trust-region or Lanczos-based cubic solvers; the paper does not provide such an analysis.
  • The Moreau-envelope stationarity coincidence (Corollary 5.3) suggests a general recipe: define second-order stationarity for nonsmooth functions through an L-smooth surrogate, which could reshape landscape analyses for nonsmooth deep learning objectives.
  • The Hessian estimator built only from gradient differences might be adapted to zeroth-order (function-value-only) settings, where similar concentration bounds would yield practical derivative-free second-order methods — an extension the paper does not explore.
  • The dimension dependence n³/ε⁷ in the Hessian-estimation term suggests that the true bottleneck is the variance of Hessian estimates; sharp variance reduction, e.g., via control variates or importance sampling, could materially improve the complexity.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 5 minor

Summary. The paper proposes a randomized first-order method for computing Goldstein approximate second-order stationary points of L-smooth (not necessarily twice differentiable) functions. The method applies uniform randomized smoothing to obtain a function f_σ with Lipschitz Hessian, estimates the gradient and Hessian of f_σ via first-order sampling, and then runs a cubic-Newton-type method with high-probability concentration bounds. The main result is an oracle complexity Õ(ΔL⁸n²/ε⁹ + ΔL⁶n³/ε⁷) in the regime ε₁,ε₂,δ ≍ ε. The paper also defines a Moreau-envelope notion of Goldstein SOSPs for weakly convex functions, proves a second-order stationarity correspondence, and sketches applications to nonconvex-strongly-convex and nonconvex-(Polyak–Łojasiewicz) bilevel programs.

Significance. If the central theorem can be made fully correct, the paper would provide the first randomized upper bound for computing Goldstein second-order stationary points of L-smooth functions, complementing a deterministic lower bound and extending second-order smoothing ideas from [71]. The smoothing calculus in Theorem 3.1, the gradient/Hessian concentration estimates, and the Moreau-envelope second-order correspondence are potentially useful tools. The paper is careful with measure-theoretic details and gives self-contained proofs of the main smoothing identities. Its main limitations are the dependence on exact global solutions of the cubic subproblem, the existential nature of the iterate guarantee, and a missing condition in the proof of Proposition 4.7 that currently leaves the main theorem unproven as stated.

major comments (2)
  1. [Algorithm 2, Step 1; Proposition 4.7; Theorem 4.1] The definition r⋆ := min{16εg/(17ξ), 24εH/(37ξ)} is inconsistent with the proof of Proposition 4.7. The proof asserts 17ξr⋆²/16 ≤ εg, but the first component only gives ξr⋆² ≤ (16εg/17)r⋆, which implies the desired inequality only when r⋆ ≤ 17/16. The second component does not enforce this. Thus the unconditional gradient bound in Prop 4.7 is not established, and Theorem 4.1 is not proven as stated. The general K⋆ display in Theorem 4.1 (first term ∆L^{1/2}n^{1/4}/(σ^{1/2}εg^{3/2})) appears to assume r⋆ ≈ (εg/ξ)^{1/2}, further confirming the inconsistency. Please fix the definition, e.g., r⋆ := min{√(16εg/(17ξ)), 24εH/(37ξ)}, or add an explicit r⋆≤1 hypothesis and update the batch sizes, complexity display, and proof accordingly.
  2. [Section 5.2.2 and Algorithm 5] The claimed application to NC–P/Łojasiewicz bilevel programs is left incomplete. Algorithm 5 requires Prox_{hp/(2ρ)}, but the paper says the evaluation 'allows us to apply the zeroth-order algorithm in [93]' and then 'leave[s] the details to interested readers.' No oracle complexity or accuracy analysis is given for this proximal computation, so Corollary 5.13 is conditional on an unspecified subroutine. Since this is presented as one of the paper's applications, the missing analysis should either be supplied or the claim should be explicitly marked as a heuristic extension.
minor comments (5)
  1. [Theorem 4.1 and Algorithm 2] The guarantee is existential: the proof shows that some k⋆ satisfies the stationarity conditions, but no stopping criterion or certificate is provided. A short discussion of how the user is supposed to identify such an iterate would strengthen the 'computing' language.
  2. [Algorithm 2, Step 5] The algorithm requires an exact global minimizer of the cubic subproblem (4). Lemma 4.4 relies on global optimality. The paper cites polynomial-time solvability, but a brief discussion of inexact subproblem solves and their effect on Lemma 4.4/Prop 4.7 would be useful, especially since the algorithm is otherwise first-order.
  3. [Theorem 4.1 and Algorithm 2] K⋆ is defined using Δ = fσ(x0) − min fσ, which may not be known a priori. The paper should state how Δ is obtained or how the analysis extends to an unknown Δ (e.g., doubling).
  4. [Example 5.2] The claim ∂²_C f(0)=∅ follows because f''(y)→+∞ rather than having finite cluster points; a parenthetical explanation would avoid confusion.
  5. [Section 5.1, Definition 5.7] The proposed definition of Goldstein SOSPs for weakly convex functions depends on the Moreau parameter 1/(2ρ). It would help to state explicitly that this is a new definition and to discuss its sensitivity to the choice of λ.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the core randomized-smoothing / cubic-Newton derivation is self-contained and does not reduce to its inputs; the flagged r* inequality is a proof gap, not circularity.

full rationale

The central claim (Theorem 4.1) is derived from self-contained ingredients: Theorem 3.1 shows randomized smoothing produces a function with Lipschitz Hessian, Propositions 3.2 and 3.4 give unbiased gradient/Hessian estimates with Bernstein-type concentration, Lemma 4.4 gives cubic-model decrease, Lemma 4.5 transfers it to f_sigma, and Lemma 4.6 bounds the resulting gradient and Hessian. Proposition 3.8 then transfers an approximate SOSP of f_sigma to a Goldstein approximate SOSP of f; this is a one-way implication, not an equivalence-by-construction. No fitted quantity is renamed as a prediction, and no parameter is calibrated to the Goldstein target. The weakly convex extension (Section 5.1) explicitly defines a new Moreau-envelope-based notion of Goldstein SOSPs, justifies it via optimality coincidence (Proposition 5.6, Corollary 5.3), and then computes exactly that defined object in Algorithm 3. This is transparent definition, not a hidden circular derivation of an independent target. The bilevel NC-P/L application relies on Lemma 5.12 from [18], co-authored by the present second author; however, that cited result has its own stated assumptions and is not derived here, so it is independent evidence rather than a self-citation loop. Other self-citations ([47], [48]) appear only as motivation or future directions, not in the proof of the main theorem. I do flag one serious internal defect: in Proposition 4.7 the chain '17ξr*²/16 ≤ ε_g' requires r* ≤ 1, which is not enforced by the stated r* := min{16ε_g/(17ξ), 24ε_H/(37ξ)}. This is a correctness gap in the proof as written, not a circular step: the conclusion is not assumed by the input, it just is not established for r* > 1.

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

No free parameters are fitted to data; all constants are universal or chosen analytically from L, ε, δ, η, n, and Δ. The central claim rests on the L-smooth oracle model, standard results in analysis and probability, and several external lemmas from the optimization literature, one of which ([18]) is co-authored by A.M.-C. So. The extensions additionally assume exact proximal/hypergradient oracles without counting their cost.

assumptions (4)
  • domain assumption f is L-smooth and a first-order oracle returns exact ∇f(x) at any query.
    Main assumption throughout Sections 3–4; all estimators and complexity bounds are stated in this oracle model.
  • standard math Standard measure-theoretic and probability tools (dominated convergence, Rademacher, Heine, vector/matrix Bernstein) are valid.
    Used in proofs of Theorem 3.1 and Propositions 3.2/3.4; no novel assumption.
  • standard math External lemmas: [71, Prop 2.3] (smoothing makes Lipschitz functions smooth with constant cL√n/σ), [104, Prop 6(ii)] (first-order Goldstein-to-gradient transfer), [17, Thm 3.1] (cubic model characterization), and the polynomial solvability of (4).
    Load-bearing citations for the smoothing bound, stationarity transfer, and subproblem solution; accepted literature results, not re-derived.
  • domain assumption For the weakly convex and bilevel extensions, exact proximal mappings and hypergradients are available at no extra oracle cost; the weak-convexity/smoothness of hyperobjectives comes from [27, Lemma 2.5], [20, Prop 3.1], and [18, Theorem 3].
    Algorithm 3 and 5 evaluate ∇g_{1/(2ρ)} and ∇h via these oracles; their cost is not included in the claimed complexity.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On computing Goldstein approximate second-order stationary points of structured nonsmooth nonconvex programs." pith.science (2026). https://pith.science/paper/Q5IC7JPP

@misc{pith2026260724122,
  author       = {Pith},
  title        = {Pith review of: On computing Goldstein approximate second-order stationary points of structured nonsmooth nonconvex programs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/Q5IC7JPP}},
  note         = {Machine review of arXiv:2607.24122}
}
abstract

In this paper, we exhibit a randomized first-order algorithm to compute Goldstein approximate second-order stationary points of $L$-smooth functions, using tools from randomized smoothing. The algorithm has oracle complexity $\widetilde{O}({ n^2}/{\varepsilon^9}+{ n^3}/{\varepsilon^7})$, where $n=1,2,\ldots$ is the input dimension and $\varepsilon>0$ is the (common) tolerance. We also present extensions to weakly convex functions and applications to bilevel optimization.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

107 extracted references · 6 linked inside Pith

  1. [18]

    H. Chen, J. Li, and A. M.-C. So. Set smoothness unlocks Clarke hyper-stationarity in bilevel optimization.arXiv preprint arXiv:2506.04587, 2025

    arXiv 2025

  2. [71]

    T. Lin, Z. Zheng, and M. I. Jordan. Gradient-free methods for deterministic and stochastic nonsmooth nonconvex optimization. InProceedings of the 36th International Conference on Neural Information Processing Systems, pages 26160–26175, 2022

    2022

  3. [93]

    O. Shamir. An optimal algorithm for bandit and zero-order convex optimization with two-point feedback.Journal of Machine Learning Research, 18(52):1–11, 2017

    2017

  4. [1]

    Arora, N

    S. Arora, N. Golowich, N. Cohen, and W. Hu. A convergence analysis of gradient descent for deep linear neural networks. InProceedings of the 7th International Conference on Learning Representations, 2019

    2019

  5. [2]

    Atarashi, S

    K. Atarashi, S. Oyama, and M. Kurihara. Factorization machines with regularization for sparse feature interactions.Journal of Machine Learning Research, 22(153):1–50, 2021

    2021

  6. [3]

    Y. Bai, Q. Jiang, and J. Sun. Subgradient descent learns orthogonal dictionaries. InProceedings of the 7th International Conference on Learning Representations, 2019

    2019

  7. [4]

    Barvinok.A Course in Convexity, volume 54 ofGraduate Studies in Mathematics

    A. Barvinok.A Course in Convexity, volume 54 ofGraduate Studies in Mathematics. American Mathematical Society, Providence, Rhode Island, 2002

    2002

  8. [5]

    Bhojanapalli, B

    S. Bhojanapalli, B. Neyshabur, and N. Srebro. Global optimality of local search for low rank matrix recovery. InProceedings of the 30th International Conference on Neural Information Processing Systems, pages 3880–3888, 2016

    2016

Show all 107 references
  1. [6]

    Bianchi, W

    P. Bianchi, W. Hachem, and S. Schechtman. Stochastic subgradient descent escapes active strict saddles on weakly convex functions.Mathematics of Operations Research, 49(3):1761–1790, 2024

    2024

  2. [7]

    Blondel, A

    M. Blondel, A. Fujino, N. Ueda, and M. Ishihata. Higher-order factorization machines. In Proceedings of the 30th International Conference on Neural Information Processing Systems, pages 3359–3367, 2016

    2016

  3. [8]

    Blondel, M

    M. Blondel, M. Ishihata, A. Fujino, and N. Ueda. Polynomial networks and factorization ma- chines: New insights and efficient training algorithms. InProceedings of the 33rd International Conference on Machine Learning, pages 850–858, 2016

    2016

  4. [9]

    Blondel, F

    M. Blondel, F. Llinares-L´ opez, R. Dadashi, L. Hussenot, and M. Geist. Learning energy networks with generalized Fenchel–Young losses. InProceedings of the 36th International Conference on Neural Information Processing Systems, pages 12516–12528, 2022

    2022

  5. [10]

    Blondel, A

    M. Blondel, A. Martins, and V. Niculae. Learning classifiers with Fenchel–Young losses: Generalized entropies, margins, and algorithms. InProceedings of the 22nd International Conference on Artificial Intelligence and Statistics, pages 606–615, 2019

    2019

  6. [11]

    Blondel, A

    M. Blondel, A. F. Martins, and V. Niculae. Learning with Fenchel–Young losses.Journal of Machine Learning Research, 21(35):1–69, 2020

    2020

  7. [12]

    Blondel, V

    M. Blondel, V. Niculae, T. Otsuka, and N. Ueda. Multi-output polynomial networks and factor- ization machines. InProceedings of the 31st International Conference on Neural Information Processing Systems, pages 3351–3361, 2017. 30

    2017

  8. [13]

    V. I. Bogachev.Measure Theory, Volume I. Springer-Verlag, Berlin, Heidelberg, 2007

    2007

  9. [14]

    S. Bubeck. Convex optimization: Algorithms and complexity.Foundations and Trends®in Machine Learning, 8(3–4):231–357, 2015

    2015

  10. [15]

    J. V. Burke, A. S. Lewis, and M. L. Overton. A robust gradient sampling algorithm for nonsmooth, nonconvex optimization.SIAM Journal on Optimization, 15(3):751–779, 2005

    2005

  11. [16]

    V. A. Cabannes, F. Bach, and A. Rudi. Fast rates for structured prediction. InProceedings of the 34th Annual Conference on Learning Theory, pages 823–865, 2021

    2021

  12. [17]

    Cartis, N

    C. Cartis, N. I. M. Gould, and Ph. L. Toint. Adaptive cubic regularisation methods for uncon- strained optimization. Part I: Motivation, convergence and numerical results.Mathematical Programming, 127(2):245–295, 2011

    2011

  13. [19]

    H. Chen, H. Xu, R. Jiang, and A. M.-C. So. Lower-level duality based reformulation and majorization minimization algorithm for hyperparameter optimization. InProceedings of the 27th International Conference on Artificial Intelligence and Statistics, pages 784–792, 2024

    2024

  14. [20]

    L. Chen, Y. Ma, and J. Zhang. Near-optimal nonconvex-strongly-convex bilevel optimization with fully first-order oracles.Journal of Machine Learning Research, 26(109):1–56, 2025

    2025

  15. [21]

    L. Chen, J. Xu, and J. Zhang. On finding small hyper-gradients in bilevel optimization: Hardness results and improved analysis. InProceedings of the 37th Annual Conference on Learning Theory, pages 947–980, 2024

    2024

  16. [22]

    F. H. Clarke.Optimization and Nonsmooth Analysis. Classics in Applied Mathematics. Society for Industrial and Applied Mathematics, Philadelphia, 1990

    1990

  17. [23]

    A. R. Conn, N. I. M. Gould, and Ph. L. Toint.Trust-Region Methods. MOS-SIAM Series on Optimization. Society for Industrial and Applied Mathematics, Philadelphia, 2000

    2000

  18. [24]

    Cui and J.-S

    Y. Cui and J.-S. Pang.Modern Nonconvex Nondifferentiable Optimization. MOS-SIAM Series on Optimization. Society for Industrial and Applied Mathematics, Philadelphia, 2021

    2021

  19. [25]

    F. E. Curtis, Z. Lubberts, and D. P. Robinson. Concise complexity analyses for trust region methods.Optimization Letters, 12(8):1713–1724, 2018

    2018

  20. [26]

    Davis and D

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

    2019

  21. [27]

    Davis and D

    D. Davis and D. Drusvyatskiy. Proximal methods avoid active strict saddles of weakly convex functions.Foundations of Computational Mathematics, 22(2):561–606, 2022

    2022

  22. [28]

    Davis, D

    D. Davis, D. Drusvyatskiy, and L. Jiang. Active manifolds, stratifications, and convergence to local minima in nonsmooth optimization.Foundations of Computational Mathematics, pages 1–83, 2025

    2025

  23. [29]

    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 Proceedings of the 36th International Conference on Neural Information Processing Systems, pages 6692–6...

    2022

  24. [30]

    Davis and L

    D. Davis and L. Jiang. A local nearly linearly convergent first-order method for nonsmooth functions with quadratic growth.Foundations of Computational Mathematics, 25(3):943–1024, 2025

    2025

  25. [31]

    J. C. Duchi, P. L. Bartlett, and M. J. Wainwright. Randomized smoothing for stochastic optimization.SIAM Journal on Optimization, 22(2):674–701, 2012

    2012

  26. [32]

    Durrett.Probability: Theory and Examples, volume 49 ofCambridge Series in Statistical and Probabilistic Mathematics

    R. Durrett.Probability: Theory and Examples, volume 49 ofCambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge, fifth edition, 2019

    2019

  27. [33]

    L. C. Evans and R. F. Gariepy.Measure Theory and Fine Properties of Functions. Textbooks in Mathematics. CRC Press, Taylor & Francis Group, 6000 Broken Sound Parkway NW, Suite 300, Boca Raton, FL 33487-2742, revised edition, 2015

    2015

  28. [34]

    A. D. Flaxman, A. T. Kalai, and H. B. McMahan. Online convex optimization in the bandit setting: Gradient descent without a gradient. InProceedings of the 16th Annual ACM–SIAM Symposium on Discrete Algorithms, pages 385–394, 2005

    2005

  29. [35]

    G. B. Folland.Real Analysis: Modern Techniques and Their Applications. Pure and Applied Mathematics: A Wiley Series of Texts, Monographs, and Tracts. John Wiley & Sons, Inc., New York, second edition, 1999

    1999

  30. [36]

    G. B. Folland.Advanced Calculus. Second edition, 2024. https://sites.math.washington. edu//˜folland/AdvCalc24.pdf

    2024

  31. [37]

    R. Ge, F. Huang, C. Jin, and Y. Yuan. Escaping from saddle points — online stochastic gradient for tensor decomposition. InProceedings of the 28th Annual Conference on Learning Theory, pages 797–842, 2015

    2015

  32. [38]

    B. Gebken. Using second-order information in gradient sampling methods for nonsmooth optimization.arXiv preprint arXiv:2210.04579, 2022

    2022 arXiv

  33. [39]

    B. Gebken. Analyzing the speed of convergence in nonsmooth optimization via the Goldstein subdifferential.Journal of Optimization Theory and Applications, 206(3):1–38, 2025

    2025

  34. [40]

    Gebken and S

    B. Gebken and S. Peitz. An efficient descent method for locally Lipschitz multiobjective optimization problems.Journal of Optimization Theory and Applications, 188(3):696–723, 2021

    2021

  35. [41]

    Ghadimi and M

    S. Ghadimi and M. Wang. Approximation methods for bilevel programming.arXiv preprint arXiv:1802.02246, 2018

    2018 arXiv

  36. [42]

    Giovannelli, G

    T. Giovannelli, G. D. Kent, and L. N. Vicente. A stochastic gradient method for trilevel optimization.arXiv preprint arXiv:2505.06805, 2025

    2025 arXiv

  37. [43]

    A. A. Goldstein. Optimization of Lipschitz continuous functions.Mathematical Programming, 13(1):14–22, 1977

    1977

  38. [44]

    Griewank

    A. Griewank. The modification of Newton’s method for unconstrained optimization by bounding cubic terms. Technical Report NA/12, Department of Applied Mathematics and Theoretical Physics, University of Cambridge, United Kingdom, 1981

    1981

  39. [45]

    Grimmer and Z

    B. Grimmer and Z. Jia. Goldstein stationarity in Lipschitz constrained optimization.Opti- mization Letters, 19:425–435, 2025. 32

    2025

  40. [46]

    Grohs and S

    P. Grohs and S. Hosseini. ε-subgradient algorithms for locally Lipschitz functions on Rieman- nian manifolds.Advances in Computational Mathematics, 42(2):333–360, 2016

    2016

  41. [47]

    Guan and A

    J. Guan and A. M.-C. So. ℓ1-norm rank-one symmetric matrix factorization has no spurious second-order stationary points.arXiv preprint arXiv:2410.05025, 2024

    2024 arXiv

  42. [48]

    Guan and A

    J. Guan and A. M.-C. So. On the hardness of deterministic second-order optimization of functions with Lipschitz gradients. Unpublished manuscript, 2026

    2026

  43. [49]

    Guo and B

    X. Guo and B. Hu. Global convergence of direct policy search for state-feedback H∞ robust control: A revisit of nonsmooth synthesis with Goldstein subdifferential. InProceedings of the 36th International Conference on Neural Information Processing Systems, pages 32801–32815, 2022

    2022

  44. [50]

    N. T. Hang, B. S. Mordukhovich, and M. E. Sarabi. Augmented Lagrangian method for second-order cone programs under second-order sufficiency.Journal of Global Optimization, 82(1):51–81, 2022

    2022

  45. [51]

    Hiriart-Urruty, J.-J

    J.-B. Hiriart-Urruty, J.-J. Strodiot, and V. H. Nguyen. Generalized Hessian matrix and second-order optimality conditions for problems with C1,1 data.Applied Mathematics and Optimization, 11(1):43–56, 1984

    1984

  46. [52]

    Hiriart-Urruty and D

    J.-B. Hiriart-Urruty and D. Ye. Sensitivity analysis of all eigenvalues of a symmetric matrix. Numerische Mathematik, 70(1):45–72, 1995

    1995

  47. [53]

    Hoheisel, M

    T. Hoheisel, M. Laborde, and A. Oberman. A regularization interpretation of the proximal point method for weakly convex functions.Journal of Dynamics and Games, 7(1):79–96, 2020

    2020

  48. [54]

    R. A. Horn and C. R. Johnson.Matrix Analysis. Cambridge University Press, Cambridge, second edition, 2012

    2012

  49. [55]

    Huang, X

    M. Huang, X. Chen, K. Ji, S. Ma, and L. Lai. Efficiently escaping saddle points in bilevel optimization.Journal of Machine Learning Research, 26(1):1–61, 2025

    2025

  50. [56]

    Jiang, C

    Y. Jiang, C. He, C. Zhang, D. Ge, B. Jiang, and Y. Ye. Beyond nonconvexity: A universal trust-region method with new analyses.Journal of Scientific Computing, 106(1):28, 2026

    2026

  51. [57]

    C. Jin, R. Ge, P. Netrapalli, S. M. Kakade, and M. I. Jordan. How to escape saddle points efficiently. InProceedings of the 34th International Conference on Machine Learning, pages 1724–1732, 2017

    2017

  52. [58]

    Kato.Perturbation Theory for Linear Operators, volume 132 ofClassics in Mathematics

    T. Kato.Perturbation Theory for Linear Operators, volume 132 ofClassics in Mathematics. Springer-Verlag, Berlin, Heidelberg, second edition, 1995. Originally published as volume 132 in the series: Grundlehren der Mathematischen Wissenschaften

    1995

  53. [59]

    G. D. Kent.Stochastic Methods for Multi-Level and Multi-Objective Optimization. PhD thesis, Lehigh University, 2025

    2025

  54. [60]

    P. D. Khanh, V. V. Khoa, B. S. Mordukhovich, and V. T. Phat. Local minimizers of nonconvex functions in Banach spaces via Moreau envelopes.Vietnam Journal of Mathematics, 53(4):803–813, 2025

    2025

  55. [61]

    P. D. Khanh, B. S. Mordukhovich, V. T. Phat, and D. B. Tran. Inexact proximal methods for weakly convex functions.Journal of Global Optimization, 91(3):611–646, 2025. 33

    2025

  56. [62]

    Kong and A

    S. Kong and A. S. Lewis. Lipschitz minimization and the Goldstein modulus.Mathematical Programming, pages 1–30, 2025

    2025

  57. [63]

    Kornowski and O

    G. Kornowski and O. Shamir. Oracle complexity in nonsmooth nonconvex optimization.arXiv preprint arXiv:2104.06763 (v1), 2021

    2021 arXiv

  58. [64]

    Kornowski and O

    G. Kornowski and O. Shamir. An algorithm with optimal dimension-dependence for zero- order nonsmooth nonconvex stochastic optimization.Journal of Machine Learning Research, 25(122):1–14, 2024

    2024

  59. [65]

    J. Kwon, D. Kwon, S. Wright, and R. D. Nowak. On penalty methods for nonconvex bilevel optimization and first-order stochastic approximation. InProceedings of the 12th International Conference on Learning Representations, 2024

    2024

  60. [66]

    J. D. Lee, M. Simchowitz, M. I. Jordan, and B. Recht. Gradient descent only converges to minimizers. InProceedings of the 29th Annual Conference on Learning Theory, pages 1246–1257, 2016

    2016

  61. [67]

    M. Lei, T. K. Pong, S. Sun, and M.-C. Yue. Subdifferentially polynomially bounded functions and Gaussian smoothing-based zeroth-order optimization.SIAM Journal on Optimization, 35(2):1393–1418, 2025

    2025

  62. [68]

    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

  63. [69]

    J. Li, L. Zhu, and A. M.-C. So. Nonsmooth nonconvex–nonconcave minimax optimization: Primal–dual balancing and iteration complexity analysis.Mathematical Programming, 214(1- 2):591–641, 2025

    2025

  64. [70]

    X. Li, Z. Zhu, A. M.-C. So, and R. Vidal. Nonconvex robust low-rank matrix recovery.SIAM Journal on Optimization, 30(1):660–686, 2020

    2020

  65. [72]

    A. F. Martins, M. Treviso, A. Farinhas, P. M. Aguiar, M. A. Figueiredo, M. Blondel, and V. Niculae. Sparse continuous distributions and Fenchel–Young losses.Journal of Machine Learning Research, 23(257):1–74, 2022

    2022

  66. [73]

    Mohajerin Esfahani, S

    P. Mohajerin Esfahani, S. Shafieezadeh-Abadeh, G. A. Hanasusanto, and D. Kuhn. Data-driven inverse optimization with imperfect information.Mathematical Programming, 167(1):191–234, 2018

    2018

  67. [74]

    B. S. Mordukhovich.Variational Analysis and Generalized Differentiation I: Basic Theory, volume 330 ofGrundlehren der Mathematischen Wissenschaften, A Series of Comprehensive Studies in Mathematics. Springer-Verlag, Berlin, Heidelberg, first edition, 2006

    2006

  68. [75]

    B. S. Mordukhovich.Second-Order Variational Analysis in Optimization, Variational Stability, and Control: Theory, Algorithms, Applications. Springer Series in Operations Research and Financial Engineering. Springer Nature Switzerland AG, Cham, Switzerland, 2024. 34

    2024

  69. [76]

    B. S. Mordukhovich, N. M. Nam, and N. D. Yen. Subgradients of marginal functions in parametric mathematical programming.Mathematical Programming, 116(1):369–396, 2009

    2009

  70. [77]

    J.-J. Moreau. Proximit´ e et dualit´ e dans un espace Hilbertien.Bulletin de la Soci´ et´ e Math´ ematique de France, 93:273–299, 1965

    1965

  71. [78]

    Nakatsukasa

    Y. Nakatsukasa. Off-diagonal perturbation, first-order approximation and quadratic residual bounds for matrix eigenvalue problems. In T. Sakurai, S.-L. Zhang, T. Imamura, Y. Ya- mamoto, Y. Kuramashi, and T. Hoshi, editors,Eigenvalue Problems: Algorithms, Software and Applicati...

    2015

  72. [79]

    Nesterov and B

    Yu. Nesterov and B. T. Polyak. Cubic regularization of Newton method and its global performance.Mathematical Programming, 108(1):177–205, 2006

    2006

  73. [80]

    Nesterov and V

    Yu. Nesterov and V. Spokoiny. Random gradient-free minimization of convex functions. Foundations of Computational Mathematics, 17(2):527–566, 2017

    2017

  74. [81]

    Nocedal and S

    J. Nocedal and S. J. Wright.Numerical Optimization. Springer Series in Operations Research and Financial Engineering. Springer Science+Business Media, New York, 2006

    2006

  75. [82]

    Phuoc Hai, F

    L. Phuoc Hai, F. Lara, and B. S. Mordukhovich. Regular subgradients of marginal functions with applications to calculus and bilevel programming.Journal of Optimization Theory and Applications, 205(2):36, 2025

    2025

  76. [83]

    I. F. Pinelis and A. I. Sakhanenko. Remarks on inequalities for large deviation probabilities. Theory of Probability & Its Applications, 30(1):143–148, 1986

    1986

  77. [84]

    B. T. Polyak. Gradient methods for the minimisation of functionals.USSR Computational Mathematics and Mathematical Physics, 3(4):864–878, 1963

    1963

  78. [85]

    Pougkakiotis and D

    S. Pougkakiotis and D. Kalogerias. A zeroth-order proximal stochastic gradient method for weakly convex stochastic optimization.SIAM Journal on Scientific Computing, 45(5):A2679– A2702, 2023

    2023

  79. [86]

    Rakotomandimby, J.-P

    S. Rakotomandimby, J.-P. Chancelier, M. De Lara, and M. Blondel. Learning with Fitzpatrick losses. InProceedings of the 38th International Conference on Neural Information Processing Systems, pages 79381–79409, 2024

    2024

  80. [87]

    R. T. Rockafellar.Convex Analysis. Princeton Landmarks in Mathematics and Physics. Princeton University Press, Princeton, New Jersey, 1997

    1997

  81. [88]

    R. T. Rockafellar and R. J.-B. Wets.Variational Analysis, volume 317 ofGrundlehren der Mathematischen Wissenschaften, A Series of Comprehensive Studies in Mathematics. Springer Berlin, Heidelberg, 2009

    2009

  82. [89]

    Roulet, T

    V. Roulet, T. Liu, N. Vieillard, M. E. Sander, and M. Blondel. Loss functions and operators generated by f-divergences. InProceedings of the 42nd International Conference on Machine Learning, pages 52110–52138, 2025

    2025

  83. [90]

    Rudin.Principles of Mathematical Analysis

    W. Rudin.Principles of Mathematical Analysis. International Series in Pure and Applied Mathematics. McGraw-Hill Book Company, New York, third edition, 1976. 35

    1976

  84. [91]

    Sahinoglu, Y

    E. Sahinoglu, Y. Sun, and S. Shahrampour. Finite-time analysis of stochastic nonconvex nonsmooth optimization on the Riemannian manifolds.arXiv preprint arXiv:2510.21468, 2025

    2025

  85. [92]

    R. Sato, M. Tanaka, and A. Takeda. A gradient method for multilevel optimization. In Proceedings of the 35th International Conference on Neural Information Processing Systems, pages 7522–7533, 2021

    2021

  86. [94]

    Shen and T

    H. Shen and T. Chen. On penalty-based bilevel gradient descent method. InProceedings of the 40th International Conference on Machine Learning, pages 30992–31015, 2023

    2023

  87. [95]

    Sonntag, B

    K. Sonntag, B. Gebken, G. M¨ uller, S. Peitz, and S. Volkwein. A descent method for nonsmooth multiobjective optimization in Hilbert spaces.Journal of Optimization Theory and Applications, 203(1):455–487, 2024

    2024

  88. [96]

    J. Sun, Q. Qu, and J. Wright. A geometric analysis of phase retrieval.Foundations of Computational Mathematics, 18(5):1131–1198, 2018

    2018

  89. [97]

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

    2022

  90. [98]

    Vershynin.High-Dimensional Probability: An Introduction with Applications in Data Science, volume 47 ofCambridge Series in Statistical and Probabilistic Mathematics

    R. Vershynin.High-Dimensional Probability: An Introduction with Applications in Data Science, volume 47 ofCambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge, 2018

    2018

  91. [99]

    J.-P. Vial. Strong and weak convexity of sets and functions.Mathematics of Operations Research, 8(2):231–259, 1983

    1983

  92. [100]

    L. N. Vicente and P. H. Calamai. Bilevel and multilevel programming: A bibliography review. Journal of Global Optimization, 5(3):291–306, 1994

    1994

  93. [101]

    J. Xia, Z. Lin, and Q. Deng. Revisiting randomized smoothing: Nonsmooth nonconvex optimization beyond global Lipschitz continuity.arXiv preprint arXiv:2508.13496, 2025

    2025 arXiv

  94. [102]

    H. Yang, L. Luo, C. J. Li, M. Jordan, and M. Fazel. Accelerating inexact hypergradient descent for bilevel optimization. InOPT 2023: Optimization for Machine Learning (NeurIPS 2023 Workshop), 2023

    2023

  95. [103]

    Yousefian, A

    F. Yousefian, A. Nedi´ c, and U. V. Shanbhag. On stochastic gradient and subgradient methods with adaptive steplength sequences.Automatica, 48(1):56–67, 2012

    2012

  96. [104]

    Zhang, H

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

    2020

  97. [105]

    J. Zhou, X. Liu, J. Nie, and X. Tang. A tight SDP relaxation for the cubic–quartic regularization problem.arXiv preprint arXiv:2511.00168, 2025. 36

    2025

  98. [106]

    Z. Zhu, T. Ding, J. Zhou, X. Li, C. You, J. Sulam, and Q. Qu. A geometric analysis of neural collapse with unconstrained features. InProceedings of the 35th International Conference on Neural Information Processing Systems, pages 29820–29834, 2021

    2021

  99. [107]

    V. A. Zorich.Mathematical Analysis I. Universitext. Springer-Verlag, Berlin, Heidelberg, second edition, 2015. Original Russian edition: Matematicheskij Analiz (Part I, 6th corrected edition, Moscow, 2012) MCCME (Moscow Center for Continuous Mathematical Education Publ.). 37

    2015

Pith tools

Reviewed July 31, 2026 · model on record in the stance chip above.