🤖 machine learning

Do Neural Networks Really Beat the Curse of Dimensionality? A Bit-Complexity View

Este artigo argumenta que, quando a eficiência de aproximação é avaliada através da complexidade de bits computacional em vez da contagem de parâmetros, nenhum método supera fundamentalmente os limites intrínsecos estabelecidos pela entropia métrica, revelando que as vantagens percebidas das redes neurais decorrem frequentemente de diferenças na complexidade da classe de funções em vez de superioridade arquitetônica, e redefinindo a tradicional "maldição da dimensionalidade" como uma "maldição da complexidade de bits" mais fundamental.

Autores originais: Tong Mao, Jinchao Xu

Publicado 2026-08-04

📖 8 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Tong Mao, Jinchao Xu

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

Imagine que você está tentando descrever um objeto complexo e de alta dimensão — como uma galáxia giratória ou um bolo de várias camadas — para um amigo que só consegue entender desenhos simples e planos. No mundo da ciência da computação e da matemática, isso é conhecido como um "problema de aproximação de alta dimensão". Por décadas, cientistas têm lutando contra um inimigo notório chamado "maldição da dimensionalidade". O nome parece assustador, mas a ideia é simples: à medida que o número de variáveis (ou dimensões) em um problema cresce, a quantidade de informação necessária para descrevê-lo com precisão explode. É como tentar pintar um quadro de um objeto de 100 dimensões; o número de pinceladas necessárias parece crescer tão rápido que se torna impossível terminar o trabalho.

Por muito tempo, a maneira padrão de medir o quão bem um computador resolve esses problemas era contando "parâmetros". Pense em parâmetros como os botões, seletores e configurações de uma máquina. Se um método usa menos botões para obter o mesmo resultado, ele é considerado mais eficiente. Recentemente, as redes neurais (os sistemas de IA que alimentam coisas como reconhecimento de imagem e modelos de linguagem) têm sido celebradas porque parecem quebrar essa maldição. Elas parecem resolver problemas de alta dimensão com um número de botões que não explode conforme as dimensões crescem, levando muitos a acreditar que encontraram uma chave mágica para desbloquear os problemas mais complexos da ciência.

No entanto, há uma armadilha que frequentemente é negligenciada no meio do entusiasmo. No mundo real, os computadores não armazenam números com precisão infinita; eles os armazenam como sequências de 0s e 1s, ou "bits". Cada botão nessa máquina precisa ser codificado em um número específico de bits para ser armazenado e calculado. Este artigo faz uma pergunta fundamental: Se pararmos de contar apenas os botões e começarmos a contar os bits reais de informação necessários para armazená-los, as redes neurais ainda parecem mágicas? Os autores, Tong Mao e Jinchao Xu, mergulham fundo nesta questão, usando um conceito chamado "entropia métrica" (que essencialmente mede a quantidade mínima de informação necessária para descrever uma forma ou função) para ver se as redes neurais realmente vencem a maldição ou se estão apenas escondendo o custo de outra forma.

O Grande Assalto da Contagem de Bits

Os autores deste artigo, Tong Mao e Jinchao Xu, decidiram colocar seus chapéus de detetive e olhar para a "maldição da dimensionalidade" de um novo ângulo. Em vez de apenas contar quantos parâmetros (botões) um método usa, eles perguntaram: "Quantos bits de memória são realmente necessários para armazenar esses botões e obter uma boa resposta?"

Para entender a investigação deles, imagine que você está tentando descrever uma colina suave e ondulante para um robô.

O Jeito Antigo (Contando Parâmetros): Você poderia dizer: "Preciso de 100 pontos para descrever esta colina". Se você mudar para um novo método, como uma rede neural, e disser: "Eu só preciso de 10 pontos", você sente que venceu. Você venceu a maldição!
O Novo Jeito (Contando Bits): Mas espere. E se esses 10 pontos forem incrivelmente sensíveis? E se, para descrever a forma da colina com precisão, cada um desses 10 pontos precisar ser armazenado com precisão extrema — como precisar de 1.000 bits para cada ponto? De repente, você não está usando 10 unidades de informação; você está usando 10.000. Enquanto isso, o método "antigo" usava 100 pontos, mas cada um deles só precisava de 10 bits. No final, o método "antigo" usou, na verdade, menos bits no total.

O artigo argumenta que, por muito tempo, fomos enganados pela "contagem de parâmetros". Vimos as redes neurais usando menos botões e assumimos que elas eram mais eficientes. Mas quando os autores mediram a eficiência em termos de bits (a moeda real da computação), a história mudou.

