Error bounds, PL condition, and quadratic growth for weakly convex functions, and linear convergences of proximal point methods

Resumen Técnico: Límites de Error, Condición PL, Crecimiento Cuadrático para Funciones Débilmente Convexas, y Convergencias Lineales de Métodos de Punto Proximal

Planteamiento del Problema
Muchos problemas de optimización prácticos, particularmente en el aprendizaje automático y el procesamiento de señales, carecen de convexidad fuerte. Si bien se sabe que los algoritmos de primer orden logran la convergencia lineal bajo convexidad fuerte, estudios recientes han demostrado que también se puede garantizar la convergencia lineal bajo condiciones de regularidad más débiles (por ejemplo, la desigualdad de Polyak-Lojasiewicz, límites de error, crecimiento cuadrático) para funciones suaves y convexas. Sin embargo, las relaciones entre estas condiciones no se comprendían bien en el entorno de las funciones no suaves y no convexas. Específamente, la clase de funciones débilmente convexas (funciones tales que $f + \frac{\rho}{2}\|\cdot\|^2$ es convexa para algún $\rho \geq 0$) abarca muchos modelos modernos (por ejemplo, redes profundas no suaves, composiciones de funciones convexas y suaves), pero carecía de un marco unificado que conectara estas condiciones de regularidad. Además, las pruebas existentes para la convergencia lineal del Método de Punto Proximal (PPM) a menudo dependían de supuestos restrictivos (por ejemplo, minimizadores únicos, continuidad de Lipschitz local del subdiferencial inverso) o argumentos complejos.

Metodología
El artículo emplea herramientas del análisis no suave, específicamente la noción de pendiente, el principio de variación de Ekeland y los lemmas de estimación de distancia, para analizar las relaciones entre las condiciones de regularidad. Los autores definen cinco condiciones clave sobre un conjunto de nivel $[f \leq f^\star + \nu]$:

1. Convexidad Fuerte (SC)
2. Desigualdad de Secante Restringida (RSI)
3. Límite de Error del Subdiferencial (EB)
4. Desigualdad de Polyak-Lojasiewicz (PL)
5. Crecimiento Cuadrático (QG)

Los autores utilizan la pendiente $|\nabla f|(x) = \text{dist}(0, \hat{\partial}f(x))$ (donde $\hat{\partial}f$ es el subdiferencial de Fréchet) para cerrar la brecha entre los entornos suaves y no suaves. Establecen implicaciones lógicas y equivalencias entre estas condiciones, enfocándose particularmente en el caso donde la constante de crecimiento cuadrático $\mu_q$ excede el parámetro de convexidad débil $\rho$.

Basándose en estas equivalencias, el artículo analiza el Método de Punto Proximal (PPM):
$$x_{k+1} = \text{prox}_{c_k f}(x_k) = \arg\min_x \left( f(x) + \frac{1}{2c_k}\|x - x_k\|^2 \right)$$
Los autores proporcionan una prueba modular para la convergencia lineal tanto en entornos convexos como débilmente convexos. También extienden el análisis al PPM Inexacto (iPPM), donde los subproblemas se resuelven de forma aproximada, abordando sutilezas respecto a los criterios de parada y la factibilidad (asegurando que las iteraciones permanezcan dentro del dominio de $f$).

Contribuciones Clave

1. Unificación de las Condiciones de Regularidad para Funciones Débilmente Convexas:
   El artículo establece la jerarquía y equivalencia de las condiciones de regularidad para funciones $\rho$-débilmente convexas.

   • Cadena de Implicación General: $(SC) \implies (RSI) \implies (EB) \iff (PL) \implies (QG)$.
   • Equivalencia bajo $\mu_q > \rho$: Si una función $\rho$-débilmente convexa satisface el Crecimiento Cuadrático con una constante $\mu_q > \rho$, entonces las cuatro condiciones $(RSI), (EB), (PL)$y$(QG)$ son equivalentes.
   • Los autores derivan conversiones de coeficientes explícitas entre estas condiciones (resumidas en la Tabla 1 del artículo), lo que permite a los profesionales traducir constantes de una condición a otra.

