cs.LGJan 23, 2026

Sample-wise Constrained Learning via a Sequential Penalty Approach with Applications in Image Processing

Authors: Francesca Lanzillotta, Chiara Albisani, Davide Pucci, Daniele Baracchi, Alessandro Piva, Matteo Lapucci

Organizations: The authors are with the Department of Information Engineering (DINFO) of the University of Florence, via di S. Marta 3, Firenze, 50139, Italy.

Abstract

In many learning tasks, certain requirements on the processing of individual data samples can arguably be formalized, in an intelligible way, as strict constraints of the underlying optimization problem, rather than by means of arbitrary penalties that often require heavy trial-and-error tuning. In this paper we show that, in these scenarios, learning can be carried out exploiting a sequential penalty method that allows to explicitly deal with constraints. For the proposed algorithm we show that, under classical assumptions and in the considered learning scenario, penalty subproblems can provably be solved in finite time with suitable guarantees of approximate stationarity in expectation; we also show that, when the latter condition is guaranteed for the subproblems, the overall sequential scheme possesses almost sure convergence properties to KKT-stationary points of (general) constrained problems. The results of experiments on sandbox and real-world image processing tasks show that the method is indeed viable to be used in practical deep learning scenarios.

Figures & tables

Appendix figures & tables6 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

May 27, 2025

Position: Adopt Constraints Over Fixed Penalties in Deep Learning

Deep learning models are increasingly subject to explicit requirements, or constraints, such as safety levels, fairness limits, and sparsity budgets. In practice, such requirements are often handled through fixed weighted-sum penalization: the constraints are added to the task loss with fixed coefficients, and the resulting scalarized objective is minimized. This position paper argues that fixed penalization is often ill-suited to deep learning problems with non-negotiable requirements, for three main reasons. First, in non-convex settings, the penalized and constrained problems are not, in general, equivalent, so a minimizer of the penalized objective need not solve the constrained problem. Second, a penalty coefficient sets an objective-constraint trade-off rather than the constraint level, so finding an acceptable coefficient often takes trial and error, each trial a full training run. Third, fixed penalization weakens hard requirements into soft penalties to be traded off against task performance. As a result, compliance is no longer built into the problem, and requirements can be quietly relaxed. We therefore argue that, when a deep learning problem specifies non-negotiable requirements, one should solve the constrained problem itself instead of a surrogate defined by fixed penalization.
May 18, 2026

Stochastic Penalty-Barrier Method for Constrained Machine Learning

Constrained Machine Learning (CML) enables fairness-aware training, physics-informed neural networks, and integration of symbolic domain knowledge into statistical models. In this work, we introduce the Stochastic Penalty-Barrier Method (SPBM) for CML problems. SPBM extends classical penalty and barrier methods by incorporating an exponential averaging of the dual variables, a stabilized penalty schedule, and the Moreau envelope to handle non-smoothness. We analyze the bias that mini-batching introduces in the barrier function and show that the feasible set of the resulting transformed problem is contained within the original one. We compare SPBM with CML baselines across multiple fairness and physics informed neural networks experiments. We find that SPBM is competitive with state-of-the-art methods. We also observe, on our fairness-based computational benchmark, that the per-epoch runtime of CML methods is largely independent of the number of constraints, and within 1.3×1.3\times of the per-epoch runtime of regularized Adam, for a number of constraints ranging from 9090 to 99009900.
Aug 9, 2026

Constrained Learning with Universally Learnable Concept Classes

We study constrained statistical learning over infinite-dimensional hypothesis classes in the fully nonconvex setting, and establish universal PACC learnability of the solutions of dual algorithms: Probably Approximately Correct on Constraints, guaranteeing optimality and constraint satisfaction at once. This strengthens near-PACC results, whose feasibility residual no amount of data can remove. Optimality is caught between generalization, governed by Rademacher complexity and favoring small classes, and strong Lagrangian duality, which rests on Lyapunov convexity for vector measures and needs decomposability, a demand pulling the other way. We reconcile the two by posing the population problem over a universal RKHS HK\mathcal{H}_K, dense in a decomposable envelope, and learning over norm balls of growing radius. This yields the Tikhonov complexity Tnε\mathfrak{T}^{\varepsilon}_{n}, the least RKHS norm reaching an ε\varepsilon-optimal Lagrangian level set; we prove it finite, obtain exact learnability of the optimal value, and make the sample threshold explicit and polynomial in 1/ε1/\varepsilon under a source condition. Feasibility is harder: absent convexity the Lagrangian may not attain its infimum, and dual information pins down only an averaged constraint-risk vector, not the risks of any returned predictor. We introduce the closure-realization gap ε∞⋆\varepsilon^\star_\infty, an index of how well HK\mathcal{H}_K retrieves feasible solutions from dualization; it is a property of the problem, not of a modeling choice. Learnability is exact when ε∞⋆=0\varepsilon^\star_\infty=0, in particular under dual differentiability, and near-PACC with residual exactly ε∞⋆\varepsilon^\star_\infty otherwise. Finally, no distribution-free threshold exists already in the unconstrained specialization, so universality is the canonical frame for dual algorithms over large hypothesis classes.