信息
学院
王浩
课题组
与合作者在
非凸优化算法
研究中
取得重要进展
,
提出了一种求解非凸Lp范数球投影问题的高效算法
。
相关
成果
被
理论机器学习领域
知名
学术期刊
Journal of Machine Learning Research (JMLR)
接收。
稀疏性已经成为现代数据科学和工程领域中表征感兴趣的参数和信号的基本结构之一。
稀疏性
能
自然地体现
具有少数非零元的$n$-维信号的紧凑模式, 使
得信号
能够
被
少于$n$个数据比特的有效信息表示。例如, 在许多机器学习问题中, 稀疏解克服了欠定线性系统的不适定性, 增强了具有大量冗余特征模型的可解释性, 提高了学习系统的泛化性能, 并保证了模型在训练和推理阶段都显著地节省计算量。
稀疏性通常是通过施加可以诱导稀疏结构的正则项实现,
由此产生的非凸稀疏优化问题
则
对数值优化算法提出了更高
的
要求。
为了系统地促进模型解的稀疏性，
优化与机器学习社区研究者们
对
非凸Lp范数球投影问题
开展
了大量研究
。
然而
，Lp范数非凸、非光滑以及非利普希茨数学性质对算法的分析与设计提出了挑战
，
而且在大规模优化问题中，计算该投影的高效数值算法
也
十分有限。
为此，
研究团队首先推导出表征该问题最优解的一阶必要条件，
继而
设计了一种迭代重加权L1球投影 (Iteratively Reweighted L1 Ball Projection, IRBP) 算法计算一阶驻点的数值方法。
该算法实现简单, 且计算效率高 (图1和图2)。
同时
，研究团队
也
证明了所提算法的全局收敛性以及收敛速率。
该
算法的
提出
为求解
一类难以处理的稀疏约束优化问题提供了
坚实的研究基础
。
图
1 IRBP
求解二维
L
0.5
范数球投影问题产生的迭代序列路径
图2(a) p = 0.4
图2(b)
p = 0.5
图
2 IRBP
与当前先进算法的性能比较
此项研究由上海科技大学、
华盛顿
大学等单位
合作
完成
, 上海科技大学
为
第一完成单位。
信息学院
2019级博士生
杨翔宇
为第一作者
,
王浩教授为
通讯作者
。
论文标题：
Towards an Efficient Approach for the Nonconvex Lp-ball Projection: Algorithm and Analysis
论
文
链接：
https://arxiv.org/abs/2101.01350
