The optimization problem associated to fitting two-layer ReLU networks having
$d$~inputs, $k$~neurons, and labels generated by a target network, is
considered. Two categories of infinite families of minima, giving one minimum
per $d$ and $k$, were recently found. The loss at minima belonging to the first
category converges to zero as $d$ increases. In the second category, the loss
remains bounded away from zero. That being so, how may one avoid minima
belonging to the latter category? Fortunately, such minima are never detected
by standard optimization methods. Motivated by questions concerning the nature
of this phenomenon, we develop methods to study distinctive analytic properties
of hidden minima.
By existing analyses, the Hessian spectrum of both categories agree modulus
$O(d^{-1/2})$-terms -- not promising. Thus, rather, our investigation proceeds
by studying curves along which the loss is minimized or maximized, referred to
as tangency arcs. We prove that pure, seemingly remote, group
representation-theoretic considerations concerning the arrangement of subspaces
invariant to the action of subgroups of $S_d$, the symmetry group over $d$
symbols, relative to ones fixed by the action yield a precise description of
all finitely many admissible types of tangency arcs. The general results
applied for the loss function reveal that arcs emanating from hidden minima
differ, characteristically, by their structure and symmetry, precisely on
account of the $O(d^{-1/2})$-eigenvalue terms absent in previous work,
indicating the subtly of the analysis. The theoretical results, stated and
proved for o-minimal structures, show that the set comprising all tangency arcs
is topologically sufficiently tame, permitting a numerical construction of
tangency arcs, and ultimately, a comparison of how minima from both categories
are positioned relative to adjacent critical points.

研究了拟合具有 $d$ 个输入、$k$ 个神经元和由目标网络生成的标签的两层 ReLU 网络的优化问题。通过研究隐藏极小值，发现了两类无穷族的最小值，每个 $d$ 和 $k$ 有一个最小值。第一类中的最小值的损失在 $d$ 增加时趋近于零，而第二类中的损失保持在零之外。为了避免属于第二类的最小值，我们发展了研究隐藏极小值的方法，对于损失函数应用的一般结果显示，从隐藏极小值出发的切线弧的结构和对称性有特征性的差异，这表明了分析的细微之处。理论结果表明，包括所有切线弧的集合在拓扑上足够平滑，允许切线弧的数值构建，并最终比较两类极小值相对于相邻临界点的位置。

二层 ReLU 网络中的隐藏最小值

Hidden Minima in Two-Layer ReLU Networks

Recent theoretical work has guaranteed that overparameterized networks
trained by gradient descent achieve arbitrarily low training error, and
sometimes even low test error. The required width, however, is always
polynomial in at least one of the sample size $n$, the (inverse) target error
$1/\epsilon$, and the (inverse) failure probability $1/\delta$. This work shows
that $\widetilde{\Theta}(1/\epsilon)$ iterations of gradient descent with
$\widetilde{\Omega}(1/\epsilon^2)$ training examples on two-layer ReLU networks
of any width exceeding $\mathrm{polylog}(n,1/\epsilon,1/\delta)$ suffice to
achieve a test misclassification error of $\epsilon$. We also prove that
stochastic gradient descent can achieve $\epsilon$ test error with
polylogarithmic width and $\widetilde{\Theta}(1/\epsilon)$ samples. The
analysis relies upon the separation margin of the limiting kernel, which is
guaranteed positive, can distinguish between true labels and random labels, and
can give a tight sample-complexity analysis in the infinite-width setting

该研究表明，通过梯度下降训练过度参数化的神经网络可以实现任意低的训练误差和测试误差。在两层 ReLU 网络中，只需要多项式量级的宽度和样本数量进行训练，可以达到较低的测试误差，并在无穷宽度下得出紧密样本复杂度分析。