PaperlayerView exact revision on arXiv

Source-linked AI summary

Constrained Online Learning with Noisy Constraint Values

Vaneet Aggarwal

arXiv:2609.06921v1cs.LGcs.AImath.OC

TL;DR

The paper asks which regret and feasibility guarantees remain possible when adversarial constraint values and gradients are observed through unbiased noise. It proves that Gaussian value noise prevents jointly polynomially sublinear regret and hard violation, then introduces LEDGER and budget violation to obtain tunable static and dynamic guarantees. The resulting balanced static pair is O(T^2/3) regret and O(T^2/3) budget violation without a Slater condition.

  • Problem

    Noisy constraint values create a statistical obstruction to jointly controlling regret and hard violation, even when gradients are known.

  • Method

    LEDGER tracks observed net consumption in a nonnegative balance and chooses constraint weights before current feedback noise, using signed accounting for maximum-window budget control.

  • Results

    O(T^2/3) expected regret and O(T^2/3) expected budget violation are achieved at V = T^-1/6 under common feasibility and conditional finite-variance feedback.

  • Takeaways & Limitations

    Budget violation is an achievable alternative to hard violation under noisy values, while the same update tracks predictable feasible comparator paths without common feasibility or a path-length input.

  • Takeaways & Limitations

    Fixed positive Gaussian value noise rules out jointly polynomially sublinear regret and hard violation, and the guarantees provide expected budget control rather than a roundwise safety guarantee.

Abstract

from arXiv · show

We study constrained online convex optimization with adversarial constraints when constraint values and gradients are observed through unbiased noise. Gaussian value noise of standard deviation $σ$ yields a worst-case lower bound of $Ω(\min\{σ,1\}T/\log^7T)$ on the maximum of expected regret and expected hard violation, even with known gradients. This rules out any jointly $O(T^{1-δ})$ guarantee for fixed $δ>0$ and fixed positive noise level. We therefore study budget violation: the largest cumulative overspend over any window within a fixed horizon. We introduce \LEDGER, which tracks observed net consumption in a nonnegative balance and sets constraint weights before the current feedback noise. Under common feasibility and conditional finite-variance feedback, for fixed problem parameters, \LEDGER\ achieves $O(\sqrt T/V)$ expected regret and $O(\sqrt V\,T^{3/4}+σ\sqrt T)$ expected budget violation for $V\in[T^{-1/2},1]$. This gives the pair $(O(\sqrt T),O(T^{3/4}))$ at $V=1$ and $(O(T^{2/3}),O(T^{2/3}))$ at $V=T^{-1/6}$, without a Slater condition. The budget-focused endpoint $V=T^{-1/2}$ gives $(O(T),O(\sqrt T))$. The same update yields $O((1+E[P_T])\sqrt T/V)$ expected dynamic regret for predictable feasible comparator paths, without common feasibility or path-length input. Its budget bound instead depends on the shortest feasible path, up to a dimension factor.

1 Introduction

The paper shows that noisy constraint values create a near-linear obstruction to jointly controlling regret and hard violation, then introduces budget violation as an achievable alternative. LEDGER provides tunable static and dynamic guarantees under noisy feedback, including balanced regret–budget rates without a Slater condition.

  • Budget violation: Budget violation permits underspending to offset overspending within windows, unlike hard violation, which charges each infeasible round separately.For alternating levels −1 and +1, terminal violation is zero, hard violation is T/2, and budget violation is 1 for even T.
  • Limits of hard-violation guarantees: Noisy constraint values yield a worst-case joint regret–hard-violation lower bound that excludes polynomially sublinear rates, even with known gradients.The growing-order bound is Ω(σT/log^7 T) for 0 < σ ≤ 1.
  • Static guarantees: For V ∈ [T^-1/2, 1], LEDGER achieves O(√T/V) expected regret and O(√V T^3/4 + σ√T) expected budget violation under common feasibility.At V = T^-1/6, the pair is (O(T^2/3), O(T^2/3)); at V = 1, it is (O(√T), O(T^3/4)).
  • Dynamic guarantees: The same update gives predictable-comparator dynamic regret O((1 + E[P_T])√T/V) without common feasibility or a path-length input.Its budget analysis instead uses a predictable feasible path and can depend on the shortest feasible path, with a dimension-dependent factor.
  • LEDGER: LEDGER tracks observed net consumption in a nonnegative balance and sets constraint weights predictably before current feedback noise.Its design connects signed queues and quadratic dual regularization to maximum-window control under noisy adversarial feedback.
  • Scope and comparisons: The paper’s guarantees separate feedback models, comparator classes, and violation metrics, with noisy dynamic bounds stated in expectation against adaptive adversaries.The dynamic budget bound tracks a predictable online chasing path rather than necessarily the regret comparator.

