acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

In this paper, we exhibit a randomized first-order algorithm to compute Goldstein approximate second-order stationary points of -smooth functions, using tools from randomized smoothing. The algorithm has oracle complexity , where is the input dimension and is the (common) tolerance. We also present extensions to weakly convex functions and applications to bilevel optimization.

Primary area:
optimization
Keywords:
Variational analysis, second-order theory, upper bounds, oracle complexity, nonconvex nonsmooth optimization, $L$-smooth functions, weak convexity, bilevel optimization, second-order stationarity

Reviews

Among:
Shape:
1234this paper, Top 17%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.75 over 4 reviews, above 83% of the others.
Reviewer_6uBEOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper investigates the computation of Goldstein approximate second-order stationary points for nonconvex functions with Lipschitz-continuous gradients, without assuming twice differentiability or Lipschitz-continuous Hessians. The proposed approach combines randomized smoothing, gradient-based estimators of gradients and Hessians, and cubic regularization. The authors establish a high-probability first-order oracle complexity of O~(n2ε−9+n3ε−7)\widetilde{O}(n^2\varepsilon^{-9}+n^3\varepsilon^{-7}) and show that approximate stationarity of the smoothed function transfers to the original problem. The framework is further extended to weakly convex functions via the Moreau envelope, with applications to bilevel optimization. The results are supported by theoretical analysis and illustrative examples, without numerical experiments.

Critical strengths
  1. They provide a randomized algorithm with complexity guarantees. The authors establish that Goldstein approximate second-order stationary points of Lipschitz-gradient functions can be computed using polynomially many first-order oracle calls. This provides a rigorous computational guarantee without requiring twice differentiability or Lipschitz Hessians.

  2. A second-order smoothing framework is introduced. The paper combines randomized smoothing with cubic regularization and proves that stationarity guarantees transfer from the smoothed surrogate to the original function. Its Moreau-envelope extension provides a principled stationarity notion and algorithmic approach for weakly convex nonsmooth functions, broadening the framework’s theoretical applicability.

Critical weaknesses
  1. The algorithm’s practicality remains unclear. Algorithm 1 requires globally solving the cubic-regularized subproblem in Eq. (2) at every iteration. It is a very challenging task. Its computational cost is not included in the first-order oracle bound, and the numerical accuracy required to preserve the guarantees is unspecified.

  2. No substantive comparison with the concurrent Lei et al. (2026). The introduction acknowledges this work, which targets essentially the same stationarity notion and also combines randomized smoothing with cubic regularization, but provides no quantitative comparison of assumptions, guarantees, or complexity. The paper should establish precisely what the different oracle and smoothing distribution enable.

  3. The complexity bound is steep. The ε−9\varepsilon^{-9} and n3ε−7n^3\varepsilon^{-7} dependence suggests substantial computational costs at high accuracy or in large dimensions. No numerical evidence demonstrates a useful operating regime, and the paper does not establish whether these dependencies are intrinsic or artifacts of the analysis.

Questions for authors
  1. The dependence of the sample sizes bgb_g and bHb_H on K⋆K_\star in Lines 242 and 250 seems counterintuitive. For fixed tolerances ϵ1\epsilon_1, ϵ2\epsilon_2, and δ\delta, the formulas appear to prescribe smaller sample sizes when fewer outer iterations are performed. Is this interpretation correct, and could you explain the reasoning behind this dependence?

  2. Does the update in Step 7 (Line 256) of Algorithm 1 guarantee convergence without a line-search strategy? Please clarify how the cubic regularization ensures sufficient descent.

  3. AI-use statement (Lines 461–470). The authors report using generative AI to “formulate mathematical claims” and “provide critical ingredients for proving mathematical claims,” and state that all content was verified. Although AI use is not itself a weakness, the statement should identify the specific claims or proof components developed with AI assistance and explain how they were verified.

Reviewer_VDQkOpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper proposes an algorithm for finding a second-order stationary point of an LL-smooth function, using a gradient oracle. The algorithm proposed runs in polynomial time in the initial suboptimality gap, dimension, and error. The algorithm is based on approximating first and second order information of a Gaussian-smoothed version of the objective function.

Critical strengths

-The paper is well-written and I found the exposition and mathematical writing polished and very clear.

