Metraipolis › archive › dc_6715a1fceef2
Constrained Online Learning with Noisy Constraint Values — arXiv:2609.06921
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.06921
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T13:57:36.519Z
- SHA-256 of the archived text
5a7b52cdbcfbdd91e1a2b033a39c72797aefae33c7a99ffb357d48ff3d447c36- Stable URL of this page
https://metraipolis.com/documento/dc_6715a1fceef2
How to cite
Constrained Online Learning with Noisy Constraint Values — arXiv:2609.06921 — arXiv (en), https://arxiv.org/abs/2609.06921 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_6715a1fceef2 (Metraipolis archive dc_6715a1fceef2, sha256 5a7b52cdbcfbdd91e1a2b033a39c72797aefae33c7a99ffb357d48ff3d447c36)
BibTeX
@misc{dc6715a1fceef2,
title = {Constrained Online Learning with Noisy Constraint Values — arXiv:2609.06921},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.06921},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_6715a1fceef2; sha256 5a7b52cdbcfbdd91e1a2b033a39c72797aefae33c7a99ffb357d48ff3d447c36},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.06921. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We study constrained online convex optimization with adversarial constraints and conditionally unbiased, finite-variance observations of constraint values and gradients. Under common feasibility, our \LEDGER\ algorithm attains $O(\sqrt T)$ expected regret and $O(\sqrt{T\log(eT)})$ expected budget violation, the largest cumulative overspend over any window. It uses a reflected exponential potential, clipped signed observations, and predictable adaptive regularization, with one feedback triple and one projection per round. Neither a Slater condition, independence between feedback channels, nor an absolute constraint-value bound is needed. A Gaussian testing lower bound proves that the budget rate has optimal horizon dependence under square-root regret at fixed positive noise, including the logarithm. The same obstruction holds for terminal violation, so the logarithm is not a cost of maximizing over windows; an $O(\sqrt T)$ budget bound instead forces linear regret. In contrast, fixed positive Gaussian value noise yields a joint regret--hard-violation lower bound of $\Omega(\min\{\sigma,1\}T/\log^2 T)$, even with exact gradients in one dimension. The hard-violation construction matches arbitrarily many moments while preserving a feasible-endpoint gap and constant endpoint probabilities. Together, the bounds separate uncertainty about hard feasibility from learnable signed budgets. Deterministic restarts remove the horizon input without changing either upper rate.
Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-09 in cs.LG).
Categorie arXiv: Machine Learning (cs.LG) ; Artificial Intelligence (cs.AI); Optimization and Control (math.OC).
Pagina del lavoro: https://arxiv.org/abs/2609.06921 — 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-16T13:39:42.917Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-09-09?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).