piCholesky: Polynomial Interpolation of Multiple Cholesky Factors for Efficient Approximate Cross-Validation
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
On the stable Cholesky factorization-based method for the maximum correntropy criterion Kalman filtering
This paper continues the research devoted to the design of numerically stable square-root implementations for the maximum correntropy criterion Kalman filtering (MCC-KF). In contrast to the previously obtained results, h…
Memory-Efficient 4-bit Preconditioned Stochastic Optimization
Preconditioned stochastic optimization algorithms, exemplified by Shampoo, outperform first-order optimizers by offering theoretical convergence benefits and practical gains in large-scale neural network training. Howeve…
QuantizationStochastic OptimizationFused-Lasso Regularized Cholesky Factors of Large Nonstationary Covariance Matrices of Longitudinal Data
Smoothness of the subdiagonals of the Cholesky factor of large covariance matrices is closely related to the degrees of nonstationarity of autoregressive models for time series and longitudinal data. Heuristically, one e…
Time SeriesTime Series AnalysisOperator Learning at Machine Precision
Neural operator learning methods have garnered significant attention in scientific computing for their ability to approximate infinite-dimensional operators. However, increasing their complexity often fails to substantia…
Algebra of L-banded Matrices
Convergence is a crucial issue in iterative algorithms. Damping is commonly employed to ensure the convergence of iterative algorithms. The conventional ways of damping are scalar-wise, and either heuristic or empirical.…