2 Setting

The paper studies online convex optimization with adversarial constraints observed through noisy local feedback, distinguishing hard, terminal, and windowed budget violations. Its budget metric tracks maximum overspending over any window, while LEDGER uses noisy observations in a nonnegative balance.

  • Problem setting: The learner operates on a compact convex set against adaptive convex losses and constraints, receiving only noisy value, gradient, and loss observations at the played action.The adversary cannot depend on current-round observation noise, and projection onto the known decision set is available.
  • Feedback assumptions: Constraint feedback may have dependent channels, while value noise is conditionally unbiased and has finite variance, including Gaussian and bounded noise.All LEDGER guarantees, including the budget-focused endpoint, hold under this finite-variance model.
  • Comparator assumptions: The static comparator class requires a deterministic action feasible on every round almost surely, with common feasibility but no Slater condition.Static regret bounds apply to each fixed feasible comparator rather than a hindsight action selected using the noise.
  • Violation metrics: Hard violation charges each infeasible round separately, whereas budget violation measures the largest cumulative overspend over any window.Budget violation equals a reflected-random-walk maximum for true levels, but the learner maintains a noisy balance with regularization instead.
  • Estimator: The affine noisy constraint estimator preserves comparator feasibility in conditional mean and separates value noise from direction noise in the analysis.At the played action, the estimator contains only value noise; action–comparator differences contain only direction noise.

3 Limits of hard-violation guarantees

Noisy constraint values make jointly polynomially sublinear regret and hard-violation guarantees impossible at fixed positive noise, even with exact gradients. The paper therefore establishes lower bounds through indistinguishable constraint-level distributions and separates this result from the budget metric.

  • Main lower bound: Noisy constraint values rule out joint O(T^(1−δ)) regret and hard violation for any fixed δ, σ > 0, though not every sublinear rate.The obstruction is attributed to the value channel rather than the constraint geometry.
  • Moment matching: Moment matching yields a worst-case joint regret–hard-violation lower bound of Ω(σT^(1−1/(4n))) for every fixed matching order n.The construction uses two distributions whose noisy observations are difficult to distinguish while their feasible comparators differ.
  • Strengthened bound: Choosing the matching order as O(log T / log log T) strengthens the lower bound to Ω(σT/log^7 T) for fixed positive σ.The lower bound remains joint and excludes polynomially sublinear rates rather than every sublinear rate.
  • Information restriction: The lower-bound constructions retain a fixed always-feasible comparator and remain valid even when the full loss and constraint slope are revealed.This isolates noisy value observations as the source of the obstruction.
  • Budget lower bound: A separate two-instance test gives a joint regret–budget lower bound, but it does not establish optimality of LEDGER’s budget guarantee.The stated lower bounds do not apply to exact-value feedback.

4 Achievable guarantees with LEDGER

LEDGER replaces noisy positive-part constraint queues with a regularized balance of observed signed consumption and chooses constraint weights before current feedback noise. It achieves a regret–budget tradeoff under finite-variance feedback and extends to predictable feasible comparator paths without common feasibility.

  • Algorithm: LEDGER prices future constraint consumption using a nonnegative balance of observed signed consumption, targeting budget violation rather than hard violation.The update uses one feedback triple, one projection, and one scalar balance, without clipping or estimating the noise distribution.
  • Noise handling: The method avoids noisy positive-part bias and current-noise correlation by using a conditional-mean affine estimator and predictable constraint weights.Comparator feasibility is preserved in conditional mean, while direction and value noise enter separate parts of the analysis.
  • Balance analysis: The regularized balance controls its second moment, which bounds the running maximum associated with windowed budget violation.LEDGER’s internal balance is not identical to the true budget-violation process, but regularization replaces the exact Lindley identity with an inequality.
  • Static guarantee: For V ∈ [T^−1/2,1], LEDGER achieves expected regret O(√T/V) and expected budget violation O(√V T^(3/4) + σ√T).The constants depend on the known gradient bound, decision-set diameter, true-level bound, and noise scale; guarantees allow adaptive adversaries and require no Slater condition.
  • Dynamic comparators: For predictable feasible comparator paths, the same update provides expected dynamic regret O((1 + E[P_T])√T/V) without common feasibility or path-length input.The budget bound can instead depend on a shortest feasible path, with a dimension-dependent factor from convex-body chasing.
  • Path dependence: A chasing-path analysis lets budget control depend on a shortest feasible path, while the algorithm itself remains unchanged and does not compute the analytical path.For stationary constraints, a constant feasible path gives a bound independent of the regret comparator’s movement.

