On Approximate Computation of Critical Points

Technical Summary: On Approximate Computation of Critical Points

Problem Statement
The paper addresses the computational complexity of finding critical points (stationary points where the gradient vanishes) for nonconvex functions, specifically focusing on the tractability of approximate computation. While it is well-established that finding exact critical points for cubic polynomials is NP-hard, a prevailing belief in the optimization community suggests that finding approximate critical points—points where the gradient norm is small ($\|\nabla f(x)\| \le \epsilon$) or points close to a true critical point ($\|x - x^*\| \le \epsilon$)—should be computationally tractable. The authors challenge this intuition, investigating whether even coarse approximations of critical points can be computed in polynomial time for simple classes of nonconvex functions, such as low-degree polynomials.

Methodology
The authors employ the standard Turing model of computation, where the input consists of the coefficients of a parametric function class (primarily polynomials of fixed degree). The core methodology involves polynomial-time reductions from the Clique problem (a known NP-complete problem) to the problem of finding approximate critical points.

Key technical tools include:

1. Polynomial Construction: The authors construct specific cubic and quartic polynomials (and products of polynomials with exponentials) whose critical points correspond to cliques in a given graph. A central construction is a quartic polynomial $g_{G,C,k}(x)$ designed such that its roots correspond exactly to indicator vectors of $k$-cliques in a graph $G$.
2. Hardness of Approximation: To prove hardness for approximate computation, the authors must demonstrate that if an algorithm returns a point that is "close" to being a critical point (in terms of gradient norm or Euclidean distance), it effectively solves the underlying NP-hard decision problem.
3. Analytical Bounds: The proofs rely heavily on bounding the behavior of the constructed polynomials. This includes:
   • Establishing that the polynomials are coercive and attain minima.
   • Using the First and Second Order Necessary Conditions (FONC/SONC) to bound the location of minimizers.
   • Applying Lipschitz continuity arguments to relate the value of the polynomial at a point near a critical point to the value at the true critical point.
   • Utilizing bounds on the roots of univariate polynomials (Fujiwara's bound) to constrain the magnitude of variables.

Key Contributions and Results

The paper establishes that computing approximate critical points is intractable (unless P=NP) under several distinct definitions of "approximation" and under various structural assumptions:

1. $\epsilon$-Approximate Critical Points (Gradient Norm):

   • Theorem 3: The authors prove that unless P=NP, no polynomial-time algorithm can compute a $2^n$-approximate critical point (where $\|\nabla p(x)\| \le 2^n$) for a cubic polynomial in $n$ variables. This holds even if the algorithm is allowed to return an arbitrary point when no critical point exists.
   • Corollary 8: This result extends to pseudo-polynomial time algorithms for finding $n^d$-approximate critical points.
   • Implication for Unique Critical Points: The hardness persists even if the polynomial is promised to have a unique critical point. Finding a $2^n$-approximate critical point in this setting would refute the Planted Clique conjecture and imply NP=RP.

2. Structural Assumptions (Lower Boundedness and Uniqueness):

   • Proposition 9: Deciding if the exponential of a cubic polynomial (which is always lower bounded) has a critical point is NP-hard.
   • Proposition 10: Even for lower-bounded functions guaranteed to have a critical point and no spurious critical points (i.e., every critical point is a global minimum), finding a critical point is hard. This implies that the absence of spurious local minima does not guarantee tractability.
   • Theorem 11: For lower-bounded quartic polynomials, finding a $2^n$-approximate critical point within a ball of radius $2^n$ is NP-hard, even if the algorithm is permitted to behave arbitrarily when no critical point exists in the unit hypercube.

3. $\epsilon$-Near Critical Points (Distance to Solution):

   • Definition: An $\epsilon$-near critical point is a point within distance $\epsilon$ of a true critical point.
   • Theorem 13: Unless P=NP, no polynomial-time algorithm can compute a $\frac{1}{12000 n^{3.5}}$-near critical point for a cubic polynomial.
   • Theorem 15: This hardness result extends to lower-bounded functions (products of quartic polynomials and exponentials), showing that finding a $\frac{1}{1000 n^7}$-near critical point is also intractable.

Significance and Claims
The paper's primary significance lies in overturning the common belief that approximate critical point computation is a tractable task in nonconvex optimization. The authors argue that the hardness of nonconvex optimization does not stem solely from the presence of spurious local minima or saddle points, but is intrinsic to the task of locating any stationary point, even approximately.

• Contrast with Oracle Models: The authors distinguish their results from prior work in oracle-based models (e.g., Carmon et al., Hollender and Zampetakis), which provide lower bounds on query complexity. This paper operates in the Turing model, ruling out any polynomial-time algorithm, including those based on convex relaxations or other non-oracle approaches.
• Implications for Algorithms: The results suggest that standard algorithms like Gradient Descent or Newton's method (and its higher-order extensions) cannot be guaranteed to find even coarse approximations of critical points in polynomial time for general cubic polynomials. Specifically, the paper notes that the most natural higher-order extension of Newton's method (solving for critical points of degree-3 Taylor expansions) lacks tractable per-iteration complexity unless P=NP.
• Future Directions: The authors modestly conclude that their results motivate the search for specific classes of parametric functions and structural assumptions (checkable in polynomial time) under which approximate critical point computation becomes tractable. They note that while convexity allows for tractability, checking convexity for polynomials of degree 4 or higher is itself hard, leaving a gap in understanding which structural properties enable efficient approximation.