Sublinear Classical and Quantum Algorithms for General Matrix Games

Tongyang Li, Chunhao Wang, Shouvanik Chakrabarti, Xiaodi Wu

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:

  1. 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$).
  2. 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

  1. $\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.
  2. 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

Abstract

We investigate sublinear classical and quantum algorithms for matrix games, a fundamental problem in optimization and machine learning, with provable guarantees. Given a matrix, sublinear algorithms for the matrix game were previously known only for two special cases: (1) the maximizing vectors live in the L1-norm unit ball, and (2) the minimizing vectors live in either the L1- or the L2-norm unit ball. We give a sublinear classical algorithm that can interpolate smoothly between these two cases: for any fixed q between 1 and 2, we solve, within some additive error, matrix games where the minimizing vectors are in an Lq-norm unit ball. We also provide a corresponding sublinear quantum algorithm that solves the same task with a quadratic improvement in dimensions of the maximizing and minimizing vectors. Both our classical and quantum algorithms are optimal in the dimension parameters up to poly-logarithmic factors. Finally, we propose sublinear classical and quantum algorithms for the approximate Carathéodory problem and the Lq-margin support vector machines as applications.
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