The Oracle Complexity of Simplex-based Matrix Games: Linear Separability and Nash Equilibria

• URL: http://arxiv.org/abs/2412.06990v1
• Date: Mon, 09 Dec 2024 20:58:26 GMT
• Title: The Oracle Complexity of Simplex-based Matrix Games: Linear Separability and Nash Equilibria
• Authors: Guy Kornowski, Ohad Shamir,
• Abstract summary: We study the problem of solving matrix games of the form $max_mathbfwinmathcalWmin_mathbfpinDeltamathbfptopAmathbfw$. This problem encapsulates canonical tasks such as finding a linear separator and computing Nash equilibria in zero-sum games.
• Score: 37.300102993926046
• License:
• Abstract: We study the problem of solving matrix games of the form $\max_{\mathbf{w}\in\mathcal{W}}\min_{\mathbf{p}\in\Delta}\mathbf{p}^{\top}A\mathbf{w}$, where $A$ is some matrix and $\Delta$ 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 [Nemirovski and Yudin, 1983]) is not well-understood. In this work, we first identify different oracle models which are implicitly used by prior algorithms, amounting 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. Specifically, we start by proving that algorithms for linear separability based on one-sided multiplications must require $\Omega(\gamma_A^{-2})$ iterations, where $\gamma_A$ is the margin, as matched by the Perceptron algorithm. We then prove that accelerated algorithms for this task, which utilize multiplications from both sides, must require $\tilde{\Omega}(\gamma_{A}^{-2/3})$ iterations, establishing the first oracle complexity barrier for such algorithms. Finally, by adapting our lower bound to $\ell_1$ geometry, we prove that computing an $\epsilon$-approximate Nash equilibrium requires $\tilde{\Omega}(\epsilon^{-2/5})$ iterations, which is an exponential improvement over the previously best-known lower bound due to Hadiji et al. [2024].

Related papers

• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  We show that this problem has randomized communication complexity $Omega(frac1kcdot n2log|mathbbF|)$. As an application, we obtain an $Omega(frac1kcdot n2log|mathbbF|)$ space lower bound for any streaming algorithm with $k$ passes.
  arXiv  Detail & Related papers  (2024-10-26T06:21:42Z)
• Simple and Nearly-Optimal Sampling for Rank-1 Tensor Completion via Gauss-Jordan [49.1574468325115]
  We revisit the sample and computational complexity of completing a rank-1 tensor in $otimes_i=1N mathbbRd$. We present a characterization of the problem which admits an algorithm amounting to Gauss-Jordan on a pair of random linear systems.
  arXiv  Detail & Related papers  (2024-08-10T04:26:19Z)
• Structured Semidefinite Programming for Recovering Structured Preconditioners [41.28701750733703]
  We give an algorithm which, given positive definite $mathbfK in mathbbRd times d$ with $mathrmnnz(mathbfK)$ nonzero entries, computes an $epsilon$-optimal diagonal preconditioner in time. We attain our results via new algorithms for a class of semidefinite programs we call matrix-dictionary approximation SDPs.
  arXiv  Detail & Related papers  (2023-10-27T16:54:29Z)
• Towards Characterizing the First-order Query Complexity of Learning (Approximate) Nash Equilibria in Zero-sum Matrix Games [0.0]
  We show that exact equilibria can be computed efficiently from $O(fracln Kepsilon)$ instead of $O(fracln Kepsilon2)$ queries. We introduce a new technique for lower bounds, which allows us to obtain lower bounds of order $tildeOmega(frac1Kepsilon)$ for any $epsilon leq 1 / (cK4)$.
  arXiv  Detail & Related papers  (2023-04-25T12:42:59Z)
• Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
  We consider the problem of minimizing the number of matrix-vector queries needed for accurate trace estimation in the dynamic setting where our underlying matrix is changing slowly. We provide a novel binary tree summation procedure that simultaneously estimates all $m$ traces up to $epsilon$ error with $delta$ failure probability. Our lower bounds (1) give the first tight bounds for Hutchinson's estimator in the matrix-vector product model with Frobenius norm error even in the static setting, and (2) are the first unconditional lower bounds for dynamic trace estimation.
  arXiv  Detail & Related papers  (2022-09-30T04:15:44Z)
• The First Optimal Acceleration of High-Order Methods in Smooth Convex Optimization [88.91190483500932]
  We study the fundamental open question of finding the optimal high-order algorithm for solving smooth convex minimization problems. The reason for this is that these algorithms require performing a complex binary procedure, which makes them neither optimal nor practical. We fix this fundamental issue by providing the first algorithm with $mathcalOleft(epsilon-2/(p+1)right) $pth order oracle complexity.
  arXiv  Detail & Related papers  (2022-05-19T16:04:40Z)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  We give a sketching-based iterative algorithm that computes $1+varepsilon$ approximate solutions for the ridge regression problem. We also show that this algorithm can be used to give faster algorithms for kernel ridge regression.
  arXiv  Detail & Related papers  (2022-04-13T22:18:47Z)
• The Fine-Grained Hardness of Sparse Linear Regression [12.83354999540079]
  We show that there are no better-than-brute-force algorithms for the problem. We also show the impossibility of better-than-brute-force algorithms when the prediction error is measured.
  arXiv  Detail & Related papers  (2021-06-06T14:19:43Z)
• Sublinear classical and quantum algorithms for general matrix games [11.339580074756189]
  We investigate sublinear classical and quantum algorithms for matrix games. For any fixed $qin (1,2), we solve the matrix game where $mathcalX$ is a $ell_q$-norm unit ball within additive error. We also provide a corresponding sublinear quantum algorithm that solves the same task in time.
  arXiv  Detail & Related papers  (2020-12-11T17:36:33Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.