An Online and Unified Algorithm for Projection Matrix Vector Multiplication with Application to Empirical Risk Minimization
Lianke Qin, Zhao Song, Lichen Zhang, Danyang Zhuo
Abstract
Online matrix vector multiplication is a fundamental step and bottleneck in many machine learning algorithms. It is defined as follows: given a matrix at the pre-processing phase, at each iteration one receives a query vector and needs to form the matrix-vector product (approximately) before observing the next vector. In this work, we study a particular instance of such problem called the online projection matrix vector multiplication. Via a reduction, we show it suffices to solve the inverse maintenance problem. Additionally, our framework supports dimensionality reduction to speed up the computation that approximates the matrix-vector product with an optimization-friendly error guarantee. Moreover, our unified approach can handle both data-oblivious sketching and data-dependent sampling. Finally, we demonstrate the effectiveness of our framework by speeding up the empirical risk minimization solver.
BibTeX
@InProceedings{pmlr-v206-qin23a,
title = {An Online and Unified Algorithm for Projection Matrix Vector Multiplication with Application to Empirical Risk Minimization},
author = {Qin, Lianke and Song, Zhao and Zhang, Lichen and Zhuo, Danyang},
booktitle = {Proceedings of The 26th International Conference on Artificial Intelligence and Statistics},
pages = {101--156},
year = {2023},
editor = {Ruiz, Francisco and Dy, Jennifer and van de Meent, Jan-Willem},
volume = {206},
series = {Proceedings of Machine Learning Research},
month = {25--27 Apr},
publisher = {PMLR},
pdf = {https://proceedings.mlr.press/v206/qin23a/qin23a.pdf},
url = {https://proceedings.mlr.press/v206/qin23a.html},
abstract = {Online matrix vector multiplication is a fundamental step and bottleneck in many machine learning algorithms. It is defined as follows: given a matrix at the pre-processing phase, at each iteration one receives a query vector and needs to form the matrix-vector product (approximately) before observing the next vector. In this work, we study a particular instance of such problem called the online projection matrix vector multiplication. Via a reduction, we show it suffices to solve the inverse maintenance problem. Additionally, our framework supports dimensionality reduction to speed up the computation that approximates the matrix-vector product with an optimization-friendly error guarantee. Moreover, our unified approach can handle both data-oblivious sketching and data-dependent sampling. Finally, we demonstrate the effectiveness of our framework by speeding up the empirical risk minimization solver.}
}