In this paper, we aim to build the global convergence theory of encoder-only
shallow Transformers under a realistic setting from the perspective of
architectures, initialization, and scaling under a finite width regime. The
difficulty lies in how to tackle the softmax in self-attention mechanism, the
core ingredient of Transformer. In particular, we diagnose the scaling scheme,
carefully tackle the input/output of softmax, and prove that quadratic
overparameterization is sufficient for global convergence of our shallow
Transformers under commonly-used He/LeCun initialization in practice. Besides,
neural tangent kernel (NTK) based analysis is also given, which facilitates a
comprehensive comparison. Our theory demonstrates the separation on the
importance of different scaling schemes and initialization. We believe our
results can pave the way for a better understanding of modern Transformers,
particularly on training dynamics.

该研究建立了关于编码器式浅层 Transformer 的全局收敛理论，从体系结构、初始化和在有限宽度范围内的缩放的角度进行了现实情景的探究。研究重点在于如何解决 Transformer 核心组成部分 softmax 的问题。研究表明，在实践中使用的 He/LeCun 初始化方式下，我们的浅层 Transformer 的全局收敛只需要二次超参数化，且给出了基于神经切络核的分析，有助于综合比较不同缩放方案和初始化的重要性的差异。我们相信我们的研究结果对于更好地理解现代 Transformer，特别是训练动态方面具有重要意义。

关于编码器型浅层变换器的收敛性研究

On the Convergence of Encoder-only Shallow Transformers

Policy gradient methods are among the most effective methods for large-scale
reinforcement learning, and their empirical success has prompted several works
that develop the foundation of their global convergence theory. However, prior
works have either required exact gradients or state-action visitation measure
based mini-batch stochastic gradients with a diverging batch size, which limit
their applicability in practical scenarios. In this paper, we consider
classical policy gradient methods that compute an approximate gradient with a
single trajectory or a fixed size mini-batch of trajectories under soft-max
parametrization and log-barrier regularization, along with the widely-used
REINFORCE gradient estimation procedure. By controlling the number of "bad"
episodes and resorting to the classical doubling trick, we establish an anytime
sub-linear high probability regret bound as well as almost sure global
convergence of the average regret with an asymptotically sub-linear rate. These
provide the first set of global convergence and sample efficiency results for
the well-known REINFORCE algorithm and contribute to a better understanding of
its performance in practice.

研究了 RL 中的 policy gradient methods，建立了 REINFORCE 算法的全局收敛理论，围绕梯度估计和采样效率等方面进行了研究。

使用 REINFORCE 的高效样本强化学习

Sample Efficient Reinforcement Learning with REINFORCE

Distributed training of $l_1$ regularized classifiers has received great
attention recently. Most existing methods approach this problem by taking steps
obtained from approximating the objective by a quadratic approximation that is
decoupled at the individual variable level. These methods are designed for
multicore and MPI platforms where communication costs are low. They are
inefficient on systems such as Hadoop running on a cluster of commodity
machines where communication costs are substantial. In this paper we design a
distributed algorithm for $l_1$ regularization that is much better suited for
such systems than existing algorithms. A careful cost analysis is used to
support these points and motivate our method. The main idea of our algorithm is
to do block optimization of many variables on the actual objective function
within each computing node; this increases the computational cost per step that
is matched with the communication cost, and decreases the number of outer
iterations, thus yielding a faster overall method. Distributed Gauss-Seidel and
Gauss-Southwell greedy schemes are used for choosing variables to update in
each step. We establish global convergence theory for our algorithm, including
Q-linear rate of convergence. Experiments on two benchmark problems show our
method to be much faster than existing methods.

本研究设计了一种分布式算法来解决 $l_1$ 正则化问题，通过块优化和 Gauss-Seidel 算法更新，达到减少迭代次数和加速算法的目的，在全局收敛率方面得到了理论支持。实验表明，该方法比现有方法更快。