本文针对最小化部分可分平滑凸函数和简单可分离凸函数之和的问题，展示了随机（块）坐标下降法在并行化时可以加速。 研究表明，与串行方法相比，在高概率下近似解决问题所需的迭代次数的理论加速比简单地依赖于并行处理器数量和目标函数平滑部分可分离的自然且易于计算的可分离度度量。 此外，当每次迭代更新的块数是随机的时，该算法的处理能力也非常出色，并可以解决涉及具有 200 亿个非零元素的矩阵的 LASSO 问题。

Dec, 2012

通过开发随机块坐标下降法，我们证明该方法能够以概率至少为 1-rho 获得 Epsilon - 准确解，其迭代次数不超过 O (n / Epsilon*log (1/rho))，并且将前人研究的复杂度缩小 4 倍，消除了对数项中的 Epsilon，并成功地解决了 l1 正则化最小二乘和支持向量机等问题。

Jul, 2011

本文提出了一种分布式随机块坐标下降方法来最小化具有大量变量 / 坐标的凸函数，并分析了其复杂度，其中局部块可分的光滑部分直接影响了其复杂度，进一步扩展了已有研究成果，该方法在分布式环境下的实现还使用了集群计算和计算同步等技术。

Jun, 2014

本文提出了一种并行坐标下降算法，用于解决具有可分离约束的光滑凸优化问题，在线性网络系统的分布式模型预测控制（MPC）中可能出现。我们的算法基于块坐标下降更新，并具有非常简单的迭代。我们证明了该算法在光滑凸优化的标准假设下具有（次）线性收敛率。此外，我们的算法使用本地信息，因此适用于分布式实现。此外，它具有较低的迭代复杂性，适用于嵌入式控制。我们派生了一个基于这种新并行算法的 MPC 方案，其中网络中的每个子系统都可以使用分布式和廉价的计算来计算可行的和稳定的控制输入。为了确保 MPC 方案的稳定性，我们使用从分布式合成中派生的终端成本公式。初步的数字测试显示我们的优化算法比其他现有方法具有更好的性能。

Feb, 2013

本文提出一种新的针对分离结构和非强凸函数的凸凹鞍点问题的高效随机块坐标下降方法，采用自适应原始 - 对偶更新方法，可灵活地并行优化大规模问题。该方法在多个机器学习应用中均有显著提高，包括鲁棒主成分分析、Lasso 和通过组 Lasso 进行特征选择等。在理论和实际上，我们证明了该方法在所有这些应用中都具有明显优势。

Nov, 2015

本文提出了一种异步并行随机坐标下降算法，它具有线性收敛速率和 $1/K$ 的次线性速率，可实现基于多核系统的近线性加速，并取得了在 40 核处理器上的实现结果。

Nov, 2013

本篇研究分析几种解决非凸优化问题的新方法，其中目标函数为由非凸光滑项和已知凸简单项组成的总和，提出了随机坐标下降算法，并研究了它们的收敛性质及一些最优性衡量指标。同时，还针对一般情况下的非凸复合优化问题，证明了算法所生成的序列渐近收敛到固定点，同时在某些最优性测度下期望具有亚线性收敛率，如果目标函数满足误差界限条件，则导出了目标函数期望值的局部线性收敛率，并进行了广泛的数值实验来评估算法性能和与现有方法的比较。

May, 2013

本文提出了一种基于随机块坐标下降和自适应步长的原始 - 对偶更新框架，用于解决具有可分结构的凸 - 凹鞍点问题，并在正则化的经验风险最小化问题上进行了实证分析，结果表明该方法具有较快的收敛速度和良好的表现。

Jun, 2015

本文提出了一种用于解决多块凸优化问题的随机 Primal-Dual 近端块坐标更新框架，并使用其达到 $O (1/t)$ 的收敛速度，且包含现有算法的特例，以及推广至解决随机编程的问题。

May, 2016

该论文介绍了如何加速随机坐标下降方法，提高收敛速度，同时又不用支付每次迭代的代价。它提出了一个新的通用方法，并证明它的收敛性，并在多个领域中获得更快的渐近运行时间。

May, 2013