Research map / Optimization / Nonconvex and smooth optimization
Stability-based Generalization Analysis of Randomized Coordinate Descent for Pairwise Learning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Analyzes generalization of randomized coordinate descent (RCD) for pairwise learning via on-average argument stability, giving expected excess-risk bounds for convex and strongly convex losses, with early stopping and low-noise refinements.
Problem
Generalization behavior of models trained by randomized coordinate descent under the pairwise learning framework (ranking, metric learning, AUC maximization) is poorly understood, with prior RCD theory limited to pointwise learning or optimization error.
Approach
Extends on-average argument stability analysis to RCD for pairwise losses, using coercivity of the gradient operator in expectation and the self-bounding property of smooth functions to bound stability, then balances estimation and optimization error via early stopping.
Key results
- For convex empirical risk with step size ~ sqrt(L/n) rate, RCD achieves excess risk O(sqrt(L/n)) with T ~ n^{1/2} d L^{-1/2} iterations; under low noise F(w*)=O(1/n) it reaches O(1/n).
- For strongly convex case, excess risk O(sqrt(log(n))/n) type rate (stated as O(L d^{1/2} sqrt(log(nσ/L)) / (nσ^{3/2}))) with T ~ d σ^{-1} log(nσ/L) iterations.
- Experiments on AUC maximization show RCD's on-average stability bound scales as O(T/n^2), with logistic loss yielding smaller iterate distances than hinge loss.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use early stopping to balance estimation and optimization | RCD for pairwise learning · Pairwise learning, convex | excess risk: O(1/\sqrt{n}) | Helped |
| Assume the low-noise condition F(w*) = O(1/n) | RCD for pairwise learning · Pairwise learning, convex | excess risk: O(1/\sqrt{n}) -> O(1/n) | Helped |
| Use strongly convex rather than convex empirical risk | RCD for pairwise learning · Pairwise learning | excess risk: O(1/\sqrt{n}) -> O(\sqrt{\log(n)} / n) | Helped |
| Use strong convexity | RCD for pairwise learning · Pairwise learning, strongly convex | iterations for the stated convergence rate: T \asymp n -> T \asymp \log (n) | Helped |
| Use logistic loss instead of hinge loss | RCD · AUC maximization on a3a, gisette, madelon, and usps | Euclidean distance Δ_t | Helped |
| Use RCD instead of SGD | Pairwise learning stability · AUC maximization on LIBSVM datasets | on-average argument stability: O(T/n^2) vs. O((T/n)^2) | Helped |
Surprising findings
- Under the strongly convex setting, the approximate optimal rate O(1/n) is reachable with only T ~ log(n) iterations, much fewer than the T ~ n needed in the convex case.
Limitations
- Analysis restricted to convex and strongly convex empirical risks; nonconvex and nonparametric cases left open.
- Experiments only verify stability trends empirically on small LIBSVM datasets, not generalization error itself.
- Theoretical rates for strongly convex case are not fully matched to the optimal rate (extra sqrt(log n) factor).
Experimental setup
Datasets: a3a gisette madelon usps
Benchmarks: a3a gisette madelon usps
Metrics: Euclidean distance between iterates on neighboring datasets
Baselines: SGD for pairwise learning
Builds on: on-average argument stability (Lei & Ying 2020) pairwise learning SGD stability (Lei et al. 2021) coercivity of gradient descent operator self-bounding property of smooth functions
Closest papers by meaning
- Error Analysis Affected by Heavy-Tailed Gradients for Non-Convex Pairwise Stochastic Gradient Descent (AAAI 2025 · similarity 0.90)
- Uniform Stability and Generalization Error of GD and SGD on Fixed-Point Parameters (NeurIPS 2026 · similarity 0.89)
- Towards Generalization beyond Pointwise Learning: A Unified Information-theoretic Perspective (ICML 2024 · similarity 0.88)
- Stability and Generalization Analysis of Decentralized SGD: Sharper Bounds Beyond Lipschitzness and Smoothness (ICML 2025 · similarity 0.88)
- Improved Stability and Generalization Guarantees of the Decentralized SGD Algorithm (ICML 2024 · similarity 0.87)
- Algorithmic Stability Unleashed: Generalization Bounds with Unbounded Losses (ICML 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.