Standard machine learning models are built to optimize a single global objective, such as minimizing mean squared error or maximizing cluster inertia. In this traditional paradigm, data points are often treated as independent entities during optimization. However, when we introduce fairness constraints—such as ensuring demographic parity, individual fairness, or envy-freeness—we break this independence.
Fairness is inherently relational. To determine if a model is fair, we must compare how it treats different individuals or demographic groups. This relational requirement introduces global dependencies across the dataset, transforming straightforward optimization problems into computationally grueling bottlenecks. As a result, algorithms that run efficiently in standard settings often suffer from severe scalability issues when fairness constraints are applied.
Understanding why these constraints incur such high computational overhead reveals the core algorithmic challenges of fair machine learning, as well as the clever paradigms researchers use to overcome them.
The Quadratic Trap: Pairwise Comparisons and Envy
Many intuitive definitions of fairness require evaluating pairs of data points. For example, individual fairness dictates that similar individuals should receive similar outcomes, while envy-freeness requires that no user prefers another user's allocation over their own.
In a standard classification or ranking task, evaluating a model's performance on $n$ items takes linear time, $O(n)$. But if we must guarantee that no individual envies any other, we are forced to inspect the relationships between all possible pairs. This immediately shifts the computational complexity from linear to quadratic, $O(n^2)$.
Standard Optimization (Linear):
[Point 1] -> Evaluate Loss
[Point 2] -> Evaluate Loss
[Point 3] -> Evaluate Loss
Fairness-Constrained Optimization (Quadratic):
[Point 1] <---> [Point 2] (Check Envy/Similarity)
[Point 1] <---> [Point 3] (Check Envy/Similarity)
[Point 2] <---> [Point 3] (Check Envy/Similarity)
As Virginie Do et al. demonstrate in the context of personalized recommender systems, this quadratic growth makes exhaustive fairness verification impossible for populations of millions of users. A similar bottleneck occurs in ranking and regression models. Harikrishna Narasimhan et al. note that computing pairwise fairness metrics across all combinations of items results in quadratic growth, making direct optimization on massive datasets intractable without specialized sampling distributions that preserve gradient signals.
This quadratic trap also extends to graph-based models and continuous evaluations. For instance, Maarten Buyl and Tijl De Bie show that enforcing fairness constraints across all possible node pairs in a network leads to an $O(n^2)$ complexity that hinders scalability for large graphs. When optimizing classifiers for local demographic disparities across continuous prediction thresholds, Jinqiu Jin et al. observe a similar quadratic overhead relative to the number of samples, creating a significant barrier for iterative training loops.
The Exponential Curse of Intersectional Groups
While pairwise comparisons create quadratic scaling relative to the number of samples, accounting for multiple demographic attributes creates an exponential explosion relative to the number of protected groups.
Real-world fairness applications rarely deal with a single, binary attribute. Instead, practitioners must account for multiple overlapping categories (e.g., combining race, gender, age, and income brackets) to prevent bias against intersectional groups. If an algorithm relies on enumerating partitions or balancing quotas across every combination of these attributes, the number of constraints grows exponentially.
1 Attribute (Gender: M/F) -> 2 Groups
2 Attributes (+Race: 4 categories) -> 2 x 4 = 8 Groups
3 Attributes (+Age: 5 brackets) -> 2 x 4 = 5 = 40 Groups
...
k Attributes -> Exponential Explosion
In fair clustering, this scaling behavior is particularly destructive. Zhen Dai et al. show that the computational complexity of maintaining exact representation constraints grows exponentially with the number of protected demographic groups, making traditional exact algorithms prohibitive for fine-grained classes.
When selecting a representative subset of items under fairness constraints, algorithms often rely on exhaustive enumeration over group partitions. As Chenyang Xu et al. explain, this dependency makes fair submodular maximization computationally infeasible when the number of protected groups is large. Similarly, Yijun Bian et al. demonstrate that extending group fairness measures to handle multi-valued or intersectional attributes through exhaustive checking incurs costs that render real-world deployment impractical.
Algorithmic Paradigms for Scalable Fairness
To bridge the gap between theoretical fairness guarantees and practical efficiency, researchers have developed several algorithmic paradigms designed to bypass quadratic and exponential bottlenecks.
Data Compression via Coresets
One powerful approach to scaling fair clustering is to reduce the size of the dataset before applying the expensive fairness constraints. This is achieved using fair coresets—small, weighted summaries of the data that mathematically preserve both the geometric structure of the points and their sensitive group proportions.
Instead of running a computationally heavy, fairness-constrained clustering algorithm on millions of raw data points, the algorithm is run on a tiny coreset. Melanie Schmidt et al. utilized this technique to scale fair $k$-means clustering to massive streaming datasets, achieving orders-of-magnitude speedups. By compressing the data into a representative subset that maintains group balances, Lingxiao Huang demonstrated that the quadratic or worse complexity typical of fair clustering can be bypassed, enabling these models to handle large-scale datasets.
Localized Search and Anchor Zones
For individual fairness constraints—where every single point requires a cluster center within a specific radius determined by its local neighborhood density—global optimization is notoriously slow.
To scale this, Mohammadhossein Bateni et al. introduced a local-search strategy constrained by anchor zones. Instead of checking simultaneous constraints across all points globally, the algorithm localizes the search space. This bounds the constraint checks to regional neighborhoods, allowing the method to scale to datasets with hundreds of thousands of observations while maintaining strict individual fairness guarantees.
Post-Processing and Smoothing
Another way to avoid the computational cost of integrating fairness directly into the training process (which often requires slow, iterative minimax optimization or distributionally robust inner loops) is to decouple the two stages. Practitioners can train a standard, highly efficient model first, and then apply a fast post-processing step to enforce fairness.
Felix Petersen et al. implemented this by treating the dataset as a graph and applying Graph Laplacian regularization to post-process predictions. By "smoothing" the outputs so that similar individuals receive similar outcomes, they achieved individual fairness on large-scale models in seconds, completely avoiding the need for computationally grueling fair retraining.
Color-Agnostic Formulations
To combat the exponential curse of multi-group fairness, researchers are designing algorithms whose runtimes are decoupled from the number of demographic attributes.
Qilong Feng developed a "color-agnostic" parameterized approximation algorithm for doubly constrained fair clustering. By structuring the optimization problem so that the runtime depends primarily on the number of clusters ($k$) rather than the number of demographic labels, this approach provides a constant-factor approximation that remains stable even as the complexity of the protected classes grows.