Optimal Estimates for Pairwise Learning with Deep ReLU Networks
Junyu Zhou Shuo Huang Han Feng Ding-Xuan Zhou
Pairwise learning refers to learning tasks where a loss takes a pair of
samples into consideration. In this paper, we study pairwise learning with deep
ReLU networks and estimate the excess generalization error. For a general loss
satisfying some mild conditions, a sharp bound for the estimation error of
order $O((V\log(n) /n)^{1/(2-\beta)})$ is established. In particular, with the
pairwise least squares loss, we derive a nearly optimal bound of the excess
generalization error which achieves the minimax lower bound up to a logrithmic
term when the true predictor satisfies some smoothness regularities.