Abstract
This paper presents a comprehensive theoretical analysis of non-convex pairwise learning—such as ranking and AUC maximization—in the presence of heavy-tailed gradient noise. By modeling gradient noise using the sub-Weibull distribution and employing novel algorithmic stability tools, the authors establish near-optimal generalization bounds for both standard and minibatch Stochastic Gradient Descent (SGD). The findings suggest that heavy-tailed noise, often viewed as a hindrance, can provide positive dependencies that aid optimization in complex non-convex landscapes.
Introduction
Pairwise learning is a critical paradigm in machine learning for tasks where the loss function depends on pairs of data points, including ranking search results and maximizing the Area Under the Curve (AUC). Given a dataset of $n$ samples, the $O(n^2)$ possible pairs make these problems computationally intensive. While SGD is the standard optimization tool, existing theoretical guarantees often rely on restrictive assumptions of convexity and sub-Gaussian (well-behaved) noise.
In practice, deep learning gradients frequently exhibit heavy tails—extreme values that deviate from standard distributions—and loss functions are typically non-convex. This research bridges the gap between theory and practice by providing a mathematical framework for SGD under these realistic, challenging conditions.
Methodology and Stability Analysis
The authors utilize the concept of algorithmic stability to derive generalization guarantees. A model is considered stable if small perturbations in the training data (e.g., changing one data point) result in minimal changes to the final model. To address the complexities of pairwise learning, the authors developed novel pairwise $\ell_1$ uniform model stability tools specifically designed to handle dependencies in pairwise sampling.
Instead of assuming gradients are bounded by a constant, they model gradient noise using the sub-Weibull distribution. This flexible framework covers a spectrum from well-behaved to very heavy-tailed noise. Furthermore, to analyze non-convexity, they employ the Polyak-Łojasiewicz (PL) condition, a standard assumption that allows for global convergence analysis even when the loss function is not perfectly convex.
As shown in the stability analysis (Figure 1), the proposed methods (Theorems 3, 4, and 5) provide competitive stability bounds compared to previous work, particularly when relaxing the Lipschitz constant ($L$) and strong convexity ($\mu$) requirements in favor of tail-heaviness parameters ($\theta$).
Generalization and Excess Risk
A key contribution of this work is the establishment of tighter generalization error bounds. Under the PL condition, the authors achieved a stability bound of $O(T^{1/4})$, a significant improvement over the $O(T^{1/2})$ bounds found in prior literature.
The excess risk bounds (Figure 2) demonstrate that the proposed non-convex pairwise SGD achieves generalization performance comparable to existing bounds for simpler convex problems. Furthermore, the paper provides the first stability-based analysis for pairwise minibatch SGD, elucidating the interaction between batch size ($b$) and iteration count ($T$). This confirms empirical observations that larger batches can impact generalization if not managed correctly.
Theoretical Insights
- Ditching the "Bounded Gradient" Crutch: Most previous proofs require the gradient to never exceed a certain value. This paper replaces that rigid requirement with the sub-Weibull assumption, making the theory much more applicable to actual deep learning training runs where gradients can occasionally spike.
- Positive Dependencies of Heavy Tails: One of the most interesting findings is that sub-Weibull noise brings "positive dependencies" for optimization. The "jumpiness" of heavy-tailed gradients can help the algorithm navigate complex non-convex landscapes more effectively.
Limitations and Future Work
While this work provides significant upper bounds on error, the corresponding lower bounds (best possible error) remain to be established. Future research could also explore even more extreme noise distributions, such as $\alpha$-stable distributions, and further refine the relationship between the tail-heaviness parameter $\theta$ and the number of iterations $T$ to enhance practical utility.
Summary updated