acceptodds
Under review as a conference paper at ICLR 2027

Fixed Dimension Matters: Tight Complexity and Computational Hardness for Higher-Order Smooth Nonconvex Stationarity

Abstract

We study approximate first-order stationarity for nonconvex functions whose derivatives of orders have prescribed Lipschitz constants , and whose initial function-value gap is at most . For every **fixed** dimension and fixed order , we establish a tight oracle bound of finding -stationary points with deterministic exact gradient-only oracles. We also show that, for every fixed finite and fixed , stationary-point search is PLS-complete for bounded functions with bounded derivatives through order and Lipschitz -th derivative.

Primary area:
optimization
Keywords:
Fixed dimension, High-order smoothness, Tight oracle complexity, Computational hardness

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_hXFKOpenReview ↗
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 dd 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 dd 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 (2q+1)d(2q+1)^d gradient queries per stencil where qq is the order of the Taylor model chosen by the algorithm. For fixed (d,p)(d,p), this is a constant as ε→0\varepsilon \to 0. If dd grows with 1/ε1/\varepsilon, 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 dd and instead pay exponential dependence on qq.
  • 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 dd for any p≥3p \ge 3. 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

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.

Weakness 1: The PLS-completeness result is not very interesting...

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≥3p\ge3. 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.

Weakness 2:...I believe... can avoid this exponential dependence on dd and instead pay exponential dependence on qq.

