揭示矩阵博弈求解的理论极限，证明了最优算法至少需ε^{-2/3}次迭代。
The Oracle Complexity of Simplex-based Matrix Games
- 区分单边与双边矩阵向量乘法的查询模型，明确算法复杂度差异。
- 在ℓₚ单纯形设定下，证明ε-近似解需至少˜Ω(ε^{-2/3})次迭代。
- 对线性分类器和纳什均衡计算等经典任务，给出紧致下界，匹配最新算法。
我们研究形式为 $\min_{\mathbf{p}\inΔ}\max_{\mathbf{w}\in\mathcal{W}}\mathbf{p}^\top A\mathbf{w}$ 的矩阵博弈，其中 $A$ 为矩阵，$Δ$ 为概率单纯形。该问题涵盖线性分离器寻找与零和博弈纳什均衡计算等典型任务。然而，其内在复杂性（在标准预言机复杂度框架下）仍不清晰。本文首先识别出以往算法隐含使用的不同预言机模型：分别对应从单侧或双侧对矩阵 $A$ 进行向量乘法。随后，我们针对两种访问模型证明了复杂度下界，从而揭示二者间的本质差异。主要结果为：在一般 ℓₚ/单纯形设定下，若 $\mathcal{W}$ 为 ℓₚ 球（$p\in[1,\infty]$），任何使用双侧矩阵向量乘法的算法，求得 ε-子优解至少需 $\tildeΩ(ε^{-2/3})$ 次迭代。对于任意 $p\in[1,\infty]$，该下界要么是首次提出，要么较此前最优结果实现指数级提升。此外，对线性分离器与纳什均衡计算等经典任务，我们的下界与近期 Karmarkar、O'Carroll 与 Sidford（2026）提出的算法复杂度在对数因子范围内一致，从而在自然设置下解决了其预言机复杂度问题。
原文摘要 · Abstract (English)
We study the problem of solving matrix games of the form $\min_{\mathbf{p}\inΔ}\max_{\mathbf{w}\in\mathcal{W}}\mathbf{p}^{\top}A\mathbf{w}$, where $A$ is a matrix and $Δ$ is the probability simplex. This problem encapsulates canonical tasks such as finding a linear separator and computing Nash equilibria in zero-sum games. However, perhaps surprisingly, its inherent complexity (as formalized in the standard framework of oracle complexity) is not well understood. In this work, we first identify different oracle models that are implicitly used by prior algorithms, corresponding to multiplying the matrix $A$ by a vector from either one or both sides. We then prove complexity lower bounds for algorithms under both access models, which in particular imply a separation between them. As our main result, we prove that in the general $\ell_p$/simplex setting where $\mathcal{W}$ is an $\ell_p$ ball for $p\in[1,\infty]$, any algorithm that utilizes two-sided matrix-vector multiplications requires $\tildeΩ(ε^{-2/3})$ iterations to return an $ε$-suboptimal solution. For any $p\in[1,\infty]$, this is either the first lower bound for such problems, or an exponential improvement over the previously best-known results. Moreover, for the canonical tasks of finding a linear separator and computing a Nash equilibrium, our lower bounds match (up to log factors) recent algorithms of Karmarkar, O'Carroll and Sidford (2026), thereby resolving their oracle complexities in a natural setting.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。