Stability bound: does the gap go to 0?
R(f(Sₙ)) ≤ R_Sₙ(f(Sₙ)) + βₙ + (2nβₙ + M)·√(log(1/δ)/(2n))
loss bound M
δ
your own rate βₙ = n^(−α), α =
quiz mode
hide the answers
The gap vanishes iff βₙ → 0
and
√n·βₙ → 0, i.e. βₙ = o(1/√n). The term 2nβₙ·√(log(1/δ)/(2n)) behaves like √n·βₙ; the term M·√(log(1/δ)/(2n)) always goes to 0.