Resumen Técnico: Un Marco Unificado para Tickets de Lotería Fuertes Cuantizados y Continuos

Planteamiento del Problema

La Hipótesis del Ticket de Lotería Fuerte (SLTH, por sus siglas en inglés) postula que redes neuronales suficientemente sobreparametrizadas y con inicialización aleatoria contienen subredes dispersas capaces de igualar el rendimiento de una red más pequeña entrenada sin realizar actualizaciones de pesos. Si bien los fundamentos teóricos de la SLTH dependen en gran medida del Problema de la Suma de Subconjuntos Aleatorios (RSSP), la literatura existente se ha limitado en gran medida al entorno continuo (pesos de precisión arbitraria).

Las extensiones recientes al entorno cuantizado, donde los pesos se muestrean de conjuntos discretos, han enfrentado limitaciones significativas. Trabajos previos en este dominio (por ejemplo, Diffenderfer y Kailkhura [2021], Sreenivasan et al. [2022], Kumar y Natale [2025]) o bien restringieron las redes objetivo a pesos continuos aproximándolos con redes binarias, o proporcionaron garantías para representaciones exactas en entornos cuantizados con solo un decaimiento inverso-polinomial en la probabilidad de fallo. Además, estos enfoques trataron las representaciones aproximadas (continuas) y las representaciones exactas (cuantizadas) como líneas de investigación disjuntas, careciendo de un marco teórico unificado que contemple simultáneamente los errores de redondeo y de aproximación.

Metodología

Los autores abordan estas brechas desarrollando un análisis riguroso del RSSP en el entorno discreto y aplicándolo a la SLTH cuantizada.

1. Problema de la Suma de Subconjuntos Aleatorios Discreto (RSSP)

La contribución matemática central es un nuevo análisis del RSSP discreto. Los autores definen el problema donde las variables aleatorias $X_1, \dots, X_n$ son muestreadas uniformemente de un conjunto discreto $\{-M, \dots, M\}$, y el objetivo es encontrar un subconjunto cuya suma sea un objetivo $z$ dentro de una tolerancia $\Delta$.

• Relación de Recurrencia: El análisis utiliza una relación de recurrencia para la función indicadora $f_t(z)$, que representa si un objetivo $z$ es $\Delta$-aproximado en el tiempo $t$.
• Análisis de Crecimiento de Volumen: Los autores rastrean el crecimiento del "volumen" $v_t$, definido como el número de valores distintos en el rango $\{-M, \dots, M\}$ que pueden ser $\Delta$-aproximados. Demuestran que $v_t$ crece en dos fases distintas:
  1. Crecimiento Rápido: $v_t$ alcanza rápidamente $M+1$.
  2. Crecimiento Lento: $v_t$ aumenta lentamente para cubrir el rango completo de $2M+1$.
• Límites Probabilísticos: Al analizar estas fases utilizando argumentos de tipo martingala e desigualdades de concentración (específicamente aprovechando la desigualdad de Markov inversa y la cota de Hoeffding), los autores derivan límites ajustados para el tiempo $\tau$ requerido para que el conjunto completo sea $\Delta$-aproximado.

2. Aplicación a la SLTH Cuantizada

Los autores extienden los resultados de Cunha et al. [2023] del RSSP continuo al entorno discreto para establecer garantías de SLTH para redes cuantizadas.

• Construcción de la Red: Consideran una red $g$ de $2\ell$ capas, sobreparametrizada y con inicialización aleatoria, donde los pesos se extraen uniformemente de un conjunto discreto $S_\delta$ (precisión $\delta$).
• Estrategia de Poda: El objetivo es podar $g$ para aproximar una red objetivo $\ell$-capa $f$ con pesos en $S_\delta$. El proceso de poda se descompone en la resolución de una colección de instancias independientes de RSSP para pesos y neuronas individuales.
• Propagación del Error: La prueba sigue la estrategia de Pensia et al. [2020], elevando la garantía de aproximación desde un solo peso a una neurona, luego a una capa y, finalmente, a la red completa. Crucialmente, el análisis rastrea la propagación del error a través de las no linealidades (ReLU) y tiene en cuenta la acumulación de errores a través de las capas.

Principales Contribuciones

1. Límites Ajustados para el RSSP Discreto: El artículo establece nuevos y agudos límites probabilísticos para el RSSP discreto. A diferencia de los análisis discretos previos (por ejemplo, Kumar y Natale [2025]) que producían un decaimiento inverso-polinomial de la probabilidad de fallo, este trabajo demuestra una probabilidad de fallo exponencialmente pequeña en el número de bits de precisión.
2. Marco Unificado: El marco propuesto unifica la literatura al demostrar que:
   • Las representaciones aproximadas en el entorno continuo (como en Malach et al. [2020], Pensia et al. [2020]) emergen como un caso límite cuando $\delta \to 0$.
   • Las representaciones exactas en el entorno cuantizado (como en Kumar y Natale [2025]) emergen como un caso límite cuando $\Delta = 0$.
   • El marco gestiona simultáneamente tanto los errores de redondeo (debidos a la cuantización) como los errores de aproximación (debidos a la poda).
3. Mejores Garantías de Sobreparametrización: Los autores derivan que una red aleatoria de profundidad-$2\ell$ con anchura $O(d \log(1/\delta))$ (donde $d$ es la anchura objetivo y $\delta$ es la precisión) puede ser podada para aproximar cualquier red objetivo de profundidad $\ell$ y anchura $d$ con un error $\epsilon$.

Resultados

• Garantías Teóricas: El teorema principal (Teorema 3) establece que con alta probabilidad ($1 - 4d^{2\ell} \exp(-C'n)$), una red cuantizada de $2\ell$ capas con inicialización aleatoria puede ser podada para aproximar cualquier red cuantizada de $\ell$ capas con un error $\epsilon$. La probabilidad de fallo decae exponencialmente con el factor de sobreparametrización.
• Validación Experimental:
  • Experimentos de Suma de Subconjuntos: Los autores validaron empíricamente la teoría del RSSP discreto, observando que la probabilidad de resolver un problema de suma de subconjuntos exacto ($\Delta=0$) se acerca a 1 cuando el número de muestras $n \gtrsim C \log(M)$, con $C \approx 1.5$.
  • Eficiencia de la Poda: En una prueba práctica, los autores identificaron con éxito una subred que aproxima a una ResNet-50 (25 millones de parámetros, precisión FP8) resolviendo las instancias de RSSP requeridas. Este proceso tomó aproximadamente 33 minutos en una sola CPU sin paralelización, demostrando la viabilidad computacional.

Significado y Reivindicaciones

El artículo afirma proporcionar un paso fundamental hacia una teoría cohesiva de los tickets de lotería fuertes que cierra la brecha entre los entornos continuos y cuantizados. Al unificar estas líneas de investigación previamente separadas, el trabajo:

• Agudiza los límites existentes: Mejora la garantía de la probabilidad de fallo de un decaimiento inverso-polinomial a un decaimiento exponencial en el régimen cuantizado.
• Amplía la relevancia práctica: Aborda la realidad de la computación de precisión finita (cuantización) manteniendo al mismo tiempo el rigor teórico de las garantías de aproximación.
• Unifica el campo: Muestra que tanto las representaciones continuas aproximadas como las representaciones cuantizadas exactas son casos especiales de un único marco más general.

Los autores enfatizan que sus resultados respaldan las observaciones empíricas existentes respecto a la existencia de tickets de lotería en redes cuantizadas y proporcionan una base teórica más sólida para el uso de la poda en entornos de precisión finita y recursos restringidos.