Michael I.Jordan：AI 时代变革，源于应用场景中的优化算法

▲点击上方 雷锋网 关注

雷锋网 AI 科技评论按：8 月 9 日，为期两周的 2018 国际数学家大会（ICM）在里约热内卢完美谢幕，来自全球一百多个国家的 3000 多位数学家出席了本次盛会。

ICM 是国际数学联盟主办的、每四年一次的全球最高标准的数学科学学术会议。其中，在 ICM 2018 最后一次全体讲座中，UCB 教授 Michael I. Jordan 提出了属于 AI 时代的新问题：「How should scientists efficiently compute the world's data in a way that addresses real-world problems.」

近年来，运筹优化与决策算法作为数学在现实中的应用领域，一直受到数学界的广泛关注。而在此次面对 ICM 全体参会数学家的讲座中，Jordan 教授发表了聚焦「是否存在最佳的优化方法」问题的，主题为「Dynamical，symplectic and stochastic perspectives on Gradient-Based optimization」的讲座。人工智能领域中运筹优化和算法决策的重要性，再一次成为了全场的焦点。

Michael I.Jordan 是加州大学伯克利分校 UCB 电气工程与计算机科学系、统计系杰出教授，美国科学院、美国工程院、美国艺术与科学院三院院士，机器学习领域目前唯一获此成就的科学家，是机器学习的奠基者、人工智能领域的泰斗之一。

Michael I.Jordan已确认参加由雷锋网、乂学教育·松鼠AI和IEEE LTSC主办的『全球AI+智适应教育峰会』，免费门票、VIP门票开放申请中。

访问大会官网即刻申请：https://gair.leiphone.com/gair/aiedu2018（复制链接到浏览器或直接点击阅读原文）

以下是 Michael I.Jordan 教授演讲的主要内容：

今天演讲的主题是动态的、保辛的随机视角下的梯度优化方法。内容围绕动态系统（dynamical systems）和优化之间的关系展开。这在数学中是一个古老而宽泛的领域。动态系统研究涉及数学的众多分支，主要基于对梯度流与力学变分观点。「数据工程」通常被称为「机器学习」或「人工智能」，是跨越统计学、物理学、计算机科学和数学的跨领域学科。

对我们来说，将计算与实际问题相结合是一项艰巨的任务。我们的目标是在这个领域中建立一些新的联系，从基于梯度优化的连续时间、变分角度研究等各个方面着手。我们超越了经典的梯度流理论，专注于二阶动态，旨在展示这种动力学与快速收敛 (converge) 的优化算法之间的相关性。

虽然我们关注理论研究，但实际的应用背景对我们来说也同样重要。现代统计数据分析通常涉及非常大的数据集和参数空间，因此计算效率在实际应用中至关重要。

在这样的前提下，效率的概念比传统的计算复杂性理论中「算法复杂度」的概念更加严格。我们接下来讨论多项式复杂性和指数复杂性之间的区别，这是一个非常有意义的关注点。在大规模数据分析中，一个可以实际应用的算法不仅需要多项式的复杂度阶，而且需要在相关问题参数中线性或者近似线性的复杂度。优化理论为提升算法的效率提供了实践和理论的支持。它提供了计算效率高的算法，并提供了允许将收敛速度确定为问题参数的显式函数的分析工具。鉴于基于 Hessian 的优化方法在参数空间的维度上会产生二次或三次的复杂度，在讨论非一阶方法的时候，效率可能是一个有意义的讨论点。

更广泛地说，统计推断（statistical inference）和计算思想的融合，是当前世纪的主要趋势之一——目前以诸如「数据科学」和「机器学习」这样的术语来出现。这是一种寻求将计算和统计推断需求共同研究的新的数学概念的趋势。例如，人们希望将数据分析算法的运行时间的计算化成关于统计风险、数据样本数量、模型复杂度等统计量的函数，同时考虑计算资源限制，如处理器数量、通信带宽和异步程度。对这种权衡的基本理解似乎可以通过更低的下界的发展而出现——通过建立「最优」概念，可以消除冗余的概念并揭示必然的联系。在这里，优化理论也很重要。

