去年，MichaelI.Jordan的实验室发表论文《CoCoA: A General Framework for Communication-Efficient Distributed Optimization》，提出了机器学习分布式优化的通用框架CoCoA。机器之心技术顾问王彦辰对研究进行了深度解读。1.Introduction在做深度学习时，现代数据集的规模必须高效设计和开发，理论上算法也必须分布式和优化。分布式系统可以实现可扩展性——无论是垂直扩展还是水平扩展，提高计算和存储能力；但与此同时，算法设计者面临着一些独特的困难。一个特别关键的挑战是开发在机器学习工作负载的背景下有效协调机器之间通信的方法。对于大多数生产集群，网络通信确实比单个工作机器上的本地内存访问慢得多；然而，扩展一台机器显然是不可行的。这个问题可以进一步复杂化，本地计算和远程通信之间的最佳平衡取决于数据集的具体属性（如维度、数据点数量、稀疏度、偏度等）、分布式系统的具体属性（对于例如，数据存储格式、分布式方案和数据访问方式等逻辑方面，以及网络层次、带宽和计算实例规格等物理条件）和负载的特定属性（例如，简单的ETL过程是绝对不同于适合回归的逻辑迭代）。因此，算法设计者必须让他们的优化/机器学习算法足够灵活，在保证快速收敛的前提下，在特定的分布式系统中实现“计算-通信”的最佳平衡。CoCoA是最近由加州大学伯克利分校的MichaelI.Jordan实验室提出的框架，通过对种类繁多的优化问题进行智能分解来实现上述目标。通过自由选择原始目标或对偶目标来解决，该框架成功地利用了凸对偶性，允许将全局问题分解为一组子问题，这些子问题可以在工作机器上并行有效地解决，并将本地更新组合在一起以确保以可证明的方式快速全球收敛。CoCoA有两个显着优势：1）任意局部求解器可以在每个工作机器上最有效地运行；2）计算-通信权衡可以作为形式化问题的一部分进行调整，因此可以针对每个不同的问题和数据集进行调整以进行有效调节。根据数据在分布式集群上的分布（无论是按特征还是按数据点），CoCoA可以将全局问题分解为近似的局部子问题，建议应解决原始目标或对偶目标。每个子问题都使用最先进的现成单机求解器求解，然后将每次迭代的局部更新合并到单个REDUCE步骤中（术语REDUCE借用自MAP-REDUCE）。实验表明，CoCoA可以在SVM、线性/逻辑回归和套索算法上实现高达50倍的加速。在本报告中，我们将了解CoCoA的核心思想和最重要的结论，感兴趣的读者可以在参考资料中找到详细的演示和更多实验。这份报告的目的是启发分布式机器学习领域的读者，并邀请更多人加入我们的讨论，与我们交流知识，为我们的技术社区做出贡献。2.问题设置CoCoA的目标是解决机器学习算法中常见的以下一类优化问题：其中l和r是向量变量u的凸函数。在机器学习领域，l通常是一个单独的函数，表示所有数据点上的经验损失（empiricalloss）之和；而表示p范数的正则化项。SVM、线性/逻辑回归、套索和稀疏逻辑回归都属于这一类。这个问题通常在原始空间或对偶空间中解决。在我们的讨论中，我们将这个原始/对偶问题抽象为以下Fenchel-Rockafeller对偶形式：其中α和w是原始/对偶变量，A是包含数据点的列向量的数据矩阵，f*和g*是f和g的凸共轭。非负对偶间隙，其中w(α)=?f(Aα)，提供原始或对偶次优的可计算上限，并且可以在强凸性下找到***解点减少到零。它可用于验证解决方案的质量并作为收敛的标志。根据l的平滑度和r的强凸性，我们可以将目标l(u)+r(u)映射到OA或OB：每种情况的典型情况是：elasticnetregression是CaseI，lasso是CaseII,SVM是CaseIII。这里省略推翻过程。三、CoCoA框架为了在数据分布在K台机器上时最小化目标OA，我们需要将计算分布到K个局部子样本，并在每次全局迭代期间组合K个局部更新。先将数据矩阵A的列分成K个数据分区。对于每个工人机器k，定义，其中i∈Pk，否则。请注意，这种表示与数据的分布方式无关——数据矩阵的维度n和d可以分别表示特征数或数据点数。这种可互换性是CoCoA的一个显着优势——提供灵活的数据分区方式，无论是通过特征还是数据点，取决于哪个更大以及使用哪种算法。分布g(α)很简单，因为它是可分离的；但是为了分布f(Aα)，我们需要最小化它的二次近似值。我们定义以下只读取局部数据子样本的局部二次子问题：表示机器k上的列集，类似于上一次迭代的共享向量，表示局部变量αi在所有i∈Pk上的变化，并且它是当i?Pk时为零。这个子问题是围绕固定v的邻域f的线性化，可以通过最有效的二次优化求解器来求解。可以直观地看出，试图用局部变化非常接近地近似全局目标OA。如果每个局部子问题都可以得到最佳解决，那么REDUCEK更新可以解释为OA的f部分的数据独立、块不可知的近似。然而，与传统的近似方法不同，CoCoA不需要完美的局部解。相反，它容忍局部次优（定义为与最佳的预期绝对偏差）并将其纳入自己的收敛范围，如下所示。对于想要重用针对特定问题、数据集和机器配置优化的现有单一求解器的从业者来说，这是一个巨大的优势。完整的算法如下：有两个可调整的超参数：γ控制来自worker机器的更新如何组合，σ'代表数据分区的难度。实际上，对于给定的γ∈(0,1]，我们设置σ':=γK。γ=1和σ'=K保证了最快的收敛，尽管理论上任何一个都应该足够了。有关详细证明，请参阅原始论文。CoCoA的原始对偶灵活性是一个主要优势。尽管我们一直在解决OA，但我们可以自由地将其视为原始问题或对偶问题-如果我们将原始问题映射到OA，那么OA就是原物；如果我们把它映射到OB，那么OA就是对偶。将OA视为原语使我们能够解决像lasso这样的非强凸正则化项，这通常是在数据按特征而不是按数据点分布时出现的。这适用于套索、稀疏逻辑回归或其他类似L1的稀疏诱导先验。解决CoCoA的这个原始变体每次全局迭代的通信成本为O（数据点数）。另一方面，将OA视为对偶允许我们考虑非平滑损失，例如SVM的铰链损失或绝对偏差损失，并且当数据按数据点而非特征分布时效果最佳。这种变体每次全局迭代的通信成本为O（特征数量）。下面是这两个CoCoA变体的总结：重用上表，我们现在得到：下表给出了CoCoA框架中构建的常见模型的示例：在原始设置（算法2）中，局部子问题变成了局部数据块上的二次问题，其中只有局部数据块被正则化。在对偶设置（算法3）中，经验损失仅应用于局部，它使用由二次项近似的正则化项。4.收敛性分析收敛性的详细论证过于技术化，会混淆我们的讨论。为了避免这种情况，我们这里只给出关键结果。有兴趣的读者可以参考原论文了解详情。为了简化我们的演示，这里给出我们的三个主要假设：数据平均分布在K台机器上；数据矩阵A的列满足||xi||≤1；我们只考虑γ=1和σ'=K，这保证了收敛性，并且在分布式环境中也是最快的。我们的第一个收敛结果涉及使用gi或L-Lipschitz的一般凸性（这两个条件是等价的）：其中L-boundedsupport和-smooth的定义可以在原始论文中找到。该定理涵盖具有非强凸正则化项的模型（例如套索和稀疏逻辑回归）或具有非平滑损失的模型（例如SVM的铰链损失）。我们也可以在stronglyconvexgiorsmooth（这两个条件也是等价的）上表现出更快的线性收敛，这涵盖了elasticnetregression和logisticregression：类似的，μ-strongconvexityofDefinitions也可以在原论文中找到。这两个定理都将以下假设作为局部解Θ质量的定义。该假设基本上将Θ定义为局部二次问题的经验绝对偏差之前的乘法常数。在实践中，分配给并行本地计算的时间应该大致等于所有Kworker池更新的总通信时间成本。将这些收敛定理与我们之前的类别相关联：V.实验我们将CoCoA与几种当前最先进的通用大规模分布式优化算法进行比较，用于套索、弹性网络回归和SVM：MB-SGD：小批量随机梯度下降.对于lasso，我们在L1-prox上与MB-SGD进行比较。我们在ApacheSparkMLlibv1.5.0中实现并优化了它。GD：完全梯度下降。对于套索，我们使用了近似版本PROX-GD。我们在ApacheSparkMLlibv1.5.0中实现并优化了它。L-BFGS：有限记忆拟牛顿法。对于套索，我们使用了OWL-QN（orthant-wiselimitedquasi-Newtonmethod）。我们在ApacheSparkMLlibv1.5.0中实现并优化了它。ADMM：交替方向乘数法。对于套索，我们使用了共轭梯度；对于SVM，我们使用了SDCA（随机双坐标上升）。MB-CD：用于小批量并行化的坐标下降。对于SVM，我们使用MB-SDCA。为了避免麻烦，这里不讲比较涉及的各个方法的调参细节。有兴趣的读者可以参考原始论文以重现论文的结果。对于CoCoA，所有实验都使用随机坐标下降作为单机上的局部求解器。如果使用更复杂的求解器，当然可以进一步提高性能水平。这种开放式的做法留给有兴趣的读者去探索。我们比较的指标是与原始最优性的距离。为此，我们对所有方法运行大量迭代，直到观察不到显着进展，然后选择其中最小的原始值。使用的数据集是：所有代码都是用ApacheSpark编写的，并且都在AmazonEC2m3.xlarge实例上运行（每台机器一个核心）。代码已发布到GitHub：www.github.com/gingsmith/proxcocoa。在原始设置中，我们应用CoCoA在上述每个数据集上拟合套索模型，其中随机坐标下降用作局部求解器，总迭代次数H调节局部解质量Θ。我们还将多核SHOTGUN作为边缘案例。对于MB-CD、SHOTGUN和原始CoCoA，数据集按特征分布；而对于MB-SGD、PROX-GD、OWL??-QN和ADMM，数据集按数据点分布。在几秒钟内绘制原始次优图，我们得到：很明显CoCoA的收敛速度甚至比比较中最好的方法OWL-QN快50倍以上，并且在具有大量特征的数据集上表现出色，这是经常使用套索的领域。在双重设置中，我们考虑拟合SVM。CoCoA使用随机双坐标上升作为局部求解器。所有方法都按数据点分布数据。显然，CoCoA的性能大大超过其他方法。为了理解CoCoA的原始对偶互换性，我们将它的两个变体都拟合到弹性网络回归模型中，并使用坐标下降作为局部求解器。当数据集具有大量特征而不是数据点时，原始CoCoA表现更好并且对强凸性退化具有鲁棒性。另一方面，当数据集有大量数据点而不是特征时，对偶CoCoA表现更好，并且在针对强凸性的损失方面不那么稳健。这提醒从业者，当面对不同的问题设置时，应该使用不同的CoCoA变体——算法2或算法3。原论文还报告了更多有趣的发现，比如原始的CoCoA可以保留局部稀疏性，并且将其最终传递是全局的稀疏性；控制Θ的调谐H允许机器学习系统设计人员一路探索计算通信权衡，以确定当前系统的最佳平衡点。6.总结CoCoA是一个通用的分布式优化框架，可以在分布式集群中实现通信高效的原始对偶优化。它通过利用对偶性将全局目标分解为局部二次近似子问题来实现，这些子问题可以使用架构师选择的任何当前最先进的单机求解器以任意精度并行求解。CoCoA的灵活性使机器学习系统设计人员和算法开发人员可以轻松探索分布式系统的“计算-通信”权衡曲线，并为其特定的硬件配置和计算负载选择最佳平衡点。在实验中，CoCoA将这种选择总结为一个单一的可调超参数H（总迭代次数），其间接等价Θ（局部解的质量）是进入primal和dualCoCoA收敛速度的两个重要理论证明。实证结果表明，CoCoA的性能优于当前最先进的分布式优化方法高达50倍。【本文为栏目组织《机器之心》原创文章，微信公众号《机器之心（id：almosthuman2014）》】点此查看作者更多好文
