← Proof Notes
Counterexample / Transformers & in-context learning

Insufficient radius control in perturbed gradient descent

Transformers as Statisticians: Provable In-Context Learning with In-Context Algorithm Selection ↗

348 citations ↗Semantic Scholar · 2026-09-09

2023 · arXiv v2 (6 July 2023); NeurIPS 2023 published version · Reviewed 09 September 2026

An explicit example contradicts the selected statement as written.

Paper context

Overview

This paper constructs transformers that carry out familiar learning algorithms, such as regression and gradient descent, using examples in a prompt without updating the transformer’s weights. It also shows how a single transformer can select an algorithm or task from the supplied data. The analysis gives quantitative prediction and pretraining guarantees for specified statistical settings, alongside experiments on algorithm selection.

Role of the theoretical result

The selected lemma controls how errors accumulate when transformer layers approximate successive steps of convex gradient descent, supporting quantitative guarantees for that construction. Its failure means the argument needs a valid bound keeping the iterates inside the region where the update is controlled; it does not invalidate every construction in the paper.

Original paper ↗

01 / Summary

Summary of the result

The local-smoothness argument identifies a bound relative to the minimizer with a bound relative to the origin. Starting from zero, nonexpansiveness yields an origin-radius bound involving 2‖w*‖, rather than ‖w*‖. Under the stated radius condition, an admissible perturbation can consequently leave the smoothness domain. A one-dimensional convex C³ objective gives an accumulated error of 2.1 after two steps, exceeding the claimed bound of 0.2.

02 / Statement

Statement under review

arXiv v2 Lemma 14, PDF pp.11–12; proof Appendix C.4, p.40. Published NeurIPS Lemma D.1, p.28; proof Appendix E.3, p.34. · paraphrased

Approximate convex gradient descent started at zero accumulates at most L times the per-step error and stays within a specified radius, assuming smoothness only inside a ball.

∥w^L−wGDL∥2≤Lε,∥w^L∥2≤R/2+Lε≤R.\|\widehat w^L-w^L_{\rm GD}\|_2\le L\varepsilon,\qquad\|\widehat w^L\|_2\le R/2+L\varepsilon\le R.
Relevant assumptions ↘
  • f is convex on the whole Euclidean space and has a minimizer w*.
  • Its gradient is L_f-Lipschitz on the origin-centred ball B(R); global smoothness is not required.
  • R>=2||w*||, eta<=2/L_f, both initial iterates are zero, each additive perturbation has norm at most epsilon, and L<=R/(2epsilon).

03 / Derivation

Counterexample and derivation

5 steps · complete derivation
  1. 01

    Choose a locally smooth convex objective

    Take the quadratic centred at 1 and add a positive quartic term only to the right of 2. The function is globally convex and C3; on [-2,2] it is exactly the quadratic, with gradient Lipschitz constant 1. Its unique minimizer is 1.

    f(w)=12(w−1)2+250(w−2)+4,f′(w)=w−1+1000(w−2)+3.f(w)=\tfrac12(w-1)^2+250(w-2)_+^4,\quad f\prime(w)=w-1+1000(w-2)_+^3.
  2. 02

    Check every numerical hypothesis

    Use R=2, L_f=1, eta=2, epsilon=0.1, and two steps. R=2|w*|, eta=2/L_f, and 2<=R/(2epsilon)=10. The perturbations are (0.1,0).

    (R,Lf,η,ε,L)=(2,1,2,0.1,2),(e0,e1)=(0.1,0).(R,L_f,\eta,\varepsilon,L)=(2,1,2,0.1,2),\quad(e^0,e^1)=(0.1,0).
  3. 03

    Compute the exact trajectory

    The first gradient is -1, so exact gradient descent moves from 0 to 2. At 2 the gradient is 1, so the next exact iterate returns to 0.

    wGD0=0,wGD1=2,wGD2=0.w^0_{\rm GD}=0,\quad w^1_{\rm GD}=2,\quad w^2_{\rm GD}=0.
  4. 04

    Compute the perturbed trajectory

    The first perturbed iterate is 2.1, already outside B(2). There the gradient is 1.1+1=2.1. The next perturbed iterate is therefore -2.1.

    w^1=2.1,f′(2.1)=2.1,w^2=2.1−2(2.1)=−2.1.\widehat w^1=2.1,\quad f\prime(2.1)=2.1,\quad\widehat w^2=2.1-2(2.1)=-2.1.
  5. 05

    Compare with both claimed bounds

    The final error is 2.1 while the claimed accumulated-error bound is 0.2. Already at the first step, the claimed radius bound is 1.1 while the iterate is 2.1. The proof’s final induction instead bounds distance to w*, which does not establish membership in the required ball about zero.

    ∣w^2−wGD2∣=2.1>0.2;∣w^1∣=2.1>1.1.|\widehat w^2-w^2_{\rm GD}|=2.1>0.2;\quad|\widehat w^1|=2.1>1.1.

