We develop new sub-optimality bounds for gradient descent (GD) that depend on
the conditioning of the objective along the path of optimization, rather than
on global, worst-case constants. Key to our proofs is directional smoothness, a
measure of gradient variation that we use to develop upper-bounds on the
objective. Minimizing these upper-bounds requires solving implicit equations to
obtain a sequence of strongly adapted step-sizes; we show that these equations
are straightforward to solve for convex quadratics and lead to new guarantees
for two classical step-sizes. For general functions, we prove that the Polyak
step-size and normalized GD obtain fast, path-dependent rates despite using no
knowledge of the directional smoothness. Experiments on logistic regression
show our convergence guarantees are tighter than the classical theory based on
L-smoothness.

我们开发了一种梯度下降法的新次优性边界，该边界依赖于优化路径中的目标条件，而不是全局最坏情况下的常数。我们的证明关键在于方向平滑性，这是一种梯度变化的度量，我们用它来开发上界约束。通过求解隐式方程来最小化这些上界约束，我们展示了这些方程对于凸二次函数是容易解决的，并为两种传统步长提供了新的保证。对于一般函数，我们证明了 Polyak 步长和归一化梯度下降法尽管不使用方向平滑性的任何知识，但能够获得快速的路径相关性。逻辑回归上的实验证明，我们的收敛保证比基于 L 平滑性的传统理论更紧致。

方向平滑性和梯度方法：收敛性和适应性

Directional Smoothness and Gradient Methods: Convergence and Adaptivity

This paper proposes a novel proximal-gradient algorithm for a decentralized
optimization problem with a composite objective containing smooth and
non-smooth terms. Specifically, the smooth and nonsmooth terms are dealt with
by gradient and proximal updates, respectively. The proposed algorithm is
closely related to a previous algorithm, PG-EXTRA \cite{shi2015proximal}, but
has a few advantages. First of all, agents use uncoordinated step-sizes, and
the stable upper bounds on step-sizes are independent of network topologies.
The step-sizes depend on local objective functions, and they can be as large as
those of the gradient descent. Secondly, for the special case without
non-smooth terms, linear convergence can be achieved under the strong convexity
assumption. The dependence of the convergence rate on the objective functions
and the network are separated, and the convergence rate of the new algorithm is
as good as one of the two convergence rates that match the typical rates for
the general gradient descent and the consensus averaging. We provide numerical
experiments to demonstrate the efficacy of the introduced algorithm and
validate our theoretical discoveries.

本文介绍一种新的分布式优化问题的近端 - 梯度算法，用于处理包含平滑和非平滑项的组合目标，我们提出的新算法与以前的算法相比具有一些优势，例如不需要协调步长和可得到线性收敛。

一种具有网络独立步长和分离收敛速度的去中心化近端梯度方法

A decentralized proximal-gradient method with network independent  step-sizes and separated convergence rates

In this paper, we consider distributed optimization problems where the goal
is to minimize a sum of objective functions over a multi-agent network. We
focus on the case when the inter-agent communication is described by a
strongly-connected, \emph{directed} graph. The proposed algorithm, ADD-OPT
(Accelerated Distributed Directed Optimization), achieves the best known
convergence rate for this class of problems,~$O(\mu^{k}),0<\mu<1$, given
strongly-convex, objective functions with globally Lipschitz-continuous
gradients, where~$k$ is the number of iterations. Moreover, ADD-OPT supports a
wider and more realistic range of step-sizes in contrast to existing work. In
particular, we show that ADD-OPT converges for arbitrarily small (positive)
step-sizes. Simulations further illustrate our results.

本文提出了一种名为 ADD-OPT 的分布式优化算法，它能够在具有强全局性连续 Lipschitz 梯度的强凸目标函数情况下，以最佳已知收敛速度 O (μ^k)，k 为迭代次数。此外，ADD-OPT 支持一定范围的步长，并对此进行了模拟。