# Near-Optimal Solutions of Constrained Learning Problems

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 42 references that are in the map.
- First posted on arXiv 18 Mar 2024.

## Builds on (most cited first, 21 of 21)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Counterfactual Fairness](https://mlsanity.com/paper/1703.06856/) (2017)
- [Deep Reinforcement Learning for Autonomous Driving: A Survey](https://mlsanity.com/paper/2002.00444/) (2020)
- [A Reductions Approach to Fair Classification](https://mlsanity.com/paper/1803.02453/) (2018)
- [Preventing Fairness Gerrymandering: Auditing and Learning for Subgroup Fairness](https://mlsanity.com/paper/1711.05144/) (2017)
- [Theoretical insights into the optimization landscape of over-parameterized shallow neural networks](https://mlsanity.com/paper/1707.04926/) (2017)
- [Optimization with Non-Differentiable Constraints with Applications to Fairness, Recall, Churn, and Other Goals](https://mlsanity.com/paper/1809.04198/) (2018)
- [The Complexity of Constrained Min-Max Optimization](https://mlsanity.com/paper/2009.09623/) (2020)
- [Learning One-hidden-layer Neural Networks with Landscape Design](https://mlsanity.com/paper/1711.00501/) (2017)
- [Lagrangian Duality for Constrained Deep Learning](https://mlsanity.com/paper/2001.09394/) (2020)
- [Satisfying Real-world Goals with Dataset Constraints](https://mlsanity.com/paper/1606.07558/) (2016)
- [Globally Optimal Gradient Descent for a ConvNet with Gaussian Inputs](https://mlsanity.com/paper/1702.07966/) (2017)
- [Training Well-Generalizing Classifiers for Fairness Metrics and Other Data-Dependent Constraints](https://mlsanity.com/paper/1807.00028/) (2018)
- [Differentially Private and Fair Deep Learning: A Lagrangian Dual Approach](https://mlsanity.com/paper/2009.12562/) (2020)
- [Probably Approximately Correct Constrained Learning](https://mlsanity.com/paper/2006.05487/) (2020)
- [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)
- [Controlled Sparsity via Constrained Optimization or: How I Learned to Stop Tuning Penalties and Love Constraints](https://mlsanity.com/paper/2208.04425/) (2022)
- [A Lagrangian Duality Approach to Active Learning](https://mlsanity.com/paper/2202.04108/) (2022)
- [Inexact Stochastic Mirror Descent for two-stage nonlinear stochastic programs](https://mlsanity.com/paper/1805.11732/) (2018)
- [Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow](https://mlsanity.com/paper/2007.07002/) (2020)

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

- [Constrained Diffusion Models via Dual Training](https://mlsanity.com/paper/2408.15094/) (2024)
- [Alignment of large language models with constrained learning](https://mlsanity.com/paper/2505.19387/) (2025)
- [Position: Adopt Constraints Over Fixed Penalties in Deep Learning](https://mlsanity.com/paper/2505.20628/) (2025)
- [Solving Differential Equations with Constrained Learning](https://mlsanity.com/paper/2410.22796/) (2024)
- [Fast State-Augmented Learning for Wireless Resource Allocation with Dual Variable Regression](https://mlsanity.com/paper/2506.18748/) (2025)
- [AL-CoLe: Augmented Lagrangian for Constrained Learning](https://mlsanity.com/paper/2510.20995/) (2025)
- [Everywhere Learning: Artificial Intelligence with Pointwise Constraints](https://mlsanity.com/paper/2606.01557/) (2026)
- [Adaptive Symmetrization of the KL Divergence](https://mlsanity.com/paper/2511.11159/) (2025)
- [CG4AI: A Column Generation Framework for Training AI Models Under Constraints](https://mlsanity.com/paper/2608.26375/) (2026)

## Abstract (arXiv)

With the widespread adoption of machine learning systems, the need to curtail their behavior has become increasingly apparent. This is evidenced by recent advancements towards developing models that satisfy robustness, safety, and fairness requirements. These requirements can be imposed (with generalization guarantees) by formulating constrained learning problems that can then be tackled by dual ascent algorithms. Yet, though these algorithms converge in objective value, even in non-convex settings, they cannot guarantee that their outcome is feasible. Doing so requires randomizing over all iterates, which is impractical in virtually any modern applications. Still, final iterates have been observed to perform well in practice. In this work, we address this gap between theory and practice by characterizing the constraint violation of Lagrangian minimizers associated with optimal dual variables, despite lack of convexity. To do this, we leverage the fact that non-convex, finite-dimensional constrained learning problems can be seen as parametrizations of convex, functional problems. Our results show that rich parametrizations effectively mitigate the issue of feasibility in dual methods, shedding light on prior empirical successes of dual learning. We illustrate our findings in fair learning tasks.