Counterexample

For the specified convex objective, the exact iterates are (0, 2, 0), whereas the perturbed iterates are (0, 2.1, −2.1). Both the radius assertion and the two-step error bound fail.

f(w)=12(w−1)2+250(w−2)+4,0→2→0,0→2.1→−2.1,2.1>2ε=0.2.f(w)=\frac12(w-1)^2+250(w-2)_+^4,\quad 0\to2\to0,\quad0\to2.1\to-2.1,\quad2.1>2\varepsilon=0.2.

04 / Implications

Implications and proposed correction

Theoretical implications

Affected result

Lemma D.1 is false under its stated local-smoothness assumptions. The published text explicitly uses it to justify linear error accumulation in Theorem D.1; that use needs a valid domain argument. This is not a counterexample to every transformer construction or to the broad claim that transformers can implement learning algorithms.

Empirical scope

Relation to reported experiments

The counterexample does not evaluate the paper’s empirical in-context learning results.

Proposed correction

Sufficient conditions and revised bound

For a fixed horizon L, a sufficient domain condition is 2||w*||+L epsilon<=R. Replace the origin-radius assertion by ||w_hat^l||<=2||w*||+l epsilon, and retain the local nonexpansiveness induction within that ball. Alternatively assume global L_f-smoothness for the accumulated-error claim; that alone does not restore the erroneous R/2 origin bound. From initialization zero, nonexpansiveness gives ||w_hat^l-w*||<=||w*||+l epsilon. The triangle inequality then gives the stated corrected origin bound. Under the stronger headroom condition all update inputs remain in the smoothness region, making the induction legitimate.

2∥w∗∥+Lε≤R⟹∥w^ℓ∥≤2∥w∗∥+ℓε≤R.2\|w^*\|+L\varepsilon\le R\quad\Longrightarrow\quad\|\widehat w^\ell\|\le2\|w^*\|+\ell\varepsilon\le R.

Implementation implications

Enlarge the smoothness and update-approximation region, or use a separately analysed projected algorithm. Projection changes the update rule and is not a silent repair of the original construction.

Limits of this review

  • The witness is for the supporting stability lemma, not a complete refutation of Theorem D.1’s existential network claim.
  • Global smoothness would restore the linear accumulated-error estimate but not the stated origin-radius estimate.
  • The downstream ICLR 2026 paper is cited only as an observed reuse; no finding about its full theorems is made.

05 / References

Sources and correction history

  1. 01
    Published NeurIPS paper ↗

    Lemma D.1 and its use after Theorem D.1, p.28; proof p.34

  2. 02
    arXiv v2 ↗

    Lemma 14, pp.11–12; proof Appendix C.4, p.40

  3. 03
    Author publication page ↗

    Publication listing checked for a revised or correction link

  4. 04
    Author code repository ↗

    All-state issue listing was empty on retrieval

  5. 05
    Later reuse: In-Context Algorithm Emulation in Fixed-Weight Transformers ↗

    Lemma D.4, p.34, reproduces the same local-smoothness statement; only this reuse was checked

Download the arithmetic witnesses · Python, no dependencies ↓
Correction search · 09 September 2026

2026-09-09 Fresh arXiv history confirms latest v2, 6 July 2023. Re-read exact arXiv and published NeurIPS statements and complete short proof; visually checked the published statement. Exact-title searches with correction, erratum, mistake, Lemma 14, Lemma D.1, and the descriptive lemma name. Fresh all-state author repository issue listing contained zero issues. Author publication page checked. Indexed OpenReview versions and a later ICLR 2026 lemma repeat the same assumptions and bound; no repair identified. No explicit qualification, replacement lemma, or addressing discussion for this domain escape was found in the inspected material. OpenReview direct PDF and API access returned 403; its indexed snippets cannot certify the full discussion history. No exhaustive audit of all later applications was performed.

A bounded search is not evidence of priority or proof that no correction exists.

Entirely AI-generated analysis, including cross-checks by separate AI agents; no independent human verification. Authors have not been contacted. Review standard.

Suggest a correction with a source ↗
Next analysisPrior total variation does not control conditional label agreement