Simplified derivations for high-dimensional convex learning problems

David G. Clark, Haim SompolinskyarXiv 2024 · DOI · arXiv

Introduction

Understanding the fundamental limits of neural networks—such as the maximum capacity of a perceptron or the generalization error of a regression model—traditionally relies on the "replica method" from statistical physics. While powerful, the replica method is often mathematically opaque, requiring complex assumptions like replica-symmetry-breaking (RSB) that can obscure physical intuition.

This paper introduces a unified, intuitive framework using the bipartite cavity method as a simpler alternative. By identifying a shared bipartite structure across point classification, manifold classification, and kernel regression, the authors provide a "recipe" for deriving exact results in statistical learning theory with greater clarity and less algebraic complexity.

Methods: The Bipartite Cavity Approach

The core innovation is the application of the bipartite cavity method (specifically the zero-temperature version) to convex optimization problems. Instead of analyzing the entire system simultaneously, the cavity method examines the effect of adding or removing a single variable.

The authors map these learning problems onto a bipartite graph consisting of two types of nodes:

  1. Feature Variables: e.g., synaptic weights ($w_i$) or eigenbasis errors ($\Delta_i$).
  2. Datum Variables: e.g., Lagrange multipliers ($\lambda^\mu$) or prediction errors ($\epsilon^\mu$).
Bipartite structures for Gardner capacity, Manifold capacity, and Kernel ridge regression.

By analyzing how a "cavity" in the feature layer responds to the data layer, and vice versa, the authors derive self-consistent equations. Crucially, they focus on the Karush-Kuhn-Tucker (KKT) conditions—the rules defining the optimal solution in convex optimization—rather than computing complex partition functions.

Theoretical Framework and Key Insights

The paper highlights several critical insights that emerge from this bipartite perspective:

  • Unified Problem Structure: Classification (Gardner and Manifold) and regression (Kernel Ridge) are shown to be fundamentally similar, consisting of feature and datum layers interacting through random couplings.
  • Scaling Symmetry: The authors identify a specific scaling symmetry (where scaling weights doesn't alter the classification boundary) that explains why earlier "naïve mean-field" approaches fortuitously yielded correct results for perceptron capacity.
  • Physical Response Functions: The method naturally produces "response functions." For instance, in the perceptron problem, the response function $S^w$ represents the weight vector's shift when a new data point is added, which relates directly to the fraction of "supporting points" (the most difficult data points to classify).

Datasets and Evaluation

As a theoretical work, the paper utilizes standard synthetic data models to validate the derivations:

  • Random Points: i.i.d. Gaussian points for the classic Gardner problem.
  • Structured Manifolds: Randomly embedded geometric shapes (spheres, ellipsoids) to model data classes.
  • Kernel Eigenbasis: Random eigenfunction assumptions to model high-dimensional kernel ridge regression.

Key Results

The framework successfully reproduces landmark results with significantly simplified math:

  • Gardner Capacity: Re-derivation of the classic formula for perceptron capacity with a margin.
  • Manifold Capacity: Reproduction of results for classifying structured manifolds, demonstrating that a manifold's "anchor point" behaves like a single point in the Gardner problem.
  • Kernel Ridge Regression: Exact derivation of generalization and training errors, matching results previously obtained through more arduous random matrix theory or replica calculations.

Limitations and Future Directions

The primary limitation is the requirement for convexity. The current framework relies on KKT conditions, which are guaranteed only for global optima in convex landscapes. Non-convex problems, such as deep multi-layer networks, may require more advanced techniques like RSB to account for multiple local minima.

Future work could extend this bipartite approach to:

  • Correlated Data: Moving beyond i.i.d. assumptions to realistic data structures.
  • Soft Margins: Incorporating slack variables for non-linearly separable datasets.
  • Dynamics: Applying the method to the learning dynamics of recurrent neural networks.

Summary updated

BibTeX
@misc{clark2024simplified,
  author = {David G. Clark and Haim Sompolinsky},
  title = {{Simplified derivations for high-dimensional convex learning problems}},
  year = {2024},
  eprint = {2412.01110},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2412.01110},
}
Figure