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.
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.
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