Constrained Online Learning with Noisy Constraint Values

Vaneet Aggarwal

cs.LGSep 7, 2026

Constrained Online Learning with Noisy Constraint Values

Authors: Vaneet Aggarwal

Organizations: Purdue University

Abstract

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 $Ω(\min\{σ,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.

Explore similar work

Jun 30, 2026cs.LG

Constrained Online Convex Optimization without Slater's Condition

We study constrained online convex optimization with adversarial losses and stochastic or adversarial constraints. For stochastic constraints, existing algorithms that achieve nearly optimal regret and constraint violation bounds typically rely on regularity assumptions such as Slater's condition, while adversarial-constraint algorithms avoid these assumptions by using a rather restrictive round-wise feasible comparator. We bridge this gap with an anytime primal-dual framework that incorporates an adaptive regularizer into the dual update. The regularizer stabilizes the dual process without relying on the negative drift induced by Slater's condition. For stochastic constraints and convex losses, our algorithm achieves

O(\sqrt{T})

expected regret and

O(\sqrt{T}\log T)

expected cumulative constraint violation. Furthermore, we show that our algorithm also admits high-probability bounds of the same order on regret and constraint violation. For strongly convex losses, the regret bound improves to

O(\log T)

with a violation bound of the same order. With a minor modification, the framework also applies to adversarial constraints and provides guarantees for hard constraint violation.

Kihyun Yu, Junehee Lee, Dabeen Lee

Convex Optimization Stochastic Optimization Adversarial Training

Ask PDF

Jun 6, 2026cs.LG

Noise-Adaptive High-Probability Regret Bounds for Online Convex Optimization

We study high-probability regret bounds for online convex optimization (OCO) with strongly convex losses and establish three results that resolve open questions at the intersection of noise adaptivity, feedback structure, and constraint satisfaction. For the full-information setting with sub-Gaussian stochastic gradients, we prove a noise-adaptive high-probability regret bound in which the martingale deviation term scales with the noise level

σ

rather than the gradient bound

G

, yielding a multiplicative improvement of

G/σ

over the classical Azuma-Hoeffding baseline. Our analysis introduces an exponential supermartingale argument that bypasses the bounded-difference requirement of Freedman's inequality, enabling direct treatment of unbounded sub-Gaussian noise without truncation artifacts. For bandit feedback, we prove a minimax lower bound: the high-probability regret scales linearly in

\log(1/δ)

, in contrast to the

\sqrt{\log(1/δ)}

confidence cost under full information. This constitutes a formal separation in the confidence cost of strongly convex OCO across feedback models. Regarding constrained OCO with stochastic constraints satisfying a Slater condition, we provide simultaneous high-probability guarantees for both cumulative regret and long-run constraint violation, achieving

\mathcal{O}(\sqrt{T\log(m/δ)})

regret and

\mathcal{O}(\sqrt{T}/(ζδ) + m\sqrt{T\log(m/δ)})

violation. Synthetic experiments corroborate all theoretical predictions.

Wentao Zhang, Yutong Zhang, Wentao Mo

Convex Optimization Linear Regret Conformal Test Martingales

Ask PDF

May 20, 2026cs.LG

A Geometric Approach to Constrained Online Learning

We study constrained online convex optimization with adversarial time-varying constraints. At each round the learner acts before observing the loss and constraint, and is compared with the best fixed action satisfying all constraints in hindsight. The goal is to obtain minimax-optimal regret while controlling cumulative constraint violation (CCV). Prior algorithms achieved

O(\log T)

regret with

O(\sqrt{T\log T})

CCV for strongly convex losses, and

O(\sqrt{T})

regret with

O(\sqrt{T}\log T)

CCV for convex losses. We propose NP-OGD, an iterated nested-projection algorithm. For strongly convex losses it achieves

O(\log T)

regret and

O(\log T)

CCV; for convex losses it achieves

O(\sqrt{T})

regret and

O(\sqrt{T})

CCV. The analysis relies on a geometric movement bound: after lifting the nested projected-gradient trajectory to one higher dimension, the lifted path is self-contracted under a nonstandard norm, so a finite-length theorem for self-contracted curves controls the total projection movement. We also prove complementary lower bounds using layered sphere packings. For strongly convex losses, any online algorithm with polynomially sublinear regret can incur CCV at least

Ω((\log T)^{(d-1)/(d+1)}/\log\log T)

. For convex losses, we prove CCV lower bounds

Ω(T^{(d-1)/(2(d+3))})

for weakly adaptive algorithms and

Ω(T^{(d-1)/(2d)})

for NP-OGD. Finally, for the constrained experts special case over

N

experts, an active Hedge algorithm attains

O(\sqrt{T\log N})

regret and

O(N)

CCV, with a matching minimax CCV lower bound for sufficiently large horizons.

Dhruv Sarkar, Abhishek Sinha

Convex Optimization O(T^Β)$ Simultaneous Regret Learning-Augmented Algorithms

Ask PDF