Lower Bound Extends Beyond Tensor Algorithms

Higher-order oracle methods can query derivatives through order $p$, so lower bounds for them must rule out more than a particular update formula. Previous minimax lower-bound machinery applied to tensor algorithms that used prescribed regularized Taylor-model updates. This paper argues that restriction is unnecessary: for smooth convex--concave problems on compact product domains, arbitrary adaptive deterministic and randomized algorithms face the same accuracy exponent for tangent residual and saddle-gap criteria.

Core Contribution

For $p\geq2$, with the $p$-th derivative Lipschitz constant bounded by $L_p$, the paper defines $Q_{\mathrm{tan}}=L_pD_Z^p/\epsilon$ and $Q_{\mathrm{gap}}=L_pD_Z^{p+1}/\epsilon$. Its central theorem places randomized and deterministic oracle complexity between a lower bound proportional to $Q_E^{2/(3p-1)}$ and an existing upper bound with that exponent multiplied by $[1+\log(3+Q_E)]^{6(p-1)}$. Randomization does not improve the exponent, provided the algorithm must succeed with probability at least $2/3$ on every instance.

That is a meaningful strengthening of the earlier restricted-class result. The paper does not propose a faster solver; it characterizes what any solver can achieve when each feasible query exposes the objective value and every derivative through order $p$. The remaining logarithmic gap means the result is near-optimal rather than an exact minimax characterization.

Technical Approach

The hard instance begins as a scalar convex--concave chain. Its role is to make progress depend on reaching a terminal chain coordinate: if that coordinate stays small, both the tangent residual and the primal--dual gap remain bounded away from zero. The construction then uses smooth, exactly flat gates and rotates the chain into hidden orthogonal directions. Exact flatness is the key device. At a query outside a gate's active region, the gate contributes no derivative information at any order through $p$, rather than merely contributing a small signal.

The product-domain geometry is handled explicitly rather than inferred from an unconstrained construction. The authors choose Euclidean balls for the primal and dual domains with radius $R=D_Z/(2\sqrt{2})$, then scale the potential so its $p$-th derivative has Lipschitz constant at most $L_p$. Lemma 4.8 lower-bounds the tangent residual by a constant multiple of $\lambda c/\sqrt n$, while Lemma 4.9 lower-bounds the saddle gap by a constant multiple of $\lambda c^2$. The latter proof treats both interior points, where feasible witness steps remain inside the balls, and boundary points, where strong convexity--concavity supplies separation from the interior saddle point.

The information argument differs for deterministic and randomized policies. For a deterministic algorithm making $N$ feasible queries, Proposition 5.1 chooses a fresh orthogonal frame after each query in dimensions $d_x=d_y=2N+2$. Each oracle answer can reveal at most one new frame pair; after the output is fixed, a final orthogonal pair completes the potential while preserving all previous answers. The construction leaves the final chain coordinates $a_n=b_n=0$ at the output.

For randomized algorithms, the frame is sampled before the run from independent Haar orthonormal frames. A concentration lemma bounds inner products between adaptive query points and unrevealed directions when the ambient dimension is sufficiently large. This couples the randomized transcript to the gated hard instance: with high probability, the algorithm still cannot access the hidden coordinates quickly enough.

Results and Analysis

The result applies to both error criteria, which matters because tangent residual and saddle gap require different geometric witnesses. For sufficiently large $Q_E$, the paper gives

Here $c_p$ and $C_p$ depend only on $p$. Relative to the cited upper bound, the lower bound establishes that the polynomial accuracy dependence cannot be improved by abandoning Taylor-model tensor updates, changing feasible outputs, or introducing randomness. That makes the exponent persuasive evidence about the oracle model itself, not just one family of methods.

The evidence is theoretical rather than experimental. There are no empirical benchmarks, runtime measurements, or implementation results, and the theorem assumes a high-dimensional setting, compact convex product domains, smooth convex--concave objectives, and complete $p$-jet access at every query. Those assumptions are appropriate for oracle complexity, but they limit direct conclusions about finite-dimensional implementations or methods that only approximate higher derivatives.