5 Experimental illustrations

Experiments on linear losses and affine constraints illustrate the separation between hard and budget violation and the regret cost of stronger budget control. Across noisy settings, LEDGER’s fitted budget slopes are substantially lower than its hard-violation slopes.

  • Experimental design: The experiments use linear losses, affine constraints, stationary or alternating budgets, horizons 10^3–10^6, and 20 seeds per configuration.Comparisons include three LEDGER values, exact-feedback and noisy baselines, signed queues, Gaussian noise in all channels, and additional Student-t3 tests.
  • Metric separation: On the blocks instance, LEDGER’s hard-violation slopes are 0.98 at V = 1 and 0.95 at V = T^−1/6, versus budget-violation slopes 0.50 and 0.42.The curves report medians of 20 seeds with interquartile-range bands rather than confidence intervals.
  • Tradeoff: At T = 10^6 on the stationary instance, changing V from 1 to T^−1/6 reduces median budget violation from 5,391 to 737 while changing median regret from −1,151 to 10,386.The reported negative regret is possible because only the comparator is required to be feasible each round.
  • Budget-focused endpoint: At V = T^−1/2, median violation falls to 0.054 while median regret rises to 245,203.This endpoint displays the empirical loss cost of tighter budget control.

6 Conclusion

The paper shows that Gaussian value noise prevents jointly polynomially sublinear regret and hard violation, motivating budget violation and the LEDGER method. LEDGER achieves balanced regret–budget guarantees and extends to predictable feasible comparator paths under adaptive adversaries.

  • Fixed positive Gaussian value noise prevents jointly polynomially sublinear regret and hard violation, even with exact gradients and a common feasible comparator.
  • LEDGER achieves a balanced O(T^2/3) expected regret–budget pair under conditional finite-variance feedback without Slater’s condition.
  • The same update tracks predictable feasible paths and controls budget violation through the shortest feasible path, up to a dimension factor, against adaptive adversaries.
  • The results establish an O(T^2/3) upper bound alongside the lower bound and remove the linear path-length dependence of dynamic regret.
  • The dynamic result also removes the convex-body-chasing dimension factor from budget tracking against adaptive adversaries.

A Related work in full

Related work spans long-term constraints, adversarial and stochastic constraint models, budgeted formulations, noisy-feedback lower bounds, safe learning, and alternative feedback models. The paper distinguishes its noisy adversarial setting from exact-feedback, fixed-distribution, and fixed-constraint results.

  • Long-term and adversarial constraints: Long-term-constraint OCO developed from fixed-constraint regret–violation trade-offs to adversarial time-varying constraints and dynamic guarantees.
  • Long-term and adversarial constraints: Existing adversarial methods obtain dynamic regret and violation guarantees under common feasibility, known path length, exact values, or feasible-set information.
  • Stochastic constraints: Stochastic-constraint methods assume fixed constraint distributions and comparators feasible for the mean, whereas this paper allows adversarially varying constraints and roundwise-feasible comparators.
  • Noisy feedback and budget formulations: Signed queue updates are standard, but the paper analyzes their regret–window-violation behavior under noisy adversarial feedback rather than exact positive-part observations.
  • Noisy feedback and budget formulations: Budgeted and knapsack formulations use spending plans or global comparators, differing from this paper’s learner-side budget-violation metric.
  • Noise and lower bounds: The lower bounds use Le Cam two-point arguments with high-order moment matching, connecting Gaussian-noise hardness to supersmooth deconvolution rates.
  • Other feedback models: Safe-learning results target fixed constraints with pessimistic feasible regions, while alternative feedback frameworks study different observation models from noisy local constraint values and directions.
  • Proof techniques: The analysis combines fixed-step OGD, quadratic dual regularization, Doob’s maximal inequality, Abel summation, and Lindley’s reflected recursion using conditional second moments.

B.1 Explicit constructions and finite-horizon bounds

