Michael Jordan新研究：采样可以比优化更快地收敛

凸函数（左）和非凸函数（右）

机器学习和数据科学融合了计算机科学与统计学，以解决推理问题。它们的规模和复杂性都要求现代计算基础设施的支持。它们的算法基础基于两种通用的计算策略，这两种策略都源于数学——优化和马尔科夫链蒙特卡洛方法（MCMC）采样。针对这些策略的研究大多是单独进行的：优化研究侧重于评估和预测问题，而采样研究侧重于需要评估不确定性的任务，如形成置信区间和进行假设测试。然而，在两个研究领域中使用共同的方法要素开始成为一种趋势。特别是这两个领域都侧重于使用梯度和随机梯度——而不是函数值或高阶导数——来作为单个算法步骤的计算复杂性和总体收敛速率之间的有益折衷。实验证明，这种妥协的效果相当惊人。但是，将优化和采样联系起来的理论研究相对较少，因此限制了这种思路的发展。尤其是，优化理论最近的快速发展 [34] 并没有带来采样理论的此类发展。因此，机器学习的推理范围仍然有限，很少能够考虑不确定性的估计。

在最近的研究 [13, 15, 14, 11, 9, 17, 30, 31] 中，理论联系开始出现。其中优化理论中的 工具 已经被用于证明 MCMC 采样中的收敛速率——通常还包括维度相关性。这些结果显示的总体信息是采样比优化要慢，这一结果符合普遍观点，即采样方法只有在需要其提供更强的输出推理时才合理。但是，这些结果是在凸函数的设定中取得的。对于凸函数，可以通过局部信息来评估全局属性。而基于梯度的优化非常适合这种设置。

在本文中，Michael Jordan 等研究者关注的是非凸设定。他们考虑了有界区域之外为凸而区域内为非凸的一类问题。这种问题出现在具有适当先验的贝叶斯混合模型问题 [33, 32]，以及统计物理学中常见的带噪声多稳态模型中 [24, 25]。研究者发现，如果这一非凸区域在 R^d 中具有一个恒定的非零半径，那么 MCMC 方法就会在 O(d/ε) 或 O(d^2ln(1/ε)) 步数内收敛到 ε准确率，而任何优化方法都需要 O((1/ε)^d) 步以上才能收敛。因此，对于这类问题，采样比优化更高效。

论文：Sampling Can Be Faster Than Optimization 

论文链接：https://arxiv.org/pdf/1811.08413.pdf

摘要：近年来，优化算法和蒙特卡洛采样算法为统计机器学习应用的快速发展提供了计算基础。然而，关于这两种方法论之间关系的理论理解非常有限，对其相对优势和劣势的理解也比较缺乏。此外，现有的结果主要是在凸函数（用于优化）及对数凹函数（用于采样）中获得的。在这种设定下，局部属性决定全局属性，优化算法在计算层面无疑比采样算法更高效。我们测试了一类来自混合建模及多稳态系统的非凸目标函数。在这种非凸设定下，我们发现采样算法的计算复杂度随模型维度线性扩展，而优化算法的计算复杂度则呈指数扩展。

仔细考虑非凸半径 R 和维度 d 之间的相对尺度是很有趣的（对于常数 Lipschitz 平滑度 L）；当 R 是常量或者小于 O(log d) 时，采样通常比优化更容易；当 R≤√ d 时，采样的收敛上界仍然比优化复杂度下界稍低；当 R>√ d 时，其对比是不确定的；并且当 R>d 时，相反的结论成立。

近年来基于梯度优化的理论快速发展，部分是因为下界理论的研究，类似定理 4 的形式，其对很多种算法都有效。在 MCMC 算法上发展这样的下界理论是很有趣的，尤其是能捕捉维度依赖关系的理论。此外，开发其它类型的非凸性的下界和上界理论也是很有趣的。

深度神经网络的目标函数是高度非凸的，但使用优化方法（SGD）却能达到很好的效果。这篇论文能为深度学习优化带来新的思路吗？或许混合方法会是不错的选择，但在实验研究中是不是早就有这样的尝试了呢？