🤖 machine learning

A Data-dependent Early Stopping Rule using Rademacher Complexity with L1-norm

Este artigo propõe um arcabouço analítico baseado na complexidade de Rademacher com uma norma L1 para estimar o tempo ideal de parada antecipada para modelos de regressão linear sem exigir treinamento ou suposições probabilísticas, demonstrando sua aplicabilidade a redes neurais não lineares por meio de sondagem linear.

Autores originais: Duy Hoang, Bastien Berret, Olivier Bruneau, Laurent Fribourg

Publicado 2026-08-26

📖 5 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Duy Hoang, Bastien Berret, Olivier Bruneau, Laurent Fribourg

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Treinar um computador para reconhecer padrões, seja identificando um gato em uma fotografia ou prevendo o preço de uma ação, envolve um delicado equilíbrio. A máquina aprende observando exemplos, ajustando suas configurações internas para se adequar aos dados que viu. No entanto, se ela aprender de forma perfeita demais, começa a memorizar as peculiaridades específicas desses exemplos em vez de compreender as regras subjacentes. Isso é um pouco como um estudante que memoriza as respostas de um teste prático, mas falha no exame real porque não consegue aplicar a lógica a novas questões. No mundo da inteligência artificial, essa falha de generalização é um grande obstáculo. Para evitá-la, os pesquisadores frequentemente utilizam uma estratégia chamada "parada precoce" (early stopping), onde interrompem o processo de aprendizado no momento exato — após o modelo ter aprendido as regras, mas antes de começar a memorizar o ruído. O desafio sempre foi saber exatamente quando esse momento chega. Tradicionalmente, encontrar esse ponto ideal exige executar o processo de treinamento várias vezes em conjuntos de dados separados, um método que é lento, computacionalmente caro e que muitas vezes depende de suposições.

Uma equipe de pesquisadores da Université Paris-Saclay propôs uma nova maneira de resolver esse problema de tempo sem a necessidade de tentativas repetidas. Em vez de adivinhar ou executar simulações extras, eles desenvolveram um método matemático que pode prever o ponto de parada ideal diretamente a partir dos próprios dados. A abordagem deles baseia-se em um conceito conhecido como complexidade de Rademacher, que essencialmente mede o quão bem um modelo consegue distinguir entre padrões reais e ruído aleatório. Ao usar essa medida, os pesquisadores criaram uma regra que diz ao computador exatamente quando parar de aprender. O que torna o trabalho deles distinto é que não exige suposições sobre a forma ou distribuição dos dados, um requisito comum em métodos anteriores. Além disso, eles descobriram que utilizar uma forma específica de medir o erro, conhecida como norma L1, proporcionou previsões significativamente mais precisas do que os métodos padrão utilizados na área.

Os pesquisadores focaram seu trabalho inicial em modelos lineares, que são o tipo mais simples de algoritmos de aprendizado de máquina, mas demonstraram que suas descobertas poderiam ser estendidas a redes neurais não lineares complexas. Para testar sua teoria, aplicaram seu método a um problema clássico: distinguir dígitos manuscritos. Em um experimento, treinaram uma rede neural para diferenciar os números três e cinco de um conjunto de dados com mais de dez mil imagens. Usando sua nova regra, o sistema calculou um tempo de parada de 342 etapas. Quando compararam isso ao tempo de parada ideal real, obtido ao executar o processo de treinamento completo e verificar um conjunto de teste separado, o ótimo real foi de 357 etapas. A diferença foi insignificante, e o desempenho do modelo parado no tempo previsto foi quase idêntico ao desempenho do modelo parado no ótimo real. Em outro teste envolvendo os números zero e um, o tempo de parada previsto foi de 415 etapas, enquanto o ótimo real foi de 418 etapas. Em ambos os casos, o modelo treinado usando a regra deles evitou a armadilha do sobreajuste (overfitting) e alcançou a melhor precisão possível para dados não vistos.

O estudo também revelou que o método funciona melhor quando há uma grande quantidade de dados em relação à complexidade do modelo. Quando os pesquisadores testaram cenários com menos pontos de dados, o método tornou-se menos preciso, sugerindo às vezes um tempo de parada de zero, o que indica que o modelo não deve ser treinado de forma alguma. Isso está alinhado com o entendimento de que modelos complexos precisam de dados suficientes para aprender regras gerais. Os pesquisadores também compararam seu novo método com técnicas mais antigas que dependem de diferentes suposições matemáticas sobre os dados. Eles descobriram que sua abordagem, que utiliza a norma L1 para o cálculo, produziu consistentemente tempos de parada muito mais próximos do ótimo real do que os métodos antigos. Isso sugere que a forma como o erro é medido é tão importante quanto a própria regra de parada.

