On Approximate Computation of Critical Points

Resumen Técnico: Sobre la Computación Aproximada de Puntos Críticos

Planteamiento del Problema
El artículo aborda la complejidad computacional de encontrar puntos críticos (puntos estacionarios donde el gradiente se anula) para funciones no convexas, centrándose específicamente en la tractabilidad de la computación aproximada. Si bien está bien establecido que encontrar puntos críticos exactos para polinomios cúbicos es NP-duro, una creencia prevalente en la comunidad de optimización sugiere que encontrar puntos críticos aproximados —puntos donde la norma del gradiente es pequeña ($\|\nabla f(x)\| \le \epsilon$) o puntos cercanos a un punto crítico real ($\|x - x^*\| \le \epsilon$)— debería ser computacionalmente tratable. Los autores desafían esta intuición, investigando si incluso las aproximaciones toscas de los puntos críticos pueden computarse en tiempo polinomial para clases simples de funciones no convexas, como los polinomios de bajo grado.

Metodología
Los autores emplean el modelo de Turing estándar de computación, donde la entrada consiste en los coeficientes de una clase de funciones paramétricas (principalmente polinomios de grado fijo). La metodología central implica reducciones de tiempo polinomial desde el problema de Clique (un problema conocido como NP-completo) hacia el problema de encontrar puntos críticos aproximados.

Herramientas técnicas clave:

1. Construcción Polinomial: Los autores construyen polinomios cúbicos y cuárticos específicos (y productos de polinomios con exponenciales) cuyos puntos críticos corresponden a cliques en un grafo dado. Una construcción central es un polinomio cuártico $g_{G,C,k}(x)$ diseñado de tal manera que sus raíces corresponden exactamente a los vectores indicadores de $k$-cliques en un grafo $G$.
2. Dureza de la Aproximación: Para probar la dureza de la computación aproximada, los autores deben demostrar que si un algoritmo devuelve un punto que está "cerca" de ser un punto crítico (en términos de la norma del gradiente o la distancia euclidiana), este resuelve efectivamente el problema de decisión subyacente que es NP-duro.
3. Límites Analíticos: Las demostraciones dependen fuertemente de acotar el comportamiento de los polinomios construidos. Esto incluye:
   • Establecer que los polinomios son coercitivos y alcanzan mínimos.
   • Utilizar las Condiciones Necesarias de Primer y Segundo Orden (FONC/SONC) para acotar la ubicación de los minimizadores.
   • Aplicar argumentos de continuidad de Lipschitz para relacionar el valor del polinomio en un punto cercano a un punto crítico con el valor en el punto crítico real.
   • Utilizar límites sobre las raíces de polinomios univariados (el límite de Fujiwara) para restringir la magnitud de las variables.

Contribuciones Clave y Resultados

El artículo establece que computar puntos críticos aproximados es intratable (a menos que P=NP) bajo varias definiciones distintas de "aproximación" y bajo diversas suposiciones estructurales:

1. Puntos Críticos $\epsilon$-Aproximados (Norma del Gradiente):

   • Teorema 3: Los autores demuestran que, a menos que P=NP, ningún algoritmo de tiempo polinomial puede computar un punto crítico $2^n$-aproximado (donde $\|\nabla p(x)\| \le 2^n$) para un polinomio cúbico en $n$ variables. Esto se mantiene incluso si el algoritmo tiene permitido devolver un punto arbitrario cuando no existe un punto crítico.
   • Corolario 8: Este resultado se extiende a algoritmos de tiempo pseudo-polinomial para encontrar puntos críticos $n^d$-aproximados.
   • Implicación para Puntos Críticos Únicos: La dureza persiste incluso si se garantiza que el polinomio tiene un único punto crítico. Encontrar un punto crítico $2^n$-aproximado en este escenario refutaría la conjetura de Planted Clique e implicaría que NP=RP.

2. Suposiciones Estructurales (Acotación Inferior y Unicidad):

   • Proposición 9: Decidir si la exponencial de un polinomio cúbico (que siempre está acotado inferiormente) tiene un punto crítico es NP-duro.
   • Proposición 10: Incluso para funciones acotadas inferiormente que garantizan tener un punto crítico y sin puntos críticos espurios (es decir, cada punto crítico es un mínimo global), encontrar un punto crítico es difícil. Esto implica que la ausencia de mínimos locales espurios no garantiza la tractabilidad.
   • Teorema 11: Para polinomios cuárticos acotados inferiormente, encontrar un punto crítico $2^n$-aproximado dentro de una bola de radio $2^n$ es NP-duro, incluso si se permite al algoritmo comportarse arbitrariamente cuando no existe un punto crítico en el hipercubo unitario.

3. Puntos Críticos $\epsilon$-Cercanos (Distancia a la Solución):

   • Definición: Un punto crítico $\epsilon$-cercano es un punto dentro de una distancia $\epsilon$ de un punto crítico real.
   • Teorema 13: A menos que P=NP, ningún algoritmo de tiempo polinomial puede computar un punto crítico $\frac{1}{12000 n^{3.5}}$-cercano para un polinomio cúbico.
   • Teorema 15: Este resultado de dureza se extiende a funciones acotadas inferiormente (productos de polinomios cuárticos y exponenciales), mostrando que encontrar un punto crítico $\frac{1}{1000 n^7}$-cercano también es intratable.

Significancia y Reivindicaciones
La principal significancia del artículo radica en revertir la creencia común de que la computación de puntos críticos aproximados es una tarea tratable en la optimización no convexa. Los autores argumentan que la dureza de la optimización no convexa no proviene únicamente de la presencia de mínimos locales espurios o puntos de silla, sino que es intrínseca a la tarea de localizar cualquier punto estacionario, incluso de forma aproximada.

• Contraste con Modelos de Oráculo: Los autores distinguen sus resultados de trabajos previos en modelos basados en oráculos (por ejemplo, Carmon et al., Hollender y Zampetakis), los cuales proporcionan límites inferiores en la complejidad de consultas. Este artículo opera en el modelo de Turing, descartando cualquier algoritmo de tiempo polinomial, incluyendo aquellos basados en relajaciones convexas u otros enfoques que no sean de oráculo.
• Implicaciones para Algoritmos: Los resultados sugieren que algoritmos estándar como el Descenso de Gradiente o el método de Newton (y sus extensiones de orden superior) no pueden garantizar el hallazgo de siquiera aproximaciones toscas de puntos críticos en tiempo polinomial para polinomios cúbicos generales. Específicamente, el artículo señala que la extensión más natural del método de Newton (resolver los puntos críticos de expansiones de Taylor de grado 3) carece de una complejidad por iteración tratable a menos que P=NP.
• Direcciones Futuras: Los autores concluyen modestamente que sus resultados motivan la búsqueda de clases específicas de funciones paramétricas y suposiciones estructurales (verificables en tiempo polinomial) bajo las cuales la computación de puntos críticos aproximados sea tratable. Observan que, si bien la convexidad permite la tractabilidad, verificar la convexidad para polinomios de grado 4 o superior es, en sí mismo, difícil, dejando un vacío en la comprensión de qué propiedades estructurales permiten una aproximación eficiente.