Data-dependent Algorithmic Robustness Analysis of Pairwise Learning

Donglai WU, Runqiu Wu, Yunwen Lei
Proceedings of the 17th Asian Conference on Machine Learning, PMLR 304:654-669, 2025.

Abstract

This paper develops a new framework to understand generalization for pairwise learning problems, which covers many popular machine learning problems as specific examples. By integrating robust optimization principles with pairwise loss structures, we establish data-dependent generalization bounds that significantly improve over existing approaches. Our method overcomes key limitations of prior work by leveraging observable training data properties rather than restrictive theoretical assumptions. This results in tighter performance guarantees that better reflect real-world learning behavior, particularly for complex datasets with dependent training pairs.

Cite this Paper

BibTeX
@InProceedings{pmlr-v304-wu25b, title = {Data-dependent Algorithmic Robustness Analysis of Pairwise Learning}, author = {WU, Donglai and Wu, Runqiu and Lei, Yunwen}, booktitle = {Proceedings of the 17th Asian Conference on Machine Learning}, pages = {654--669}, year = {2025}, editor = {Lee, Hung-yi and Liu, Tongliang}, volume = {304}, series = {Proceedings of Machine Learning Research}, month = {09--12 Dec}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v304/main/assets/wu25b/wu25b.pdf}, url = {https://proceedings.mlr.press/v304/wu25b.html}, abstract = {This paper develops a new framework to understand generalization for pairwise learning problems, which covers many popular machine learning problems as specific examples. By integrating robust optimization principles with pairwise loss structures, we establish data-dependent generalization bounds that significantly improve over existing approaches. Our method overcomes key limitations of prior work by leveraging observable training data properties rather than restrictive theoretical assumptions. This results in tighter performance guarantees that better reflect real-world learning behavior, particularly for complex datasets with dependent training pairs.} }
Endnote
%0 Conference Paper %T Data-dependent Algorithmic Robustness Analysis of Pairwise Learning %A Donglai WU %A Runqiu Wu %A Yunwen Lei %B Proceedings of the 17th Asian Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2025 %E Hung-yi Lee %E Tongliang Liu %F pmlr-v304-wu25b %I PMLR %P 654--669 %U https://proceedings.mlr.press/v304/wu25b.html %V 304 %X This paper develops a new framework to understand generalization for pairwise learning problems, which covers many popular machine learning problems as specific examples. By integrating robust optimization principles with pairwise loss structures, we establish data-dependent generalization bounds that significantly improve over existing approaches. Our method overcomes key limitations of prior work by leveraging observable training data properties rather than restrictive theoretical assumptions. This results in tighter performance guarantees that better reflect real-world learning behavior, particularly for complex datasets with dependent training pairs.
APA
WU, D., Wu, R. & Lei, Y.. (2025). Data-dependent Algorithmic Robustness Analysis of Pairwise Learning. Proceedings of the 17th Asian Conference on Machine Learning, in Proceedings of Machine Learning Research 304:654-669 Available from https://proceedings.mlr.press/v304/wu25b.html.

Related Material