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

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

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

一个 proper 学习归约 ​

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

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

证明边界 ​

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

若凸松弛输出一个类外投票，却仍与原类最优风险比较，improper learner 可能绕过类内搜索。下界必须对应所允许的全部输出算法，而不是某个优化程序的失败。

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