Several recent works have studied the convergence \textit{in high
probability} of stochastic gradient descent (SGD) and its clipped variant.
Compared to vanilla SGD, clipped SGD is practically more stable and has the
additional theoretical benefit of logarithmic dependence on the failure
probability. However, the convergence of other practical nonlinear variants of
SGD, e.g., sign SGD, quantized SGD and normalized SGD, that achieve improved
communication efficiency or accelerated convergence is much less understood. In
this work, we study the convergence bounds \textit{in high probability} of a
broad class of nonlinear SGD methods. For strongly convex loss functions with
Lipschitz continuous gradients, we prove a logarithmic dependence on the
failure probability, even when the noise is heavy-tailed. Strictly more general
than the results for clipped SGD, our results hold for any nonlinearity with
bounded (component-wise or joint) outputs, such as clipping, normalization, and
quantization. Further, existing results with heavy-tailed noise assume bounded
$\eta$-th central moments, with $\eta \in (1,2]$. In contrast, our refined
analysis works even for $\eta=1$, strictly relaxing the noise moment
assumptions in the literature.

通过研究一类广泛的非线性随机梯度下降方法在高概率下的收敛界限，我们证明了对于具有 Lipschitz 连续梯度的强凸损失函数，即使在噪声具有重尾分布的情况下，也能实现失败概率的对数依赖性，这对于任何具有有界（逐分量或联合）输出的非线性性质（如剪切、归一化和量化）都是成立的，与以往对于具有重尾噪声的研究相比，我们的研究结果在噪声的矩阶限制上得以松弛。

高概率收敛界限在重尾噪声下的非线性随机梯度下降

High-probability Convergence Bounds for Nonlinear Stochastic Gradient  Descent Under Heavy-tailed Noise

This paper builds upon our prior formalisation of R^n in ACL2(r) by
presenting a set of theorems for reasoning about convex functions. This is a
demonstration of the higher-dimensional analytical reasoning possible in our
metric space formalisation of R^n. Among the introduced theorems is a set of
equivalent conditions for convex functions with Lipschitz continuous gradients
from Yurii Nesterov's classic text on convex optimisation. To the best of our
knowledge a full proof of the theorem has yet to be published in a single piece
of literature. We also explore "proof engineering" issues, such as how to state
Nesterov's theorem in a manner that is both clear and useful.

本文在 ACL2 (r) 平台上对 R^n 进行了形式化处理，并着重研究了凸函数的一组公理和证明，包括了一组关于引理的等价条件，并且探讨了证明工程的问题。

ACL2 (r) 中的凸函数

Convex Functions in ACL2(r)

This paper considers the problem of unconstrained minimization of smooth
convex functions having Lipschitz continuous gradients with known Lipschitz
constant. We recently proposed an optimized gradient method (OGM) for this
problem and showed that it has a worst-case convergence bound for the cost
function decrease that is twice as small as that of Nesterov's fast gradient
method (FGM), yet has a similarly efficient practical implementation. Drori
showed recently that OGM has optimal complexity over the general class of
first-order methods. This optimality makes it important to study fully the
convergence properties of OGM. The previous worst-case convergence bound for
OGM was derived for only the last iterate of a secondary sequence. This paper
provides an analytic convergence bound for the primary sequence generated by
OGM. We then discuss additional convergence properties of OGM, including the
interesting fact that OGM has two types of worst-case functions: a piecewise
affine-quadratic function and a quadratic function. These results help complete
the theory of optimal first-order methods for smooth convex minimization.

本文考虑了光滑凸函数的无约束极小化问题，并给出了分析收敛性质的结果，同时探讨了针对光滑凸函数的最优一阶算法。

优化梯度法的收敛分析

On the convergence analysis of the optimized gradient method

Recently, there have been growing interests in solving consensus optimization
problems in a multi-agent network. In this paper, we develop a decentralized
algorithm for the consensus optimization problem
$$\min\limits_{x\in\mathbb{R}^p}~\bar{f}(x)=\frac{1}{n}\sum\limits_{i=1}^n
f_i(x),$$ which is defined over a connected network of $n$ agents, where each
function $f_i$ is held privately by agent $i$ and encodes the agent's data and
objective. All the agents shall collaboratively find the minimizer while each
agent can only communicate with its neighbors. Such a computation scheme avoids
a data fusion center or long-distance communication and offers better load
balance to the network.
This paper proposes a novel decentralized EXact firsT-ordeR Algorithm
(abbreviated as EXTRA) to solve the consensus optimization problem. "exact"
means that it can converge to the exact solution. EXTRA can use a fixed large
step size, {which is independent of the network size}, and has synchronized
iterations. The local variable of every agent $i$ converges uniformly and
consensually to an exact minimizer of $\bar{f}$. In contrast, the well-known
decentralized gradient descent (DGD) method must use diminishing step sizes in
order to converge to an exact minimizer. EXTRA and DGD have the same choice of
mixing matrices and similar per-iteration complexity. EXTRA, however, uses the
gradients of last two iterates, unlike DGD which uses just that of last
iterate.
EXTRA has the best known convergence rates among the existing first-order
decentralized algorithms. Specifically, if $f_i$'s are convex and have
Lipschitz continuous gradients, EXTRA has an ergodic convergence rate
$O(\frac{1}{k})$ in terms of the first-order optimality residual. If $\bar{f}$
is also restricted strongly convex, EXTRA converges to an optimal solution at a
linear rate $O(C^{-k})$ for some constant $C>1$.

该论文提出了一个名为 EXTRA 的分布式算法，该算法使用固定的步长和同步迭代来解决多智能体网络中的共识优化问题，并具有最佳已知的收敛速率和较好的负载平衡。