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] LinearSVC: close liblinear-scale fit gap on Iris and Digits #479
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.
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.
Activity
godofecht commentedon Aug 26, 2026
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.