Data Compression using Rank-1 Lattices for Parameter Estimation in Machine Learning
This work addresses computational efficiency in supervised machine learning for large-scale data processing, but it is incremental as it modifies an existing approach.
The authors tackled the computational challenge of calculating mean squared error losses for large datasets by introducing data compression algorithms using rank-1 lattices, which reduce dataset size and speed up iterative loss calculations, with proven arbitrary high convergence rates for sufficiently smooth functions.
The mean squared error and regularized versions of it are standard loss functions in supervised machine learning. However, calculating these losses for large data sets can be computationally demanding. Modifying an approach of J. Dick and M. Feischl [Journal of Complexity 67 (2021)], we present algorithms to reduce extensive data sets to a smaller size using rank-1 lattices. Rank-1 lattices are quasi-Monte Carlo (QMC) point sets that are, if carefully chosen, well-distributed in a multidimensional unit cube. The compression strategy in the preprocessing step assigns every lattice point a pair of weights depending on the original data and responses, representing its relative importance. As a result, the compressed data makes iterative loss calculations in optimization steps much faster. We analyze the errors of our QMC data compression algorithms and the cost of the preprocessing step for functions whose Fourier coefficients decay sufficiently fast so that they lie in certain Wiener algebras or Korobov spaces. In particular, we prove that our approach can lead to arbitrary high convergence rates as long as the functions are sufficiently smooth.