Skip to content

[Perf #478] LinearSVC: close liblinear-scale fit gap on Iris and Digits #479

Open

Description

@godofecht

Parent: #478

Current canonical v2 losses are real and large: Iris is ~0.613x end-to-end (Flow fit 1.580 ms vs sklearn 0.863 ms; prediction is already much faster), and Digits is ~0.216x (Flow fit 1650.7 ms vs sklearn 356.8 ms). The bottleneck is therefore overwhelmingly fit/solver work, not API overhead.

Audit and profile the LinearSVC training implementation against sklearn/liblinear. Attribute time to coordinate/gradient updates, multiclass strategy, convergence checks, memory layout, repeated dot products, allocation/copies and stopping criteria. Preserve canonical accuracy/parity.

Acceptance: dedicated fit flame/profile breakdown; operation-count comparison against sklearn/liblinear where practical; no avoidable per-sample/per-feature allocation; scaled 100/1k/10k+ sample benchmarks; Iris and Digits end-to-end >=0.95x first, target >=1.05x; prediction must not regress; learned weight/intercept state parity must be reported.

Activity

  1. godofecht commented on Aug 26, 2026

    @godofecht
    OwnerAuthor

    I narrowed the current dense primal Newton path to one solver-level optimization: the active-set Hessian is H = I + 2 C Z_I^T Z_I, so the exact Newton system can be solved matrix-free with Hv = v + 2 C Σ_i z_i(z_i^T v). H is always SPD and λ_min(H) >= 1, so CG is valid and the linear residual directly certifies Newton-direction error: ||d-d*||_2 <= ||r||_2. This removes Θ(n_active d^2) Hessian construction and Θ(d^2) storage; k CG iterations cost Θ(k n_active d), with a rough active-data break-even 2k < d. For Digits d≈65, that makes <~32 Hessian actions the first concrete target. I added the full derivation and an idiomatic Flow witness to OpenProjects under ml/matrix-free-newton-cg-for-linear-svc.{md,flow}. The witness checks dense-vs-matrix-free H·v and recovers a 3D Newton solution in 3 CG iterations. Next local A/B should log n_active, d, CG/PCG iterations, residual norm, linear-solve time, line-search time, and objective/state parity from identical Newton iterates. No hosted CI/workflow use.

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