-The paper studies a problem that is well-grounded in the non-convex optimization literature. The authors make a contribution to the field: showing that with only LL-smoothness but no a-priori bounds on the Hessian, it is possible to find a second order stationary point with runtime polynomial in all the relevant parameters. I do think it is a nice contribution that no assumptions on the Hessian are made.

Critical weaknesses

The main weakness of the paper is its positioning in the literature, and relatedly, the significance of the contribution. The paper misses referencing a large body of the related literature, namely, the literature on optimization without Lipschitz gradient or Hessian, which began with the well-known work [1]. Several recent papers have studied the same problem as this paper: [2] studied convergence of second order methods to second order stationary points without Lipschitz Hessian, while [3] studied convergence of first order methods to second order stationary points without Lipschitz Hessian. The algorithm of [2] runs in a dimension free number of iterations, while the algorithm of [3] runs in a number of iterations polylogarithmic in the dimension, although [2,3] both make certain regularity assumptions on the Hessian that this paper does not make, but that are satisfied by a wide range of applications. Therefore the main contribution of the present submission is eliminating the assumptions on the Hessian altogether, and proposing a slower algorithm in this setting. This set of related prior work should be referenced and compared to.

The algorithm also requires heavy matrix computations -- estimation of the Hessian in step 5 and solving a quadratic program in step 6 of the algorithm -- and step 6 cannot be implemented with just a matrix-vector oracle either. Step 6 seems to also be computationally difficult in the worst-case, as the quadratic program is not necessarily convex. See the algorithm's description on p. 5. This makes the algorithm less relevant for practical settings in ML; this is also a theoretical weakness in the non-convex optimization literature.

[1] Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaie. Why gradient clipping accelerates training: A theoretical justification for adaptivity. ICLR 2019.

[2] Chenghan Xie, Chenxi Li, Chuwen Zhang, Qi Deng, Dongdong Ge, and Yinyu Ye. Trust Region Methods For Nonconvex Stochastic Optimization Beyond Lipschitz Smoothness. AAAI 2024.

[3] Efficiently Escaping Saddle Points under Generalized Smoothness via Self-Bounding Regularity. Daniel Yiming Cao, August Y. Chen, Karthik Sridharan, Benjamin Tang. NeurIPS 2025.

Questions for authors

The algorithm, while technically requiring only a first order oracle, requires heavy matrix computations. Furthermore, step 6 of the algorithm seems to also be computationally difficult in the worst-case, as the quadratic program is not necessarily convex. Could the authors please clarify the computational complexity (given the gradient oracle) of their algorithm?

Reviewer_GfatOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
3(+1)
Presentation
2(+1)
Soundness
2
Read review
Paper summary

The paper studies Goldstein approximate second-order stationarity for functions with Lipschitz gradients whose Hessians need not exist everywhere. The main idea is to smooth the objective over a uniform ball and then apply cubic regularization using derivative estimates obtained from gradient evaluations. For a common tolerance $\varepsilon $, the method achieves a high-probability oracle complexity of $\tilde O(n^2/\varepsilon^9 + n^3/\varepsilon^7) $, with smoothness and initial-gap factors omitted here. The paper also proves that a weakly convex function and its Moreau envelope share the same Rockafellar second-order stationary points, and discusses extensions to bilevel optimization.

Critical strengths

Overall, the results are correct and there are no major errors or issues. The connection between uniform-ball smoothing and the Goldstein generalized Hessian is clear, and the main convergence argument appears technically sound. The equivalence of Rockafellar second-order stationarity between a weakly convex function and its Moreau envelope is also an interesting theoretical result.

Critical weaknesses

The first concern I have is that the motivation and the advance over prior work are not clearly explained. The introduction appeals to the benefits of classical second-order stationarity, but does not establish which of these benefits carry over to the weaker Goldstein condition which this work mainly study. The comparison with Lei et al. (2026) (lines 58–64) mainly lists differences in smoothing distributions and oracle models, without explaining what is gained in assumptions, guarantees, or complexity. Similarly, in Section 5.2, the authors emphasize weaker differentiability assumptions for bilevel optimization, while giving less attention to the change in stationarity target and the oracle access required. This makes the significance of the results difficult to assess to a non-expert in this specific area. I believe a direct comparison with the closest existing guarantees, together with a concrete example illustrating why the proposed stationarity notion is useful, would make the contribution much clearer.

