We propose a communication- and computation-efficient distributed
optimization algorithm using second-order information for solving ERM problems
with a nonsmooth regularization term. Current second-order and quasi-Newton
methods for this problem either do not work well in the distributed setting or
work only for specific regularizers. Our algorithm uses successive quadratic
approximations, and we describe how to maintain an approximation of the Hessian
and solve subproblems efficiently in a distributed manner. The proposed method
enjoys global linear convergence for a broad range of non-strongly convex
problems that includes the most commonly used ERMs, thus requiring lower
communication complexity. It also converges on non-convex problems, so has the
potential to be used on applications such as deep learning. Initial
computational results on convex problems demonstrate that our method
significantly improves on communication cost and running time over the current
state-of-the-art methods.

提出了一种使用二阶信息进行通信和计算效率高的分布式优化算法来解决具有非平滑正则化项的 ERM 问题。该算法使用逐步二次逼近法，并描述了如何在分布式方式下有效地维护 Hessian 的逼近并解决子问题。该方法适用于广泛的非强凸问题，具有全局线性收敛性，需要更低的通信复杂度。同时，该方法可以收敛于非凸问题，因此具有在深度学习等应用中使用的潜力。初步的计算结果表明，该方法在凸问题上显著提高了通信成本和运行时间，超越了现有技术的方法。

一种用于非光滑规则化的经验风险最小化的分布式拟牛顿算法

A Distributed Quasi-Newton Algorithm for Empirical Risk Minimization  with Nonsmooth Regularization

The Frank-Wolfe (FW) optimization algorithm has lately re-gained popularity
thanks in particular to its ability to nicely handle the structured constraints
appearing in machine learning applications. However, its convergence rate is
known to be slow (sublinear) when the solution lies at the boundary. A simple
less-known fix is to add the possibility to take 'away steps' during
optimization, an operation that importantly does not require a feasibility
oracle. In this paper, we highlight and clarify several variants of the
Frank-Wolfe optimization algorithm that have been successfully applied in
practice: away-steps FW, pairwise FW, fully-corrective FW and Wolfe's minimum
norm point algorithm, and prove for the first time that they all enjoy global
linear convergence, under a weaker condition than strong convexity of the
objective. The constant in the convergence rate has an elegant interpretation
as the product of the (classical) condition number of the function with a novel
geometric quantity that plays the role of a 'condition number' of the
constraint set. We provide pointers to where these algorithms have made a
difference in practice, in particular with the flow polytope, the marginal
polytope and the base polytope for submodular optimization.

本文研究了 Frank-Wolfe 算法，提出了几个变体并分别给出了全局线性收敛性证明，证明了不同算法的收敛速度取决于几何量与条件数的乘积，这些算法在机器学习，子模优化等领域取得了实际应用。

关于 Frank-Wolfe 优化变量的全局线性收敛性

On the Global Linear Convergence of Frank-Wolfe Optimization Variants

Recently, several convergence rate results for Douglas-Rachford splitting and
the alternating direction method of multipliers (ADMM) have been presented in
the literature. In this paper, we show global linear convergence rate bounds
for Douglas-Rachford splitting and ADMM under strong convexity and smoothness
assumptions. We further show that the rate bounds are tight for the class of
problems under consideration for all feasible algorithm parameters. For
problems that satisfy the assumptions, we show how to select step-size and
metric for the algorithm that optimize the derived convergence rate bounds. For
problems with a similar structure that do not satisfy the assumptions, we
present heuristic step-size and metric selection methods.

本文提出了关于 Douglas-Rachford 分裂算法和交替方向乘子法（ADMM）的全局线性收敛速度界限，说明了在强凸性和平滑性假设下的速率界限，并为所有可行的算法参数考虑到界限紧密性。本文讨论了如何选择算法的步长和指标来优化收敛速度上界，并针对不满足假设但构造相似的问题提出启发式的步长和指标选择方法。