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).