Statistical Guarantees in the Search for Less Discriminatory Algorithms

Resumen Técnico: Garantías Estadísticas en la Búsqueda de Algoritmos Menos Discriminatorios

Enunciado del Problema
La legislación antidiscriminación de EE. UU., particularmente la doctrina del impacto desproporcionado, puede imponer responsabilidad a las empresas que no adopten una "alternativa menos discriminatoria" (ALD)—una política de decisión que logre objetivos comerciales equivalentes mientras reduce el impacto desproporcionado sobre grupos protegidos. Investigaciones recientes sugieren que esta doctrina obliga a las empresas a buscar proactivamente dichos algoritmos en dominios de alto riesgo como el empleo, los préstamos y la vivienda.

Sin embargo, surge un desafío central a partir de la multiplicidad de modelos: reentrenar modelos con diferentes semillas aleatorias o subconjuntos de datos a menudo produce predictores con precisión comparable pero impactos desproporcionados materialmente diferentes. Si bien las empresas pueden muestrear múltiples modelos para encontrar uno menos discriminatorio, no pueden reentrenar indefinidamente. El problema central es operacionalizar el estándar legal de "buena fe": ¿Cuándo es suficiente una búsqueda de ALDs para demostrar que una búsqueda adicional es poco probable que produzca mejoras significativas? La orientación legal y regulatoria actual carece de criterios precisos para determinar cuándo el costo marginal de una búsqueda adicional supera el beneficio marginal en la reducción de la discriminación.

Metodología
Los autores formalizan la búsqueda de ALD como un problema de parada óptima. Una empresa entrena una secuencia de modelos $h_1, h_2, \dots$ muestreando a partir de un procedimiento de entrenamiento aleatorizado $\mathcal{A}$ condicionado a un conjunto de datos fijo $D$. El objetivo es detener el entrenamiento en el tiempo $\tau$ cuando el beneficio marginal esperado de entrenar un modelo adicional (en términos de reducción del impacto desproporcionado) cae por debajo de un umbral de costo $\gamma$ (definido como la relación entre el costo de entrenamiento y la utilidad de una mejora unitaria en el impacto desproporcionado).

El marco aborda dos fuentes de incertidumbre:

1. Distribución Desconocida: La distribución del rendimiento del modelo (impacto desproporcionado) es desconocida.
2. Datos Finitos: El impacto desproporcionado real de un modelo no puede observarse directamente; solo está disponible una estimación empírica en un conjunto de prueba.

Para resolver esto, el artículo desarrolla algoritmos de parada adaptativa que proporcionan garantías de alta probabilidad. El enfoque descompone la ganancia marginal esperada $g(u)$ en dos componentes:

• Probabilidad de Mejora ($p$): La probabilidad de que una nueva muestra sea estrictamente mejor que la mejor actual.
• Mejora Esperada Condicional (CEI, $\mu$): La magnitud esperada de mejora dado que una nueva muestra es mejor.

Los autores construyen límites superiores válidos en cualquier momento para estas cantidades:

• Acotación de $p$: Utilizan una secuencia novedosa que acota superiormente la probabilidad de observar un nuevo mínimo en una secuencia de variables aleatorias i.i.d. (Lema 3.2). Este límite se cumple para todos los pasos de tiempo $t$ simultáneamente con probabilidad $1-\delta$.
• Acotación de $\mu$: Proponen varios límites basados en supuestos distribucionales (Tabla 1). Un límite universal ($\bar{\mu}(u) = u$) no requiere supuestos. Límites más ajustados se derivan bajo supuestos como una cola izquierda sub-uniforme, una cola izquierda exponencial o un límite inferior conocido sobre el impacto desproporcionado.
• Corrección por Datos Finitos: Para manejar la brecha entre el impacto desproporcionado empírico y el real, los autores introducen un supuesto de un efecto de selección no decreciente (Supuesto 3.4), lo que implica que el efecto de regresión a la media no aumenta a medida que mejora el rendimiento observado.

Contribuciones Clave

