Resumen Técnico: Búsqueda de Vecindad Grande Regularizada (RLNS)

Planteamiento del Problema

La integración de capas de optimización combinatoria en redes neuronales ha emergido como un paradigma poderoso para la predicción estructurada, permitiendo que los modelos generen decisiones discretas que satisfacen restricciones complejas. La formulación estándar involucra una capa definida por $\hat{y}(\theta) \triangleq \arg \max_{y \in \mathcal{Y}} \langle \theta, y \rangle$, donde $\mathcal{Y}$ es un conjunto finito pero combinatoriamente grande de salidas factibles.

El desafío fundamental en este entorno es la diferenciabilidad. Dado que el operador $\arg \max$ proporciona gradientes nulos en casi todas partes, los enfoques existentes suelen recurrir a la regularización para obtener una relajación continua y diferenciable. Sin embargo, la mayoría de los métodos actuales (por ejemplo, pérdidas Fenchel-Young, optimizadores perturbados) asumen fundamentalmente el acceso a un solucionador global exacto (un oráculo MAP global) o un oráculo marginal para calcular las expectativas de la distribución de Gibbs. Para problemas de optimización NP-duros comunes en investigación de operaciones, llamar a un oráculo global en cada paso de entrenamiento es computacionalmente intratable. En consecuencia, los profesionales dependen de heurísticas escalables como la Búsqueda de Vecindad Grande (LNS), que refina iterativamente las soluciones congelando subconjuntos de variables y reoptimizando el resto. La falta de un marco basado en principios para utilizar LNS como una capa combinatoria diferenciable sigue siendo un cuello de botella crítico.

Metodología: Búsqueda de Vecindad Grande Regularizada (RLNS)

Los autores presentan la Búsqueda de Vecindad Grande Regularizada (RLNS), una versión estocástica de LNS que cierra la brecha entre las heurísticas escalables y las capas de optimización diferenciables. La idea central es regularizar o perturbar los subproblemas locales dentro del marco de LNS, transformando la heurística en un muestreador de Cadenas de Markov Monte Carlo (MCMC) eficiente sobre el conjunto combinatorio de soluciones factibles.

1. Marco y Regularización Local

RLNS define una familia de funciones de regularización local derivadas de un regularizador global $\Omega$. Para un subconjunto de soluciones $\mathcal{Z} \subseteq \mathcal{Y}$, un regularizador local $\Omega_{\mathcal{Z}}$ se define mediante una aplicación de inclusión. En lugar de resolver el problema regularizado global, RLNS muestrea iterativamente de distribuciones localmente regularizadas $p_{\Omega_{\mathcal{Y}(k)}}((s_\theta)[\mathcal{Y}(k)])$, donde $\mathcal{Y}(k)$ es la vecindad local definida por el congelamiento de un subconjunto de coordenadas $S^{(k)}$.

2. Regularización Entrópica y Muestreo de Gibbs por Bloques

