Complexity aspects of local minima and related notions

• URL: http://arxiv.org/abs/2008.06148v2
• Date: Tue, 15 Jun 2021 22:05:57 GMT
• Title: Complexity aspects of local minima and related notions
• Authors: Amir Ali Ahmadi, Jeffrey Zhang
• Abstract summary: We consider the notions of (i) critical points, (ii) second-order points, (iii) local minima, and (iv) strict local minima for multivariates. We show that it is strongly NP-hard to decide if a cubic has a critical point. We briefly present a potential application of finding local minima cubics to the design of a third-order Newton method.
• Score: 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.

Related papers

• 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)
• On Maximal Families of Binary Polynomials with Pairwise Linear Common Factors [1.249418440326334]
  We characterize maximal families over the binary field $mathbbF$. Our findings prompt several more open questions, which we plan to address in an extended version of this work.
  arXiv  Detail & Related papers  (2024-05-14T16:30:28Z)
• Efficient Solution of Point-Line Absolute Pose [52.775981113238046]
  We revisit certain problems of pose estimation based on 3D--2D correspondences between features which may be points or lines. We show experimentally that the resulting solvers are numerically stable and fast.
  arXiv  Detail & Related papers  (2024-04-25T12:09:16Z)
• Polynomial-Time Solutions for ReLU Network Training: A Complexity Classification via Max-Cut and Zonotopes [70.52097560486683]
  We prove that the hardness of approximation of ReLU networks not only mirrors the complexity of the Max-Cut problem but also, in certain special cases, exactly corresponds to it. In particular, when $epsilonleqsqrt84/83-1approx 0.006$, we show that it is NP-hard to find an approximate global dataset of the ReLU network objective with relative error $epsilon$ with respect to the objective value.
  arXiv  Detail & Related papers  (2023-11-18T04:41:07Z)
• A Direct Reduction from the Polynomial to the Adversary Method [92.54311953850168]
  We give a simple and direct reduction from the method (in the form of a dual) to the adversary method. This shows that any lower bound in the form of a dual is an adversary lower bound of a specific form.
  arXiv  Detail & Related papers  (2023-01-24T21:37:20Z)
• An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree [79.43134049617873]
  In this paper, we demonstrate an exponential separation between exact degree and approximate quantum query for a partial function. For an alphabet size, we have a constant versus separation complexity.
  arXiv  Detail & Related papers  (2023-01-22T22:08:28Z)
• Shallow neural network representation of polynomials [91.3755431537592]
  We show that $d$-variables of degreeR$ can be represented on $[0,1]d$ as shallow neural networks of width $d+1+sum_r=2Rbinomr+d-1d-1d-1[binomr+d-1d-1d-1[binomr+d-1d-1d-1[binomr+d-1d-1d-1d-1[binomr+d-1d-1d-1d-1
  arXiv  Detail & Related papers  (2022-08-17T08:14:52Z)
• Sums of Separable and Quadratic Polynomials [0.3222802562733786]
  We study separable plus quadratic (SPQ)s. We show that convex SPQ optimization problems can be solved by "small" semidefinite programs.
  arXiv  Detail & Related papers  (2021-05-11T03:26:46Z)
• Complexity Aspects of Fundamental Questions in Polynomial Optimization [3.42658286826597]
  We show that unless P=NP, there cannot be a SDP that finds a point within Euclidean distance of a local minimum of a quadratic program. We also show that testing whether aally constrained program with a finite optimal value has an optimal solution is NP-hard. In our final chapter, we present an characterization of coercives that lends itself to a hierarchy of SDPs.
  arXiv  Detail & Related papers  (2020-08-27T14:58:02Z)
• On the complexity of finding a local minimizer of a quadratic function over a polytope [1.0048921884287543]
  We show that unless P=NP, there cannot be a Euclidean-time algorithm that finds a point within $cn$ of a local minimizer of an $n$ quadratic function over a polytope. Our proof technique also implies that the problem of deciding whether a quadratic function has a local minimizer over anunbounded polyhedron, and that of deciding if a quartic has a local minimizer are NP-hard.
  arXiv  Detail & Related papers  (2020-08-12T20:09:34Z)
• SURF: A Simple, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  SURF is an algorithm for approximating distributions by piecewises. It outperforms state-of-the-art algorithms in experiments.
  arXiv  Detail & Related papers  (2020-02-22T01:03:33Z)

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.