- 地址:
- 广东省广州市天河区88号
- 邮箱:
- admin@youweb.com
- 手机:
- 13800000000
- 电话:
- 400-123-4657
作者 | 袁淦钊
单位 | 鹏城实验室
研究方向 | 数值优化、机器学习
这次向大家分享的工作是鹏城实验室牵头,联合腾讯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个坐标作全局组合搜索。
该算法也被称为块坐标下降方法,但和以往方法有所不同,有以下四点值得注意:
- 我们使用了临近点策略,这个策略是为了保证充分下降条件和全局收敛性质;
- 我们直接求解原来具有组合结构的子问题,而不使用替代函数最小化其上界;
- 在坐标选择上,以往可以根据一阶最优条件/KKT条件残差来选择坐标,但这种策略对于非凸问题不再适用。我们采用两种策略。一种是随机策略,这种策略的最大的好处是保证算法得到块K稳定点(下方将讨论);另一种是贪心策略,这种策略直接根据目标值下降的多少来选择坐标,在实际中通常可以加速算法收敛;
- 在求解子问题中,虽然子问题是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