New Insight of Variance reduce in Zero-Order Hard-Thresholding: Mitigating Gradient Error and Expansivity Contradictions

Resumen Técnico: Nueva Perspectiva sobre la Reducción de Varianza en Umbralización Dura de Orden Cero

Enunciado del Problema
El artículo aborda el desafío de resolver problemas de optimización con restricciones $\ell_0$, fundamentales para lograr aprendizaje disperso en tareas de aprendizaje automático de alta dimensión. El problema específico se formula como la minimización de un riesgo empírico regularizado $F(\theta) = \frac{1}{n}\sum_{i=1}^n f_i(\theta)$ sujeto a $\|\theta\|_0 \leq k$. Si bien los algoritmos iterativos de umbralización dura son efectivos para las restricciones $\ell_0$, tradicionalmente requieren acceso a gradientes verdaderos. En muchos escenarios modernos —como problemas de banda, ataques adversarios de caja negra y aprendizaje por refuerzo— los gradientes son inaccesibles, lo que hace necesario el uso de métodos de optimización de orden cero (ZO) que dependen de evaluaciones de funciones.

El algoritmo actual de vanguardia para este entorno, Umbralización Dura Estocástica de Orden Cero (SZOHT), adolece de una limitación crítica. Los autores identifican un conflicto inherente entre la desviación (error) de los estimadores de gradiente ZO y la expansividad (no no-expansividad) del operador de umbralización dura. Para garantizar la convergencia, SZOHT impone condiciones estrictas sobre el número de direcciones aleatorias ($q$) utilizadas para la estimación del gradiente y el nivel de dispersión ($k$). Estas condiciones suelen ser demasiado restrictivas para aplicaciones prácticas, limitando la utilidad del algoritmo.

Metodología
El artículo propone una nueva perspectiva para resolver el conflicto entre los gradientes ZO y la umbralización dura centrándose en la reducción de varianza. Los autores argumentan que el conflicto es fundamentalmente entre el operador de umbralización dura y la varianza de la estimación del gradiente, y no el error de estimación en sí mismo.

Para abordar esto, el artículo introduce un marco generalizado llamado pM-SZHT (Umbralización Dura Estocástica de Orden Cero con p-Memorización). Este marco utiliza gradientes históricos para reducir la varianza, de manera similar a las técnicas de reducción de varianza de primer orden como SAGA y SVRG, pero adaptadas al entorno ZO. Los componentes principales incluyen:

1. Expresión Iterativa Generalizada: El algoritmo sigue la regla de actualización $\theta^{(r+1)} = H_k(\theta^{(r)} - \eta \hat{g}^{(r)}(\theta^{(r)}))$, donde $\hat{g}^{(r)}$ es una estimación de gradiente generalizada que incorpora reducción de varianza.
2. p-Memorización: El marco emplea un mecanismo de memoria donde un subconjunto aleatorio de estimaciones de gradiente se actualiza en cada iteración, permitiendo que el algoritmo aproveche la información histórica para estabilizar las estimaciones ZO.
3. Algoritmos Específicos: Dentro de este marco, los autores instancian algoritmos específicos, incluyendo VR-SZHT (una adaptación ZO de SVRG) y SARAH-SZHT (una adaptación ZO de SARAH).

Análisis Teórico
El artículo proporciona un análisis exhaustivo de la convergencia bajo supuestos estándar de aprendizaje disperso: Convexidad Fuerte Restringida (RSC) y Suavidad Fuerte Restringida (RSS).

• Mitigación del Conflicto: El análisis demuestra que, mediante el uso de reducción de varianza, el algoritmo puede eliminar la dependencia estricta del número de direcciones aleatorias ($q$) requerido para la convergencia. En SZOHT, $q$ debe ser lo suficientemente grande para satisfacer límites específicos en relación con $k$; en los métodos propuestos, la convergencia está garantizada para cualquier $q > 0$ (siempre que otros parámetros como la tasa de aprendizaje se elijan correctamente).
• Tasas de Convergencia: Los resultados teóricos muestran que los algoritmos propuestos logran tasas de convergencia mejoradas en comparación con SZOHT. Específicamente, la complejidad de consultas para VR-SZHT se deriva como $O([n + \frac{\kappa^3}{\kappa^2+1}] \log(1/\epsilon))$, lo que representa una mejora significativa sobre la complejidad de SZOHT de $O((k + d/s^2)\kappa^2 \log(1/\epsilon))$, particularmente cuando el número de condición $\kappa$ es grande.
• Independencia de $q$: Un hallazgo teórico clave es que la reducción de varianza desacopla la condición de convergencia del número de direcciones aleatorias, permitiendo una selección de parámetros más flexible.

Resultados Experimentales
Los autores validan sus métodos en dos tareas principales:

1. Regresión Ridge: Utilizando datos sintéticos, los algoritmos propuestos con reducción de varianza (VR-SZHT, SAGA-SZHT, SARAH-SZHT) superan consistentemente a SZOHT estándar y a ZOHT de gradiente completo (FGZOHT). Logran valores de función más bajos con menos operaciones de umbralización dura (NHT) y llamadas competitivas al oráculo de orden cero (IZO).
2. Ataques Adversarios de Caja Negra: Los métodos se aplican para generar perturbaciones adversarias universales dispersas en el conjunto de datos CIFAR-10 contra un clasificador de caja negra. Los resultados indican que los métodos con reducción de varianza, particularmente SARAH-SZHT y SAGA-SZHT, logran tasas de éxito de ataque más altas y valores de pérdida más bajos en comparación con SZOHT. Por ejemplo, SARAH-SZHT atacó con éxito 7 de 10 imágenes en la clase "avión", superando a SZOHT.

Significado y Afirmaciones
El artículo afirma proporcionar una "nueva perspectiva" sobre la reducción de varianza, enmarcándola no solo como un mecanismo de aceleración, sino como una herramienta necesaria para mitigar las contradicciones únicas entre los estimadores ZO y los operadores de umbralización dura. El significado del trabajo radica en:

• Relajación de Restricciones: Elimina las restricciones prohibitivas sobre el número de direcciones aleatorias ($q$) encontradas en SZOHT, haciendo viable la umbralización dura ZO para un rango más amplio de problemas del mundo real.
• Marco General: Establece un marco de análisis general (pM-SZHT) que abarca varios métodos ZO con reducción de varianza, ofreciendo una comprensión teórica unificada.
• Utilidad Práctica: Los resultados experimentales en ataques adversarios y regresión demuestran que estos métodos pueden lograr un rendimiento competitivo o superior en comparación con los algoritmos ZO de vanguardia, manteniendo al mismo tiempo las restricciones de dispersión.

Los autores concluyen que su enfoque mejora eficazmente los algoritmos existentes para la optimización de orden cero dispersa, ofreciendo una solución más flexible y resistente para escenarios donde los gradientes son inaccesibles.