Talvez o mais importante seja que os pesquisadores mostraram que a parada precoce não é apenas um conceito teórico, mas uma necessidade prática em muitos casos. Eles calcularam o que aconteceria se o treinamento fosse permitido continuar indefinidamente. Nos exemplos que estudaram, o desempenho do modelo em novos dados na verdade piorava se o treinamento continuasse além do ponto ideal, confirmando que a parada precoce evita a degradação do modelo. No entanto, eles também observaram que, em alguns cenários específicos e altamente complexos, onde o modelo possui muito mais parâmetros do que dados, continuar o treinamento poderia eventualmente levar a melhores resultados, um fenôso conhecido como "sobreajuste benigno" (benign overfitting). O método deles ajuda a identificar em qual situação o usuário se encontra, permitindo decidir se deve parar cedo ou continuar.

Ao fornecer uma maneira de calcular o tempo de parada ideal sem executar o processo de treinamento completo, este trabalho oferece um caminho mais eficiente para o desenvolvimento de uma inteligência artificial confiável. Ele elimina a necessidade de tentativa e erro, economizando tempo e recursos computacionais. O método é particularmente útil para situações onde os dados são abundantes, mas o poder computacional é limitado, ou onde o custo do treinamento é alto. Embora o estudo atual se concentre em modelos lineares e tipos específicos de dados, os pesquisadores acreditam que seu framework pode ser adaptado para sistemas mais complexos e diferentes tipos de saídas. Seu trabalho oferece uma resposta clara e baseada em dados a uma questão que há muito tempo exige suposições, oferecendo uma ferramenta mais precisa para navegar no equilíbrio entre aprender e memorizar.

Resumo Técnico: Uma Regra de Parada Antecipada Dependente de Dados usando Complexidade de Rademacher com Norma L1

Definição do Problema
O treinamento de redes neurais requer o equilíbrio entre ajustar os dados de treinamento e alcançar um desempenho robusto em entradas não vistas, uma propriedade conhecida como generalizabilidade. Isso é determinado pelo hiato entre o risco empírico ( $L_S$ ) e o risco esperado da população ( $L_D$ ). A perda de generalização ( $L_G$ ) é definida como a diferença entre esses dois. Durante o gradiente descendente (GD), $L_S$ tipicamente diminui enquanto $L_G$ aumenta, criando um compromisso "viés-variância" (bias-variance trade-off). O objetivo da parada antecipada (early stopping) é interromper o treinamento em um tempo ótimo $t^*$ que minimize a soma $L_S + L_G$ .

Classicamente, $t^*$ é estimado numericamente monitorando um conjunto de teste separado ( $S_{test}$ ). Alternativamente, existem abordagens analíticas usando Teoria de Matrizes Aleatórias (RMT), mas elas frequentemente dependem de fortes suposições probabilísticas, como distribuições de dados Gaussianas ou distribções de autovalores específicas (ex: Marchenko–Pastur) da matriz de covariância dos dados. Este artigo aborda a necessidade de uma regra de parada antecipada analítica que não exija conjuntos de teste separados ou suposições de distribuição restritivas.

Metodologia
Os autores propõem um framework analítico baseado na Complexidade de Rademacher (RC) para estimar o tempo de parada ideal sem realizar o gradiente descendente. A metodologia foca em modelos lineares e regressão linear, com extensões para redes não lineares via "linear probing".

