We aim to make stochastic gradient descent (SGD) adaptive to (i) the noise
$\sigma^2$ in the stochastic gradients and (ii) problem-dependent constants.
When minimizing smooth, strongly-convex functions with condition number
$\kappa$, we prove that $T$ iterations of SGD with exponentially decreasing
step-sizes and knowledge of the smoothness can achieve an $\tilde{O} \left(\exp
\left( \frac{-T}{\kappa} \right) + \frac{\sigma^2}{T} \right)$ rate, without
knowing $\sigma^2$. In order to be adaptive to the smoothness, we use a
stochastic line-search (SLS) and show (via upper and lower-bounds) that SGD
with SLS converges at the desired rate, but only to a neighbourhood of the
solution. On the other hand, we prove that SGD with an offline estimate of the
smoothness converges to the minimizer. However, its rate is slowed down
proportional to the estimation error. Next, we prove that SGD with Nesterov
acceleration and exponential step-sizes (referred to as ASGD) can achieve the
near-optimal $\tilde{O} \left(\exp \left( \frac{-T}{\sqrt{\kappa}} \right) +
\frac{\sigma^2}{T} \right)$ rate, without knowledge of $\sigma^2$. When used
with offline estimates of the smoothness and strong-convexity, ASGD still
converges to the solution, albeit at a slower rate. We empirically demonstrate
the effectiveness of exponential step-sizes coupled with a novel variant of
SLS.

通过利用指数步长和随机线性搜索等技术，使得随机梯度下降算法适应不同噪声水平和问题相关的常数，可以在强凸函数的条件下，取得与理论最优相近的收敛速度，同时能够有效地处理噪声和数据不凸的情况。

面向噪声自适应、问题自适应（加速）随机梯度下降

Towards Noise-adaptive, Problem-adaptive (Accelerated) Stochastic  Gradient Descent

We study stochastic gradient descent {\em without replacement} (\sgdwor) for
smooth convex functions. \sgdwor is widely observed to converge faster than
true \sgd where each sample is drawn independently {\em with replacement}
\cite{bottou2009curiously} and hence, is more popular in practice. But it's
convergence properties are not well understood as sampling without replacement
leads to coupling between iterates and gradients. By using method of
exchangeable pairs to bound Wasserstein distance, we provide the first
non-asymptotic results for \sgdwor when applied to {\em general smooth,
strongly-convex} functions. In particular, we show that \sgdwor converges at a
rate of $O(1/K^2)$ while \sgd is known to converge at $O(1/K)$ rate, where $K$
denotes the number of passes over data and is required to be {\em large
enough}. Existing results for \sgdwor in this setting require additional {\em
Hessian Lipschitz assumption} \cite{gurbuzbalaban2015random,haochen2018random}.
For {\em small} $K$, we show \sgdwor can achieve same convergence rate as
\sgd for {\em general smooth strongly-convex} functions. Existing results in
this setting require $K=1$ and hold only for generalized linear models
\cite{shamir2016without}. In addition, by careful analysis of the coupling, for
both large and small $K$, we obtain better dependence on problem dependent
parameters like condition number.

本文提出了一种新的随机梯度下降算法 sgdwor 来优化平滑凸函数，相较于使用独立且重复地采样的传统算法 sgd，sgdwor 算法采样不重复且能获得更快的收敛速度，本文给出了 sgdwor 算法在一般的平滑且强凸函数下的首个非渐进结果：k 次通信传输后，sgdwor 算法的收敛速度为 O (1/k^2)，并与 sgd 算法在小 k 下具有相同收敛率，同时对问题相关参数（如条件数）的依赖性更弱。

不带替换的 SGD：一般平滑凸函数更锐利的速率

SGD without Replacement: Sharper Rates for General Smooth Convex  Functions

We consider a multi-agent framework for distributed optimization where each
agent has access to a local smooth strongly convex function, and the collective
goal is to achieve consensus on the parameters that minimize the sum of the
agents' local functions. We propose an algorithm wherein each agent operates
asynchronously and independently of the other agents. When the local functions
are strongly-convex with Lipschitz-continuous gradients, we show that the
iterates at each agent converge to a neighborhood of the global minimum, where
the neighborhood size depends on the degree of asynchrony in the multi-agent
network. When the agents work at the same rate, convergence to the global
minimizer is achieved. Numerical experiments demonstrate that Asynchronous
Gradient-Push can minimize the global objective faster than state-of-the-art
synchronous first-order methods, is more robust to failing or stalling agents,
and scales better with the network size.

本文提出了一种异步多代理分布式优化算法，每个代理都有一个局部的强凸平滑函数，共同目标是达成对将代理的局部函数之和最小化的参数进行共识。实验结果表明，与同步一阶方法相比，Asynchronous Gradient-Push 算法收敛速度更快，更具鲁棒性，并且随着网络规模的增大，它的扩展性更好。