We have replaced the exponential tensor-product stencil with a total-degree construction in the revised manuscript. For q≥2q\ge2, it usesNd,q=(d+q−1q−1)N_{d,q}=\binom{d+q-1}{q-1}gradient values to reconstruct all tensors required by an order-qq model, which is polynomial in dd for each fixed qq. 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 CpupC_p^{\mathrm{up}} depends only on pp. In particular, the q=2q=2 choice gives O((d+1)[1+ΔL2ϵ−3/2])O((d+1)[1+\Delta\sqrt{L_2}\epsilon^{-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.

Weakness 3: For the reader... I would suggest the authors provide the basic notions... I would also add some missing related work...

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,pd,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,ΛpM_0,\ldots,M_p,\Lambda_p. On valid promised inputs, an output is a rational ϵ\epsilon-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:

  • Fearnley et al. (2022), The Complexity of Gradient Descent: CLS = PPAD ∩\cap PLS, for constrained KKT complexity and the relationship between these classes.
  • Kontogiannis, Panageas, and Pollatos (2026), The Computational Complexity of Avoiding Strict Saddle Points in Constrained Optimization, for constrained second-order stationarity, including fixed-dimensional hardness and the role of the chosen SOSP definition.
  • Fearnley et al. (2025), The Complexity of Computing KKT Solutions of Quadratic Programs, for CLS-completeness of box-constrained quadratic KKT search when dimension is part of the input.

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 f:Rd→Rf:\mathbb R^d\to\mathbb R and ϵ>0\epsilon>0, a point xx is an ϵ\epsilon-approximate first-order stationary point, or ϵ\epsilon-FOSP, if

∣∇f(x)∣2≤ϵ.\\|\nabla f(x)\\|_2\le\epsilon.

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.

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

The paper studies the deterministic gradient-only oracle complexity of finding ϵ\epsilon-stationary points of nonconvex functions on Rd\mathbb{R}^d whose derivatives of orders 1,…,p1,\ldots,p satisfy simultaneous Lipschitz conditions, with constants L1,…,LpL_1,\ldots,L_p and initial optimality gap Δ\Delta.

The paper establishes two main results.

First, for fixed dimension dd and smoothness order pp, it characterizes the gradient-only oracle complexity as Θd,p(Rϵ)\Theta_{d,p}(R_\epsilon), above a constant threshold, where

L_q^{1/q}\epsilon^{-(q+1)/q}.$$ For fixed positive smoothness parameters, this yields the tight rate $\Theta(\epsilon^{-(p+1)/p})$. The upper bound combines finite-difference reconstruction of higher-order derivative tensors with regularized Taylor models. The matching lower bound uses a one-dimensional resisting-oracle construction based on smooth plateaus, and applies to arbitrary deterministic gradient-query algorithms, including those that output unqueried points. Second, the paper establishes PLS-completeness of a totalized white-box stationary-point problem with higher-order smoothness promises for every fixed $p\geq 1$ and $d\geq 2$. The proof extends the hard family of Hollender and Zampetakis (2025) through polynomial-kernel smoothing while preserving stationary-point decoding and efficient exact rational evaluation. The cases $p=1,2$ were previously known. The contributions are theoretical, with complete proofs provided in the appendix.
Critical strengths

1. Tight characterization across simultaneous smoothness parameters.

The upper and lower bounds match not only in their dependence on ϵ\epsilon, but also uniformly across the initial gap and all smoothness constants. Both are governed by the intrinsic length scale

(\epsilon/L_q)^{1/q}.$$ Each nonterminal regularized step guarantees objective decrease proportional to $\epsilon\rho_\epsilon$, while the lower-bound construction incurs at most a comparable gap cost per covered query. This provides a coherent explanation for the optimal exponent $(p+1)/p$ and is a meaningful theoretical contribution. **2. General lower bound for unrestricted deterministic algorithms.** The lower bound applies to arbitrary deterministic gradient-query algorithms, without restrictions on query locations or requiring the output to be previously queried. This extends the first-order construction of Chewi et al. (2023) to arbitrary fixed higher-order smoothness, while going beyond the algorithm-specific higher-order examples of Cartis et al. (2020). The use of support measure rather than support diameter to control the initial gap is particularly useful, since it allows the construction to accommodate arbitrarily distant queries without increasing the gap proportionally to their separation.
Critical weaknesses

1. The dependence on dimension remains largely unresolved.

Although the paper establishes a tight complexity characterization for every fixed dimension, it does not quantify the dependence on dd beyond constants in the upper bound. The proposed finite-difference construction uses (2q+1)d(2q+1)^d gradient evaluations per iteration, while the lower bound is independent of dimension.

This exponential stencil size appears unnecessarily large. For example, when p=2p=2, a Hessian approximation can be constructed using d+1d+1 gradient evaluations through coordinate-wise finite differences. With a sufficiently small finite-difference radius, this suggests a dimension-dependent oracle upper bound of order

\epsilon^{-3/2}\right]\right).$$ More generally, total-degree interpolation suggests the possibility of reconstructing higher-order derivative tensors using a number of gradient queries polynomial in $d$ for fixed $p$. Such a refinement would strengthen the interpretation of the results by quantifying the tradeoff between dimension and accuracy. In particular, it could clarify the regimes in which higher-order gradient-only methods outperform existing dimension-independent upper bounds. The absence of this analysis limits the conclusions that can be drawn about dimension dependence beyond the fixed-dimensional asymptotic regime. **2. The contribution builds substantially on existing techniques, limiting its broader novelty.** The normalized upper-bound exponent is already implied by the objective-function-free regularization framework of Gratton et al. (2025), combined with fixed-dimensional finite-difference approximations. The main oracle novelty is therefore the matching unrestricted lower bound and the uniform characterization of the smoothness parameters. While this lower bound is valuable, its construction closely follows the resisting-oracle approach of Chewi et al. (2023), extended through a smooth plateau satisfying higher-order derivative constraints. Similarly, the PLS-completeness result for $p\geq 3$ extends existing hardness constructions through polynomial-kernel smoothing. The preservation of exact rational evaluation and stationary-point decoding requires technical care, but the reduction does not appear to introduce a fundamentally new computational hardness mechanism. Overall, I view the results as mathematically clean and technically sound, but somewhat incremental relative to the existing higher-order regularization, oracle lower-bound, and PLS-hardness literature. As the authors acknowledge in Remark 3.2, the reliance on exact gradient information and uncharged internal model minimization also limits the immediate algorithmic implications.
Questions for authors
  1. Dimension-dependent oracle complexity. Could the exponential tensor-product stencil be replaced by a total-degree construction whose query complexity is polynomial in dd for fixed pp? In particular, does the p=2p=2 case admit an O(dϵ−3/2)O(d\epsilon^{-3/2}) bound under normalized parameters using coordinate-wise Hessian reconstruction? Can the authors obtain an explicit dimension-dependent bound or identify a lower bound demonstrating necessary dependence on dd?

  2. Novelty and scope of the computational hardness extension. For p≥3p\geq 3, what is the main technical or conceptual difficulty beyond polynomial-kernel smoothing and preservation of exact rational evaluation? Additionally, Remark D.11 shows that normalizing all analytic bounds requires rescaling the target accuracy by an instance-dependent factor QIQ_I. Is this loss necessary for the reduction, or could hardness be established at fixed positive accuracy with normalized smoothness bounds? Clarifying this distinction would help assess the strength of the result.

  3. Comparison with value-and-gradient complexity. Table 1 includes both fixed-dimensional and growing-dimensional results under different oracle and function-class assumptions. What is known about the complexity of fixed-dimensional value-and-gradient methods under the same simultaneous higher-order smoothness and initial-gap assumptions considered here? A more direct comparison would clarify to what extent the claimed continuing benefit of higher-order smoothness is specific to the gradient-only oracle model.

5 comments

We thank the reviewer for the detailed assessment. The suggested dimension-dependent refinement has led to an improved upper bound in the revised manuscript. We have also clarified the technical contributions, normalization, and comparison between the two oracle models. Blue text in the revised manuscript marks newly added or revised content.

Weakness 1 and Question 1: The dependence on dimension remains largely unresolved...Could the exponential tensor-product stencil be replaced by a total-degree construction whose query complexity is polynomial in dd for fixed pp...

We have replaced the exponential tensor-product stencil with a total-degree construction, and the suggested Hessian-Lipschitz improvement now appears explicitly in the paper.

Proposition 3.3 now givesT_{d,p}^{\nabla}(\epsilon;\Delta,L_1,\ldots,L_p)\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\\},\qquad N_{d,q}=\binom{d+q-1}{q-1},where CpupC_p^{\mathrm{up}} depends only on pp.

