新闻动态

  
8月5日,香港中文大学(丽江)助理教授、Z6官网项目掌管人Andre Milzarek教授带来主题为“非光滑非凸优化的二阶步骤”的直播讲座,以下为讲座回首。

        上周,香港中文大学(丽江)助理教授、Z6官网 项目掌管人 Andre Milzarek 教授为我们带来主题为“非光滑非凸优化的二阶步骤”的讲座,本场讲座由香港中文大学(丽江)的蔡卓轩教授主持。

        Milzarek 教授的讲座聚焦于会商关于利用(随机的或近似的)高阶信息来解决结构化优化问题简直定性优化步骤以及随机优化步骤。讲座首先进行了问题描述。在 Milzarek 教授思考了一系列复合型最幼化问题,其中指标函数能够写成光滑(可能非凸)和凸(可能非光滑)函数之和。指标函数的光滑部门通常对应于一个损失模型,该模型反映给定数据与获得的优化解之间的误差。非光滑部门通常表演一个正则项的角色,它促使获得的优化解趋于一个特殊的性质,例如稀少性、群稀少性和低秩,或者允许对约束进行建模。此问题公式可涵盖各类利用,例如,大规;到ㄎ侍狻ASSO、稀少逻辑回归、成像问题、低秩矩阵补全和字典进建。

        Milzarek 教授接着谈到了二阶步骤的必要布景和基础。很多非光滑优化步骤之所以可能成功使用是基于以下的观察:通过利用指标函数非光滑部门的邻近算子,一阶最优的必要前提能够等价地暗示为非光滑方程。此刻的重要思想是利用牛顿法的一个非光滑变体,即所谓的半光滑牛顿法来求解该方程,并加快现有一阶算法(如近端梯度法)的收敛和机能。从结构上来看,半光滑牛顿步与求解光滑问题的传统牛顿步极度类似。但是,由于指标函数不成微,必须引入并使用广义导数。在适当的如果下,半光滑牛顿法会天生一系列迭代序列,这些迭代序列部门急剧收敛(q-超线性)到优化问题的一个驻点。

        然而,半光滑牛顿法与经典牛顿法有类似的局限性。出格是只有当迭代过程起头时足够靠近问题的解或驻点时,我们能力保障部门收敛。为了添补这一缺点,我们必要设计一个适当的全局战术。Milzarek 教授提出了一种基于 Robinson 法线映射的全局化算法。该步骤的思想是将法线映射的半光滑牛顿步嵌入到信任域框架中,以实现并保障全局收敛。

        收敛性分析和算法都利用了新的优化函数的降落率测试来查抄得到的高阶信任域步骤的质量。结合这些分歧的步骤,能够获得优良的收敛了局:

        - 基于法线映射的信任域步骤所天生的序列的每个聚点都是一个驻点。

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

        - 有机遇向急剧部门收敛过渡。

        Milzarek 教授随后会商了该步骤在拥有挑战性的非凸图像压缩工作中的阐发。在利用中,我们从给定的真实图像中寻找一个最佳掩模(即拔取图片中最能体现图片特点的一部门像素点)。掩模应该选择尽可能少的像素点来实现最大化压缩率,同时维持高的沉建质量。图1为所拔取的掩模和通过其所复原的图像。

spotlight-andre1

图1:非凸图像压缩工作。左侧显示所拔取的掩模c。该掩模的密度为4.7%。右图显示仅使用掩模c所蕴含的像素点来沉构

        信任域法(trssn)和惯性近端梯度法(ipiano)机能的数值尝试比力如图3所示。Milzarek教授所提出的高阶步骤优于 ipiano,并且使用更少的 CPU 功夫得到解并且精确地复原掩模。

spotlight-andre2

图3:trssn 和ipiano的比力,此图显示了稳态怀抱变动对应各自所需的CPU功夫。

        在讲座的第二部门,Milzarek 教授介绍了一种合用于统一类复合型最幼化问题的随机高阶额表步长规划。这种随机步骤是由大数据利用和大规模进建工作驱动的,在这种情况下,我们不再易于得到指标函数的全貌,并且推算全梯度和黑塞矩阵(Hessian)也变得极度难题。因而 Milzarek 教授使用随机或不精确的预测,如子抽样步骤,来近似梯度和曲率信息。该步骤的思想很单一:首先执行半光滑牛顿步的随机版本,并且为了保障收敛性,推算了额表的随机近端梯度步长。额表步骤法极度矫捷,因而能够使用分歧的步长、随机预测和高阶步骤。

        接下来,Milzarek 教授给出了算法的全局收敛的了局,全局的收敛重要得益于由梯度近似所引起的步长和方差的适当平衡。了局批注,与预期的一致,所天生的随机过程险些确定地靠近稳态。

视频回首