Global Convergence of Frank Wolfe on One Hidden Layer Networks

Alexandre d'Aspremont, Mert PilanciarXiv 2020 · OpenReview

Introduction

Training neural networks is traditionally viewed through the lens of non-convex optimization, a landscape often characterized by local minima and NP-hard complexity. While practitioners have found immense success using Stochastic Gradient Descent (SGD), the theoretical guarantees for global convergence in these architectures remain elusive. In "Global Convergence of Frank Wolfe on One Hidden Layer Networks," authors Alexandre d’Aspremont and Mert Pilanci bridge this gap. They demonstrate that under specific conditions—namely overparameterization and data whitening—training a one-hidden-layer ReLU network can be treated as a globally convergent convex optimization problem.

The Optimization Challenge: The Linear Minimization Oracle

The core difficulty in training neural networks lies in the selection of weights. In the context of incremental algorithms like Frank-Wolfe (also known as Conditional Gradient), this selection is managed by a Linear Minimization Oracle (LMO). Typically, solving the LMO for a neural network involves a non-convex search for the "best" next neuron to add to the model, a task that is generally NP-hard.

This paper investigates the regimes where this traditionally hard problem becomes tractable. By leveraging the geometry of the data and the architecture of the network, the authors transform the LMO from a non-convex nightmare into a solvable convex program.

Theoretical Framework

The authors' approach relies on several key technical components that redefine the training process:

1. Variation Norm Regularization

By employing an $\ell_1$-like penalty in the space of measures—referred to as the "variation norm"—the authors regularize the network in a way that allows the training to be treated as a convex problem within an infinite-dimensional function space. This shift in perspective is fundamental to applying Frank-Wolfe dynamics to neural architectures.

2. Spike-free Matrices and Data Whitening

A pivotal contribution of the paper is the introduction of "spike-free" data matrices. When a data matrix $A$ is spike-free, the non-convex LMO can be exactly reformulated as a Second Order Cone Program (SOCP). SOCPs are a class of convex optimization problems that can be solved efficiently with standard solvers. The authors show that "whitening" the input data—a common preconditioning technique—helps satisfy this spike-free condition, particularly when the number of samples $n$ is less than or equal to the dimension $d$.

3. The Shapley-Folkman Theorem

To address the gap between the non-convex reality and the convex relaxation, the authors utilize the Shapley-Folkman theorem. This classical result from geometry suggests that as the number of neurons increases, the "duality gap" (the distance from the global optimum) naturally shrinks. This provides a theoretical justification for why "wider" networks are inherently easier to optimize.

Algorithm and Convergence

The paper focuses on the Frank-Wolfe algorithm, which builds the network incrementally by adding one neuron at each iteration. For datasets where $n > d$, the authors propose a Stochastic Frank-Wolfe variant that operates on small, spike-free minibatches.

The primary theoretical result is a proven global convergence rate of $O(1/T)$, where $T$ represents the number of neurons (and iterations). This rate indicates that the training loss and the duality gap decrease steadily as the network expands, a claim supported by the authors' numerical experiments on synthetic Gaussian data and toy networks.

Key Insights

  • Overparameterization as a Catalyst: The research reinforces the modern deep learning paradigm where having more parameters than data points simplifies the optimization geometry rather than complicating it.
  • The Phase Transition: There is a distinct phase transition in optimization difficulty. When $n \le d$, whitened data is almost always spike-free, making global optimization "easy." As $n$ exceeds $d$, the probability of the SOCP successfully solving the LMO drops sharply.
  • Tractable Neuron Selection: The most surprising finding is that the neuron selection step, the historical bottleneck for Frank-Wolfe in deep learning, is exactly solvable via SOCP under the right conditions.

Limitations and Future Directions

While the paper provides a robust theoretical foundation, it notes several limitations:

  • Architectural Constraints: The theory is currently limited to one-hidden-layer ReLU networks. Extending these guarantees to deeper architectures is challenging because the variation norm does not generalize easily to multi-layer stacks.
  • Data Dimensions: The "spike-free" condition is most naturally met when the number of samples is smaller than the input dimension ($n \le d$). While stochastic minibatches offer a workaround, they introduce new complexities regarding precision.
  • Computational Overhead: The required data whitening/preconditioning step can be computationally expensive for very high-dimensional datasets.

In conclusion, this work provides a vital link between functional analysis and neural network training, proving that for certain architectures, global optimality is not just a hope, but a mathematical certainty.

Summary updated

Abstract

We derive global convergence bounds for the Frank Wolfe algorithm when training one hidden layer neural networks. When using the ReLU activation function, and under tractable preconditioning assumptions on the sample data set, the linear minimization oracle used to incrementally form the solution can be solved explicitly as a second order cone program. The classical Frank Wolfe algorithm then converges with rate $O(1/T)$ where $T$ is both the number of neurons and the number of calls to the oracle.
BibTeX
@misc{daspremont2020global,
  author = {Alexandre d'Aspremont and Mert Pilanci},
  title = {{Global Convergence of Frank Wolfe on One Hidden Layer Networks}},
  year = {2020},
  eprint = {2002.02208},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2002.02208},
}
Figure