Research map / Learning theory and algorithms / Combinatorial and search optimization
Near-Optimal Solutions of Constrained Learning Problems
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that for rich parametrizations, Lagrangian minimizers at optimal dual variables (and best dual iterates of dual ascent) are near-optimal and near-feasible for the convex functional problem, removing the need for randomization over iterates.
Problem
Dual ascent methods for non-convex constrained learning converge in objective value but their primal iterates may be infeasible; randomization over iterates is typically needed for feasibility guarantees, which is impractical.
Approach
Treat the non-convex parametrized constrained problem as a perturbation of a convex functional problem; bound the suboptimality and constraint violation of Lagrangian minimizers at optimal dual variables in terms of the parametrization's approximation error nu, the dual function's curvature, and constraint sensitivity, so last/best iterates are near-feasible without randomization.
Key results
- Last-iterate and randomized predictors show similar accuracy and constraint satisfaction on COMPAS fair learning.
- Constraint violation of last primal iterates decreases by up to an order of magnitude as parametrization capacity increases (random projection dimension).
- Unconstrained model is slightly more accurate than constrained models but less counterfactually fair.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Train without fairness constraints instead of using constrained learning | COMPAS classifier · COMPAS | test accuracy | Helped |
| Add counterfactual fairness constraints | COMPAS classifier · COMPAS | counterfactual fairness | Helped |
| Use the last iterate instead of a randomized predictor | Dual Constrained Learning · COMPAS | accuracy | No clear effect |
| Use the last iterate instead of a randomized predictor | Dual Constrained Learning · COMPAS | constraint violation | No clear effect |
| Increase parametrization richness (ablation) | 2-layer sigmoid neural network · COMPAS | maximum constraint violation | Helped |
Surprising findings
- Richer parametrizations not only lower approximation error but also make the dual optimization easier, so last iterates become more feasible.
Limitations
- Assumptions (strong convexity of loss in functional space, LICQ-type full-rank Jacobian, strict feasibility) are strong and hard to verify in practice.
- Experiments are limited to a single fair learning task on COMPAS with a small 2-layer network.
- Estimation error from empirical Lagrangian minimization is not analyzed.
Experimental setup
Datasets: COMPAS
Benchmarks: COMPAS
Metrics: test accuracy counterfactual fairness constraint violation
Baselines: unconstrained model randomized predictor
Builds on: dual ascent projected supergradient ascent strong duality via perturbation function analysis counterfactual fairness
Closest papers by meaning
- Probably Approximately Correct Constrained Learning (NeurIPS 2020 · similarity 0.89)
- Learning with Statistical Equality Constraints (NeurIPS 2025 · similarity 0.88)
- Learning Valid Dual Bounds in Constraint Programming: Boosted Lagrangian Decomposition with Self-Supervised Learning (AAAI 2025 · similarity 0.87)
- Convex Formulations for Training Two-Layer ReLU Neural Networks (ICLR 2025 · similarity 0.87)
- Semi-infinite Nonconvex Constrained Min-Max Optimization (NeurIPS 2025 · similarity 0.86)
- Constrained Bi-Level Optimization: Proximal Lagrangian Value Function Approach and Hessian-free Algorithm (ICLR 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.