不可知学习通常被认为是计算困难的，即使对于简单的假设类（如半空间），在一般分布下也没有已知的高效算法。