Multicalibração com 1% de Erro Exige Um Milhão de Amostras de Treinamento, Provam Pesquisadores

Quatro pesquisadores resolveram uma questão teórica aberta no campo de ML justo: exatamente quantos dados são necessários para certificar a multicalibração, a propriedade que exige que as previsões de um modelo sejam igualmente bem calibradas em todos os subgrupos demográficos. A resposta — Θ̃(ε⁻³) amostras, com fatores poliogarítmicos — fornece às equipes de conformidade e engenharia de ML um orçamento concreto de dados pela primeira vez.

O artigo, "The Sample Complexity of Multicalibration," é assinado por Natalie Collina, Jiuyao Lu, Georgy Noarov e Aaron Roth (arXiv, abril de 2026). Trabalhando no cenário padrão de aprendizado em lote — um aprendiz observa n amostras i.i.d. de uma distribuição desconhecida e, em seguida, produz um preditor — eles provam limites superiores e inferiores correspondentes sobre o erro de multicalibração medido pelo Expected Calibration Error (ECE). Especificamente, para qualquer κ > 0 fixo, no regime em que o número de grupos demográficos |G| ≤ ε⁻κ, a complexidade amostral minimax é Θ̃(ε⁻³): esse número de amostras é necessário e suficiente para reduzir o erro de multicalibração populacional abaixo de ε.

O limite inferior se aplica mesmo a preditores aleatorizados, descartando qualquer truque probabilístico para reduzir os requisitos de dados. O limite superior correspondente é alcançado por um preditor aleatorizado derivado por uma redução online-to-batch, convertendo algoritmos de aprendizado online existentes em um procedimento em lote eficiente em amostras.

O resultado operacional mais preciso é a diferença entre multicalibração e calibração marginal. A calibração marginal — que garante a acurácia geral das previsões sem considerar a pertença a subgrupos — exige apenas Θ̃(ε⁻²) amostras. Exigir calibração simultânea em todos os subgrupos protegidos acrescenta um fator ε⁻¹ adicional. Para equipes que projetam pipelines de treinamento em torno de tolerâncias específicas de erro de equidade, essa diferença de expoente se traduz diretamente em decisões sobre o tamanho do conjunto de dados: atingir um erro de multicalibração de ε = 0,01 exige da ordem de 10⁶ amostras, não as 10⁴ que a calibração marginal exige na mesma tolerância.

O artigo identifica um limiar preciso no caso limite κ = 0, em que o número de grupos cresce no máximo como uma constante — nesse ponto, a complexidade amostral colapsa para Θ̃(ε⁻²), igualando a calibração marginal. Isso sugere que, em cenários com poucos grupos, o custo extra que as empresas associam às auditorias de equidade por grupo pode estar superestimado. Os resultados se generalizam para uma métrica de multicalibração Lp ponderada para todo 1 ≤ p ≤ 2, com expoente ótimo de complexidade amostral 3/p, e se estendem a uma classe mais ampla de propriedades elicitáveis, incluindo expectis e quantis de densidade limitada — cobrindo métricas de equidade além da calibração média que reguladores estão começando a referenciar.

Um segundo resultado diz respeito aos cenários em lote e online. Para calibração marginal, o cenário online é estritamente mais difícil do que o em lote. A multicalibração quebra esse padrão: a complexidade amostral em lote e online são equivalentes, com fatores poliogarítmicos. Uma organização que investiu em infraestrutura de multicalibração online obtém garantias no cenário em lote sem custo amostral adicional — e vice-versa.

Para empresas sujeitas às obrigações de sistemas de alto risco do EU AI Act ou a programas internos de auditoria de viés, as implicações práticas são diretas. Até agora, as decisões de aquisição de dados para certificação de equidade eram amplamente heurísticas. O limite Θ̃(ε⁻³) converte uma aspiração de conformidade em uma especificação de engenharia: defina a tolerância aceitável de ECE ε, conte os subgrupos protegidos no escopo e calcule o piso do conjunto de treinamento. Auditores de equidade que citavam a multicalibração como padrão ouro agora podem anexar um requisito específico de tamanho de conjunto de dados a essa citação.

O limite é minimax — caracteriza o pior caso sobre distribuições — portanto, implantações reais com estrutura favorável podem precisar de menos dados. Mas em ambientes regulatórios adversariais, garantias de pior caso são exatamente o que os auditores querem.