KDD 2020 开源论文 | 稀疏优化的块分解算法

©PaperWeekly 原创 · 作者｜袁淦钊

单位｜鹏城实验室

研究方向｜数值优化、机器学习

 

这次向大家分享的工作是鹏城实验室牵头，联合腾讯 AI 实验室和中山大学在 SIGKDD 2020 上发表的文章：A Block Decomposition Algorithm for Sparse Optimization。

论文标题： A Block Decomposition Algorithm for Sparse Optimization

论文链接： https://arxiv.org/pdf/1905.11031.pdf

相关资料（代码/PPT/相关论文）： https://yuangzh.github.io

稀疏优化由于其内在的组合结构，一般比较难求解。组合搜索方法可以获得其全局最优解，但往往局限于小规模的优化问题；坐标下降方法速度快，但往往陷入于一个较差的局部次优解中。

 

我们提出一种结合组合搜索和坐标下降的块 K 分解算法。具体地说，我们考虑随机策略或/和贪婪策略，选择 K 个坐标作为工作集，然后基于原始目标函数对工作集坐标进行全局组合搜索。我们对块 K 分解算法进行了最优性分析，我们证明了我们的方法比现有的方法找到更强的稳定点。

此外，我们还对算法进行了收敛性分析，并构建其收敛速度。大量的实验表明，我们的方法目前取得的性能臻于艺境。我们的块 K 分解算法的工作发表在国际人工智能会议 SIGKDD 2020 和 CVPR 2019 上。

 

简介

 

本文主要讨论求解以下稀疏约束或稀疏正则优化问题：

 

我们假设 f(x) 是光滑的凸函数。这类问题在压缩感知、信号处理、统计学习等问题上有着广泛的应用。

提出的算法

 

以下是我们提出的块 K 分解算法：

 

算法非常简洁，只有两步。第一步：选择 K 个坐标集，第二步：基于原始目标函数 f(x)，对选择的 K 个坐标作全局组合搜索。

 

该算法也被称为块坐标下降方法，但和以往方法有所不同，有以下四点值得注意：

 

1. 我们使用了临近点策略，这个策略是为了保证充分下降条件和全局收敛性质；

   
   
2. 我们直接求解原来具有组合结构的子问题，而不使用替代函数最小化其上界；
   
   
3. 在坐标选择上，以往可以根据一阶最优条件 / KKT 条件残差来选择坐标，但这种策略对于非凸问题不再适用。我们采用两种策略。一种是随机策略，这种策略的最大的好处是保证算法得到块 K 稳定点（下方将讨论）；另一种是贪心策略，这种策略直接根据目标值下降的多少来选择坐标，在实际中通常可以加速算法收敛；
   
   
4. 在求解子问题中，虽然子问题是 NP 难的，且没有快速的封闭解，但是我们依然可使用全局树形搜索获得全局最优点。注意，K 通常是一个很小的整数；例如，在我们的实验中，K=16。我们考虑简单的二次函数例子： 。我们先系统地穷举下面的全二叉树，通过求解 个线性系统得到所有可能的局部极小值；然后我们选出使得目标值达到最小的那个作为最优解。

与以往的方法的比较

 

目前常见的稀疏优化方法有四类：

 

a. 第一类是松弛近似方法。这类方法最大的缺点是不能直接每一步控制问题的稀疏特性。

 

我们方法优点：可以直接控制解的稀疏特性。

 

b. 第二类是贪心算法。这类方法最大的缺点是初始化点必须为空集或零。

 

 

我们方法优点：可以任意初始化，而且最终精度对初始化不敏感。

 

c. 第三类方法是全局优化算法。这类方法的最大缺点是仅限于小规模问题。

 

 

我们方法优点：利用了全局最优化算法，提高了算法精度。

 

d. 第四类方法是临近梯度方法。这类方法的最大缺点是算法陷入到较差的局部次优值。

我们方法优点：从理论和实验上都优胜于临近梯度方法。

 

最优性分析

 

以下我们定义稀疏优化问题的稳定点：基本稳定点、李普希茨稳定点，块 K 稳定点。

基本稳定点就是指，当非零元指标集已知时，解达到全局最优。这类稳定点的一个很好的性质是：稳定点是可枚举的，这使得我们能够验证某个解是否是该问题的全局最优解。

 

 

李普希茨稳定点是通过一个临近算子来刻画，经典的临近梯度法得到的是李普希茨稳定点。临近梯度法每一步需要求解一个临近算子，该算子有快速封闭解，但是这种简单的上界替代函数方法通常导致算法精度不高。

 

 

这是我们提出的块 K 稳定点的概念。块 K 稳定点是指，当我们（全局地）最小化任意的 K 个坐标（其余的 n-K 个坐标固定不变），我们都不能使得目标函数值得到改进。

 

我们得到以下的关于这三类稳定点的层次关系：

 

 

我们已证明，我们的块 K 稳定点比以往的基本稳定点和李普希茨稳定点更强。可以以上图举例。假如我们从上方的图中的绿色区域（块 K 稳定点）选择一个点，该点落入黄色区域（最优点集）中有一个概率 P1；我们从上方的图中的红色区域（李普希茨稳定点）选择一个点，该点落入黄色区域（最优点集）中有一个概率 P2。由于 P1 总是大于 P2，因此我们的方法更大的概率落入最优解集中。

 

