作者 | 袁淦钊

单位 | 鹏城实验室

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

这次向大家分享的工作是鹏城实验室牵头，联合腾讯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 默认每篇文章都是首发，均会添加“原创”标志

投稿方式：

? 方法一：在PaperWeekly知乎专栏页面点击“投稿”，即可递交文章

? 方法二：发送邮件至：hr@paperweekly.site ，所有文章配图，请单独在附件中发送

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

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

加入社区：http://paperweek.ly

微信公众号：PaperWeekly

新浪微博：@PaperWeekly