Statistical Guarantees in the Search for Less Discriminatory Algorithms

Resumo Técnico: Garantias Estatísticas na Busca por Algoritmos Menos Discriminatórios

Declaração do Problema
A lei antidiscriminação dos EUA, particularmente a doutrina do impacto desproporcional, pode impor responsabilidade civil a empresas que não adotarem uma "alternativa menos discriminatória" (ALD) — uma política de decisão que atinja objetivos comerciais equivalentes enquanto reduz o impacto desproporcional sobre grupos protegidos. Estudos recentes sugerem que essa doutrina obriga as empresas a buscar proativamente tais algoritmos em domínios de alto risco, como emprego, empréstimos e habitação.

No entanto, um desafio central surge da multiplicidade de modelos: o re-treinamento de modelos com diferentes sementes aleatórias ou subconjuntos de dados frequentemente produz preditores com acurácia comparável, mas impactos desproporcionais materialmente diferentes. Embora as empresas possam amostrar múltiplos modelos para encontrar um menos discriminatório, elas não podem re-treinar indefinidamente. O problema central é operacionalizar o padrão legal de "boa-fé": Quando uma busca por ALDs é suficiente para demonstrar que uma busca adicional é improvável de produzir melhorias significativas? Orientações legais e regulatórias atuais carecem de critérios precisos para determinar quando o custo marginal de uma busca adicional supera o benefício marginal na redução da discriminação.

Metodologia
Os autores formalizam a busca por ALD como um problema de parada ótima. Uma empresa treina uma sequência de modelos $h_1, h_2, \dots$ amostrando a partir de um procedimento de treinamento randomizado $\mathcal{A}$ condicionado a um conjunto de dados fixo $D$. O objetivo é interromper o treinamento no tempo $\tau$ quando o benefício marginal esperado de treinar um modelo adicional (em termos de redução do impacto desproporcional) cair abaixo de um limiar de custo $\gamma$ (definido como a razão entre o custo de treinamento e a utilidade de uma melhoria unitária no impacto desproporcional).

O framework aborda duas fontes de incerteza:

1. Distribuição Desconhecida: A distribuição do desempenho do modelo (impacto desproporcional) é desconhecida.
2. Dados Finitos: O impacto desproporcional verdadeiro de um modelo não pode ser observado diretamente; apenas uma estimativa empírica em um conjunto de teste está disponível.

Para resolver isso, o artigo desenvolve algoritmos de parada adaptativa que fornecem garantias de alta probabilidade. A abordagem decompõe o ganho marginal esperado $g(u)$ em dois componentes:

• Probabilidade de Melhoria ($p$): A probabilidade de que uma nova amostra seja estritamente melhor que a melhor atual.
• Melhoria Esperada Condicional (CEI, $\mu$): A magnitude esperada da melhoria dado que uma nova amostra é melhor.

Os autores constroem limites superiores válidos a qualquer momento para essas quantidades:

• Limitando $p$: Eles utilizam uma sequência inovadora que limita superiormente a probabilidade de observar um novo mínimo em uma sequência de variáveis aleatórias i.i.d. (Lema 3.2). Este limite vale para todos os passos de tempo $t$ simultaneamente com probabilidade $1-\delta$.
• Limitando $\mu$: Eles propõem vários limites baseados em suposições distribucionais (Tabela 1). Um limite universal ($\bar{\mu}(u) = u$) não requer suposições. Limites mais apertados são derivados sob suposições como uma cauda esquerda sub-uniforme, uma cauda esquerda exponencial ou um limite inferior conhecido para o impacto desproporcional.
• Correção para Dados Finitos: Para lidar com a lacuna entre o impacto desproporcional empírico e o verdadeiro, os autores introduzem uma suposição de um efeito de seleção não decrescente (Suposição 3.4), implicando que o efeito de regressão à média não aumenta à medida que o desempenho observado melhora.

Principais Contribuições

