Simultaneous O(1/(nt)) Rate in Contaminated PAC Learning

Interactive exploration of convergence rates in iterative learning with label contamination. Based on the open problem from Amin et al. (2026).

25
5

Error Convergence (Linear Scale)

Error Convergence (Log-Log Scale)

Rate Exponent vs Contamination

Error Ratio to Theoretical Bounds

Key Findings

Gap Exists For α > 0, the empirical convergence rate is consistently closer to O(t-1/2) than O(t-1), suggesting the simultaneous O(1/(nt)) rate is not achievable.
No Contamination At α = 0, the O(1/(nt)) rate is trivially achievable, matching classical PAC bounds.
Recursive Barrier The contamination creates a feedback loop: noise at round t depends on error at round t-1, fundamentally limiting simultaneous convergence.
Reweighting Helps Constants Reweighted ERM improves constant factors by ~15% but does not change the asymptotic rate exponent.