For q≥2q\ge2, the revised Algorithm 2 reconstructs all tensors needed by an order-qq model from gradients on the simplex lattice Z_{d,q}=\left\\{z\in\mathbb N_0^d:\sum_{j=1}^d z_j\le q-1\right\\}. Polynomial reproduction and symmetrization give the error bound∣Gr−Drf(x)∣op≤Aqd(r−1)/2Lqhq−r+1,2≤r≤q,\\|G_r-D^rf(x)\\|_{\mathrm{op}}\le A_qd^{(r-1)/2}L_qh^{q-r+1},\qquad 2\le r\le q,with AqA_q independent of dd. Choosingh=νqd−(q−1)/2(ϵLq)1/q,h=\nu_qd^{-(q-1)/2}\left(\frac{\epsilon}{L_q}\right)^{1/q},where νq\nu_q depends only on qq, makes the descent constants independent of dimension. The smaller radius carries no additional query cost in the exact-gradient model.

For q=2q=2, this reduces to coordinatewise Hessian reconstruction and symmetrization, using d+1d+1 gradient values. The explicit specialization in Appendix C.1 yields T≤1+(d+1)[1+96ΔL2ϵ−3/2].T\le 1+(d+1)\left[1+96\Delta\sqrt{L_2}\epsilon^{-3/2}\right]. Thus the proposed O(dϵ−3/2)O(d\epsilon^{-3/2}) guarantee holds under normalized parameters. More generally, for fixed 2≤q≤p2\le q\le p, the leading cost is Oq(dq−1ϵ−(q+1)/q)O_q(d^{q-1}\epsilon^{-(q+1)/q}), improving on the gradient-descent guarantee when d=o(ϵ−1/q)d=o(\epsilon^{-1/q}).

Algorithms 1–2 have been updated accordingly: the order choice includes the stencil cost, and endpoint gradients are reused. Appendix B gives the reconstruction, and Lemmas C.3–C.4 in Appendix C.1 establish the error and descent bounds.

Weakness 2: The contribution builds substantially on existing techniques, limiting its broader novelty.

Thank you for this comment. Extending existing techniques to our setting requires overcoming nontrivial technical obstacles. We have revised the exposition to make these challenges explicit for each result and explain the technical innovations in our constructions that resolve them.

1. Higher-order lower bound: exact replies with simultaneous derivative and gap control.

The difficulty is to preserve exact constant replies while enforcing every derivative-Lipschitz budget and the initial gap. Mollification can perturb the replies, while summing bumps can introduce query-count-dependent factors through overlaps.

