[Perf #478] Lasso fit: beat sklearn coordinate descent rather than settling for a near tie

[godofecht]

Parent: #478

Canonical v2 Diabetes: Flow fit 0.784 ms vs sklearn 0.704 ms; Flow predict is much faster (0.0087 ms vs 0.0725 ms). End-to-end is ~0.980x, inside practical-near-tie territory but still below the #478 target.

Profile coordinate updates, residual recomputation, feature norms, convergence/duality-gap checks, memory access, zero-skipping and allocation. Audit whether residuals and norms are maintained incrementally and whether the feature loop vectorizes.

Acceptance: fit-only profile and iteration count comparison; scaled rows/features/sparsity/alpha sweeps; coefficient/intercept and objective-state parity; fit >=1.05x sklearn on the canonical case without regressing prediction.

[godofecht]

I worked through the stopping-rule side of this fit gap. The current Gram CD path already maintains q = X^T r, q0 = X^T y, G = X^T X, and w, so it can compute a certified Lasso duality gap in O(p) per sweep without reconstructing the residual.

For objective P(w)=0.5||y-Xw||^2 + lambda||w||_1, with lambda = alpha * n_samples, use:

r2 = y2 - w^T q0 - w^T q

qinf = ||q||_inf

s = min(1, lambda / qinf) (or 1 when qinf=0)

D = s * (r2 + w^T q) - 0.5 * s^2 * r2

P = 0.5 * r2 + lambda * ||w||_1

gap = P - D

Since theta = s r is dual feasible, P-P* <= gap. That gives a real objective-quality stopping certificate instead of the current absolute max_change < ~1e-16 rule.

On the accompanying synthetic 5x3 Flow witness, gap <= 1e-8 certifies at sweep 14 while the near-machine-epsilon coefficient-motion stop fires materially later. This does not claim the same ratio on Diabetes; the next useful benchmark is to log {sweep, dual_gap, max_change, CD_time} on the canonical row and choose a tolerance that preserves sklearn-equivalent objective/coefficient/prediction diagnostics.

Full derivation + Flow witness are now in godofecht/OpenProjects:
ml/duality-gap-certified-lasso-stopping.md
ml/duality-gap-certified-lasso-stopping.flow

No hosted CI/workflow was used.