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] KernelSVC fit: match libsvm training efficiency without changing semantics #480
Canonical v2: Iris Flow fit 1.075 ms vs sklearn 0.904 ms; Digits Flow fit 111.20 ms vs sklearn 50.47 ms. Prediction on Digits is already faster than sklearn, so the dominant deficit is training.
Profile kernel-matrix construction, cache reuse, SMO/working-set selection, shrinking, convergence checks, support-vector compaction, allocation/copy traffic and repeated kernel evaluations. Compare against sklearn/libsvm's algorithmic work, not only wall clock.
Acceptance: stage-level timing and kernel-evaluation counts; explicit cache-hit/miss evidence; scaled sample/feature sweeps; no score/parity regression; fit >=0.95x sklearn on both canonical datasets, target >=1.05x; keep prediction performance at least current.
Found a concrete pair-local allocation/copy target in the current SMO implementation. _kernel_svc_smo_precomputed materializes Q[i,j] = y_i y_j K[i,j] for every OvO binary problem even though the full shared kernel K already exists. This matrix is algebraically redundant.
The current WSS3 curvature
Qii + Qjj - 2 yi yj Qij
simplifies exactly to
Kii + Kjj - 2 Kij
because yi^2 = yj^2 = 1.
The incremental gradient update
Gk += Qik*di + Qjk*dj
can likewise be evaluated directly from K as
Gk += yk * (Kik*(yi*di) + Kjk*(yj*dj)).
So pair-local Q can be removed without changing the mathematical SMO trajectory. For a pair with m rows this eliminates 8*m*m bytes of pair-local storage plus all Q-construction writes. At a balanced Digits scale (N=1797, K=10, 45 OvO pairs, ~359 rows/pair), that is about 46.4 MB of cumulative pair-local Q payload writes across one multiclass fit.
I wrote the derivation and a Flow semantic witness in godofecht/OpenProjects:
The next local A/B should measure pair-preparation vs SMO time and require unchanged SMO step count / working-set sequence digest / support-vector count before attributing any remaining gap to working-set or shrinking efficiency.
Activity
godofecht commentedon Aug 25, 2026
Found a concrete pair-local allocation/copy target in the current SMO implementation.
_kernel_svc_smo_precomputedmaterializesQ[i,j] = y_i y_j K[i,j]for every OvO binary problem even though the full shared kernelKalready exists. This matrix is algebraically redundant.The current WSS3 curvature
Qii + Qjj - 2 yi yj Qijsimplifies exactly to
Kii + Kjj - 2 Kijbecause
yi^2 = yj^2 = 1.The incremental gradient update
Gk += Qik*di + Qjk*djcan likewise be evaluated directly from K as
Gk += yk * (Kik*(yi*di) + Kjk*(yj*dj)).So pair-local Q can be removed without changing the mathematical SMO trajectory. For a pair with m rows this eliminates
8*m*mbytes of pair-local storage plus all Q-construction writes. At a balanced Digits scale (N=1797, K=10, 45 OvO pairs, ~359 rows/pair), that is about 46.4 MB of cumulative pair-local Q payload writes across one multiclass fit.I wrote the derivation and a Flow semantic witness in
godofecht/OpenProjects:ml/zero-copy-dual-kernel-view-for-kernel-svc-fit.mdml/zero-copy-dual-kernel-view-for-kernel-svc-fit.flowThe next local A/B should measure pair-preparation vs SMO time and require unchanged SMO step count / working-set sequence digest / support-vector count before attributing any remaining gap to working-set or shrinking efficiency.