Lemma C.5 resolves this using a union-indicator convolution. The plateau equals one at every prescribed point, has derivative bounds Kpρ−qK_p\rho^{-q} independent of the query count and geometry, and has support measure at most Kp(∣S∣+1)ρK_p(|S|+1)\rho. With ρ=Cp∗ρϵ\rho=C_p^*\rho_\epsilon and f′=2ϵϕf'=2\epsilon\phi, all smoothness budgets hold simultaneously with gap Op((∣S∣+1)ϵρϵ)O_p((|S|+1)\epsilon\rho_\epsilon). This combination of exact interpolation, uniform derivative control, and linear gap cost yields the unrestricted lower bound.

2. Upper bound: parameter-uniform control of gradient-reconstructed models.

Building on objective-function-free regularization, our analysis controls reconstruction errors using LqL_q alone and establishes constants uniform over the other smoothness budgets.

The obstacle is that a tensor error δr\delta_r contributes δr∣s∣r\delta_r\\|s\\|^r, which can dominate the regularization term Lq∣s∣q+1L_q\\|s\\|^{q+1} for small steps. Lemmas C.3–C.4 useτq=(ϵ/Lq)1/q,h=νqd−(q−1)/2τq,δr=βqLqτqq−r+1,\tau_q=(\epsilon/L_q)^{1/q},\qquad h=\nu_qd^{-(q-1)/2}\tau_q,\qquad \delta_r=\beta_qL_q\tau_q^{q-r+1},where νq\nu_q and βq\beta_q depend only on qq. The endpoint-gradient estimate guarantees either ϵ\epsilon-stationarity or ∣s∣>τq/2\\|s\\|>\tau_q/2; in the latter case, all reconstruction errors are absorbed into a decrease of order ϵτq\epsilon\tau_q. Optimizing the query bound over the order, including stencil size, yields Proposition 3.3 and the fixed-dimensional minimax rate.

3. PLS-hardness: higher regularity with global decoding and exact evaluation.

Smoothing must preserve decoding for every accepted output, including points near cell boundaries and periodic seams, while retaining exact polynomial-time rational evaluation.

Our polynomial kernel combines sufficient boundary vanishing with rational coefficients. Its radius guarantees a uniform gradient perturbation below the decoding margin and restricts each convolution to at most four source cells, enabling exact rational integration. Differentiating the kernel supplies the global derivative bounds with polynomial-length encodings. Lemmas D.4–D.8 establish these requirements together.

The revised Introduction and Sections 3.1–3.2 highlight these mechanisms; the proof sketch of Theorem 4.2 and Lemmas D.4–D.8 provide the corresponding hardness argument.

Part 1 of Question 2: For p≥3p\ge 3, what is the main technical or conceptual difficulty beyond polynomial-kernel smoothing and preservation of exact rational evaluation?

The main difficulty is preserving the decoding guarantee for every accepted output while enforcing stronger regularity. Every approximate stationary point of the smoothed objective must still decode to a source solution, including points near cell boundaries and periodic seams. The smoothing radius must reconcile these requirements: shrinking it reduces gradient perturbation but increases higher-derivative bounds as inverse powers of the radius. Lemmas D.5–D.7 address this jointly. The uniform estimate ∣∇GI−∇FI∣∞≤ϵ0/4\\|\nabla G_I-\nabla F_I\\|_\infty\le\epsilon_0/4 ensures that every ϵ0/4\epsilon_0/4-FOSP of GIG_I lies within the source decoder’s threshold, while a common rational bound QIQ_I certifies all required analytic bounds with polynomial encoding length.

Part 2 of Question 2: Is the normalization loss necessary, or could hardness be established at fixed positive accuracy with normalized smoothness bounds?

Yes. Under simultaneous normalization of all analytic bounds, some instance-dependent accuracy loss is necessary unless every problem in PLS admits a polynomial-time algorithm. Here, normalization includes the function-value bound, as in Remark D.11.

