Fast and Accurate Least-Mean-Squares Solvers for High Dimensional Data.

Area of Science:

• Machine Learning
• Computational Geometry
• Data Summarization

Background:

• Least-mean-squares (LMS) solvers are fundamental in machine learning and matrix factorization.
• Existing methods for finding representative vector subsets are computationally expensive.
• Caratheodory's Theorem provides a constructive proof but is impractical for large datasets.

Purpose of the Study:

• To develop an efficient algorithm for identifying a subset of d+1 vectors with positive weights whose weighted sum matches the original set.
• To significantly improve the performance of existing LMS solvers.
• To enable efficient data summarization for large-scale machine learning.

Main Methods:

• A novel algorithm with O(nd+d^4logn) time complexity, utilizing Caratheodory's construction on small, optimized subsets.
• Fusion of data summarization techniques: sketches and coresets.
• A faster O(nd) construction for high-dimensional data, yielding a weighted subset of O(d) sparsified points.

Main Results:

• The proposed algorithm significantly outperforms existing methods in speed.
• Achieved performance boosts of up to 100x for LMS solvers in libraries like scikit-learn.
• Demonstrated the effectiveness of combining sketches and coresets for data summarization.

Conclusions:

• The new algorithm offers a practical and efficient solution for vector subset selection in LMS problems.
• The approach is generalizable to streaming and distributed data settings.
• Provides a valuable tool for accelerating machine learning computations and enabling analysis of larger datasets.