{"id":"c681e4c5-a27a-4962-95a2-57ed910a8701","arxiv_id":"2506.17698","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"Fixed-step Halpern iteration, and the new GHAL and AdaGHAL variants, provably solve fixed-point equations for contractive, nonexpansive, mildly expansive, and the newly defined gradually expansive class of operators at near-optimal oracle complexity.","lead":"This paper shows that a simple, fixed-step version of Halpern iteration solves fixed-point equations at near-optimal speed for contractive and nonexpansive operators, and for mildly expansive operators right up to the known hardness boundary. It then defines a new class of 'gradually expansive' operators, where expansion is tied to how far the algorithm is from a fixed point, and proves an efficient O(1/ε) bound for them.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 2's safeguard parameter β' is incompatible with inequality (24): for the advertised α≤0.4 setting, the contraction upper bound exceeds the safeguard threshold, so the proof does not establish the O(D/ε) guarantee.","rationale":"The reader's weakest assumption was non-vacuity of the gradually expansive class, a legitimate significance concern. The more urgent issue is internal to Theorem 2: the proof's no-safeguard argument uses inequality (24), but the stated parameter choices violate the condition needed for that inequality to imply the safeguard never fires. This directly threatens the central O(D/ε) claim, because the safeguard's halt path returns an iterate whose certified error is only ε_{k-1} or worse, not ε. I checked the surrounding algebra: (23), (24), the inner-loop iteration count, and the geometric sum are internally consistent, so the gap is localized to the choice of β'. The theorem can very likely be repaired by choosing β'ε_k, the safeguard fires and the output error exceeds ε. Repeating with β'=0.01 should restore the no-trigger guarantee.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof of Theorem 2 hinges on the claim that the safeguard in Algorithm 1, Line 8, never fires. The only quantitative support is inequality (24), which gives ||y_{j+1}-y_j|| ≤ q_k ||y_j-y_{j-1}|| with q_k = 1 - λ_k(c+λ_k)/(1+c). The safeguard fires exactly when the observed ratio is at least 1 - β'λ_k. For the published α≤0.4 instance (β=0.975, β'=1/1.01), c≈0.011, so q_k ≈ 1 - 0.0109λ_k while the threshold is 1 - β'λ_k ≈ 1 - 0.9901λ_k. Thus q_k > 1 - β'λ_k for every λ_k∈(0,1), and in particular for λ_k=Θ(ε_k/D) as ε→0. Inequality (24) therefore cannot establish the required strict inequality ||y_{j+1}-y_j|| < (1-β'λ_k)||y_j-y_{j-1}||. If the gradual-expansion inequality (22) is tight, the safeguard fires before the fixed-point error reaches ε_k, and Algorithm 1 returns a point certified only to error ε_{k-1} (or the initial error), not ε. The proof's own no-trigger requirement is β' < c/(1+c); the stated range β'∈[1/(1+c),1), and the recommended β'=1/1.01, violate it by about two orders of magnitude. This is a concrete, localized gap in the central O(D/ε) guarantee for gradually expansive operators, independent of any concern about the applicability of Definition 1.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies oracle-based computation of ε-approximate fixed points of Lipschitz operators in normed spaces and Busemann spaces. It analyzes a fixed-step variant of Halpern iteration, proves near-optimal oracle complexity for contractive and nonexpansive operators, extends the guarantees to mildly expansive operators up to the HPV89 hardness frontier, and introduces GHAL/AdaGHAL that adapt to the unknown Lipschitz constant. The final main contribution is a new class of α-gradually expansive operators, for which GHAL is claimed to compute ε-approximate fixed points in O(D/ε) oracle queries when α≤0.4, and polynomially in general for α<√2−1. The paper also contains numerical illustrations and a discussion of open problems.","tokens_in":35136,"tokens_out":23243,"duration_ms":224726,"significance":"The parts of the paper concerning γ≤1 and mildly expansive operators are carefully argued and, if correct, constitute a genuine unification: GHAL and AdaGHAL recover the known optimal rates for contractive and nonexpansive operators and reach the HPV89 boundary for γ=1+O(ε/D). The proofs are unusually detailed; I checked the step-size algebra in Lemma 1 and the contraction chain in Theorem 2 and found no other inconsistencies. The gradual-expansion contribution is potentially significant but is currently blocked by a concrete parameter error in Theorem 2 and by the absence of nontrivial motivating examples for Definition 1.","major_comments":[{"comment":"The claim that the safeguard never fires is not supported by the stated parameter range. Inequality (24) gives ||y_{j+1}-y_j|| ≤ q_k ||y_j-y_{j-1}|| with q_k = 1 - λ_k(c+λ_k)/(1+c). The safeguard fires when the ratio is at least 1-β'λ_k, so the proof requires q_k < 1-β'λ_k, i.e. β' < (c+λ_k)/(1+c) for all λ_k, equivalently β' < c/(1+c). The theorem states β'∈[1/(1+c),1), which for c<1 is disjoint from the required interval. For the advertised α=0.4, β=0.975, c≈0.011, c/(1+c)≈0.0109, while β'=1/1.01≈0.9901; then q_k≈1-0.0109λ_k and 1-β'λ_k≈1-0.9901λ_k, so q_k exceeds the threshold for every sufficiently small λ_k. Since the safeguard halts the whole algorithm and returns a point with error at most ε_{k-1}, the stated O(D/ε) guarantee with final error ≤ε is not established; if (22) is tight, the safeguard fires before the inner loop reaches ε_k. The parameter condition (and the numerical instantiation of β' in Section 5.1.2) needs to be corrected, e.g. by taking β'0; the two forms are equivalent, but stating both without comment may confuse readers.","section":"Abstract and Section 4"},{"comment":"The reference list entry [BB96] spells the first author as 'Baillion'; the standard spelling is 'Baillon'.","section":"References"},{"comment":"In the second remark after Proposition 1, 'γ <1 +∥T(x 0−x 0∥/D' is missing a parenthesis and should read 'γ <1 + ∥T(x_0)−x_0∥/D'.","section":"Remark after Proposition 1"},{"comment":"The phrase 'largest constant c' is confusing because the displayed equation uniquely determines c; consider simply saying 'the constant c>0 defined by ...'.","section":"Theorem 2 statement"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. First, the fixed-step Halpern analysis in Section 2 is real: Lemmas 1 and 2 show a constant step size reaches ε-accuracy at near-optimal complexity for contractive and nonexpansive operators, and GHAL/AdaGHAL adapt to the contraction factor more cleanly than restart-based schemes. Second, the flagship result for gradually expansive operators—Theorem 2's O(D/ε) guarantee—is not proven as stated. I checked the stress-test concern and it holds up. The proof claims the Algorithm 1 safeguard never fires, but the contraction factor in (24) is q = 1 − λ(c+λ)/(1+c), while the safeguard threshold is 1 − β′λ. To prevent firing you need β′ < c/(1+c). For the advertised α=0.4 case (β=0.975, β′=1/1.01), c≈0.011, so c/(1+c)≈0.011 while β′≈0.99. The threshold is about two orders of magnitude too large. If the gradual-expansion inequality (22) is tight, the safeguard fires before the inner loop reaches ε_k, and the algorithm returns a point certified only to ε_{k−1}. The no-trigger claim is not a missing detail; it is numerically incompatible with the chosen parameters.\n\nWhat the paper does well: the fixed-step Halpern perspective is surprising, and the complexity results for nonexpansive, contractive, and mildly expansive operators are solid, including the boundary comparison with HPV89. The new α-gradually expansive class is genuinely new and clearly separated from prior restart-based work. The proofs in Sections 2 and 3 are checkable and, as far as I traced them, consistent. The paper is also honest about limitations—it admits the class was reverse-engineered and that the only worked example is one where Picard iteration already converges.\n\nSoft spots beyond the gap: the gradual-expansion class is non-vacuous only in a weak sense; Section 5.2.3 concedes no concrete example where standard iterations fail; and the numerical experiments are illustrative only. But these are secondary. The load-bearing issue is Theorem 2, and the rest of the paper stands independently.\n\nThis is for researchers in fixed-point complexity and oracle-efficient algorithms. It deserves a serious referee, but the referee should push for a fix to the safeguard parameter or a revised claim. If the no-trigger condition is repaired by taking β′ < c/(1+c)—still an absolute constant, so O(D/ε) would survive—the theorem is likely salvageable. As it stands, the headline guarantee for gradual expansion is unproven.","headline":"The fixed-step Halpern analysis and adaptive algorithms are solid, but Theorem 2's safeguard parameter is incompatible with the paper's own contraction bound, so the advertised O(D/ε) guarantee for gradually expansive operators is unsupported.","tokens_in":35798,"tokens_out":5130,"would_cite":true,"duration_ms":47177,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["47H09","47H10","68Q17","90C30"],"pacs":[],"model":"deepseek-v4-flash","headline":"Fixed-step Halpern iteration, with gradually shrinking step sizes, achieves near-optimal oracle complexity for contractive and nonexpansive operators and reaches epsilon-approximate fixed points of gradually expansive operators up to…","keywords":["fixed-point computation","Halpern iteration","oracle complexity","nonexpansive operators","expansive operators","gradual expansiveness","Banach spaces","adaptive algorithms"],"falsifier":"Take the paper's own example $T(x)=\\mathrm{Proj}_{[-D/2,D/2]^d}(x+\\exp(\\alpha x/D))$ with $\\alpha=0.4$, verify condition (2) on a fine grid, and run GHAL with $\\beta=0.975$, $\\beta'=1/1.01$ down to error $\\epsilon$; if any grid pair violates (2), or if the observed oracle count grows faster than a constant times $D/\\epsilon$ as $\\epsilon\\to0$, the premise or the claimed rate would be contradicted.","tokens_in":34497,"feed_emoji":"🎯","tokens_out":13511,"duration_ms":125110,"temperature":0.7,"pith_summary":"This paper asks what lies between fixed-point problems that are efficiently solvable (operators with Lipschitz constant at most one) and those that are exponentially hard (constant larger than one). It claims that a deliberately simple-looking iteration, Halpern iteration with a fixed step size, can already find $\\epsilon$-approximate fixed points at near-optimal oracle complexity for contractive and nonexpansive operators, and even tolerates expansion slightly beyond one. Building on that, it designs the Gradual and Adaptive Gradual Halpern Algorithms, which tune the step size without knowing the Lipschitz constant or the set diameter. The new frontier is the class of $\\alpha$-gradually expansive operators, where expansion is allowed to grow in proportion to the current fixed-point error; for these, the paper proves $\\epsilon$-accurate fixed points in $O(D/\\epsilon)$ iterations when $\\alpha \\le 0.4$, corresponding to Lipschitz constants up to about $1.4$. This matters because it is the first provable tractability regime beyond nonexpansiveness, placed exactly at the threshold where known exponential lower bounds begin.","feed_headline":"Halpern iteration reaches fixed points beyond the nonexpansive barrier","feed_subtitle":"Adaptive variants find epsilon-approximate fixed points in O(1/epsilon) oracle calls, right at the hardness boundary.","key_machinery":"The central object is the Gradual Halpern Algorithm (GHAL), which repeatedly runs fixed-step Halpern iteration with geometrically decreasing target errors $\\epsilon_k=\\beta^k\\epsilon_0$ and step sizes $\\lambda_k=\\beta\\epsilon_k/D$. The load-bearing mechanism is Inequality (24), which shows that inside each inner loop successive iterates contract by a factor $1-\\frac{\\lambda_k}{1+c}(c+\\lambda_k)$; this contraction holds precisely because the $\\alpha$-gradual expansiveness condition of Definition 1 was engineered to make the inner loop contract. Definition 1 bounds the excess expansion of $T$ by $\\alpha$ times the larger fixed-point error at the two points divided by the set diameter, permitting Lipschitz constants as large as $1+\\alpha$. A safeguard in GHAL detects non-contraction of successive iterates and stops with a certificate, and AdaGHAL removes the need to know the diameter by doubling an estimate $D$ whenever an iterate escapes it.","core_discovery":"The central claim is that the fixed-step Halpern iteration contracts distances between successive iterates by a factor $(1-\\lambda)\\gamma$, so it remains useful even when $\\gamma$ exceeds one, provided the step size makes $(1-\\lambda)\\gamma<1$. Lemma 1 and Lemma 2 show that this iteration produces an $\\epsilon$-approximate fixed point for $\\gamma\\in(0,1]$ in $O(\\ln(\\|T(x_0)-x_0\\|/\\epsilon)/(\\epsilon/D_*+\\ln(1/\\gamma)))$ iterations, and for mildly expansive operators with $\\gamma<1+\\beta\\epsilon/D$ in $O(\\ln(\\|T(x_0)-x_0\\|/((1-\\beta)\\epsilon))/(-\\ln((1-\\lambda)\\gamma)))$ iterations. GHAL and AdaGHAL then decrease the target error and step size geometrically, recovering the optimal complexity of contractive and nonexpansive operators without knowing $\\gamma$ or $D$. For $\\alpha$-gradually expansive operators, Theorem 2 states that with $\\alpha\\le0.4$, and more generally $\\alpha<\\sqrt{2}-1$ with polynomial bounds, GHAL outputs a point with fixed-point error at most $\\epsilon$ after $O(D/\\epsilon)$ oracle queries. Because the analysis uses only convexity of the norm or metric, all of these guarantees hold in arbitrary normed vector spaces, infinite-dimensional Banach spaces, and Busemann spaces.","pith_inferences":["The gradual-expansion condition can be read as a quantitative, point-dependent Lipschitz bound: the farther a point is from being a fixed point, the more expansion is allowed; verifying it for operators from game dynamics or nonconvex training would immediately transfer the $O(D/\\epsilon)$ guarantee to those settings, a step the paper leaves open.","Combining gradual expansiveness with a local error bound (a quantitative relation between fixed-point error and distance to the fixed-point set) could yield linear convergence near the fixed-point set, because the permitted expansion vanishes as the fixed-point error goes to zero; this is a natural extension of the paper's restart-based analysis to the new class.","The $O(D/\\epsilon)$ rate for gradual expansion is only an upper bound; a matching lower bound for this class would show whether the threshold $\\alpha=\\sqrt{2}-1$ is intrinsic to the problem or an artifact of the analysis.","Because the paper's explicit gradually expansive example is one where ordinary Picard iteration also converges, the practical reach of the new class depends on finding natural operators that satisfy Definition 1 but defeat simpler methods; until then, the result is best read as a conditional tractability statement."],"forward_implications":["One parameter-free algorithm now matches the known optimal oracle complexity for both contractive and nonexpansive operators, so a user does not need to know in advance which regime the operator belongs to.","For mildly expansive operators with $\\gamma\\le 1+c\\epsilon/D$, an $\\epsilon$-fixed point is found in $O(\\ln(1/\\epsilon)/\\epsilon)$ oracle calls, a guarantee that cannot be extended much further without exponential dependence on the dimension, by the hardness result the paper cites.","In infinite-dimensional Banach spaces, GHAL attains fixed-point error $(\\gamma-1)D+\\epsilon$ for $\\gamma\\in(1,2)$ in $O(\\gamma D\\ln(\\|T(x_0)-x_0\\|/\\epsilon)/\\epsilon)$ calls, giving a finite-query nontrivial bound for general Lipschitz operators where no fixed point need exist.","For $\\alpha$-gradually expansive operators with $\\alpha\\le0.4$, the oracle complexity is $O(D/\\epsilon)$ even though the global Lipschitz constant may be as large as about $1.4$; this is the paper's new tractable frontier.","All these iteration bounds transfer to Busemann spaces, so the complexity statements are not special to Euclidean or Hilbert geometry."],"supporting_citations":[{"why":"Supplies the exponential oracle lower bound for gamma-Lipschitz Brouwer fixed-point problems, the hardness frontier that the mildly expansive results match up to constants.","marker":"[HPV89]"},{"why":"Introduces Halpern iteration, the classical method whose fixed-step variant is the basic update of GHAL and AdaGHAL.","marker":"[Hal67]"},{"why":"Provides lower bounds and exact optimal accelerated complexity for fixed-point iterations, benchmarks GHAL and AdaGHAL must match for nonexpansive and contractive operators.","marker":"[PR22]"},{"why":"Establishes lower bounds showing that the 1/k rate of Halpern iteration is optimal for nonexpansive fixed-point computation, used for the near-optimality claims.","marker":"[DW22]"},{"why":"Gives the minimal displacement bound inf ||T(x)-x|| <= (1-1/gamma)D for gamma-Lipschitz operators, the baseline for the infinite-dimensional Banach-space error bound.","marker":"[Goe73]"},{"why":"Defines almost averaged and almost nonexpansive operators under local error bounds, the nearby framework that the paper contrasts with its new gradual expansion condition.","marker":"[LTT18]"},{"why":"Develops restart-based Halpern methods for monotone inclusions; Section 3.3 compares GHAL and AdaGHAL against this restarting strategy and shows they beat it for small gamma.","marker":"[Dia20]"},{"why":"Gives tight optimal error bounds for fixed-point iterations with different step sizes, supporting the claim that fixed-step Halpern can be near-optimal.","marker":"[CC23]"}],"fun_headline_variants":["Adaptive Halpern iteration cracks fixed points beyond nonexpansive","Gradual Halpern reaches fixed points at the hardness frontier","Beyond nonexpansive: adaptive Halpern finds fixed points fast","Fixed-step Halpern: efficient fixed points even for expansive maps","Halpern iteration tames gradual expansion beyond nonexpansive"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is the $\\alpha$-gradual expansiveness condition of Definition 1: expansion beyond Lipschitz constant one is tolerated only in proportion to the larger fixed-point error at the two points, scaled by the set diameter; if operators arising in applications do not satisfy this condition, the claimed new tractable frontier does not apply.","fun_headline_variants_meta":{"raw":{"variants":["Adaptive Halpern iteration cracks fixed points beyond nonexpansive","Gradual Halpern reaches fixed points at the hardness frontier","Beyond nonexpansive: adaptive Halpern finds fixed points fast","Fixed-step Halpern: efficient fixed points even for expansive maps","Halpern iteration tames gradual expansion beyond nonexpansive"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001064,"raw_usage":{"total_tokens":4580,"prompt_tokens":1181,"completion_tokens":3399,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":797,"completion_tokens_details":{"reasoning_tokens":3307}},"tokens_in":797,"tokens_out":3399,"duration_ms":25116,"temperature":1.0,"reasoning_tokens":3307,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T19:04:39.345082+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take the paper's own example $T(x)=\\mathrm{Proj}_{[-D/2,D/2]^d}(x+\\exp(\\alpha x/D))$ with $\\alpha=0.4$, verify condition (2) on a fine grid, and run GHAL with $\\beta=0.975$, $\\beta'=1/1.01$ down to error $\\epsilon$; if any grid pair violates (2), or if the observed oracle count grows faster than a constant times $D/\\epsilon$ as $\\epsilon\\to0$, the premise or the claimed rate would be contradicted.","supporting_citations":[],"review_version":1}