18-29期VALSE Webinar会后总结

2018 年 9 月 26 日 VALSE

卡内基梅隆大学张弘扬博士2018年9月19日VALSE Webinar 成功举办。

张弘扬，美国卡内基梅隆大学机器学习专业四年级博士生，于2015年在北京大学获得硕士学位。研究兴趣包括机器学习，优化，理论计算机科学，统计学及其应用。在计算机视觉和人工智能领域的顶级会议/期刊上发表过多篇论文，包括ICML，NIPS，COLT，ICALP，ITCS，IEEE TIT，Proceedings of the IEEE等。并于2017年共同撰写了《视觉分析中的低秩模型》一书。他还担任各种顶级会议/期刊的委员会成员和审稿人，如STOC，COLT，ICML，NIPS，AISTATS，ICLR，AAAI，IJCAI，ISIT，JMLR，TPAMI，Proceedings of the IEEE，IEEE TSP等。

张弘扬博士Webinar的题目是：New Paradigms and Global Optimality in Non-Convex Optimization。

在报告中，张弘扬博士首先介绍了自己关于非凸优化的最新工作。首先张博士指出非凸优化在各个领域无处不在，从机器学习，信号处理到统计学和理论计算机科学。同时也指出了非凸优化通常会遇到计算问题：局部搜索算法，如梯度下降或随机梯度下降，只会收敛到鞍点或局部极小点，而不是我们渴望的全局最优解。解决这些问题有三种主要方法：1、良好的初始化; 2、用一系列的凸优化逼近非凸问题; 3、研究损失landspace好的结构，例如强对偶性或“局部最小值=全局最小值”。在本次演讲中，张博士的工作重点关注后两种方法，这两种方法是非凸优化中全局最优性的新范式。第一部分讲解了如何能够任意接近学习线性分类器和1-bit压缩感知学习的非凸问题的全局最优性。通过局部化技术，可以利用求解一系列凸问题来解决期望0-1损失函数最小化问题。另外还给出了负面的结论，表明任何一次性最小化都不适用于此设置。第二部分张博士讲解了矩阵分解问题的强对偶性。他指出强对偶的性质在矩阵分解及其相关问题中即使只有接近最优样本复杂性的时候也是成立的。还指出一般的矩阵分解需要至少2 ^ n时间来求解，其中n是矩阵的大小。

问答部分：

问题1：不满足强对偶怎么办？

回答：利用non-convex问题的好的结构，才能得到强对偶。对于大部分问题，不一定能够有强对偶。比如说 deep neural network，我们可能只能得到弱对偶，我们可以在一定程度上分析弱对偶离强对偶差距有多大。我们可以证明随着neural network 宽度的增加，他会越来越接近强对偶。极限情况下，当我们有越来越多的宽度时，我们期望可以得到强对偶。

问题2：当矩阵中的元素缺失率比较高的时候，这个方法work吗？

回答：这个方法主要是理论上的结果，其实n*r已经非常小，并达到信息论的极限了。这时候我们能够观测到的比例是r/n。当r比较小时，其实我们已经达到非常高的缺失率了。所以这个方法对缺失率比较高的时候，还是很work的。

问题3：r* norm具体是一个什么范数？

回答：r* norm其实是一个bi-conjugate function，当我们对UVT这样的矩阵做F范数的时候，对这个东西做bi-conjugate，就可以自然的导出r*。

问题4：弱对偶通常只能得到目标函数值的下界估计，自变量借助于对偶优化，有没有好的估计？

回答：弱对偶实际上是说对偶问题是原始问题的下界，我们最先的工作中也给出了一个上界的估计，可以证明这个上界估计也是趋于0的。比如说对于deep neural network，可以得到一些近似强对偶性。

问题5：如若拆分的真实rank不知道的时候，有办法证明吗

回答：目前的形式我们确实是需要知道rank是什么，但是我们在最新的一个JMLR的submission中证明了如果我们把 F范数换成r范数，时，右边自然就导出了以前的方法，例如r norm minimization。并且r norm minimization是不需要知道rank是什么的。所以说这套理论同样适用于rank 不知道的时候。

问题6：请问信息论极限是如何得到的？

回答：Rank r的矩阵自由度至少是n*r，n是矩阵的size， r是矩阵的rank。所以说当观测到的元素个数比这个小的时候，通过出现鸽笼定理，你就会知道至少需要这么多的样本个数，才能准确恢复。因为我们的guarantee非常强，我们要求准确恢复，所以对于矩阵填充这样一个问题，至少需要的样本点个数是n*r。

问题7：文章提出的最优解，是针对神经网络算法？还是所有非凸优化算法都适用？

回答：今天talk所讲的主要针对矩阵填充，最新工作只是针对neural network的问题，毕竟具体问题需要具体分析，因为对于general non-convex的问题是一个NP-hard的问题，所以不可能对于所有的问题都有一个非常强的保证。

问题 8：sparse coding 可以用吗？

回答：具体问题具体分析，我相信理论上是有可能是有用的，需要具体尝试才能有结果。

问题 9：宽泛的问题，关于非凸优化问题是需要一些手段得到我们想要的所谓的全局最优解，分享解决具体问题时，具体的建议，比如建模时如何建立更合理的模型，或者建立非凸模型用什么手段建立一个更好的结果？

回答：这个talk主要还是关于landscape方面的progress，最近也有一些使用算法上的一些使用momentum 或者adam，对于大家关心的deep neural network，往往会得到一些比较好的结果，从经验上来看，我觉得有的时候对于一些问题来说未必需要得到它的全局最优解，对于一些问题可能局部最优解可能就已经比较好了，但是对于有一些别的问题，比如说，矩阵填充以及learning halfspace这些问题，我们已经设计出了这样的算法，这些在理论上是非常漂亮的，但是对于一些实际问题往往到达局部最优解就够了，所以大家关心的点可能就是如何escape settle point等等。最近也有一些这方面的进展，比如加一些扰动或者避免一些saddle point，接下来我们的工作就是期望利用问题的具体结构，得到non-convex的问题的具体形式，对于刘老师的问题只能说具体问题具体分析，毕竟对于不同的non-convex问题，就目前的技术来说，我们也不期望用一个大一统的理论。

问题10：对于非凸的问题，具体问题更重要，对于具体的问题设计的方法，可能会更有效，目前来说，还比较难找一个统一的方法，像在凸的情况下？

回答：对，因为毕竟从理论上来说是一个NP-Hard的一个问题，NP-Hard问题不太可能找到一个，毕竟有最坏的情况存在，所以不太可能有一个非常强大的“武器”把这些都消灭，所以我的建议还是具体问题具体分析，一定要深入理解这样一个问题，然后发现它们的一些结构，然后利用这样一个结构做一个事情。

录像视频在线观看地址：

http://www.iqiyi.com/u/2289191062

PPT链接：

http://vision.ouc.edu.cn/valse/slides/20180919/valse.pdf

特别鸣谢本次Webinar主要组织者：

VOOC责任委员：刘日升（大连理工）

活动参与方式：

1、VALSE Webinar活动依托在线直播平台进行，活动时讲者会上传PPT或共享屏幕，听众可以看到Slides，听到讲者的语音，并通过聊天功能与讲者交互；

2、为参加活动，请关注VALSE微信公众号：valse_wechat 或加入VALSE QQ群（目前A、B、C、D、E、F、G群已满，除讲者等嘉宾外，只能申请加入VALSE H群，群号：701662399）；

*注：申请加入VALSE QQ群时需验证姓名、单位和身份，缺一不可。入群后，请实名，姓名身份单位。身份：学校及科研单位人员T；企业研发I；博士D；硕士M。