論文の概要: Complexity aspects of local minima and related notions
- arxiv url: http://arxiv.org/abs/2008.06148v2
- Date: Tue, 15 Jun 2021 22:05:57 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-30 18:02:16.558135
- Title: Complexity aspects of local minima and related notions
- Title（参考訳）: 局所ミニマの複雑性と関連する概念
- Authors: Amir Ali Ahmadi, Jeffrey Zhang
- Abstract要約: 我々は (i) 臨界点、 (ii) 二次点、 (iii) 局所ミニマ、 (iv) 多変量に対する厳密な局所ミニマの概念を考える。
立方体が臨界点を持つかどうかを決定することはNPハードであることを示す。
本稿では,3階ニュートン法の設計における局所最小値立方体探索の可能性について概説する。
- 参考スコア（独自算出の注目度）: 3.42658286826597
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the notions of (i) critical points, (ii) second-order points,
(iii) local minima, and (iv) strict local minima for multivariate polynomials.
For each type of point, and as a function of the degree of the polynomial, we
study the complexity of deciding (1) if a given point is of that type, and (2)
if a polynomial has a point of that type. Our results characterize the
complexity of these two questions for all degrees left open by prior
literature. Our main contributions reveal that many of these questions turn out
to be tractable for cubic polynomials. In particular, we present an
efficiently-checkable necessary and sufficient condition for local minimality
of a point for a cubic polynomial. We also show that a local minimum of a cubic
polynomial can be efficiently found by solving semidefinite programs of size
linear in the number of variables. By contrast, we show that it is strongly
NP-hard to decide if a cubic polynomial has a critical point. We also prove
that the set of second-order points of any cubic polynomial is a spectrahedron,
and conversely that any spectrahedron is the projection of the set of
second-order points of a cubic polynomial. In our final section, we briefly
present a potential application of finding local minima of cubic polynomials to
the design of a third-order Newton method.
- Abstract（参考訳）: 我々はその概念を考える
(i)臨界点
(ii)二次点
(iii)地方ミニマ、及び
(iv) 多変量多項式に対する厳密な局所ミニマ。
各種類の点について、および多項式の次数の関数として、(1) が与えられた点がその型である場合、(2) がその型の点を持つ場合、(1) を決定する複雑さについて検討する。
本研究は,この2つの質問の難易度を,文献に残した全ての程度に特徴付ける。
我々の主な貢献は、これらの問題の多くは立方多項式に対して扱いやすいことが判明した。
特に、立方多項式の点の局所極小性に対して、効率的にチェック可能な必要十分条件を示す。
また,変数数に線形な大きさの半定値プログラムを解いて,立方多項式の局所最小値を求めることができることを示した。
対照的に、立方体多項式が臨界点を持つかどうかを決定することはNPハードであることを示す。
また、任意の立方多項式の 2次点の集合が spectrahedron であり、逆に任意の spectrahedron が立方多項式の 2次点の集合の射影であることも証明する。
最後の節では、三階ニュートン法の設計に立方多項式の局所的極小を見つける潜在的な応用について簡単に述べる。
関連論文リスト
- The polarization hierarchy for polynomial optimization over convex bodies, with applications to nonnegative matrix rank [0.6963971634605796]
我々は、凸体上の関数を制約に最適化する問題に対して、外部近似の収束族を構築する。
階層の3段階の数値的な実装は、この問題に対して非常に厳密な近似をもたらすことが示されている。
論文 参考訳（メタデータ） (2024-06-13T18:00:09Z) - On Maximal Families of Binary Polynomials with Pairwise Linear Common Factors [1.249418440326334]
二進体 $mathbbF$ 上の極大族を特徴づける。
我々の発見は、よりオープンないくつかの質問を呼び起こし、この研究の拡張バージョンで対処する予定です。
論文 参考訳（メタデータ） (2024-05-14T16:30:28Z) - Efficient Solution of Point-Line Absolute Pose [52.775981113238046]
点や線である可能性のある特徴間の3D--2D対応に基づくポーズ推定の特定の問題を再検討する。
得られた解法は数値的に安定かつ高速であることを示す。
論文 参考訳（メタデータ） (2024-04-25T12:09:16Z) - 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) - A Direct Reduction from the Polynomial to the Adversary Method [92.54311953850168]
逆法に(双対の形で)方法から単純かつ直接的に還元する。
これは、双対形式におけるどんな下界も、特定の形式の逆下界であることを示している。
論文 参考訳（メタデータ） (2023-01-24T21:37:20Z) - An Exponential Separation Between Quantum Query Complexity and the
Polynomial Degree [79.43134049617873]
本稿では,部分関数に対する完全次数と近似量子クエリの指数関数的分離を実証する。
アルファベットのサイズについては、定値対分離の複雑さがある。
論文 参考訳（メタデータ） (2023-01-22T22:08:28Z) - Shallow neural network representation of polynomials [91.3755431537592]
d+1+sum_r=2Rbinomr+d-1d-1[binomr+d-1d-1d-1[binomr+d-1d-1d-1]binomr+d-1d-1d-1[binomr+d-1d-1d-1]binomr+d-1d-1d-1]
論文 参考訳（メタデータ） (2022-08-17T08:14:52Z) - 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) - On the complexity of finding a local minimizer of a quadratic function
over a polytope [1.0048921884287543]
P=NPがなければ、ポリトープ上の$n$2次関数の局所最小値の$cn$以内の点を見つけるユークリッド時間アルゴリズムは存在しない。
また,2次関数が非有界ポリヘドロン上の局所最小値を持つか否か,およびクォートが局所最小値を持つか否かを判定する問題も示唆している。
論文 参考訳（メタデータ） (2020-08-12T20:09:34Z) - SURF: A Simple, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
SURFは分布を断片的に近似するアルゴリズムである。
実験では最先端のアルゴリズムよりも優れています。
論文 参考訳（メタデータ） (2020-02-22T01:03:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。