pages/claim-3-outer-loop/page.md

# Claim 3: constant-step outer-loop complexity

```json
{"type":"markdown","id":"claim_3_exact_counterexample","created_at":"2026-07-29T09:13:00+00:00","title":"Claim 3: exact constant-step counterexample"}
```

## Registered claim

Theorem 1 states that, under smoothness, Lipschitz gradient, bounded stochastic
gradient variance, and controlled inner-sampling error, a **constant** step size
(r=O(1/L_\Phi)) needs (S=O(1/\epsilon_{opt}^2)) outer iterations to reach

\[
\mathbb E\|\nabla\Phi(\theta^S)\|^2\le\epsilon_{opt}^2.
\]

The previous revision reconstructed the exponent numerically but never ran the
actual outer loop.  The exact outer loop below falsifies the universal claim.

## One-dimensional instance satisfying every stated assumption

Take

\[
\Phi(\theta)=\frac12\theta^2,\qquad L_\Phi=1,
\]

Use the loss (\ell(\theta,z)=\theta^2/2+\theta z) with the exact inner target
uniform on (z\in\{-1,1\}).  Its theta-gradient is 1-Lipschitz in z, and it
produces the unbiased stochastic gradient

\[
\widehat g_s=\theta_s+\xi_s,
\qquad \Pr(\xi_s=1)=\Pr(\xi_s=-1)=\frac12.
\]

This objective is globally smooth and lower bounded.  The estimator has bias
zero and uniformly bounded conditional variance σ^2=1.  The inner sampler is
already the exact target, so δ_sample=0; the required
(O(\epsilon_{opt}/L_f)) condition is then satisfied for every epsilon.  The
Lipschitz-gradient assumption holds with (L_f=1).

Choose the allowed constant step (r=1/4=O(1/L_\Phi)) and theta_0=1.  The actual
outer-loop update is

\[
\theta_{s+1}=\frac34\theta_s-\frac14\xi_s.
\]

Writing (m_s=\mathbb E\theta_s) and
(v_s=\operatorname{Var}(\theta_s)), independence and zero mean give the exact
recurrences

\[
m_s=\left(\frac34\right)^s,
\qquad
v_{s+1}=\frac9{16}v_s+\frac1{16},quad v_0=0.
\]

Therefore

\[
v_s=\frac17\left(1-\left(\frac9{16}\right)^s\right),
\qquad
\mathbb E\|\nabla\Phi(\theta_s)\|^2=m_s^2+v_s.
\]

For every s>=1 this expected squared gradient is at least 1/16, and it
converges to 1/7.  Consequently, for any epsilon_opt<1/4, **no number of
iterations after the first update** can satisfy the claimed stationarity
criterion.  In particular, increasing S as (O(1/\epsilon_{opt}^2)) does not
remove the constant-step variance floor.

## The pinned proof exposes the same missing condition

The source proof concludes with

\[
\frac1S\sum_{s=0}^{S-1}\mathbb E\|\nabla\Phi(\theta_s)\|^2
\le \frac{4(\Phi(\theta^0)-\Phi_{inf})}{rS}
+4(L_f\delta_{sample})^2+2L_\Phi r\sigma^2.
\]

The final term is constant when r and sigma^2 are fixed.  To obtain arbitrary
epsilon stationarity one additionally needs, for example,
(r\sigma^2=O(\epsilon_{opt}^2)), a growing minibatch that reduces the variance,
or a diminishing step size.  None is present in the registered theorem.
Moreover, the displayed source bound is for an average/random iterate, while
the theorem claims the last iterate theta^S; that strengthening is also not
established by the telescoping argument.

## CPU-only exact certificate

`code/outer_loop_counterexample.py` evaluates 4,096 recurrence steps using only
`fractions.Fraction`, verifies the closed form at every step, and confirms the
1/16 lower floor and 1/7 limit.

```bash
python3 code/outer_loop_counterexample.py
```

## Verdict

**FALSIFIED.** Under the assumptions as registered, constant-step stochastic
noise prevents arbitrary epsilon stationarity.  The exponent identity by
itself hid this missing scope condition.