# Feasible Learning

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 49 references that are in the map.
- First posted on arXiv 24 Jan 2025.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Direct Preference Optimization: Your Language Model is Secretly a Reward Model](https://mlsanity.com/paper/2305.18290/) (2023)
- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [QLoRA: Efficient Finetuning of Quantized LLMs](https://mlsanity.com/paper/2305.14314/) (2023)
- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [The Implicit Bias of Gradient Descent on Separable Data](https://mlsanity.com/paper/1710.10345/) (2017)
- [Age Progression/Regression by Conditional Adversarial Autoencoder](https://mlsanity.com/paper/1702.08423/) (2017)
- [Shampoo: Preconditioned Stochastic Tensor Optimization](https://mlsanity.com/paper/1802.09568/) (2018)
- [Orca: Progressive Learning from Complex Explanation Traces of GPT-4](https://mlsanity.com/paper/2306.02707/) (2023)
- [Responsive Safety in Reinforcement Learning by PID Lagrangian Methods](https://mlsanity.com/paper/2007.03964/) (2020)
- [On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems](https://mlsanity.com/paper/1906.00331/) (2019)
- [A Survey of Reinforcement Learning from Human Feedback](https://mlsanity.com/paper/2312.14925/) (2023)
- [Fairness without Demographics through Adversarially Reweighted Learning](https://mlsanity.com/paper/2006.13114/) (2020)
- [Optimization with Non-Differentiable Constraints with Applications to Fairness, Recall, Churn, and Other Goals](https://mlsanity.com/paper/1809.04198/) (2018)
- [Near-optimal Local Convergence of Alternating Gradient Descent-Ascent for Minimax Optimization](https://mlsanity.com/paper/2102.09468/) (2021)
- [Controlled Sparsity via Constrained Optimization or: How I Learned to Stop Tuning Penalties and Love Constraints](https://mlsanity.com/paper/2208.04425/) (2022)
- [Operator splitting for a homogeneous embedding of the linear complementarity problem](https://mlsanity.com/paper/2004.02177/) (2020)
- [Resilient Constrained Learning](https://mlsanity.com/paper/2306.02426/) (2023)
- [On PI Controllers for Updating Lagrange Multipliers in Constrained Optimization](https://mlsanity.com/paper/2406.04558/) (2024)
- [Neyman-Pearson classification: parametrics and sample size requirement](https://mlsanity.com/paper/1802.02557/) (2018)

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

- [Position: Adopt Constraints Over Fixed Penalties in Deep Learning](https://mlsanity.com/paper/2505.20628/) (2025)
- [Constrained Sliced Wasserstein Embedding](https://mlsanity.com/paper/2506.02203/) (2025)
- [Dual Optimistic Ascent (PI Control) is the Augmented Lagrangian Method in Disguise](https://mlsanity.com/paper/2509.22500/) (2025)
- [Everywhere Learning: Artificial Intelligence with Pointwise Constraints](https://mlsanity.com/paper/2606.01557/) (2026)
- [ReliableNet: A Chance-Constrained Approach to Trustworthy Classification in Deep Learning](https://mlsanity.com/paper/2608.09768/) (2026)

## Abstract (arXiv)

We introduce Feasible Learning (FL), a sample-centric learning paradigm where models are trained by solving a feasibility problem that bounds the loss for each training sample. In contrast to the ubiquitous Empirical Risk Minimization (ERM) framework, which optimizes for average performance, FL demands satisfactory performance on every individual data point. Since any model that meets the prescribed performance threshold is a valid FL solution, the choice of optimization algorithm and its dynamics play a crucial role in shaping the properties of the resulting solutions. In particular, we study a primal-dual approach which dynamically re-weights the importance of each sample during training. To address the challenge of setting a meaningful threshold in practice, we introduce a relaxation of FL that incorporates slack variables of minimal norm. Our empirical analysis, spanning image classification, age regression, and preference optimization in large language models, demonstrates that models trained via FL can learn from data while displaying improved tail behavior compared to ERM, with only a marginal impact on average performance.