Resumo Técnico: Um Framework Unificado para Bilhetes de Loteria Fortes Quantizados e Contínuos

Declaração do Problema

A Hipótese do Bilhete de Loteria Forte (SLTH) postula que redes neurais suficientemente sobreparametrizadas e inicializadas aleatoriamente contêm sub-redes esparsas capazes de igualar o desempenho de uma rede menor treinada sem qualquer atualização de pesos. Embora os fundamentos teóricos da SLTH dependam fortemente do Problema da Soma de Subconjuntos Aleatórios (RSSP), a literatura existente tem se limitado amplamente ao cenário contínuo (pesos de precisão arbitrária).

Extensões recentes para o cenário quantizado, onde os pesos são amostrados de conjuntos discretos, enfrentaram limitações significativas. Trabalhos anteriores neste domínio (por exemplo, Diffenderfer e Kailkhura [2021], Sreenivasan et al. [2022], Kumar e Natale [2025]) ou restringiram as redes alvo a pesos contínuos enquanto aproximavam com redes binárias, ou forneceram garantias para representações exatas em configurações quantizadas com apenas um decaimento polinomial inverso na probabilidade de falha. Além disso, essas abordagens trataram representações aproximadas (contínuas) e representações exatas (quantizadas) como linhas de investigação distintas, carecendo de um framework teórico unificado que considere simultaneamente erros de arredondamento e de aproximação.

Metodologia

Os autores abordam essas lacunas desenvolvendo uma análise rigorosa do RSSP no cenário discreto e aplicando-a à SLTH quantizada.

1. Problema da Soma de Subconjuntos Aleatórios Discreto (RSSP)

A principal contribuição matemática é uma nova análise do RSSP discreto. Os autores definem o problema onde variáveis aleatórias $X_1, \dots, X_n$ são amostradas uniformemente de um conjunto discreto $\{-M, \dots, M\}$, e o objetivo é encontrar um subconjunto cuja soma seja um alvo $z$ dentro de uma tolerância $\Delta$.

• Relação de Recorrência: A análise utiliza uma relação de recorrência para a função indicadora $f_t(z)$, representando se um alvo $z$ é $\Delta$-aproximado no tempo $t$.
• Análise de Crescimento de Volume: Os autores rastreiam o crescimento do "volume" $v_t$, definido como o número de valores distintos no intervalo $\{-M, \dots, M\}$ que podem ser $\Delta$-aproximados. Eles provam que $v_t$ cresce em duas fases distintas:
  1. Crescimento Rápido: $v_t$ atinge rapidamente $M+1$.
  2. Crescimento Lento: $v_t$ sobe lentamente para cobrir todo o intervalo $2M+1$.
• Limites Probabilísticos: Ao analisar essas fases usando argumentos do tipo martingala e desigualdades de concentração (especificamente aproveitando a desigualdade de Markov reversa e a desigualdade de Hoeffding), os autores derivam limites estreitos para o tempo $\tau$ necessário para que todo o conjunto seja $\Delta$-aproximado.

2. Aplicação à SLTH Quantizada

Os autores estendem os resultados de Cunha et al. [2023] do RSSP contínuo para o cenário discreto para estabelecer garantias de SLTH para redes quantizadas.

• Construção da Rede: Eles consideram uma rede sobreparametrizada e inicializada aleatoriamente $g$ com $2\ell$ camadas, onde os pesos são extraídos uniformemente de um conjunto discreto $S_\delta$ (precisão $\delta$).
• Estratégia de Poda (Pruning): O objetivo é podar $g$ para aproximar uma rede alvo de $\ell$ camadas $f$ com pesos em $S_\delta$. O processo de poda é decomposto na resolução de uma coleção de instâncias independentes de RSSP para pesos e neurônios individuais.
• Propagação de Erro: A prova segue a estratégia de Pensia et al. [2020], elevando a garantia de aproximação de um único peso para um neurônio, depois para uma camada e, finalmente, para toda a rede. Crucialmente, a análise rastreia a propagação do erro através de não-linearidades (ReLU) e contabiliza o acúmulo de erros entre as camadas.

Principais Contribuições

1. Limites Estreitos para o RSSP Discreto: O artigo estabelece novos limites probabilísticos agudos para o RSSP discreto. Diferente de análises discretas anteriores (por exemplo, Kumar e Natale [2025]) que resultavam em decaimento polinomial inverso da probabilidade de falha, este trabalho prova uma probabilidade de falha exponencialmente pequena no número de bits de precisão.
2. Framework Unificado: O framework proposto unifica a literatura ao demonstrar que:
   • Representações aproximadas no cenário contínuo (como em Malach et al. [2020], Pensia et al. [2020]) emergem como um caso limite quando a precisão $\delta \to 0$.
   • Representações exatas no cenário quantizado (como em Kumar e Natale [2025]) emergem como um caso limite quando a tolerância $\Delta = 0$.
   • O framework lida simultaneamente com erros de arredondamento (devido à quantização) e erros de aproximação (devido à poda).
3. Melhores Garantias de Sobreparametrização: Os autores derivam que uma rede aleatória de profundidade-$2\ell$ com largura $O(d \log(1/\delta))$ (onde $d$ é a largura alvo e $\delta$ é a precisão) pode ser podada para aproximar qualquer rede alvo de profundidade $\ell$ e largura $d$.

Resultados

• Garantias Teóricas: O teorema principal (Teorema 3) afirma que, com alta probabilidade ($1 - 4d^{2\ell} \exp(-C'n)$), uma rede quantizada de $2\ell$ camadas inicializada aleatoriamente pode ser podada para aproximar qualquer rede quantizada de $\ell$ camadas com erro $\epsilon$. A probabilidade de falha decai exponencialmente com o fator de sobreparametrização.
• Validação Experimental:
  • Experimentos de Soma de Subconjuntos: Os autores validaram empiricamente a teoria do RSSP discreto, observando que a probabilidade de resolver um problema de soma de subconjuntos exato ($\Delta=0$) aproxima-se de 1 quando o número de amostras $n \gtrsim C \log(M)$, com $C \approx 1.5$.
  • Eficiência de Poda: Em um teste prático, os autores identificaram com sucesso uma sub-rede que aproxima uma ResNet-50 (25 milhões de parâmetros, precisão FP8) resolvendo as instâncias de RSSP necessárias. Este processo levou aproximadamente 33 minutos em uma única CPU sem paralelização, demonstrando a viabilidade computacional.

Significância e Alegações

O artigo alega fornecer um passo fundamental em direção a uma teoria coesa de bilhetes de loteria fortes que une a lacuna entre os cenários contínuos e quantizados. Ao unificar essas linhas de pesquisa anteriormente separadas, o trabalho:

• Refina os limites existentes: Melhora a garantia de probabilidade de falha de decaimento polinomial inverso para decaimento exponencial no regime quantizado.
• Amplia a relevância prática: Aborda a realidade da computação de precisão finita (quantização) mantendo o rigor teórico das garantias de aproximação.
• Unifica o campo: Mostra que tanto as representações contínuas aproximadas quanto as representações quantizadas exatas são casos especiais de um único framework mais geral.

Os autores enfatizam que seus resultados apoiam as observações empíricas existentes sobre a existência de bilhetes de loteria em redes quantizadas e fornecem uma base teórica mais forte para o uso de poda em ambientes de precisão finita e recursos restritos.