# The empirical duality gap of constrained statistical learning

arXiv: https://arxiv.org/abs/2002.05183 · HTML: https://mlsanity.com/paper/2002.05183/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Feb 2020.

## Built on by (most cited first, 9 of 9)

- [Model-Based Domain Generalization](https://mlsanity.com/paper/2102.11436/) (2021)
- [Towards Principled Disentanglement for Domain Generalization](https://mlsanity.com/paper/2111.13839/) (2021)
- [Constrained Learning with Non-Convex Losses](https://mlsanity.com/paper/2103.05134/) (2021)
- [Adversarial Robustness with Semi-Infinite Constrained Learning](https://mlsanity.com/paper/2110.15767/) (2021)
- [Multi-task Bias-Variance Trade-off Through Functional Constraints](https://mlsanity.com/paper/2210.15573/) (2022)
- [Learnability, Sample Complexity, and Hypothesis Class Complexity for Regression Models](https://mlsanity.com/paper/2303.16091/) (2023)
- [LORE: Lagrangian-Optimized Robust Embeddings for Visual Encoders](https://mlsanity.com/paper/2505.18884/) (2025)
- [Cross-Learning from Scarce Data via Multi-Task Constrained Optimization](https://mlsanity.com/paper/2511.13680/) (2025)
- [Constrained Learning with Universally Learnable Concept Classes](https://mlsanity.com/paper/2608.08414/) (2026)

## Abstract (arXiv)

This paper is concerned with the study of constrained statistical learning problems, the unconstrained version of which are at the core of virtually all of modern information processing. Accounting for constraints, however, is paramount to incorporate prior knowledge and impose desired structural and statistical properties on the solutions. Still, solving constrained statistical problems remains challenging and guarantees scarce, leaving them to be tackled using regularized formulations. Though practical and effective, selecting regularization parameters so as to satisfy requirements is challenging, if at all possible, due to the lack of a straightforward relation between parameters and constraints. In this work, we propose to directly tackle the constrained statistical problem overcoming its infinite dimensionality, unknown distributions, and constraints by leveraging finite dimensional parameterizations, sample averages, and duality theory. Aside from making the problem tractable, these tools allow us to bound the empirical duality gap, i.e., the difference between our approximate tractable solutions and the actual solutions of the original statistical problem. We demonstrate the effectiveness and usefulness of this constrained formulation in a fair learning application.