A "Magia" que Não é Tão Mágica

Os pesquisadores analisaram dois tipos principais de "magia" pelas quais as redes neurais eram famosas:

Taxas Independentes de Dimensão: Alguns estudos alegavam que as redes neurais poderiam aproximar certas funções complexas sem que seu desempenho piorasse conforme o número de dimensões aumentava. Parecia que elas tinham encontrado uma maneira de ignorar o tamanho do problema inteiramente.
Superconvergência: Esta é a ideia de que redes neurais profundas (redes com muitas camadas) podem aproximar funções suaves muito mais rápido do que métodos tradicionais como polinômios ou elementos finitos. Parecia que elas estavam ultrapassando a competição em alta velocidade.

A investigação dos autores revelou que essas "superpotências" são, em grande parte, uma ilusão criada pela forma como medimos as coisas.

Quando analisaram a entropia métrica — um termo sofisticado para a complexidade intrínseca da classe de funções sendo aproximada — descobriram que as funções que as redes neurais são boas em aproximar (como as em "espaços de Barron") são, na verdade, apenas mais simples do que as funções com as quais os métodos tradicionais têm dificuldade. Não é que a rede neural seja um artista melhor; é que a pintura que lhe foi pedida para copiar é menos detalhada do que a que o artista tradicional estava tentando copiar. A velocidade "independente da dimensão" não é porque a rede é especial; é porque o alvo era fácil desde o início.

A Armadilha da Rede Profunda

A descoberta mais surpreendente diz respeito às redes neurais profundas. Estas são as redes com muitas camadas que têm recebido todo o destaque. O artigo mostra que, embora as redes profundas possam, de fato, alcançar uma taxa de erro mais rápida quando medidas pelo número de parâmetros (os "botões"), essa velocidade vem com um imposto oculto.

Como as redes profundas são tão complexas e sensíveis, os números dentro delas (os pesos e vieses) precisam ser armazenados com precisão muito maior para evitar erros. Os autores provaram que o número de bits necessários para armazenar esses parâmetros cresce explosivamente à medida que a rede se torna mais profunda.

Pense nisso desta forma: uma rede rasa é como uma ponte de madeira robusta. Ela exige muitas tábuas (parâmetros), mas cada tábua é fácil de medir e armazenar. Uma rede profunda é como uma ponte de vidro. Ela usa menos tábuas, mas cada tábua é tão frágil e precisa que você precisa de um scanner a laser para medi-la. Se você tentar construir a ponte de vidro com uma fita métrica comum (precisão finita), ela desmorona.

O artigo demonstra que, quando contamos o total de bits necessários para construir essa ponte de vidro, a "eficiência" desaparece. Os bits extras necessários para manter a rede profunda estável cancelam a vantagem de ter menos parâmetros. Na verdade, para muitos problemas padrão, as redes profundas acabam exigindo tantos bits, ou até mais, do que métodos clássicos como polinômios ou elementos finitos.

O Veredito: É um Pouco de Maldição

Então, as redes neurais vencem a maldição da dimensionalidade? Segundo Mao e Xu, a resposta é não, pelo menos não da maneira que pensávamos.

A "maldição" não é realmente sobre o número de dimensões. É sobre a complexidade de bits. O limite fundamental de quão bem você pode aproximar uma função é determinado por quanta informação (bits) essa função realmente contém. Isso é governado pela "entropia métrica".

Se uma função é complexa, ela requer muitos bits para ser descrita, não importa qual ferramenta você use.
Se uma função é simples, ela requer menos bits.

As redes neurais não mudam as regras do jogo; elas apenas mudam a forma como contamos a pontuação. Quando olhamos para o jogo através da lente dos bits, em vez dos parâmetros, a "superioridade" das redes neurais muitas vezes desaparece. As vantagens aparentes, como taxas independentes de dimensão ou superconvergência, são frequentemente apenas porque as redes neurais estão sendo testadas em classes de funções que são inerentemente menos complexas (possuem menor entropia métrica) do que aquelas em que os métodos tradicionais são testados.

Por Que Isso Importa

Este artigo não diz que as redes neurais são inúteis. Ele diz que precisamos ser mais inteligentes sobre como as avaliamos. No mundo real, os computadores têm memória finita. Eles não podem armazenar precisão infinita. Se um método parece ótimo no papel porque usa menos parâmetros, mas exige uma quantidade massiva de memória para armazenar esses parâmetros com precisão, ele pode não ser a melhor escolha para uma aplicação real.

