机器之心编辑部编译

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

对于凸函数而言,局部最优点即全局最优点,这是很多优化方法奏效的重要前提。对于非凸函数,可以使用采样方法(如 MCMC),但普遍比优化方法的收敛要慢得多。而在 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)却能达到很好的效果。这篇论文能为深度学习优化带来新的思路吗?或许混合方法会是不错的选择,但在实验研究中是不是早就有这样的尝试了呢?

理论采样优化Michael Jordan
4
相关数据
深度学习技术

深度学习(deep learning)是机器学习的分支,是一种试图使用包含复杂结构或由多重非线性变换构成的多个处理层对数据进行高层抽象的算法。 深度学习是机器学习中一种基于对数据进行表征学习的算法,至今已有数种深度学习框架,如卷积神经网络和深度置信网络和递归神经网络等已被应用在计算机视觉、语音识别、自然语言处理、音频识别与生物信息学等领域并获取了极好的效果。

机器学习技术

机器学习是人工智能的一个分支,是一门多领域交叉学科,涉及概率论、统计学、逼近论、凸分析、计算复杂性理论等多门学科。机器学习理论主要是设计和分析一些让计算机可以自动“学习”的算法。因为学习算法中涉及了大量的统计学理论,机器学习与推断统计学联系尤为密切,也被称为统计学习理论。算法设计方面,机器学习理论关注可以实现的,行之有效的学习算法。

数据科学技术

数据科学,又称资料科学,是一门利用数据学习知识的学科,其目标是通过从数据中提取出有价值的部分来生产数据产品。它结合了诸多领域中的理论和技术,包括应用数学、统计、模式识别、机器学习、数据可视化、数据仓库以及高性能计算。数据科学通过运用各种相关的数据来帮助非专业人士理解问题。

收敛技术

在数学,计算机科学和逻辑学中,收敛指的是不同的变换序列在有限的时间内达到一个结论(变换终止),并且得出的结论是独立于达到它的路径(他们是融合的)。 通俗来说,收敛通常是指在训练期间达到的一种状态,即经过一定次数的迭代之后,训练损失和验证损失在每次迭代中的变化都非常小或根本没有变化。也就是说,如果采用当前数据进行额外的训练将无法改进模型,模型即达到收敛状态。在深度学习中,损失值有时会在最终下降之前的多次迭代中保持不变或几乎保持不变,暂时形成收敛的假象。

导数技术

导数(Derivative)是微积分中的重要基础概念。当函数y=f(x)的自变量x在一点x_0上产生一个增量Δx时,函数输出值的增量Δy与自变量增量Δx的比值在Δx趋于0时的极限a如果存在,a即为在x0处的导数,记作f'(x_0) 或 df(x_0)/dx。

准确率技术

分类模型的正确预测所占的比例。在多类别分类中,准确率的定义为:正确的预测数/样本总数。 在二元分类中,准确率的定义为:(真正例数+真负例数)/样本总数

置信区间技术

在统计学中,一个概率样本的置信区间(Confidence interval),是对这个样本的某个总体参数的区间估计(Interval Estimation)。置信区间展现的是,这个总体参数的真实值有一定概率落在与该测量结果有关的某对应区间。置信区间给出的是,声称总体参数的真实值在测量值的区间所具有的可信程度,即前面所要求的“一定概率”。这个概率被称为置信水平。举例来说,如果在一次大选中某人的支持率为55%,而置信水平0.95上的置信区间是(50%, 60%),那么他的真实支持率落在50%和60%之区间的机率为95%,因此他的真实支持率不足50%的可能性小于2.5%(假设分布是对称的)。

目标函数技术

目标函数f(x)就是用设计变量来表示的所追求的目标形式,所以目标函数就是设计变量的函数,是一个标量。从工程意义讲,目标函数是系统的性能标准,比如,一个结构的最轻重量、最低造价、最合理形式;一件产品的最短生产时间、最小能量消耗;一个实验的最佳配方等等,建立目标函数的过程就是寻找设计变量与目标的关系的过程,目标函数和设计变量的关系可用曲线、曲面或超曲面表示。

深度神经网络技术

深度神经网络(DNN)是深度学习的一种框架,它是一种具备至少一个隐层的神经网络。与浅层神经网络类似,深度神经网络也能够为复杂非线性系统提供建模,但多出的层次为模型提供了更高的抽象层次,因而提高了模型的能力。

推荐文章
暂无评论
暂无评论~