June 03, 2026
We study the deterministic first-order oracle complexity of finding \(\epsilon\)-stationary points in smooth nonconvex optimization when the objective satisfies higher-order smoothness assumptions. While the classical \(\epsilon^{-2}\) rate is optimal under only Lipschitz gradients, higher-order smoothness leads to accelerated first-order upper bounds, most notably the \(\epsilon^{-7/4}\) rate under Lipschitz Hessians and the \(\epsilon^{-5/3}\) rate under Lipschitz third derivatives. The matching lower bounds, however, have remained open. We resolve this gap by proving a new dimension-free first-order lower bound for higher-order smooth nonconvex functions, valid for every finite smoothness order. In particular, our construction gives a matching \(\Omega(\epsilon^{-7/4})\) lower bound in the Hessian-Lipschitz case and a matching \(\Omega(\epsilon^{-5/3})\) lower bound in the third-order-smooth regime. The hard instance is based on a block-chain mechanism that enforces blockwise oracle revelation while preserving the smoothness structure needed for the scalar hard instance. The lower-bound construction was discovered with the assistance of ChatGPT 5.5 Pro and subsequently verified by the authors.
Finding approximate stationary points is one of the basic tasks in smooth nonconvex optimization. Given a differentiable objective \(f\), the goal is to find a point \(x\) with \[\begin{align} \|\nabla f(x)\|\le\epsilon.\notag \end{align}\] We focus on first-order methods, which only query function values and gradients, because they are the most widely used methods in large-scale nonconvex optimization. For functions with \(L_1\)-Lipschitz gradients and initial gap \(\Delta\), gradient descent finds such a point in \(O(\Delta L_1\epsilon^{-2})\) first-order oracle calls. This rate is worst-case optimal under only gradient Lipschitzness, so in the general smooth function class there is no room for acceleration beyond the classical \(\epsilon^{-2}\) dependence.
| \(p=1\) | \(p=2\) | \(p\ge3\) | |
|---|---|---|---|
| Upper bound | |||
| (gradient descent) | |||
| [1]–[7] | |||
| [5] | |||
| 1-4 Lower bound | |||
| [8] | |||
| [9] | |||
| [9] | |||
| 1-4 Our result | |||
| (Theorem 1) | |||
| (Theorem 1) |
A natural way to seek faster rates is to impose higher-order smoothness on the objective. The first and most important case is second-order smoothness, namely Lipschitz continuity of the Hessian: it is the weakest standard assumption beyond gradient Lipschitzness that controls how curvature changes, and it gives algorithms enough structure to distinguish convex-like regions from genuinely nonconvex ones. Algorithmic evidence for acceleration under this assumption comes from several related oracle models and target guarantees. One line of work uses Hessian-vector products to obtain curvature-aware guarantees, often with the stronger goal of finding approximate local minima. For example, [1] approximately solve cubic-regularized subproblems and find approximate local minima within \(O(\epsilon^{-7/4})\) Hessian-vector-product complexity. In a related Hessian-vector-product-based accelerated framework, [2] obtain \(O(\epsilon^{-7/4})\) complexity for finding first-order stationary points. Within the first-order saddle-escaping literature, accelerated and negative-curvature-based gradient methods yield \(O(\epsilon^{-7/4})\) complexity bounds in the Hessian-Lipschitz setting [3], [4].
The line closest to our setting keeps both the oracle and the target purely first-order. The accelerated “convex until proven guilty” framework of [5] runs accelerated gradient in regions that behave convexly and uses failure of convexity as a certificate for progress in the nonconvex landscape, giving \(O(\epsilon^{-7/4}\log(1/\epsilon))\) first-order complexity under Lipschitz Hessians and \(O(\epsilon^{-5/3}\log(1/\epsilon))\) under Lipschitz third derivatives. Subsequent work refined this picture in two directions: restarted accelerated gradient removes the logarithmic factor in the Hessian-Lipschitz case [6], while parameter-free accelerated methods recover the \(O(\epsilon^{-7/4})\) complexity without requiring the same smoothness-parameter tuning [7]. [10] give a gradient-only quasi-Newton method with \(O(d^{1/4}\epsilon^{-13/8})\) complexity, improving the \(\epsilon\)-dependence in low dimension but with explicit dimension dependence rather than a dimension-free guarantee. Thus higher-order smoothness does allow acceleration beyond \(\epsilon^{-2}\), even when the algorithm only observes function values and gradients. The absence of matching dimension-free lower bounds has been explicitly noted in later work that sharpened or reinterpreted the upper-bound landscape: even after the logarithmic factor was removed, and even after online-learning viewpoints recovered parts of the upper-bound picture, the dimension-free deterministic first-order lower bound remained unchanged [6], [11].
Despite these upper-bound developments, whether the accelerated rates were optimal remained unclear. On the lower-bound side, the best previous result is due to [9], who proved an \(\Omega(\epsilon^{-12/7})\) lower bound in the Hessian-Lipschitz setting and an \(\Omega(\epsilon^{-8/5})\) lower bound for arbitrarily smooth functions. This left an exponent gap of \(1/28\) in the Hessian-Lipschitz case, between \(12/7\) and \(7/4\), and an exponent gap of \(1/15\) relative to the \(5/3\) first-order rate under Lipschitz third derivatives. Whether these gaps reflected a limitation of the known lower-bound constructions or a genuine separation has remained a long-standing open problem. This motivates the following question.
What is the optimal first-order oracle complexity of finding \(\epsilon\)-stationary points when higher-order smoothness is available?
In this work, we answer this question by proving a new lower bound, which resolves a long-standing open gap in deterministic first-order oracle complexity. Our contributions are as follows.
As summarized in Table 1, we give a new dimension-free first-order lower-bound construction for higher-order smooth nonconvex functions, valid for every finite smoothness order \(p\). In the Hessian-Lipschitz case, the construction gives the matching \(\Omega(\epsilon^{-7/4})\) dependence, closing the gap between the previous \(\epsilon^{-12/7}\) lower bound and the best known first-order upper bound. Under Lipschitz third derivatives, it gives the matching \(\Omega(\epsilon^{-5/3})\) dependence in the third-order-smooth regime. The full theorem tracks the dependence on \(\Delta\), \(L_1,\ldots,L_p\), and the active smoothness constraints.
Technically, we introduce a block-chain hard instance that augments the scalar transition problem with a linear operator for observation. The nonconvex potential is applied after a linear readout, whose operator norm provides an additional knob for calibrating higher-order smoothness while preserving the scalar residual certificate. To keep this pullback compatible with first-order revelation, each scalar coordinate is replaced by a chain block: the previous scalar state enters through an entry coordinate, whereas the current scalar state is read through a suffix projection. This separation lets a zero-respecting method reveal the construction only layer by layer, yielding a block-layer tail-hiding property and a gradient lower bound before the hidden tail is reached.
For \(n\in\mathbb{N}\), write \([n]=\{1,\ldots,n\}\). We use \(\langle\cdot,\cdot\rangle\) for the Euclidean inner product, \(\|\cdot\|\) for the Euclidean norm of a vector and the induced operator norm of a matrix, and \(\operatorname{supp}(x)\) for the support of a vector \(x\). The vectors \(e_1,e_2,\ldots\) denote the standard basis vectors in the ambient Euclidean space; when the dimension matters, we write \(e_j^{(m)}\in\mathbb{R}^m\). For a \(C^q\) function \(f\), \(D^q f(x)\) denotes its \(q\)-th Fréchet derivative at \(x\), viewed as a symmetric \(q\)-linear form. For a \(q\)-linear form \(A\), we write \[\|A\|_{\rm op} := \sup_{\|v_1\|,\ldots,\|v_q\|\le1}|A[v_1,\ldots,v_q]|.\] For a map \(G\) between Euclidean spaces, \(\operatorname{Lip}(G)\) denotes its global Lipschitz constant with respect to the induced Euclidean norms; in particular, \(\operatorname{Lip}(D^q f)\) uses the above operator norm on \(q\)-linear forms. The notation \(a\lesssim b\) means \(a\le Cb\) for a positive absolute constant \(C\), \(a\gtrsim b\) means \(b\lesssim a\), and \(a\asymp b\) means both \(a\lesssim b\) and \(b\lesssim a\). We use \(O(\cdot)\), \(\Omega(\cdot)\), and \(\Theta(\cdot)\) with the same convention that hidden constants are positive and absolute unless explicitly stated otherwise. Named numerical constants introduced below, such as the constants \(\ell_q\) in the scalar primitive bounds, are displayed explicitly in quantitative rates rather than absorbed into this asymptotic notation.
The literature surrounding first-order nonconvex optimization and higher-order smoothness is broad, so we discuss only the strands most directly related to our lower-bound result; the references below are necessarily selective.
A separate line of work studies algorithms that can query higher-order derivative information, rather than only function values and gradients. Classical trust-region methods and regularized Newton methods form the basic second-order toolkit [12], [13]. In the Hessian-Lipschitz setting, cubic regularization builds a local quadratic model with a cubic penalty and achieves the \(O(\epsilon^{-3/2})\) complexity for finding first-order stationary points [13], [14]; related work also characterizes the complexity of reaching second-order stationarity [15]. More generally, regularized \(p\)th-order Taylor methods achieve \(O(\epsilon^{-(p+1)/p})\) under Lipschitz \(p\)th derivatives [16], and worst-case analyses for second-order methods further clarify the optimality of this oracle model [17]. These rates are matched by lower bounds for algorithms with access to derivatives up to order \(p\) [8]. Recent mixed-oracle work further studies tradeoffs between gradient and Hessian queries; in particular, finite-difference Hessian approximations yield improved low-dimensional gradient complexity, and even a small number of Hessian queries can change the gradient-query exponent [18]. This higher-order-oracle theory is complementary to our setting: we impose higher-order smoothness on the objective, but the algorithm remains first-order.
There is also a substantial stochastic, finite-sum, and approximate-local-minimum counterpart to the oracle-complexity literature. For second-order stationarity, early stochastic saddle-escaping results show that noisy or perturbed gradient methods can avoid strict saddles and reach approximate local minima [19]–[21]. Under Hessian-Lipschitz structure, Hessian-vector and gradient-only algorithms obtain faster approximate-local-minimum guarantees through cubic regularization, accelerated saddle escaping, and negative-curvature extraction [1]–[4], [22]–[24]. Stochastic and finite-sum refinements combine perturbed SGD, variance reduction, stochastic cubic regularization, and third-order smoothness to improve sample or gradient complexity for local-minimum finding [25]–[34]. More recently, an online-to-nonconvex conversion viewpoint gives deterministic and stochastic upper bounds through a common framework [11]. On the lower-bound side, [35] characterize the power and limitations of stochastic Hessian-vector and higher-order oracles, showing that second-order information does not remove the intrinsic stochastic barrier in the same way it can in deterministic optimization. In finite-sum models, lower bounds for higher-order smooth nonconvex objectives were developed by [36] and then sharpened in a dimension-free form by [37]. In the bounded-variance stochastic-gradient model, [38] prove tight lower bounds showing that SGD is minimax optimal for finding first-order stationary points, while stronger mean-squared smoothness assumptions recover the variance-reduction rate. These works address sample, noise, component-oracle, or saddle-escaping complexity; they are therefore complementary to the deterministic, dimension-free full-gradient lower bound studied here.
We follow the oracle-complexity framework of [8], [9].
Following Def. 1 of [8], let \(p\ge1\) and \(L_p>0\). We say that \(f:\mathbb{R}^d\to\mathbb{R}\) has \(L_p\)-Lipschitz \(p\)th-order derivatives if it is \(p\) times continuously differentiable and, for every \(x\in\mathbb{R}^d\) and every \(v\in\mathbb{R}^d\) with \(\|v\|=1\), the directional projection \(f_{x,v}(t):=f(x+tv)\) satisfies \[\left| f_{x,v}^{(p)}(t)-f_{x,v}^{(p)}(t') \right| \le L_p|t-t'| \qquad \text{for all }t,t'\in\mathbb{R}.\] Let \(\Delta>0\). The class \(\mathcal{F}_p(\Delta,L_p)\) denotes the union, over \(d\in\mathbb{N}\), of all \(C^\infty\) functions \(f:\mathbb{R}^d\to\mathbb{R}\) with \(L_p\)-Lipschitz \(p\)th-order derivatives and \(f(0)-\inf_x f(x)\le\Delta\). For positive \(L_1,\ldots,L_p\), define \[\mathcal{F}_{1:p}(\Delta,L_1,\ldots,L_p) := \bigcap_{q=1}^p \mathcal{F}_q(\Delta,L_q).\]
As in Eq. (7) of [8], a deterministic first-order method \(\mathsf A\) starts from \(x^{(0)}=0\) and, when applied to \(f:\mathbb{R}^d\to\mathbb{R}\), generates iterates \(x^{(t)}\in\mathbb{R}^d\) such that \(x^{(t+1)}\) is a deterministic function of the previous oracle answers \[\left(f(x^{(0)}),\nabla f(x^{(0)}),\ldots,f(x^{(t)}),\nabla f(x^{(t)})\right).\] Define \[T_\epsilon(\mathsf A,f) := \inf\{t\ge0:\|\nabla f(x^{(t)})\|\le\epsilon\}.\] We use the convention \(\inf\emptyset=\infty\). For a class of deterministic first-order methods \(\mathcal{A}\) and a function class \(\mathcal{F}\), write \[T_\epsilon(\mathcal{A},\mathcal{F}) := \inf_{\mathsf A\in\mathcal{A}}\sup_{f\in\mathcal{F}}T_\epsilon(\mathsf A,f),\] up to the immaterial additive constant coming from whether the initial point is counted as a query.
Following Eq. (5) of [9], a sequence \(\{x^{(t)}\}_{t\ge0}\) is first-order zero-respecting with respect to \(f\) if \[\operatorname{supp}(x^{(t)}) \subseteq \bigcup_{s<t}\operatorname{supp}(\nabla f(x^{(s)})) \qquad\text{for all }t\ge0.\] A first-order method is zero-respecting if, for every \(f\), its generated iterate sequence is zero-respecting with respect to \(f\). By contrast, a function \(f:\mathbb{R}^d\to\mathbb{R}\) is a classical first-order zero-chain [9] if, for every \(i\in[d]\) and \(x\in\mathbb{R}^d\), \[\operatorname{supp}(x)\subseteq\{1,\ldots,i-1\} \quad\Longrightarrow\quad \operatorname{supp}(\nabla f(x))\subseteq\{1,\ldots,i\}.\]
We also fix two elementary primitives used in the construction. For \(m\in\mathbb{N}\), let \(\mathsf P_m\in\mathbb{R}^{m\times m}\) be the path Laplacian in tridiagonal form, and let \(H_{\gamma,L}^{(m)}\) be the corresponding massive path operator: \[\label{eq:path-primitive} \mathsf P_1:=0,\qquad \mathsf P_m:= \begin{pmatrix} 1 & -1 & & & \\ -1& 2 & -1 & & \\ & \ddots & \ddots & \ddots & \\ & & -1 & 2 & -1\\ & & & -1 & 1 \end{pmatrix} \quad(m\ge2),\qquad H_{\gamma,L}^{(m)}:=\gamma I_m+L\mathsf P_m .\tag{1}\] For \(r\ge1\), let \(\Upsilon_r\) be the scalar potential from Eq. (10) of [9]: \[\label{eq:scalar-potential} \Upsilon_r(x):= 120\int_1^x \frac{t^2(t-1)}{1+(t/r)^2}\,dt .\tag{2}\]
We collect the elementary bounds on these two primitives for later use.
The primitives in 1 and 2 satisfy the following bounds.
For every \(m\in\mathbb{N}\) and \(\gamma,L>0\), \(0\preceq \mathsf P_m\preceq 4I\) and \(\gamma I\preceq H_{\gamma,L}^{(m)}\preceq(\gamma+4L)I\).
Lemma 2 of [9] gives constants \(\ell_q>0\), \(q\ge1\), which may be chosen so that \(\ell_q\le \exp(\frac{3}{2} q\log q+C_\ell q)\) for a numerical constant \(C_\ell<\infty\). For every \(r\ge1\), we have \(\Upsilon_r\in C^\infty(\mathbb{R})\), \(\Upsilon_r'(0)=\Upsilon_r'(1)=0\), \(m_{\Upsilon_r}:=\inf_x\Upsilon_r(x)=\Upsilon_r(1)=0\), and \(\Upsilon_r(0)\le10\). Moreover, for every \(q\ge1\), \[\operatorname{Lip}\bigl(\Upsilon_r^{(q)}\bigr) \le \ell_q r^{3-q}, \qquad \left\|\Upsilon_r^{(q+1)}\right\|_\infty \le \ell_q r^{3-q}.\]
We now build the hard instance, starting from the limitation of the scalar-chain template used in prior first-order lower bounds.
We begin by recalling the scalar chain underlying the first-order lower bound of [9]. For a fixed \(r\ge1\), its original unscaled form has a multiplier \(0<\mu\le1\) on the scalar nonconvex potential: \[\phi_\mu(u) := \frac{\sqrt\mu}{2}(u_1-1)^2 + \frac{1}{2}\sum_{s=1}^{N}(u_{s+1}-u_s)^2 + \mu\sum_{s=1}^{N}\Upsilon_r(u_s), \qquad u\in\mathbb{R}^{N+1}.\]
For \(s\ge2\), the cross term \(-u_{s-1}u_s\) is the only transmission from phase \(s-1\) to phase \(s\), while the separable potential \(\mu\Upsilon_r(u_s)\) supplies the on-site nonconvex forcing. The following residual certificate is the key point used by the lower-bound argument.
There exists a numerical constant \(c_0:=1/4\) such that, for every \(N\ge1\), every \(r\ge1\), every \(0<\mu\le1\), and every \(u\in\mathbb{R}^{N+1}\) with \(u_N=u_{N+1}=0\), the scalar chain \(\phi_\mu\) defined above satisfies \[\|\nabla\phi_\mu(u)\|_2 \ge c_0\mu^{3/4}.\]
Thus, as long as a zero-respecting method has not reached the tail coordinate, we have \(u_N=0\), and the scalar transition lower bound certifies a large gradient norm. To turn this residual certificate into an \(\epsilon\)-stationarity obstruction under prescribed smoothness budgets, [9] consider the scaled instance \(f(x):=\lambda\sigma^2\phi_\mu(x/\sigma)\), with \(N=T\). The parameters \(\lambda,\sigma,\mu,r\) are then calibrated so that the scaled chain belongs to the target smoothness class, while the chain length \(T\) is set by the available function-value budget; with these choices, all points whose tail coordinates remain hidden still have gradient norm larger than \(\epsilon\).
One key parameter in the scalar hard instance \(\phi_\mu\) is \(\mu\), which sets the strength of the nonconvex onsite potential relative to the quadratic chain. This parameter must be tuned carefully in order to satisfy higher-order smoothness constraints while retaining a nontrivial gradient certificate. By contrast, \(\lambda\) and \(\sigma\) are global amplitude and length-scale parameters: they rescale all derivative orders in a coupled way, and therefore cannot by themselves provide the selective balance needed for higher-order calibration. [9] also extend the construction beyond quadratic activations and obtain analogous gradient lower bounds, but the resulting scalar balancing still leaves a gap between the best known first-order upper bound \(\epsilon^{-7/4}\) for \(p=2\) and their calibrated lower bound \(\epsilon^{-12/7}\).
Our construction closes this gap through two observations.
Tune smoothness through a linear pullback. Instead of relying only on the scalar coefficient \(\mu\), we introduce an additional balancing mechanism by applying the nonconvex potential after a linear observation map. At the level of intuition, this amounts to replacing the coordinatewise potential by \[\begin{align} \sum_{s=1}^{N}\Upsilon_r(u_s) \rightarrow \sum_{s=1}^{N}\Upsilon_r(a_s^\top u) \end{align}\] where \(u\mapsto(a_1^\top u,\ldots,a_N^\top u)\) is a linear operator. Smoothness constraints are stable under such pullbacks: the relevant derivative operator norms are multiplied only by powers of the operator norm of this linear map. Thus the geometry of the observation map gives a new way to tune higher-order smoothness without changing the scalar residual certificate.
Separate revelation from observation. An arbitrary linear observation map would destroy the lower-bound argument: the gradient of \(\Upsilon_r(a_s^\top u)\) points in the direction \(a_s\), which could reveal information outside the zero-chain order. The remedy is to separate the coordinates that drive the oracle revelation from the coordinates observed by the nonconvex potential. Informally, the construction uses a map of the form \[\begin{align} u\rightarrow (u, a_s^\top u), \end{align}\] where the first component keeps the original chain-like revelation structure, while the second component feeds the nonconvex potential and supplies the high-order smoothness scaling. The formal block construction below implements this separation by making the nonconvex readout compatible with the reveal order.
With this intuition in mind, we now define the block chain.
Definition 1 (Block chain). Let \(M,N\in\mathbb{N}\), let \(\gamma,L,\lambda,\kappa,\tau>0\), and let \(a\in\mathbb{R}^M\) be a nonzero suffix vector, meaning that for some \(j_\star\in[M]\), \(\operatorname{supp}(a)\subseteq\{j_\star,\ldots,M\}\). Set \(d:=MN\), and identify \(\mathbb{R}^d\) with \((\mathbb{R}^M)^N\). For a block vector \(z=(z_1,\ldots,z_N)\in(\mathbb{R}^M)^N\), the scalar chain variable in phase \(s\) is the suffix readout \(u_s:=a^\top z_s\), with \(u_0:=1\). The entry coordinate of phase \(s\) is \(x_s:=e_1^\top z_s\). The previous phase enters the next block through \(x_s\), while the current phase is read only through the suffix readout \(u_s\). For \(r\ge1\), define \[\begin{align} f_{M,N,\gamma,L,a,\lambda,\kappa,\tau,r}(z) &:= \sum_{s=1}^N \left[ \frac{1}{2} z_s^\top H_{\gamma,L}^{(M)}z_s - \lambda u_{s-1}x_s + \frac{\kappa}{2}u_s^2 + \tau\Upsilon_r(u_s) \right]. \label{eq:block-chain-expanded} \end{align}\qquad{(1)}\]
For the normalized member of this family, set \[\label{eq:scalar-reduction-geometry} e:=e_1,\qquad \rho:=e^\top\!\left(H_{\gamma,L}^{(M)}\right)^{-1}e,\qquad \alpha:=a^\top\!\left(H_{\gamma,L}^{(M)}\right)^{-1}e,\qquad \beta:=a^\top\!\left(H_{\gamma,L}^{(M)}\right)^{-1}a.\qquad{(2)}\] When \(\alpha>0\), choose \[\label{eq:scalar-reduction-normalization} \lambda:=\frac{1}{\alpha},\qquad \tau:=\frac{1}{\beta},\qquad \kappa:=\lambda^2\rho .\qquad{(3)}\] For \(r\ge1\), define \[\label{eq:normalized-hard-instance} \bar f_{M,N,\gamma,L,a,r} := f_{M,N,\gamma,L,a,\lambda,\kappa,\tau,r},\qquad{(4)}\] where \(\lambda,\tau,\kappa\) are given by ?? .
The term \(-\lambda u_{s-1}x_s\) is the structural replacement for the scalar transmission term \(-u_{s-1}u_s\). If one coupled successive readouts directly after the substitution \(u_s=a^\top z_s\), the gradient would point immediately in the suffix direction \(a\), allowing a zero-respecting method to reach the readout coordinates without traversing the block. We instead inject the previous scalar state through the entry coordinate \(x_s=e_1^\top z_s\). The quadratic block then propagates this signal toward the suffix readout, so the scalar chain is lifted to a block chain while preserving the layer-by-layer revelation structure.
The normalization in ?? is chosen so that the high-dimensional block chain reduces, at the level of the scalar readouts \(u_s=a^\top z_s\), to the same scale as the scalar chain from Proposition [prop:scalar-transition-lower-bound]. The quantities \(\rho,\alpha,\beta\) are the Green-kernel responses of the quadratic block: \(\alpha\) measures how an input through the entry coordinate reaches the suffix readout, \(\beta\) measures the self-response of that readout, and \(\rho\) measures the self-response of the entry coordinate. Thus \(\lambda=1/\alpha\) normalizes the transmission from \(u_{s-1}\) to \(u_s\), \(\tau=1/\beta\) puts the nonconvex potential on the same scalar scale, and \(\kappa=\lambda^2\rho\) compensates for the curvature introduced by injecting through the entry coordinate. In this sense, \(\bar f_{M,N,\gamma,L,a,r}\) is the block-chain member whose scalar projection has the Carmon-chain normalization.
We now collect the basic estimates for the block chain that will be used later in the lower-bound calibration.
Lemma 1 (Boundedness and smoothness of normalized hard instances). Fix \(p\ge2\), \(M,N\in\mathbb{N}\), \(\gamma,L>0\), \(r\ge1\), and a nonzero vector \(a\in\mathbb{R}^M\). Assume \(\alpha>0\). Then the normalized hard-instance family from ?? satisfies \[\operatorname{Lip}\!\left(\nabla \bar f_{M,N,\gamma,L,a,r}\right) \le \gamma+4L + \frac{2\|a\|}{\alpha} + \left( \frac{\rho}{\alpha^2} + \frac{\ell_1r^2}{\beta} \right)\|a\|^2 .\] For \(q=2,\ldots,p\), \[\operatorname{Lip}\!\left(D^q\bar f_{M,N,\gamma,L,a,r}\right) \le \frac{\ell_qr^{3-q}\|a\|^{q+1}}{\beta}.\] Moreover, \[\bar f_{M,N,\gamma,L,a,r}(0) - \inf \bar f_{M,N,\gamma,L,a,r} \le \frac{10N}{\beta} + \frac{\rho}{2\alpha^2}.\]
Proof. See Appendix 7.1. ◻
Lemma 1 makes explicit the calibration role of the vector \(a\). The first-order Lipschitz bound has a baseline scale \(\gamma+4L\), so its dominant contribution can be fixed through \(L\). In contrast, for \(q\ge2\), the \(q\)-th order Lipschitz bound depends on \(a\) through \(\|a\|^{q+1}\) (with the normalization by \(\beta\)). Thus tuning \(\|a\|\) separates the higher-order smoothness constraints from the first-order scale.
We next record the block-layer consequence needed in the lower-bound argument: the last scalar chain variable remains hidden until the suffix of the last block has been reached.
Lemma 2 (Tail hiding for zero-respecting sequences). Let \(F=f_{M,N,\gamma,L,a,\lambda,\kappa,\tau,r}\) be the block-chain function in Definition 1, and let \(j_\star\in[M]\) satisfy \[\operatorname{supp}(a)\subseteq S:=\{j_\star,\ldots,M\}.\] For \(\ell\ge0\), define the block-layer coordinate set \[I_\ell := \left\{ (s,j)\in[N]\times[M]: (s-1)j_\star+\min\{j,j_\star\}\le \ell \right\}.\] Let \(\{z^{(t)}\}_{t\ge0}\), \(z^{(t)}=(z_1^{(t)},\ldots,z_N^{(t)})\), be first-order zero-respecting with respect to \(F\), in the standard coordinate-support sense recalled in Section 3, with \(z^{(0)}=0\). Then, identifying supports with subsets of \([N]\times[M]\), \[\operatorname{supp}(z^{(t)})\subseteq I_t \qquad\text{for all }t\ge0.\] Consequently, if \(t<Nj_\star\), then \[u_N^{(t)}:=a^\top z_N^{(t)}=0.\]
Proof. See Appendix 7.2. ◻
Lemma 3 (Gradient lower bound for normalized hard instances). Fix \(M,N\in\mathbb{N}\), \(\gamma,L>0\), \(r\ge1\), and a nonzero vector \(a\in\mathbb{R}^M\). Assume \(\alpha>0\). For any \(z=(z_1,\ldots,z_N)\in(\mathbb{R}^M)^N\) satisfying \[a^\top z_N=0,\] the normalized hard-instance family from ?? satisfies \[\left\|\nabla \bar f_{M,N,\gamma,L,a,r}(z)\right\| \gtrsim \frac{\sqrt{\gamma}}{ \sqrt{\beta} + \frac{\beta\sqrt{\rho}}{\alpha} }.\]
Proof. See Appendix 7.3. ◻
Lemmas 1, 2, and 3 are the uncalibrated interface of the construction: the block geometry enters only through \(\rho,\alpha,\beta\), \(\|a\|\), and the suffix layer \(j_\star\). It remains to choose these quantities so that the smoothness budgets, initial gap, reveal depth, and gradient certificate all have the desired scales.
We now carry out the calibration left open by the block-chain construction. Throughout this section, let \(p\ge2\), let \(L_1,\ldots,L_p,\epsilon,\Delta>0\), and let \(\ell_1,\ldots,\ell_p\) be the constants from Proposition [prop:primitive-bounds].
The following scale summarizes the active smoothness budget. For a fixed potential parameter \(r\), \(\Gamma_p(r)\) is the largest mass scale compatible with all derivative Lipschitz constraints, up to the numerical constants already absorbed into the construction. We then optimize over \(r\). Define \[\begin{align} \Gamma_p(r) &:= \min\left\{ L_1,\, \frac{L_1}{\ell_1r^2},\, \left(\frac{L_2\epsilon}{\ell_2r}\right)^{1/2},\, \min_{3\le q\le p} \left( \frac{L_q\epsilon^{q-1}r^{q-3}}{\ell_q} \right)^{1/q} \right\}, \qquad r\ge1,\\ \Gamma_p &:= \sup_{r\ge1}\Gamma_p(r), \end{align}\] where the last minimum is omitted when \(p=2\). Let \(r_\star\ge1\) be such that \(\Gamma_p(r_\star)\asymp\Gamma_p\).
The parameter \(\Gamma_p\) is the only implicit quantity in the final rate. The next proposition unpacks its \(\epsilon\)-dependence in the high-accuracy regime.
For all sufficiently small \(\epsilon\), the following simplifications of \(\Gamma_p\) hold. If \(p\in\{2,3\}\), then \[\Gamma_p = \left(\frac{L_p\epsilon^{p-1}}{\ell_p}\right)^{1/p}.\] If \(p\ge4\), then \[\Gamma_p = \epsilon^{2/3} \sup_{R>0} \min\left\{ \frac{L_1}{\ell_1R^2},\, \left(\frac{L_2}{\ell_2R}\right)^{1/2},\, \min_{3\le q\le p} \left(\frac{L_qR^{q-3}}{\ell_q}\right)^{1/q} \right\}.\]
Proof. See Appendix 8.1. ◻
We can now state the deterministic first-order lower bound.
Theorem 1 (Main deterministic first-order lower bound). Let \(\mathcal{A}_{\rm det}\) denote the class of deterministic first-order methods. Assume that \(\epsilon\le c_\epsilon\min_{1\le q\le p} \Delta^{q/(q+1)}(L_q/\ell_q)^{1/(q+1)}\), where \(c_\epsilon>0\) is a sufficiently small absolute constant. Then \[T_\epsilon\bigl(\mathcal{A}_{\rm det}, \mathcal{F}_{1:p}(\Delta,L_1,\ldots,L_p)\bigr) \gtrsim \Delta L_1^{1/2}\Gamma_p^{1/2}\epsilon^{-2}.\] In particular, for sufficiently small \(\epsilon\), this implies \[T_\epsilon\bigl(\mathcal{A}_{\rm det}, \mathcal{F}_{1:p}(\Delta,L_1,\ldots,L_p)\bigr) \gtrsim \begin{cases} \Delta L_1^{1/2}(L_2/\ell_2)^{1/4}\epsilon^{-7/4}, & p=2,\\ \Delta L_1^{1/2}(L_3/\ell_3)^{1/6}\epsilon^{-5/3}, & p=3,\\ \Delta L_1^{1/2} \min_{1\le q\le p}(L_q/\ell_q)^{1/(2q)}\epsilon^{-5/3}, & p\ge4. \end{cases}\]
We record three consequences of the theorem.
The lower bound can be written as \[\Delta L_1^{1/2}\Gamma_p^{1/2}\epsilon^{-2} = \Delta L_1\epsilon^{-2} \left(\frac{\Gamma_p}{L_1}\right)^{1/2}.\] Here \(\Delta L_1\epsilon^{-2}\) is the classical first-order complexity scale under Lipschitz gradients alone. The remaining factor \((\Gamma_p/L_1)^{1/2}\) is the acceleration factor imposed by the active higher-order smoothness constraints. In this sense, \(\Gamma_p\) measures how much of the baseline \(L_1\)-scale remains available after enforcing the higher-order smoothness budgets; when the active constraint makes \(\Gamma_p\) depend on \(\epsilon\), this factor converts the baseline \(\epsilon^{-2}\) rate into the accelerated exponents.
The special cases in Theorem 1 match the known upper bounds not only in the exponent of \(\epsilon\), but also in their dependence on the initial gap and smoothness constants. In the Hessian-Lipschitz regime, the \(\epsilon^{-7/4}\) rate appears in several accelerated or curvature-exploiting algorithms [1]–[7]. In the purely deterministic first-order stationarity setting, these bounds have the scale \(O(\Delta L_1^{1/2}L_2^{1/4}\epsilon^{-7/4})\), up to logarithmic factors in some variants; the restarted methods of [6] remove this logarithmic loss. For third-order smoothness, [5] obtain the corresponding first-order upper bound \(O(\Delta L_1^{1/2}L_3^{1/6}\epsilon^{-5/3} \log(L_1\Delta/\epsilon^2))\) gradient evaluations. Thus the \(p=2\) and \(p=3\) lower bounds match the polynomial dependence on \(\epsilon\), \(\Delta\), and the active smoothness constants in the corresponding upper bounds.
Together with the third-order first-order upper bound, the last line of Theorem 1 shows that the \(\epsilon\)-dependence saturates once third derivatives are Lipschitz. Indeed, for every \(p\ge4\), adding Lipschitz bounds on derivatives of order \(4\) and higher does not improve the dimension-free first-order exponent beyond \(\epsilon^{-5/3}\). Higher-order smoothness may still matter through the dependence on the smoothness constants: the active term in \(\Gamma_p\), or in the simplified bound above, can change when the higher-order Lipschitz budgets are favorable. This gives lower-bound support for the corresponding observation in the “convex until proven guilty” framework of [5].
It remains to specify the calibrated instance used in the proof of Theorem 1. Lemmas 1, 2, and 3 reduce this to choosing the block geometry: the block length creates reveal depth, the number of phases uses the available gap, and the suffix vector \(a\) sets the low-rank smoothness and gradient certificate scales.
Condition 2 (Calibrated parameters). Use the scale \(\Gamma_p\) and \(r_\star\) defined above. Set \[\gamma:=c_{\rm hp}\Gamma_p .\] With this value of \(\gamma\), choose the free parameters of \(\bar f_{M,N,\gamma,L,a,r}\) in the following order: \[\begin{align} M&:=\left\lceil C_M\sqrt{\frac{L_1}{\gamma}}\right\rceil,\qquad N:=\left\lfloor c_N\frac{\Delta\gamma}{\epsilon^2}\right\rfloor,\qquad L:=L_1,\\ a&:=\frac{\gamma^{5/4}}{L_1^{1/4}\epsilon} \bigl( \underbrace{0,\ldots,0}_{\lfloor M/2\rfloor-1}, 1,\ldots,1 \bigr)^\top\in\mathbb{R}^M,\qquad r:=r_\star. \end{align}\] Here \(c_{\rm hp}>0\) is a sufficiently small absolute constant and \(C_M>0,c_N>0\) are sufficiently large and sufficiently small absolute constants, respectively. Let \(H:=H_{\gamma,L}^{(M)}\). For this choice of \(a\), the positivity condition required by the scalar-reduction normalization holds; define \(\lambda,\tau,\kappa\) by ?? . We assume the nontrivial gap regime in which \(N\ge1\). Set \(d:=MN\) and, under the block identification \(\mathbb{R}^d\cong(\mathbb{R}^M)^N\), define the calibrated hard instance \[f_{\Delta,L_{1:p},\epsilon} := \bar f_{M,N,\gamma,L,a,r}.\]
The following lemma verifies that this choice realizes the desired scales and therefore produces a hard instance in the target smoothness class.
Lemma 4 (Zero-respecting lower bound for the calibrated instance). Let the parameters be chosen as in Condition 2. Then the quantities from the scalar-reduction normalization satisfy \[\rho\asymp(\gamma L_1)^{-1/2},\qquad \alpha\asymp\frac{\gamma^{1/4}}{L_1^{1/4}\epsilon},\qquad \beta\asymp\frac{\gamma}{\epsilon^2},\qquad \|a\|\asymp\frac{\gamma}{\epsilon}.\] If \(\epsilon\le c_\epsilon\min_{1\le q\le p} \Delta^{q/(q+1)}(L_q/\ell_q)^{1/(q+1)}\) for a sufficiently small absolute constant \(c_\epsilon>0\), then the calibrated instance \(f_{\Delta,L_{1:p},\epsilon}\) belongs to \(\mathcal{F}_{1:p}(\Delta,L_1,\ldots,L_p)\). Moreover, any first-order zero-respecting method \(\mathsf A\) applied to \(f_{\Delta,L_{1:p},\epsilon}\), starting from the origin, satisfies \[T_\epsilon\bigl(\mathsf A,f_{\Delta,L_{1:p},\epsilon}\bigr) \gtrsim \Delta L_1^{1/2}\Gamma_p^{1/2}\epsilon^{-2}\]
Proof. See Appendix 8.2. ◻
Proof of Theorem 1. Choose the absolute constant \(c_\epsilon\) in the theorem no larger than the corresponding constant in Lemma 4. Lemma 4 gives the stated lower bound for zero-respecting methods on an instance in \(\mathcal{F}_{1:p}(\Delta,L_1,\ldots,L_p)\). The class \(\mathcal{F}_{1:p}(\Delta,L_1,\ldots,L_p)\) is closed under orthogonal changes of variables, so Proposition 1 of [9] transfers the zero-respecting lower bound to arbitrary deterministic first-order methods. Taking the infimum over \(\mathsf A\in\mathcal{A}_{\rm det}\) gives the minimax claim. The explicit display follows by substituting Proposition [prop:gamma-p-upper-bound]; in the \(p\ge4\) regime we use its supremum at \(R=1\), which gives \(\Gamma_p\ge\epsilon^{2/3}\min_{1\le q\le p}(L_q/\ell_q)^{1/q}\). ◻
We established a dimension-free deterministic first-order lower bound for finding approximate stationary points under higher-order smoothness. In the Hessian-Lipschitz case the bound gives the matching \(\Omega(\epsilon^{-7/4})\) dependence, and under Lipschitz third derivatives it gives the matching \(\Omega(\epsilon^{-5/3})\) dependence. Thus the accelerated rates achieved by first-order methods under higher-order smoothness are optimal, up to the standard logarithmic factors present in some upper bounds. The main technical device is the block-chain hard instance. It separates the scalar transition obstruction from the blockwise oracle-discovery process: the scalar state is carried by a suffix readout inside each block, while the path quadratic forces zero-respecting methods to expose the block one coordinate layer at a time.
DZ first began thinking about this problem in 2019, but did not make substantial progress at that time. Motivated by the recent advances in the mathematical reasoning capabilities of AI models, DZ revisited the problem in May 2026 with AI assistance. DZ supplied the relevant prior literature and designed prompts asking ChatGPT 5.5 Pro to search for a first-order lower-bound construction. Through several rounds of interaction, ChatGPT 5.5 Pro identified the block-chain construction as the right direction and began validating its correctness. DZ then took primary responsibility for checking the proofs, simplifying several proof paths, improving the presentation, and formulating extension directions, again with assistance from ChatGPT 5.5 Pro.
Appendix
Proof of Lemma 1. Let \(\Upsilon:=\Upsilon_r\) and \(F:=\bar f_{M,N,\gamma,L,a,r}\), and let \(e,\rho,\alpha,\beta,\lambda,\tau,\kappa\) be the quantities in ?? and ?? for the present \((M,\gamma,L,a)\), and set \(H:=H_{\gamma,L}^{(M)}\). In particular, \(\kappa=\rho/\alpha^2\). Write \(z=(z_1,\ldots,z_N)\in(\mathbb{R}^M)^N\), \(u_s:=a^\top z_s\), and \(u_0:=1\). We use the uniform properties \(m:=\inf_x\Upsilon(x)=\Upsilon(1)=0\), \(\Upsilon(0)\le 10\), and, for \(q=1,\ldots,p\), \(\|\Upsilon^{(q+1)}\|_\infty\le \ell_q r^{3-q}\).
We first prove the \(q=1\) smoothness bound. Decompose \(F=Q+R\), where \[Q(z) := \sum_{s=1}^N \left[ \frac{1}{2} z_s^\top H z_s - \lambda u_{s-1}e^\top z_s + \frac{\kappa}{2}u_s^2 \right],\] and \(R(z):=\tau\sum_{s=1}^N\Upsilon(u_s)\). For any block vector \(v=(v_1,\ldots,v_N)\), the quadratic part satisfies \[\begin{align} D^2Q(z)[v,v] &= \sum_{s=1}^N v_s^\top H v_s + \kappa\sum_{s=1}^N(a^\top v_s)^2 - 2\lambda\sum_{s=2}^N(a^\top v_{s-1})(e^\top v_s). \end{align}\] Hence, using \(\|e\|=1\), \[\begin{align} |D^2Q(z)[v,v]| &\le \|H\|\sum_{s=1}^N\|v_s\|^2 + \kappa\|a\|^2\sum_{s=1}^N\|v_s\|^2 + 2\lambda\|a\|\sum_{s=2}^N\|v_{s-1}\|\|v_s\| \\ &\le \left( \|H\|+\kappa\|a\|^2+2\lambda\|a\| \right)\|v\|^2. \end{align}\] Therefore \[\|D^2Q(z)\|_{\rm op} \le \gamma+4L + \frac{\rho}{\alpha^2}\|a\|^2 + \frac{2\|a\|}{\alpha}.\]
For the nonlinear part, \[D^2R(z)[v,v] = \tau\sum_{s=1}^N \Upsilon''(u_s)(a^\top v_s)^2.\] Thus \[\begin{align} |D^2R(z)[v,v]| &\le \tau\|\Upsilon''\|_\infty \sum_{s=1}^N |a^\top v_s|^2 \\ &\le \frac{\ell_1 r^2}{\beta}\|a\|^2\|v\|^2. \end{align}\] Consequently, \[\|D^2F(z)\|_{\rm op} \le \gamma+4L + \frac{2\|a\|}{\alpha} + \left( \frac{\rho}{\alpha^2} + \frac{\ell_1r^2}{\beta} \right)\|a\|^2 \qquad \text{for every }z,\] and hence \[\operatorname{Lip}(\nabla F) \le \gamma+4L + \frac{2\|a\|}{\alpha} + \left( \frac{\rho}{\alpha^2} + \frac{\ell_1r^2}{\beta} \right)\|a\|^2 .\]
We now prove the higher-order smoothness bounds. Fix \(q\in\{2,\ldots,p\}\). All terms in \(Q\) are quadratic, so \(D^{q+1}Q\equiv0\). Thus only \(R\) contributes. For arbitrary block vectors \[v^{(0)},v^{(1)},\ldots,v^{(q)}\in(\mathbb{R}^M)^N, \qquad v^{(\ell)}=(v^{(\ell)}_1,\ldots,v^{(\ell)}_N),\] we have \[\begin{align} D^{q+1}R(z) [v^{(0)},v^{(1)},\ldots,v^{(q)}] &= \tau \sum_{s=1}^N \Upsilon^{(q+1)}(u_s) \prod_{\ell=0}^{q} \bigl(a^\top v_s^{(\ell)}\bigr). \end{align}\] Therefore \[\begin{align} \left| D^{q+1}R(z) [v^{(0)},v^{(1)},\ldots,v^{(q)}] \right| &\le \frac{\ell_q r^{3-q}}{\beta} \sum_{s=1}^N \prod_{\ell=0}^{q} \left|a^\top v_s^{(\ell)}\right|. \end{align}\] We use the elementary inequality that for nonnegative sequences \(b^{(0)},\ldots,b^{(q)}\), \[\sum_s\prod_{\ell=0}^q b_s^{(\ell)} \le \prod_{\ell=0}^q \left(\sum_s (b_s^{(\ell)})^2\right)^{1/2}.\] Applying this with \(b_s^{(\ell)}:=|a^\top v_s^{(\ell)}|\) gives \[\begin{align} \sum_{s=1}^N \prod_{\ell=0}^{q} |a^\top v_s^{(\ell)}| &\le \prod_{\ell=0}^{q} \left( \sum_{s=1}^N |a^\top v_s^{(\ell)}|^2 \right)^{1/2} \\ &\le \|a\|^{q+1} \prod_{\ell=0}^{q} \|v^{(\ell)}\|. \end{align}\] Hence \[\|D^{q+1}F(z)\|_{\rm op} = \|D^{q+1}R(z)\|_{\rm op} \le \frac{\ell_q r^{3-q}\|a\|^{q+1}}{\beta}.\] By the fundamental theorem of calculus along line segments, \[\|D^qF(x)-D^qF(y)\|_{\rm op} \le \sup_{0\le t\le1} \|D^{q+1}F(y+t(x-y))\|_{\rm op} \|x-y\|,\] so \[\operatorname{Lip}(D^qF) \le \frac{\ell_q r^{3-q}\|a\|^{q+1}}{\beta}, \qquad q=2,\ldots,p.\]
For each phase \(s\), write \(v:=u_{s-1}\). Since \(H\succ0\), \[\begin{align} \frac{1}{2} z_s^\top H z_s-\lambda v e^\top z_s &= \frac{1}{2} \left\|z_s-\lambda vH^{-1}e\right\|_H^2 -\frac{\lambda^2v^2}{2}e^\top H^{-1}e\\ &\ge -\frac{\kappa}{2}v^2, \end{align}\] where \(\|w\|_H^2:=w^\top Hw\), \(\kappa=\lambda^2\rho\), and \(\rho=e^\top H^{-1}e\). Hence \[\begin{align} &\frac{1}{2} z_s^\top H z_s-\lambda u_{s-1}e^\top z_s +\frac{\kappa}{2}u_s^2+\tau\Upsilon(u_s)\\ &\qquad\ge \frac{\kappa}{2}(u_s^2-u_{s-1}^2)+\tau\Upsilon(u_s). \end{align}\] Summing over \(s=1,\ldots,N\), using \(u_0=1\), \(u_N^2\ge0\), and \(\Upsilon\ge0\), gives \(F(z)\ge \frac{\kappa}{2}(u_N^2-u_0^2)\ge-\frac{\kappa}{2}\). At the origin, \(u_s=0\) for every \(s\ge1\), and all quadratic, linear, and stabilization terms vanish. Since \(\Upsilon(0)\le10\), \(F(0)\le10N\tau\). Therefore \[F(0)-\inf_zF(z) \le 10N\tau+\frac{\kappa}{2} = \frac{10N}{\beta}+\frac{\rho}{2\alpha^2}.\] ◻
Proof of Lemma 2. For each phase \(s\), all coordinates in \(\{s\}\times S\) have layer index \(s j_\star\), since for \(j\in S\), \((s-1)j_\star+\min\{j,j_\star\}=s j_\star\). We prove by induction that \(\operatorname{supp}(z^{(t)})\subseteq I_t\) for every \(t\ge0\), where supports are understood in block-coordinate notation.
The key step is the following one-step support implication. Suppose \(\operatorname{supp}(z)\subseteq I_t\). Write \(H=H_{\gamma,L}^{(M)}\), \(u_s=a^\top z_s\), \(x_s=e_1^\top z_s\), and use the convention \(x_{N+1}=0\). The \(s\)-th gradient block is \[g_s = Hz_s - \lambda u_{s-1}e_1 + (\kappa u_s+\tau\Upsilon_r'(u_s))a - \lambda x_{s+1}a.\] We check that each term is supported in \(I_{t+1}\).
Since \(H\) is tridiagonal, \(Hz_s\) can only move support inside phase \(s\) by one neighboring coordinate. In terms of \(I_t\), this can increase \(\min\{j,j_\star\}\) by at most one, so \(Hz_s\) is supported in \(I_{t+1}\).
For the entry term \(-\lambda u_{s-1}e_1\), if \(s=1\), then the coordinate \((1,1)\) belongs to \(I_{t+1}\). If \(s\ge2\) and \(u_{s-1}\ne0\), then \(z_{s-1}\) has some support in the suffix \(S\), so \((s-1)j_\star\le t\). Hence the coordinate \((s,1)\), whose layer index is \((s-1)j_\star+1\), belongs to \(I_{t+1}\).
For the term \((\kappa u_s+\tau\Upsilon_r'(u_s))a\), if \(z_s\) has no support in \(S\), then \(u_s=0\), and Proposition [prop:primitive-bounds] gives \(\Upsilon_r'(0)=0\), so the coefficient vanishes. Otherwise \(\{s\}\times S\) is already contained in \(I_t\), and the term is supported in \(I_t\subseteq I_{t+1}\).
Finally, consider \(-\lambda x_{s+1}a\). If \(x_{s+1}=0\), the term vanishes. If \(x_{s+1}\ne0\), then coordinate \((s+1,1)\) belongs to the support of \(z\), so \(sj_\star+1\le t\). Thus \(\{s\}\times S\), whose coordinates all have layer index \(sj_\star\), is contained in \(I_t\). Hence this term is also supported in \(I_t\subseteq I_{t+1}\). Therefore \(\operatorname{supp}(\nabla F(z))\subseteq I_{t+1}\) whenever \(\operatorname{supp}(z)\subseteq I_t\).
Now use the zero-respecting property. Since \(z^{(0)}=0\), the induction starts with \(\operatorname{supp}(z^{(0)})\subseteq I_0\). If \(\operatorname{supp}(z^{(t')})\subseteq I_{t'}\) for all \(t'<t\), then the one-step implication gives \(\operatorname{supp}(\nabla F(z^{(t')}))\subseteq I_{t'+1}\subseteq I_t\) for \(t'<t\). By zero-respectingness, \[\operatorname{supp}(z^{(t)}) \subseteq \bigcup_{t'<t}\operatorname{supp}(\nabla F(z^{(t')})) \subseteq I_t.\] This proves the induction claim.
If \(t<Nj_\star\), then no coordinate \((N,j)\) with \(j\in S\) lies in \(I_t\). Since \(\operatorname{supp}(a)\subseteq S\), we conclude \(u_N^{(t)}=a^\top z_N^{(t)}=0\). ◻
Lemma 5 (Gradient projection identity). For \(M,N\in\mathbb{N}\), \(\gamma,L,r>0\), and any nonzero vector \(a\in\mathbb{R}^M\), let \(e,\rho,\alpha,\beta,\lambda,\tau,\kappa\) be the quantities in ?? and ?? for the present \((M,\gamma,L,a)\), and set \(H:=H_{\gamma,L}^{(M)}\). Let \(g_s\) denote the \(s\)-th block of \(\nabla\bar f_{M,N,\gamma,L,a,r}(z)\), namely \[g_s = Hz_s - \lambda u_{s-1}e + (\kappa u_s+\tau\Upsilon_r'(u_s))a - \lambda(e^\top z_{s+1})a,\] where \(u_s=a^\top z_s\). With \[w_{\mathrm{out}}=\frac{H^{-1}a}{\beta},\qquad w_{\mathrm{in}}=H^{-1}\left(e-\frac{\alpha}{\beta}a\right),\] one has, for \(s=1,\ldots,N-1\), \[w_{\mathrm{out}}^\top g_s+\lambda w_{\mathrm{in}}^\top g_{s+1} = \tau\left[ 2u_s-u_{s-1}-u_{s+1}+\Upsilon_r'(u_s) \right].\]
Proof. Write \(x_s=e^\top z_s\) within this proof. We first expand the two projections without substituting the parameter identities \(\lambda=1/\alpha\), \(\tau=1/\beta\), and \(\kappa=\lambda^2\rho\). Since \[w_{\mathrm{out}}=\frac{H^{-1}a}{\beta}, \qquad w_{\mathrm{out}}^\top H z_s=\frac{u_s}{\beta},\qquad w_{\mathrm{out}}^\top e=\frac{\alpha}{\beta},\qquad w_{\mathrm{out}}^\top a=1,\] we have \[w_{\mathrm{out}}^\top g_s = \frac{u_s}{\beta} - \lambda\frac{\alpha}{\beta}u_{s-1} + \kappa u_s + \tau\Upsilon_r'(u_s) - \lambda x_{s+1}.\] For the second projection, use only \(a^\top w_{\mathrm{in}}=0\) to remove the terms parallel to \(a\): \[\begin{align} w_{\mathrm{in}}^\top g_{s+1} &= w_{\mathrm{in}}^\top H z_{s+1} - \lambda u_s w_{\mathrm{in}}^\top e + (\kappa u_{s+1}+\tau\Upsilon_r'(u_{s+1}))a^\top w_{\mathrm{in}} - \lambda x_{s+2}a^\top w_{\mathrm{in}} \\ &= x_{s+1} - \frac{\alpha}{\beta}u_{s+1} - \lambda(w_{\mathrm{in}}^\top e)u_s . \end{align}\] Thus \(\lambda w_{\mathrm{in}}^\top g_{s+1} =\lambda x_{s+1} -\lambda\frac{\alpha}{\beta}u_{s+1} -\lambda^2(w_{\mathrm{in}}^\top e)u_s\). Adding the two expansions cancels the \(x_{s+1}\) terms and gives \[w_{\mathrm{out}}^\top g_s+\lambda w_{\mathrm{in}}^\top g_{s+1} = \left( \frac{1}{\beta}+\kappa-\lambda^2 w_{\mathrm{in}}^\top e \right)u_s - \lambda\frac{\alpha}{\beta}u_{s-1} - \lambda\frac{\alpha}{\beta}u_{s+1} + \tau\Upsilon_r'(u_s).\] Finally, \(w_{\mathrm{in}}^\top e=\rho-\frac{\alpha^2}{\beta}\). Using the parameter choices \(\lambda=1/\alpha\), \(\tau=1/\beta\), and \(\kappa=\lambda^2\rho\), the coefficient of \(u_s\) becomes \[\frac{1}{\beta}+\lambda^2\rho-\lambda^2\left(\rho-\frac{\alpha^2}{\beta}\right) = \frac{2}{\beta} = 2\tau,\] while \(\lambda\frac{\alpha}{\beta}=\frac{1}{\beta}=\tau\). Therefore \[w_{\mathrm{out}}^\top g_s+\lambda w_{\mathrm{in}}^\top g_{s+1} = \tau\left[ 2u_s-u_{s-1}-u_{s+1}+\Upsilon_r'(u_s) \right].\] ◻
We now prove Lemma 3.
Proof of Lemma 3. Write \(u_s:=a^\top z_s\), \(u_0:=1\), and \(u_{N+1}:=0\), and let \(g_s\) denote the \(s\)-th block of \(\nabla \bar f_{M,N,\gamma,L,a,r}(z)\). Let \(e,\rho,\alpha,\beta,\lambda,\tau,\kappa\) be the quantities in ?? and ?? for the present \((M,\gamma,L,a)\), set \(H:=H_{\gamma,L}^{(M)}\), and define \[w_{\mathrm{out}}:=\frac{H^{-1}a}{\beta}, \qquad w_{\mathrm{in}}:=H^{-1}\left(e-\frac{\alpha}{\beta}a\right).\] Set \(r_s:=2u_s-u_{s-1}-u_{s+1}+\Upsilon_r'(u_s)\), \(s=1,\ldots,N\). Since \(u_N=u_{N+1}=0\), Proposition [prop:scalar-transition-lower-bound] with \(\mu=1\) gives \(\|\nabla\phi_1(u)\|_2\ge c_0\). The last gradient coordinate of \(\phi_1\) is \(u_{N+1}-u_N=0\), so \(\|r\|_2\ge c_0\). By Lemma 5, for \(s=1,\ldots,N-1\), \[\tau r_s = w_{\mathrm{out}}^\top g_s + \lambda w_{\mathrm{in}}^\top g_{s+1}.\] For the last phase, \(u_N=0\), \(u_{N+1}=0\), and \(\Upsilon_r'(0)=0\), so the same projection expansion gives \(\tau r_N=w_{\mathrm{out}}^\top g_N\). Let \(A:=\|w_{\mathrm{out}}\|+\lambda\|w_{\mathrm{in}}\|\). Then \[\tau |r_s| \le A(\|g_s\|+\|g_{s+1}\|), \qquad s=1,\ldots,N-1,\] and \(\tau |r_N|\le A\|g_N\|\). Squaring and summing yields \[\tau^2\|r\|_2^2 \le C A^2 \left\|\nabla \bar f_{M,N,\gamma,L,a,r}(z)\right\|^2\] for an absolute constant \(C\). Since \(\|r\|_2\ge c_0\), \[\left\|\nabla \bar f_{M,N,\gamma,L,a,r}(z)\right\| \gtrsim \frac{\tau}{A}.\] Finally, since \(H\succeq \gamma I\), \[\|H^{-1}a\|^2 = a^\top H^{-2}a \le \frac{1}{\gamma}a^\top H^{-1}a = \frac{\beta}{\gamma},\] and \[\|w_{\mathrm{out}}\| = \frac{\|H^{-1}a\|}{\beta} \le \frac{1}{\sqrt{\gamma\beta}},\] and \[\|w_{\mathrm{in}}\|^2 \le \frac{1}{\gamma} \left(e-\frac{\alpha}{\beta}a\right)^\top H^{-1} \left(e-\frac{\alpha}{\beta}a\right) \le \frac{\rho}{\gamma}.\] The last inequality follows by expanding the quadratic form and using the definitions of \(\alpha,\beta,\rho\). Thus \(\lambda\|w_{\mathrm{in}}\|\le \frac{1}{\alpha\sqrt{\gamma}}\sqrt{\rho}\). Therefore \[\frac{\tau}{A} \gtrsim \frac{\sqrt{\gamma}}{ \sqrt{\beta} + \frac{\beta\sqrt{\rho}}{\alpha} }.\] This proves the claim. ◻
Proof of Proposition [prop:gamma-p-upper-bound]. First consider \(p\in\{2,3\}\). In this case all terms in \(\Gamma_p(r)\) are nonincreasing for \(r\ge1\), so the supremum is attained at \(r=1\). Thus \[\Gamma_p = \min\left\{ L_1,\, \frac{L_1}{\ell_1},\, \min_{2\le q\le p} \left(\frac{L_q\epsilon^{q-1}}{\ell_q}\right)^{1/q} \right\}.\] For sufficiently small \(\epsilon\), the \(q=p\) term is the minimum, proving the claim for \(p\in\{2,3\}\).
Now suppose \(p\ge4\). For \(R>0\), define \[\mathfrak G_p(R) := \min\left\{ \frac{L_1}{\ell_1R^2},\, \left(\frac{L_2}{\ell_2R}\right)^{1/2},\, \min_{3\le q\le p} \left(\frac{L_qR^{q-3}}{\ell_q}\right)^{1/q} \right\}.\] The function \(\mathfrak G_p(R)\) is continuous and positive on \((0,\infty)\), and it is bounded above by the \(q=3\) term \((L_3/\ell_3)^{1/3}\). Moreover, \(\mathfrak G_p(R)\to0\) as \(R\to\infty\), and \(\mathfrak G_p(R)\to0\) as \(R\downarrow0\), because one of the terms with \(q\ge4\) is present. Hence the supremum \(\mathfrak G_p=\sup_{R>0}\mathfrak G_p(R)\) is finite, positive, and attained at some \(R_\star>0\).
For \(r\ge1\), set \(R:=r\epsilon^{1/3}\). Equivalently, \(r=R\epsilon^{-1/3}\), and the constraint \(r\ge1\) becomes \(R\ge\epsilon^{1/3}\). With this change of variables, each nonconstant term in \(\Gamma_p(r)\) has the same factor \(\epsilon^{2/3}\): \[\frac{L_1}{\ell_1r^2} = \epsilon^{2/3}\frac{L_1}{\ell_1R^2}, \qquad \left(\frac{L_2\epsilon}{\ell_2r}\right)^{1/2} = \epsilon^{2/3}\left(\frac{L_2}{\ell_2R}\right)^{1/2},\] and, for \(q=3,\ldots,p\), \[\left( \frac{L_q\epsilon^{q-1}r^{q-3}}{\ell_q} \right)^{1/q} = \epsilon^{2/3} \left( \frac{L_qR^{q-3}}{\ell_q} \right)^{1/q}.\] Therefore \[\Gamma_p = \sup_{R\ge\epsilon^{1/3}} \min\left\{ L_1,\, \epsilon^{2/3}\mathfrak G_p(R) \right\} \le \epsilon^{2/3}\mathfrak G_p .\]
It remains to prove the matching lower bound. Taking \(r_\star=R_\star\epsilon^{-1/3}\), we have \(r_\star\ge1\) for sufficiently small \(\epsilon\). Also, for sufficiently small \(\epsilon\), \(\epsilon^{2/3}\mathfrak G_p\le L_1\). Therefore \[\Gamma_p \ge \Gamma_p(r_\star) = \min\left\{ L_1,\, \epsilon^{2/3}\mathfrak G_p(R_\star) \right\} = \epsilon^{2/3}\mathfrak G_p\] for sufficiently small \(\epsilon\). Together with the upper bound, this proves \(\Gamma_p=\epsilon^{2/3}\mathfrak G_p\). ◻
Lemma 6 (Path Green-kernel estimate). Let \(0<h\le 1\), let \(M\in\mathbb{N}\) satisfy \(c_M h^{-1}\le M\le C_M h^{-1}\) for fixed positive absolute constants \(c_M,C_M\), and let \[A_h:=h^2 I_M+\mathsf P_M, \qquad H:=L_1 A_h=\gamma I_M+L_1\mathsf P_M, \qquad h=\sqrt{\gamma/L_1}.\] Then there exist positive constants \(c,C\), depending only on \(c_M,C_M\), such that for all \(i,j\in[M]\), \[\frac{c}{L_1h}\exp(-C h|i-j|) \le (H^{-1})_{ij} \le \frac{C}{L_1h}\exp(-c h|i-j|).\] Equivalently, \[(H^{-1})_{ij} = \Theta\!\left( \frac{1}{\sqrt{\gamma L_1}} \exp(-\Theta(h|i-j|)) \right).\]
Proof. The case \(M=1\) is immediate, since then \(A_h=h^2I\) and the assumption \(M\asymp h^{-1}\) forces \(h\asymp1\). Assume \(M\ge2\), and write \(A=A_h\). In coordinates, \[A= \begin{pmatrix} 1+h^2 & -1 \\ -1 & 2+h^2 & -1 \\ & \ddots & \ddots & \ddots \\ && -1 & 2+h^2 & -1 \\ &&& -1 & 1+h^2 \end{pmatrix}.\]
We use the standard inverse formula for tridiagonal matrices in the following form. For a tridiagonal matrix with diagonal entries \(\alpha_1,\ldots,\alpha_n\) and off-diagonal entries \(-\beta_1,\ldots,-\beta_{n-1}\), define \(\delta_1=\alpha_1\), \(\delta_{k+1}=\alpha_{k+1}-\frac{\beta_k^2}{\delta_k}\), \(d_n=\alpha_n\), and \(d_{k-1}=\alpha_{k-1}-\frac{\beta_{k-1}^2}{d_k}\). Then, with \[b_i=\frac{\beta_1\cdots\beta_{i-1}}{d_1\cdots d_i}, \qquad a_i=\frac{\beta_i\cdots\beta_{n-1}}{\delta_i\cdots\delta_n\, b_n},\] the inverse entries are \(a_{i\wedge j}b_{i\vee j}\). In our case, \[\alpha_1=\alpha_M=1+h^2,\qquad \alpha_k=2+h^2\quad(2\le k\le M-1), \qquad \beta_k=1.\] Thus for \(i\le j\), using the convention that empty products equal \(1\), \[(A^{-1})_{ij} = \frac{ (\delta_1\cdots\delta_{i-1})(d_{j+1}\cdots d_M) }{ \delta_1\cdots\delta_M }. \]
Let \(\eta\in(0,1)\) be the smaller root of \(s^2-(2+h^2)s+1=0\), namely \(\eta=\frac{2+h^2-h\sqrt{h^2+4}}{2}\), so that \(\eta+\eta^{-1}=2+h^2\). Set \(\Delta_k:=\delta_1\cdots\delta_k\), with \(\Delta_0:=1\). For \(0\le k\le M-1\), \[\Delta_k = \eta^{-k}\frac{1+\eta^{2k+1}}{1+\eta},\] and the final endpoint gives \[\Delta_M = \eta^{-M}\frac{(1-\eta)(1-\eta^{2M})}{1+\eta}.\] Similarly, by reversing the path, \[d_{j+1}\cdots d_M = \eta^{-(M-j)} \frac{1+\eta^{2(M-j)+1}}{1+\eta}.\] Substituting these formulas into \((*)\), and then using symmetry, yields \[(A^{-1})_{ij} = \frac{ \eta^{|i-j|+1} (1+\eta^{2(i\wedge j)-1}) (1+\eta^{2(M-i\vee j)+1}) }{ (1-\eta^2)(1-\eta^{2M}) }.\] Since \(1-\eta=\frac{h}{2}\left(\sqrt{h^2+4}-h\right)\), we have \(1-\eta\asymp h\), \(1-\eta^2\asymp h\), and \(-\log\eta\asymp h\) for \(0<h\le1\). Because \(M\asymp h^{-1}\), \(1-\eta^{2M}\asymp1\). The remaining factors are bounded between positive absolute constants, and therefore \[c h^{-1}e^{-C h|i-j|} \le (A^{-1})_{ij} \le C h^{-1}e^{-c h|i-j|}.\] Finally, \(H^{-1}=L_1^{-1}A_h^{-1}\), so \[(H^{-1})_{ij} \asymp \frac{1}{L_1h}e^{-\Theta(h|i-j|)} = \frac{1}{\sqrt{\gamma L_1}}e^{-\Theta(h|i-j|)}.\] ◻
We now prove Lemma 4.
Proof of Lemma 4. Let the parameters be chosen as in Condition 2 and set \(h:=\sqrt{\gamma/L_1}\), \(W:=L_1^{1/4}\epsilon\gamma^{-5/4}\), \(j_\star:=\lfloor M/2\rfloor\), and \(S:=\{j_\star,\ldots,M\}\). Thus \(a=\mathbf{1}_S/W\), \(M\asymp h^{-1}\), \(\gamma\asymp\Gamma_p\), \(M\asymp L_1^{1/2}\gamma^{-1/2}\), and \(N\asymp\Delta\gamma/\epsilon^2\). Let \(e,\rho,\alpha,\beta\) be the quantities in ?? for the present \((M,\gamma,L_1,a)\), and set \(H:=H_{\gamma,L_1}^{(M)}\).
We first check the quantities that enter Lemmas 1 and 3. Lemma 6 gives \[(H^{-1})_{ij} \asymp (\gamma L_1)^{-1/2}\exp(-\Theta(h|i-j|)).\] Taking \(i=j=1\) gives \(\rho\asymp(\gamma L_1)^{-1/2}\). For the suffix quantities, \(|S|\asymp h^{-1}\) and \(h|j-1|\asymp1\) for \(j\in S\), so \[\|a\| = \frac{\sqrt{|S|}}{W} \asymp \frac{\gamma}{\epsilon},\] and \[\alpha = \frac{1}{W}\sum_{j\in S}(H^{-1})_{j1} \asymp \frac{1}{W} h^{-1}(\gamma L_1)^{-1/2} = \frac{\gamma^{1/4}}{L_1^{1/4}\epsilon}.\] Also, for each \(i\in S\), \[\sum_{j\in S}(H^{-1})_{ij} \asymp h^{-1}(\gamma L_1)^{-1/2} = \gamma^{-1},\] and therefore \[\beta = \frac{1}{W^2}\sum_{i,j\in S}(H^{-1})_{ij} \asymp \frac{1}{W^2}h^{-1}\gamma^{-1} = \frac{\gamma}{\epsilon^2}.\] In particular, \(\tau=\frac{1}{\beta}\asymp\frac{\epsilon^2}{\gamma}\) and \(\frac{\rho}{\alpha^2}\asymp\frac{\epsilon^2}{\gamma}\). The choice \(r=r_\star\) and \(\gamma=c_{\rm hp}\Gamma_p\), with \(c_{\rm hp}\) sufficiently small, imply \(\ell_qr^{3-q}\gamma^q\epsilon^{1-q}\lesssim L_q\), \(q=1,\ldots,p\). Substituting the calibrated orders into Lemma 1 gives \[\begin{align} \operatorname{Lip}\!\left(\nabla f_{\Delta,L_{1:p},\epsilon}\right) &\lesssim L_1 + \frac{\|a\|}{\alpha} + \left( \frac{\rho}{\alpha^2} + \frac{\ell_1r^2}{\beta} \right)\|a\|^2 \\ &\asymp L_1 + L_1^{1/4}\gamma^{3/4} + \gamma + \ell_1r^2\gamma \lesssim L_1 . \end{align}\] For \(q=2,\ldots,p\), \[\operatorname{Lip}\!\left(D^q f_{\Delta,L_{1:p},\epsilon}\right) \lesssim \frac{\ell_qr^{3-q}\|a\|^{q+1}}{\beta} \asymp \ell_qr^{3-q}\gamma^q\epsilon^{1-q} \lesssim L_q .\] It remains to ensure that the calibrated initial gap is at most \(\Delta\). The tolerance assumption supplies the needed lower bound on \(\Gamma_p\). Since \(\Gamma_p\ge\Gamma_p(1)\), it is enough to lower bound every term in \(\Gamma_p(1)\) by a constant multiple of \(\epsilon^2/\Delta\). The \(q=1\) part of the tolerance assumption gives \(\frac{L_1}{\ell_1}\gtrsim\frac{\epsilon^2}{\Delta}\), which controls the \(L_1/\ell_1\) term in \(\Gamma_p(1)\). It also controls the \(L_1\) term, since \(L_1=\ell_1(L_1/\ell_1)\) and \(\ell_1\) is a fixed numerical constant: \(L_1\gtrsim\frac{\epsilon^2}{\Delta}\). For \(q=2,\ldots,p\), the same assumption gives \[\frac{L_q}{\ell_q} \gtrsim \frac{\epsilon^{q+1}}{\Delta^q},\] and hence \[\left(\frac{L_q\epsilon^{q-1}}{\ell_q}\right)^{1/q} \gtrsim \frac{\epsilon^2}{\Delta}.\] Thus \(\Gamma_p(1)\gtrsim\epsilon^2/\Delta\). After decreasing \(c_\epsilon\) by an absolute factor if necessary, this gives \(\epsilon^2/\gamma\lesssim\Delta\). The initial gap bound from the same lemma gives \[f_{\Delta,L_{1:p},\epsilon}(0) - \inf f_{\Delta,L_{1:p},\epsilon} \lesssim N\tau+\frac{\rho}{\alpha^2} \lesssim c_N\Delta+\frac{\epsilon^2}{\gamma} \le \Delta,\] after choosing \(c_N\) sufficiently small. Thus \(f_{\Delta,L_{1:p},\epsilon}\in \mathcal{F}_{1:p}(\Delta,L_1,\ldots,L_p)\), after only absolute-constant adjustments in the calibration.
It remains to turn the calibrated gradient certificate into an iteration lower bound. The denominator in Lemma 3 has scale \(\sqrt{\beta}\asymp\frac{\sqrt{\gamma}}{\epsilon}\) and \(\frac{\beta\sqrt{\rho}}{\alpha}\asymp\frac{\sqrt{\gamma}}{\epsilon}\), so whenever \(a^\top z_N=0\), Lemma 3 gives \(\left\|\nabla f_{\Delta,L_{1:p},\epsilon}(z)\right\|\gtrsim\epsilon\). If the hidden absolute constant is smaller than one, we run the same construction with a fixed larger multiple of the target tolerance; this changes all displayed rates only by absolute factors. Let \(\mathsf A\) be any first-order zero-respecting method and let \(z^{(t)}\) be its iterates on \(f_{\Delta,L_{1:p},\epsilon}\). Since \(\operatorname{supp}(a)\subseteq\{j_\star,\ldots,M\}\), Lemma 2 gives the hiding condition \(a^\top z_N^{(t)}=0\) for every \(t<Nj_\star\). Consequently no such iterate is \(\epsilon\)-stationary. Since \(j_\star\asymp M\), \[T_\epsilon\bigl(\mathsf A,f_{\Delta,L_{1:p},\epsilon}\bigr) \ge Nj_\star \asymp NM \asymp \frac{\Delta\gamma}{\epsilon^2} \sqrt{\frac{L_1}{\gamma}} \asymp \Delta L_1^{1/2}\Gamma_p^{1/2}\epsilon^{-2}.\] ◻
Department of Computer Science, Indiana University Bloomington, IN 47408, USA; e-mail: dz13@iu.edu↩︎