1. Formalização da Busca por ALD: O artigo formaliza a busca por algoritmos menos discriminatórios como um problema de parada ótima, fornecendo um framework estatístico para certificar a suficiência de uma busca.
2. Algoritmo de Parada Adaptativa (Algoritmo 1): Os autores apresentam um algoritmo que treina modelos adaptativamente e para quando o produto da probabilidade de melhoria limitada superiormente e da CEI limitada superiormente cai abaixo do limiar de custo $\gamma$.
3. Garantias Estatísticas (Teorema 3.5): O principal resultado teórico fornece uma garantia de alta probabilidade ($1-\delta$) de que, quando o algoritmo para, o benefício marginal esperado de um treinamento adicional está de fato abaixo do limiar de custo. Isso permite que as empresas forneçam um "certificado" a tribunais ou reguladores de que uma busca adicional é improvável de ajudar.
4. Limites Baseados em Dados (Algoritmo 2): O artigo estende o framework para estimar o limite da CEI a partir de dados (sob a Suposição 3.6), permitindo limites mais apertados sem pré-especificar parâmetros distribucionais, embora isso exija um limite de união sobre orçamentos de confiança.
5. Validação Empírica: A abordagem é validada em conjuntos de dados reais de crédito (Adult, Folktables) e habitação (HMDA) usando regressão logística, florestas aleatórias e árvores de gradiente aumentado.

Resultados

• Multiplicidade de Modelos: A análise empírica confirma variação significativa no impacto desproporcional entre modelos treinados com procedimentos idênticos, mas sementes diferentes, enquanto a variação na acurácia permanece pequena. Isso apoia a premissa de que o re-treinamento pode produzir modelos menos discriminatórios "de graça" (sem perda de acurácia).
• Desempenho de Parada: Nos experimentos, o algoritmo geralmente para após treinar um número relativamente pequeno de modelos (frequentemente menos de 60). Além desse ponto, os ganhos marginais na redução do impacto desproporcional caem para centésimos de percentual por modelo.
• Comparação com a Verdade Terrena: Quando comparado a um regime de "informação completa" (onde a distribuição verdadeira é conhecida), o tempo de parada do algoritmo ligeiramente "ultrapassa" o tempo de parada ótimo em dezenas de modelos em média. No entanto, os autores observam que a escala logarítmica dos ganhos marginais significa que esse ultrapassamento representa uma diminuição polinomial no valor, e o algoritmo identifica com sucesso o ponto onde os retornos diminuem significativamente.
• Métodos Conscientes da Equidade: O método desempenha-se comparavelmente quando aplicado a modelos treinados com frameworks conscientes da equidade (por exemplo, Fairlearn) versus treinamento "padrão" (vanilla).

Significado e Alegações
O artigo alega fornecer as primeiras ferramentas estatísticas para quantificar e certificar a suficiência de uma busca por ALD sob multiplicidade de modelos. Ao enquadrar a busca como um problema de parada ótima com limites de alta probabilidade, os autores oferecem um mecanismo para empresas demonstrarem esforços de "boa-fé" a reguladores e tribunais sem exigir recursos infinitos.

Os autores são modestos quanto ao escopo de sua contribuição, observando que:

• Seu procedimento é um componente de uma busca mais ampla que inclui considerações qualitativas (por exemplo, seleção de características, suposições de modelo).
• O framework assume uma razão custo-benefício fixa; a determinação desses valores permanece um tema de debate jurídico e econômico em curso.
• Os resultados empíricos são ilustrativos, baseados em conjuntos de dados publicamente disponíveis e classes de modelos específicas, e podem diferir em configurações industriais com conjuntos de dados massivos e pipelines complexos.
• O framework pode ser estendido para outros problemas de parada ótima (por exemplo, ajuste de hiperparâmetros, engenharia de prompts para LLMs), mas o artigo foca especificamente no contexto da ALD.

Em última análise, o trabalho preenche a lacuna entre a doutrina legal que exige uma busca por alternativas menos discriminatórias e as limitações práticas do desenvolvimento de aprendizado de máquina, oferecendo um método estatístico rigoroso para determinar quando uma busca é "suficientemente boa".