- 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
-
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.
-
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
-
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.
-
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?
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−χ; both estimates of χ 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.