1. Formalización de la Búsqueda de ALD: El artículo formaliza la búsqueda de algoritmos menos discriminatorios como un problema de parada óptima, proporcionando un marco estadístico para certificar la suficiencia de una búsqueda.
2. Algoritmo de Parada Adaptativa (Algoritmo 1): Los autores presentan un algoritmo que entrena modelos de forma adaptativa y se detiene cuando el producto de la probabilidad de mejora acotada superiormente y la CEI acotada superiormente cae por debajo del umbral de costo $\gamma$.
3. Garantías Estadísticas (Teorema 3.5): El resultado teórico principal proporciona una garantía de alta probabilidad ($1-\delta$) de que, cuando el algoritmo se detiene, el beneficio marginal esperado de un entrenamiento adicional está efectivamente por debajo del umbral de costo. Esto permite a las empresas proporcionar un "certificado" a tribunales o reguladores de que una búsqueda adicional es poco probable que ayude.
4. Límites Basados en Datos (Algoritmo 2): El artículo extiende el marco para estimar el límite de CEI a partir de datos (bajo el Supuesto 3.6), permitiendo límites más ajustados sin preespecificar parámetros distribucionales, aunque esto requiere un límite de unión sobre presupuestos de confianza.
5. Validación Empírica: El enfoque se valida en conjuntos de datos reales de crédito (Adult, Folktables) y vivienda (HMDA) utilizando regresión logística, bosques aleatorios y árboles impulsados por gradiente.

Resultados

• Multiplicidad de Modelos: El análisis empírico confirma una variación significativa en el impacto desproporcionado entre modelos entrenados con procedimientos idénticos pero diferentes semillas, mientras que la variación en la precisión permanece pequeña. Esto respalda la premisa de que el reentrenamiento puede producir modelos menos discriminatorios "gratis" (sin pérdida de precisión).
• Rendimiento de Parada: En los experimentos, el algoritmo generalmente se detiene después de entrenar un número relativamente pequeño de modelos (a menudo menos de 60). Más allá de este punto, las ganancias marginales en la reducción del impacto desproporcionado caen a centésimas de porcentaje por modelo.
• Comparación con la Verdad Terrenal: Cuando se compara con un régimen de "información completa" (donde se conoce la distribución real), el tiempo de parada del algoritmo "sobrepasa" ligeramente el tiempo de parada óptimo en decenas de modelos en promedio. Sin embargo, los autores señalan que la escala logarítmica de las ganancias marginales significa que este sobrepaso representa una disminución polinómica en el valor, y el algoritmo identifica con éxito el punto donde los rendimientos disminuyen significativamente.
• Métodos Conscientes de la Equidad: El método funciona de manera comparable cuando se aplica a modelos entrenados con marcos conscientes de la equidad (por ejemplo, Fairlearn) en comparación con el entrenamiento "estándar" o "vanilla".

Significado y Afirmaciones
El artículo afirma proporcionar las primeras herramientas estadísticas para cuantificar y certificar la suficiencia de una búsqueda de ALD bajo multiplicidad de modelos. Al enmarcar la búsqueda como un problema de parada óptima con límites de alta probabilidad, los autores ofrecen un mecanismo para que las empresas demuestren esfuerzos de "buena fe" a reguladores y tribunales sin requerir recursos infinitos.

Los autores son modestos sobre el alcance de su contribución, señalando que:

• Su procedimiento es un componente de una búsqueda más amplia que incluye consideraciones cualitativas (por ejemplo, selección de características, supuestos del modelo).
• El marco asume una relación costo-beneficio fija; determinar estos valores sigue siendo objeto de debate legal y económico en curso.
• Los resultados empíricos son ilustrativos, basados en conjuntos de datos de acceso público y clases de modelos específicas, y pueden diferir en entornos industriales con conjuntos de datos masivos y pipelines complejos.
• El marco puede extenderse a otros problemas de parada óptima (por ejemplo, ajuste de hiperparámetros, ingeniería de prompts para LLM), pero el artículo se centra específicamente en el contexto de la ALD.

En última instancia, este trabajo cierra la brecha entre la doctrina legal que requiere una búsqueda de alternativas menos discriminatorias y las limitaciones prácticas del desarrollo de aprendizaje automático, ofreciendo un método estadístico riguroso para determinar cuándo una búsqueda es "suficiente".