查看原文
其他

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

袁淦钊 PaperWeekly 2022-07-04


©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 的交流群里。



您可能也对以下帖子感兴趣

文章有问题?点此查看未经处理的缓存