2. Pruebas Simplificadas de Convergencia Lineal para PPM:
   El artículo presenta una prueba simple y modular para la convergencia lineal de PPM para funciones tanto convexas como débilmente convexas.

   • Caso Convexo: Bajo cualquiera de las condiciones de regularidad equivalentes (PL, EB, RSI, QG), el PPM logra la convergencia lineal tanto para los valores de la función como para la distancia al conjunto de soluciones. La prueba relaja supuestos previos, eliminando el requisito de un minimizador único o de la continuidad de Lipschitz local del subdiferencial inverso.
   • Caso Débilmente Convexo: Los resultados se extienden a funciones $\rho$-débilmente convexas siempre que la inicialización esté dentro de un conjunto de nivel que satisfaga QG con $\mu_q > \rho$ y que los tamaños de paso cumplan $1/c_k > \rho$.

3. Análisis del PPM Inexacto (iPPM):
   Los autores aclaran los matices de la inexactitud y la factibilidad en el iPPM. Establecen la convergencia lineal para el iPPM bajo criterios de parada estándar (criterios A y B de Rockafellar), siempre que la función satisfaga QG en un vecindad del conjunto de soluciones. La prueba combina una desigualdad clave de la literatura previa con el marco de condiciones de regularidad modular.

Resultos

• Teóricos: El Teorema 3.1 confirma que, para funciones débilmente convexas, la equivalencia de las condiciones de regularidad se mantiene si $\mu_q > \rho$. Esto generaliza resultados previos limitados a funciones suaves o convexas.
• Algorítmicos: Los Teoremas 4.2 y 4.3 demuestran que el PPM converge linealmente con tasas que dependen de las constantes de regularidad (por ejemplo, $\omega_k = \frac{1}{1+c_k\mu_p}$). El Teorema 5.3 extiende esto al PPM inexacto, mostrando que mientras la inexactitud esté controlada (la suma de los errores es finita), la tasa de convergencia lineal se preserva asintóticamente.
• Numéricos: Experimentos en problemas de SVM Lineal, Lasso y Elastic-Net confirman la convergencia lineal teórica del PPM. Los experimentos utilizan el paquete de modelado YALMIP y el solver MOSEK, mostrando una convergencia rápida tanto en las brechas de valor de costo como en la distancia al conjunto de soluciones.

Significancia y Reivindicaciones
El artículo afirma generalizar la comprensión de las condiciones de regularidad desde los entornos suaves/convexos hacia la clase más amplia de funciones no suaves débilmente convexas. Al aclarar las conexiones entre estas condiciones, los autores proporcionan un marco unificado que simplifica el análisis de algoritmos iterativos.

Específicamente, el artículo sostiene que:

• La equivalencia de las condiciones (RSI, EB, PL, QG) bajo $\mu_q > \rho$ permite un análisis flexible; se puede establecer una condición para derivar resultados de convergencia a través de las otras.
• Las pruebas de convergencia lineal de PPM son más simples y transparentes que la literatura existente, evitando supuestos restrictivos como los minimizadores únicos.
• Los resultados facilitan el desarrollo de algoritmos para la optimización no suave, particularmente en aplicaciones de optimización cónica de gran escala y aprendizaje automático donde la convexidad débil es prevalente.

Los autores señalan que, si bien la equivalencia de estas condiciones era conocida para funciones suaves o convexas, extender esto al entorno de las funciones débilmente convexas y proporcionar una prueba limpia para el PPM (incluyendo versiones inexactas) constituye la principal novedad. El trabajo se presenta como una versión extendida de un artículo de conferencia, con la adición de pruebas detalladas, conversiones de coeficientes y un análisis extendido del iPP inexacto.