【KDD2020】稀疏优化的块分解算法

论文标题：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 上。