Formulação da Norma L1: Diferente de muitas abordagens de RC existentes que utilizam a norma L2, este trabalho expressa a complexidade de Rademacher usando a norma L1. Essa escolha é motivada pelo desejo de eliminar uma constante dependente de dados $M$ (um limite para a perda) do limite de erro de generalização. Ao definir $p=1$ no limite de norma $L_p$ geral, os autores derivam um limite superior para a perda populacional ( $L_D$ ) que depende apenas do vetor de erro empírico e da norma do modelo, evitando a dependência explícita de $M$ .
Dinâmica do Fluxo de Gradiente: O problema é modelado em tempo contínuo usando Fluxo de Gradiente (GF). Os autores analisam a dinâmica do vetor de erro de treinamento $v(t)$ e dos parâmetros do modelo $a(t)$ . O limite superior da perda populacional, denotado por $L^*_D(t)$ , mostra-se em formato de "U", diminuindo inicialmente conforme o erro empírico cai e aumentando posteriormente conforme a norma do modelo cresce.
Critério de Parada Analítico ( $t^+$ ): A principal contribuição é a derivação de um critério dependente de dados $C(s)$ $C (s)$ que garante que $L^*_D(t)$ $L_{D}^{*} (t)$ seja decrescente para todo $t \leq s$ $t \leq s$ .
- Os autores decompõem os autovalores da matriz de covariância dos dados em conjuntos "informativos" (grandes) e "ruído/nuisance" (pequenos).
- Eles definem uma função $\Phi(t)$ envolvendo esses autovalores e a dinâmica do erro.
- O tempo de parada $t^+$ é definido como o supremo do tempo $s$ tal que $\Phi(t) > 0$ para todo $t \in [0, s)$ .
- Matematicamente, $t^+$ é o primeiro momento em que $\Phi(t)$ cruza o zero. É provado que $t^+$ é um limite inferior para a estimativa do tempo ótimo real $t^*$ (ou seja, $t^+ \leq t^*$ ). Sob condições específicas (ex: quando o mínimo real reside no primeiro intervalo de invariância de sinal), $t^+ = t^*$ .
Aproximação: O artigo fornece uma aproximação simples $t^+_{approx} \approx \frac{1}{\lambda_1} \ln \frac{\Gamma(0)}{\Omega(0)}$ , que se assemelha a uma formulação de relação sinal-ruído (SNR) encontrada na literatura de RMT, mas derivada aqui sem suposições probabilísticas.

Principais Contribuições

Estimativa Analítica Livre de Distribuição: O artigo introduz um método para estimar o tempo de parada antecipada ideal analiticamente sem assumir dados Gaussianos ou distribuições de autovalores específicas.
Vantagem da Norma L1: Os autores demonstram teoricamente e numericamente que o uso da norma L1 para a complexidade de Rademacher produz um tempo de parada estimado ( $t^+$ ) significativamente mais próximo do ótimo numérico ( $t_{test}$ ) do que a abordagem baseada na norma L2.
Foco em Subparametrização: O método é especificamente desenhado para o regime subparametrizado ( $m \leq n$ ), onde o "overfitting benigno" (benign overfitting) e a "descida dupla época-a-época" (epoch-wise double descent) são menos prevalentes, tornando a parada antecipada uma estratégia benéfica.
Aplicação de Linear Probing: Embora a teoria seja derivada para modelos lineares, os autores aplicam com sucesso os resultados a redes não lineares (especificamente no MNIST de classificação) congelando as camadas ocultas e treinando apenas a camada de saída (linear probing).

Resultos
Os autores validam seu método através de vários exemplos:

Dados Gaussianos Sintéticos: Em tarefas de classificação binária com diferentes tamanhos de amostra ( $n=512$ e $n=16384$ ), a estimativa analítica $t^+$ igualou exatamente o tempo ótimo real $t^*$ no primeiro caso e forneceu um limite inferior estrito no segundo. A estimativa baseada em L1 foi consistentemente mais próxima do ótimo do conjunto de teste do que a estimativa baseada em L2.
Classificação MNIST (3-5 e 0-1): Usando uma rede ReLU de 4 camadas com linear probing, o método previu com precisão o tempo de parada. Para a classificação 3-5, $t^+ = 342$ comparado ao ótimo numérico $t^* = 357$ e ao ótimo do conjunto de teste $t_{test} = 356$ . Para a classificação 0-1, $t^+ = 415$ coincidiu com $t^* = 415$ e foi próximo de $t_{test} = 418$ .
Parada Benéfica: Em todos os casos testados, a perda no tempo de parada estimado foi menor do que a perda no tempo de treinamento infinito ( $L^*_D(t^+) < L^*_D(\infty)$ ), confirmando que a parada antecipada é benéfica e evita o regime de "overfitting benigno".
Robustez: O método funcionou bem em diferentes distribuições de dados (Gaussian, Uniform, Pareto), com o desempenho melhorando à medida que a razão de amostras para parâmetros ( $n/m$ ) aumentava.

Significância e Alegações
O artigo alega que sua principal significância reside em fornecer uma regra de parada antecipada analítica e dependente de dados que opera sem a necessidade de um conjunto de validação separado ou suposições probabilísticas restritivas sobre a distribuição dos dados. Ao alavancar a complexidade de Rademacher com a norma L1, os autores oferecem uma ferramenta prática para determinar quando interromper o treinamento de modelos lineares (e, via linear probing, certas redes não lineares) para minimizar o erro de generalização. Os autores observam modestamente que, embora o método funcione bem para modelos subparametrizados, não pretende ser aplicado ao regime sobreparametrizado onde ocorre o "overfitting benigno". Eles também identificam direções para trabalhos futuros, incluindo a aplicação direta a modelos totalmente não lineares, saídas vetoriais e o tratamento de ruído aleatório nos dados de entrada.

Mais como este