Secondly, the paper would benefit from having proof sketches at least for the main results (the authors did mention some key ideas for Theorem 4.1). Key proof ideas can highlight the novelty or advance in techniques that the author contribute. Moreover, the theoretical results would benefit from a smoother transition which include, for example, how the two consecutive results are related or how the first one leads to the second one. One example is for Proposition 3.2 and Proposition 3.3. When discussing these estimators for the gradient and Hessian, it is unclear what is the new ideas or challenges that go into such a process. Appendix C.2 for the Hessian estimator involves some nontrivial work that can be highlighted in the main paper.

Questions for authors

Since Lei et al. (2026) already combine randomized smoothing with cubic regularization for the same stationarity target, what is the main theoretical advance of your result after accounting for the stronger gradient oracle? The comparison in lines 58–64 identifies methodological differences but leaves their significance unclear. Please compare the assumptions, probability guarantees, and total oracle complexity for the same $ (\varepsilon_1,\varepsilon_2, \delta) $ target, and explain which advantages come specifically from uniform-ball smoothing and which depend on having gradient access.

Reviewer_rEFfOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper presents an algorithm to compute Goldstein approximate second-order stationary points (SOSPs) of an LL-smooth function ff using only a gradient oracle for ff as follows

  • Define a uniform-ball smoothed version fσf_\sigma of the function ff.
  • Estimate the gradient and Hessian of fσf_\sigma at xx by sampling uniformly from a σ\sigma-radius ball around xx and a σ\sigma-radius sphere around xx respectively. The paper also presents concentration bounds for these estimates using the (vector and matrix) Bernstein inequalities.
  • Use these estimates with the cubic Newton method to find an approximate SOSP for fσf_\sigma
  • Show that an approximate SOSP for fσf_\sigma corresponds to a Goldstein approximate SOSP for ff. The algorithm, presented as Algorithm 1 in the paper, is shown to have oracle complexity of O~(L8n2/ε9+L6n3/ε7)\widetilde{O}({ L^8 n^2}/{\varepsilon^9}+{ L^6 n^3}/{\varepsilon^7}).

The paper then extends this method to weakly convex functions ff by applying the algorithm to its Moreau envelope fλf_\lambda which is smooth, and has the same global/local minimizers.

A similar extension is considered with bilevel optimization, in two case: where the lower level objective function ℓ\ell

  1. is strongly convex (corresponding to a smooth hyperobjective function under some regularity conditions),
  2. satisfies the PŁ inequality (corresponding to a weakly convex hyperobjective function under some regularity conditions),

which reduces to previously considered cases.

Critical strengths

The major strengths of the paper as I see it are the following:

  1. Characterization of SOSPs for weakly convex functions (Theorem 5.3, via Proposition F.1) using its Moreau envelope (with the caveat that most discussion is in the supplementary material; see additional note below).
  2. The high probability oracle complexity guarantee for Algorithm 1, enabled by the concentration bounds for the gradient and Hessian estimators.

However, the presentation of ideas in the main text does not emphasize these contributions strongly enough to make this paper a clear accept.

Critical weaknesses
  1. It is not clear from an initial reading of the paper which of the results are new work and which are established. For example, in Section 3, there is significant overlap with [1] and [2], which are not cited in this section (but are cited elsewhere in the paper and in the proofs in the Appendix)

    • Section 3.1: the twice differentiability of fσf_\sigma seems to already be established in [1] (albeit for Gaussian smoothing), and similarly the Lipschitz modulus for the Hessian in [2] (for uniform smoothing as in this work).
    • Section 3.2: the estimators seem to again be already studied in [1] and [2]
    • Similarly in Section 4, it is not clear how this analysis of the cubic Newton method with estimated gradient and Hessian sits in comparison to previously established results.
  2. Algorithm 1 requires, as an approximation O(L4n/ε5)O(L^4 n/\varepsilon^5) outer loop iterations, which is pretty large for modest nn and ε\varepsilon. Further, each step similarly requires a large number of calls to the gradient oracle to estimate the gradient and Hessian of fσf_\sigma. It is not clear to me whether this algorithm will be feasible in practice from the analysis presented, which makes it difficult to evaluate the practical significance and applicability of Algorithm 1.

  3. As an additional note, Section 5.1 which characterizes the SOSPs of weakly convex functions, is somewhat disconnected from the previous discussion (including the prerequisite definitions) and not developed enough in the main paper. In fact the majority of the paper is spent on the LL-smooth case, rather than demonstrating the reduction of non-smooth problems in Section 5 to the LL-smooth case, as may be expected from the title.


