Introduction
In the era of massive datasets, the computational cost of traditional optimization methods often becomes a bottleneck. Many fundamental problems in machine learning and operations research can be framed as matrix games—minimax optimization problems of the form $\min_x \max_y y^T Ax$. Standard solvers typically require time proportional to the number of entries in the matrix ($n \times d$), which is prohibitive when $n$ and $d$ are in the millions.
This paper addresses the challenge of developing sublinear algorithms—methods that provide an approximate solution by querying only a fraction of the matrix entries. While sublinear shortcuts were previously established for specific $\ell_1$-$\ell_1$ and $\ell_2$-$\ell_1$ games, this work provides a generalized framework for $\ell_q$-$\ell_1$ matrix games where $q \in (1, 2]$. This generalization effectively bridges the gap between existing solvers and provides optimal dimension-dependent runtimes for both classical and quantum architectures.
The $\ell_q$-$\ell_1$ Matrix Game Framework
The core objective is to solve the minimax problem: $$\min_{x \in \Delta_q^d} \max_{y \in \Delta_1^n} y^T Ax$$ where $\Delta_q^d$ is the $\ell_q$-norm unit ball in $\mathbb{R}^d$ and $\Delta_1^n$ is the probability simplex in $\mathbb{R}^n$. This formulation is critical for applications such as Support Vector Machines (SVMs) and the approximate Carathéodory problem.
Classical Approach: Primal-Dual Dynamics
The authors utilize a primal-dual framework to iteratively approach the saddle point. The algorithm maintains two players:
- The Primal Player: Updates their strategy using a generalized $p$-norm Online Gradient Descent (OGD), where $p$ is the conjugate exponent of $q$ ($1/p + 1/q = 1$).
- The Dual Player: Employs Multiplicative Weight Updates (MWU).
To achieve sublinearity, the algorithm avoids full matrix-vector multiplications. Instead, it uses a novel $\ell_q$-sampling strategy. By sampling rows and columns with probabilities proportional to their $\ell_q$-norms, the algorithm constructs unbiased estimators of the gradients. This allows the solver to converge to an $\epsilon$-approximate solution in $O(\frac{(n+d)(p+\log n)}{\epsilon^2})$ time, which is linear in the dimensions $(n+d)$ rather than the product $(nd)$.
Quantum Speedups without QRAM
A significant contribution of this work is the translation of the $\ell_q$-sampling framework into the quantum domain. Unlike many quantum machine learning algorithms that rely on the theoretically complex "Quantum RAM" (QRAM), this approach uses a standard oracle model, making it more feasible for near-term quantum hardware.
Quantum $\ell_q$-Sampling
Standard quantum states naturally represent $\ell_2$-norm distributions (where measurement probabilities are proportional to the square of the amplitudes). The authors develop a novel Quantum $\ell_q$-sampling subroutine using Grover-style amplitude amplification. This allows the quantum algorithm to sample indices proportional to $|x_i|^q$ for any $q \in (1, 2]$.
By integrating this subroutine into the primal-dual framework, the quantum algorithm achieves a quadratic speedup in terms of the dimensions $n$ and $d$, with a runtime of $\tilde{O}(\frac{p^2\sqrt{n}}{\epsilon^4} + \frac{p^{3.5}\sqrt{d}}{\epsilon^7})$. Notably, the algorithm remains "hybrid" in nature, outputting a classical vector rather than a quantum state, which simplifies its integration into existing classical workflows.
Key Results and Applications
Theoretical Optimality
The authors provide lower bounds proving that their algorithms are dimension-optimal. Classically, one cannot solve these games faster than $O(n+d)$, and quantumly, the limit is $O(\sqrt{n}+\sqrt{d})$. This work hits these theoretical limits, establishing the most efficient possible dependence on the size of the input matrix.
Practical Implications
- $\ell_q$-Margin SVMs: The algorithms provide a faster training path for classifiers that maximize the margin between classes under general $\ell_q$-norms, which is useful for robust feature selection.
- Approximate Carathéodory Problem: The work yields the first sublinear algorithms for finding sparse representations of points within a convex hull under $\ell_p$ metrics ($p \geq 2$).
Limitations and Future Directions
While the algorithms are optimal regarding the dimensions $n$ and $d$, the quantum version suffers from a high dependence on the error parameter $\epsilon$ ($1/\epsilon^7$). This suggests that for applications requiring extremely high precision, the classical sublinear algorithm may still be preferable.
Future research may focus on reducing this $\epsilon$ dependence by incorporating variance reduction techniques like Stochastic Variance Reduced Gradient (SVRG) into the quantum sampling framework. Additionally, extending these techniques to cases where $q > 2$ (and thus $p < 2$) remains an open challenge, likely requiring new iterations of the Multiplicative Weight Update lemma.
Summary updated