经典统计理论没有考虑时间维度，它的方程在数据复杂性、风险和变量维度之间进行权衡，但在这些方程中并不包含运行时间。而在计算机科学的另一方面，你会发现算法设计需要在运行时间、运行资源等复杂性度量之间进行权衡，但统计风险不在其中。所以要如何将这两种方式放在一起是我们这个时代的一大挑战。优化起到了将这两个领域结合在一起的作用，它提供了算法和对问题更深层次的理解，特别是当我们开始考虑通过优化去达到更优的下界。

在 20 世纪 70 年代开始的一项开创性研究中，Nemirovski、Nesterov 和其他人开发了一种优化的复杂性理论，建立了收敛速度的下界，并发现实现这些下界限的算法。此外，复杂性模型是相对的——指定了「oracle」，那么算法只能使用 oracle 可用的信息。例如，只访问函数值和梯度的 oracle。因此，实际计算效率的相关指导方法可以在理论中以自然的方式施加。

计算和统计数据通过优化结合在一起。而哪些领域会先开始组合在一起？我们如何开始建立理论和实践？在现实生活、公司和科学中，以下对于成功案例至关重要。一个是基于梯度的优化，我学到的算法版本，是在关注 Hessian 矩阵和牛顿迭代法以及更高阶的版本。在二三十年间，它们发挥了很多作用，特别是在大规模计算问题上得到了成功应用，但计算 Hessian 很难，也很难去估算它们。现在我们经常会有随机差异，在这些问题上我们没有办法准确地观察事物。这些问题只是存在于统计领域，我们可能存在各种错误比如采样偏差等。我们必须面对它并且利用它。最终，加速概念在前苏联优化界出现了，它是研究优化算法，尤其是如何获得最快的优化算法的概念。这类被称为「加速算法」的优化算法（Nesterov, 1998），通常可以达到 oracle 的最下限速率，尽管 Nesterov 加速方法为什么能够达到 oracle 的理论原因还是个谜。

我们认为，一些谜团是出自于离散时间算法和分析的优化的历史焦点。在优化中，「连续优化」和「离散优化」之间的区别，在于如何匹配（「空间」）变量。相比之下，我们的讨论将集中在连续时间上。在连续时间中，我们可以将加速度作为一种差异概念给予数学意义，将它作为沿曲线的速度变化。我们可以提出「最快速率是多少」的问题，来作为变分分析的一个问题。本质上，这是为给定的 oracle 本身找到「优化的最佳方法」作为优化的形式问题。这种变分的观点也具有生成性的优点——我们可以推导出实现想要的 fast rates 的算法，而不是去为某一个特殊方式得出的特定算法去分析并建立一个符合算法要求的 fast rate。

为了使连续时间上的结果能够推广、得出数字计算机可以实现的算法，我们将连续时间动态系统的问题离散化。有趣的是，我们会发现，广泛应用于从变分或哈密顿角度获得的动态的辛迭代积分器，与优化有关。从辛积分获得的算法可以更快地通过相空间移动，这为「加速」赋予了几何意义。

考虑在某种意义上的「加速」的连续时间下的随机动态系统也是有意义的。最简单形式的基于梯度的积分微分方程是 Langevin 扩散。我们看到，通过考虑欠阻尼 Langevin 扩散，我们将获得更类似于加速梯度下降的方法，并且实际上可证明产生比过阻尼扩散更快的速率。

Nesterov 在 1980 年代提出了一种建立收敛速度下界的梯度下降方法。在 1983 年 Nesterov 发表了开创性论文后，随后的三十年中，各种其他问题背景下的各种加速算法得到了发展。这些包括镜像下降、复合目标函数、非欧几里德几何、随机梯度下降和高阶梯度下降。我们已经证明了以上这些算法的收敛速度：他们的收敛速率通常达到 oracle 下限。总体来说，加速一直是现代优化理论中最富有成效的思想之一。

