acceptodds
Desk rejected at ICLR 2027

Computable Support and Convergence Certificates for Cyclic Coordinate Descent

Desk rejected at ICLR 2027, so left out of the paper lists and the map.

Abstract

When may a sparse optimizer regard its support as final and report a parameter-error bound? We give a finite-candidate test based on uniform curvature of a sign-preserving active neighborhood and strict inactive-gradient margins. The test proves the complete support and signs, uniqueness of the global minimizer, a solution enclosure, and an invariant region with an exact-cycle rate. It requires neither global strong convexity nor absolute diagonal dominance. A rank-deficient quadratic separates this primal test from every standard Gap Safe sphere at the same candidate, regardless of the feasible dual center. We also obtain a descent-safeguarded inexact-update guarantee and an exact-arithmetic certificate test for rational squared loss. Experiments on 30 non-ridge, high-dimensional objectives compare parameter-error decisions with screening followed by the same face analysis. Dual extrapolation reduces the primal test's earlier decisions from 28 to 17, and screened routes remain cheaper for the requested parameter accuracy. The analytic cycle bounds are conservative in the experiments. On 217 compact rational inputs, the test accepts 37 candidates, and exact rational trajectories satisfy the safeguard and cycle budgets.

Primary area:
optimization
Keywords:
cyclic coordinate descent, convex optimization, sparse learning, support certification, active-set identification, a posteriori error bounds, convergence analysis, safe screening, generalized linear models, inexact coordinate descent

Related papers

Discussion (0)

Sign in to comment.