The appendix constructs indistinguishable noisy instances using symmetric discrete laws and Gaussian convolution, then converts their testing difficulty into regret or constraint-violation lower bounds. Moment matching raises the KL-order and yields finite-horizon bounds.

  • Instance construction: The hard instances use K=[0,1], linear losses, affine constraints, exact gradients, and i.i.d. Gaussian value noise.
  • Instance construction: A three-point pair matches mean and variance, while Gaussian convolution reduces its one-round KL divergence to O((s/σ)^8).
  • Higher-order constructions: Consecutive Chebyshev–Gauss laws match the first 2n−1 moments and have KL divergence O((s/σ)^(4n)/(2n)!).
  • Finite-horizon bounds: The finite-horizon testing reduction gives max{expected regret, expected constraint violations} at least sT/[6(n+1)^7].
  • Finite-horizon bounds: The reduction represents learner observations as noisy i.i.d. signals whose laws do not depend on the strategy, enabling a two-point change-of-measure argument.
  • Finite-horizon bounds: Randomized oblivious instances yield deterministic-instance lower bounds by extracting a realization attaining the maximum term.

B.4 Proofs of Theorems 3.1 and 3.2 and Proposition 3.3

The proofs select noise scales and moment-matched distributions so that indistinguishability persists over the horizon while feasible comparators remain separated. The resulting bounds cover growing-order logarithmic constructions and a simpler constant-order lower bound.

  • Theorem 3.1: Theorem 3.1 applies the general lower-bound proposition to a three-point pair with a fourth-order first unmatched moment and eighth-order KL scaling.
  • Theorem 3.2: The Chebyshev–Gauss proof separates feasible comparators through interlacing while preserving high-order moment matching and small Gaussian-convolution KL.
  • Theorem 3.2: Theorem 3.2 chooses n(T) by (2n)!16^n ≥ 12(n+1)^6T, yielding s=min{σ,1}/2 and lower bound min{σ,1}T/[12(n(T)+1)^7].
  • Theorem 3.2: The order parameter satisfies n(T)≤⌈log T⌉+3 and asymptotically n(T)=O(log T/log log T).
  • Proposition 3.3: Proposition 3.3 uses two constant constraints whose observation laws have KL Ts^2/(2σ^2)=1/128, producing a regret–hard-violation lower bound of order σT.
  • Scope of the proofs: The lower-bound construction relies on Gaussian supersmoothness; other bounded-noise models require separate endpoint analysis.

D LEDGER: regret and budget analysis

The analysis connects the discounted dual recursion to a reflected random walk, showing that geometric discounting preserves a constant fraction of the maximum windowed violation while introducing a stated worst-case factor.

  • Discounted dual recursion: Geometric discounting retains a horizon-uniform fraction of the best-window sum when γ^T is bounded below.The proof uses the reflected-recursion representation and Abel summation.
  • Windowed violation: The recursion identifies windowed violation with the running maximum of a reflected random walk over signed observed consumption.This links the algorithmic balance process to the classical Lindley recursion.
  • Discounted dual recursion: The maximum realized dual value can exceed the discounted lower-bound prediction by more than the factor γ^(T−1).The discount factor is therefore a worst-case lower bound rather than a tight characterization of every realization.

D.2 Proof of the LEDGER guarantee

The proof combines primal projected-gradient analysis with a regularized dual recursion, then controls the running maximum pathwise and transfers observed-value bounds to true budget violation.

  • Primal–dual analysis: The primal update is projected gradient descent, while the dual update is projected ascent on a regularized concave quadratic.Conditional unbiasedness makes the observed dual term cancel in expectation with the true constraint term.
  • Moment conditions: Conditional finite variance suffices for the required second moments and direction-noise expectations, without higher-moment assumptions.The proof also gives a pathwise dual bound when value noise is almost surely bounded.
  • Regret bound: The fixed-step analysis yields the regret bound after dropping the nonnegative dual second-moment term and substituting the prescribed step size.The parameter range V ≤ 1 enters through the second-moment control.
  • Budget bound: The violation analysis applies the discounted reflected-recursion lemma to observed levels and then transfers the result from observed to true levels.The discount remains effective over the horizon because γ^(T−1) is bounded below by a constant.
  • Budget bound: The running maximum of the dual variable is controlled before expectation, using pathwise inequalities, martingale maximal bounds, and finite dual second moments.This ordering is essential because the target metric is the expected maximum over windows.
  • Primal–dual analysis: Retaining one quarter of the regularization controls martingale corrections that would otherwise prevent direct bounds on expected positive-part window violations.The proof emphasizes that expectation-level cancellation alone does not control the expected maximum over windows.

E LEDGER: dynamic comparators

