We say that a learning rule A is an AERM (Asymptotic Empirical Risk Minimizer) with rate...

 

Transcribed Image Text:

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). 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).

Answer rating: 100% (QA)

To prove this theorem well use the definitions of onaveragereplaceonestable e1m and AERM e2m and the... View the full answer