Trajectory-Dependent Generalization Bounds for Pairwise Learning with φ-mixing Samples

Liu, Liyuan; Chen, Hong; Li, Weifu; Gong, Tieliang; Deng, Hao; Wang, Yulong

doi:10.24963/ijcai.2025/639

Trajectory-Dependent Generalization Bounds for Pairwise Learning with φ-mixing Samples

Liyuan Liu, Hong Chen, Weifu Li, Tieliang Gong, Hao Deng, Yulong Wang

Download BibTeX Cite

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence. Main Track. Pages 5743-5751.

https://doi.org/10.24963/ijcai.2025/639

Keywords

Machine Learning: ML: Learning theory

Abstract

Recently, the mathematical tool from fractal geometry (i.e., fractal dimension) has been employed to investigate optimization trajectory-dependent generalization ability for some pointwise learning models with independent and identically distributed (i.i.d.) observations. This paper goes beyond the limitations of pointwise learning and i.i.d. samples, and establishes generalization bounds for pairwise learning with uniformly strong mixing samples. The derived theoretical results fill the gap of trajectory-dependent generalization analysis for pairwise learning, and can be applied to wide learning paradigms, e.g., metric learning, ranking and gradient learning. Technically, our framework brings concentration estimation with Rademacher complexity and trajectory-dependent fractal dimension together in a coherent way for felicitous learning theory analysis. In addition, the efficient computation of fractal dimension can be guaranteed for random algorithms (e.g., stochastic gradient descent algorithm for deep neural networks) by bridging topological data analysis tools and the trajectory-dependent fractal dimension.

Liyuan Liu, Hong Chen, Weifu Li, Tieliang Gong, Hao Deng, and Yulong Wang. 2025. Trajectory-Dependent Generalization Bounds for Pairwise Learning with φ-mixing Samples. In Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-25. IJCAI, 5743–5751. https://doi.org/10.24963/ijcai.2025/639

@inproceedings{ijcai2025p639,
  title     = {Trajectory-Dependent Generalization Bounds for Pairwise Learning with φ-mixing Samples},
  author    = {Liu, Liyuan and Chen, Hong and Li, Weifu and Gong, Tieliang and Deng, Hao and Wang, Yulong},
  booktitle = {Proceedings of the Thirty-Fourth International Joint Conference on
               Artificial Intelligence, {IJCAI-25}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {James Kwok},
  pages     = {5743--5751},
  year      = {2025},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2025/639},
  url       = {https://doi.org/10.24963/ijcai.2025/639},
}

TY  - CPAPER
TI  - Trajectory-Dependent Generalization Bounds for Pairwise Learning with φ-mixing Samples
AU  - Liu, Liyuan
AU  - Chen, Hong
AU  - Li, Weifu
AU  - Gong, Tieliang
AU  - Deng, Hao
AU  - Wang, Yulong
T2  - Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-25
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2025
SP  - 5743
EP  - 5751
DO  - 10.24963/ijcai.2025/639
UR  - https://doi.org/10.24963/ijcai.2025/639
ER  -