南京大学赵申宜：SCOPE - Scalable Composite Optimization fo

嗨，大家好。这里是学术报告专栏，读芯术小编不定期挑选并亲自跑会，为大家奉献科技领域最优秀的学术报告，为同学们记录报告干货，并想方设法搞到一手的PPT和现场视频——足够干货，足够新鲜！话不多说，快快看过来，希望这些优秀的青年学者、专家杰青的学术报告 ，能让您在业余时间的知识阅读更有价值。

 

 

人工智能论坛如今浩如烟海，有硬货、有干货的讲座却百里挑一。“AI未来说·青年学术论坛”系列讲座由中国科学院大学主办，百度全力支持，读芯术作为合作自媒体。承办单位为中国科学院大学学生会，协办单位为中国科学院计算所研究生会、网络中心研究生会、人工智能学院学生会、化学工程学院学生会、公共政策与管理学院学生会、微电子学院学生会。“AI未来说·青年学术论坛”第六期“机器学习”专场已于2019年6月23日下午在中科院举行。南京大学赵申宜为大家带来报告《SCOPE: Scalable Composite Optimization for Learning》。

 

Shen-Yi Zhao is currently a Ph.D. candidate of the Department of Computer Science and Technology at Nanjing University, under the supervision of Dr. Wu-Jun Li. Before that, he received his B.S. degree from the Department of Mathematics at Nanjing University. His research interests include parallel and distributed optimization for large-scale machine learning. He has published four first-authored papers at top conferences of artificial intelligence and machine learning. He has won multiple awards including national scholarship and Baidu scholarship.

 

报告内容：Many machine learning models, such as logistic regression (LR) and support vector machine (SVM), can be formulated ascomposite optimization problems. Recently, many distributed stochastic optimization (DSO) methods have been proposed to solve the large-scale composite optimization problems, which have shown better performance than traditional batch methods. However, most of these DSO methods might not be scalable enough. In this talk, I will introduce a novel DSO method, called scalable composite optimization for learning (SCOPE). SCOPE is both computation-efficient and communication-efficient. Theoretical analysis shows that SCOPE is convergent with linear convergence rate when the loss function is smooth and strongly convex. Furthermore, empirical results on real datasets show that SCOPE can outperform other state-of-the-art distributed learning methods, including both batch learning methods and DSO methods.

 

SCOPE: Scalable Composite Optimization for Learning

 

赵申宜博士报告的主要内容包括背景介绍、SCOPE方法、非凸的模型和结论等四个方面。他首先介绍了如何学习一个模型，即先收集相关的数据和选择模型，再选择相应的优化器，然后通过迭代获得最优的模型。以此为基础，引入了合成优化的方法，损失函数为所有样本的损失函数的平均值，优化目标为最小化损失函数来获得与理论最优参数值距离非常小的模型的参数值。并以逻辑斯蒂回归（LR，Logistic Regression）和支持向量机（SVM，Support Vector Machine）的方法为例介绍了它们的目标函数和随机梯度下降（SGD，Stochastic Gradient Descent）的优化方法。

 

现有的数据集的规模越来越大，如包含14，000，000 张图片的 ImageNet 数据集和包含 2，500，000，000个单词的 English Wikipedia 数据集，一般来说，数据集的样本数目越多，训练所得到的模型的泛化性就越好。由于数据集的规模太大，为了提升计算效率，需要用分布式的方法来训练模型。由此引出了传统的分布式算法：分布式系统中有不同的worker，每个 worker 都有自己的数据集，每个 worker 在所拥有的数据集上进行采样，然后分别计算每个worker的梯度，并把这些梯度发送给server来更新模型的整体参数，再把更新后的模型的整体参数回传给每个worker，如此不断迭代优化，直到模型收敛。此外，还有很多其他的分布式算法，如异步的 SGD、SVRG、SDCA和 SAGA，分散的 SGD 以及块坐标下降等算法。但这些算法都有一个问题，就是需要频繁的通信，即每计算完一个梯度就要与别的机器进行通信，这样会带来O(NT)的通信开销，N通常是非常大的，因此算法的速度就变得非常慢。

 

为了解决频繁通信的问题，他们的团队提出了一种新的分布式SGD算法叫做SCOPE。该方法主要有三点贡献：一是局部学习（local learning），每一个worker可以更加的自主，并且可以减少通信的开销；二是对于光滑的严格凸函数有线性收敛速度；三是可以使用恢复规则来处理高维稀疏数据。

 

接着赵申宜博士介绍了SCOPE算法的框架：分布式系统中有不同的worker，每个worker都有自己的数据集，每个worker在所拥有的数据集上进行采样，并计算每个worker的梯度，并通过计算的梯度来更新每个worker的模型参数值，然后把所有woker的模型参数值传递给server，更新后的模型整体参数值即为传递到server上的所有参数值的平均值，再把模型整体参数值回传给每个worker，如此不断迭代优化，直到模型收敛。与传统的分布式算法的不同点是，该方法向server传递的是每个worker的模型参数值，而不是每个worker的模型参数的梯度值。赵申宜博士介绍了SCOPE的框架之后，又详细讲解了SCOPE的算法，受SVRG算法的启发，SCOPE算法计算的梯度为全梯度；采用局部学习的策略，使用每一个worker的本地数据来更新每一个worker在不同时刻、不同样本的模型参数值；在该算法的内层循环中没有通信。

 

赵申宜博士在讲目标函数时，先讲解了局部目标函数，即通过最小化该目标函数来获得每一个worker的局部最优参数。并由此引出了局部-全局差异性的指标，以及如何通过该指标获得好的数据划分。接着讨论了SCOPE算法的收敛性，并进一步讲了非平滑正则条件下SCOPE算法及其收敛性。通过SCOPE算法的通信复杂度，可以进一步推断出局部学习可以减低通信的次数的这一结论。

 

在展示实验结果之前，先讲解了如何使用SCOPE算法处理高维稀疏的数据，即仅仅更新模型中与样本中非零值坐标位置处对应的参数值，该等价条件可以通过恢复规则来保证。然后讲了在rcv1和avazu数据集上使用8个CPU训练的逻辑斯蒂回归模型和Lasso模型的实验结果。实验结果表明：从梯度和收敛时间角度，SCOPE方法与其他方法相比有很大的优势，且在一定worker范围内，模型的加速随worker的数目的增加而线性增加。

 

然后又讲到了非凸函数模型，非凸函数表示模型存在很多局部极小值，此时局部学习的策略受到限制，可能的原因是由于训练的样本数目不够大。为解决该问题，提出了在同步SGD算法中压缩每一个worker梯度的GMC算法，可以把模型的开销从O(d)降低到O(rd)，其中r≤1%。并进一步展示了非凸函数在CIFAR10数据集上训练ResNet20和AlexNet模型中的实验结果。

 

最后，赵申宜博士对报告的内容进行了总结：面向通信的有效分布的SGD算法，对于凸函数模型，可以使用本地学习策略的SCOPE算法；对于非凸函数模型，可以使用用于稀疏通信的压缩梯度的GMC算法。