In the past several years, the convergence of the last iterate of the
Stochastic Gradient Descent (SGD) algorithm has triggered people's interest due
to its good performance in practice but lack of theoretical understanding. For
Lipschitz and convex functions, different works have established the optimal
$O(\log(1/\delta)\log T/\sqrt{T})$ or $O(\sqrt{\log(1/\delta)/T})$
high-probability convergence rates for the final iterate, where $T$ is the time
horizon and $\delta$ is the failure probability. However, to prove these
bounds, all the existing works are limited to compact domains or require almost
surely bounded noises. It is natural to ask whether the last iterate of SGD can
still guarantee the optimal convergence rate but without these two restrictive
assumptions. Besides this important question, there are still lots of
theoretical problems lacking an answer. For example, compared with the last
iterate convergence of SGD for non-smooth problems, only few results for smooth
optimization have yet been developed. Additionally, the existing results are
all limited to a non-composite objective and the standard Euclidean norm. It
still remains unclear whether the last-iterate convergence can be provably
extended to wider composite optimization and non-Euclidean norms. In this work,
to address the issues mentioned above, we revisit the last-iterate convergence
of stochastic gradient methods and provide the first unified way to prove the
convergence rates both in expectation and in high probability to accommodate
general domains, composite objectives, non-Euclidean norms, Lipschitz
conditions, smoothness and (strong) convexity simultaneously. Additionally, we
extend our analysis to obtain the last-iterate convergence under heavy-tailed
noises.

研究证明了随机梯度下降法的最终迭代在各种条件下都能以最优的收敛速度收敛，包括期望和高概率收敛，在紧致域、非平滑问题和组合优化中都能适用。

随机梯度方法的最后迭代收敛性再探讨

Revisiting the Last-Iterate Convergence of Stochastic Gradient Methods

In this paper, a new variant of accelerated gradient descent is proposed. The
pro-posed method does not require any information about the objective function,
usesexact line search for the practical accelerations of convergence, converges
accordingto the well-known lower bounds for both convex and non-convex
objective functions,possesses primal-dual properties and can be applied in the
non-euclidian set-up. Asfar as we know this is the rst such method possessing
all of the above properties atthe same time. We also present a universal
version of the method which is applicableto non-smooth problems. We demonstrate
how in practice one can efficiently use thecombination of line-search and
primal-duality by considering a convex optimizationproblem with a simple
structure (for example, linearly constrained).

本文提出一种新的加速梯度下降的变种，该方法不需要任何有关目标函数的信息，使用精确线性搜索进行实际加速收敛，可以根据已知的凸和非凸目标函数的下界进行收敛，具有原始对偶属性，并可在非欧几里得设置中应用。同时，我们还提出了一种适用于非平滑问题的通用方法。