拉格朗日公式可以在连续时间内捕获加速度，显示该公式如何产生一系列微分方程，其收敛速度是离散的连续时间对应物。我们强调这些微分方程的数值积分问题，建立了我们在下面讨论的辛积分方法。

辛积分是微分方程离散化的一般方法，它保留了动力系统的各种连续对称性。从力学获得的微分方程的情况下，这些对称性包括物理上有意义的积分，例如能量和动量。即使动态量只是近似值，辛积分器也能精确保存这些量，除了从物理守恒的观点来看这一结果的吸引力之外，连续对称性的保留意味着辛积分器比其他积分格式更稳定。因此可以在离散时间系统中使用更大的步长。正是后一个事实表明辛积分器在加速优化方法相关的微分方程中起作用。辛积分器可以从拉格朗日框架导出，但更自然地，可以从哈密顿框架导出。但事实上，辛方法在拓扑上比 Nesterov 加速法的一个三序列变种更稳定，如果选择更大的步长，这一事实就会更加明显。辛集成与优化中的加速现象之间存在着联系，当后者被解释为连续时间现象时，辛积分提供了获得离散时间近似的有效且灵活的方式。

最需要注意的是非凸优化中的加速度与鞍点的逃逸问题。现实中存在的问题大都具有非凸特性。事实证明，对于统计学习中的广泛问题，非凸情形下存在足够的数学结构，即可以获得有用的数学结果。实际上，在许多情况下，来自凸优化的想法和算法适当地修改可以被应用于非凸环境。特别对于基于梯度的优化，在凸问题中执行良好的相同算法也倾向于在非凸问题中产生良好的性能。从这个意义上说，凸优化除了拥有自己的许多自然应用之外，还可以作为非凸优化的实验室。在鞍点附近存在 pancake 区域，在这个区域内进行梯度下降将「卡住」需要指数量级的时间逃逸。这个区域并不平坦，而是随着 Hessian 的变化而变化。Lipschitz 假设使我们能够控制这种变化。

到目前为止关注的是动态系统。系统是确定的。随机性以有限的方式被引入，作为一种扰动，确保从鞍点快速逃离。我们特别分析了球中的非均匀扰动，足以快速逃离，但是这不是必要的。鉴于这种简单选择的成功，我们用动力研究中更彻底的随机方法来解决我们的问题。

基于梯度的优化的一般主题及其在大规模统计推断问题中的应用，目前非常活跃。我们要强调一下在未来几年可能引起持续关注的一些课题。一个令人值得注意的问题是，在统计设置中经常使用优化方法来解决点估计问题，其中核心问题是在参数空间中输出具有所需统计特性的单个点。

而更广泛的问题是，使用概率分布的一些精炼的形式来提供与该相关的不确定性的指标。通过考虑作为概率分布空间的空间，优化思想也可以在这里体现：我们可以要求不收敛到单个点，而是收敛到点的分布上。哈密顿方法自然而然地产生震荡解，并且正如我们所看到的，需要一些工作来获得收敛到某一个点的算法。这表明哈密顿方法实际上在分布收敛的设定中比在点估计设定中更容易使用，从而提供了点估计和更广泛的推断问题之间的算法桥梁。事实上，在贝叶斯推断中，哈密顿公式（以及不同积分器形式的辛积分）已经成功地应用于 MCMC 算法（马尔科夫链蒙特卡洛算法）的设置中，其中哈密顿函数的动量分量提供了更快的混合。加速算法和高效的推断算法之间更深层次的联系值得研究。

数学正在成为数据领域的一个强大工具，已经证明了许多定理。对力学的梯度流和变分透视的研究可以应用于该区域。最后，我需要重申一下数学工具在解决基于数据的实际问题中的重要性。尽管有一些现实世界的为数据分析的数学应用问题，我们承认这个领域还不是很成熟，但未来非常值得期待。