Fugu-MT 論文翻訳(概要): An Argmax Principle for Sum-of-Squares Relaxations on the Sphere

論文の概要: An Argmax Principle for Sum-of-Squares Relaxations on the Sphere

arxiv url: http://arxiv.org/abs/2608.02594v1
Date: Mon, 03 Aug 2026 17:58:00 GMT
ステータス: 翻訳完了
システム内更新日: 2026-08-04 15:07:25.75045
Title: An Argmax Principle for Sum-of-Squares Relaxations on the Sphere
Title（参考訳）: 球面上の正方形の緩和に対するArgmax原理
Authors: Fernando Jeronimo Granha, Pei Wu, Haochen Xu,
Abstract要約: 単位球面上の最適化問題の総和緩和を解析するためのargmax原理を開発する。私たちの指導原則は、最大値が丸みを帯びた候補であることです。
参考スコア（独自算出の注目度）: 42.540924632302925
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We develop an argmax principle for analyzing sum-of-squares relaxations of optimization problems over the unit sphere. Given a feasible pseudo-expectation, we form a polynomial of high-order pseudo-moments, such as $Φ_k(u)=\widetilde{\mathbb E}\langle x,u\rangle^{2k}$. Our guiding principle is that its maximizers are rounding candidates: their local and global optimality conditions reveal the reweighed pseudo-expectation inequalities governing SoS convergence. This viewpoint unifies several problems previously analyzed by rather different techniques. We obtain three results. First, for Best Separable State, we give a degree-$O(\sqrt{n/ε})$ SoS analysis for approximating $h_{\mathrm{sep}}(P)$ in the perfect-completeness regime, improving and simplifying Barak, Kothari and Steurer (STOC'17). The dependence is essentially tight for inverse-linear gap under the Exponential-Time Hypothesis, matching hardness from $\mathrm{QMA}(2)$ protocols. Second, for the matrix $2\to4$ norm, degree-$O(\sqrt n/ε)$ SoS gives a multiplicative $(1+ε)$ approximation. Barak et al. (STOC'12) previously gave a comparable-time constant-gap decision algorithm; our result gives a multiplicative guarantee and extends to a family of $p\to q$ norms with even $q$. Finally, for degree-$d$ polynomial optimization, we recover the convergence theorem of Bhattiprolu et al. (FOCS'17) with a shorter, more direct proof: degree-$k$ SoS gives approximation ratio $O_d((n/k)^{d/2-1})$. The paper introduces no new relaxation. Instead, the high-moment argmax gives a common way to read an SoS solution, unifying previously separate convergence analyses and yielding sharper bounds or simpler proofs.
Abstract（参考訳）: 単位球面上の最適化問題の総和緩和を解析するためのargmax原理を開発する。実現可能な擬予想が与えられたとき、高次擬モーメントの多項式を形成して、例えば $\_k(u)=\widetilde{\mathbb E}\langle x,u\rangle^{2k}$ である。我々の指導原則は、その最大値が丸みを帯びた候補であることであり、その局所的および大域的最適条件は、SoS収束を規定する相対的擬似観測の不等式を明らかにする。この観点は、以前、かなり異なる手法で分析されたいくつかの問題を統一する。 3つの結果が得られます。まず、最良の分離状態に対して、完全完全性系において$h_{\mathrm{sep}}(P)$を近似するための次数-$O(\sqrt{n/ε})$ SoS分析を与え、バラック、コタリ、シュタイラー(STOC'17)を改良し単純化する。この依存は本質的には指数時間仮説の下での逆線形ギャップに対して厳密であり、$\mathrm{QMA}(2)$プロトコルの硬さに一致する。第二に、行列 $2\to4$ ノルムに対して次数-$O(\sqrt n/ε)$ SoS は乗法$(1+ε)$近似を与える。 Barak et al (STOC'12) は、以前同等の時間定数ギャップ決定アルゴリズムを提供していた。最後に、次数-$$$多項式最適化のために、より短い直接証明で Bhattiprolu et al (FOCS'17) の収束定理を回復する: degree-$k$ SoS は近似比 $O_d((n/k)^{d/2-1})$ を与える。論文は新しいリラックスは導入しない。代わりに、高モメント argmax は SoS の解を読む共通の方法を与え、以前は分離されていた収束解析を統一し、よりシャープな境界あるいはより単純な証明を与える。

論文の概要: An Argmax Principle for Sum-of-Squares Relaxations on the Sphere

関連論文リスト