Normalized gradient descent has shown substantial success in speeding up the
convergence of exponentially-tailed loss functions (which includes exponential
and logistic losses) on linear classifiers with separable data. In this paper,
we go beyond linear models by studying normalized GD on two-layer neural nets.
We prove for exponentially-tailed losses that using normalized GD leads to
linear rate of convergence of the training loss to the global optimum. This is
made possible by showing certain gradient self-boundedness conditions and a
log-Lipschitzness property. We also study generalization of normalized GD for
convex objectives via an algorithmic-stability analysis. In particular, we show
that normalized GD does not overfit during training by establishing finite-time
generalization bounds.

本文探讨了如何在两层神经网络上使用标准化的梯度下降算法，证明了使用标准化梯度下降算法可以实现指数尾数损失函数的快速收敛，并讨论了凸性目标的归纳性及过拟合问题。

学习可分数据的两层神经网络的快速收敛

Fast Convergence in Learning Two-Layer Neural Networks with Separable  Data

The block Kaczmarz method is an iterative scheme for solving overdetermined
least-squares problems. At each step, the algorithm projects the current
iterate onto the solution space of a subset of the constraints. This paper
describes a block Kaczmarz algorithm that uses a randomized control scheme to
choose the subset at each step. This algorithm is the first block Kaczmarz
method with an (expected) linear rate of convergence that can be expressed in
terms of the geometric properties of the matrix and its submatrices. The
analysis reveals that the algorithm is most effective when it is given a good
row paving of the matrix, a partition of the rows into well-conditioned blocks.
The operator theory literature provides detailed information about the
existence and construction of good row pavings. Together, these results yield
an efficient block Kaczmarz scheme that applies to many overdetermined
least-squares problem.

本论文提出了一种采用随机控制方案的块 Kaczmarz 算法，具有预期的线性收敛率，并且在矩阵及其子矩阵的几何特性方面表示，算法的最大效力可实现为矩阵的行铺设及其子块的良好结构，并且与运算符理论文献中提供的好行铺设构造方式相结合，进而实现了对多种超定最小二乘问题的高效块 Kaczmarz 方案。