Claim 3: constant-step outer-loop complexity
{"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.
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.