路径坐标优化稀疏学习:算法与理论
本文介绍了 “逐一” 坐标下降算法及其在 $ L_1 $- 惩罚回归(套索)、garotte 和弹性网络等相关方法中的应用,证明了该算法可以与广泛应用的 LARS(或同伦)过程竞争,在大规模 lasso 问题中引起了不少关注。但注意到它并不适用于 “融合 Lasso”,所以论文提出了一个广义算法,在比标准的凸优化器运行时间更短的时间内得出了解决方案。最后,将该过程推广到二维融合 Lasso,并展示了其在一些图像平滑问题上的性能。
Aug, 2007
本篇研究分析几种解决非凸优化问题的新方法,其中目标函数为由非凸光滑项和已知凸简单项组成的总和,提出了随机坐标下降算法,并研究了它们的收敛性质及一些最优性衡量指标。同时,还针对一般情况下的非凸复合优化问题,证明了算法所生成的序列渐近收敛到固定点,同时在某些最优性测度下期望具有亚线性收敛率,如果目标函数满足误差界限条件,则导出了目标函数期望值的局部线性收敛率,并进行了广泛的数值实验来评估算法性能和与现有方法的比较。
May, 2013
本文研究了在稀疏约束下最小化一般连续可微函数的问题,并根据不同的最优性标准提出了三个数值算法:迭代硬阈值法、贪心算法和部分稀疏单纯形法来找到满足最优性标准的点,并分析了这些方法的理论收敛性和与导出的最优性条件的关系。
Mar, 2012
提出一种新的随机坐标下降方法,应用广泛,采用四种新颖的思想,包括平滑、加速、同伦、坐标下降和非均匀采样,具有迭代收敛保证,数值实验表明其优于现有算法。
Nov, 2017
本文探讨了非凸优化中加速近端梯度法及其变体的收敛性,并提出了一种新的变体利用自适应动量和块坐标更新来进一步改进广泛类别的非凸问题中的性能,在稀疏线性回归和正则化中表现出可证明的局部线性收敛性。
Oct, 2017
提出了一种基于 prox-linear surrogate 的原则的优化算法,证明了其全迭代序列收敛于关键点并具有较快的收敛速度,并将其应用于非凸正则化线性回归和非负矩阵分解等问题。
Oct, 2014
本文提出一种新的针对分离结构和非强凸函数的凸凹鞍点问题的高效随机块坐标下降方法,采用自适应原始 - 对偶更新方法,可灵活地并行优化大规模问题。该方法在多个机器学习应用中均有显著提高,包括鲁棒主成分分析、Lasso 和通过组 Lasso 进行特征选择等。在理论和实际上,我们证明了该方法在所有这些应用中都具有明显优势。
Nov, 2015
本文提出并分析了一种新的并行坐标下降方法 ---'NSync',其中在每次迭代中更新随机坐标子集,同时允许非均匀选择子集,我们在强凸性假设下得到了收敛速率,同时说明了如何为集合分配概率以优化界限。该方法的复杂度和实际性能可以比其均匀变体快一个数量级。令人惊讶的是,每个迭代只更新一个随机选择的坐标系的策略 --- 以最优概率 --- 在理论和实践上都可能需要较少的迭代次数,而不是在每个迭代中更新所有坐标系的策略。
Oct, 2013
本文介绍了一种随机外推的原始 - 对偶坐标下降方法,它适应数据矩阵的稀疏性和目标函数的有利结构,更新了仅包含稀疏数据的一小部分原始和对偶变量,并使用较大的步长和密集数据,保留了为每种情况设计的特定方法的优点。此外,我们的方法不需要任何修改即可适应稀疏性,在有利的情况下获得快速收敛保证,特别是我们证明了在度规亚正则情况下的线性收敛,这适用于强凸强凹问题和分段线性二次函数。我们显示了序列的几乎确定收敛和原始 - 对偶间隙和目标值的最优亚线性收敛率,在一般凸凹情况下。数值证据证明了我们的方法在稀疏和密集环境中的最新实证表现,与现有方法相匹配和改进。
Jul, 2020