Efficient Global Optimization of Two-layer ReLU Networks: Quadratic-time
  Algorithms and Adversarial Training
  The non-convexity of the artificial neural network (ANN) training landscape
brings inherent optimization difficulties. While the traditional
back-propagation stochastic gradient descent (SGD) algorithm and its variants
are effective in certain cases, they can become stuck at spurious local minima
and are sensitive to initializations and hyperparameters. Recent work has shown
that the training of an ANN with ReLU activations can be reformulated as a
convex program, bringing hope to globally optimizing interpretable ANNs.
However, naively solving the convex training formulation has an exponential
complexity, and even an approximation heuristic requires cubic time. In this
work, we characterize the quality of this approximation and develop two
efficient algorithms that train ANNs with global convergence guarantees. The
first algorithm is based on the alternating direction method of multiplier
(ADMM). It solves both the exact convex formulation and the approximate
counterpart. Linear global convergence is achieved, and the initial several
iterations often yield a solution with high prediction accuracy. When solving
the approximate formulation, the per-iteration time complexity is quadratic.
The second algorithm, based on the "sampled convex programs" theory, is simpler
to implement. It solves unconstrained convex formulations and converges to an
approximately globally optimal classifier. The non-convexity of the ANN
training landscape exacerbates when adversarial training is considered. We
apply the robust convex optimization theory to convex training and develop
convex formulations that train ANNs robust to adversarial inputs. Our analysis
explicitly focuses on one-hidden-layer fully connected ANNs, but can extend to
more sophisticated architectures.
