SGD Algorithms based on Incomplete U-statistics: Large-Scale Minimization of Empirical Risk

Guillaume Papa, Stéphan Clémençon, Aurélien BelletNeurIPS 2015 · OpenReview

Introduction

In standard machine learning paradigms, we typically minimize an empirical risk that is an average over individual data points. However, many critical learning problems require evaluating relationships between multiple points. For instance, ranking (AUC maximization) compares pairs of points, metric learning evaluates distances between similar and dissimilar pairs, and clustering assesses intra-cluster distances.

Mathematically, these objectives are represented as $U$-statistics—averages over $d$-tuples (where $d \ge 2$). The primary challenge here is scale. For a dataset with $n$ observations, there are $O(n^2)$ possible pairs and $O(n^3)$ triplets. In large-scale settings with millions of points, computing the exact gradient involves trillions of operations, rendering traditional batch gradient descent impossible.

To bypass this, researchers typically rely on Stochastic Gradient Descent (SGD). But how should we sample the data to form the gradient estimates? This paper demonstrates that the standard sampling method is suboptimal and proposes a highly efficient alternative based on "incomplete $U$-statistics."

The Sampling Dilemma: Complete vs. Incomplete

When approximating the gradient for $U$-statistic objectives, there are two primary ways to sample the data:

  1. The Standard Approach (Complete $U$-statistics on Subsamples): The conventional method involves selecting a small subset of individual data points ($n'$) and computing the gradient using all possible tuples within that subset. If a computational budget allows for $B$ gradient terms, $n'$ is chosen such that $\binom{n'}{d} = B$.
  2. The Proposed Approach (Incomplete $U$-statistics): The authors propose a disarmingly simple alternative: bypass the subsample entirely and sample $B$ tuples directly from the entire dataset with replacement.

The authors argue that the standard "complete" approach is inefficient because it forces the sampled tuples to be highly dependent (since they share the same underlying $n'$ data points). This dependence restricts the algorithm's ability to effectively reduce the variance of the gradient estimates.

Theoretical Insights: Variance is the Enemy

The convergence speed and generalization ability of SGD are heavily dominated by the variance of its gradient estimates. Through a rigorous conditional performance analysis, the paper establishes a theoretical framework comparing these two sampling strategies.

The key theoretical result proves that for a fixed computational budget (number of gradient evaluations), the variance of the incomplete estimator is strictly lower than that of the subsample-based complete estimator. Furthermore, the efficiency gap between the two methods widens significantly as the complexity (degree $d$) of the $U$-statistic increases. For example, the performance gains are even more dramatic for metric learning (which can involve degree-3 triplets) than for AUC maximization (degree-2 pairs).

Empirical Results

To validate their theoretical claims, the authors evaluated the proposed approach on large-scale datasets, including Covtype (~600,000 examples), IJCNN1 (~200,000 examples), and SUSY (5,000,000 examples).

Comparison of SGD-Incomplete vs SGD-Complete across Covtype and Ijcnn1 datasets.

Across various batch sizes and learning rates, the "Incomplete" SGD consistently reached a lower risk estimate on the test set much faster than the "Complete" version. On the massive 5-million-point SUSY dataset used for metric learning, the performance gap was described as spectacular, with the incomplete approach showing significantly lower variance between runs and achieving vastly superior test error.

Limitations and Future Directions

While sampling tuples directly is statistically superior, the authors acknowledge a practical hardware limitation: it can sometimes be less "cache-friendly." Loading a block of points into memory and forming pairs locally (the complete approach) can be faster per operation on modern hardware than fetching entirely random tuples from across the dataset.

Additionally, this work focuses exclusively on uniform sampling. The authors suggest that future research should explore non-uniform (importance) sampling. By intelligently focusing on "hard" tuples that provide more gradient information, it may be possible to accelerate convergence even further, provided researchers can find tractable ways to approximate the distribution of all possible tuples without incurring an $O(n^d)$ overhead.

Summary updated

Abstract

In many learning problems, ranging from clustering to ranking through metric learning, empirical estimates of the risk functional consist of an average over tuples (e.g., pairs or triplets) of observations, rather than over individual observations. In this paper, we focus on how to best implement a stochastic approximation approach to solve such risk minimization problems. We argue that in the large-scale setting, gradient estimates should be obtained by sampling tuples of data points with replacement (incomplete U-statistics) instead of sampling data points without replacement (complete U-statistics based on subsamples). We develop a theoretical framework accounting for the substantial impact of this strategy on the generalization ability of the prediction model returned by the Stochastic Gradient Descent (SGD) algorithm. It reveals that the method we promote achieves a much better trade-off between statistical accuracy and computational cost. Beyond the rate bound analysis, experiments on AUC maximization and metric learning provide strong empirical evidence of the superiority of the proposed approach.
BibTeX
@inproceedings{papa2015sgd,
  author = {Guillaume Papa and Stéphan Clémençon and Aurélien Bellet},
  title = {{SGD Algorithms based on Incomplete U-statistics: Large-Scale Minimization of Empirical Risk}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2015},
  url = {https://openreview.net/forum?id=HyZB9dZ_br},
}
Figure