# An error analysis for polynomial optimization over the simplex based on the multivariate hypergeometric distribution

arXiv: https://arxiv.org/abs/1407.2108 · HTML: https://mlsanity.com/paper/1407.2108/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Jul 2014.

## Built on by (most cited first, 1 of 1)

- [Inductive randomness predictors: beyond conformal](https://mlsanity.com/paper/2503.02803/) (2025)

## Abstract (arXiv)

We study the minimization of fixed-degree polynomials over the simplex. This problem is well-known to be NP-hard, as it contains the maximum stable set problem in graph theory as a special case. In this paper, we consider a rational approximation by taking the minimum over the regular grid, which consists of rational points with denominator r (for given r). We show that the associated convergence rate is O(1/r2) for quadratic polynomials. For general polynomials, if there exists a rational global minimizer over the simplex, we show that the convergence rate is also of the order O(1/r2). Our results answer a question posed by De Klerk et al. (2013) and improves on previously known O(1/r) bounds in the quadratic case.