Fugu-MT 論文翻訳(概要): The Complexity of Min-Max Optimization for Quadratic Polynomials

論文の概要: The Complexity of Min-Max Optimization for Quadratic Polynomials

arxiv url: http://arxiv.org/abs/2606.17000v1
Date: Mon, 15 Jun 2026 17:37:13 GMT
ステータス: 翻訳完了
システム内更新日: 2026-06-16 18:36:05.111448
Title: The Complexity of Min-Max Optimization for Quadratic Polynomials
Title（参考訳）: 二次多項式に対するMin-Max最適化の複雑さ
Authors: Martino Bernasconi, Matteo Castiglioni, Andrea Celli, Alexandros Hollender,
Abstract要約: 我々は、超キューブ上での min-max 最適化の近似定常点の計算が二次数に対してPPAD-hardであることを示す。その結果, 2-team 0-sum polymatrix に対するPPAD-hardness 結果が得られた。
参考スコア（独自算出の注目度）: 71.85811744604827
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: 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.
Abstract（参考訳）: 我々は、超キューブ上の min-max 最適化の近似定常点が二次多項式に対してPPAD-hard であることを証明する。これは多項式が多重線型である場合でも、各変数は少なくとも3つの単項に現れ、近似係数は逆多項式である。その結果, 2チームゼロサム・ポリマトリクスゲームにおけるPPAD硬度の最初の結果が得られた。

関連論文リスト

Polynomial-Time Solutions for ReLU Network Training: A Complexity Classification via Max-Cut and Zonotopes [70.52097560486683]
我々は、ReLUネットワークの近似の難しさがマックス・カッツ問題の複雑さを反映しているだけでなく、特定の場合において、それと完全に一致することを証明した。特に、$epsilonleqsqrt84/83-1approx 0.006$とすると、目的値に関して相対誤差$epsilon$でReLUネットワーク対象の近似グローバルデータセットを見つけることはNPハードであることが示される。
論文参考訳（メタデータ） (2023-11-18T04:41:07Z)
An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree [79.43134049617873]
本稿では,部分関数に対する完全次数と近似量子クエリの指数関数的分離を実証する。アルファベットのサイズについては、定値対分離の複雑さがある。
論文参考訳（メタデータ） (2023-01-22T22:08:28Z)
Accelerated and Improved Stabilization for High Order Moments of Racah Polynomials [0.6445605125467573]
Inproved Stabilization (ImSt) と呼ばれる新しいアルゴリズムを提案する。 ImStは、現在のアルゴリズムよりも高次になるまで、幅広いパラメータに対して機能する。
論文参考訳（メタデータ） (2022-12-30T17:07:26Z)
Enumeration of max-pooling responses with generalized permutohedra [39.58317527488534]
最大プーリング層(英: Max-pooling layer)は、入力座標のシフトしたウィンドウの最大値を取ることで入力アレイをサンプリングする関数である。このようなポリトープの面を特徴付け、1次元最大プーリング層における頂点数と面数の生成関数と閉式を得る。
論文参考訳（メタデータ） (2022-09-29T17:45:54Z)
Progressive approximation of bound states by finite series of square-integrable functions [0.0]
有限サイズの基底集合において、有界状態に対する時間非依存的なシュリンガー方程式を解くために「三対角表現法」を用いる。
論文参考訳（メタデータ） (2022-02-20T00:25:35Z)
Sums of Separable and Quadratic Polynomials [0.3222802562733786]
我々は分離可能プラス二次(SPQ)を研究します。凸spq最適化問題は「小さな」半定義プログラムによって解決できることを示す。
論文参考訳（メタデータ） (2021-05-11T03:26:46Z)
Complexity Aspects of Fundamental Questions in Polynomial Optimization [3.42658286826597]
P=NPがなければ、二次プログラムの局所最小値のユークリッド距離内の点を見つけるSDPは存在しないことを示す。また、最適値が有限であるプログラムが最適解を持つか否かをテストすることはNPハードであることを示す。最終章では,SDPの階層化に寄与する強制力の特性について紹介する。
論文参考訳（メタデータ） (2020-08-27T14:58:02Z)
Complexity aspects of local minima and related notions [3.42658286826597]
我々は (i) 臨界点、 (ii) 二次点、 (iii) 局所ミニマ、 (iv) 多変量に対する厳密な局所ミニマの概念を考える。立方体が臨界点を持つかどうかを決定することはNPハードであることを示す。本稿では,3階ニュートン法の設計における局所最小値立方体探索の可能性について概説する。
論文参考訳（メタデータ） (2020-08-14T00:50:13Z)
SURF: A Simple, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
SURFは分布を断片的に近似するアルゴリズムである。実験では最先端のアルゴリズムよりも優れています。
論文参考訳（メタデータ） (2020-02-22T01:03:33Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。