Constrained Learning with Universally Learnable Concept Classes

arXiv:2608.08414v1 Announce Type: new Abstract: 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 H_K, dense in a decomposable envelope, and learning over norm balls of growing radius. This yields the Tikhonov complexity mathfrak{T}^{arepsilon}_{n}, the least RKHS norm reaching an arepsilon-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/arepsilon 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 arepsilon^star_infty, an index of how well H_K retrieves feasible solutions from dualization; it is a property of the problem, not of a modeling choice. Learnability is exact when arepsilon^star_infty=0, in particular under dual differentiability, and near-PACC with residual exactly arepsilon^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.

Source: arXiv cs.LG | 2026-08-11