Sublinear classical and quantum algorithms for general matrix games

Tongyang Li, Chunhao Wang, Shouvanik Chakrabarti, Xiaodi Wu

Introduction

Matrix games are a fundamental pillar of optimization and machine learning, representing a minimax competition between two players:

$$\min_{x \in \mathcal{X}} \max_{y \in \mathcal{Y}} y^T Ax$$

Solving these games is mathematically equivalent to solving linear programs and training essential classifiers like Support Vector Machines (SVMs). However, in the era of "Big Data," the matrices involved ($A \in \mathbb{R}^{n \times d}$) are often so large that even reading every entry—a task requiring $O(nd)$ time—becomes a computational bottleneck.

This paper introduces the first sublinear-time classical and quantum algorithms for solving general $\ell_q$-$\ell_1$ matrix games. By only sampling a tiny fraction of the matrix, these algorithms provide a path to solving massive optimization problems that were previously computationally prohibitive. While sublinear algorithms existed for specific cases (where both players use the $\ell_1$-norm or one uses the $\ell_2$-norm), this work fills a critical gap by addressing general $\ell_q$-$\ell_1$ games for any $q \in (1, 2]$.

The Primal-Dual Framework

The authors utilize a primal-dual framework that iteratively updates the strategies of both players to reach an $\epsilon$-approximate Nash equilibrium. The core of the classical approach lies in balancing two distinct update mechanisms:

  1. Primal Update: This utilizes a generalized $p$-norm Online Gradient Descent (OGD), where $1/p + 1/q = 1$.
  2. Dual Update: This employs Multiplicative Weight Updates (MWU) combined with a specialized $\ell_q$-sampling technique.

By integrating these methods, the classical algorithm achieves a complexity of $O\left(\frac{(n+d)p}{\epsilon^2}\right)$. This is significant because it demonstrates that the algorithm only needs to inspect $O(n+d)$ entries of the matrix, rather than the full $O(nd)$, to reach a solution. This scaling is theoretically optimal, as the authors prove that $\Omega(n+d)$ queries are strictly necessary for any classical algorithm in this setting.

Quantum Acceleration and $\ell_q$-Sampling

The most striking contribution of the paper is the translation of these sampling steps into the quantum domain. Quantum computers are naturally suited for $\ell_2$-norm operations due to the nature of quantum states; however, $\ell_q$-sampling is non-trivial.

The authors developed a novel quantum subroutine for $\ell_q$-sampling using amplitude amplification. This allows the preparation of quantum states where measurement probabilities follow an $\ell_q$-norm distribution. By leveraging this, the quantum algorithm achieves a quadratic speedup in the dimension parameters $n$ and $d$, running in:

$$\tilde{O}\left(\left(\frac{\sqrt{n}}{\epsilon^4} + \frac{\sqrt{d}}{\epsilon^7} ight) \text{poly}(p)\right)$$

Importantly, this quantum approach is "near-term friendly." It avoids the requirement for complex, futuristic quantum data structures like Quantum Random Access Memory (QRAM). Instead, it uses a hybrid approach where quantum state preparation is isolated and controlled by classical processing, making it more feasible for implementation on emerging hardware.

Key Insights and Applications

Smooth Interpolation

The proposed algorithms act as a bridge between different geometric constraints. When $q=2$, the solver mirrors existing $\ell_2$ techniques. As $q$ approaches 1, it naturally transitions into the behavior of $\ell_1$ solvers, providing a unified framework for matrix games.

Approximate Carathéodory Problem

The paper provides the first sublinear algorithms for finding sparse linear combinations in $p$-norm unit balls. This has significant implications for geometry and functional analysis, where finding sparse representations is a recurring challenge.

$\ell_q$-margin SVMs

The research enables the first sublinear algorithms for training $\ell_q$-margin SVMs. This allows for the efficient training of classifiers with specific geometric margin requirements on datasets that are too large to be processed by standard quadratic programming solvers.

Limitations and Future Directions

While the algorithms achieve optimal scaling in terms of dimensions $n$ and $d$, there are areas for further refinement:

  • Error Dependence: The dependence on the error parameter $\epsilon$ is relatively high, particularly in the quantum case ($1/\epsilon^7$). Future research may explore variance-reduction techniques to improve this scaling.
  • Norm Constraints: The current framework is limited to $q \in (1, 2]$. Extending this to $p > 2$ for the primal player would likely require a new "$q$-th moment" version of the Multiplicative Weight Update lemma.
  • Empirical Validation: As a theoretical breakthrough, the "hidden constants" in the big-O notation remain to be tested. Practical implementation on actual quantum hardware, once it reaches sufficient scale, remains a vital future milestone.

In conclusion, this work provides a comprehensive theoretical foundation for solving general matrix games in sublinear time, offering a significant leap in both classical efficiency and quantum speedup for high-dimensional optimization.

Summary updated

BibTeX
@inproceedings{li2021sublinear,
  author = {Tongyang Li and Chunhao Wang and Shouvanik Chakrabarti and Xiaodi Wu},
  title = {{Sublinear classical and quantum algorithms for general matrix games}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i10.17028},
}
Figure