- 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 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
-
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.
-
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
-
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.
-
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.
-
The complexity bound is steep. The and 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
-
The dependence of the sample sizes and on in Lines 242 and 250 seems counterintuitive. For fixed tolerances , , and , 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?
-
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.
-
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.