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

三条轴分别回答“数据够不够”“能不能算出来”和“结果能不能表示并部署”。把它们压成一个“复杂度”数字，会让有限 VC 维被误读为高效算法，也会让一次非凸优化失败被误读为不可学习。分开记账不是拆散问题，而是确定瓶颈究竟来自观测、求解还是输出接口。

优化误差还提供一个中间层：算法即使在多项式时间停止，也可能只得到近似经验最优。它如何进入总体风险，要通过泛化控制和误差分解连接，不能把“程序已经返回”直接等同于统计目标已经达到。

一个 proper 学习归约 ​

给定含 $m$ 个子句的 CNF 公式 $\mathrm{\Phi }$，把实例空间取为这些子句，并让每个赋值 $a$ 对应假设 $h_a(C)=\mathbf{1}\{a\text{ 满足 }C\}$。在可满足情形下，对子句均匀抽样并统一标注为正；若一个高效 proper learner 能以 $\epsilon <1/m$ 输出某个 $h_a$，低于 $1/m$ 的总体错误迫使该赋值满足每个子句，于是输出本身给出 SAT 见证。这个归约明确使用了可采样分布、风险 gap 和 proper 输出表示，完整量词见学习困难性的归约公理库学习困难性的归约hardness of learning reduction · prediction-preserving reduction通过可采样分布、表示映射和风险间隙，把高效学习器转化为源问题求解器。。

若允许 unrestricted improper 输出，常数函数 $h(C)\equiv 1$ 在这批样本上零错误，却不编码共同满足全部子句的赋值，归约立即失效。这个反例说明：类内搜索困难只能推出 proper 路线困难；要证明所有学习器都困难，还须让任意低风险输出都可解码源问题。

证明边界 ​

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

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

这个三轴账本为相邻页面分工：Proper 与 Improper 学习公理库Proper 与 Improper 学习Proper learning · Improper learning区分比较类与学习器实际允许输出的函数类。固定比较类与输出类的关系，近似 ERM 与优化误差公理库近似 ERM 与优化误差approximate ERM · optimization error刻画训练目标未被精确最小化时，经验次优量如何进入总体超额风险。解释有限求解精度怎样进入风险界，而学习困难性的归约公理库学习困难性的归约hardness of learning reduction · prediction-preserving reduction通过可采样分布、表示映射和风险间隙，把高效学习器转化为源问题求解器。负责把可采样性、风险间隙和解码步骤串成真正的计算下界。三者共同防止把“统计上存在”“某条算法路线可算”和“所有路线都容易”混为一谈。