Optimal mistake bound learning is hard
The authors have suggested and established the fact that a combinatorial function \(K\) can be constructed in polynomial time for a given optimal MB learning algorithm as subroutine. It is also same as the reverse reduction theorem of Little Stone. Subsequently, the authors have established that the \(k\)-dimension problem and optimal MB learning have the same time complexity.
scientific article; zbMATH DE number 1220704