You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{{ message }}
Repository navigation
[Perf #478] Lasso fit: beat sklearn coordinate descent rather than settling for a near tie #486
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.
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
Activity
godofecht commentedon Aug 26, 2026
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, andw, 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, withlambda = alpha * n_samples, use:r2 = y2 - w^T q0 - w^T qqinf = ||q||_infs = min(1, lambda / qinf)(or 1 when qinf=0)D = s * (r2 + w^T q) - 0.5 * s^2 * r2P = 0.5 * r2 + lambda * ||w||_1gap = P - DSince
theta = s ris dual feasible,P-P* <= gap. That gives a real objective-quality stopping certificate instead of the current absolutemax_change < ~1e-16rule.On the accompanying synthetic 5x3 Flow witness,
gap <= 1e-8certifies 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.mdml/duality-gap-certified-lasso-stopping.flowNo hosted CI/workflow was used.