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

# claim-3-outer-loop


---
<!-- trackio-cell
{"type": "markdown", "id": "cell_f04ef9a1e048", "created_at": "2026-07-30T08:19:10+00:00", "title": "Claim 3 \u2014 exact counterexample, FALSIFIED", "pinned": true, "pinned_at": "2026-07-30T08:19:10+00:00"}
-->
## Claim 3 — constant-step outer-loop complexity (Theorem 1)

> "Theorem 1 proves the outer loop of the gradient-flow-sampler-based DRO algorithm requires `O(1/ε²_opt)` iterations to reach an ε-stationary point."

The registered theorem states: under smoothness (`Φ` is `L_Φ`-smooth), Lipschitz-gradient, bounded stochastic-gradient variance, and controlled inner-sampling error `δ_sample=O(ε_opt/L_f)`, a **constant** step size `r=O(1/L_Φ)` reaches `E‖∇Φ(θ^S)‖² ≤ ε²_opt` after `S=O(1/ε²_opt)` outer iterations — for **any** `ε_opt`.

**Counterexample, satisfying every stated hypothesis exactly.** Take `Φ(θ)=θ²/2` (`L_Φ=1`), and the stochastic gradient estimator `ĝ_s = θ_s + ξ_s` with `ξ_s ∈ {−1,+1}` equiprobable — unbiased, variance `σ²=1` (bounded, Assumption `as:gradest`). The inner sampler is taken to be *exact* (`δ_sample=0` exactly, trivially `O(ε_opt/L_f)` for every `ε_opt`). Choose the allowed constant step `r=1/3=O(1/L_Φ)`. The exact outer-loop update is `θ_{s+1} = (1−r)θ_s − r·ξ_s`.

Writing `m_s=E[θ_s]`, `v_s=Var(θ_s)`: `m_s=(1−r)^s·θ_0` and `v_{s+1}=(1−r)²v_s + r²` — computed here with `fractions.Fraction` (exact rational arithmetic, no floating-point rounding) for **1,500** steps, with the closed form `v_s = r²(1−(1−r)^(2s))/(1−(1−r)²)` re-verified at every single step.

- `E‖∇Φ(θ_s)‖² = m_s² + v_s → 1/5 = 0.200000` as `s→∞` (exact rational limit).
- After the very first update, `E‖∇Φ(θ_1)‖² = 17/9 ≈ 1.8889`.
- **For any `ε_opt` with `ε²_opt < 1/5 ≈ 0.2000` (i.e. `ε_opt ≲ 0.4472`), NO finite or infinite number of additional constant-step outer iterations can bring `E‖∇Φ(θ^S)‖²` below `ε²_opt`.** The claimed `S=O(1/ε²_opt)` scaling — for arbitrarily small `ε_opt` — is false under exactly the stated hypotheses.

**Why the theorem's proof sketch misses this.** The source's own telescoping bound is
`(1/S)Σ E‖∇Φ(θ_s)‖² ≤ 4(Φ(θ⁰)−Φ_inf)/(rS) + 4(L_f·δ_sample)² + 2L_Φ·r·σ²`.
The final term `2L_Φ·r·σ²` is a **constant** once `r` and `σ²` are fixed — reaching arbitrary `ε_opt` needs an *additional* condition (e.g. `r·σ²=O(ε²_opt)`, a diminishing step size, or a growing minibatch) that is not present in the registered theorem statement. The displayed bound is also for the average/random iterate, while the theorem as registered claims the **last** iterate `θ^S` — a further unproven strengthening.

**Verdict: FALSIFIED** — under the stated hypotheses, constant-step stochastic noise creates a strictly positive variance floor that `S→∞` cannot remove.

````raw
{
 "L_Phi": 1,
 "assumptions_satisfied": {
  "as_fsmooth_L_f_lipschitz": true,
  "as_gradest_bounded_variance_and_delta_sample_O_eps_over_Lf": true,
  "as_totalsmooth_L_Phi_smooth": true
 },
 "claim3_falsified": true,
 "constant_step_r": "1/3",
 "contradicted_for_eps_opt_below_sqrt_of": "1/5",
 "delta_sample": 0,
 "eps_opt_squared_floor": "1/5",
 "exact_steps_evaluated": 1500,
 "floor_expected_grad_sq_after_first_update": "17/9",
 "floor_float": 1.8888888888888888,
 "gradient_estimator": "theta + Rademacher noise (unbiased, sigma^2=1)",
 "limit_expected_grad_sq": "1/5",
 "limit_expected_grad_sq_float": 0.2,
 "note": "For any eps_opt with eps_opt^2 < r/(2-r) = 1/5, no finite or infinite number of additional outer iterations S can bring E||grad Phi(theta^S)||^2 below eps_opt^2 -- the constant-step variance floor is strictly positive and O(1/eps_opt^2) growth in S does not remove it.",
 "objective": "Phi(theta) = theta^2 / 2"
}
````