- Rating
- 3
- Confidence
- 4
- Informativeness
- 3
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The paper studies online convex optimization when constraint values and first-order feedback are noisy. It assumes conditionally finite-variance observations of constraint values. It compares three ways of measuring violations: adding up the positive violation on every round, measuring the signed budget at the end, and taking the largest signed-budget violation over any time window. The comparison is against a fixed feasible action on every round.
The paper proves a near-linear lower bound for joint regret and roundwise hard violation. It also shows that square-root regret requires budget violation of at least order \sqrt{T}logT when noise is fixed and positive. Its algorithm, LEDGER, matches this horizon dependence: expected regret (O(\sqrt{T}) and expected maximum-window violation (O(\sqrt{T} logT). LEDGER combines clipping, a reflected queue, a suitable potential, and an adaptive regularizer.
Critical strengths
-
The lower and upper bounds explain a meaningful difference between the violation measures. The hard-violation construction shows why noisy constraint values make it difficult to control positive violations on every round. Proposition 3.2 shows that terminal violation alone requires the logarithmic penalty under square-root regret. Together with Theorem 4.1, these results give a clear account of what is achievable for fixed problem parameters.
-
The analysis handles the difficulties caused by finite-variance noise. The algorithm allows feedback components within a round to be dependent, handles the queue's reflection boundary, and avoids assuming a two-sided bound on constraint values. It also accounts explicitly for clipping, regularization, and the noise martingale when transferring the queue bound to true violation.
Critical weaknesses
Two limitations affect the significance of the result. The matching rates concern horizon dependence for fixed parameters and positive noise; they do not establish sharp dependence on all parameters at once. Also, the finite-horizon constants can be too large to be useful. Appendix C.6 gives a bound of about 61,795 while the trivial bound is 10,000. The authors acknowledge both limitations. The results should therefore be presented as asymptotic guarantees, without suggesting that they provide useful safety certificates at moderate horizons.
Questions for authors
-
Appendix C.6 gives a bound of about 61,795 where the trivial bound is 10,000. Using the existing analysis, at roughly what horizon does the bound first improve on the trivial one for the same parameters? Which terms account for most of the gap? This would help me judge whether the result has useful finite-horizon implications in addition to its asymptotic contribution.
-
The matching claim is stated for fixed positive noise. Could you place the lower and upper bounds side by side with their noise dependence explicit, and identify the regimes in which they match or leave a gap as noise decreases with the horizon? This would help clarify how broadly the optimality claim should be read.
-
Could the authors identify the specific step in the maximum-window proof that cannot be obtained by directly combining the cited adaptive-regularization method with a standard reflected-queue and martingale argument? In particular, which obstacle requires the choice of potential or the treatment of clipping? A precise comparison would help me assess the depth of the technical contribution.