acceptodds
Under review as a conference paper at ICLR 2027

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.

Primary area:
optimization
Keywords:
cyclic coordinate descent, quadratic programming, support vector machines, convergence rates

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_6wDoOpenReview ↗
Rating
4
Confidence
2
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

The authors study the rate of convergence for cyclic coordinate descent, when minimizing convex quadratic objectives, with a focus on SVM-dual problems. They demonstrate that convergence depends not only on the Hessian but also on the geometry of the optimum, relative to the constraints.

The authors derive a new convergence bound and perform a boundary-aware convergence analysis. They construct a synthetic optimization problem family where the Hessian is identical, but with arbitrarily slow convergence (thus the Hessian alone is insufficient to discern the convergence rates), and show empirical improvements on SVM benchmarks over prior work.

Critical strengths
  1. The authors make use of information that was previously unutilized for deriving a global convergence bound - by incorporating the geometry of the active constraints (in addition to the Hessian). Demonstrating how boundary conditions affect objective growth, regardless of Hessian singularity. This is a novel approach to a well known problem, and the authors prove its practicality.

  2. The authors construct a well thought-out family of optimization problems (where the Hessian is identical, but convergence is arbitrarily slow) and demonstrate that previous approaches relying solely on the Hessian are insufficient: this is a convincing analysis to support their new convergence analysis and prove its value beyond mere novelty.

Critical weaknesses
  1. In their experiments, the proposed bounds significantly improve on prior theoretical guarantees. However, they are still (sometimes) several orders of magnitude more conservative than observed rates. The question then remains whether the new bounds on convergence are indeed tight, or prior bounds were simply extremely loose.

  2. The main theorem allows for problems with singular Hessians and non-unique optimal points. However, the proposed screening construction requires additional positive-definitiveness for application to the theorem (Eq. 17). The authors acknowledge this limitation, and it is indeed an important practical limitation.

Questions for authors

In the experiments where the proposed bound is weaker than the observed convergence rate, the authors acknowledge that the bound may remain too conservative - what do the authors believe is the source of this discrepancy between the theoretical and experimental result?

1 comment

Dear Reviewer 6wDo,

Thank you for recognizing the novelty and theoretical value of our work, and for your valuable remarks. New and changed text in the revised manuscript is marked in dark teal.

Tightness and the experimental gap. The numerical plots bracket the unknown worst-case one-sweep factor using a spectral upper bound and a finite-search lower estimate. The large ratios in the plots refer to 1−χ1-\chi; both estimates of χ\chi may still be close to one. The upper bound can be conservative because it uses lower bounds on the margins and allows directions excluded by the box or actual sweep. The search can also miss the worst-case starting point, and its approximate reference can lower the witness value. Section 6.1 now explains these sources. Separately, Theorem 2 gives exactness for an interior optimum, and Theorem 4 establishes asymptotic sharpness of the decrease fraction. These sharp cases coexist with conservative bounds on other instances.

Screening limitation. We agree that positive definiteness of the screened matrix is a real practical restriction. It implies a unique optimizer, although the full Hessian may remain singular. The general theorem allows nonunique solutions through growth measured from the nearest optimizer; this particular screened construction does not cover them. Section 4 already makes this distinction explicit.

We also wanted to let you know about the new application in Section 6.2. The theory motivates choosing the cyclic coordinate order by a nearest-neighbor traversal of the training examples. This order is computed once per training fold and reused across the binary SVM fits for different classes and hyperparameter values. Total model-selection time, including order construction and the final refit, falls by 12.5-18.4% relative to the fastest baseline on three datasets.

Reviewer_DiWGOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
1
Soundness
3
Read review
Paper summary

The paper titled “Boundary Geometry and Global Rates of Cyclic Coordinate Descent for SVM Duals” Study exact cycliccoordinate minimization forbox-constrained convex quadratics and develop global contraction bounds that capture both coordinate order and boundary geometry. The current theoretical contraction factors derived from general scalar error bounds are notoriously loose and conservative. The authors aim to derive an instance-specific spectral convergence certificate for cyclic coordinate minimization that explicitly incorporates coordinate order, triangular Hessian interactions, and boundary growth. The paper’s results sharpens Wang & Lin's contraction factor, which has been the most well-known result in this area. On 6 binary classification datasets using linear and RBF kernels, experiments show that the spectral decrease fraction is typically 106 to 108 times sharper than the Wang–Lin bound.

Critical strengths

Connecting the strictly lower triangular part of the Hessian T with a matrix-valued growth surrogate M is mathematically insightful. The paper does have some nice theoretical results. Proposition 3 mathematically proves that the proposed bound strictly beats Wang & Lin's bound providing a clear theoretical result in optimization theory.

Critical weaknesses

Although the spectral bound improves upon Wang & Lin, there is a numerical gap between the certified guarantee and the empirical search witness (differing by a factor of 102 to 104 in Tables 1 and 3, and Figure 1). The formulation is strictly tailored to uncoupled box constraints. SVM formulations that include a bias term often impose a linear equality constraint (yTα=0y^T\alpha=0), which falls entirely outside the scope of this work. Computing the certified rate requires solving dense matrix operations and solving eigen value problems on large matrices. For large SVMs computing this certificate is quite expensive which limits its practical application.

Questions for authors

na

1 comment