Indeed, when ∣f∣∞≤1\\|f\\|_\infty\le1 and Lip⁡(∇f)≤1\operatorname{Lip}(\nabla f)\le1, gradient descent finds an ϵ\epsilon-FOSP in O(ϵ−2)O(\epsilon^{-2}) steps. For fixed positive ϵ\epsilon, this is a constant number of steps relative to the input length. Proposition D.12 in revised manuscript now establishes a polynomial bit-time implementation under our representation and output-encoding conventions. Consequently, PLS-hardness with both normalized bounds and fixed positive accuracy would yield polynomial-time algorithms for every PLS problem.

Our reduction therefore retains instance dependence in either the analytic bounds or the accuracy. It establishes hardness at fixed accuracy ϵ0/4\epsilon_0/4 with instance-dependent bounds. Normalizing G~I=GI/QI\widetilde G_I=G_I/Q_I preserves the original acceptance threshold through

\le\frac{\epsilon_0}{4Q_I} \quad\Longleftrightarrow\quad \\|\nabla G_I(x)\\|\le\frac{\epsilon_0}{4}.$$ Thus, the accuracy loss cannot be eliminated altogether in this simultaneously normalized regime without the polynomial-time consequence above. If only smoothness constants are normalized while the function-value or initial-gap bound may grow with the instance, this obstruction does not apply. > **Question 3**: What is known about the complexity of fixed-dimensional value-and-gradient methods under the same simultaneous higher-order smoothness and initial-gap assumptions considered here? In the revised manuscript, we have incorporated this comparison into **Table 1**, with the scope of the related results discussed in **Appendix A**. All entries concern deterministic exact-oracle algorithms for finding an $\epsilon$-FOSP on $\mathcal F_{1:p}(\Delta,L_1,\ldots,L_p)$, with fixed $d$, $p$, and all positive smoothness and initial-gap budgets fixed as $\epsilon\downarrow0$. Here, $\Theta$ denotes matching upper and lower bounds, whereas $O$ reports an upper bound only. | Dimension | Smoothness order | Gradient-only guarantee | Value-and-gradient guarantee | |---|---|---|---| | $d=1$ | $p=1$ | $\Theta(\epsilon^{-2})$ [1] | $\Theta(\log(1/\epsilon))$ [1] | | $d=1$ | $p\ge2$ | $\Theta(\epsilon^{-(p+1)/p})$ — Theorem 3.1 | $O(\log(1/\epsilon))$ [1] | | $d=2$ | $p=1$ | $\Theta(\epsilon^{-2})$ [1] | $\Theta(\epsilon^{-1})$ [2] | | $d=2$ | $p=2$ | $\Theta(\epsilon^{-3/2})$ — Theorem 3.1 | $\Theta(\epsilon^{-1})$ — upper: [2]; lower: [3] | | $d=2$ | $p\ge3$ | $\Theta(\epsilon^{-(p+1)/p})$ — Theorem 3.1 | $O(\epsilon^{-1})$ [2] | | Fixed $d\ge3$ | $p\ge1$ | $\Theta(\epsilon^{-(p+1)/p})$ — Theorem 3.1 | $O(\epsilon^{-(p+1)/p})$ — Proposition 3.3 | For $d=2,p=2$, the lower bound is the direct FOSP argument in Appendix F of [3], before its second-order corollary. The final value-and-gradient entry follows from **Proposition 3.3** by running the gradient-only algorithm and ignoring function values. In two dimensions, the optimal value-and-gradient exponent remains $1$ from $p=1$ to $p=2$, whereas the optimal gradient-only exponent improves from $2$ to $3/2$. Our theorem establishes continuing improvement of the tight gradient-only rate for every fixed smoothness order. The entries marked $O$ leave open whether further smoothness improves the optimal value-and-gradient rate. **References** [1] Sinho Chewi, Sébastien Bubeck, and Adil Salim. On the Complexity of Finding Stationary Points of Smooth Functions in One Dimension. ALT 2023. [2] Alexandros Hollender and Manolis Zampetakis. The Computational Complexity of Finding Stationary Points in Non-Convex Optimization. Mathematical Programming 2025. [3] Andreas Kontogiannis, Vasilis Pollatos, Sotiris Kanellopoulos, Panayotis Mertikopoulos, Aris Pagourtzis, and Ioannis Panageas. The Computational Complexity of Finding Second-Order Stationary Points. ICML 2024.
Reviewer_687EOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies nonconvex optimization with higher-order smoothness, aiming to find first-order stationarity using deterministic exact gradient-only queries in fixed dimension. Under fixed dimension, they derived a tight oracle bound of Θ(ϵ−(p+1)/p)\Theta(\epsilon^{-(p+1)/p}) to find ϵ\epsilon-stationary point. Also the paper extends PLS-completeness of stationary-point search to bounded functions of every fixed finite smoothness order in dimensions at least two.