The same update supports predictable roundwise-feasible comparator paths without common feasibility, while adaptive-adversary budget control is obtained through an online chasing path and retains a dimension factor.

  • Dynamic comparators: Predictable feasible comparator sequences permit dynamic regret analysis without assuming a common feasible point.The comparator path is an analytical benchmark and need not be observed by the learner.
  • Shortest feasible path: The shortest feasible path is defined by minimizing total movement among paths satisfying every round’s constraint.Its length is zero exactly when the realized feasible sets share a common point, but the minimizing path need not be predictable.
  • Dynamic comparators: The dynamic regret proof replaces the static comparator term with a path-length term and preserves the conditional-unbiasedness argument.The resulting inequality applies to every predictable feasible path.
  • Adaptive adversaries: An online convex-body-chasing selector supplies a predictable feasible path whose movement is bounded by a dimension-dependent competitive ratio times the shortest feasible path.The selector avoids using a hindsight minimizer that may depend on future feedback noise.
  • Limitations: The dimension factor is a limitation of the chosen chasing reduction, and a dimension-free shortest-path budget bound for general adaptive constraints remains open.The cited lower bound for convex body chasing does not establish that the budget metric itself must incur this factor.
  • Limitations: Improving the linear path-length dependence to a square-root dependence while retaining noisy-value budget guarantees remains an open direction.The current result uses a single fixed-step primal update rather than exact-feedback projection or positive-part surrogates.

F.1 Protocol and detailed measurements

The evaluation compares LEDGER with noisy-feedback baselines across stationary and block instances, noise distributions, noise scales, horizons, and V settings. Results illustrate the regret–budget trade-off while emphasizing that finite-horizon measurements do not establish theorem expectation bounds.

  • Protocol: The experiments use stationary and alternating-block instances with noisy value, gradient, and linear-loss feedback, alongside an exact-feedback reference.Configurations initialize all methods identically and include V = 1, V = T^-1/6, and V = T^-1/2 for LEDGER.
  • Protocol: Table 3 reports T = 10^6, σ = 0.3 medians over 20 seeds, with separate regret, hard-violation, and budget-violation metrics.Negative regret denotes improvement over the best fixed feasible action; the three LEDGER rows correspond to the three V settings.
  • Scaling and limitations: Fitted finite-horizon regret-magnitude slopes are 0.46 for V = 1 and 0.69 for V = T^-1/6, while endpoint regret slopes are about 1.00 and 1.03 across instances.These slopes use absolute regret and do not establish worst-case rates or bounds on signed regret.
  • Noise robustness: Student-t3 noise with the same standard deviation gives similar LEDGER medians to Gaussian noise, while the noise-scale sweep shows larger budget violations for balanced settings as σ increases.The reported trends are consistent with the finite-variance guarantee, but measured violations need not increase monotonically with noise.

F.2 Additional results and discussion

Finite-horizon experiments illustrate LEDGER’s separation of hard and budget violation, its regret–budget tradeoff across V, and behavior under finite-variance noise. These measurements support the theoretical patterns but do not verify expectation bounds statistically.

  • Metric separation: LEDGER’s budget-violation slopes are 0.50 and 0.42 while hard-violation slopes are 0.98 and 0.95 on the blocks instance at V = 1 and V = T^-1/6.At V = T^-1/2, stronger budget control comes with positive regret 161 836 and fitted regret slope 1.03.
  • Lower-bound constructions: At n = 3 and T = 10^6, LEDGER’s larger mean hard violation is about 0.45σT at V = 1 and 0.10σT at V = T^-1/6, while budget violations are 6 868 and 854 in world P3.Budget violation grows much more slowly than hard violation on these lower-bound instances.
  • Stationary instance: On the stationary instance, the naive plug-in reaches regret about 0.26T and median WCVT approximately 71 813, whereas LEDGER substantially reduces regret at V = 1 and V = T^-1/6.The plug-in’s zero terminal overspend coexists with substantial earlier-window overspend.
  • Tradeoff parameter: At T = 10^6, moving from V = 1 to V = T^-1/6 divides median budget violation by 7.3, from 5 391 to 737, while regret moves from -1 151 to 10 386.Continuing to V = T^-1/3 gives budget violation 181 and regret 108 358; the endpoint V = T^-1/2 yields budget violation 0.054 and regret 245 203.
  • Normalized comparisons: Across the tested horizons, normalized median regret rises from 0.75 to 1.08 while normalized budget violation falls from 1.06 to 0.17.These are finite-horizon median comparisons, not statistical verification of the theorem’s expectation bounds.
  • Noise distributions: Similar LEDGER performance under Gaussian and Student-t3 noise supports practical relevance of the finite-variance guarantee on the tested instances.The experiments focus on static-comparator guarantees; dynamic path-length bounds remain a direction for further experiments.
Loading 2609.06921v1…