Boundary Geometry and Global Rates of Cyclic Coordinate Descent for SVM Duals
Abstract
Cyclic coordinate descent is widely used to train support vector machines, but global linear convergence alone gives limited guidance about the rate on a particular instance. We study exact cyclic coordinate minimization for box-constrained convex quadratics and develop global contraction bounds that capture both coordinate order and boundary geometry. Our convergence certificate combines two ingredients: interactions between successive coordinate updates, encoded by the triangular part of the normalized Hessian, and objective growth, captured by a matrix lower bound on the optimality gap. It remains valid for cases with singular Hessians, nonunique minimizers, and updates clipped at the boundary. An error-bound specialization of our analysis strictly sharpens the Wang-Lin factor when both use the same error-bound constant. In the positive-definite case, the analysis shows that the worst-case contraction of one Gauss-Seidel sweep remains a global upper bound under box constraints, with equality for an interior optimizer. We also demonstrate the limitations of Hessian-only bounds by constructing a two-coordinate family with a fixed singular normalized Hessian, whose worst-case contraction approaches one as its boundary margin vanishes. The theory is complemented by practical procedures for bounding the worst-case contraction on individual instances and numerical evaluation on several classical SVM datasets.
Related
- Randomized average block coordinate descent method with heavy-ball momentum for tensor least squares problem under the t-product
- Globally Convergent Block Coordinate Descent Algorithms for Semi-Nonnegative Independent Component Analysis
- On randomized batch-sampling coordinate descent methods for solving linear least-squares problems
- How to Train Your Intercept: A Comparison of Intercept Update Strategies in Coordinate Descent
- A Unified Coordinate Descent Framework for Penalized Longitudinal Log-Contrast Quantile Regression
BibTeX
@misc{gladin2026boundary,
title = {{Boundary Geometry and Global Rates of Cyclic Coordinate Descent for SVM Duals}},
author = {Egor Gladin and Eva Ibodova},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.39240},
eprint = {2609.39240},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.39240},
}
RIS
TY - UNPB
TI - Boundary Geometry and Global Rates of Cyclic Coordinate Descent for SVM Duals
AU - Egor Gladin
AU - Eva Ibodova
PY - 2026
DA - 2026/09/30
PB - arXiv
DO - 10.48550/arxiv.2609.39240
UR - https://arxiv.org/abs/2609.39240
AB - Cyclic coordinate descent is widely used to train support vector machines, but global linear convergence alone gives limited guidance about the rate on a particular instance. We study exact cyclic coordinate minimization for box-constrained convex quadratics and develop global contraction bounds that capture both coordinate order and boundary geometry. Our convergence certificate combines two ingredients: interactions between successive coordinate updates, encoded by the triangular part of the normalized Hessian, and objective growth, captured by a matrix lower bound on the optimality gap. It remains valid for cases with singular Hessians, nonunique minimizers, and updates clipped at the boundary. An error-bound specialization of our analysis strictly sharpens the Wang-Lin factor when both use the same error-bound constant. In the positive-definite case, the analysis shows that the worst-case contraction of one Gauss-Seidel sweep remains a global upper bound under box constraints, with equality for an interior optimizer. We also demonstrate the limitations of Hessian-only bounds by constructing a two-coordinate family with a fixed singular normalized Hessian, whose worst-case contraction approaches one as its boundary margin vanishes. The theory is complemented by practical procedures for bounding the worst-case contraction on individual instances and numerical evaluation on several classical SVM datasets.
ER -