Os autores sugerem que a "maldição da dimensionalidade" é, na verdade, uma "maldição da complexidade de bits". O limite real não é quantos parâmetros você tem, mas quantos bits você precisa para descrever o problema. Ao mudar nosso foco de contar botões para contar bits, obtemos uma imagem muito mais clara e realista do que essas ferramentas poderosas podem e não podem fazer. É um lembrete de que, no mundo da matemática de alta dimensão, o diabo está sempre nos detalhes — e esses detalhes são medidos em bits.

Resumo Técnico: As Redes Neurais Realmente Vencem a Maldição da Dimensionalidade? Uma Visão de Complexidade de Bits

1. Enunciado do Problema

A aproximação de alta dimensão é um desafio central na computação científica e no aprendizado de máquina, tradicionalmente dificultada pela "maldição da dimensionalidade". Na teoria da aproximação clássica, o número de graus de liberdade ( $N$ ) necessário para atingir uma precisão prescrita frequentemente cresce exponencialmente com a dimensão ( $d$ ). Por exemplo, em espaços de Sobolev $H^r([0,1]^d)$ , a taxa de convergência ótima para métodos clássicos (polinômios, elementos finitos) escala como $O(N^{-r/d})$ , onde o expoente se deteriora à medida que $d$ aumenta.

A literatura recente sugere que redes neurais (tanto rasas quanto profundas) podem superar essa maldição, exibindo taxas independentes da dimensão ou "superconvergência" (por exemplo, alcançando $O(N^{-2r/d})$ para redes ReLU profundas em espaços de Sobolev). No entanto, esses resultados são tipicamente medidos em termos do número de parâmetros ( $N$ ).

O artigo identifica uma lacuna crítica: a computação prática opera sob precisão finita. Os parâmetros devem ser codificados usando um número finito de bits. Os autores argumentam que medir a eficiência apenas pelo contagem de parâmetros é enganoso porque ignora a complexidade de bits necessária para representar esses parâmetros com precisão suficiente. O problema central é reavaliar as taxas de aproximação através da lente da complexidade de bits computacional e da entropia métrica para determinar se as redes neurais possuem realmente uma vantagem intrínseca sobre os métodos clássicos.

2. Metodologia

Os autores desenvolvem um framework de aproximação unificado baseado em codificação binária e entropia métrica.

2.1 Entropia Métrica e Complexidade de Bits

A ferramenta teórica central é a entropia métrica (ou número de entropia dyádica) $\epsilon_m(K)_X$ , definida como o raio mínimo $\epsilon$ tal que um conjunto compacto $K$ em um espaço de Banach $X$ pode ser coberto por $2^m$ bolas de raio $\epsilon$ .

Proposição 2 estabelece que $\epsilon_m(K)_X$ é quantitativamente equivalente ao erro de aproximação ótimo alcançável com $m$ bits. Assim, a entropia métrica caracteriza o conteúdo de informação intrínseco (complexidade de bits) de uma classe de funções.
O artigo distingue entre taxas baseadas em parâmetros (convergência em termos de $N$ ) e taxas baseadas em bits (convergência em termos de $N_b$ , o total de bits).

2.2 Análise de Codificação

A metodologia envolve a análise de como as aproximações clássicas e de redes neurais se traduzem em representações de bits finitos:

Representação de Parâmetros: Um método de aproximação mapeia uma função $f$ para um conjunto de parâmetros $\Theta \in \mathbb{R}^N$ .
Quantização: Os parâmetros são quantizados para $\tau$ bits cada, resultando em um orçamento total de bits $N_b = N\tau$ .
Análise de Estabilidade: Os autores analisam a constante de Lipschitz (sensibilidade) do mapa de reconstrução $\tilde{S}_N$ . Se a reconstrução for altamente sensível a perturbações nos parâmetros, um $\tau$ maior (mais bits por parâmetro) é necessário para manter uma tolerância de erro específica.
Limites Inferiores: Usando o Lema 2, o artigo deriva limites inferiores para erros de aproximação baseados na diferença entre a entropia métrica da classe de funções alvo e a entropia métrica da classe de aproximação.

3. Contribuições Principais e Resultados

3.1 Métodos Clássicos (Polinômios, FEM, Grades Esparsas)

O artigo analisa métodos clássicos (aproximação polinomial, elementos finitos, grades esparsas) sob o framework de complexidade de bits.

