Global Optimization for Non-Convex Fairness Constraints

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 2181 papers214 conceptsfrozen 2026-10-04

In the pursuit of algorithmic equity, researchers have discovered a fundamental mathematical hurdle: fairness is rarely "convex." While standard machine learning often relies on smooth, bowl-shaped loss landscapes where every downhill step leads toward a global optimum, adding fairness constraints warps this geometry. This research direction focuses on understanding and navigating the rugged, non-convex landscapes created when we demand that models be both accurate and just.

The Geometry of Fairness

Most machine learning models are trained by minimizing a loss function. When we add a fairness constraint—such as requiring that a model’s error rate be identical for different demographic groups—we are essentially carving out a "feasible region" within the model's parameter space.

As Kazuto Fukuchi, Jun Sakuma, and Toshihiro Kamishima demonstrate in Prediction with Model-Based Neutrality, these constraints often introduce non-convexity. Instead of a single optimal solution, the landscape becomes fractured. A model might find a "local optimum" that looks fair and accurate compared to its immediate neighbors but is significantly worse than a global solution hidden behind a mathematical ridge.

This problem is particularly acute for metrics defined by ratios, such as predictive parity. Edgar Dobriban and Kevin Jiang note in Fair Classification by Direct Intervention on Operating Characteristics that these ratio-based rules make it difficult to find globally optimal fair solutions using standard linear techniques.

The Trap of Local Optima

When an optimization problem is non-convex, standard gradient-based tools—the workhorses of modern AI—can get "stuck." In the context of fairness, getting stuck in a local minimum isn't just a technical failure; it’s a social one. It means the model has settled for a sub-optimal balance between accuracy and equity.

Jakub Marecek and Quan Zhou argue in Fairness in Forecasting of Observations of Linear Dynamical Systems that local search techniques are insufficient for complex fairness constraints. They propose using global optimization techniques, such as Semidefinite Programming (SDP) relaxations, to ensure the model identifies the true mathematical balance between performance and social equity.

Similarly, YooJung Choi and Golnoosh Farnadi highlight in Learning Fair Naive Bayes Classifiers by Discovering and Eliminating Discrimination Patterns that while signomial programming can eliminate millions of unfair outcomes, it typically converges to local optima. This leaves a "fairness gap" where the most accurate possible fair model remains undiscovered.

Predictive Multiplicity and Arbitrariness

Non-convexity doesn't just make models harder to train; it makes their decisions feel arbitrary. Because a non-convex landscape can have multiple disjoint regions of "good" solutions, two models trained on the same data with the same fairness constraints might reach identical accuracy and fairness scores but make wildly different predictions for the same individual.

Carol Xuan Long and Flavio Calmon explore this in Arbitrariness Lies Beyond the Fairness-Accuracy Frontier. They show that fairness constraints often expand the set of near-optimal models, leading to "predictive multiplicity." This suggests that without global coordination or specific ensemble strategies, the "fair" model we choose is essentially a roll of the dice.

Escaping the Trade-off Dogma

The difficulty of non-convex optimization has fueled the belief in a strict "price of fairness"—the idea that any gain in equity must come at the cost of accuracy. However, recent work suggests this trade-off is often an artifact of poor optimization rather than a mathematical necessity.

In Search-based Automatic Repair for Fairness and Accuracy in Decision-making Software, Jie Zhang and Mark Harman use search-based mutations to perturb models out of their local optima. They found that in 61% of cases, they could improve both fairness and accuracy simultaneously. This "win-win" is only possible because the original models were trapped in sub-optimal regions of the non-convex space.

New Frontiers in Robust Fairness

As the field moves toward more complex architectures, the gap between convex theory and non-convex practice grows. Jacob Abernethy and Jie Zhang point out in Active Sampling for Min-Max Fairness that while theoretical guarantees for min-max fairness exist for convex losses, they remain unproven for the non-convex neural networks used in production today.

To bridge this gap, researchers are developing more stable algorithmic frameworks:

By treating fairness not just as a constraint to be added, but as a fundamental change to the optimization landscape, this research direction provides the tools to move beyond local heuristics toward provably equitable machine learning.

Papers in this version

Showing 60 of 181 papers.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 86 papers
  2. Version 1 · 2026-10-04 · 181 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_non_convex_fairness_optimization_ff049362,
  title = {non-convex fairness optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/non-convex-fairness-optimization/rdr_ff049362248a4ca18de9a3b2953e92e6},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_global_optimization_for_non_convex_fairn_ff049362_v1,
  title = {Global Optimization for Non-Convex Fairness Constraints},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/global-optimization-for-non-convex-fairness-constraints/rdr_ff049362248a4ca18de9a3b2953e92e6/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}