[1] Ming Lei, Ting Kei Pong, Man-Chung Yue, Liaoyuan Zeng, and Hao Zhang. A Gaussian smoothing-based zeroth-order method for Goldstein second-order stationarity. arXiv preprint arXiv:2607.21258, 2026

[2] Tianyi Lin, Zeyu Zheng, and Michael I Jordan. Gradient-free methods for deterministic and stochastic nonsmooth nonconvex optimization. In Proceedings of the 36th International Conference on Neural Information Processing Systems, pp. 26160–26175, 2022.

Questions for authors
  1. Is the extent of the new work in Section 3 limited to the concentration inequalities? Since the results are very similar to [1] and [2], I believe that they should be explicitly cited in this section in the main paper for comparison.

  2. As I understand, Algorithm 1 is the cubic Newton method on an LL-smooth objective using estimated gradient and Hessian. It is not clear to me where the analysis in this paper sits in relation to previous works.

    1. What are the known upper bounds for this problem?
    2. Are these new upper bounds tighter than previously known results?
    3. If previous results cannot be directly compared or used here, is it because they are only partially applicable to the current setting?
  3. Please address the issues raised above regarding the practical feasibility of Algorithm 1.

    1. If possible, a few numerical experiments would be useful to demonstrate convergence in reasonable number of outer loop steps and oracle calls per step.
    2. The constant cc (arising in the Lipschitz modulus of the Hessian ∇2fσ\nabla^2 f_\sigma) and the smoothness parameter LL of ff are used to estimate the number of outer loop steps, and also the number of oracle calls in each step. In the case that these constants are unknown, is there a heuristic to choose K⋆K_\star, bgb_g, and bHb_H to run the algorithm?
  4. The title mentions structured non-smooth, nonconvex programs, and these are considered in Section 5, but only as brief extensions of the main result which is for LL-smooth functions. The abstract also reflects this by relegating any mention of non-smooth objectives to a single sentence.

    1. I believe the abstract should be amended to clarify the structure exploited, and specifically mention that such problems are solved by reduction to LL-smooth objectives using the Moreau envelope.

    2. The main paper also does not describe in detail the non-smooth case, especially in regards to bilevel optimization where the reduction to a ρ\rho-weakly convex problem and then (or directly for the NC-SC case) to a LL-smooth problem are from previous results and only briefly discussed. It is not clear to me whether this extension alone justifies the title.

Other minor clarifications

  1. In Section 5, the notation fλf_\lambda is used for the Moreau envelope with parameter λ\lambda (presumably). This notation is not introduced (and the Moreau envelope is not defined in the main text) and is also easily confused with the notation fσf_\sigma for the uniform smoothed version of ff. This needs to be clarified in the main paper.

  2. In Proposition 5.4, I don't understand what z∈∂C2fλ(x)(w)z \in \partial^2_C f_\lambda(x)(w) means. Is this meant to be A∈∂C2fσ(x)A \in \partial^2_C f_\sigma(x) as in earlier definitions and z=Awz = Aw?

Some minor stylistic suggestions (not considered in the score)

  1. In some places, the notation zTxz^{\rm T} x is used for the inner product (of vectors in Rn\mathbb{R}^n), whereas in some places it is ⟨z,x⟩\langle z, x \rangle. Since the Appendix A: Notation specifically reserves the latter for the Frobenius inner product of matrices, it should preferably not be used for vectors.

  2. Many theorems and propositions are introduced as follows: “Let L,ε,…>0L, \varepsilon, \ldots > 0 be arbitrary and ff be LL-smooth” (or weakly convex etc.). Consider rewriting this to “Let ff be LL-smooth and ε,…>0\varepsilon, \ldots > 0 be arbitrary. This makes for a slightly smoother read.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.