Critical strengths
  1. Matching lower bound under all smoothness budgets simultaneously for nonconvex optimization.
  2. The computational hardness results extends existing result to every fixed finite order.
Critical weaknesses
  1. Your algorithm Line 19 requires to solve a subproblem exactly, but the model (in Line 18) itself may be nonconvex, also I may regard Line 19 as another nontrivial oracle in algorithm design. Although this is permitted under the oracle complexity model, it limits the computational interpretation of the upper bound. So I am concerned that the algorithm class definition in lower and upper bound study here should be clarified.
Questions for authors
  1. The lower bound construction generalizes the one-dimensional constant-reply mechanism of Chewi et al. (2023). Could the authors clarify the main technical challenges in extending this construction to higher-order smoothness?
3 comments

We thank the reviewer for the constructive feedback. We have clarified the computational model and highlighted the main technical requirements of the higher-order lower-bound construction. Blue text in the revised manuscript marks newly added or revised content.

Weakness 1: Your algorithm Line 19 requires to solve a subproblem exactly, but the model (in Line 18) itself may be nonconvex, also I may regard Line 19 as another nontrivial oracle in algorithm design. Although this is permitted under the oracle complexity model, it limits the computational interpretation of the upper bound. So I am concerned that the algorithm class definition in lower and upper bound study here should be clarified.

In the revised manuscript, we have clarified the following three points in Section 2 and Remark 3.2:

  1. The upper and lower bounds use the same algorithm class: deterministic gradient-only algorithms with arbitrary exact internal computation at no query cost. The lower bound applies to this entire class, including our upper-bound algorithm.
  2. Exact model minimization is potentially difficult internal computation. The model is determined entirely by queried gradients and known parameters, so minimizing it supplies no additional information about the unknown objective.
  3. The upper bound counts gradient queries. It does not bound the cost of solving the nonconvex subproblem or establish a polynomial-time implementation.

Question 1: The lower bound construction generalizes the one-dimensional constant-reply mechanism of Chewi et al. (2023). Could the authors clarify the main technical challenges in extending this construction to higher-order smoothness?

The main challenge is to preserve exact constant replies while controlling all derivative-Lipschitz bounds and the initial gap simultaneously. Direct mollification can perturb the prescribed replies, whereas summing local bumps can introduce overlap-dependent derivative bounds.

Lemma C.5 instead convolves the indicator of a union of neighborhoods of the prescribed points SS, including any unqueried output. The resulting plateau satisfies

\\|\phi^{(q)}\\|_\infty\le K_p\rho^{-q}\quad(1\le q\le p),\qquad \operatorname{Leb}(\operatorname{supp}\phi)\le K_p(|S|+1)\rho.$$ Choosing $\rho=\rho_{\epsilon}^{\star}=C_p^{\star}\rho_\epsilon$, where $\rho_{\epsilon}=\max_{1\le q\le p}(\epsilon/L_q)^{1/q}$, and setting $f'=2\epsilon\phi$ enforce all smoothness constraints with gap $O_p((|S|+1)\epsilon\rho_\epsilon)$. **The derivative bounds remain independent of the query count and geometry, while the gap cost grows only linearly with the count.** We now highlight this mechanism in **Section 3.2**, with the complete argument in **Appendix C.2**.

My concerns are resolved, and I will keep my score, thank you very much.

Thank you for your positive feedback. We are sincerely grateful for the time and effort you dedicated to this discussion.

Comments on the paper

1 comment
Area_Chair_JeVfOpenReview ↗

Reviewers: please read and comment on author's feedback, and consider editing your rating.

Dear Reviewers,

The authors have replied to your reviews. Does the author solve your concerns? Please respond to the author and consider editing your rating. The author-reviewer discussion phase will end on November 18 at 11:59pm AoE. Thanks.

AC

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.