菜单总览
新闻

讲座回顾——非光滑非凸优化的二阶方法

  • 2020.08.12
  • 新闻
8月5日,香港中文大学(深圳)助理教授、AIRS项目负责人Andre Milzarek教授带来主题为“非光滑非凸优化的二阶方法”的直播讲座,以下为讲座回顾。

        上周,香港中文大学(深圳)助理教授、AIRS 项目负责人 Andre Milzarek 教授为我们带来主题为“非光滑非凸优化的二阶方法”的讲座,本场讲座由香港中文大学(深圳)的蔡卓轩教授主持。

        Milzarek 教授的讲座聚焦于讨论关于利用(随机的或近似的)高阶信息来解决结构化优化问题的确定性优化方法以及随机优化方法。讲座首先进行了问题描述。在 Milzarek 教授考虑了一系列复合型最小化问题,其中目标函数可以写成光滑(可能非凸)和凸(可能非光滑)函数之和。目标函数的光滑部分通常对应于一个损失模型,该模型反映给定数据与获得的优化解之间的误差。非光滑部分通常扮演一个正则项的角色,它促使获得的优化解趋于一个特殊的性质,例如稀疏性、群稀疏性和低秩,或者允许对约束进行建模。此问题公式可涵盖各种应用,例如,大规模机器学习问题、LASSO、稀疏逻辑回归、成像问题、低秩矩阵补全和字典学习。

        Milzarek 教授接着谈到了二阶方法的必要背景和基础。许多非光滑优化方法之所以能够成功运用是基于以下的观察:通过利用目标函数非光滑部分的邻近算子,一阶最优的必要条件可以等价地表示为非光滑方程。现在的主要思想是应用牛顿法的一个非光滑变体,即所谓的半光滑牛顿法来求解该方程,并加速现有一阶算法(如近端梯度法)的收敛和性能。从结构上来看,半光滑牛顿步与求解光滑问题的传统牛顿步非常相似。但是,由于目标函数不可微,必须引入并使用广义导数。在适当的假设下,半光滑牛顿法会生成一系列迭代序列,这些迭代序列局部快速收敛(q-超线性)到优化问题的一个驻点。

        然而,半光滑牛顿法与经典牛顿法有相似的局限性。特别是只有当迭代过程开始时足够接近问题的解或驻点时,我们才能保证局部收敛。为了弥补这一缺陷,我们需要设计一个适当的全局策略。Milzarek 教授提出了一种基于 Robinson 法线映射的全局化算法。该方法的思想是将法线映射的半光滑牛顿步嵌入到信赖域框架中,以实现并保证全局收敛。

        收敛性分析和算法都利用了新的优化函数的下降率测试来检查得到的高阶信赖域步骤的质量。结合这些不同的方法,可以获得良好的收敛结果:

        - 基于法线映射的信赖域方法所生成的序列的每个聚点都是一个驻点。

        - Kurdyka-Lojasiewicz 理论适用于非凸问题,确保了更强的收敛性和更快的收敛速度。

        - 有机会向快速局部收敛过渡。

        Milzarek 教授随后讨论了该方法在具有挑战性的非凸图像压缩任务中的表现。在应用中,我们从给定的真实图像中寻找一个最佳掩模(即选取图片中最能体现图片特征的一部分像素点)。掩模应该选择尽可能少的像素点来实现最大化压缩率,同时保持高的重建质量。图1为所选取的掩模和通过其所恢复的图像。

图1:非凸图像压缩任务。左侧显示所选取的掩模c。该掩模的密度为4.7%。右图显示仅使用掩模c所包含的像素点来重构

        信赖域法(trssn)和惯性近端梯度法(ipiano)性能的数值实验比较如图3所示。Milzarek教授所提出的高阶方法优于 ipiano,并且使用更少的 CPU 时间得到解并且精确地恢复掩模。

图3:trssn 和ipiano的比较,此图显示了稳态度量变化对应各自所需的CPU时间。

        在讲座的第二部分,Milzarek 教授介绍了一种适用于同一类复合型最小化问题的随机高阶额外步长方案。这种随机方法是由大数据应用和大规模学习任务驱动的,在这种情况下,我们不再易于得到目标函数的全貌,并且计算全梯度和黑塞矩阵(Hessian)也变得十分困难。于是 Milzarek 教授使用随机或不精确的预测,如子抽样方法,来近似梯度和曲率信息。该方法的思想很简单:首先执行半光滑牛顿步的随机版本,并且为了保证收敛性,计算了额外的随机近端梯度步长。额外步骤法非常灵活,因此可以使用不同的步长、随机预测和高阶方法。

        接下来,Milzarek 教授给出了算法的全局收敛的结果,全局的收敛主要得益于由梯度近似所引起的步长和方差的适当平衡。结果表明,与预期的一致,所生成的随机过程几乎确定地接近稳态。

视频回顾