Resultado: Para métodos clássicos aproximando espaços de Sobolev $H^r$ , a taxa baseada em parâmetros é $O(N^{-r/d})$ . Quando convertida para taxas baseadas em bits, a convergência torna-se $O((N_b / \log N_b)^{-r/d})$ .
Subotimalidade: Os autores mostram que esses métodos são geralmente subotimizantes em relação aos limites de entropia métrica intrínsecos das classes de funções. A entropia métrica de $H^r$ decai como $m^{-r/d}$ , mas os métodos clássicos frequentemente falham em atingir essa taxa quando as restrições de bits são consideradas, particularmente devido ao overhead logarítmico na codificação dos parâmetros.

3.2 Redes Neurais: Rasas e Profundas

O artigo reavalia o desempenho de redes neurais (ReLU e ReLU $^k$ ) em espaços de Barron e espaços de Sobolev.

Redes Rasas em Espaços de Barron:
- Redes rasas alcançam taxas baseadas em parâmetros de $O(N^{-1/2 - (2k+1)/2d})$ em espaços de Barron.
- Visão de Complexidade de Bits: Ao considerar a codificação de bits, a taxa permanece comparável à entropia métrica do espaço de Barron. A aparência de "independência de dimensão" é atribuída à baixa entropia métrica do próprio espaço de Barron, não a uma superioridade arquitetônica. A classe alvo é simplesmente menos complexa que o espaço de Sobolev.
Redes Profundas e Superconvergência:
- Foi demonstrado que redes ReLU profundas podem alcançar taxas de "superconvergência" de $O(N^{-2r/d})$ em espaços de Sobolev, aparentemente dobrando o expoente em comparação com métodos clássicos.
- Visão de Complexidade de Bits: Os autores demonstram que essa melhoria é um artefato da contagem de parâmetros. O Lema 1 prova que o mapa de reconstrução para redes profundas exibe sensibilidade exponencial a perturbações de parâmetros (a constante de Lipschitz cresce como $(n+1)(W+1)^{n+1}M^{n+1}$ ).
- Para manter a mesma precisão, a precisão necessária (bits por parâmetro) cresce polinomialmente com o tamanho da rede. Consequentemente, a taxa baseada em bits para redes profundas degrada-se para $O(N_b^{-2r/3d})$ (ou similar, dependendo das constantes), o que não ultrapassa a taxa clássica de $O(N_b^{-r/d})$ . A "superconvergência" é compensada pelo enorme custo de bits necessário para uma representação estável de precisão finita.

3.3 Limites Inferiores e Otimalidade

Usando o framework de entropia métrica, o artigo estabelece limites inferiores fundamentais:

Nenhum método pode fundamentalmente exceder a ordem de aproximação ditada pela entropia métrica da classe de funções alvo.
Muitas vantagens aparentes das redes neurais (independência de dimensão, superconvergência) derivam da análise de classes de funções com menor complexidade intrínseca (ex: espaços de Barron) ou de ignorar o custo de bits da estabilidade (no caso de redes profundas).

4. Significância e Conclusões

O artigo conclui que a "maldição da dimensionalidade" não é uma propriedade intrínseca da aproximação de alta dimensão, mas sim uma maldição da complexidade de bits governada pela entropia métrica.

Reenquadramento da Maldição: A limitação fundamental não é a dimensão $d$ em si, mas a entropia métrica da classe de funções sendo aproximada. Se uma classe de funções possui baixa entropia métrica (como os espaços de Barron), ela pode ser aproximada eficientemente independentemente da dimensão.
Limitações das Redes Neurais: As redes neurais não possuem uma vantagem arquitetônica intrínseca que permita contornar os limites impostos pela entropia métrica.
- Seu sucesso em classes específicas (Barron) deve-se à baixa complexidade dessas classes.
- Sua "superconvergência" em redes profundas é uma ilusão de contagem de parâmetros que desaparece quando as restrições de precisão finita (complexidade de bits) são aplicadas.
Implicação Prática: Na computação prática de precisão finita, o custo de bits para representar os parâmetros é o verdadeiro gargalo. Métodos que parecem superiores em contagem de parâmetros podem ser inferiores em complexidade de bits devido à instabilidade.

Os autores afirmam que uma visão unificada baseada em entropia métrica e complexidade de bits fornece um benchmark mais preciso e realista para avaliar métodos de aproximação, revelando que os métodos clássicos tradicionais e as redes neurais estão sujeitos aos mesmos limites fundamentais de teoria da informação.