Cuando el regularizador global es la entropía negativa de Shannon ($\Omega = -\gamma H_s$), los autores demuestran que RLNS realiza un muestreo de Gibbs por bloques exacto. Específicamente, la distribución localmente regularizada coincide con la distribución de Gibbs globalmente regularizada condicionada en las variables fijas:
$$p_{\Omega_{\mathcal{Y}(k)}}((s_\theta)[\mathcal{Y}(k)](y) = p_{\Omega}(s_\theta)(y \mid y^{(k)}_{[S^{(k)}]})$$
Bajo un esquema de selección de variables irreducible, la distribución estacionaria de las iteraciones de RLNS converge exactamente a la distribución de Gibbs globalmente regularizada. Este resultado es único para la regularización entrópica; la Proposición 2 caracteriza la entropía de Shannon como el único regularizador separable que garantiza esta exactitud.

3. Regularización Basada en Perturbación

En escenarios donde los oráculos marginales locales (requeridos para el muestreo entrópico) son intratables, pero los oráculos MAP locales están disponibles, los autores proponen el uso de la regularización basada en perturbación. Al añadir ruido $\epsilon Z$ a las puntuaciones locales y resolver el problema de maximización local perturbado, RLNS puede muestrear de la distribución regularizada local. Este enfoque aprovecha los oráculos LNS estándar (por ejemplo, programación dinámica para subproblemas de la mochila) sin requerir mecanismos de rechjo de muestras, a diferencia de la búsqueda local basada en Metropolis-Hastings.

4. Aprendizaje e Interpolación

El artículo establece una conexión entre el número de iteraciones de RLNS ($K$) y el objetivo de aprendizaje:

• $K=1$ (Pérdida Fenchel-Young Local): Un solo paso de RLNS proporciona un estimador insesgado para una pérdida Fenchel-Young local. En el caso de la entropía, esto recupera el objetivo de verosimilitud compuesta (pseudolikelihood), que maximiza la verosimilitud de los subconjuntos de variables condicionadas al resto.
• $K \to \infty$ (Pérdida Fenchel-Young Global): A medida que aumentan las iteraciones, el estimador converge al gradiente de la pérdida Fenchel-Young global, aproximando la estimación de máxima verosimilitud exacta.
  Esto permite a los profesionales interpolar entre la verosimilitud compuesta y la estimación de máxima verosimilitud exacta ajustando $K$, permitiendo el aprendizaje de extremo a extremo sin solucionadores globales.

Contribuciones Clave

1. Marco RLNS: Introducción de una versión estocástica y regularizada de LNS que integra la regularización local en los subproblemas de LNS, creando una capa combinatoria diferenciable.
2. Equivalencia Teórica: Demostración de que, bajo la regularización entrópica, RLNS implementa un muestreador de Gibbs por bloques exacto cuya distribución estacionaria coincide con la distribución de Gibbs globalmente regularizada.
3. Tractabilidad vía Perturbación: Demostración de que la regularización basada en perturbación permite que RLNS utilice oráculos MAP locales estándar, asegurando la tractabilidad siempre que la LNS estándar sea tratable.
4. Interpolación de Paradigmas de Aprendizaje: Demostración teórica y empírica de que el número de iteraciones de RLNS permite la interpolación entre la verosimilitud compuesta y la estimación de máxima verosimilitud exacta.
5. Validación Empírica: Evaluación en tres problemas distintos:
   • Vectores $\kappa$-hot: Tarea de estimación controlada que valida la convergencia frente a la verdad de campo base (ground truth).
   • Problema de Asignación Generalizada (GAP): Aprendizaje para predecir asignaciones donde los subproblemas locales son problemas de la mochila 0/1.
   • Programación de Vehículos Estocástica: Un benchmark del mundo real donde RLNS-1 supera a las bases de diferenciación de caja negra y de entropía cruzada binaria.

Resultados

• Convergencia: En el experimento de vectores $\kappa$-hot, RLNS converge más rápido que el MCMC de búsqueda local y logra un Error Absoluto Medio (MAE) menor que la estimación de Monte Carlo para el mismo número de muestras, particularmente cuando una alta proporción de variables se mantienen libres.
• Escalabilidad: En los experimentos de GAP, los oráculos MAP locales utilizados por RLNS son órdenes de magnitud más rápidos que los solucionadores de Programación Lineal Entera Mixta (MILP) globales, especialmente a medida que aumenta la escala del problema.
• Rendimiento: En la programación de vehículos estocástica, RLNS-1 (usando una sola iteración) casi iguala el rendimiento del aprendizaje Fenchel-Young perturbado (PFY) global en términos de costo de retraso, mientras que solo requiere que el solucionador procese subproblemas de aproximadamente un tercio del tamaño original. Supera significativamente a las bases de Diferenciación de Caja Negra (DBB) y de Entropía Cruzada Binaria (BCE).
• Análisis de Sesgo: Los límites teóricos muestran que el error de aproximación escala con el número de restricciones compartidas (restricciones de corte) entre las variables congeladas y las libres, lo que motiva esquemas de selección de variables que minimicen estas dependencias cruzadas (por ejemplo, selección de corte mínimo).

Significado y Reivindicaciones

El artículo afirma cerrar una brecha crítica en la literatura al permitir el uso de heurísticas altamente escalables (LNS) como capas diferenciables en redes neuronales, eliminando la dependencia de solucionadores globales computacionalmente intratables. Al establecer una conexión rigurosa entre LNS y el muestreo de Gibbs, este trabajo proporciona un marco basado en principios para diferenciar a través de capas de optimización combinatoria utilizando únicamente oráculos locales. Los autores posicionan a RLNS como una solución práctica para el aprendizaje de extremo a extremo en tareas de predicción estructurada que involucran restricciones NP-duras, ofreciendo un compromiso ajustable entre el costo computacional y la precisión estadística mediante el número de iteraciones $K$.