Abstract
This research, presented at IJCAI-25, bridges the gap between theoretical generalization analysis and the practical reality of training complex models on dependent data. By leveraging fractal geometry, the authors provide a nuanced explanation for why algorithms like Stochastic Gradient Descent (SGD) generalize effectively in pairwise learning tasks. The study establishes the first generalization bounds for pairwise learning that account for both non-independent ($\phi$-mixing) data and the specific optimization path taken during training.
Introduction: The Over-parameterization Paradox
Traditional machine learning theory often relies on two "idealized" assumptions that frequently fail in real-world applications:
- i.i.d. Data: It assumes data points are independent and identically distributed. However, time series or spatial observations often exhibit temporal or spatial dependencies.
- Hypothesis Space Capacity: Traditional bounds, such as VC-dimension, consider the entire set of possible models. For deep neural networks with millions of parameters, these bounds often become "vacuous," suggesting extreme overfitting that does not occur in practice.
Furthermore, pairwise learning—where the loss function depends on pairs of samples (e.g., ranking or metric learning)—is mathematically more challenging to analyze than standard pointwise learning. This paper addresses these challenges by examining the actual trajectory an algorithm takes through the parameter space, rather than the size of the space itself, while simultaneously handling non-independent data.
Methodology: Fractal Geometry and Mixing Processes
The researchers combine advanced mathematical tools to build a robust theoretical framework:
- Fractal Geometry (Minkowski Dimension): Instead of measuring the total number of parameters, the authors measure the "fractal dimension" of the path taken by the optimization algorithm. If the algorithm visits a structured subset of parameter configurations, its "effective dimension" is significantly lower than its total parameter count.
- $\phi$-Mixing Processes: Data dependency is modeled using "uniformly strong mixing" ($\phi$-mixing), allowing for the analysis of data where future observations are partially dependent on past ones.
- Data-Dependent Pseudo-Metric: To move beyond the requirement for smooth (Lipschitz continuous) loss functions, a new distance metric between models is introduced based on the data itself.
- Algorithmic Trajectories: The hypothesis space is defined by the set of weights $\{w_t\}$ visited during $T$ iterations of the training process.
Key Results and Convergence Analysis
The authors prove that the generalization error for pairwise learning with mixing samples achieves a decay rate of $O\left(\Psi \sqrt{\frac{\log(n)}{n}}\right)$, where $n$ is the sample size and $\Psi$ represents the penalty for data dependency. This rate matches those found in simpler i.i.d. settings while incorporating the complexities of dependent data.
The analysis also establishes a matching lower bound, proving that the relationship between fractal dimension and generalization is fundamentally tight.
Experimental Validation
While primarily theoretical, the findings are validated through numerical experiments using synthetic $\phi$-mixing data and Fully Connected Networks (FCNs) of varying depths. The researchers utilized Topological Data Analysis (TDA) tools, specifically Persistent Homology, to numerically estimate fractal dimensions.
The experiments revealed a strong correlation between the "Persistent Homology dimension" of the SGD trajectory and the actual generalization gap. This provides empirical evidence that fractal dimension serves as a valid proxy for model complexity and generalization performance.
Conclusion and Future Directions
This work highlights that model complexity is not a fixed property of architecture but a property of how the optimizer moves through it. While data dependency slows convergence, the error still decays polynomially as more samples are added.
Future research may focus on:
- Computational Efficiency: Reducing the cost of calculating fractal dimensions for large-scale models like LLMs.
- Broader Dependency Models: Extending the framework to more general processes like $\tau$-mixing.
- Optimizer Analysis: Investigating how different optimizers (e.g., Adam or Lion) influence the fractal dimension of the trajectory and subsequent generalization.
Summary updated