18-09期VALSE Webinar会后总结
美国爱荷华大学徐易博士2018年4月18日VALSE Webinar 成功举办。徐易，美国爱荷华大学计算机系博士在读，本科毕业于浙江大学数学系，随后在美国南达科他州立大学获得硕士学位。主要研究兴趣在机器学习，优化和统计学习理论。博士期间已经在机器学习领域顶级会议NIPS，ICML和AAAI 发表5篇文章。 担任过NIPS 2016，IJCAI 2016，AAAI 2017，IJCAI 2018，ACM TKDD，IEEE TBD，FCS等期刊和会议审稿人。
徐易博士Webinar的题目为：Accelerated Stochastic Subgradient Methods under Local Error Bound Condition.
在报告中, 徐易博士首先回顾了在机器学习的优化问题中常用的一些first-order的算法比如GD，AGD，SG。在大数据的情况下，这些方法每步更新的时候（次）梯度计算法量非常大，所以大家会常用SGD，SSG。但是SGD和SSG的收敛速度比较慢，此外SGD不能适用于非光滑函数，但是许多机器学习的问题又都是非光滑的。针对上述问题，徐易博士提出了一种加速SSG的方法，ASSG和它的变种RASSG。通过引入Local Error Bound这个概念，从理论上可以证明ASSG/RASSG能得到更快的收敛速度。最后还通过实验验证了所提出的ASSG/RASSG在机器学习问题中的有效性。
问答部分：
问题1：在介绍Structured composite non-smooth problems的时候，要求R(w) is polyhedral，这里的polyhedral如何理解？回答：直观理解，Polyhedral函数是piecewise affine。这是一个优化里面的概念，如果R(w) 的eipgraph 是 polyhedral的话，那么我们就说R(w) 是polyhedral。
问题2：在Error Bound里面，c的值可以不知道，但是\theta必须知道吧？回答：对的。一般在Local Error Bound里面，theta的值很多时候都是知道的。此外，我们的RASSG算法也可以针对于c的值不知道的情况。
问题3：次梯度在实际计算中要怎么确定？回答：次梯度是一个集合。在实际中，我们如果遇到只能算次梯度的点，那么就在这个集合里面随机抽取一个来使用。 一个很简单的一维例子，绝对值函数在0点的次梯度是 [-1,1], 那么我们使用的时候就在这个区间里面随机抽取一个值来使用。
问题4：请问这个论文的相关代码公布了吗？回答：我们会很快公布出来。可以在我的主页上下载：https://homepage.cs.uiowa.edu/~yxu71/
问题5：ASSG收敛到局部极小的可能性大吗？回答：想这个问题应该是属于非凸优化，我们这个论文里面没有涉及到非凸优化。 我相信ASSG/RASSG 能收敛到局部极小。
问题6：RASSG可以再解释一下吗，c是如何不需要考虑的？回答：首先我介绍一下ASSG这个算法，我们给定一个步长，然后跑一定的步数(t), 这样叫做一个stage， 然后我们把这个stage得到的解作为下一个stage的初始解，同时我们又减小步长，然后同样的步数(t), 这样又得到一个解，如此循环，比如跑10个stage，我们可以得到最后的解。所以这个t的大小在我们的算法里面非常关键，但是问题是这个t的大小在理论上是跟c的值有关的。 那么设置t的时候如果太小，收敛会慢，如果太大，其实又浪费了。这个时候，我们提出了RASSG。总的说来，RASSG是跑若干个ASSG，首先我们给定一个相对较小的t，然后我们跑一个ASSG（这个ASSG可能跑了5个stage），得到一个解，把这个解作为初始值，同时我们增大t，再跑一个ASSG，如此循环（比如10次或者5次），我们得到最后的解。
问题7：跟GD比起来，快了多少？回答：首先GD（或者Subgradient Descent）是deterministic的算法，而ASSG/RASSG是stochastic算法。如果数据很大的时候，我们一般会使用stochastic的算法，因为当数据很大的时候，可能每一步迭代的（次）梯度计算量非常之大，但是这个时候随机（次）梯度可以很快计算出来。所以这是stochastic算法的一个主要优势。当然在一些特殊问题上，ASSG/RASSG 能得到linear收敛速度O（log(1/epsilon)），比如l1 regularized hinge loss，而SG在这个问题上的收敛速度是O(1/epsilon^2). 此外，GD理论上只适用于光滑函数，而ASSG/RASSG 没有这个限制，当然对应的，SG可以用于非光滑函数。
问题8：核范数满足polyhedral条件吗？回答：不满足。核范数满足Local Error Bound, 所以适用我们的算法。
问题9：如果用到神经网络里面，相比于其他的Adam等等算法能加速吗？回答：在我们的论文里面，我们没有对比Adam算法。我们在机器学习的凸优化问题里面对比过其他算法，ASSG/RASSG还是有很大优势的。据我所知，在神经网络里面，一些论文用了和我们ASSG很类似的算法。也就是先给定一个步长，跑一定的步数之后，再减小步长，如此循环。我相信我们的算法在神经网络里有一定的优势的。
录像视频在线观看地址：http://www.iqiyi.com/u/2289191062
特别鸣谢本次Webinar主要组织者：VOOC责任委员：钟燕飞（武汉大学）VODB协调理事：张利军（南京大学）
活动参与方式：1、VALSE Webinar活动依托在线直播平台进行，活动时讲者会上传PPT或共享屏幕，听众可以看到Slides，听到讲者的语音，并通过聊天功能与讲者交互；2、为参加活动，请关注VALSE微信公众号：valse_wechat 或加入VALSE QQ群（目前A、B、C、D、E、F、G群已满，除讲者等嘉宾外，只能申请加入VALSE H群，群号：701662399），直播链接会在报告当天（每周三）在VALSE微信公众号和VALSE QQ群发布；*注：申请加入VALSE QQ群时需验证姓名、单位和身份，缺一不可。入群后，请实名，姓名身份单位。身份：学校及科研单位人员T；企业研发I；博士D；硕士M。3、在活动开始前10分钟左右，讲者会开启直播，听众点击直播链接即可参加活动，支持安装Windows系统的电脑、MAC电脑、手机等设备；4、活动过程中，请勿送花、打赏等，也不要说无关话语，以免影响活动正常进行；5、活动过程中，如出现听不到或看不到视频等问题，建议退出再重新进入，一般都能解决问题；6、建议务必在速度较快的网络上参加活动，优先采用有线网络连接；7、VALSE微信公众号会在每周一推送上一周Webinar报告的总结及视频（经讲者允许后），每周四发布下一周Webinar报告的通知。
页:
[1]