Learning Halfspaces and Neural Networks with Random Initialization

Yuchen Zhang, Jason D. Lee, Martin J. Wainwright, Michael I. JordanarXiv 2015 · OpenReview

TL;DR

This paper introduces novel algorithms for learning halfspaces and neural networks, even with non-convex loss functions. They demonstrate that while learning can be efficient in terms of data and input dimension, it can be exponentially slow with respect to the desired accuracy and the Lipschitz constant of the loss function. Crucially, they show that for data with a guaranteed margin, learning becomes polynomial in accuracy, and this efficiency is preserved even with noisy labels.

What Problem Does This Paper Address?

The paper tackles the challenge of non-convex empirical risk minimization (ERM), a fundamental problem in machine learning. Specifically, it focuses on learning halfspaces (linear classifiers) and multi-layer neural networks. Traditional ERM aims to find a model that minimizes the average loss over the training data. However, when the loss function is non-convex (like the zero-one loss, which is ideal but hard to optimize), finding the globally optimal model is computationally difficult, often NP-hard. Existing methods often rely on convex relaxations of the loss, which don't always yield the optimal solution for the original non-convex problem. This paper seeks to develop algorithms that can directly handle non-convex losses and provide theoretical guarantees on their performance, exploring the trade-offs between accuracy, sample size, and computational complexity.

Methods

The core of the paper's algorithmic contribution lies in random initialization strategies followed by optimization. For learning halfspaces with general L-Lipschitz loss functions, they propose two algorithms:

  1. Algorithm 1: Initializes the weight vector by drawing uniformly from a sphere of a carefully chosen radius.
  2. Algorithm 2: Uses a more sophisticated initialization derived from solving a least-squares problem on sampled data.

Both algorithms run multiple rounds of initialization and then apply standard optimization techniques. For learning multi-layer neural networks, they introduce Algorithm 3, which recursively generates networks by training shallower networks as weak classifiers. This algorithm also relies on random initialization and optimization steps.

A key technique used in the theoretical analysis is the Johnson-Lindenstrauss lemma for dimensionality reduction, which helps in analyzing the effect of random projections on inner products. They also leverage Rademacher complexity bounds to bound the generalization error.

For the specific case of separable data (where a perfect classifier exists with a margin), they propose Algorithm 4 (BoostNet), which builds upon AdaBoost. This algorithm trains a strong classifier by iteratively combining weak classifiers trained using Algorithm 3 (or its halfspace counterparts).

Datasets

Not discussed in the paper. The theoretical results are presented in terms of general datasets and distributions. The simulation section uses synthetic data for learning parity functions.

Key Insights and Ideas

  • Random Initialization is Key (and Needs Theory): The paper provides theoretical justification for the heuristic use of random initialization in non-convex optimization. It shows that careful treatment of the initialization step is crucial for achieving good theoretical guarantees.
  • Exponential Dependence on Accuracy is (Likely) Unavoidable: For general L-Lipschitz loss functions, the algorithms' time complexity is exponential in $(L/\epsilon^2)\log(L/\epsilon)$, where $\epsilon$ is the desired excess risk. A hardness result (assuming RP ≠ NP) suggests this exponential dependence on accuracy cannot be avoided for learning halfspaces with a specific continuous loss.
  • Margin is a Game-Changer for Neural Networks: When data is separable with a constant margin $\gamma$, learning neural networks becomes significantly more efficient. The BoostNet algorithm achieves polynomial time complexity in $1/\epsilon$ and $1/\gamma$, a stark contrast to the general agnostic learning case.
  • Noise Resilience: The BoostNet algorithm's efficiency for margin-separable data is shown to be robust to random label flipping up to a certain probability.

Key Results

  • Halfspaces: Algorithms achieve arbitrarily small excess risk $\epsilon > 0$ with time complexity polynomial in input dimension $d$ and sample size $n$, but exponential in $(L/\epsilon^2)\log(L/\epsilon)$.
  • Hardness for Halfspaces: Unless RP = NP, no randomized poly(n, d, 1/$\epsilon$)-time algorithm can learn halfspaces with a specific continuous loss to arbitrary accuracy.
  • Neural Networks (Agnostic): Algorithm 3 achieves an $\epsilon$-excess risk with time complexity polynomial in $n, d$, and $\epsilon$, but exponential in $m$ (number of layers), $B$ (weight norm bound), and $1/\epsilon$.
  • Neural Networks (Separable Data): BoostNet (Algorithm 4) learns a neural network that perfectly separates data with margin $\Omega(\gamma)$ in polynomial time in $d, 1/\epsilon, 1/\delta$, and a term $C_{m,B,1/\gamma}$ that depends exponentially on $1/\gamma$. This is a significant improvement over the agnostic case.
  • BoostNet with Noisy Labels: For separable data, BoostNet can learn a network with generalization error $\epsilon$ even when labels are randomly flipped with probability $\eta < 1/2$.
  • Simulation: BoostNet outperforms backpropagation on learning noisy parity functions, especially for higher degrees, suggesting it's less prone to getting stuck in local optima.

Limitations and Future Work

  • Exponential Complexity in Accuracy: The general algorithms for halfspaces and neural networks have time complexity that is exponential in the desired accuracy $\epsilon$. While this is shown to be potentially unavoidable for halfspaces, future work might explore ways to mitigate this for neural networks, especially in practical settings.
  • Constant Margin Assumption: The efficient learning of neural networks relies on the data being separable with a constant margin. Relaxing this assumption or understanding its impact on learnability is a potential future direction.
  • Practical Efficiency: The authors suspect that their theoretical bounds might be conservative, and algorithms could be more efficient in practice. Further empirical studies and analysis of practical performance would be valuable.
  • Specific Architectures: The paper focuses on sigmoid-activated neural networks. Extending the results to other activation functions (like ReLU) or different network architectures could be an area for future research.

Summary updated

Abstract

We study non-convex empirical risk minimization for learning halfspaces and neural networks. For loss functions that are $L$-Lipschitz continuous, we present algorithms to learn halfspaces and multi-layer neural networks that achieve arbitrarily small excess risk $\epsilon>0$. The time complexity is polynomial in the input dimension $d$ and the sample size $n$, but exponential in the quantity $(L/\epsilon^2)\log(L/\epsilon)$. These algorithms run multiple rounds of random initialization followed by arbitrary optimization steps. We further show that if the data is separable by some neural network with constant margin $\gamma>0$, then there is a polynomial-time algorithm for learning a neural network that separates the training data with margin $\Omega(\gamma)$. As a consequence, the algorithm achieves arbitrary generalization error $\epsilon>0$ with ${\rm poly}(d,1/\epsilon)$ sample and time complexity. We establish the same learnability result when the labels are randomly flipped with probability $\eta<1/2$.
BibTeX
@misc{zhang2015learning,
  author = {Yuchen Zhang and Jason D. Lee and Martin J. Wainwright and Michael I. Jordan},
  title = {{Learning Halfspaces and Neural Networks with Random Initialization}},
  year = {2015},
  eprint = {1511.07948},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1511.07948},
}
Figure