# piCholesky: Polynomial Interpolation of Multiple Cholesky Factors for Efficient Approximate Cross-Validation

Source: [piCholesky: Polynomial Interpolation of Multiple Cholesky Factors for Efficient Approximate Cross-Validation](<https://www.sota2.com/research/paper/68fa51e81e209131ce97715b>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2026-06-05T05:00:26.567Z

Authors: Da Kuang, Alex Gittens, Raffay Hamid

Published: 2014-04-02T05:33:41.000Z

## Abstract

The dominant cost in solving least-square problems using Newton's method is often that of factorizing the Hessian matrix over multiple values of the regularization parameter ($\\lambda$). We propose an efficient way to interpolate the Cholesky factors of the Hessian matrix computed over a small set of $\\lambda$ values. This approximation enables us to optimally minimize the hold-out error while incurring only a fraction of the cost compared to exact cross-validation. We provide a formal error bound for our approximation scheme and present solutions to a set of key implementation challenges that allow our approach to maximally exploit the compute power of modern architectures. We present a thorough empirical analysis over multiple datasets to show the effectiveness of our approach.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

- [Algorithm Execution Time on MNIST](<https://www.sota2.com/research/sota/algorithm-execution-time-on-mnist.md>): Algorithm Execution Time; MNIST; Execution Time (s): 188.

- [Image Classification on Caltech-256 (Minimum Hold-out Error)](<https://www.sota2.com/research/sota/image-classification-on-caltech-256-minimum-hold-out-error.md>): Image Classification; Caltech-256; Min Hold-out Error: 94.21.

- [Algorithm Execution Time on COIL-100](<https://www.sota2.com/research/sota/algorithm-execution-time-on-coil-100.md>): Algorithm Execution Time; COIL-100; Execution Time (s): 167.

- [Algorithm Execution Time on Caltech-101](<https://www.sota2.com/research/sota/algorithm-execution-time-on-caltech-101.md>): Algorithm Execution Time; Caltech-101; Execution Time (s): 169.

- [Algorithm Execution Time on Caltech-256](<https://www.sota2.com/research/sota/algorithm-execution-time-on-caltech-256.md>): Algorithm Execution Time; Caltech-256; Execution Time (s): 174.

- [Image Classification on COIL-100 (Minimum Hold-out Error)](<https://www.sota2.com/research/sota/image-classification-on-coil-100-minimum-hold-out-error.md>): Image Classification; COIL-100; Minimum Hold-out Error: 0.4507.

- [Image Classification on MNIST (Minimum Hold-out Error)](<https://www.sota2.com/research/sota/image-classification-on-mnist-minimum-hold-out-error.md>): Image Classification; MNIST; Minimum Hold-out Error: 36.34.

- [Image Classification on Caltech-101 (Minimum hold-out error)](<https://www.sota2.com/research/sota/image-classification-on-caltech-101-minimum-hold-out-error.md>): Image Classification; Caltech-101; Min Hold-out Error: 0.6934.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/1404.0466>)

[PDF](<https://arxiv.org/pdf/1404.0466.pdf>)