Timezone: »

 
Poster
Sharper Generalization Bounds for Pairwise Learning
Yunwen Lei · Antoine Ledent · Marius Kloft

Thu Dec 10 09:00 AM -- 11:00 AM (PST) @ Poster Session 5 #1396
in Poster Session 6 »
Pairwise learning refers to learning tasks with loss functions depending on a pair of training examples, which includes ranking and metric learning as specific examples. Recently, there has been an increasing amount of attention on the generalization analysis of pairwise learning to understand its practical behavior. However, the existing stability analysis provides suboptimal high-probability generalization bounds. In this paper, we provide a refined stability analysis by developing generalization bounds which can be $\sqrt{n}$-times faster than the existing results, where $n$ is the sample size. This implies excess risk bounds of the order $O(n^{-1/2})$ (up to a logarithmic factor) for both regularized risk minimization and stochastic gradient descent. We also introduce a new on-average stability measure to develop optimistic bounds in a low noise setting. We apply our results to ranking and metric learning, and clearly show the advantage of our generalization bounds over the existing analysis.

Author Information

Yunwen Lei (University of Birmingham)

I am currently a Lecturer at School of Computer Science, University of Birmingham. Previously, I was a Humboldt Research Fellow at University of Kaiserslautern, a Research Assistant Professor at Southern University of Science and Technology, and a Postdoctoral Research Fellow at City University of Hong Kong. I obtained my PhD degree in Computer Science at Wuhan University in 2014.

Antoine Ledent (TU Kaiserslautern)

I obtained a PhD in stochastic analysis at the University of Luxembourg, and am now working in statistical learning theory as a postdoc.

Marius Kloft (TU Kaiserslautern)

More from the Same Authors