- Rating
- 3
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
No use of LLM was used for this review.
Critical strengths
- The query lower bound is the most novel result of the paper.
- The technique used in the PLS-hardness result can be of independent interest. The authors' analysis can be seen as an alternative (and generalized) proof of the PLS-hardness result of Kontogiannis et al. (2024) for the HESSIAN-FOSP problem. The authors show a polynomial-time computable kernel extension extension of the function used in the original hard instance of Hollender & Zampetakis (2023) up to p-th order of smoothness. This way, the authors provide an interesting bound (Lemma D.6) on the error coming from this extension for any x and use this technique to bypass the need of "reproving" that the Groups 1-4 used in Hollender & Zampetakis (2023) still do not create any FOSPs under higher-order smoothness.
- The dimension does not need to be constant for PLS-membership, since the paper uses exactly the same membership grid reduction from Hollender & Zampetakis (2023). So, the authors' initial claim about constant is an understatement.
Critical weaknesses
- The PLS-completeness result is not very interesting. The membership is essentially for free from Hollender & Zampetakis. The hardness uses this extension trick to ensure that the interpolated function of Hollender & Zampetakis becomes p-th smoothness without creating spurious FOSPs in locations away from the ITER solutions. However, the fundamental complexity question regarding FOSPs has already been settled by Hollender & Zampetakis, and Fearnley et al (2022) for the KKT problem.
- The upper-bound implementation uses gradient queries per stencil where is the order of the Taylor model chosen by the algorithm. For fixed , this is a constant as . If grows with , that factor can substantially change the overall complexity. So, it queries $(2q+1)^d$ gradient values per iteration. However, I believe that the authors can avoid this exponential dependence on and instead pay exponential dependence on .
- For the reader who is not familiar with the white-box model, I think that the computational complexity part of paper is difficult to follow. I would suggest the authors provide the basic notions of complexity theory (Turing machines, TFNP, PLS) in the preliminaries and provide the formal white box definition of their problem of interest. I would also add some missing related work regarding the computational complexity of stationary points; see [1] - [3].
[1] Fearnley, John, et al. "The complexity of gradient descent: CLS= PPAD∩ PLS." Journal of the ACM 70.1 (2022): 1-74.
[2] Kontogiannis, Andreas, Ioannis Panageas, and Vasilis Pollatos. "The Computational Complexity of Avoiding Strict Saddle Points in Constrained Optimization." arXiv preprint arXiv:2604.02285 (2026).
[3] Fearnley, John, et al. "The complexity of computing KKT solutions of quadratic programs." Journal of the ACM 72.5 (2025): 1-48.
Questions for authors
- I believe that the technique used for extending the function to higher-order smoothness in the PLS-hardness proof would be very useful to show PLS-hardness for higher-order stationary points (e.g., 3rd-order) in unconstrained optimization. In fact, hardness is already proved by this paper and only membership remains unproved; however, I think it would be possible to show PLS membership for constant for any . Have the authors looked at the computational complexity beyond FOSPs? In any case, I would suggest adding such directions to their conclusion as related open questions.
- I would also suggest the authors add the formal definition of approximate FOSP (i.e., the solution concept that this paper studies) in the preliminaries.
4 comments
Part II
Question 1: I believe... show PLS-hardness for higher-order stationary points (e.g., 3rd-order) in unconstrained optimization... I would suggest adding such directions to their conclusion as related open questions.
Yes. We have looked at computational complexity beyond FOSPs, including the PLS-completeness of approximate second-order stationarity in unconstrained optimization established by Kontogiannis et al. (2024), cited in our original manuscript.
Following your suggestion, Section 5 in the revised manuscript now highlights approximate third- and higher-order stationarity in fixed dimension as a further direction, particularly the PLS-membership question. The discussion identifies the need to specify the stronger stationarity criterion and construct a corresponding finite local-search formulation.
Question 2: I would also suggest the authors add the formal definition of approximate FOSP...
We have added the definition explicitly near the beginning of Section 2: for differentiable and , a point is an -approximate first-order stationary point, or -FOSP, if
I would like to thank the authors for their response. I have decided to maintain my positive rating.
Thank you for your positive assessment. We sincerely appreciate the time and effort you have devoted to this discussion.
Part I
We thank the reviewer for the constructive suggestions. We have clarified the scope of the hardness result, improved the dimension-dependent upper bound, and expanded the computational-complexity preliminaries and related-work discussion. Blue text in the revised manuscript marks newly added or revised content.
Thank you for this comment. We build on Hollender and Zampetakis’s classification, and PLS membership is inherited from their finite local-search construction. The Hessian-Lipschitz case is also covered by Kontogiannis et al. (2024).
The additional result concerns hardness under arbitrary prescribed finite smoothness order, including p≥3. Hardness for a function class does not automatically extend to its smoother subclasses. Our construction provides globally bounded derivatives and a Lipschitz highest derivative while preserving exact polynomial-time rational evaluation and the decodability of every approximate stationary point.
Remark 4.3 explicitly identifies the known cases and the scope of this extension. The revised Section 1.2 further clarifies the relationship to the constrained KKT/CLS classification of Fearnley et al. This extension complements the oracle result: higher smoothness improves gradient-query complexity, while computational hardness persists in the stated finite-description model.
We have replaced the exponential tensor-product stencil with a total-degree construction in the revised manuscript. For q≥2, it usesNd,q=(q−1d+q−1)gradient values to reconstruct all tensors required by an order-q model, which is polynomial in d for each fixed q. Proposition 3.3 now statesT_{d,p}^{\nabla}\le C_p^{\mathrm{up}}\min_{1\le q\le p}\left\\{N_{d,q}\left[1+\Delta L_q^{1/q}\epsilon^{-(q+1)/q}\right]\right\\},where Cpup depends only on p. In particular, the q=2 choice gives O((d+1)[1+ΔL2ϵ−3/2]) gradient queries.
Algorithms 1–2 have been updated: the order choice includes the stencil cost, and endpoint gradients are reused. In the revised manuscript, Appendix B gives the construction; Lemmas C.3–C.4 in Appendix C.1 prove the reconstruction and descent estimates with constants independent of dimension.
In the revised manuscript, we have expanded Section 2 and added an explanation of the representation and total-search convention at the beginning of Section 4, immediately before Definition 4.1.
Representation and running time. The preliminaries now explain finitely described Turing machines, binary encodings, and bit-operation complexity. At rational query points, the value evaluator returns an exact rational and the gradient evaluator returns a vector of exact rationals. For fixed d,p, a fixed polynomial in the description and query lengths uniformly bounds evaluator time and output length; clocks enforce this bound. This is distinguished from the oracle model, which charges only gradient queries.
TFNP and PLS. We now explain that TFNP comprises total search problems with polynomially bounded, polynomial-time-verifiable solutions. PLS formalizes finite local search with polynomial-time initialization, potential evaluation, and an improving-neighbor or local-optimality routine; the number of successive improvements need not be polynomial.
Formal input and output. Definition 4.1 specifies the evaluator descriptions, binary-encoded accuracy, and analytic-bound declarations M0,…,Mp,Λp. On valid promised inputs, an output is a rational ϵ-FOSP satisfying the inherited polynomial encoding-length bound. On arbitrary inputs, the problem retains the full base solution relation, including its accepted violation certificates. Higher smoothness is a semantic promise on the hard subclass, so the verifier need not decide higher differentiability of arbitrary machine descriptions.
Related work. Section 1.2 now discusses all three recommended references: