The Complexity of Min-Max Optimization for Quadratic Polynomials
We prove that computing approximate stationary points of min-max optimization over the hypercube is PPAD-hard for quadratic polynomials. This holds even when the polynomials are multilinear, each variable appears in at most three monomials, and the approximation factor is inverse polynomial. As a direct consequence, we obtain the first PPAD-hardness results for two-team zero-sum polymatrix games.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Sums of Separable and Quadratic Polynomials
We study separable plus quadratic (SPQ) polynomials, i.e., polynomials that are the sum of univariate polynomials in different variables and a quadratic polynomial. Motivated by the fact that nonnegative separable and no…
Complexity Aspects of Fundamental Questions in Polynomial Optimization
In this thesis, we settle the computational complexity of some fundamental questions in polynomial optimization. These include the questions of (i) finding a local minimum, (ii) testing local minimality of a point, and (…
On the Complexity of Detecting Convexity over a Box
It has recently been shown that the problem of testing global convexity of polynomials of degree four is {strongly} NP-hard, answering an open question of N.Z. Shor. This result is minimal in the degree of the polynomial…
Open-Ended Question AnsweringTight $L_\infty$ Sample Complexity for Low-Degree and Sparse Boolean Polynomials
Motivated by the optimization of bounded binary black-box functions, we study the problem of learning polynomial surrogates over the Boolean hypercube. To ensure that optimizing the surrogate yields good solutions for th…
Sparse Gaussian Processes via Parametric Families of Compactly-supported Kernels
Gaussian processes are powerful models for probabilistic machine learning, but are limited in application by their $O(N^3)$ inference complexity. We propose a method for deriving parametric families of kernel functions w…
Gaussian Processes