mlsanityData to 7 Oct 2026

Stability-based Generalization Analysis of Randomized Coordinate Descent for Pairwise Learning

arXiv 2503.01530 ↗First posted 3 Mar 2025cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

Pairwise learning includes various machine learning tasks, with ranking and metric learning serving as the primary representatives. While randomized coordinate descent (RCD) is popular in various learning problems, there is much less theoretical analysis on the generalization behavior of models trained by RCD, especially under the pairwise learning framework. In this paper, we consider the generalization of RCD for pairwise learning. We measure the on-average argument stability for both convex and strongly convex objective functions, based on which we develop generalization bounds in expectation. The early-stopping strategy is adopted to quantify the balance between estimation and optimization. Our analysis further incorporates the low-noise setting into the excess risk bound to achieve the optimistic bound as O(1/n), where n is the sample size.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 24 of its 56 references that are in the map. First posted on arXiv 3 Mar 2025.

Builds on

24 of 56 references.

References · 24

  1. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 547
  2. 2020Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descentcited by 118
  3. 2019Sharper bounds for uniformly stable algorithmscited by 91
  4. 2016The Landscape of Empirical Risk for Non-convex Lossescited by 86
  5. 2019On Generalization Error Bounds of Noisy Gradient Methods for Non-Convex Learningcited by 57
  6. 2013One-Pass AUC Optimizationcited by 42
  7. 2021Stability and Deviation Optimal Risk Bounds with Convergence Rate O(1/n)cited by 42
  8. 2020Toward Better Generalization Bounds with Locally Elastic Stabilitycited by 41
  9. 2017Algorithmic stability and hypothesis complexitycited by 39
  10. 2023On the Optimization and Generalization of Multi-head Attentioncited by 37
  11. 2013On the Generalization Ability of Online Learning Algorithms for Pairwise Loss Functionscited by 23
  12. 2013On the Complexity Analysis of Randomized Block-Coordinate Descent Methodscited by 21
12 more
  1. 2022Beyond Lipschitz: Sharp Generalization and Excess Risk Bounds for Full-Batch GDcited by 19
  2. 2018Graphical Convergence of Subgradients in Nonconvex Optimization and Learningcited by 17
  3. 2020Differentially Private Stochastic Coordinate Descentcited by 8
  4. 2014Consistency Analysis of an Empirical Minimum Error Entropy Algorithmcited by 7
  5. 2023Select without Fear: Almost All Mini-Batch Schedules Generalize Optimallycited by 5
  6. 2023Minibatch and Local SGD: Algorithmic Stability and Linear Speedup in Generalizationcited by 5
  7. 2015On the Robustness of Regularized Pairwise Learning Methods Based on Kernelscited by 4
  8. 2021Stability and Generalization for Randomized Coordinate Descentcited by 4
  9. 2022Randomized methods for computing optimal transport without regularization and their convergence analysiscited by 3
  10. 2024Generalization analysis with deep ReLU networks for metric and similarity learningcited by 3
  11. 2023On the Stability and Generalization of Triplet Learningcited by 2
  12. 2023Stability-based Generalization Analysis for Mixtures of Pointwise and Pairwise Learningcited by 1

Built on by

Not cited yet.