# Fine-grained Analysis of Non-parametric Estimation for Pairwise Learning

arXiv: https://arxiv.org/abs/2305.19640 · HTML: https://mlsanity.com/paper/2305.19640/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 68 references that are in the map.
- First posted on arXiv 31 May 2023.

## Builds on (most cited first, 18 of 18)

- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Error bounds for approximations with deep ReLU networks](https://mlsanity.com/paper/1610.01145/) (2016)
- [On Exact Computation with an Infinitely Wide Neural Net](https://mlsanity.com/paper/1904.11955/) (2019)
- [Nonparametric regression using deep neural networks with ReLU activation function](https://mlsanity.com/paper/1708.06633/) (2017)
- [Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers](https://mlsanity.com/paper/1811.04918/) (2018)
- [Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks](https://mlsanity.com/paper/1703.02930/) (2017)
- [Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networks](https://mlsanity.com/paper/1909.12292/) (2019)
- [Deep Neural Network Approximation Theory](https://mlsanity.com/paper/1901.02220/) (2019)
- [Gradient Descent can Learn Less Over-parameterized Two-layer Neural Networks on Classification Problems](https://mlsanity.com/paper/1905.09870/) (2019)
- [On the Generalization Ability of Online Learning Algorithms for Pairwise Loss Functions](https://mlsanity.com/paper/1305.2505/) (2013)
- [Generalization and Stability of Interpolating Neural Networks with Minimal Width](https://mlsanity.com/paper/2302.09235/) (2023)
- [Stochastic Proximal AUC Maximization](https://mlsanity.com/paper/1906.06053/) (2019)
- [GNNRank: Learning Global Rankings from Pairwise Comparisons via Directed Graph Neural Networks](https://mlsanity.com/paper/2202.00211/) (2022)
- [Pairwise Learning to Rank by Neural Networks Revisited: Reconstruction, Theoretical Analysis and Practical Performance](https://mlsanity.com/paper/1909.02768/) (2019)
- [Depth Selection for Deep ReLU Nets in Feature Extraction and Generalization](https://mlsanity.com/paper/2004.00245/) (2020)
- [Realization of spatial sparseness by deep ReLU nets with massive data](https://mlsanity.com/paper/1912.07464/) (2019)
- [Learning Lipschitz Functions by GD-trained Shallow Overparameterized ReLU Neural Networks](https://mlsanity.com/paper/2212.13848/) (2022)
- [Pairwise Ranking with Gaussian Kernels](https://mlsanity.com/paper/2304.03185/) (2023)

## Built on by (most cited first, 2 of 2)

- [Generalization analysis with deep ReLU networks for metric and similarity learning](https://mlsanity.com/paper/2405.06415/) (2024)
- [Optimization, Generalization and Differential Privacy Bounds for Gradient Descent on Kolmogorov-Arnold Networks](https://mlsanity.com/paper/2601.22409/) (2026)

## Abstract (arXiv)

In this paper, we are concerned with the generalization performance of non-parametric estimation for pairwise learning. Most of the existing work requires the hypothesis space to be convex or a VC-class, and the loss to be convex. However, these restrictive assumptions limit the applicability of the results in studying many popular methods, especially kernel methods and neural networks. We significantly relax these restrictive assumptions and establish a sharp oracle inequality of the empirical minimizer with a general hypothesis space for the Lipschitz continuous pairwise losses. As an example, we apply our general results to study pairwise least squares regression and derive an excess population risk bound that matches the minimax lower bound for the pointwise least squares regression. The key novelty lies in constructing a structured deep ReLU neural network to approximate the true predictor, and in designing a targeted hypothesis space composed of networks with this structure and controllable complexity. Experiments validate the effectiveness of the proposed method. This example demonstrates that the obtained general results indeed help us to explore the generalization performance on a variety of problems that cannot be handled by existing approaches.