AL-CoLe: Augmented Lagrangian for Constrained Learning

Ignacio Boero, Ignacio Hounie, Alejandro Ribeiro · 2025

Read AL-CoLe: Augmented Lagrangian for Constrained Learning by Ignacio Boero, Ignacio Hounie, Alejandro Ribeiro (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-20995.txt.

Introduction

Ignacio Boero leads two co-authors on AL-CoLe, an augmented Lagrangian method for learning under constraints such as fairness limits. Lagrangian duality is popular for constrained learning despite non convex models, but plain duality leaves a gap that augmented forms can narrow with small changes.

Strong duality results are established under mild conditions, dual ascent is proved to converge to feasible optimal primal solutions, and PAC style generalization guarantees are supplied. Tests on fairness constrained classification show the method working in practice. The package gives constrained learning a firmer theoretical base than heuristic penalty tuning usually offers.

Catalog record

CREATORIgnacio Boero, Ignacio Hounie, Alejandro Ribeiro
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE29 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-20995

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

AL-CoLe: Augmented Lagrangian for Constrained Learning Ignacio Boero, Ignacio Hounie, Alejandro Ribeiro Abstract Despite the non-convexity of most modern machine learning parameterizations, Lagrangian duality has become a popular tool for addressing constrained learning problems. We revisit Augmented Lagrangian methods, which aim to mitigate the duality gap in non-convex settings while requiring only minimal modifications, and have remained comparably unexplored in constrained learning settings. We establish strong duality results under mild conditions, prove convergence of dual ascent algorithms to feasible and optimal primal solutions, and provide PAC-style generalization guarantees. Finally, we demonstrate its effectiveness on fairness constrained classification tasks. † † address: University of Pennsylvania 1 Introduction The widespread adoption of machine learning in critical domains has underscored the need to curtail undesirable behavior. A natural approach is to extend empirical risk minimization (ERM) with additional statistical risks—such as fairness, robustness, or safety—as explicit constraints. Doing so, however, raises challenges for both optimization and generalization. On the optimization side, mini-batch updates make feasibility during training intractable, limiting interior-point methods, while the non-convexity of neural networks prevents strong duality, weakening guarantees of feasibility and optimality for dual methods. On the generalization side, constraint estimation error impacts both feasibility and optimality, the latter depending on sensitivity to perturbations. To circumvent the lack of strong duality, prior work has treated non-convex constrained problems as parameterizations of convex functional ones, where duality holds. This yields bounds on the duality gap in terms of approximation error and allows extending PAC-learnability [ 1 ] to constrained settings [ 2 , 3 ] . More recently, [ 4 ] showed that primal solutions obtained from dual iterates can achieve near-feasible, near-optimal solutions in over-parameterized regimes. Although a growing body of work has studied constrained learning via dual formulations [ 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 ] , these approaches typically rely on (non-augmented) dual ascent. Augmented Lagrangian (AL) methods were originally proposed to close the duality gap in nonconvex optimization [ 13 ] . Although they have appeared sporadically in machine-learning applications—such as diffusion models [ 14 ] , physics-informed neural networks [ 15 ] , pruning [ 16 ] , learning-to-optimize [ 17 ] , SVMs [ 18 ] , reinforcement learning [ 19 ] , and stochastic optimization [ 20 ] —these uses are largely empirical and lack a theoretical foundation. In particular, they neither define constraints on statistical risk functionals nor study the generalization properties of empirical AL methods under such constraints. In this work, we study AL methods for constrained learning and develop a generalization theory within the PAC-Constrained framework [ 2 ] . We prove that, under mild assumptions, strong duality holds between the primal and extended dual problems, eliminating approximation error. Crucially, we show that constrained learning problems are PACC-learnable , rather than merely near-PACC-learnable as previously believed. Moreover, augmented dual algorithms—defined by sequences of unconstrained subproblems—yield primal iterates converging to feasible and optimal solutions. Finally, we validate our results empirically on a fairness-constrained classification task, comparing augmented and standard dual methods. Figure 1: Dynamics of lagrange multipliers \lambda training iterations, for both the augmented Lagrangian and regular Lagrangian methods. Both methods use the same hyperparameters, including the dual learning rate. 2 Augmented Lagrangian for constrained learning 2.1 Statistical Constrained Learning Constrained learning problems typically consist of the minimization of a risk functional under constraints over distinct risk functionals and data distributions, namely \displaystyle\text{minimize}\; \displaystyle{\displaystyle\ell}_{0}(f_{\theta})\quad\text{over all }\theta\in\Theta (P) \displaystyle\text{s.t.} \displaystyle\ell_{i}(f_{\theta})\leq 0,\;i\in\{1,\dots,m\} with the risk functionals defined as {\ell}_{i}(f_{\theta}):=\mathbb{E}_{(x,y)\sim\mathcal{D}_{i}}\!\left[\,\bar{\ell}_{i}\!\big(f_{\theta}(x),\,y\big)\,\right],\;\forall i\in\{0,\dots,m\} (1) where f_{\theta}(x):\mathcal{X}\to\mathcal{Y} is a function parametrized by the vector \theta\subseteq\Theta\in\mathbb{R}^{p} , \bar{\ell}_{i} denotes the sample-wise loss and \ell_{i} is its corresponding expected risk under distribution \mathcal{D}_{i} . Here \ell_{0} represents the risk we wish to minimize (e.g. cross entropy) and \ell_{i} the risks we wish to constrain (e.g. counterfactual fairness). For most common parametrization choices (e.g. neural networks), P is a non-convex constrained optimization problem. 2.2 Augmented Lagrangian and Duality Augmented Lagrangian methods for inequality-constrained problems were first introduced in [ 13 ] . For problem P the augmented Lagrangian is defined as \displaystyle L(\theta,\lambda,\alpha)=\ell_{0}(f_{\theta})\;+\;\alpha\sum_{i=1}^{m}\Psi(l_{i}(f_{\theta}),\frac{\lambda_{i}}{\alpha}) (2) for (\lambda,\alpha)\in T\subseteq\mathbb{R}^{m}\times(0,+\infty) where \Psi(x,y)=[\text{max}^{2}\left\{0,2x+y\right\}-y^{2}]/4 (3) The corresponding augmented dual problem is defined as \displaystyle\text{maximize} \displaystyle g(\lambda,\alpha)\quad\text{over all}\;(\lambda,\alpha)\in T,\;\text{where} (D) \displaystyle g(\lambda,\alpha):=\inf_{\theta\in\Theta}L(\theta,\lambda,\alpha) Analogous to the standard (non-augmented) dual problem, weak duality and concavity hold [ A.1 ]. In contrast, the augmented Lagrangian enables strong duality even in non-convex settings. We now state the assumptions required to guarantee strong duality in our problem. Assumption 2.1 (Bounded Objective) . The function \ell_{0} is bounded below. Assumption 2.2 (Closed Domain) . The set \Theta is closed (e.g., \Theta=\mathbb{R}^{p} ). Assumption 2.3 (Continuity) . The mapping \theta\mapsto f_{\theta} is continuous, and the sample-wise losses \bar{\ell}_{i}(\cdot,y) are continuous and uniformly bounded in y . Assumption 2.4 (Compact Feasible Level Set) . There exist u>0 and \bar{p}>\inf(P) such that \{\theta\in\Theta:\ell_{0}(\theta)\leq\bar{p},\ \ell_{i}(\theta)\leq u,\ \forall i=1,\dots,m\} is compact. Assumption 2.1 holds whenever the sample-wise losses \bar{\ell}_{0} are bounded below, as is the case for standard losses such as MSE or cross-entropy. Assumptions 2.2 and 2.3 impose only mild regularity on the parameterization mapping and the constraint functions. Finally, Assumption 2.4 generalizes Slater’s condition to non-convex settings; in the convex case, Slater’s condition is sufficient for it to hold. Theorem 2.1 (Strong Duality) . If Assumptions 2.1 – 2.4 hold, then strong duality holds for problem P , i.e., \inf(P)=\sup(D). Proof. See Appendix A.2 . ∎ Although concavity and strong duality imply that solving P should be straightforward—since subgradient methods address the dual and, in turn, the primal—one difficulty remains: the dual optimum may exist only as a limit. Thus, establishing the existence of bounded dual variables (\alpha^{*},\lambda^{*}) such that g(\alpha^{*},\lambda^{*})=\sup(D)=\inf(P) is crucial. In non-augmented dual formulations, the boundedness of the multipliers \lambda^{*} hinges on first-order sufficiency (e.g., the KKT conditions) being necessary. This necessity, in turn, is guaranteed by assuming the objective and constraint functions are C^{1} and that a first-order constraint qualification holds—for instance, the Linear Independence Constraint Qualification (LICQ). Assumption 2.5 (Linear Independence Constraint Qualification) . Problem P satisfies the Linear Independence Constraint Qualification (LICQ). That is, the set of active constraint gradients \{\nabla_{\theta}\ell_{i}(f_{\theta}^{*})\} is linearly independent at the optimal point \theta^{*} . For the augmented dual problem, it is also required that the second-order sufficient conditions be necessary, together with the assumption that both the constraint and objective functions are \mathcal{C}^{2} . Assumption 2.6 (Smoothness) . Each function \ell_{i}(f_{\theta}) is twice continuously differentiable, i.e., \mathcal{C}^{2} . Assumption 2.7 (Second-Order Sufficient Condition) . Let \bar{\theta}\in\Theta and \bar{\lambda}\in\mathbb{R}^{+} be such that the KKT conditions hold, i.e., \nabla_{\theta}L(\bar{\theta},\bar{\lambda},0)=0 and \nabla_{\lambda}L(\bar{\theta},\bar{\lambda},0)=0 . If Assumption 2.5 holds, such a pair (\bar{\theta},\bar{\lambda}) exists. Define H:=\nabla_{\theta}^{2}L(\bar{\theta},\bar{\lambda},0) , I_{0}:=\{\,i:f_{i}(\bar{\theta})=0,\ \lambda_{i}>0\,\} , I_{1}:=\{\,i:f_{i}(\bar{\theta})=0,\ \lambda_{i}=0\,\}. Then the second-order sufficient condition requires z^{\top}Hz\;>\;0\quad\forall z\in C(\bar{\theta}),\quad\text{where} (4) C(\bar{\theta})=\{\,z:\begin{cases}\nabla f_{i}(\bar{\theta})^{\top}z=0,&i\in I_{0},\\ \nabla f_{i}(\bar{\theta})^{\top}z\leq 0,&i\in I_{1}\end{cases}\}. Assumption 2.6 enforces smoothness of both the loss functions and the parametrization mapping. It is satisfied, for instance, when employing neural networks with \mathcal{C}^{2} activations (e.g., sigmoid) and smooth loss functions (e.g., MSE). In contrast, Assumptions 2.7 and 2.5 are less transparent, as their validity depends on the first- and second-order properties of the problem at the optimum. Nevertheless, these conditions are typically assumed to hold. For a detailed discussion

Read the complete text