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

The universal approximation property (UAP) of neural networks is fundamental
for deep learning, and it is well known that wide neural networks are universal
approximators of continuous functions within both the $L^p$ norm and the
continuous/uniform norm. However, the exact minimum width, $w_{\min}$, for the
UAP has not been studied thoroughly. Recently, using a
decoder-memorizer-encoder scheme, \citet{Park2021Minimum} found that $w_{\min}
= \max(d_x+1,d_y)$ for both the $L^p$-UAP of ReLU networks and the $C$-UAP of
ReLU+STEP networks, where $d_x,d_y$ are the input and output dimensions,
respectively. In this paper, we consider neural networks with an arbitrary set
of activation functions. We prove that both $C$-UAP and $L^p$-UAP for functions
on compact domains share a universal lower bound of the minimal width; that is,
$w^*_{\min} = \max(d_x,d_y)$. In particular, the critical width, $w^*_{\min}$,
for $L^p$-UAP can be achieved by leaky-ReLU networks, provided that the input
or output dimension is larger than one. Our construction is based on the
approximation power of neural ordinary differential equations and the ability
to approximate flow maps by neural networks. The nonmonotone or discontinuous
activation functions case and the one-dimensional case are also discussed.

本论文探讨神经网络的最小宽度及其在紧致域中的 UAP，证明了 L^p-UAP 和 C-UAP 共享最小宽度的通用下界，且 L^p-UAP 的临界宽度可以通过使用 Leaky-ReLU 网络达到。