随机块坐标下降方法的复杂性分析
本研究提出了一种基于 Bregman 距离的随机 Bregman(块)坐标下降法,解决了无法全局 Lipschitz 连续(部分)梯度假设的复合问题优化及收敛分析方面的瓶颈,给出了迭代收敛复杂度,并提出了加速 RBCD 方法。
Jan, 2020
本篇论文探讨了一种近似的 BCD 方法,通过 successively 最小化一系列 f 不等式紧上界或者局部严格凸逼近来更新变量块,该方法适用于不可微或非凸问题,并能够实现收敛性的特征描述。这个结果将许多经典算法的收敛结果统一和扩展了,如 BCD 方法、DC 方法、EM 算法和交替近端最小化算法。
Sep, 2012
本文提供了一种对于块坐标下降方法族的统一迭代复杂度分析,涵盖了流行的方法如块坐标梯度下降 (BCGD) 和块坐标近端梯度下降 (BCPG),更进一步地,对于多块非光滑凸性问题,BSUM 框架覆盖的所有算法均能够实现全局次线性迭代复杂度,而在每个块都被精确最小化的块坐标最小化问题中,本文还在无需每个块强凸性假设下建立了次线性收敛速率。此外,在只有两个变量块的情况下,特殊的 Gauss-Seidel 规则的 BSUM 算法能够加速实现 $O (1/r^2)$ 改善率。
Oct, 2013
通过开发随机块坐标下降法,我们证明该方法能够以概率至少为 1-rho 获得 Epsilon - 准确解,其迭代次数不超过 O (n / Epsilon*log (1/rho)),并且将前人研究的复杂度缩小 4 倍,消除了对数项中的 Epsilon,并成功地解决了 l1 正则化最小二乘和支持向量机等问题。
Jul, 2011
本论文提出了一种基于多核并行处理技术和凸逼近的近似并行块协调下降(BCD)方法,并研究了该方法的收敛性,结果表明在 Lasso 问题的特定情况下,循环块选择规则优于随机规则。
Jun, 2014
提出了一种新的基于块坐标下降(OBCD)的非光滑复合优化方法,该方法能够在正交约束下解决一般的非光滑复合问题,是具备收敛保证的可行方法。
Apr, 2023
本文提出了一种基于新颖的正则化最大最小化问题的 Riemann 块坐标下降(RBCD)方法,用于解决高维概率分布下 Wasserstein 距离的问题。该方法能够有效地进行降维和计算,适用于大规模问题。数值结果表明,该方法比现有的一些算法更加高效。
Dec, 2020
本文提出了一种用于训练深度神经网络的光滑的多凸形式,该方法利用了凸分析中的近端点方法,开发了一个块协调下降(BCD)训练算法,证明了其具有全局收敛性和 R - 线性收敛速率,并在实验中展示了优于 Caffe 工具箱中所有随机梯度下降(SGD)变体的表现。
Nov, 2017