Non Convex Optimization for Algorithmic Fairness

111 concepts82 papers1 proposal

When we train a standard machine learning model, we are usually searching a mathematical landscape for a configuration that minimizes error. For many classic objectives—like least-squares regression or logistic regression—this landscape is a beautifully smooth, convex bowl. Convexity is a practitioner's best friend: it guarantees that no matter where you start, walking downhill will always lead you to the single, globally optimal model.

However, when we demand that a model also be fair, we warp this landscape. Enforcing fairness means adding constraints—such as requiring that a model's error rates, predictions, or selection criteria be balanced across different demographic groups. As Kazuto Fukuchi et al. demonstrate in Prediction with Model-Based Neutrality, these constraints frequently introduce non-convexity into the optimization objective. The smooth, predictable bowl collapses into a rugged terrain filled with local minima, deceptive plateaus, and optimization traps.

Why Fairness Breaks Convexity

To understand why fairness constraints destroy convexity, we must look at the mathematical structure of common fairness metrics. A set is convex if a straight line drawn between any two valid points stays entirely within that set. Fairness metrics break this property in three distinct ways:

1. Fractional Ratios and Conditional Probabilities

Metrics like predictive parity or calibration require equalizing ratios across groups (for example, ensuring that the proportion of positive predictions that are actually correct is identical for all demographics). As Xianli Zeng et al. point out in Fair Bayes-Optimal Classifiers Under Predictive Parity, these metrics are defined by non-linear fractional equations. Slicing through a convex loss function with a non-linear fractional constraint warps the feasible region, making it non-convex.

2. Statistical Independence and Covariance

Achieving demographic parity or neutrality requires making the model's predictions statistically independent of a protected attribute. Junpei Komiyama et al. show in Nonconvex Optimization for Regression with Fairness Constraints that limiting the statistical correlation or covariance between predictions and sensitive attributes yields a non-convex feasible space, preventing standard convex solvers from finding exact solutions.

3. Pipeline Combinations

The problem compounds in multi-stage systems, such as hiring funnels or multi-tier screening processes. In Multi Stage Screening: Enforcing Fairness and Maximizing Efficiency in a Pre-Existing Pipeline, Kevin Stangl et al. reveal that the combination or averaging of two individually fair selection policies does not necessarily result in a fair aggregate policy. This lack of closure under convex combinations means the underlying decision space is fundamentally non-convex.

The Danger of Fairness Traps

When an optimization landscape becomes non-convex, standard gradient-based algorithms lose their guarantees. A solver can easily get stuck in a local minimum—a point where any small change makes the model look worse, even though a vastly superior and fairer model exists just over the horizon.

The authors of Auditability and the Landscape of Distance to Multicalibration describe these phenomena as "fairness traps." When optimizing for complex group metrics, gradient descent can encounter regions where the mathematical gradient signals that no further improvement is possible. This leaves the model trapped in a sub-optimal state where both accuracy and equity are compromised. As Mahdi Khalili notes in Mitigating Bias in Machine Learning: A Comprehensive Review and Novel Approaches, getting stuck in these local minima prevents the model from reaching the global optimum where fairness and performance are most effectively balanced.

Escaping the Traps: Algorithmic Solutions

To overcome the challenges of non-convexity, researchers have developed several distinct strategies to reshape or navigate the optimization landscape.

Convex Proxies and Upper Bounds

One common approach is to replace the troublesome non-convex constraints with well-behaved convex approximations. For instance, Muhammad Bilal Zafar et al. in Fairness Beyond Disparate Treatment & Disparate Impact: Learning Classification without Disparate Mistreatment introduce "covariance proxies" to approximate non-convex misclassification rate constraints. Similarly, Hyungrok Do et al. demonstrate in Fair Generalized Linear Models with a Convex Penalty that complex, non-convex fairness criteria can be upper-bounded by a simple convex penalty on the model's linear components, restoring computational tractability and avoiding local minima.

Geometric and Manifold Optimization

Instead of relaxing the constraints, some methods embrace the non-convex geometry directly by optimizing over specialized mathematical structures. In Fast and Efficient MMD-Based Fair PCA via Optimization over Stiefel Manifold, Junghyun Lee et al. address the non-convexity of fair dimensionality reduction by optimizing directly on the Stiefel manifold. This geometric approach avoids the approximation errors introduced by standard rank-relaxations, preserving more data utility while strictly enforcing group fairness.

Post-Processing and Operating Characteristics

Another alternative is to bypass parameter-space optimization entirely. In Fair Classification by Direct Intervention on Operating Characteristics, Kevin Jiang et al. introduce a framework that optimizes directly within the geometric space of a model's operating characteristics (such as true positive and false positive rates). By shifting the optimization from the non-convex parameter space of a neural network to the structured space of operating regions, they achieve near-optimal fairness-accuracy trade-offs without destabilizing model training.

Key Foundational Work

Fairness-aware Learning through Regularization Approach (2011) — contributed 3 concept elements to this direction.
Prediction with Model-Based Neutrality (2013) — contributed 2 concept elements to this direction.
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 2, frozen text):

@misc{lacuna_non_convex_fairness_optimization_ff049362_v2,
  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/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake