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

claim-3-outer-loop

---

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.

{
 "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"
}