Press "Enter" to skip to content

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 个坐标作全局组合搜索。

 

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

 

 

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

 

我们直接求解原来具有组合结构的子问题,而不使用替代函数最小化其上界;

 

在坐标选择上,以往可以根据一阶最优条件 / 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)和二值优化问题。

Be First to Comment

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注