Fast and Accurate Least-Mean-Squares Solvers

Least-mean-squares (LMS) solvers such as Linear / Ridge-Regression and SVD not only solve fundamental machine learning problems, but are also the building blocks in a variety of other methods, such as matrix factorizations. We suggest an algorithm that gets a finite set of <inline-formula><tex-math notation="LaTeX">$n$</tex-math><alternatives><mml:math><mml:mi>n</mml:mi></mml:math><inline-graphic xlink:href="maalouf-ieq1-3139612.gif"/></alternatives></inline-formula> <inline-formula><tex-math notation="LaTeX">$d$</tex-math><alternatives><mml:math><mml:mi>d</mml:mi></mml:math><inline-graphic xlink:href="maalouf-ieq2-3139612.gif"/></alternatives></inline-formula>-dimensional real vectors and returns a subset of <inline-formula><tex-math notation="LaTeX">$d+1$</tex-math><alternatives><mml:math><mml:mrow><mml:mi>d</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:math><inline-graphic xlink:href="maalouf-ieq3-3139612.gif"/></alternatives></inline-formula> vectors with positive weights whose weighted sum is <italic>exactly</italic> the same. The constructive proof in Caratheodory's Theorem computes such a subset in <inline-formula><tex-math notation="LaTeX">$O(n^2d^2)$</tex-math><alternatives><mml:math><mml:mrow><mml:mi>O</mml:mi><mml:mo>(</mml:mo><mml:msup><mml:mi>n</mml:mi><mml:mn>2</mml:mn></mml:msup><mml:msup><mml:mi>d</mml:mi><mml:mn>2</mml:mn></mml:msup><mml:mo>)</mml:mo></mml:mrow></mml:math><inline-graphic xlink:href="maalouf-ieq4-3139612.gif"/></alternatives></inline-formula> time and thus not used in practice. Our algorithm computes this subset in <inline-formula><tex-math notation="LaTeX">$O(nd+d^4\log {n})$</tex-math><alternatives><mml:math><mml:mrow><mml:mi>O</mml:mi><mml:mo>(</mml:mo><mml:mi>n</mml:mi><mml:mi>d</mml:mi><mml:mo>+</mml:mo><mml:msup><mml:mi>d</mml:mi><mml:mn>4</mml:mn></mml:msup><mml:mo form="prefix">log</mml:mo><mml:mi>n</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:math><inline-graphic xlink:href="maalouf-ieq5-3139612.gif"/></alternatives></inline-formula> time, using <inline-formula><tex-math notation="LaTeX">$O(\log n)$</tex-math><alternatives><mml:math><mml:mrow><mml:mi>O</mml:mi><mml:mo>(</mml:mo><mml:mo form="prefix">log</mml:mo><mml:mi>n</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:math><inline-graphic xlink:href="maalouf-ieq6-3139612.gif"/></alternatives></inline-formula> calls to Caratheodory's construction on small but “smart” subsets. This is based on a novel paradigm of fusion between different data summarization techniques, known as sketches and coresets. For large values of <inline-formula><tex-math notation="LaTeX">$d$</tex-math><alternatives><mml:math><mml:mi>d</mml:mi></mml:math><inline-graphic xlink:href="maalouf-ieq7-3139612.gif"/></alternatives></inline-formula>, we suggest a faster construction that takes <inline-formula><tex-math notation="LaTeX">$O(nd)$</tex-math><alternatives><mml:math><mml:mrow><mml:mi>O</mml:mi><mml:mo>(</mml:mo><mml:mi>n</mml:mi><mml:mi>d</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:math><inline-graphic xlink:href="maalouf-ieq8-3139612.gif"/></alternatives></inline-formula> time and returns a weighted subset of <inline-formula><tex-math notation="LaTeX">$O(d)$</tex-math><alternatives><mml:math><mml:mrow><mml:mi>O</mml:mi><mml:mo>(</mml:mo><mml:mi>d</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:math><inline-graphic xlink:href="maalouf-ieq9-3139612.gif"/></alternatives></inline-formula> sparsified input points. Here, a sparsified point means that some of its entries were set to zero. As an application, we show how to boost the performance of existing LMS solvers, such as those in scikit-learn library, up to x100. Generalization for streaming and distributed data is trivial. Extensive experimental results and open source code are provided.