Structure from Randomness in Halfspace Learning with the Zero-One Loss

Ata Kabán, Robert J. DurrantJAIR 2020 · DOI · OpenReview

Introduction

In the world of machine learning, the "curse of dimensionality" is a well-known specter. Traditional statistical learning theory suggests that when the number of features ($d$) significantly exceeds the number of training samples ($N$), models are prone to overfitting. However, modern practice often contradicts this, with massive models successfully learning from relatively small datasets.

A study by Ata Kabán and Robert J. Durrant, published in the Journal of Artificial Intelligence Research, provides a compelling explanation for this phenomenon. By analyzing data through the lens of Random Projections (RP), the authors demonstrate that high-dimensional learning is feasible due to "benign" geometric structures inherent in the data.

The Challenge of High Dimensions

The primary issue addressed is the vacuousness of classical Vapnik-Chervonenkis (VC) theory in high-dimensional settings. Standard generalization bounds for linear classification typically scale with $\sqrt{d/N}$. In scenarios where $d \gg N$, these bounds become uninformative, predicting error rates that exceed 100%.

While researchers often assume specific structures like sparsity or large margins to mitigate this, such assumptions can be restrictive. Kabán and Durrant propose a more universal approach to measuring "learnability" that automatically identifies whatever benign structure might exist within the data support.

Methodology: Random Projections as a Probe

The authors utilize Random Projection (RP) not just as a dimensionality reduction technique, but as a mathematical "probe" for the original high-dimensional space. RP involves multiplying high-dimensional data by a random matrix to project it into a lower-dimensional space ($k \ll d$).

Their approach involves:

  1. Compressive Learning: Analyzing the Empirical Risk Minimizer learned in the projected space.
  2. Flipping Probability: Calculating the probability that a data point will fall on the opposite side of a decision boundary after random projection.
  3. New Loss Function: Integrating this flipping probability to derive a smooth, scale-invariant loss function that serves as a surrogate for the non-convex zero-one loss.
  4. Gaussian Width: Using high-dimensional geometry concepts to show that the required projection dimension $k$ depends on the data's intrinsic geometry rather than the raw dimensionality $d$.

Key Insights: The Role of Flipping Probability

A central contribution of the paper is the derivation of a new loss function based on the "flipping probability." This probability is a function of the angle $\theta$ between a data point and the normal vector of the separating hyperplane.

Flipping probability $f_k(\theta)$ as a function of the angle $\theta$ for various projection dimensions $k$.

As shown in the figure above, as the projection dimension $k$ increases, the flipping probability $f_k(\theta)$ becomes a sharper approximation of the zero-one loss. This mechanism allows the model to capture "benign" structures: if a classifier's predictions remain stable under random squashing, it has likely captured a robust geometric feature of the data.

Furthermore, this approach reveals a "Great Unification" in machine learning. The authors show that Large Margin Distribution Machines (LDM) and the exponential loss used in Boosting (Adaboost) are essentially different ways of minimizing this flipping probability under random perturbations.

Results and Implications

The theoretical framework was validated using both synthetic "toy" data and six real-world datasets from the UCI repository. Key findings include:

  • Superior Generalization: A classifier minimizing the new theoretical bound ("Bound min.") statistically outperformed standard Support Vector Machines (SVMs) on five out of six UCI datasets.
  • Dimension-Free Bounds: The generalization bounds scale with the intrinsic complexity of the data. If the data resides on a low-dimensional manifold or possesses a large margin, the bounds tighten automatically.
  • Robustness: The "Bound min." approach proved more resilient to outliers and irrelevant details compared to SVMs, which can be sensitive to specific support vectors.

Conclusion

The work of Kabán and Durrant shifts the focus from raw dimensionality to intrinsic geometric structure. By leveraging randomness as a tool for discovery, they provide a theoretical foundation for why high-dimensional learning works in practice. While the current focus is on linear halfspaces and involves non-convex optimization challenges, the insights pave the way for extending these "dimension-free" principles to more complex models like deep neural networks.

Summary updated

Abstract

We prove risk bounds for halfspace learning when the data dimensionality is allowed to be larger than the sample size, using a notion of compressibility by random projection. In particular, we give upper bounds for the empirical risk minimizer learned efficiently from randomly projected data, as well as uniform upper bounds in the full high-dimensional space. Our main findings are the following: i) In both settings, the obtained bounds are able to discover and take advantage of benign geometric structure, which turns out to depend on the cosine similarities between the classifier and points of the input space, and provide a new interpretation of margin distribution type arguments. ii) Furthermore our bounds allow us to draw new connections between several existing successful classification algorithms, and we also demonstrate that our theory is predictive of empirically observed performance in numerical simulations and experiments. iii) Taken together, these results suggest that the study of compressive learning can improve our understanding of which benign structural traits – if they are possessed by the data generator – make it easier to learn an effective classifier from a sample.
BibTeX
@article{kaban2020structure,
  author = {Ata Kabán and Robert J. Durrant},
  title = {{Structure from Randomness in Halfspace Learning with the Zero-One Loss}},
  journal = {J. Artif. Intell. Res.},
  year = {2020},
  doi = {10.1613/jair.1.11506},
}
Figure