Metraipolis › archive › dc_9fc355d151e3

Constrained Learning with Universally Learnable Concept Classes — arXiv:2608.08414

Source
arXiv (en)
Original
https://arxiv.org/abs/2608.08414
License (as archived)
CC0-1.0
Archived
2026-10-19T09:02:46.898Z
SHA-256 of the archived text
0a54bd58966ed8ed49bfa311fbc9af741ee8dc79149d9c4c825047810c00d5dd
Stable URL of this page
https://metraipolis.com/documento/dc_9fc355d151e3

How to cite

Constrained Learning with Universally Learnable Concept Classes — arXiv:2608.08414 — arXiv (en), https://arxiv.org/abs/2608.08414 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_9fc355d151e3 (Metraipolis archive dc_9fc355d151e3, sha256 0a54bd58966ed8ed49bfa311fbc9af741ee8dc79149d9c4c825047810c00d5dd)
BibTeX
@misc{dc9fc355d151e3,
  title = {Constrained Learning with Universally Learnable Concept Classes — arXiv:2608.08414},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.08414},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_9fc355d151e3; sha256 0a54bd58966ed8ed49bfa311fbc9af741ee8dc79149d9c4c825047810c00d5dd},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.08414. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 $\mathcal{H}_K$, dense in a decomposable envelope, and learning over norm balls of growing radius. This yields the Tikhonov complexity $\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/\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 $\mathcal{H}_K$ retrieves feasible solutions from dualization; it is a property of the problem, not of a modeling choice. Learnability is exact when $\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.

Tema degli esploratori: statistica e scienza dei dati (retro-catalogo arXiv: annunci del 2026-08-11 in stat.ML).
Categorie arXiv: Machine Learning (cs.LG) ; Optimization and Control (math.OC); Statistics Theory (math.ST); Machine Learning (stat.ML).
Pagina del lavoro: https://arxiv.org/abs/2608.08414 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-19T09:01:32.151Z dalla pagina https://arxiv.org/catchup/stat.ML/2026-08-11?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).