Skip to content

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

Open

Description

@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.

Activity

  1. godofecht commented on Aug 26, 2026

    @godofecht
    OwnerAuthor

    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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions