We present a PTAS for learning random constant-depth networks. We show that
for any fixed $\epsilon>0$ and depth $i$, there is a poly-time algorithm that
for any distribution on $\sqrt{d} \cdot \mathbb{S}^{d-1}$ learns random Xavier
networks of depth $i$, up to an additive error of $\epsilon$. The algorithm
runs in time and sample complexity of
$(\bar{d})^{\mathrm{poly}(\epsilon^{-1})}$, where $\bar d$ is the size of the
network. For some cases of sigmoid and ReLU-like activations the bound can be
improved to $(\bar{d})^{\mathrm{polylog}(\epsilon^{-1})}$, resulting in a
quasi-poly-time algorithm for learning constant depth random networks.

该研究提出了一种 PTAS 方法，用于学习随机的常数深度网络，可以较好地适用于学习 Xavier 网络以及 ReLU 等激活函数的情形，并具有准多项式时间复杂度。

大多数神经网络几乎可学习

Most Neural Networks Are Almost Learnable

We give the first dimension-efficient algorithms for learning Rectified
Linear Units (ReLUs), which are functions of the form $\mathbf{x} \mapsto
\max(0, \mathbf{w} \cdot \mathbf{x})$ with $\mathbf{w} \in \mathbb{S}^{n-1}$.
Our algorithm works in the challenging Reliable Agnostic learning model of
Kalai, Kanade, and Mansour (2009) where the learner is given access to a
distribution $\cal{D}$ on labeled examples but the labeling may be arbitrary.
We construct a hypothesis that simultaneously minimizes the false-positive rate
and the loss on inputs given positive labels by $\cal{D}$, for any convex,
bounded, and Lipschitz loss function.
The algorithm runs in polynomial-time (in $n$) with respect to any
distribution on $\mathbb{S}^{n-1}$ (the unit sphere in $n$ dimensions) and for
any error parameter $\epsilon = \Omega(1/\log n)$ (this yields a PTAS for a
question raised by F. Bach on the complexity of maximizing ReLUs). These
results are in contrast to known efficient algorithms for reliably learning
linear threshold functions, where $\epsilon$ must be $\Omega(1)$ and strong
assumptions are required on the marginal distribution. We can compose our
results to obtain the first set of efficient algorithms for learning
constant-depth networks of ReLUs.
Our techniques combine kernel methods and polynomial approximations with a
"dual-loss" approach to convex programming. As a byproduct we obtain a number
of applications including the first set of efficient algorithms for "convex
piecewise-linear fitting" and the first efficient algorithms for noisy
polynomial reconstruction of low-weight polynomials on the unit sphere.

本研究提出了有效学习基于 ReLU 的常深度网络的算法，该算法运用了核方法、多项式逼近和凸优化的 “双损失” 方法，同时获得了解决 “凸分段线性拟合” 和 “在单位球上低权重多项式的噪音重构” 等其他应用。