The limits of squared Euclidean distance regularization

Michal Derezinski, Manfred K. WarmuthNeurIPS 2014 · OpenReview

Standard machine learning algorithms like Gradient Descent with Weight Decay ($L_2$ regularization) are the workhorses of modern AI. However, they possess a fundamental "blind spot." For certain simple linear problems, these algorithms are mathematically destined to be sub-optimal—even when enhanced with kernels. This is because they rely on linear combinations of past instances. In contrast, algorithms using $L_1$ regularization or multiplicative updates (like Exponentiated Gradient) can solve these exact same problems exponentially faster.

The Problem: The Representer Theorem's Liability

In machine learning, we often assume that more data and better regularization lead to better models. The most common family of algorithms, including Gradient Descent (GD) and Support Vector Machines (SVMs), rely on squared Euclidean distance regularization (Weight Decay). These algorithms are governed by the Representer Theorem, meaning their predictions are always a linear combination of the training instances they’ve already seen.

The authors investigate whether this fundamental reliance on linear combinations is a liability. Are there "trivial" learning problems where this entire class of $L_2$-based algorithms fails to learn efficiently? While this was previously known for the specific case of "square loss," this paper generalizes the failure to nearly all common loss functions, including logistic loss and hinge loss.

Constructing the "Hard" Problem

To prove this, the authors construct a "problem matrix" filled with random $\pm 1$ entries. The rows represent instances, and the columns represent potential targets. The goal is to learn a weight vector that "picks out" a specific column.

Instead of just looking at specific algorithms, they use a counting argument based on sign-patterns. They calculate how many different ways a low-rank matrix (which represents the predictions of these algorithms) can "guess" the signs of a random matrix. They prove that a random matrix is "rigid"—it is very hard to approximate its sign pattern with a low-rank construction.

Why $L_2$ Fails: The "Noise" Problem

The core issue lies in how $L_2$ regularization handles irrelevant features. In GD with $L_2$ regularization, the penalty for small weights is negligible (since $w_i^2$ is tiny when $w_i$ is small). Consequently, the algorithm "hangs onto" irrelevant features for a long time, trying to fit the noise.

Weight evolution comparison

In contrast, algorithms like Exponentiated Gradient (EG) or those using $L_1$ regularization (Lasso-style) use multiplicative updates or sparsity-inducing penalties. These mechanisms "wipe out" irrelevant weights exponentially fast, allowing the model to focus on the true signal much earlier. Furthermore, the authors show that using kernels is not a magic bullet: if the underlying algorithm still predicts using linear combinations of these expanded instances, the hardness result holds.

Key Results: Linear vs. Exponential Convergence

The difference in performance is stark. For a 100-dimensional problem, the average loss for standard Gradient Descent decreases roughly linearly with the number of examples seen. In contrast, EG and $L_1$-regularized GD show exponential improvement.

Average loss comparison

The authors prove a lower bound: for a random $n \times n$ matrix, any $L_2$-style algorithm will have an average loss of at least $A - B(k/n)$. Essentially, even after seeing half of the data, the algorithm's error remains significantly high. In the presence of random features, the distance between the algorithm's weight vector and the true target vector is $\sqrt{1 - k/n}$. The algorithm doesn't truly "find" the target until it has seen almost every single instance in the space.

Limitations and Future Work

While mathematically rigorous, these hardness results are demonstrated on a specific type of problem (picking a column from a random matrix), and natural data is rarely truly random.

However, the implications are profound. The authors conjecture that these limitations apply to deep feed-forward neural networks trained with Back-propagation and Weight Decay. While they provide experimental evidence that adding layers doesn't help $L_2$ methods overcome this specific type of hardness, a formal mathematical proof for the multi-layer case remains an open problem. Future work may explore if specific initialization schemes or architectural tweaks in deep learning might circumvent these fundamental bounds.

Summary updated

Abstract

Some of the simplest loss functions considered in Machine Learning are the square loss, the logistic loss and the hinge loss. The most common family of algorithms, including Gradient Descent (GD) with and without Weight Decay, always predict with a linear combination of the past instances. We give a random construction for sets of examples where the target linear weight vector is trivial to learn but any algorithm from the above family is drastically sub-optimal. Our lower bound on the latter algorithms holds even if the algorithms are enhanced with an arbitrary kernel function. This type of result was known for the square loss. However, we develop new techniques that let us prove such hardness results for any loss function satisfying some minimal requirements on the loss function (including the three listed above). We also show that algorithms that regularize with the squared Euclidean distance are easily confused by random features. Finally, we conclude by discussing related open problems regarding feed forward neural networks. We conjecture that our hardness results hold for any training algorithm that is based on the squared Euclidean distance regularization (i.e. Back-propagation with the Weight Decay heuristic).
BibTeX
@inproceedings{derezinski2014limits,
  author = {Michal Derezinski and Manfred K. Warmuth},
  title = {{The limits of squared Euclidean distance regularization}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2014},
  url = {https://openreview.net/forum?id=HJNqyFZu-B},
}
Figure