Finite de Finetti for convex bodies and Polynomial Optimization

• URL: http://arxiv.org/abs/2601.15184v1
• Date: Wed, 21 Jan 2026 17:04:13 GMT
• Title: Finite de Finetti for convex bodies and Polynomial Optimization
• Authors: Julius A. Zeiss, Gereon Koßmann, René Schwonnek, Martin Plávala,
• Abstract summary: We prove a finite de Finetti representation theorem for general convex bodies.<n>Our strategy generalizes a quantitative monogamy-of-entanglement argument from quantum theory to arbitrary convex bodies.<n>As an application, we express the optimal GPT value of a two-player non-local game as an optimization problem.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Leveraging a recently proposed notion of relative entropy in general probabilistic theories (GPT), we prove a finite de Finetti representation theorem for general convex bodies. We apply this result to address a fundamental question in polynomial optimization: the existence of a convergent outer hierarchy for problems with inequality constraints and analytical convergence guarantees. Our strategy generalizes a quantitative monogamy-of-entanglement argument from quantum theory to arbitrary convex bodies, establishing a uniform upper bound on mutual information in multipartite extensions. This leads to a finite de Finetti theorem and, subsequently, a convergent conic hierarchy for a wide class of polynomial optimization problems subject to both equality and inequality constraints. We further provide a constructive rounding scheme that yields certified interior points with controlled approximation error. As an application, we express the optimal GPT value of a two-player non-local game as a polynomial optimization problem, allowing our techniques to produce approximation schemes with finite convergence guarantees.

Related papers

• A unified approach to quantum de Finetti theorems and SoS rounding via geometric quantization [0.0]
  We study a connection between a Hermitian version of the SoS hierarchy, related to the quantum de Finetti theorem. We show that previously known HSoS rounding algorithms can be recast as quantizing an objective function.
  arXiv  Detail & Related papers  (2024-11-06T17:09:28Z)
• The polarization hierarchy for polynomial optimization over convex bodies, with applications to nonnegative matrix rank [0.6963971634605796]
  We construct a convergent family of outer approximations for the problem of optimizing functions over convex subject bodies to constraints. A numerical implementation of the third level of the hierarchy is shown to give rise to a very tight approximation for this problem.
  arXiv  Detail & Related papers  (2024-06-13T18:00:09Z)
• A Generalized Version of Chung's Lemma and its Applications [10.570672679063394]
  We develop a generalized version of Chung's lemma, which provides a simple non-asymptotic convergence framework for a more general family of step size rules. As a by-product of our analysis, we observe that exponential step sizes can adapt to the objective function's geometry, achieving the optimal convergence rate without requiring exact knowledge of the underlying landscape.
  arXiv  Detail & Related papers  (2024-06-09T04:25:10Z)
• State polynomials: positivity, optimization and nonlinear Bell inequalities [3.9692590090301683]
  This paper introduces states in noncommuting variables and formal states of their products. It shows that states, positive over all and matricial states, are sums of squares with denominators. It is also established that avinetengle Kritivsatz fails to hold in the state setting.
  arXiv  Detail & Related papers  (2023-01-29T18:52:21Z)
• Approximation of optimization problems with constraints through kernel Sum-Of-Squares [77.27820145069515]
  We show that pointwise inequalities are turned into equalities within a class of nonnegative kSoS functions. We also show that focusing on pointwise equality constraints enables the use of scattering inequalities to mitigate the curse of dimensionality in sampling the constraints.
  arXiv  Detail & Related papers  (2023-01-16T10:30:04Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  The problem of constrained decision process (CMDP) is investigated, where an agent aims to maximize the expected accumulated discounted reward subject to multiple constraints. A new utilities-dual convex approach is proposed with novel integration of three ingredients: regularized policy, dual regularizer, and Nesterov's gradient descent dual. This is the first demonstration that nonconcave CMDP problems can attain the lower bound of $mathcal O (1/epsilon)$ for all complexity optimization subject to convex constraints.
  arXiv  Detail & Related papers  (2021-10-20T02:57:21Z)
• The Geometry of Memoryless Stochastic Policy Optimization in Infinite-Horizon POMDPs [0.0]
  We consider the problem of finding the best memoryless policy for an infinite-horizon partially observable decision process. We show that the discounted state-action frequencies and the expected cumulative reward are the functions of the policy, whereby the degree is determined by the degree of partial observability.
  arXiv  Detail & Related papers  (2021-10-14T14:42:09Z)
• Lifting the Convex Conjugate in Lagrangian Relaxations: A Tractable Approach for Continuous Markov Random Fields [53.31927549039624]
  We show that a piecewise discretization preserves better contrast from existing discretization problems. We apply this theory to the problem of matching two images.
  arXiv  Detail & Related papers  (2021-07-13T12:31:06Z)
• Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
  Motivated by recent increased interest in analysis of optimization algorithms for non- optimization in deep networks and other problems in data, we give an overview of recent results of theoretical optimization algorithms for non- optimization.
  arXiv  Detail & Related papers  (2020-12-11T08:28:51Z)
• Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization [98.0595480384208]
  We propose a generalization extraient spaces which converges to a stationary point. The algorithm applies not only to general $p$-normed spaces, but also to general $p$-dimensional vector spaces.
  arXiv  Detail & Related papers  (2020-10-31T21:35:42Z)
• A refinement of Reznick's Positivstellensatz with applications to quantum information theory [72.8349503901712]
  In Hilbert's 17th problem Artin showed that any positive definite in several variables can be written as the quotient of two sums of squares. Reznick showed that the denominator in Artin's result can always be chosen as an $N$-th power of the squared norm of the variables.
  arXiv  Detail & Related papers  (2019-09-04T11:46:26Z)

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.