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, the algorithm receives a query vector and must output the product before seeing the next vector. This paper introduces a unified framework for the projection-based variant of this problem.
1. Introduction
In the landscape of modern optimization, the Online Matrix-Vector Multiplication (OMv) problem serves as a critical computational bottleneck. Algorithms such as gradient descent, Newton's method, and various interior point methods rely heavily on repeated matrix-vector products. This paper addresses a specialized yet ubiquitous version: Online Projection Matrix-Vector Multiplication (OPMv).
In OPMv, the matrix $P$ is a projection matrix, typically defined as $P = \sqrt{W} A^\top(AWA^\top)^{-1}A\sqrt{W}$. This specific form is the core operation within interior point methods used for solving Linear Programming (LP) and Empirical Risk Minimization (ERM). Historically, researchers have employed a variety of disparate techniques—such as data-dependent sampling and data-oblivious sketching—to accelerate this process. However, these methods often lacked a unifying theory and introduced inefficient "log-log" factors into the final runtime.
2. The OPMv Framework
The OPMv problem involves a static matrix $A$ and a dynamic diagonal weight matrix $W$ that changes over iterations. At each step, the algorithm must compute $Ph$ for a given query vector $h$.
3. Technical Innovations
The authors propose a unified framework that reduces OPMv to a generic "inverse maintenance" problem through three key innovations:
3.1 Reduction to Inverse Maintenance
By utilizing the Schur complement, the authors demonstrate that OPMv is equivalent to maintaining the inverse of a specifically constructed large block matrix $L$. This transformation allows the projection-vector product to be recovered from a specific corner of $L^{-1}$, turning a complex optimization sub-task into a standard dynamic data structure problem.
3.2 Coordinate-wise Embedding
The paper introduces "coordinate-wise embedding" as a unifying lens. The authors prove that both importance sampling (data-dependent) and random sketching (data-oblivious) are simply different strategies to satisfy this property. This theoretical bridge explains why previous sampling schemes were effective and provides a path toward optimal implementation.
3.3 Sketching on the Right
A significant contribution of this work is the shift from "sketching on the left" to "sketching on the right." Previous state-of-the-art methods (e.g., Lee et al., 2019) applied dimensionality reduction before the projection ($RPh$), which often pushed the optimization algorithm off its "central path," necessitating frequent and costly restarts. By sketching on the right ($PR^\top Rh$), the authors preserve the geometric integrity of the central path, eliminating these restarts and streamlining the algorithm.
4. Key Results and Complexity
The primary achievement of this research is the removal of an "unnatural" $\log^6(\log(1/\delta))$ factor from the runtime of ERM solvers. The unified framework provides a single algorithm capable of handling both sketching and sampling with rigorous guarantees.
The new expected runtime for ERM is established as: $$O(n^{\omega+o(1)} + n^{2.5-\alpha/2+o(1)} + n^{2+1/6+o(1)}) \cdot O(\log(1/\delta))$$ where $\omega$ is the exponent of matrix multiplication and $\alpha$ is the dual exponent. This represents a significant theoretical improvement over previous bounds.
5. Conclusion and Future Work
This paper provides a much-needed unification of OPMv techniques, demonstrating that complex update rules are essentially forms of dynamic inverse maintenance. While the current approach is optimized for projection matrices (where the spectral norm is $\le 1$), future work may explore generalizing this "inverse maintenance" perspective to broader classes of dynamic matrix problems and relaxing the current reliance on coordinate-wise error guarantees.
Summary updated