# Claim C1 — classical comparison-oracle complexity

## Exact registry claim

> Algorithm outputs ε-stationary point using Õ(n²/ε^1.5) queries to comparison oracle

Registry status: `unverified`.

## Public sources

- [Immutable official claim-feed snapshot](https://huggingface.co/spaces/ICML-2026-agent-repro/challenge/resolve/7b5b56aebf3abe590eab9f2c241a796125cab928/claims.json)
- [arXiv record for 2606.27082v1](https://arxiv.org/abs/2606.27082v1)
- [arXiv PDF](https://arxiv.org/pdf/2606.27082v1)
- [arXiv TeX source archive](https://export.arxiv.org/e-print/2606.27082v1)

## Source-only crosswalk

**Exact anchors.** Informal: `main_2.tex:195–203`, including informal
Theorem 1 at `197–199`; PDF pp. 2–3. Formal: `main_2.tex:1307–1355`,
including the ε-second-order definition at `1312–1318`, Algorithm 5 at
`1320–1351`, and Theorem 8 at `1353–1355`; PDF pp. 22–23.

**Assumptions.** The informal result states an `L1`-Lipschitz gradient,
`L2`-Lipschitz Hessian, an initial gap at most `Δ`, and success probability at
least `2/3`. The formal result states the same smoothness conditions,
`x* = argmin f`, `f(x0)-f(x*) ≤ Δ`, and success probability at least `2/3`.

**Source-stated conclusion.** Informally, `best-of-all` *visits* an
ε-stationary point using `~O(Δ sqrt(L2) n² / ε^1.5)` comparison-oracle
queries. Formally, Algorithm 5 *outputs a list* of `O(1/ε^1.5)` points that
contains at least one ε-second-order stationary point, with the stated
`~O(Δ sqrt(L2) n² / ε^1.5)` overall query complexity.

**Wording difference.** The registry says the algorithm *outputs* an
ε-stationary point. The informal source statement says *visits* one and warns
that comparison access cannot generally test stationarity. The formal statement
outputs a **list** containing an ε-**second-order** stationary point. These are
not interchangeable phrasings.

## Fixed outcome

**not assessed**

No proof audit, implementation, execution, result, reproduction, score, or
claim verification is contained or asserted by this page.