计算下界

信息论下界刻画的是在无计算资源限制下任何算法（甚至指数时间）能达到的最优表现，本问题中对应Õ(md+k)；计算下界则假设算法必须在多项式时间内运行，得到的下界通常更大。

该分离结果与近年来在线学习、在线凸优化中一系列计算下界工作相呼应，印证了“统计最优未必计算可行”的普遍现象。