We say that a learning rule A is an AERM (Asymptotic Empirical Risk Minimizer) with rate (m) if for every distribution D it holds that E S~Dm - min Ls (h) e(m). [Ls(A(S)) min] We say that a learning rule A learns a class H with rate (m) if for every distribution D it holds that E - S~Dm [LD (A(S)) min LD (h)] c(m). : Prove the following: THEOREM If a learning algorithm A is on-average-replace-one-stable with rate 1 (m) and is an AERM with rate 62(m), then it learns H with rate 1 (m) + 2(m).