A two-stage least-squares algorithm combining Christoffel sampling with experimental-design-based allocation of repeated evaluations improves sample complexity for learning noisy conditional expectations.
Fast algorithms for least square problems with Kronecker lower subsets
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
While leverage score sampling provides powerful tools for approximating solutions to large least squares problems, the cost of computing exact scores and sampling often prohibits practical application. This paper addresses this challenge by developing a new and efficient algorithm for exact leverage score sampling applicable to matrices that are lower column subsets of Kronecker product matrices. We synthesize relevant approximation guarantees and detail the algorithm that specifically leverages this structural property for computational efficiency. Through numerical examples, we demonstrate that utilizing efficiently computed exact leverage scores via our methods significantly reduces approximation errors, as compared to established approximate leverage score sampling strategies when applied to this important class of structured matrices.
fields
stat.ML 1years
2025 1verdicts
ACCEPT 1representative citing papers
citing papers explorer
-
Hybrid least squares for learning functions from highly noisy data
A two-stage least-squares algorithm combining Christoffel sampling with experimental-design-based allocation of repeated evaluations improves sample complexity for learning noisy conditional expectations.