An Online and Unified Algorithm for Projection Matrix Vector Multiplication with Application to Empirical Risk Minimization

Lianke Qin, Zhao Song, Lichen Zhang, Danyang Zhuo
Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, PMLR 206:101-156, 2023.

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.

Cite this Paper

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.} }
Endnote
%0 Conference Paper %T An Online and Unified Algorithm for Projection Matrix Vector Multiplication with Application to Empirical Risk Minimization %A Lianke Qin %A Zhao Song %A Lichen Zhang %A Danyang Zhuo %B Proceedings of The 26th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2023 %E Francisco Ruiz %E Jennifer Dy %E Jan-Willem van de Meent %F pmlr-v206-qin23a %I PMLR %P 101--156 %U https://proceedings.mlr.press/v206/qin23a.html %V 206 %X 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.
APA
Qin, L., Song, Z., Zhang, L. & Zhuo, D.. (2023). An Online and Unified Algorithm for Projection Matrix Vector Multiplication with Application to Empirical Risk Minimization. Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 206:101-156 Available from https://proceedings.mlr.press/v206/qin23a.html.

Related Material