学习的统计复杂度与计算复杂度

三条资源轴 ​

一个学习结论至少可按三元组审视：达到 $(\epsilon ,\delta )$ 所需样本数；处理这些样本所需时间或查询；输出预测器的表示与评价成本。小 VC 维约束第一轴，不会自动解决后两轴。

某类可能用很少样本便唯一确定，但寻找一致假设是 NP-hard；也可能精确 ERM 困难，却有 improper learner 或代理优化高效学习。反之，计算约束有时迫使算法使用更多样本，形成统计—计算间隙。

证明边界 ​

“一个 ERM 公式 NP-hard”只排除了该求解路线，不证明所有学习器困难；正式困难性需把假设问题归约到任何满足指定风险保证的算法，并明确 properness、分布族和计算假设。非凸目标也不等于不可学，最坏复杂度与经验训练速度更不能互换。

优化误差是第三种量：即使算法多项式时间，也只可能得到近似经验最优；它如何进入总体风险要借助统一泛化与误差分解。将三轴分开不是拆散问题，而是定位瓶颈究竟由数据、计算还是表示造成。

一个诊断表述是：先问是否存在用 $m=\mathrm{poly}(n,1/\epsilon )$ 个样本达到目标的任意学习器；再问它能否在相同参数的多项式时间内构造；最后问输出是否能被多项式长度编码并高效评价。第一问否定是信息论障碍，增加算力无济于事；第一问肯定而第二问否定，才是统计—计算缺口。

例如某个 proper ERM 搜索可归约为 NP-hard 问题，只能说明该类内精确优化路线困难。若存在凸松弛输出类外投票，并仍与原类最优风险比较，improper learner 可能绕过它。真正学习困难下界必须让任何满足风险保证的算法都能解出假设中的困难问题，而非把“目标非凸”当作证明。

参考资料

• Kearns, Vazirani, 1994.
• Daniely et al., works on computational hardness of learning.