稀疏优化问题由于其组合结构，完全求解这个问题属于大海捞针。我们对稀疏优化问题的全局最优点有了更准确细致的描述，我们对这类问题给出了更精确的近似。

 

可以打个比喻：甲说，鹏城实验室在广东；乙说，鹏城实验室在广东深圳；丙说，鹏城实验室在广东深圳南山区万科云城（详细广告信息可参考本文下方）。丙的说法更准确。

 

收敛性分析

 

我们证明了算法在期望意义上收敛到块 K 稳定点。

 

 

此外，我们证明了算法线性收敛性质（我想大家可能不太感兴趣，可参考我的论文和 PPT）。

 

数值实验

 

6.1 对于稀疏约束优化问题，我们比较了以下9种方法：

 

• Proximal Gradient Method (PGM)

• Accerlated Proximal Gradient Method (APGM)

• Quadratic Penalty Method (QPM)

• Subspace Pursuit (SSP)

• Regularized Orthogonal Matching Pursuit (ROMP)

• Orthogonal Matching Pursuit (OMP)

• Compressive Sampling Matched Pursuit (CoSaMP)

• Convex `1 Approximation Method (CVX-L1)

• Proposed Decomposition Method (DEC-RiGj, 我们的方法)

 

实验1

结论1

 

• 我们的分解方法精度优于其它方法。此外，K 越大，精度越高；

• 使用贪心策略选择 2 个坐标和使用随机策略选择 2 个坐标两种策略相比，前者收敛快但精度差，因此两种坐标选择策略需要结合来使用；

• 我们的方法在 30 秒内收敛。

 

实验2

结论2

 

• 基于迭代硬阈值的方法 {PGM, APGM, QPM} 性能较差；

• OMP 和 ROMP 有时性能较差；

• 在这几个数据集中，我们的方法一致地和较大地优于目前的方法。

 

6.2 对于稀疏正则优化问题，我们比较了以下5中算法：

 

• PGM-L0: PGM for L0 Problem
• APGM-L0: Accerlated PGM for L0 Problem
• PGM-L1: PGM for L1 Problem
• PGM-Lp: PGM for Lp Problem (p=1/2)
• Proposed Decomposition Method (我们的方法)

 

实验1

 

结论1

 

• PGM-Lp 比 PGM-L1 所取得的精度要好；

• 在所有数据集上，我们的分解算法总的来说比其他的方法要好。

 

总结全文

 

我们提出了一种求解稀疏优化问题的有效实用的方法。我们的方法利用了组合搜索和坐标下降的优点。我们的算法无论从理论上还是从实际上，都优于目前最具代表性的稀疏优化方法。我们的块分解算法已被扩展到解决稀疏广义特征值问题（见CVPR 2019）和二值优化问题。

 

招聘

鹏城实验室诚聘 博士后 / 助理研究员（数值优化方向）

岗位名称：博士后/助理研究员

工作地点：鹏城实验室（深圳南山区万科云城）

研究方向：数值算法/（半）离散优化/二阶优化/非凸优化/非光滑优化/机器学习

应聘材料：个人简历+学术成果（论文、科研项目、所获奖项等）发送到下方邮箱

应聘条件：35岁以下近三年内取得计算机/计算数学等学科博士学位+在数值优化/机器学习/机器视觉/数据挖掘等领域以第一作者发表过高水平论文（e.g., CCF A类/SIAM Journal）

岗位待遇：全球范围内有竞争力。

联系方式：yuangzh@pcl.ac.cn

更多阅读

#投 稿 通 道#

 让你的论文被更多人看到 

如何才能让更多的优质内容以更短路径到达读者群体，缩短读者寻找优质内容的成本呢？答案就是：你不认识的人。

总有一些你不认识的人，知道你想知道的东西。PaperWeekly 或许可以成为一座桥梁，促使不同背景、不同方向的学者和学术灵感相互碰撞，迸发出更多的可能性。 

PaperWeekly 鼓励高校实验室或个人，在我们的平台上分享各类优质内容，可以是最新论文解读，也可以是学习心得或技术干货。我们的目的只有一个，让知识真正流动起来。

📝 来稿标准：

• 稿件确系个人原创作品，来稿需注明作者个人信息（姓名+学校/工作单位+学历/职位+研究方向） 

• 如果文章并非首发，请在投稿时提醒并附上所有已发布链接 

• PaperWeekly 默认每篇文章都是首发，均会添加“原创”标志

📬 投稿邮箱：

• 投稿邮箱：hr@paperweekly.site 

• 所有文章配图，请单独在附件中发送 

• 请留下即时联系方式（微信或手机），以便我们在编辑发布时和作者沟通

🔍

现在，在「知乎」也能找到我们了

进入知乎首页搜索「PaperWeekly」

点击「关注」订阅我们的专栏吧

关于PaperWeekly

PaperWeekly 是一个推荐、解读、讨论、报道人工智能前沿论文成果的学术平台。如果你研究或从事 AI 领域，欢迎在公众号后台点击「交流群」，小助手将把你带入 PaperWeekly 的交流群里。