Dear Reviewer DiWG,

Thank you for recognizing the mathematical insight and soundness of our work. Your comments prompted us to improve the explanation and add computational evidence. New and revised text is highlighted in dark teal.

Gap between the estimates. Section 6.1 now includes an additional clarification. Conservative margins and proof steps that relax box and sweep constraints can enlarge the upper bound; an incomplete search and an inexact reference point can lower the witness value. The orders-of-magnitude differences concern the decrease fractions 1−χ1-\chi. The contraction factors χ\chi themselves can be numerically close, especially when both are near one. Theorem 2 gives exactness for an interior optimum, and Theorem 4 recovers the leading decrease constant in a singular family.

Intercept. Section 2 now explicitly covers a penalized intercept: adding a unit constant feature gives the penalty b2/2b^2/2 and preserves the box dual. An unregularized intercept introduces the equality constraint you mention and requires coupled updates. This is indeed a limitation of the current setting; the original Discussion already identifies extension to coupled dual constraints as future work.

Computational cost. We added a way to evaluate the linear-kernel certificate without forming a dense Gram matrix. The cost is O(kpd2)O(kpd^2) time and O(pd+d2)O(pd+d^2) memory: pp is the number of examples, dd the feature dimension, and kk the number of positive-definiteness tests used to bracket and refine the spectral value (35-38 in our experiments). Appendices F.6 and G.5 give the procedure and results. On three binary problems with 14,980-20,560 examples, coefficient evaluation takes 0.034-0.098 seconds; including margin construction, each takes under 1.1 seconds on a consumer laptop.

New application. The theory also motivates a practical choice of coordinate order. In Section 6.2, a nearest-neighbor order is reused across multiclass fits and hyperparameters. This reduces total model-selection time by 12.5-18.4% against the fastest baseline on three datasets, including construction of the order and the selected model's refit. Thus the revision adds evidence of an actual runtime benefit alongside the comparison of convergence bounds.

Given your positive assessment of the mathematical insight and soundness, we would appreciate reconsideration of the informativeness and overall assessments in light of these clarifications and new results.

Reviewer_oJaBOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies exact cyclic coordinate descent for box-constrained convex quadratics.

Critical strengths

Theoretically sound, Experiments compare the resulting bounds with existing guarantees. Clear writing as well

Critical weaknesses

This is a good theoretical work, while the importance of this work is not yet fully convincing to me. The bounds are sharper, but not sure how much they change our understanding of cyclic coordinate descent. The paper might need to have concrete use case in deep learning, so it should go beyond theoretical work. Also, this paper might need to have a clear explanation why this bound cannot be obtained from existing restricted-curvature or error-bound analyses. The paper discusses these connections, but I still find it hard to tell which steps need a new argument and which sharpen existing ones.

Spectral computations can additionally cost O(p^3). Would there any better way for this approach? This does not invalidate the global guarantee. But providing these explanations would be helpful to figure out when the certificate is useful beyond retrospective analysis of an already nearly solved problem.

Questions for authors

Overall, I think it can be a good theory paper, but not sure it is well fitted with ICLR. I know there are many pure optimization theory in this domain, while I do not personally agree that this would be directly related to deep learning unless they do not have experiments on real world scale (or at least, MLP scale)

1 comment

Dear Reviewer oJaB,

Thank you for recognizing the theoretical soundness, clear writing, and comparisons with earlier guarantees. Your feedback helped us clarify the contribution and add practical evidence. Changes to the manuscript text are marked in dark teal.

What the bounds explain. The family in Section 5 has a fixed Hessian, and the curvature along its single free coordinate equals one. Yet a vanishing boundary margin δ\delta requires Θ(1/δ)\Theta(1/\delta) sweeps to halve the initial error. Good curvature on the optimal face therefore does not control the time needed to approach it.

Relation to earlier analyses. The expanded proof sketch separates standard coordinate optimality and objective decrease arguments from the matrix step: combining the mixed term and quadratic growth before taking norms. Boundary margins supply growth along Hessian null directions. Proposition 3 sharpens the Wang-Lin rate with the same error-bound constant; global linear convergence was already known.

Cost and practical use. To reduce the cost of evaluating the certificate, we added a structured calculation for linear kernels. For pp examples and dd features, it takes O(kpd2)O(kpd^2) time and O(pd+d2)O(pd+d^2) storage. Here kk is the number of positive-definiteness tests used to bracket and refine the largest eigenvalue (35-38 in our experiments; Appendix F.6). At C=0.1C=0.1, bounds on three binary problems with 14,980-20,560 examples take under 1.1 seconds including margin construction on a consumer laptop.

New application. Section 6.2 uses the three-coordinate result to motivate a nearest-neighbor cyclic order. We construct it once per training fold and reuse it across one-versus-rest classifiers and hyperparameters. Total model-selection time falls by 18.2%, 18.4%, and 12.5% on Wine, Vertebral, and Libras relative to the fastest baseline, including order construction and the final refit. All methods select the same hyperparameters and test predictions agree.

Regarding venue fit, the ICLR 2027 call explicitly includes optimization, learning theory, and kernel learning. Our contribution falls within these areas.

We hope you will reconsider the overall assessment in light of these additions. Since you describe the theory as sound, we would also appreciate clarification of any specific remaining mathematical concern.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.